CODEWITHSUNDEEP
recursionparametersf#scheme
asafc
asafc

Reputation: 367

How does F# implement let rec?

I am wondering how F# implements let rec, and I couldn't find an answer. As a preface, I'll address how Scheme implements letrec:

  1. In Scheme, let is just syntactics sugar for a definition of a lambda and applying it:

(let ((x 1)) (+ x 2))

is transformed to

((lambda (x) (+ x 2)) 1)

(in each case the expression is evaluated to 3).

  1. letrec is also syntactic sugar, but #f is passed as initial argument to the lambda's parameters, and set! expressions are injected before the letrec body, like in this transformation:

(letrec ((x 1)) (+ x 2)) => ((lambda (x) (begin (set! x 1) (+ x 2))) #f).

Considering that F# doesn't have an equivalent operator to Scheme's set!, how does it implement let rec? Does it declare the function's parameters as mutable, and then mutate them in the function's body?

Upvotes: 5

Views: 1397

Answers (1)

Asti
Asti

Reputation: 12677

In F#, let rec allows a reference to the binding from within the function before it has been bound. let rec doesn't have an implementation per se, because it is merely a compiler hint.

In this contrived example, 

let rec even =
    function 0 -> true  | 1 -> false | x -> odd (x - 1)
and odd =
    function 0 -> false | 1 -> true  | x -> even (x - 1)

the compiled IL very unglamorously translates to:

public static bool even(int _arg1)
{
    switch (_arg1)
    {
    case 0:
        return true;
    case 1:
        return false;
    default:
        return odd(_arg1 - 1);
    }
}

public static bool odd(int _arg2)
{
    switch (_arg2)
    {
    case 0:
        return false;
    case 1:
        return true;
    default:
        return even(_arg2 - 1);
    }
}

All function definitions are statically compiled to IL. F# ultimately is a language which runs on the CLR. There is no meta-programming.

Upvotes: 5

Related Questions