Lil' Fun Langs' Guts
I'm still thinking about those lil' fun langs. How do they work? What's inside them? Do I need my pancreas? What if I don't want to normalize my IR? Is laziness a virtue?
Haskell-esque languages may look alike, but they differ across many dimensions:
Most implementations use standard compilation phases:
Strict vs. Lazy
In strict evaluation, arguments are evaluated before being passed to a function. In lazy evaluation, arguments are only evaluated if their value is actually needed; the result is cached, so the work happens at most once.
-- lazy eval returns `3` without applying `foo` length [ 1, foo 2, 4 ]
Aspect Strict (ML, OCaml) Lazy (Haskell) Normalization ANF / K-normal form STG / thunks required Closure conversion Standard flat closures Closures + thunks + update frames Code generation Straightforward Requires eval/apply or push/enter Memory management Values are always evaluated May contain unevaluated thunks Tail calls Simple (jump) Complex (enters, updates) Debugging Easy (call stack is meaningful) Hard (thunks obscure control flow) Runtime complexity Simpler (~200 LOC C) More complex (~500–2000 LOC C)
Strict evaluation is the simple choice. If you want laziness, Peyton Jones's STG machine is the standard approach. MicroHs sidesteps the STG machine by compiling directly to combinatory logic with graph reduction.
Lazy evaluation also unlocks infinite collections — you can define an infinite list and consume only what you need.
... continue reading