fmthoma/stg

Simple STG implementation

STG interpreter

The spineless tagless graph reduction machine, STG for short, is an automaton used to map non-strict functional languages onto stock hardware. It was developed for, and is heavily used in, the Haskell compiler GHC.

This project implements an interpreter for the STG as it is described in the 1992 paper on the subject, considering readability and staying close to the source above all other considerations.

Since 1992, the STG has undergone one notable revision, documented in the 2004 paper How to make a fast curry. The plan is to migrate to this more modern implementation, which treats function application a bit different, once I'm satisfied with the code, and still curious about the STG.

To do

• Main functionality
  • Rule 18/19 on page 65: Better primitive case
  • Test the stepper
  • Write lots of test cases
  • Remove all errors
  • Unify the stacks to one; should be more instructional. For example, an update frame is very clearly flattened into the argument and return frames it contains when an update is triggered. Should also reduce the nesting of stacks in the overview.
• Nice to have
  • Explain steps better
  • Command line options (in particular to control colouring)
  • Convenience functions for Prelude, for example to generate a list of numbers
  • Unify Pretty and PrettyAnsi instances by calling parametrized generic prettyprinters. A member definition would then look like pretty = prettyLambda pretty pretty prettyAnsi = prettyLambda prettyAnsi prettyAnsi
  • Separate lexer and parser
  • Annotate syntax tree
  • Highlight error location in input
  • HTML prettyprinter
• Small stuff