F #: What does your code turn into after compilation

The F # language appeared in the standard VisualStudio package quite recently, namely from the 2010 version (currently the most relevant one). Naturally, everyone knows this very well, the language functions on the basis of the CLR - all your code will be compiled into MS IL like any other .NET language.

Let’s look at what the compiler turns your code into, as an example of the often used and useful memorization technique. For clarity, I will write the code in F # itself and decompile it in C #.

So, the original example:

let memoize f =
    let cache = System.Collections.Generic.Dictionary()
    fun x ->
        if cache.ContainsKey(x) then
            cache.[x]
        else
            let res = f x
            cache.[x] <- res
            res
let rec memoizedFactorial =
    let factorial x =
        match x with
        | a when a = 0I -> 1I
        | x -> x * memoizedFactorial (x - 1I)
    memoize factorial
let now = System.DateTime.Now
let arguments = [10000I .. 10100I]
let factorials = arguments |> List.map memoizedFactorial
let timeDiff = System.DateTime.Now - now
printfn "Time: %A" timeDiff

A few clarifications:

• We will consider 101 factorial from 10,000 to 10,100. In order to be longer.
• We note the execution time of our calculation.
• Since there is no built-in memorization in F #, we use a home-made one. It takes any function as an argument, initializes the cache and creates a lambda expression that is used to check the existence of the element in the cache, call the real function if the element is absent, and add the element to the cache.
• For clarity, I created a separate memorized function memoizedFactorial. The effect is based on the fact that we determine the function memoizedFactorial without arguments, and as a result we return another function, to which we will pass the arguments later. Thus, it turns out that it memoizedFactorialexists in a single instance, as an object, and our cache will be the same with multiple function calls.

Let's now see what the memorialization led to.
The program execution time without memorization is 28.97 s, and with memorization 0.89 s. As the saying goes, the effect is obvious.

We look into what all this compiles. The most interesting point for a C # programmer is of course the moment the function is called memoizedFactorial. Why is the local function cache not recreated?
Let's watch.

Function main:

public static void main@()
{
    memoizedFactorial@11-1 = LazyExtensions.Create>(new Program.clo@11-1());
    memoizedFactorial@11 = Program.memoizedFactorial@11.get_Value();
    now@18 = DateTime.Now;
    arguments@20 = SeqModule.ToList(new Program.arguments@20(0, new BigInteger()));
    factorials@21 = ListModule.Map(Program.memoizedFactorial, Program.arguments);
    timeDiff@23 = (TimeSpan) (DateTime.Now - Program.now);
    fp@1 = new PrintfFormat, TextWriter, Unit, Unit, TimeSpan>("Time: %A");
    PrintfModule.PrintFormatLineToTextWriter>(Console.Out, Program.fp@1).Invoke(Program.timeDiff);
}

Hmm ... Function memoizedFactorialhas become a separate object. In addition, there are no variables at all - they all became class fields internal static class $Program. In general, up to specific classes, the code should be clear. Going deep into memoizedFactorial.

For starters, we have two class fields $Program:

internal static FSharpFunc memoizedFactorial@11;
internal static Lazy> memoizedFactorial@11-1;

It can be seen that the second is initialized by the object of the standard class into which the closure is passed. The first field does not do anything interesting, it simply returns itself (method get_Value).

So, the closure looks:

internal class clo@11-1 : FSharpFunc>
{
    // Methods
    internal clo@11-1();
    public override FSharpFunc Invoke(Unit arg00@);
}

We understand that this is a class that has an interesting method:

public override FSharpFunc Invoke(Unit arg00@)
{
    return Program.memoizedFactorial@11-1();
}

Hm. It looks like they came where they were already. But this is not so. This returns the result of calling the function memoizedFactorial@11-1. Finally, we look at this function:

internal static FSharpFunc memoizedFactorial@11-1()
{
    return memoize(new clo@13());
}

Here! Finally we got to the function memoize. And to another closure. A closure is an inheritor of the same class, we look at the Invoke method right away:

public override BigInteger Invoke(BigInteger x)
{
    if (LanguagePrimitives.HashCompare.GenericEqualityIntrinsic(x, BigInteger.Zero))
    {
        return BigInteger.One;
    }
    return (x * Program.memoizedFactorial@11.get_Value().Invoke(x - BigInteger.One));
}

Here it is our factorial! We found a function that directly calculates the value. Note that a memorialized version is used for recursion, as we wrote in F # code. Comparison with the template was converted to normal if. Also, along the way, we notice that the two are BigIntegercompared through their hashes.

Let's go back one step and see the function memoize:

public static FSharpFunc memoize(FSharpFunc f)
{
    return new memoize@3(f, new Dictionary());
}

Here, the fun began. As a result of the work, the object is returned to the designer parameters of which our closure (first argument) and the dictionary (second argument) are passed. Now it’s clear why the dictionary is not recreated every time.

We go deep:

internal class memoize@3 : FSharpFunc
{
    // Fields
    public Dictionary cache;
    public FSharpFunc f;
    // Methods
    internal memoize@3(FSharpFunc f, Dictionary cache);
    public override b Invoke(a x);
}

The class fields once again show why the cache is one for the entire program. We look at the function Invoke:

public override b Invoke(a x)
{
    if (this.cache.ContainsKey(x))
    {
        return this.cache[x];
    }
    b res = this.f.Invoke(x);
    this.cache[x] = res;
    return res;
}

And here is our memorialization function! The key is passed through the argument. fWe already know closure through object fields. The secret is unraveled.

So in F # there is no magic. Well, absolutely. All of these currying (and the function memoizedFactorialis what it is), functions like first-class citizens are actually just automatically generated classes and objects. I hope that my article will help someone better understand how F # works inside.