Implementing a Functional Language II: Graph Reduction
This is part 2 of a series in implementing a functional language. The introduction is here.
Every compilation strategy we will cover in this series will be based on the same core concept: lazy graph reduction. This idea is simple but powerful, and it’s what we’ll introduce in this section.
A functional program is really just a single large expression which evaluates to a result.
We can model it as a graph1 of nested applications. For example, the expression
f 1 2
looks like this:
We use the symbol
@ to denote an application node. Note that though
f takes two
arguments, we apply each in turn via currying. Here’s a more complicated example - the
(+ (* 2 3) 4):
To evaluate the program, we’ll repeatedly reduce expressions in the graph. We’ll stop when there are no expressions left to reduce. The resulting graph is the result of the program. Reducing an expression typically involves applying a function to one or more arguments, producing a result, and then replacing the expression with the result.
Not all expressions can be reduced:
+ 1 2 reduces to
3 does not reduce any
+ 1 does not reduce because
+ requires two arguments. An
expression which is reducible is known as a reducible expression, or redex. To evaluate an
entire program, all we need to do is repeatedly identify the next redex to reduce, and
then reduce it, stopping when there are no redexes left.
Let’s try to reduce the graph above. We start at the top, with an application node
The child nodes are
@ (another application) and
4. We can’t immediately evaluate this
expression, so we proceed down into the child application node, which itself has children
+ takes two arguments, in this case
(* 2 3) and
+ also requires
that both its arguments are evaluated, so we need to continue to reduce the first
argument. We descend into the right hand application node - the root of
(* 2 3). Here’s
where we are in the graph:
As before, we descend into the child application node, finally reaching
* takes two
numeric arguments, and we have two arguments in
3. We’ve found a reducible
expression! Specifically, the subgraph
can be reduced to the single numeric node
6. The node marked in red is the root of
the redex. Performing the reduction, the graph now looks like this:
Notice that the expression
(* 2 3) has been replaced with the result of its reduction
6). Proceeding back up graph, we can see that the arguments to
+ are now both
evaluated, so we’ve found another redex. Reducing this, we end up with a single node
which is the result of the whole expression.
The order in which we reduce expressions in a program has a profound effect on the behaviour of the program. The approach we used in reducing the program above is called normal order reduction. Normal order reduction requires that we reduce the leftmost outermost redex first.
One consequence of this is that we reduce applications before reducing their arguments. This is in contrast to a typical imperative language, where arguments to functions are evaluated before the function is called. Take for example the following Core program:
K x y = x main = K 1 (/ 1 0)
where we can assume that
(/ 1 0) will raise an error if evaluated. Following normal
order reduction, we will reduce the application of
K first, resulting in the following:
main = 1
Since the second argument to
K is never used, we never evaluate it. In a typical
imperative language, we would evaluate
(/ 1 0) first, resulting in an error. This style
of execution is called lazy evaluation, in contrast to strict evaluation. The two key
properties of lazy evaluation are the following:
- Arguments to functions are only evaluated when needed.
- Each argument is only evaluated once - further uses of the argument will use the result from the initial evaluation.
The second property doesn’t affect program behaviour but greatly improves efficiency.
Normal form and Weak head normal form
Normal order reduction specifies that we reduce the leftmost outermost redex first,
but it doesn’t specify when to stop. A natural assumption is to stop when there are no
redexes left, but this is not our only option. If the output of our program is being
printed to the screen, and we want to show progress as we go (or we’re printing an
infinite stream of values) then we want to be able to produce output without having fulling
evaluated it yet. Imagine a list made from a series of
Cons cells linked together: we
may want to print the first element before having evaluated the whole list.
To do this, we need to stop reducing when there is no longer a top-level redex. This will allow us to inspect the structure and decide what to evaluate next. An expression which has no top-level redexes (but may have inner redexes left) is in weak head normal form (WHNF). An expression which has no redexes at all is in normal form (NF). All expressions in NF are also in WHNF, but not vice versa. Here are some examples.
|Normal Form||Weak Head Normal Form|
For Core we’ll follow lazy evaluation and evaluate expressions to WHNF. For some built in
+) we will adopt strict semantics, requiring arguments to be fully
evaluated to normal form. For all user-defined functions we’ll use lazy semantics.
Let’s walk through the evaluation of the following program:
square x = * x x ; main = square (square 3)
To start with, the graph of our program consists of just the node
main. For reference
we’ve also drawn the graph of the supercombinator
square, though we don’t evaluate this
until it appears in
main is a
supercombinator with no arguments, so it is a redex. We reduce it by replacing it with its
body, yielding the following graph:
The outermost redex is the top node - the outer application of
square. To reduce it, we
replace the redex with an instance of the supercombinator body, substituting any
parameters with a pointer to the argument of the application. This gives us:
We see that the inner redex
(square 3) is now shared between two application nodes.
Notice that this transformation has resulted in a true graph rather than a tree. The
subgraph coloured blue is the instantiated body of
The application of
* cannot be reduced because
* is a strict primitive and requires
both its arguments to be evaluated first. Hence the only redex is the inner
The subgraph coloured blue is the second instantiation of
square. The only redex is now
the inner multiplication, so we reduce that.
And now we can reduce the outer multiplication, which directly yields
So the general steps are:
- Find the next redex
- Reduce it
- Update the root of the redex with the result
Unwinding the spine
To find the next redex, we need to find the leftmost outermost function application. To do that we follow these steps:
- From the root of the graph, follow the left branch until you reach a supercombinator or primitive.
- Check how many arguments the supercombinator or primitive takes and go back up the graph that number of times - you’re now at the root of the outermost function application.
The chain of left-branching application nodes is called the spine, and the process of traversing it like this is called known as unwinding the spine. The function arguments are typically stored on a stack to make them easy to access.
If the function is a supercombinator, then we’ve found a redex. If it’s a primitive, then we may first need to reduce the arguments to the function before the application becomes reducible.
If we need to reduce an argument, we must put the current stack to one side and begin unwinding again from the root of the argument. We may need to repeat this if the argument contains further unevaluated function applications. To keep track of these stacks we use a stack of stacks, known as a dump. When we need to evaluate an argument we push the current stack on to the dump, and when we’ve finished evaluating it we pop the old stack off the dump.
A supercombinator is reduced by substituting arguments into its body. If there are
let(rec) expressions in the body, they are represented as paths in the graph. For
let y = 3 in + y y
is represented as
let expression defines a sub-expression
3, which is named
y. The body of the
let expression references
y via pointers to
3. In this way, the single instance of
y is shared between the two arguments to
Let’s look at a more complex example: the reduction of a supercombinator application.
f x = let y = * x x in + y y main = f 3
We start with the
which reduces to
which reduces to
We can see that both arguments to
+ point to the same sub-expression (labelled
both arguments to
* point to the same instance of
3. The outermost application is that
+, but it requires both of its arguments to be evaluated first. Both arguments are
the inner application of
*, which we can reduce. This gives us the following:
which reduces to
Reducing supercombinator applications
When reducing a supercombinator application, there are two things we must consider:
- The argument may contain redexes, so we want to avoid copying it.
- The redex may be shared, so we want to update it with its result after reduction.
To do this we construct a new instance of the supercombinator body, substituting a pointer to the argument in place of the function parameter. This avoids having to copy the argument, which may be large. Once we’ve reduced a redex, we overwrite the root of the redex with the result of the reduction. This ensures that any other references to it will not have to reduce it again.
There’s one case we need to be careful of, however. Consider the following Core program:
id x = x main = let y = 4 in * (id y) y
After some reduction, the graph of this program looks like this:
Let’s consider the reduction of
(id 4). If we were to naively update the root of the
redex with the result, we’d end up with the following.
4! If this was a large expression, we would be at risk of doing extra
work reducing it twice. To get around this, we can add a new type of node: an indirection
node. This node simply points to another node, and we can use it to update the root of
the redex without duplicating the result. Using an indirection node (marked by a
get the following:
We can then reduce this in the normal way. When we encounter an indirection node we simply
skip over it and look at its target. In one step this reduces to
Those are the basics of graph reduction. In the next section we’ll apply this theory to our first compiler: the template instantiation machine.
In this case we could call it a tree, but trees are just a specific type of graph. Later on we’ll see that certain transformations on the tree will make it no longer a valid tree. So for simplicity we’ll refer to everything as a graph.↩︎