quchen/stgi: A user-centric visual STG implementation to help understand GHC/Haskell’s execution model.

STGi is a visual STG implementation to help understand Haskell’s execution

It does this by guiding through the running of a program, showing stack and
heap, and giving explanations of the applied transition rules. Here is what an
intermediate state looks like:


Table of contents

Quickstart guide

If you want to have a quick look at the STG, here is what you need to get going.
The program should build with both stack and cabal.

The app/Main.hs file is written so you can easily switch out the prog value
for other Programs that contain a main definition. The Stg.ExamplePrograms
module provides a number of examples that might be worth having a look, and are
a good starting point for modifications or adding your own programs. It’s
probably easier to read in Haddock format, so go ahead and run

stack haddock --open stgi

and have a look at the example programs.

When you’re happy with your app/Main.hs, run

stack build --exec "stgi-exe --colour=true" | less -R

to get coloured output in less. Type /==== to search for ====, which
finds the top of every new step; use n (next step) or N (previous step) to
navigate through the execution.

About the machine

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, with the main focus on being nice to a
human user. Things that might be important for an actual compiler backend, such
as performance or static analysis, are not considered in general, only if it
helps the understanding of the STG.

The idea behind the machine is to represent the program in its abstract syntax
tree form. However, due to references to other parts of the syntax tree, a
program is a graph, not a tree. By evaluating this graph using a small set of
rules, it can be systematically reduced to a final value, which will be the
result of the program.

The STG is

  • spineless because the graph is not represented as a single data
    structure in memory, but as a set of small, individual parts of the graph
    that reference each other. An important part of the evaluation mechanism is
    how to follow these references.
  • tagless because all heap values – unevaluated values, functions, already
    evaluated values – are represented alike on the heap, in form of closures.
    Tagful would mean these closures have to be annotated with things like
    type information, or whether they were previously evaluated already.
  • graph reducing because heap objects can be overwritten by simpler values
    the machine has found out to be equivalent. For example, the computation
    1+1 on the heap might be overwritten by a constant 2 once that result
    has been obtained somewhere.

Useful applications

STGi was started to teach myself about the STG. Not long into the project, I
decided to extend it to save others the many detours I had to take to implement
it. In that sense, it can be a useful tool if you’re interested in the
lower-level properties of a Haskell implementation. I did my best to keep the
code readable, and added some decent Haddock/comment coverage. Speaking of
Haddock: it’s an excellent tool to start looking around the project before
digging into the source!

The other benefit is for teaching others: instead (or in addition to!) of
explaining certain common Haskell issues on a whiteboard with boxes and arrows,
you can share an interactive view of common programs with others. The example
programs feature some interesting cases.

  1. Does this leak memory? On the stack or the heap?
  2. I heard GHC doesn’t have a call stack?!
  3. Why is this value not garbage collected?
  4. Why are lists sometimes not very performant?
  5. How many steps does this small, innocent function take to produce a result?

Language introduction

The STG language can be seen as a mostly simplified version of Haskell with a
couple of lower level additions. The largest difference is probably that STG is
an untyped language.

The syntax will be discussed below. For now, as an appetizer, the familiar
Haskell code

foldl' _ acc [] = acc
foldl' f acc (y:ys) = case f acc y of
    !acc' -> foldl' f acc' ys

sum = foldl' add 0

could be translated to

foldl' = f acc xs -> case xs of
    Nil -> acc;
    Cons y ys -> case f acc y of
        acc' -> foldl' f acc' ys;
    badList -> Error_foldl' badList;

sum =  -> foldl' add zero;

zero =  -> Int# 0#


An STG program consists of a set of bindings, each of the form

name = (<free vars>) <bound vars> -> <expression body>

The right-hand side is called a lambda form, and is closely related to the
usual lambda from Haskell.

  • Bound variables are the lambda parameters just like in Haskell.
  • Free variables are the variables used in the body that are not bound or
    global. This means that variables from the parent scope are not
    automatically in scope, but you can get them into scope by adding them to
    the free variables list.

The main value, termination

In the default configuration, program execution starts by moving the definitions
given in the source code onto the heap, and then evaluating the main value. It
will continue to run until there is no rule applicable to the current state. Due
to the lazy IO implementation, you can load indefinitely running programs in
your pager application and step as long forward as you want.


Expressions can, in general, be one of a couple of alternatives.

  • Letrec

    letrec <...bindings...> in <expression>

    Introduce local definitions, just like Haskell’s let.

  • Let

    let <...bindings...> in <expression>

    Like letrec, but the bindings cannot refer to each other (or themselves).
    In other words, let is non-recursive.

  • Case

    case <expression> of <alts>

    Evaluate the <expression> (called scrutinee) to WHNF and continue
    evaluating the matching alternative. Note that the WHNF part makes case
    strict, and indeed it is the only construct that does evaluation.

    The <alts> are semicolon-separated list of alternatives of the form

    Constructor <args> -> <expression> -- algebraic
    1# -> <expression>                 -- primitive

    and can be either all algebraic or all primitive. In case of algebraic
    alternatives, the constructor’s arguments are in scope in the following
    expression, just like in Haskell’s pattern matching.

    Each list of alts must include a default alternative at the end, which can
    optinally bind a variable.

    v -> <expression>       -- bound default; v is in scope in the expression
    default -> <expression> -- unbound default
  • Function application

    Like Haskell’s function application. The <args> are primitive values or

  • Primitive application

    Primitive operation on unboxed integers.

    The following operations are supported:

    • Arithmetic
      • +#: addition
      • -#: subtraction
      • *#: multiplication
      • /#: integer division (truncated towards -∞)
      • %#: modulo (truncated towards -∞)
    • Boolean, returning 1# for truth and 0# for falsehood:
      <#, <=#, ==#, /=#, >=#, >#
  • Constructor application

    An algebraic data constructor applied to a number of arguments, just like
    function application. Note that constructors always have to be saturated
    (not partially applied); to get a partially applied constructor, wrap it in
    a lambda form that fills in the missing arguments with parameters.

  • Primitive literal

    An integer postfixed with #, like 123#.

For example, Haskell’s maybe function could be implemented in STG like this:

maybe = nothing just x -> case x of
    Just j   -> just j;
    Nothing  -> nothing;
    badMaybe -> Error_badMaybe badMaybe

Some lambda expressions can only contain certain sub-elements; these special
cases are detailed in the sections below. To foreshadow these issues:

  • Lambda forms always have lifted (not primitive) type
  • Lambda forms with non-empty argument lists and standard constructors are never


A lambda form can optionally use a double arrow =>, instead of a normal arrow ->.
This tells the machine to update the lambda form’s value in memory once it has
been calculated, so the computation does not have to be repeated should the
value be required again. This is the mechanism that is key to the lazy
evaluation model the STG implements. For example, evaluating main in

add2 =  -- <add two boxed ints>
one =  -> Int# 1#;
two =  -> Int# 2#;
main =  => add2 one two

would, once the computation returns, overwrite main (modulo technical
details) with

A couple of things to keep in mind:

  • Closures with non-empty argument lists and constructors are already in WHNF,
    so they are never updatable.
  • When a value is only entered once, updating it is unnecessary work. Deciding
    whether a potentially updatable closure should actually be updatable is what
    the update analysis would do in a compiler when translating into the STG.


  • Semicolons are an annoyance that allows the grammar to be simpler. This
    tradeoff was chosen to keep the project’s code simpler, but this may change
    in the future.

    For now, the semicolon rule is that bindings and alternatives are

  • Lambda forms stand for deferred computations, and as such cannot have
    primitive type, which are always in normal form. To handle primitive types,
    you’ll have to box them like in


    is invalid, and the machine would halt in an error state. You’ll notice that
    the unboxing-boxing business is quite laborious, and this is precisely the
    reason unboxed values alone are so fast in GHC.

  • Function application cannot be nested, since function arguments are primitives
    or variables. Haskell’s map f (map g xs) would be written

    let map_g_xs =  -> map g xs
    in map f map_g_xs

    assuming all variables are in global scope. This means that nesting functions
    in Haskell results in a heap allocation via let.

  • Free variable values have to be explicitly given to closures. Function
    composition could be implemented like

    compose = f g x -> let gx = (g x) -> g x
                        in f gx

    Forgetting to hand g and x to the gx lambda form would mean that in the
    g x call neither of them was in scope, and the machine would halt with
    a “variable not in scope” error.

    This applies even for recursive functions, which have to be given to
    their own list of free variables, like in rep in the following example:

    replicate = x -> let rep = (rep x) -> Cons x rep
                      in rep

Code example

The 1992 paper gives two implementations of the map function in section 4.1.
The first one is the STG version of

map f [] = []
map f (y:ys) = f y : map f ys

which, in this STG implementation, would be written

map = f xs -> case xs of
    Nil -> Nil;
    Cons y ys -> let fy = (f y) => f y;
                     mfy = (f ys) => map f ys
                 in Cons fy mfy;
    badList -> Error_map badList

For comparison, the paper’s version is

map = {} n {f,xs} -> case xs of
    Nil {} -> Nil {}
    Cons {y,ys} -> let fy = {f,y} u {} -> f {y}
                       mfy = {f,ys} u {} -> map {f,ys}
                   in Cons {fy,mfy}
    badList -> Error_map {badList}

You can find lots of further examples of standard Haskell functions implemented
by hand in STG in the Prelude modules. Combined with the above explanations,
this is all you should need to get started.

Marshalling values

The Stg.Marshal module provides functions to inject Haskell values into the
STG (toStg), and extract them from a machine state again (fromStg). These
functions are tremendously useful in practice, make use of them! After chasing a
list value on the heap manually you’ll know the value of fromStg, and in order
to get data structures into the STG you have to write a lot of code, and be
careful doing it at that. Keep in mind that fromStg requires the value to be
in normal form, or extraction will fail.

Runtime behaviour

The following steps are an overview of the evaluation rules. Running the STG in
verbose mode (-v2) will provide a more detailed description of what happened
each particular step.

Code segment

The code segment is the current instruction the machine evaluates.

  • Eval evaluates expressions.
    • Function application pushes the function’s arguments on the stack
      and Enters the address of the function.
    • Constructor applications simply transition into the
      ReturnCon state when evaluated.
    • Similarly, primitive ints transition into the ReturnInt state.
    • Case pushes a return frame, and proceeds evaluating the scrutinee.
    • Let(rec) allocates heap closures, and extends the local environment
      with the new bindings.
  • Enter evaluates memory addresses by looking up the value at a memory
    address on the heap, and evaluating its body.

    • If the closure entered is updatable, push an update frame so it can later
      be overwritten with the value it evaluates to.
    • If the closure takes any arguments, supply it with values taken from
      argument frames.
  • ReturnCon instructs the machine to branch depending on which constructor
    is present, by popping a return frame.
  • ReturnInt does the same, but for primitive values.


The stack has three different kinds of frames.

  • Argument frames store pending function arguments. They are pushed when
    evaluating a function applied to arguments, and popped when entering a closure
    that has a non-empty argument list.
  • Return frames are pushed when evaluating a case expression, in order to
    know where to continue once the scrutinee has been evaluated. They are popped
    when evaluating constructors or primitive values.
  • Update frames block access to argument and return frames. If an evaluation
    step needs to pop one of them but there is an update frame in the way, it can
    get rid the update frame by overriding the memory address pointed to by it
    with the current value being evaluated, and retrying the evaluation now that
    the update frame is gone. This mechanism is what enables lazy evaluation in
    the STG.


The heap is a mapping from memory addresses to heap objects, which can be
closures or black holes (see below). Heap entries are allocated by let(rec),
and deallocated by garbage collection.

As a visual guide to the user, closures are annotated with Fun (takes
arguments), Con (data constructors), and Thunk (suspended computations).

Black holes

The heap does not only contain closures, but also black holes. Black holes are
annotated with the step in which they were created; this annotation is purely
for display purposes, and not used by the machine.

At runtime, when an updatable closure is entered (evaluated), it is overwritten
by a black hole. Black holes do not only provide better overview over what
thunk is currently evaluated, but have two useful technical benefits:

  1. Memory mentioned only in the closure is now ready to be collected,
    avoiding certain space leaks. The 1992 paper gives the following
    example in section 9.3.3:

    list = (x) => <long list>
    l = (list) => last list

    When entering l without black holes, the entire list is kept in memory
    until last is done. On the other hand, overwriting l with a black hole
    upon entering deletes the last pointer from it, and last can run, and be
    garbage collected, incrementally.

  2. Entering a black hole means a thunk depends on itself, allowing the
    interpreter to catch some non-terminating computations with a useful error

Garbage collection

Currently, two garbage collection algorithms are implemented:

  • Tri-state tracing: free all unused memory addresses, and does not touch
    the others. This makes following specific closures on the heap easy.
  • Two-space copying: move all used memory addresses to the beginning of the
    heap, and discard all those that weren’t moved. This has the advantage of
    reordering the heap roughly in the order the closures will be accessed by the
    program again, but the disadvantage of making things harder to track, since
    for example the main value might appear in several different locations
    throughout the run of a program.

Unhelpful error message?

The goal of this project is being useful to human readers. If you find an error
message that is unhelpful or even misleading, please open an issue with a
minimal example on how to reproduce it!

Differences from the 1992 paper


  • Function application uses no parentheses or commas like in Haskell f x y z,
    not with curly parentheses and commas like in the paper f {x,y,z}.
  • Comment syntax like in Haskell
  • Constructors can end with a # to allow labelling primitive boxes
    e.g. with Int#.
  • A lambda’s head is written (free) bound -> body, where free and
    bound are space-separated variable lists, instead of the paper’s
    {free} n {bound} -> body, which uses comma-separated lists. The
    update flag u is signified using a double arrow => instead of the
    normal arrow ->.


  • The three stacks from the operational semantics given in the paper – argument,
    return, and update – are unified into a single one, since they run
    synchronously anyway. This makes the current location in the evaluation much
    clearer, since the stack is always popped from the top. For example, having a
    return frame at the top means the program is close to a case expression.
  • Although heap closures are all represented alike, they are classified for the
    user in the visual output:

    • Constructors are closures with a constructor application body, and
      only free variables.
    • Other closures with only free variables are thunks.
    • Closures with non-empty argument lists are functions.

GHC’s current STG

The implementation here uses the push/enter evaluation model of the STG, which
is fairly elegant, and was initially thought to also be top in terms of
performance. As it turned out, the latter is not the case, and another
evaluation model called eval/apply, which treats (only) function application a
bit different, is faster in practice.

This notable revision is documented in the 2004 paper How to make a fast
. I don’t have plans to support this evaluation model right
now, but it’s on my list of long-term goals (alongside the current push/enter).

Related Articles

Back to top button