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.