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.