## Abstract Machines for Graph Reduction

## Notes for Ethan Albin's presentation

### Turner '79

(λ x. + x x) (add1 2)

Graph representation:

Rewrite as:

Christopher Wadsworth's 71 thesis is credited.
David Turner looks at a FP program without free variables. We can convert any term to a small set of combinations and define a machine based on those combinatord.

S, K, Y combinators:

(((S f) g) x) = (f x) (g x)
K x y = x
I x = x
(λ x. add1 x) 2
S (λ x. add1) (λ x. x) 2 ; introduce S
S (K add1) I 2

Avoid manually stepping and looking at each node.

We have a graph and a heap:

Problems with representing programs with these three combinators:

- Quadratic blow-up in compiler time and space
- No obvious room for optimization

In early 1980s there were two hardware implementations of this.

### Hughes '83

Take a term, break it down into those "super combinators," and run those.

*Super Combinator:* combinator; no free variables; abstraction; inside the body, any abstractions are also super combinators.

λ x. (λ y. (+ x y) x) 2

Not a super combinator. *x* is free in *+ x y*

(λ x. ((λ w λ y . + w y) x x) 2)

Super combinator: *(λ w λ y . + w y)*

[P w y = + w y], (λ x . P x x) 2
Main := (λ x . P x x)
[Main x = P x x]
λ x1 ... λ xn . E
E != λ
t in E
λ => Super Combinator

- Combinator = closed terms
- Super combinator = no free variables in expression
- SC representation = IR representation

### Augustsson '84-87

Define a machine with stack, graph, control, and dump

Linear sequence of instructions that does the work of a super combinator.
At start, stack has pointer to *root*, *w*, and *y*.

DEF GLOBAL P2
PUSHG +
PUSH 1 ;; 1 is w
MKAP
PUSH 2 ;; 2 is y
MKAP
UPDATE d
UNWIND

Creating nodes, but need to overwrite *root* with the result of the reduction.

Given some sequence of applications, how do we know which is the root of the reductions?
Which to overwrite?
At start, we're given a pointer to *root*.

Unwind moves back up and picks up the args.