F #: What your code turns into after compilation

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

Let's take a look at the frequently used and useful “memorialization” technique and look into what makes your code a compiler. For clarity, I will write the code in F # 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 = fx 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 explanations:

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

')
Let's now see what led the memorial.
Program execution time without memorization is 28.97 s, and with memorialization 0.89 s. As they say, the effect is obvious.

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

main function:

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

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

For a start, we have two fields of the $Program class:

 internal static FSharpFunc<BigInteger, BigInteger> memoizedFactorial@11; internal static Lazy<FSharpFunc<BigInteger, BigInteger>> memoizedFactorial@11-1; 

It is seen that the second is initialized by an object of the standard class to which the closure is passed. The first field does nothing interesting, it just returns itself ( get_Value method).

So, looking closure:

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

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

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

Hm Looks like they came where they were. But it is not. This returns the result of calling the memoizedFactorial@11-1 function. Finally, we are looking at this function:

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

Here! Finally we got to the memoize function. And before one more short circuit. A closure is a descendant of the same class; we immediately look at the Invoke method:

 public override BigInteger Invoke(BigInteger x) { if (LanguagePrimitives.HashCompare.GenericEqualityIntrinsic<BigInteger>(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 the recursion uses the memorized version, as we wrote in the F # code. The comparison with the template was converted to a regular if . We also note in passing that two BigInteger compared through their hashes.

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

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

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

Deepen:

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

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

 public override b Invoke(ax) { 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 memorial function! The key is passed through the argument. The closure of f we already know through the fields of the object. The secret is solved.

Thus, in F # there is no magic. Well, absolutely. All of these currying (and the memoizedFactorial function memoizedFactorial 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.