About Me

Hello, I'm an eclectic software professional working with enterprise software at SAP. This blog only contains my personal views, thoughts and opinions. It is not endorsed by SAP nor does it constitute any official communication of SAP.

Thursday, July 30, 2009

F#: Why the rec?

I've been looking into F# for a while now, and I think it's an awesome addition to the .NET framework. It's more expressive and concise than C#. It's functional by heart, with discriminated unions, pattern matching, tail-call optimization, and it also supports object oriented programming (being a .NET language, it just had to) and imperative programming. Its type inference creates the feel of a dynamic language, but in a strongly-typed language (much like in Haskell and Scala).

That said, one of the first things that I noticed is that in order to declare a recursive function you have to be explicit about it in the function definition. You have to declare it with the rec keyword.

So, this is a non-recursive function:

let add a b = a + b

The function name is add, and it takes 2 (inferred) integer parameters, a and b, and returns their sum. You call it like this:

add 1 2 // returns 3

Now, this is a recursive function:

let rec add_all l = 
  match l with
    | [] -> 0
    | head :: tail -> head + add_all tail

This function takes a list and returns the sum of its elements using pattern matching and recursion. You call it like this:

add_all [1; 2; 3; 4] // returns 10

Note: this is just an example, a better way to write this function is just:

let add_all = List.fold_left (+) 0

In the F# documentation, it's stated that you have to use rec in order to make the function identifier available in the function scope, so that you can call it recursively. But I don't know why they didn't do this by default.

What you get by default (without rec) is that, if you're defining a function with an already existing name, you'll supersede its definition, and you'll be able to use the old function in the new function's body:

let add a b = a + b

...

let add a b c = c + add a b

The second add declaration shadows the first. But the first add is still available in the second add body (because it doesn't use rec), and it's used there. I don't think that this usage pattern is more common than, say, recursion. And it breaks down if you want the second function to use the first one AND ALSO to be recursive.

The way to do that would be:

let add a b = a + b

...

let old_add = add
let rec add l = ... // can use old_add here

So, again, why bother with rec at all?

F# inherits much of its syntax from OCaml, including the rec keyword. Maybe F# should divorce from OCaml and implement more sensible defaults for a better and more consistent language.

UPDATE: after some more researching, I found out that rec is needed in order to counter a limitation in the default type-inference algorithm used. It's a kind of marker to choose a different and less powerful algorithm for the type-inference problem. The F# compiler could add another type-inference error in these cases, forcing the user to declare the return type of recursive functions, like in Scala. There are also good reasons for shadowing definitions as opposed to declaring recursive functions.

1 comment:

  1. The main reason for the rec is for reducing the complexity of the Hindley-Milner type inference in languages with side effects that could appear everywhere in a function.

    ReplyDelete