Adventures in F#--Corecursion

  • Article

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:

    !!  f1 <T>( n)  {     4    L_0000:      L_0001:      L_0002:      L_0003:      L_0005:  !!0 ::<!!>()    L_000a:  }

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.

Comments

  • Anonymous
    September 24, 2007
    PingBack from http://msdnrss.thecoderblogs.com/2007/09/24/adventures-in-f-corecursion/

  • Anonymous
    September 25, 2007
    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.

  • Anonymous
    September 27, 2007
    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?

  • Anonymous
    November 03, 2007
    The comment has been removed

  • Anonymous
    June 21, 2009
    The comment has been removed

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