Gmachine
20170617 22:02
This post is about using an abstract machine to implement a nonstrict functional language.
A nonstrict language does not evaluate expressions until they are required.
For example, [1..]
is a valid expression, it's an infinite list of ascending integers starting from 1.
A functional language allows you to name and pass functions around. For example map add1 [1..10]
applies the function add
to each element in the list.
Machines
Gmachine is a compilerbased graph reduction machine.
This compiler takes as input a simple intermediate language called Core, and compiles the code into Gmachine instructions. Then, these instructions can be run on the machine.
This is in contrast with other implementation such as template instantiation, where you traverse some of the Core code only at runtime.
Core language
The compilation works on Core, which is language simplified from a higher level nonstrict functional language such as Haskell.
Supercombinators
The following example Core program evaluates to 42:
main = double 21
double x = x + x
This program has two supercombinator definitions. main
and double
are functions, the variables after that but before the equals sign are the arguments to the function, and the expression on the righthandside (rhs) is the body of the function.
main
is a special supercombinator: it is the starting point of program execution.
Local definitions
Supercombinators can have local definitions in the form of let
or letrec
expressions
main = quadruple 20 ;
quadruple x = let twice_x = x + x
in twice_x + twice_x
infinite n = letrec ns = cons n ns
in ns
quadruple
defines locally twice_x
, to be used in the body of the let expression. This is useful for naming intermediate values and to avoid recomputing the same value twice.
infinite
declares ns
and uses ns
at the same time  the definition of ns
is recursive.
Algebraic Data Types (ADTs)
In many functional languages, such as OCaml in the example below, algebraic data types are defined by the user like so:
type colour = Red  Green  Blue
type complex = Rect of int * int  Polar of int * int
Red
, Green
, Blue
, Rect
, and Polar
, are called constructors, because you use them to construct values of the ADTs.
We can pattern match on these ADTs using a match expression:
match colour with
 Red > "Red"
 Green > "Green"
 Blue > "Blue"
In Core, we use a simple, uniform representation for constructors, and transform pattern matching into simple case expressions.
We use Pack
to define constructors:
Red = Pack{1,0}
Green = Pack{2,0}
Blue = Pack{3,0}
Rect = Pack{1,2}
Polar = Pack{2,2}
The first argument identifies a constructor in the ADT, and the second argument is the arity of the constructor, (how many arguments it requires).
A case
expression is used to determine alternative in an ADT a value is:
isRed = case c of
<1> > True ;
<2> > False ;
<3> > False
Arithmetic
Lastly, Core has arithmetic:
main = 1 + 1
And comparison:
main = if (2 > 1) 2 1
How is evaluation done?
The Gmachine works in terms of a stack and heap.
A stack contains pointers to items in the heap, and heap contains nodes, representing numbers, application, etc.
Given this example:
f g x = K (g x)
The machine will be in the state where the top of the stack is the function f
, the next item is a pointer to an application of f
to g
, and the next item is a pointer to an application of f g
to x
.
[]> @
/ \
[]> @ x
/ \
[]> f g
The goal then becomes to evaluate the function K (g x)
.
To evaluate a function application, g x
, the function and the arguments have to be pushed onto the stack first.
This is done by using the Push
instruction:
Push 1:
[]> @
/ \
[]> @ x <\
/ \ 
[]> f g 

[]/
The way 1 is counted is to ignore the top of the stack, which is the supercombinator node, and to start counting from 0.
Then x
needs to be pushed onto the stack:
Push 1:
[]> @
/ \
[]> @ x <\
/ \ 
[]> f g <\ 
 
[]+/
[]/
Now apply the function by creating an application node, using Mkap
:
Mkap:
[]> @
/ \
[]> @ x <\
/ \ 
[]> f g <\ 
 
[]> @  
/ \+/
\/
Mkap
creates an application node using the top two items of the stack.
Now we need to apply K
to (g x)
, since K
is a supercombinator, we can directly push it using Pushglobal
:
Pushglobal K
[]> @
/ \
[]> @ x <\
/ \ 
[]> f g <\ 
 
[]> @  
/ \+/
\/
[]> K
And use Mkap
to apply K
to its arguments:
Mkap:
[]> @
/ \
[]> @ x <\
/ \ 
[]> f g <\ 
 
[]> @  
/ \  
K @  
/ \+/
\/
Finally we have replaced f g x
with its body K (g x)
, so we can remove the old nodes:
Slide 3:
[]> @
/ \
K @
/ \
g x
In summary, the code generated for a supercombinator is to:
 construct the rhs of the supercombinator
 Slide n + 1, where n is the arity of the supercombinator
 Unwind
Where Unwind
is the instruction to cause machine evaluation to continue.
To recap, the key instructions are:
Push
Mkap
Pushglobal
Slide
Unwind
Minimal Gmachine
The Gmachine uses a fivetuple for it's state:
type gm_state =
gm_code (* current instruction stream *)
* gm_stack (* current stack *)
* gm_heap (* heap of nodes *)
* gm_globals (* global addresses in heap *)
* gm_stats (* statistics of machine *)
gm_code
is a list of machine instructions:
type gm_code = instruction list
The gm_stack
is a list of addresses in the heap:
type gm_stack = addr list
gm_heap
is a heap mapping addr
to node
, and can be implemented as a list, with list index as addr
.
type gm_heap = node list
gm_globals
is an association list of names to addr
in heap:
type gm_globals = (name * addr) list
The Gmachine runs by dispatching on each instruction.
Pushglobal
looks up the name in gm_globals
and pushes the node in the heap onto the stack.
Pushint
allocates an integer node on the heap, and pushes the address onto the stack.
Mkap
uses two addresses at the top of the stack to build an application node in the heap.
Push
is used to copy an argument that is passed to a function. It has to look at the application node at the (n+1)th place, and look at the rhs of the node.
Slide
tidies the stack by popping addresses off the stack.
Unwind
is always the last instruction of a sequence, and will construct a new state based on what's on top of the stack.
NNum
, the Gmachine has terminatedNAp
, must continue unwinding from next nodeNGlobal
, jump to the supercombinator code by putting it ontogm_code