[Haskell-cafe] Materials on Compiling Functional Languages.

Joachim Durchholz jo at durchholz.org
Thu Mar 10 16:02:39 UTC 2016

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 :-)

More information about the Haskell-Cafe mailing list