Introduction to the F# programming language

Yesterday after reading the post YAPES: Problem Five at Dustin Campbell's site Did it with .NET, I was motivated to download the F# compiler bits. I've been keeping track of the news related to this new programming language but still hadn't felt a strong desire to play with it. There are so many new technologies emerging that you sometimes don't know where to focus your attention. Read the post The "Driving Force" pattern--part 1 of N so that you get a glimpse of what I'm expressing here.

This time I couldn't resist and so I'm really going to study this new language. Why have I decided to do so? It's because F# is a simple yet powerful new programming language that let's you express your thinking process in a more convenient way. By looking at the solutions presented in Dustin's posts you can have a taste of the power of F#.

F# is based on principles of functional programming although it's a mix of the different flavors of programming paradigms. That's because it targets .NET Framework. This way it is a multi-paradigm programming language with concepts of imperative and object-oriented programming disciplines.

ApressExpertFSharpDec2007

The language is being developed at Microsoft Research. The folks behind the language plans to ship it with the next version of Visual Studio according to Somasegar's post F# - A Functional Programming Language. In the near future F# will be a real citizen of the .NET family of programming languages.

To me it's a completely new experience. I'm already familiarized with the new language extensions of C# like generics, lambda expressions and anonymous functions that bring to C# some of the concepts initially developed and implemented in functional programming languages. The ones mentioned here are a few language constructs if compared to the whole gamma of new functional language constructs that I must learn. There are plenty of them that I haven't seen in practice before. I'm really excited about what I'll learn on the next days and months.

OK, after a brief story it's time to show how you can start playing around with F# too.

Download F#
Go to the F# download page and get the .msi or .zip package. You can use Windows or Linux (Mono) to develop F# programs.

The package brings the F# compiler and a F# project template and debugger to be used within Visual Studio. Yes, although F# is new it has already gotten into Visual Studio. You get a lot of cool features using VS integrated development environment. The only drawback is that you need a paid full featured version of Visual Studio. Visual Studio Express editions aren't good to go. Check why in this thread about F# with Visual Studio Express.

I searched the internet and found a solution in the case you don't have a paid version of Visual Studio and want to use the VS IDE to get type checking and debugger warnings. You can follow the instructions of the post Do it yourself: Visual F# Express 2008. Basically you'll download a Visual Studio IDE that accepts add-ins but this IDE doesn't include the other .NET language as C# and VB.NET. I didn't try it because the download is big (316 MB) if you take into account that I still use a dial-up connection.

Final notes
One of the most interesting things of working in the technology arena is the velocity in which things are developed and shipped to the market. It appears that all the research done on the 70s are becoming real products today. This is because in the past there wasn't the opportunity of breaking barriers like we have today as getting in touch with people from anywhere in the world. We didn't have access to top technologies ten years ago. After the internet everything is more democratic and that's what makes the technology field one of the best to work on. You have the possibility of spreading to the world your new discoveries and they get to reality much faster. If you haven't read Somasegar's post I linked above, do so and you'll see what I mean.

References
F# site at Microsoft Research
http://research.microsoft.com/fsharp/fsharp.aspx

Don Syme's WebLog on F# and Other Research Projects - The guy behind the curtains
http://blogs.msdn.com/dsyme

Chris Smith's completely unique view on F#, more F#, and maybe other stuff
http://blogs.msdn.com/chrsmith

Brian's random thoughts about writing code for .NET
http://lorgonblog.spaces.live.com/

Jomo Fisher -- Sharp Things
http://blogs.msdn.com/jomo_fishe

LukeH's WebLog
http://blogs.msdn.com/lukeh

Books
Expert F# by Don Syme, Adam Granicz and Antonio Cisternino
Foundations of F# by Robert Pickering

Hello World Web Site with ASP.NET MVC

Hello World
A "hello world" application prints out "Hello, world!" on the screen. It is used in many introductory tutorials for teaching a programming language or upcoming technology. Such a program is typically one of the simplest programs possible in a such language or specific technology.

ASP.NET
ASP.NET
is a web application framework developed and marketed by Microsoft, that developers can use to build dynamic web sites, web applications and web services. It was first released in January 2002 with version 1.0 of the .NET Framework, and is the successor to Microsoft's Active Server Pages (ASP) technology. ASP.NET is built on the Common Language Runtime, allowing programmers to write ASP.NET code using any supported .NET language.

MVC
Model-View-Controller (MVC) is an architectural pattern used in software engineering. Successful use of the pattern isolates business logic from user interface considerations, resulting in an application where it is easier to modify either the visual appearance of the application or the underlying business rules without affecting the other. In MVC, the Model represents the information (the data) of the application and the business rules used to manipulate the data, the View corresponds to elements of the user interface such as text, checkbox items, and so forth, and the Controller manages details involving the communication to the Model of user actions such as keystrokes and mouse movements.

In detail what happens in the Model-View-Controller pattern is:

  • Browser requests URL
  • Route is determined
  • Controller is activated
  • Method on Controller is invoked
  • Controller does some stuff
  • Controller renders the View, passing in ViewData

Hello World Web Site
This Web Site basically displays a "Hello, [Name]" message. The variable "Name" receives the data that is passed in the URL to the HelloWorldController action method. The action method will store the URL data in the Controller's ViewData object. The ViewData object will then be used when the View is rendered. It'll be more clear after you implement the code.

Note: I'm not using database interaction (database Model), so the Model part of the MVC pattern isn't created.

I'll show you the steps I used to get an ASP.NET MVC Web Site running with Microsoft Visual Web Developer 2008 Express Edition.

It's important to note that the current version of ASP.NET MVC is the ASP.NET MVC Preview 2. This version wasn't planned to be used with Visual Web Developer Express, so it's necessary to use an adapted project template to get it going properly.

Stuff to download
In order to get the necessary software parts you should install the following if you still haven't them.

  1. Microsoft Visual Web Developer 2008 Express Edition
  2. ASP.NET MVC Preview 2
  3. ASP.NET 3.5 Extensions Preview
  4. ASP.NET MVC Project template

It's mandatory that you install all the above software to avoid erros when debugging the web site. I've run into errors just because I hadn't the ASP.NET 3.5 Extensions Preview, so do install everything.

Implementing the Hello World Web Site
Open Visual Web Developer and go to menu File - New Web Site. On the New Web Site dialog window, select your language of preference according to the ASP.NET MVC Project Template you selected above. This option can be selected on the combo box related to Language. If you don't change the language you won't see the project template. Give the Web Site the name HelloWorldMvcWebSite.

VWDEXHelloWorldASPNETMVCNewWebSite

The project structure is different from the one of a Web Application that is only available on paid versions of Visual Studio Web Developer that is included in Microsoft Visual Studio Standard and Microsoft Visual Professional.

The following is the the structure you get when a new ASP.NET MVC Web Site is created:

VWDEXHelloWorldASPNETMVCSolutionExplorer

Creating a new Controller
Let's create a new Controller called HelloWorld. To accomplish this, right-click on the file HomeController.cs and select Copy. Right-click on the folder Controls and select Paste. You'll have a new file called Copy of HomeController.cs. Right-click on this file and rename it to HelloWorldController.cs. Open this file and change its content so that it looks like the following:

public class HelloWorldController : Controller
{
  [ControllerAction]
  public void HiThere()
  {
    RenderView("HelloWorld");
  }
}

Creating a new View
Let's create a new View that will render the data. To accomplish this, right-click on the folder Views and select New Folder. Give the new folder the name HelloWorld. Now right-click on the file Index.aspx and select Copy. Right-click on the folder HelloWorld and select Paste. You'll have a new file called Index.aspx inside the HelloWorld folder. Right-click on this file and rename it to HelloWorld.aspx. Open this file and change its content so that it looks like the following:

<%@ Page Language="C#" AutoEventWireup="true" CodeFile="HelloWorld.aspx.cs" Inherits="views_Home_Index" %>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head id="Head1" runat="server">
    <title>Hello World ASP.NET MVC Application</title>
</head>
<body>
    <form id="form1" runat="server">
    <div>
         <h1>Hello, <%= ViewData["Name"] %></h1>
    </div>
    </form>
</body>
</html>

Configuring the routes on the Global.asax file
The routes map the URL to the proper action method defined within the Controller.

An action method called HiThere was created inside the HelloWorldController. This method is responsible for invoking the RenderView method that then will render the View (HelloWorld.aspx).

To the above described take effect it's necessary that the proper routing (mapping rules from URLs to action methods) be configured when the application starts.

Open the file Global.asax and change its content so that it looks like the following:

<%@ Application Language="C#" %>
<%@ Import Namespace="System.Web.Mvc" %>

<script RunAt="server">

  void Application_Start(object sender, EventArgs e)
  {
    // Code that runs on application startup
    RouteTable.Routes.Add(new Route
    {
      Url = "[controller]/[action]/[id]",

      Defaults = new { action = "HiThere", id = (string)null },

      RouteHandler = typeof(MvcRouteHandler)
    });

    RouteTable.Routes.Add(new Route
    {
      Url = "Default.aspx",

      Defaults = new { controller = "Home", action = "Index", id = (string)null },

      RouteHandler = typeof(MvcRouteHandler)
    });
  }

  void Application_End(object sender, EventArgs e)
  {
    //  Code that runs on application shutdown
  }

  void Application_Error(object sender, EventArgs e)
  {
    // Code that runs when an unhandled error occurs
  }

  void Session_Start(object sender, EventArgs e)
  {
    // Code that runs when a new session is started
  }

  void Session_End(object sender, EventArgs e)
  {
    // Code that runs when a session ends.

    // Note: The Session_End event is raised only when the sessionstate mode

    // is set to InProc in the Web.config file. If session mode is set to StateServer

    // or SQLServer, the event is not raised.
  }

</script>

The structure of the Web Site must be like the following in the end:

VWDEXHelloWorldASPNETMVCSolutionExplorerEnd

Starting the debugger
Now hit F5. The Web Site will appear in a new web browser window with the following URL: http://localhost:1717/HelloWorldMvcWebSite/

A message of Welcome will be displayed since the page Index.aspx is the Start Page.

Type the following address: http://localhost:1717/HelloWorldMvcWebSite/HelloWorld/

A "Hello,", message is shown. The HelloWorld Controller is being called according to the route table defined above. The default method is HiThere with its id parameter set to null. That's why the View (HelloWorld.aspx) is showing a "Hello, " message. Since an id isn't being passed the only message shown is "Hello, ".

Typing the following address: http://localhost:1717/HelloWorldMvcWebSite/HelloWorld/HiThere/Leniel

A "Hello, Leniel" message is shown. This time the URL conforms with the route that was defined inside the Global.asax file, that is:

Url = "[controller]/[action]/[id]"

These are the assignments done when the routing system detects a URL like the one above:

controller = HelloWord action = HiThere id = Leniel

Final notes
There is no doubt that the ASP.NET MVC Framework turns the life more clean and simple.

It's always good to work in an organized environment. Separating the code related to data base interaction (Model), business logic (Controller) and Presentation/UI (View) is perfect.

Not so long ago, the programming environment was a mess wit lots of event handlers mixed with data base interactions and UI code. It was really difficult to manage all that mess. But thanks God things are getting better as it should.

Another great advantage is how the URL routing is done. It translates/conforms well to the naming scheme adopted in a given project. No more unreadable URLs that are difficult to deal with. It lends to a better searchable web site. The website will play friendly with web search crawlers.

References
To get a handful of examples I advise you to check ScottGu's blog. http://weblogs.asp.net/scottgu/archive/tags/MVC/default.aspx http://weblogs.asp.net/scottgu/archive/2007/11/13/asp-net-mvc-framework-part-1.aspx

ASP.NET MVC : The Official Microsoft ASP.NET Site
http://www.asp.net/mvc/

ASP.NET MVC - Building Web Apps without Web Forms
http://msdn.microsoft.com/en-us/magazine/cc337884.aspx

you've been HAACKED
http://haacked.com/

Visual Web Developer Web Site Project
You can get the Hello World MVC Web Site project at: http://leniel.googlepages.com/HelloWorldMvcWebSite.zip

C# Word Permuter-Shifter

On April 23rd I had a job phone interview. The talk was about a Software Development Engineer in Test (SDET) position at Microsoft.

I already blogged about a C# Thread Safe Circular Queue, which was one of the questions of a screen test (prior to a phone interview) I completed on January for the same Microsoft job position.

On this last interview we (me and the Microsoft employee-interviewer) would talk a little bit and then get to the coding questions. It didn't happen as expected. Firstly the Microsoft interviewer tried to call me on my cellphone. I just couldn't hear a word of what he was saying. The sound was very low. Then we decided to start with the coding questions and then on the phone land line we would talk so that he could explain more about the position, etc.

We started a meeting on Microsoft Office Live Meeting. I was asked about a simple and easy question.

The question:

Write a program that changes the position of the words of a given sentence. For example, given the sentence "How are you going" as input, the output should be "are How going you".

Simple, isn't it? I thought that too at the moment.

As you can see, the first and second words change of position and then the third and forth words change of position and so forth.

The interviewer explained that I could write any code. It didn't need to be written with the syntax of a programming language, it could be a pseudocode.

I'm so used to code using code auto-completion (IntelliSense) and the debugger that I just didn't write any good code to solve the question. It was really frustrating. All what I needed to do was clear in my mind but I just couldn't express it. Was that the case of me being nervous? Beats me.

Today I decided about writing a post with a possible solution to this simple programming question. I opened Microsoft Visual Studio C# Express and wrote some code. In just 5 minutes I had a working code that did the job.

There are things in life that are really weird. I passed more than 45 minutes trying to write a pseudocode and then with the help of IntelliSense and debugger catching my mistakes, things flowed flawlessly and rapidly. Why that faster? I don't know how to explain it, maybe because of IntelliSense and the presence of a handy debugger!

For sure the solution I present here isn't the better, but it's a solution and that's what was asked.

Bellow is the code I wrote:

namespace WordPermuter
{
  class Program
  {
    static void Main(string[] args)
    {
      List<string> sentences = new List<string>()
      {
        { "How are you going my dear?" }, // are How going you dear? my
        { "I am going fine honey." } // am I fine going honey
      };
      DoPermutation(sentences);
    }
    static void DoPermutation(List<string> sentences)
    {
      foreach(string sentence in sentences)
      {
        // Split the sentence when it reaches a white space
        var splitted = sentence.Split(' ');
        // Increment the counter on a scale of 2
        for(int i = 0; i < splitted.Length; i = i + 2)
        {
          if(i < splitted.Length - 1)
          {
            var aux = splitted[i];
            splitted[i] = splitted[i + 1];
            splitted[i + 1] = aux;
          }
        }
        foreach(var str in splitted)
          Console.Write(str + " ");
        Console.WriteLine();
      }
    }
  }
}

What's the purpose of this code? Aha... It isn't the code itself but what approach you took to get to a solution. The interviewer wants to see how is your thinking process. No matter if you coded it wrong, but at least you should show something. As the recruiters always say: "Think it loud so that we can help you."

After a solution has been presented, the interviewer will probably ask you what if questions. What if I did this way? What If I did that way? What is the breach? What are the possible bugs?... The list of possible questions is innumerable.

I think my solution is OK! If you find any bug, please tell me.

Win32 API Mouse interaction

Windows API
The Windows API, informally WinAPI, is Microsoft's core set of application programming interfaces (APIs) available in the Microsoft Windows operating systems. All Windows programs except console programs must interact with the Windows API regardless of the language.

Win32 API
The Win32 API is the 32-bit API for modern versions of Windows. The API consists of functions implemented, as with Win16, in system DLLs. The core DLLs of Win32 are kernel32.dll, user32.dll, and gdi32.dll. Win32 was introduced with Windows NT.

Words of wisdom
Dealing with the Win32 API appears to be a regression since it takes us to the last century, that is, when programming with such API we are writing code that resembles the code written 15 years ago or more. Regression was the feeling I felt when the teacher said we'd study this API. Nevertheless, there are billions of lines of code that need maintenance because great part of these lines are used in legacy systems. So you see that learning this API is fundamental even today. This is in contrast with the mainframe computers dilemma. Even today there are a bunch of companies that still use them because of legacy systems. The feeling of regression was substituted by a enthusiasm one in the end.

Mouse interaction app
One coursework related to the Object Oriented Systems discipline I had to develop was a program that draws on the screen by free hand with the mouse assistance. The program must monitor the mouse movement, indicating its position (x, y) in the upright corner of the application window, in the format (xxx, yyy). Pressing the left mouse button it draws and pressing the right mouse button, it wipes off the screen content.

Some valuable tips that the teacher gave:
Use the events WM_MOUSE, WM_LBUTTONDOWN, WM_LBUTTONUP, WM_RBUTTONDOWN, WM_RBUTTONUP and the function SetPixel()

lword(lParam) has 0 x
hiword(lParam) has 0 Y

I originally implemented this program using DevC++. Today while composing this post I just created a new Win32 Project application using the Microsoft Visual Studio C++ Express Edition. Although the implementation differs a little bit, it wasn't difficult to port it to the Microsoft programming environment. I'll provide both implementations at the end of the post.

Let's see the mouse app main block of code. It's inside the WndProc function that is responsible for processing the messages for the main window. The code is commented so I think it's unnecessary to add more to it.

//
// FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
// PURPOSE: Processes messages for the main window.
//
// WM_COMMAND - Process the application menu
// WM_PAINT - Paint the main window
// WM_DESTROY - Post a quit message and return
// WM_LBUTTONDOWN - Left mouse button clicked
// WM_RBUTTONDOWN - Right mouse button clicked
// WM_LBUTTONUP - Left mouse button released
// WM_RBUTTONUP - Right mouse button released
// WM_MOUSEMOVE - Controls the mouse movement
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;

switch(message) //Handle the messages
{
case WM_DESTROY:

PostQuitMessage(0); // Send a WM_QUIT to the message queue

break;

case WM_PAINT:
// TODO: Add any drawing code here...
hDC = GetDC(hWnd);

BeginPaint(hWnd, &paintStruct);

EndPaint(hWnd, &paintStruct);

break;

// Left button event used to print the screen
case WM_LBUTTONDOWN:

flag = true;

// Black color
newColor = RGB(0, 0, 0);

xMouse = LOWORD(lParam);

yMouse = HIWORD(lParam);

SetPixel(hDC, xMouse, yMouse, newColor);

break;

// Right button event used to erase the screen content
case WM_RBUTTONDOWN:

flag = true;

// White color
newColor = RGB(255, 255, 255);

xMouse = LOWORD(lParam);

yMouse = HIWORD(lParam);

SetPixel(hDC, xMouse, yMouse, newColor);

break;

// Sets the flag to false so that we know the left mouse button was released
case WM_LBUTTONUP:

flag = false;

break;

// Sets the flag to false so that we know the right mouse button was released
case WM_RBUTTONUP:

flag = false;

break;

// Controls the mouse movement and shows its current position on the Window title
case WM_MOUSEMOVE:

if(flag)
{
xMouse = LOWORD(lParam);

yMouse = HIWORD(lParam);

SetPixel(hDC, xMouse, yMouse, newColor);

sprintf_s(strTitle, " x=%d y=%d", xMouse, yMouse);

SetWindowText(hWnd, strTitle);

SetWindowText(hlabel, strTitle);
}
else
{
xMouse = LOWORD(lParam);

yMouse = HIWORD(lParam);

sprintf_s(strTitle, " x=%d y=%d", xMouse, yMouse);

SetWindowText(hWnd, strTitle);

SetWindowText(hlabel, strTitle);
}

break;

case WM_COMMAND:
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
// Parse the menu selections:
switch(wmId)
{
case IDM_ABOUT:

DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);

break;

case IDM_EXIT:

DestroyWindow(hWnd);

break;

default:

return DefWindowProc(hWnd, message, wParam, lParam);
}

break;

default: // For messages that we don't deal with

return DefWindowProc (hWnd, message, wParam, lParam);
}

return 0;
}

Reference
To get more insight regarding the Win32 API, go to the Win32 Development site at the Microsoft Development Network: http://msdn.microsoft.com/en-us/library/aa139672.aspx

Dev-C++ and Visual Studio Projects
DevC++ project
http://leniel.googlepages.com/Win32APIMouseInteractAppDevCPlusPlus.zip

Visual Studio Win32 project
http://leniel.googlepages.com/Win32APIMouseInteractAppVCPlusPlus.zip

Source code Indenter-Capitalizer

Following the coursework related to the Compilers Construction discipline I attended during the Computer Engineering course, I was asked to indent and capitalize the reserved words (keywords) of a source code file. More specifically, to do this work I should use the Syntactic Analyzer built with Flex and YACC that was created in a previous coursework task.

The source code file in question is the one being analyzed by the syntactic analyzer. This way at the same time it analyses the syntactic structure of the file it also indents and capitalizes the keywords.

The following is the content of the syntactic analyzer file named sinan.yacc:

%{
   #include <stdio.h>
   #include <stdlib.h>

   int c;
%}

%token PROGRAM
%token ID
%token SEMIC
%token DOT
%token VAR
%token COLON
%token INTEGER
%token REAL
%token RCONS
%token BOOL
%token OCBRA
%token CCBRA
%token IF
%token THEN
%token ELSE
%token WHILE
%token DO
%token READ
%token OPAR
%token CPAR
%token WRITE
%token COMMA
%token STRING
%token ATRIB
%token RELOP
%token ADDOP
%token MULTOP
%token NEGOP
%token CONS
%token TRUE
%token FALSE

%%

prog : PROGRAM {printf("PROGRAM "); c = 0;}

       ID {printf("%s", yytext);}

       SEMIC {printf(";\n\n");}

       decls

       compcmd

       DOT {printf(".");}
       {
         printf("\n Syntactical Analisys done without erros!\n");

         return 0;
       }
     ;

decls : VAR {printf("VAR ");} decl_list

      ;

decl_list : decl_list decl_type
            decl_type
          ;

decl_type : id_list COLON {printf(":");} type SEMIC {printf(";\n");}
          ;

id_list : id_list COMMA {printf(", ");} ID {printf("%s", yytext);}
          ID {printf("%s", yytext);}
        ;

type : INTEGER {printf(" INTEGER");}
       REAL {printf(" REAL");}
       BOOL {printf(" BOOL");}
     ;

compcmd : OCBRA {int i; for(i = 0; i < c; i++)printf(" "); printf("{\n"); c = c + 2;} cmd_list CCBRA {printf("\n"); int i; for(i = 2; i < c; i++)printf(" "); printf("}"); c = c - 2;}
        ;

cmd_list : cmd_list SEMIC {printf(";\n\n");} cmd
           cmd
         ;

cmd : {int i; for(i = 0; i < c; i++)printf(" ");} If_cmd
      {int i; for(i = 0; i < c; i++)printf(" ");} While_cmd
      {int i; for(i = 0; i < c; i++)printf(" ");} Read_cmd
      {int i; for(i = 0; i < c; i++)printf(" ");} Write_cmd
      {int i; for(i = 0; i < c; i++)printf(" ");} Atrib_cmd
      compcmd
    ;

If_cmd : IF {printf("IF ");} exp THEN {printf(" THEN\n");} cmd Else_cmd
       ;

Else_cmd : ELSE {printf("\n"); int i; for(i = 0; i < c; i++)printf(" "); printf("ELSE\n"); c = c + 2;} cmd {c = c - 2;}

         ;

While_cmd : WHILE {printf("WHILE ");} exp DO {printf(" DO\n");} cmd
          ;

Read_cmd : READ {printf("READ");} OPAR {printf("(");} id_list CPAR {printf(")");}
         ;

Write_cmd : WRITE {printf("WRITE");} OPAR {printf("(");} w_list CPAR {printf(")");}
          ;

w_list : w_list COMMA {printf(", ");} w_elem
         w_elem
       ;
w_elem : exp
         STRING {printf("%s", yytext);}
       ;

Atrib_cmd : ID {printf("%s ", yytext);} ATRIB {printf("= ");} exp
          ;

exp : simple_exp
      simple_exp RELOP {printf(" %s ", yytext);} simple_exp
    ;

simple_exp : simple_exp ADDOP {printf(" %s ", yytext);} term
             term
           ;

term : term MULTOP {printf(" %s ", yytext);} fac
       fac
     ;

fac : fac NEGOP {printf(" %s", yytext);}
      CONS {printf(" %s", yytext);}
      RCONS {printf(" %s", yytext);}
      OPAR exp CPAR
      TRUE {printf("TRUE ");}
      FALSE {printf("FALSE ");}
      ID {printf("%s", yytext);}
    ;


%%

#include "lex.yy.c"

As you can see there is an integer variable named c right beneath the #include section. This variable is incremented and decremented according to the section of code being analyzed (parsed). Such variable is then used inside the for loops. According to its current value blank spaces are written on the screen so that the next token parsed is printed on the right position (indented).

Each keyword parsed is capitalized and printed on the screen through a simple printf command.

Let's run a simple test case with the following source code file named test.txt. The code is intentionally not indented and it doesn't do much. It's just for a testing purpose.

program factorial;

var n, fact, i: integer;
{
read(n);

fact = 1;

i = 1;

while i <= n do
{
fact = fact * i;

i = i + 1
};

if i >= fact then
{
i = fact;

fact = fact + 1
}
else
i = fact + 1;



if i < fact then
{
i = fact;

fact = fact + 1
};

write("The factorial of ", n, " is: ", fact)
}.

In blue are the keywords, so the output should present them in CAPITALIZED letters. The blocks of code should also be presented with indentation according to the logic specified above. I use 2 white spaces to indent the blocks of code. That's why I use c = c + 2 (to increment) and c = c - 2 (to decrement) the c variable is responsible for controlling the indentation.

To run the test case it's necessary to build the syntactic analyzer. I won't show here all the steps involved since it's already done in the paper described in the post Syntactic Analyzer built with Flex and YACC. So I'll just compile the sinan.yacc file since it's the only file that was modified to accomplish this task. The other necessary files to generate the executable file - such as the lexical analyzer ones - are included in the download package at the end of this post.

For a better understanding of the commands used in this post and to set up the development environment I recommend that you read at least section 3.3 of the paper Syntactic Analyzer built with Flex and YACC. That said, let's do the job. :-)

To run this test case, follow the steps listed bellow:

  1. Create a folder called IndentCapCode on the root directory C:\, which will contain all the files created henceforward.
  2. Open a command prompt and type: path=C:\MinGW\bin;%PATH%. I consider that the MinGW installation was done in the folder C:\MinGW. Change it accordingly. After completing this step the tools to build the syntactic analyzer will be available in the command prompt.
  3. Generate the file y.tab.c in the command prompt with following command: yacc sinan.yacc.
  4. Compile the files with GCC in the command prompt with the following command: gcc y.tab.c yyerror.c main.c -osinan -lfl.

The result file for the syntactic analyzer is sinan.exe. To use it just type sinan < test.txt. The file test.txt contains the source code to be analyzed by the syntactic analyzer.

You can see the commands listed above in action through the following screenshot:

In a next post related to compilers construction I'll show the implementation of a semantic analyzer. This implementation was another coursework task. I used the same principle shown here to indent the code and even to colorize the keywords. But this is for another day.

You can get the .ZIP package that contains the files used in this post: http://leniel.googlepages.com/CodeIndenterCapitalizerFlexYACC.zip

Note: if you want, you can use a batch file (.bat) to automate the steps listed above. A .bat file named ini.bat is included in the .ZIP package. For more information about batch files, read my previous post Programming-Constructing a Batch file.

Thread Safe Circular Queue in C#

While completing a screen for a Software Development Engineer in Test (SDTE) position for Microsoft I had to implement a thread safe circular queue.

The question was the following:

Implement a circular queue of integers of user-specified size using a simple array. Provide routines to initialize(), enqueue() and dequeue() the queue. Make it thread safe. A really good observation was: Please do not to use existing class libraries for this question. Thanks!

My first attempt was obviously get more information about a circular queue and bring it back to my mind. That's because I had studied it a long time ago when I was in the beginning of the computer engineering course. If you don't use it you forget it. That's the truth.

This post aims to present an implementation of a thread safe circular queue in C#. I won't deal with theory. For theory, I advise you to read the Wikipedia article about circular queue (buffer) to get started.

I reused some code from the links I present in the references section at the end of this post.

I'll break down the code I implemented so that you can go through the functions that were asked in the problem statement.

class ThreadSafeCircularQueue
{
  private int[] queue;
  private int head;
  private int tail;
  private int length;

  static Object thisLock = new Object();

  public CircularQueue()
  {
     Initialize();
  }

  ...
}

The class ThreadSafeCircularQueue has five properties: an integer array (the queue) and the queue's head, tail and length. A static object thisLock is used to make the queue thread safe.

private void Initialize()
{
  head = tail = -1;

  Console.Write("Circular Queue size: ");

  string length = Console.ReadLine();

  this.length = int.Parse(length);

  queue = new int[this.length];
}

The function Initialize() does what its name means. The queue's head and tail are set to appropriate values and the user has the opportunity of specifying the queue's size (length) by entering an integer value. A new queue is then created and has the user specified size.

The Enqueue() and Dequeue() functions shown bellow do the hard work, that is, they control all the circular queue functionality.

The Enqueue() function receives an integer value to be enqueued. Note the use of the thisLock variable. It is used so that we get thread safety, that is, all the code section inside the lock statement can't be executed by two threads at the same time. This avoids the problem of two concurrent threads trying to access the queue data structure simultaneously. If it's not controlled in the source code level we can get invalid values in the queue what could lend to a corrupted queue. That's not what is expected. When the code section that is inside the lock statement is being executed by a thread and other thread reaches the same section of code, this second thread waits till the first thread exits such code section. This way the queue has a valid set of values and its data is maintained secure.

Firstly is checked if the queue is full. It is full when it's head points to index 0 and its tail points to length - 1 or when its tail + 1 equals the same value of head. Remember that it is a circular queue.

In case the queue is full a message is shown to the user. If it still has room we check if the "end" of the queue (tail) that points to the last element has an index of length minus 1. If it is then the tail will now point to the the "start" of the queue. The other possibility is to increment the tail variable. The position referenced by the tail variable is then used to enqueue the value parameter into the queue. Then the just enqueued value is printed in the screen. A check is done to verify if the head variable has a value of -1. If it's the case then head will point to index 0.

private void Enqueue(int value)
{
  lock(thisLock)
  {
    if((head == 0 && tail == length - 1)  (tail + 1 == head))
    {
      Console.WriteLine("Circular queue is full.");

      return;
    }
    else
    {
      if(tail == length - 1)
        tail = 0;
      else
        tail++;

      queue[tail] = value;

      Console.WriteLine("In -> {0}", value);
    }

    if(head == -1)
      head = 0;
  }
}

The Dequeue() function also uses the lock statement because it must be a thread safe function.

Firstly is checked if the queue's head points to -1. Remember that in the Initialize() function when the queue is initialized its head and tail variables are set to -1. If head has a value of -1 then the queue is empty and the user is informed about that. A value of -1 is returned to conform with the function signature that needs to return an integer value.

If the queue is not empty the integer variable v receives the value that is indexed in the queue's head position. The value 0 is then assigned to the position that was just dequeued.

Now it's necessary to update the head position inside the queue. To accomplish that it's checked if head is equal tail, if it is, then head = tail = -1. This last operation states that the queue is empty after the dequeue operation. Else it's checked if head is equal length - 1. If it is the case then head receives 0. The last possible condition increments the value of head. In the end the value being dequeued (v) is printed in the screen.

Printing the values in the screen is a good way of keeping track of what is going on while the program is running.

private void Dequeue()
{
  lock(thisLock)
  {
    int value;

    if(head == -1)
    {
      Console.WriteLine("Circular queue is empty.");

      value = -1;
    }
    else
    {
      value = queue[head];
      queue[head] = 0;

      if(head == tail)
        head = tail = -1;
      else
        if(head == length - 1)
          head = 0;
        else
          head++;
    }

    Console.WriteLine("Out -> {0}", value);
  }
}

Now take a look at the Show() function bellow. Again the lock is present. Why? In an instant you'll get to the point. Hold your horses! :-)

A check is done to verify if the queue is empty. If it is the case the callee function just returns to the caller function. If it is not the case we proceed to show the values already present in the queue. If tail is less than head a for loop starting in 0 and ending in length - 1 iterates the queue and each value is written in the screen. Otherwise a for loop starting in 0 end ending in tail iterates the queue and each value is written in the screen.

private void Show()
{
  lock(thisLock)
  {
    int i;

    if(head == -1)
    {
      Console.WriteLine("Circular queue is empty.");

      return;
    }
    else
    {
      if(tail < head)
      {
        //for(i = head; i <= size - 1; i++)
        for(i = 0; i <= length - 1; i++)
          Console.Write("{0} ", queue[i]);
      }
      else
        //for(i = head; i <= tail; i++)
        for(i = 0; i <= tail; i++)
          Console.Write("{0} ", queue[i]);

      Console.WriteLine();
    }
  }
}

The following is the EnqueueDequeue() function responsible for calling the Queue(), Dequeue() and Show() functions. In this function I execute a simple test case and comment the operations being carried out.

public void EnqueueDequeue()
{
  Enqueue(1);
  Enqueue(2);
  Enqueue(3);
  Enqueue(4);
  Show();
  Enqueue(5); // Circular queue is full!
  Dequeue();
  Dequeue();
  Dequeue();
  Dequeue();
  Dequeue(); // Circular queue is empty!
  Dequeue(); // Circular queue is empty!
  Show();
  Enqueue(6);
  Show();
  Enqueue(7);
  Show();
  Dequeue();
  Dequeue();
  Enqueue(8);
  Enqueue(9);
  Show();

  // Supposing a 4 size queue:  0 ¦ 0 ¦ 0 ¦ 0
  //
  //                            1 ¦ 0 ¦ 0 ¦ 0  <- Enqueue 1
  //
  //                            1 ¦ 2 ¦ 0 ¦ 0  <- Enqueue 2
  //
  //                            1 ¦ 2 ¦ 3 ¦ 0  <- Enqueue 3
  //
  //                            1 ¦ 2 ¦ 3 ¦ 4  <- Enqueue 4
  //              
  //                            1 ¦ 2 ¦ 3 ¦ 4  <- Circular queue is full when trying to enqueue 5.
  //
  //                            0 ¦ 2 ¦ 3 ¦ 4  <- Dequeue 1
  //
  //                            0 ¦ 0 ¦ 3 ¦ 4  <- Dequeue 2
  //
  //                            0 ¦ 0 ¦ 0 ¦ 4  <- Dequeue 3
  //                   
  //                            0 ¦ 0 ¦ 0 ¦ 0  <- Dequeue 4
  //
  //                            0 ¦ 0 ¦ 0 ¦ 0  <- Circular queue is empty when trying to dequeue.
  //
  //                            0 ¦ 0 ¦ 0 ¦ 0  <- Circular queue is empty when trying to dequeue.
  //
  //                            6 ¦ 0 ¦ 0 ¦ 0  <- Enqueue 6
  //
  //                            6 ¦ 7 ¦ 0 ¦ 0  <- Enqueue 7
  //
  //                            0 ¦ 7 ¦ 0 ¦ 0  <- Dequeue 6
  //
  //                            0 ¦ 0 ¦ 0 ¦ 0  <- Dequeue 7
  //
  //                            8 ¦ 0 ¦ 0 ¦ 0  <- Enqueue 8
  //
  //                            8 ¦ 9 ¦ 0 ¦ 0  <- Enqueue 9
  //
  // * 0 is set in a position when dequeueing so that it's easier to watch the queue variable.
}

Now the main start thread:

class Program
{
  static void Main(string[] args)
  {
    ThreadSafeCircularQueue circularQueue = new ThreadSafeCircularQueue();

    Thread[] threads = new Thread[10];

    for(int i = 0; i < threads.Length; i++)
    {
      threads[i] = new Thread(new ThreadStart(circularQueue.EnqueueDequeue));
    }

    for(int i = 0; i < threads.Length; i++)
    {
      threads[i].Start();
    }

    Console.ReadLine();
  }
}

As you can see above I declare an object of type ThreadSafeCircularQueue. An array of 10 objects of type Thread is then created. In a for loop I instantiate each Thread passing to it a delegate that represents the method that'll be invoked when the thread begins executing.

In the subsequent for loop I call the Start() method of each thread and they start executing simultaneously, tough they won't concur when accessing the functions Enqueue(), Dequeue() and Show().

Visual Studio C# Console Application
You can get the Microsoft Visual Studio Project and the app executable at: http://leniel.googlepages.com/ThreadSafeCircularQueueCSharp.zip

References
During the research phase of this implementation I recurred to some sites to get more information regarding the circular queue data structure. The following list can provide you a better understanding of such a data structure.

Thread Safety articles
[1] Venners, Bill. Designing for Thread Safety: Using Synchronization, Immutable Objects, and Thread-Safe Wrappers. 1998. Available at <http://www.artima.com/designtechniques/threadsafety.html>. Accessed on April 29, 2008.

[2] Suess, Michael. A Short Guide to Mastering Thread-Safety. 2006. Available at <http://www.thinkingparallel.com/2006/10/15/a-short-guide-to-mastering-thread-safety/>. Accessed on April 29, 2008.

[3] Allen, K. Scott. Statics & Thread Safety: Part II. 2004. Available at <http://www.odetocode.com/Articles/314.aspx>. Accessed on April 29, 2008.

Circular Queue sample code
[4] Kumar, Nunna Santhosh. Circular Queue Implementation using Arrays in C++. Available at <http://www.sourcecodesworld.com/source/show.asp?ScriptID=887>. Accessed on April 29, 2008.

Thread material
[5] Albahari, Joseph. Threading in C#. 2007. Available at <http://www.albahari.com/threading/>. Accessed on April 29, 2008.

Distance Education and IT-Comm Pros

Distance EducationDistance education or distance learning is a positive manner of tackling global education shortcomings. If we think about the world population we can imagine that not everyone has easy access to the resources we’re so accustomed to. Considering time constraints, distance education reveals itself a great alternative because the time spent to get to a classroom can be a negative factor. Think about people that live outside of big cities. They can't even apply for a course they want because there is no such a course where they live. These barriers lessen education availability and so someone somewhere that doesn’t fit on the above time and place prerequisites has their plans thwarted and can't move forward towards the mainstay “Education”. It’s a really beautiful word. Look at it for an instant and realize what would be of you if you didn’t have the basic of it. To those people to acquire a diploma in some area of knowledge can be considered an unthinkable action.

With the advent of the Internet we have today a classroom right inside our own home. We have the information we want at the exact moment we want and in most part all the information is freely available, that is, we have the opportunity to learn about any subject without having to pay for that end avoiding expenses with specific material that in most cases will be used only once or at most twice to be frank.

Obviously there are prestigious institutions that provide distance education, which confer the most prestigious titles to those that finish a course without at least being present in a classroom. All that with the help of new technological advances that pervade our lives, which in turn make distance education something viable.

Particularly I don’t like the idea of distance education. I prefer to be present at the classroom. It would feel weird taking an educational leadership course in a virtual classroom. I believe that presence education is more enriching. I write this based upon all point of views, being the most important: more active social life interaction.

The virtual classroom world is interesting, yet it’s necessary to heed, for this can bring some undesirable consequences such as the lack of a direct liaison between the teacher/professor and their students and colleagues. Great part of our development is done through social interaction and this is almost foregone when we talk about distance education. There are plenty of other factors that influence my opinion, but for now this demonstrates one of the big bottlenecks that refrains the distance education of evolving in faster paces. There are still conservatives. It can be the case that in a near future such conservatives perish the thought.

The actual distance education environments, such as TelEduc in Brazil enable the distance education practice to reach more and more people. My alma mater UBM constituted a center for distance education called NEAD and uses TelEduc as its environment. I have used it and what I write here has as background my experience as a user of the system.

Tertiary institutions as the case of UBM offer a vast range of improvement courses for their employees and even support courses for students that are undergoing their internship programs and college conclusion projects. The idea appears to be good, but in practice it’s not adopted by everyone, perhaps because of the lack of information regarding the distance education platform’s features and capabilities.

It’s good to highlight that the devices and techniques used to implement distance education are in great part the result of advances pertaining to information and communication technologies. These technologies aggregate people from the more diverse knowledge fields. Information and communication technologies include the set of technological and computational resources set aside to generate and propitiate the use of information. Thus, such technologies are established on the following components: hardware and their peripheral devices, software and their resources, telecommunication systems and data and information management.

The people responsible for the development and management of these components are increasingly requested on the market. Between them are computer engineers, computer scientists, system analysts, business analysts, chief information officers (CIO), chief executive officers (CEO), chief financial officers (CFO) just to name a few.

The instructional level has been growing a lot during the last years, what rises the competitiveness on the job market. A proven fact is that executives have been using distance education to leverage their academic degree, attending courses, such as a Master of Business Administration (MBA) at international universities as MIT, University of Cambridge, University of California, Berkeley, etc. Notwithstanding the executives are on their houses in the comfort of their couches or beds.

I complete this brief analysis of the influence of distance education stating that the use of new technologies like the Internet and well developed distance education environments are making life a lot easier if we take into account the commodity and easy access to information of any given area.

It’s worth to remember about the inherited risks that most of the times pass by unnoticed. The utilization of technology in excess can enslave men, transforming them in slaves of their own inventions. Wherefore we must discuss such subject, aiming at the discovery of a steady point between the virtual and real life, providing a better way for a rich development environment where all people can evolve in a natural manner. I wrote and meant everybody, what presupposes the integration of the underprivileged people into this whole new world of information called Internet. Long live the blogs of life.