Adventures in F#--Corecursion

Adventures in F#--Corecursion

  • Comments 6

Jomo Fisher--In a prior post I touched on recursion in F#. One of the comments was about mutually recursive functions. The example given was,

let f1 a
do print a
f2 a

let f2 a
do print a
f1 a

f1 1

It turns out that this F# doesn't compile because F# scoping rules are different than what you might expect coming from C# or VB. At least it wasn't what I expected. The function f1 cannot call f2 because f2 is not in scope yet because it's lower in the file.

Mutual recursion is a useful feature and I was sure F# must have a way to support it. I searched around quite a bit, but I didn't know the right question to ask the search engines. Eventually, I got some help from my friend  Luke Hoban.

The way to create mutually recursive functions in F# is with the and keyword:

let rec f1 n =
    f2 (n+1)
and f2 n =
    f1 (n+1)
   
f1 1

Will this program overflow the stack? Let's look at the corresponding C# decompiled by Lutz Roeder's Reflector:

    public static T f1<T>(int n) {
        return f2<T>(n + 1);
    }

    public static T f2<T>(int n) {
        return f1<T>(n + 1);
    }

At first glance, it looks like this will overflow the stack. However, if you try to verify this experimentally you'll see that it doesn't. You have to look directly at the IL to understand why:

.method public static !!T f1<T>(int32 n) cil managed
{
    .maxstack 4
    L_0000: ldarg.0 
    L_0001: ldc.i4.1 
    L_0002: add 
    L_0003: tail 
    L_0005: call !!0 Test::f2<!!T>(int32)
    L_000a: ret 
}

The secret is the tail opcode. This instructs the following call to behave like a jump rather than a function call. Since no stack is consumed, the stack cannot overflow.

 

This posting is provided "AS IS" with no warranties, and confers no rights.

Leave a Comment
  • Please add 3 and 4 and type the answer here:
  • Post
  • PingBack from http://msdnrss.thecoderblogs.com/2007/09/24/adventures-in-f-corecursion/

  • I found it enlightening to write a pair of mutually recursive functions that extract alternate elements from a given list to return a pair of lists that contain the elements with even and odd indexes, respectively.

  • Cool. So F# is using ”tail” after all. What I still don't understand is why F# bother with the rec keyword, since it should be trivial to calculate if tail call optimization is possible or not (and since rec anyway have to make sure that tail call optimization is permitted).

    Another strange thing is that F# is making f1 and f2 generic since neither f1 nor f2 can return anything else than int. I would love if F# could type infere f1 and f2 to both int and float in this case, but I don't think it can - so why bother with the generics? Is it something I'm missing here?

  • Finnsson,

    F# has a "rec" keyword because it is often very useful to supercede definitions in a functional language. So you often want a not-rec let binding.

    Regarding the inferred types of the "f1" and "f2" functions, these functions never return so F# correctly infers generic types for their return types. This is just one example of type inference providing you with assurances about your code. If the compiler inferred a return type of "int" for a function that should never return then you know that you have made a mistake.

    You can learn to leverage F#'s type inference and static type checking to write more robust code. This is described in detail in some of our F#.NET Journal articles. These tricks make it much easier to write complicated code in F#.

  • Almost too much to keep up with this week.&#160; Most notably, Roger Castillo gave a fantastic talk on

  • Just as a note, tailcall is disabled in debug mode as of Beta 1.  This preserves stack frames, often simplifying debugging.

Page 1 of 1 (6 items)