Spineless Tagless G-machine

The Spineless Tagless G-machine (STG) is an abstract machine designed by Simon Peyton Jones that serves as the compilation target for lazy functional languages, most notably Haskell via the Glasgow Haskell Compiler. It resolves the tension between call-by-need semantics and concrete hardware by representing unevaluated expressions as self-describing heap closures that overwrite themselves with their computed value upon first demand — a technique called update-in-place that guarantees each expression is evaluated at most once. The STG machine is spineless because it does not maintain a stack of return addresses, and tagless because it uses a uniform representation where every value is a closure pointer, eliminating the need for runtime type tags during execution.

The STG machine bridges the gap between the lambda calculus and the von Neumann architecture without abandoning the theoretical properties that make functional programming powerful. Its design demonstrates that laziness is not merely a semantic convenience but an implementable execution strategy, provided the runtime system is willing to pay the cost of heap allocation for thunks and generational garbage collection for reclamation. Every mainstream language now borrows ideas from the STG machine's design, even if its name remains obscure outside of compiler research.