The design of GHC is based on something called STG, which stands for &quot;spineless, tagless G-machine&quot;.

Now G-machine is apparently short for &quot;graph reduction machine&quot;, which defines how laziness is implemented. Unevaluated thunks are stored as an expression tree, and executing the program involves _reducing_ these down to normal form. (A _tree_ is an acyclic graph, but Haskell&#39;s pervasive recursion means that Haskell expressions form general _graphs_, hence graph-reduction and not tree-reduction.)

What is less clear are the terms &quot;spineless&quot; and &quot;tagless&quot;.

1. I _think_ that &quot;spineless&quot; refers to the fact that function applications do not have a &quot;spine&quot; of function application nodes. Instead, you have an object that names the function called and points to all of its arguments. Is that correct?

2. I thought that &quot;tagless&quot; referred to constructor nodes not being &quot;tagged&quot; with a constructor ID, and instead case-expressions are resolved using a jump instruction. But now I&#39;m not sure that&#39;s correct. Instead, it seems to refer to the fact that nodes aren&#39;t tagged with their evaluation state. Can anyone clarify which (if any) of these interpretations is correct?


All Intermediate Language Solutions on Gang of Coders

Total of 1 Intermediate Language Solutions

Understanding STG