About Lowering

Most modern high level languages' compilers pass through (more or less) the following phases:

Figure 1 Compiler phases (from the dragon book)

Taking C# as an example, it passes through similar stages and surely, there are other stages that are taking place in the middle or at the end of compilation pipeline. However, this is not exactly our concern at this point, what interests us though, is what's taking place at the stages prior to Intermediate Code Generation.

In a lot of programming languages, there is an interesting stage that might take place (which happens in C# for example), such as code lowering, which means rewriting your high-level code in a lower level code in the same programming language (think of it as the opposite of syntax sugar). For instance, one could look at foreach loop as a fancy way to write a for loop. Furthermore, some would look at for loop as a fancy way to write a while loop, like below:

foreach (var x in new List<int> { 1, 2, 3 })
{
      Console.WriteLine(x);
}

gets lowered to the following code

List<int> list = new List<int>();
list.Add(1);
list.Add(2);
list.Add(3);
list.Add(4);

List<int>.Enumerator enumerator = list.GetEnumerator();

try
{
      while (enumerator.MoveNext())
      {
            int current = enumerator.Current;
            Console.WriteLine(current);
      }
}

finally
{
      ((IDisposable)enumerator).Dispose();
}

Which for some makes sense and probably might know about it. Furthermore, if you look at the source code of a while loop, you will see that it is being rewritten internally as a goto statement.

Moreover, (which I think by now you might have guessed it) if statements are rewritten as a goto statement and yield statements when they are used in certain ways they get converted into a state machine. Now if you are keen to experiment or would like to discover more about code lowering, go ahead and visit https://sharplab.io/ you can see the output of the lowered code.

Also keep in mind that apparently sharplab is reinterpreting/converting IL to C# (i.e. after the code has been already optimized, since a lot of optimizations tricks are happening at the syntax tree level). This idea of lowering in fact doesn't only help to optimize compiling performance, but might as well help in finding bugs in the compilation of the language itself.

What piqued my personal interest though, since C# supports functional programming, I wanted to see how does the compiler interpret the fixed-point Y-Combinator problem. For those who are unfamiliar, Y-Combinator is a way to write a recursion even if the language doesn't support that feature, and has the following lambda calculus form:

It is possible to write Y Combinator in C#, so I've grabbed the implementation from here, and it looks as follows:

static class YCombinator<T, TResult>
{
      public static Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>> Fix { get; } =
            f => ((Func<dynamic, Func<T, TResult>>)(g => f(x => g(g)(x))))((Func<dynamic, Func<T, TResult>>)(g => f(x => g(g)(x))));
}

class Program
{
      static void Main(string[] args)
      {
            var factorial = YCombinator<int, int>.Fix(f => x => x < 2 ? 1 : x * f(x - 1));
            var fibonacci = YCombinator<int, int>.Fix(f => x => x < 2 ? x : f(x - 1) + f(x - 2))

            Console.WriteLine(factorial(10));
            Console.WriteLine(fibonacci(10));
      }
}

Which yielded this relatively large and interesting output which I think it is better to inspect it closer here.

Quite fascinating, isn’t it? Of course, you can alternate between C#, IL, and you can check out the generated syntax tree for further analysis.

Of course, this test with Y-Combinator was for the pure scientific curiosity, however, this technique of observing how your code is being lowered helps tremendously in finding bottlenecks in your code and how to optimize and fix these kinds of problems in case you run into performance issues. If you would like to read further about Y-Combinator and its origin, you can check out Mike Vanier excellent article on the topic here.