## 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

S (λ x. add1) (λ x. x) 2  ; introduce S
```

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.