Am 10.03.2016 um 13:42 schrieb Maksymilian Owsianny:
I'm specifically interested in a compilation step, that is turning a AST of some functional language say untyped lambda calculus into a sequence of imperative instructions.
I was asking myself the same question. I can't offer structured material, but an insight I gained recently (old news to most people here I'm sure). The insight was that you don't compile code for the "this function is not being evaluated" case - that would be pointless because that case is handled by generic graph construction and you don't need code that's specific for the function. Instead, you generate code for the case that the function participates in being evaluated ("forced"). At least for me, that was one of those "a-ha" moments that told my why generating imperative code is even relevant for a language like Haskell. The standard case is where the top-level element of the function is a pattern match: You generate code for the match expressions, freely inline-expanding code from functions called from the match expressions. Same goes for the condition if the top-level element is an if expression. The right-hand sides of the pattern matches remain unevaluated, you generate code to construct graphs, because the compiler does not know which pattern will match. I'm pretty sure I'm missing a big part of the picture and that this model is just the starting point, but anyway, here it is :-)