.entrypoint

I had written a post on Functions in F# a couple of days ago and Binil posted a comment which prompted me to post a follow up to add some information that I left out in the original post.

F# Syntax

F# has two syntax forms available – a lightweight syntax and a verbose syntax. The lightweight syntax uses indentation to mark the beginning and end of code blocks. This naturally results in more concise code. The verbose syntax uses additional keywords to demarcate code blocks making the code lengthier than it needs to be but it makes the code less sensitive to indentation (imagine copy-pasting and sending code in email etc).

The lightweight syntax is on by default. You can explicitly set it to on by using

#light

The verbose syntax is always on which means you can still use the verbose keywords even if the lightweight syntax is on.  We can enforce the verbose syntax by switching off the lightweight syntax as follows

#light “off”

The lightweight syntax is in more prominent use than the verbose syntax and it seems that going forward the verbose syntax might be obsolete.

Only spaces can be used for indentation in F#, TABs are not accepted. Visual Studio by default converts TABs to spaces. This can be set in Tools –> Options dialog under Text Editor –> F# –> Tabs.

Tail Recursion

I had mentioned about recursive functions in my previous post on Functions in F# but I did not mention anything about tail recursion. Given the importance of recursion in F#, this is a very important topic and I want to thank Binil for bringing it to my notice.

First, let me provide some background info on what is bad about recursive functions and why tail recursion is the preferred way to write recursive functions.

When is function needs to be executed, a block of memory is allocated on the system stack for the function and is called a stack frame. When the function completes execution, this memory is reclaimed and is called unwinding the stack.

Recursive functions call themselves repeatedly until an exit condition is met. This means that a new stack frame has to be created each time the recursive call is made. Given enough nested function calls there wouldn’t be any more space on the system stack and would cause an undesirable condition called stack overflow. The program execution is terminated forcefully by the runtime.

If the function calls are not recursive, for example calling a function 1000 times in a for loop, the memory block for a function can be reclaimed when the function execution is over. So what we need to try to achieve is to write the function in such a way that the stack frame of the calling function need not be maintained while execution proceeds to the next function call. The way to do this is to make the recursive call as the last statement in the function. When we do that the compiler produces different code which allows the stack frame of the calling function to be unwound and the memory reclaimed, in effect making it similar to calling the function in a loop. This technique is called tail recursion.

Let us look at some code to make this more clear. Here is the recursive implementation of factorial that I wrote in my previous blog post.

let rec factorial x=
    if x <= 1 then
        1
    else
        x * factorial (x-1)

Here it might look as if the recursive call is the last statement in the function, but it is not. It would become clear if we wrote it this way:

let rec factorial x=
    if x <= 1 then
        1
    else
        let product = x * factorial (x-1)
        product

Now it becomes clear that the last statement in the function is returning the value of product. We also see that the function has to maintain the value of x in its stack frame and multiply it with the value returned by the recursive call. So if the function is written as shown above, there is no way to reclaim the stack memory until the chain of recursive calls return. So let us re-write the function in using tail recursion.

let factorial x =
    let rec tailRecFactorial x prod =
        if x <= 1 then
            prod
        else
            tailRecFactorial (x-1) (prod * x)
    tailRecFactorial x 1

Here we have a nested function which takes the product up to the current stage as a parameter which means nothing needs to be stored on the stack of the calling function. The stack frame can be safely reclaimed. The compiler is able to spot the tail recursive calls and generates code as if the function was called in a loop. Execution returns the original calling point when the exit condition is met.

The method I showed above to achieve tail recursion is called accumulator pattern. Another way is to use Continuations.

Trivia

When I was writing the non tail recursive factorial function, by mistake I wrote it this way:

let rec factorial x =
    if x <= 1 then
        1
    else
    x * (factorial x-1)

Can you spot the problem ?

Hint: It causes a StackOverflowException when executed.

As I have posted here, I have made some resolutions for the new year. If nothing, just for the fun. I have to add two more things to the list.

• Learning F# and
• Reducing my weight.

I have been trying to learn F# for over a year now (maybe even a little more). I have all the F# books in print now as well as the PDF for the upcoming Manning MEAP – Functional Programming for the Real World. But they been collecting dust on my shelf. Functional programming requires a new mindset and hence requires a little more effort for me than studying a new imperative language. The first book that I bought is Expert F# which is definitely the wrong book for a beginner. It is written by Don Syme et.al. who is the primary designer of the language and is a little dense. It is a good book with a lot of information but it is just not good for somebody new to functional programming. Once you have grasped the main ideas behind functional programming, it is a good book to have. The second edition of this book is coming up soon.

The game changer for me was Programming F# by Chris Smith which, IMHO, is the best book out there today to learn F#. It is a surprisingly small book and is written with such clarity that even somebody with absolutely no exposure to functional programming languages would be able to learn from it. It makes the ideas accessible and has some brilliant examples to showcase some of the features of F#. It kind of feels like an easy-going friend, which is exactly what you need when exploring unfamiliar grounds. I was so impressed with the book that I wrote a review of the book on Amazon giving it 5 stars.

I am not entirely comfortable with F# yet. But I have my feet wet and I plan to make the plunge in 2010.

Another thing that I want to tackle in 2010 is my weight (and fat). I am 190 lbs now. I used to be something like 175 lbs 3 years ago when I came to USA. 15 lbs in 3 years ! I am definitely worried about this. So is my wife. I had taken diets a couple of times previously and had always managed to reduce weight. But it always came back with a vengeance. So I am not sure whether another diet is the solution. Being on a diet is one of the most worst experiences that I have been through. Food is always on your mind and you can’t eat it. You are constantly fighting the sugar craving (I was on a low-carb diet). It is hell.

Although I haven’t made any specific plans, I think I would concentrate more on exercise and less on diet this time. Let us see how it goes.

Happy Holidays !

Wikipedia says that

…functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions…

The point I wish to make here is that functions are the  most important “things” in a functional programming language. You can say that functions are “first class citizens” in a functional programming language. This means that functions can be passed around as parameters and return values of other functions, just like any other data. Functions which can take other functions as parameters and/or return values are called Higher-Order Functions.

Functions and Type Inference

Here is an example of a simple function in F#.

let triple x = 3 * x

Here triple is the name of the function and x is the name of the parameter passed to the function. Contrary to C# naming convention for function, F# uses camel casing. Even though we have not specified any type information, the compiler is able to infer that this function takes an integer as parameter and returns an integer. This is called Type Inference and makes your F# program more concise.

How did I know that the compiler inferred the parameter and return value as int? I typed in the above functional declaration in F# interactive and terminated it with ;; and hit Enter. F# showed me:

val triple : int –> int

This means that triple is a function which takes an integer as parameter and returns an integer. If we try to call the function with a float as parameter

triple 3.0

it will spit out an error message as follows.

stdin(4,8): error FS0001: This expression was expected to have type
    int   
but here has type
    float   

We know that * (multiplication operator) works with floats as well, so why this error ? The reason for this is that in the absence of any additional type information the compiler simply defaulted the type to integer. So triple is a function which can take an integer as parameter and return an integer which is equal to three times its input. It is equivalent to the following C# function.

static int Triple(int x)
{
      return 3 * x;
}

Since the function expects integer, a parameter of type float will produce an error.

So what do we do when we need a datatype other than the default type that the compiler is able to infer? We give a hint to the compiler via type annotation.

let triple (x: float) = 3.0f * x

Note: In the above example type annotation is not strictly required because the compiler would infer x as float because 3.0f is float. But it does show you how to annotate a function parameter with its type.

Higher Order Functions

The functions mentioned above are not a higher-order functions because they do not take a function as parameter, neither do they return one. List.map and List.filter are examples of higher order functions. List.map takes a function and applies it to each item in the list (also passed as parameter to it) and returns a new list with the output values. List.filter takes a function and list as parameters and returns a new list. The output list contains those values from the input list for which the input function returned true. An example is shown below which makes use of both these higher order functions.

let triple x =
    3 * x

let isEven x =
    x % 2 = 0

let actOnEven action numbers=
    List.map action (List.filter isEven numbers)

[<EntryPoint>]
let main(args:string[]) =
    let results = (actOnEven triple [1 .. 10])
    Console.WriteLine (results)
    0

Here actOnEven is itself a higher order function.

Recursive Functions

Recursive functions are functions that call themselves. An important tenet of functional programming is the use of recursion instead of looping. We can create recursive functions using the following syntax.

let rec factorial num =
    if( num <= 1) then
        1
    else
        num * factorial (num - 1)

The rec keyword is a helping hand to the compiler for type inference. Personally, I don’t like it but I think they couldn’t find a way around it.

Function Currying

Currying (named after Haskell Brooks Curry) is an interesting technique in which you pass one of the arguments to a function and it returns another function which takes the rest of the arguments. For eg., consider the function

let add x y = x + y

If you run this in F# interactive, you will see the following message:

val add : int -> int –> int

This means that add is a function which takes an integer and returns a function which takes another integer as parameter and returns an integer. So if we call add with just one parameter, it will return another function which takes the second parameter.

let addToTwo = (add 2)

To be clear, addToTwo is a function that takes one integer parameter and returns an integer.

For eg,

addToTwo 8

will return 10.

Here addToTwo is the curried function and this technique is called function currying. Although this may look like a strange and useless language feature, it has interesting and powerful applications in functional programming (like the pipe forward operator). I will write more about this in future blog posts.

Nested Functions

In F#, a function can contain another function. Here is a simple example.

let printList numbers=
    let print num=
        printfn "%i" num
    List.map print numbers

Here print is a function nested in printList.

Some of the feature that I have mentioned here would be new to C# programmers and might feel a little strange. But have hope, for all will become more clear with time. We need to see some solid examples to appreciate the power of some of them. I have mostly presented useless examples but I hope a reader would have gleaned atleast a little information about functions and its usage in F# from this post. There is more to write but it is getting late (3 am) and tomorrow is a working day, so I gotta go. Will be back with more on F#.

References:

Programming F#

Expert F#

If you took the shortcut of a Visual Studio Setup project (as opposed to using Wix) then you must have faced the same problem that I did, viz., not being able to create the MSI as part of your TFS nightly builds which hands over the bits to the test team. The problem here is that the vdproj files of the setup projects is in a format that MSBuild (and TeamBuild) does not understand. But we know that Visual Studio can build this project. So I tried to see if I can use devenv.exe to build the project. I tried devenv.exe /? on the command prompt and found that it indeed takes a build switch. So I tried this devenv.exe MySetup.vdproj /build

That did not succeed. The following error message was spit out:

Microsoft (R) Visual Studio Version 9.0.30729.1.
Copyright (C) Microsoft Corp. All rights reserved.
—— Starting pre-build validation for project ‘MySetup’ ——
ERROR: Cannot find outputs of project output group ‘(unable to determine name)’.  Either the group, its configuration, or its project may have been removed from the solution.
ERROR: Cannot find outputs of project output group ‘(unable to determine name)’.  Either the group, its configuration, or its project may have been removed from the solution.
—— Pre-build validation for project ‘MySetup’ completed ——
—— Build started: Project: MySetup, Configuration: Debug ——
========== Build: 0 succeeded or up-to-date, 1 failed, 0 skipped ==========

I then decided to run it against the solution file devenv.exe MySolution.sln /Build

That did the trick. The setup files were created in MySolution/MySetup/Debug/ folder.

So I needed to integrate this into the build script. Using devenv.exe means this build machine needs to have Visual Studio installed on it. We already had it, so I was in luck. In some teams they might not allowed the build machine to have Visual Studio. 

I added the path to devenv.exe to the system path. Screen shot below should show you how to do that.

As a first attempt I added the following code to the AfterDropBuild target.

<Target Name="AfterDropBuild">   
    <Exec Command="devenv.exe $(SolutionRoot)/MySolution.sln /Build"/>
    <ItemGroup>
      <SetupFiles Include="$(SolutionRoot)/MySetup/Release/MySetup.msi" />
      <SetupFiles Include="$(SolutionRoot)/MySetup/Release/Setup.exe" />
    </ItemGroup>
    <Copy SourceFiles="@(SetupFiles)" DestinationFolder="C:\Temp\MSI" />
  </Target>

This attempt failed. The error message was not helpful. So I logged into the build machine and tried the same command from command prompt and nothing happened ! So changed the current directory to the location of the sln file and then ran the command again and it worked. So it seems that devenv needs only the name of the sln file (not the full path to it) and the current working directory needs to be the directory when the sln file resides.

So my second attempt:

<Target Name="AfterDropBuild">   
    <Exec Command="devenv.exe MySolution.sln /Build" WorkingDirectory="$(SolutionRoot)"/>
    <ItemGroup>
      <SetupFiles Include="$(SolutionRoot)/MySetup/Release/MySetup.msi" />
      <SetupFiles Include="$(SolutionRoot)/MySetup/Release/Setup.exe" />
    </ItemGroup>
    <Copy SourceFiles="@(SetupFiles)" DestinationFolder="C:\Temp\MSI" />
  </Target>

That worked ! Well not fully, but the Exec task worked but the Copy task failed. I found the reason for that was the files were getting created in the Debug folder and not the Release folder. In order to force a Release build I had to pass additional info to devenv. So I changed the script as shown below and I could see the bits were getting copied correctly.

<Target Name="AfterDropBuild">
    <Exec Command="devenv.exe MySolution.sln /Build &quot;Release|Any CPU&quot;" WorkingDirectory="$(SolutionRoot)"/>
    <ItemGroup>
      <SetupFiles Include="$(SolutionRoot)/MySetup/Release/MySetup.msi" />
      <SetupFiles Include="$(SolutionRoot)/MySetup/Release/Setup.exe" />
    </ItemGroup>
    <Copy SourceFiles="@(SetupFiles)" DestinationFolder="C:\Temp\MSI" />
  </Target>

Here is my final version for copying it to a remote drop location.

<Target Name="AfterDropBuild">   
    <Exec Command="devenv.exe MySolution.sln /Build &quot;Release|Any CPU&quot;" WorkingDirectory="$(SolutionRoot)"/>
    <ItemGroup>
      <SetupFiles Include="$(SolutionRoot)/MySetup/Release/MySetup.msi" />
      <SetupFiles Include="$(SolutionRoot)/MySetup/Release/Setup.exe" />
    </ItemGroup>
    <Copy SourceFiles="@(SetupFiles)" DestinationFolder="\\Build-Machine\Build_Drop_Folders\MyProjectMSI\$(BuildNumber)" />
    <Copy SourceFiles="@(SetupFiles)" DestinationFolder="\\Build-Machine\Build_Drop_Folders\MyProjectMSI\Latest_MSI" />
  </Target>

Note: Here $(SolutionRoot) is the path you have given while creating the build definition. You can see it by editing the build definition.

I don’t usually make new year resolutions. It is not because I am perfect and doesn’t need to make any changes, but it is because of my lazy nature. I have made up my mind several times in the past about achieving this and achieving that, but usually I don’t ever bring myself to completing my projects.

So why this year ?

I don’t know, but I think it would be a good thing to try. Like a new cuisine or a new hair style,  sometimes a change is nice to have – they add spice to life. So I am going to give new year resolutions a try this year.

So what is different this time ?

This time I am publicly disclosing the things I want to achieve, the projects I want to complete. I remember having read somewhere that it would be good idea to make our aspirations public. This would help motivate us to complete our projects.

As of now, I have 3 things in mind for 2010.

• I have decided to write a series of blog posts on the common software design patterns made popular by the GoF. Why design patterns? Frankly, I don’t have a very clear reason. I know it is not the hottest topic to blog about, but it is definitely a useful one. Especially for me. I have been reading about design patterns, and occasionally putting to practice, since some time in 2003 when Binil gave me The Design Patterns book. Since then, I have read a few more books on the topic. But I don’t claim to be master on the topic. Actually far from it, my understanding of many of the “advanced” patterns are still vague. Haven’t we all heard the age old adage – “the best way to learn something is to teach it.”. So I am going to write about them, which will help me understand them better and if someone is able to glean something from my posts, it will be a pleasant bonus. This would also be a good exercise in writing and keep the blog rolling.  
• Read some books. Not the kind of glancing over that I do nowadays. A thorough reading. Understanding the concepts and making it part of myself. This is pretty ambitious. As of now I have two candidates in my mind for this project. The first book is Structure and Interpretation of Computer Programs (I have had this book for 3 years now) and the second one is Domain Driven Design (been in my shelf for a little over 2 years). These are not easy books to read. But they are important books to have read for any computer programmer. As I mentioned before this is quite an ambitious target. 
• Visit some places. I have been in the US of A for about 3.5 years now. But I haven’t seen many of the good places here. Even in Washington state, there are so many good places to see. Now that I am married I have a travel companion too

I don’t know how much of this I can accomplish (as with all other things in the future). But I think it is worth a try.

Wish me luck.