A while ago I had the pleasure of reading through several classic (and somewhat old) references/literature papers from SPJ et al. about functional progamming and introduction of a simple implementation in order to understand how a lazy functional language operates and can be possibly implemented while disregarding optimizations.

In a nutshell the compilation of a functional language like Haskell transforms it into a relatively simple set of IRs in the Core. Now disregarding front-end features like solvers for type classes, the essential algorithms and transformations of the front-end source language is quite manageable (compared to something like C++ lol). I followed one of the basic type inferencing algorithms (algorithm W), which is also talked about in [1], and lowered a front-end source language (based off Haskell/Miranda but trimmed down to the minimum by not supporting type classes, etc.) and lowered to a Core-like IR.

What followed is a deeper investigation of how the next level of IR that sits beneath the Core. Essentially that layer is the STG (Spineless Tagless G-machine). The STG IR has a very direct mapping to instruction executed by a machine (whether that is virtual or not) and the STG has deviated from its original design and implementation as seen in the literature papers [1, 2] that focuses on the operation semantics. Essentially, a fairly direct mapping can be seen between source code and semantics of what happens on a machine:

  • let binding <=> heap allocation
  • case expression <=> evaluation of the scrutinee (argument) of the case argument of ... (this is where evaluation to (weak head) normal form happens)
  • alternatives of case expression <=> continuations (AKA. code where the result of case scrutinee evaluation would eventually pick and jump to)

and there are a few other things that come into play more visibly at this level of abstraction such as boxed and unboxed types that are typically sugared away in the original source code.

Overall, it is a fairly self contained simple language. I’ve captured some of the notes about the original STG semantics here: STG Operational Semantics

Next, I’ll be experimenting with design and implementation (work in progress) of a STG IR and runtime semantics based off the more recent approach with using one stack. Hopefully this goes well and I’ll report back progress and findings in a future post.

References:

[1] Peyton Jones, S. L. (1987). The implementation of functional programming languages. Prentice Hall International (UK) Ltd.

[2] Peyton Jones, S. L. (1992). Implementing lazy functional languages on stock hardware: The spineless tagless G-machine. Journal of Functional Programming, 2(2), 127-202.

[3] Marlow, S., & Peyton Jones, S. L. (2006). Making a fast curry: Push/enter vs. eval/apply for higher-order languages. Journal of Functional Programming, 16(4-5), 415–449.