SPINELESS TAGLESS G-MACHINE lazy evaluation on stock hardware — a thunk that updates itself when forced
The Spineless Tagless G-machine (STG) is how Haskell runs lazily on ordinary CPUs. Its core idea is the self-updating thunk: an unevaluated expression is a heap closure whose code, when forced, computes the value and then overwrites itself with that value — so a thunk is evaluated at most once, and every later demand reads the cached result. “Tagless”: you enter a closure by jumping to its code rather than switching on a tag. “Spineless”: no explicit spine of the graph is kept. Simon Peyton Jones's STG is the engine inside GHC, and the reason lazy evaluation is fast enough to be practical.
THE TECHNIQUE a thunk forced once, then updated in place; entered by jumping to its code
A thunk forced on demand. The demo forces it, caches the result, and shows a second demand hitting the cache — one evaluation, not two: live demo
HISTORY & CREDIT Simon Peyton Jones, 1992
“Laziness re-computes the expression every time you look.” — the STG thunk overwrites itself with its value on the first force, so every later demand is a cache read. Evaluated at most once is the whole point of a thunk. cited
1984 · Thomas Johnsson — the G-machine (graph reduction on hardware). 1992 · Simon Peyton Jones — “Implementing lazy functional languages on stock hardware: the STG-machine”: spineless, tagless, self-updating thunks. now · the execution model inside GHC.
Force once, overwrite with the value, and every later demand is free. The self-updating thunk is what makes lazy evaluation affordable on a machine that was built to be strict. Peyton Jones 1992
RECOMMEND FOR I-13 thunk forced once, computed
On the canonical compiler, a thunk x*x at x=6 forces once to 36; a second demand reads the cached value (force count stays 1):
$ i13 run m_stg.i13 # thunk (x*x), forced
RUN OK . 11 step(s) . peak stack 2 . call depth 1
forces = 1
result = 36
Recommend: i13 is strict, not lazy — the opposite pole from the STG machine. It has no thunks and no heap of self-updating closures: an I x <- e evaluates e now, once, immediately. So i13 gets the STG's headline guarantee (each value computed at most once) trivially, by evaluating eagerly rather than by the elaborate machinery of force-and-update. The STG earns “at most once” for a lazy language on strict hardware; i13 is strict on a strict machine, so it never needed the thunk. Laziness is a capability i13 declines to keep its evaluation order — and its cost model — obvious.