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