Semester 2, 2018

# Tute (Week 7)

## 1 Abstract Machines

### 1.1 The E Machine

Evaluate the following expression using E-machine rules given in the lecture (where $$\mathtt{Num}$$ is abbreviated to $$\mathtt{N}$$):

$\small (\mathtt{Apply}\ (\mathtt{Fun}\ (f.x. \mathtt{If}\ (\mathtt{Less}\ x\ (\mathtt{N}\ 2))\ (\mathtt{N}\ 0)\ (\mathtt{Apply}\ f\ (\mathtt{Minus}\ x\ (\mathtt{N}\ 1)))))\ (\mathtt{N}\ 3))$

You don't need to write down every single step, but show how the contents of the stack and environments change during evaluation.

Feel free to skip even more steps of evaluation here. Just noting down the pattern of environments sitting on the stack that emerges, which is relevant to the third question.

$\scriptsize\begin{array}{cl} & \circ\ \vert\ \bullet \succ (\mathtt{Apply}\ (\mathtt{Fun}\ (f.x.\ (\mathtt{If}\ (\mathtt{Less}\ x\ (\mathtt{N}\ 2))\ (\mathtt{N}\ 0)\ (\mathtt{Apply}\ f\ (\mathtt{Minus}\ x\ (\mathtt{N}\ 1))))))\ (\mathtt{N}\ 3))\\ \mapsto_E & (\texttt{Apply}\ \square\ (\texttt{N}\ 3)) \triangleright \circ\ \vert\ \bullet \succ (\texttt{Fun}\ (f.x.\ (\texttt{If}\ (\texttt{Less}\ x\ (\texttt{N}\ 2))\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1))))))\\ \mapsto_E & (\texttt{Apply}\ \square\ (\texttt{N}\ 3)) \triangleright \circ\ \vert\ \bullet \prec \langle\!\langle\bullet ; f.x.\ \cdots \rangle\!\rangle\\ \mapsto_E & (\texttt{Apply}\ \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle\ \square) \triangleright \circ\ \vert\ \bullet \succ (\texttt{N}\ 3)\\ \mapsto_E & (\texttt{Apply}\ \langle\!\langle\bullet ; f.x.\ \cdots \rangle\!\rangle\ \square) \triangleright \circ\ \vert\ \bullet \prec 3\\[0.5em] & \text{Let \eta_1 be the environment: } f = \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle, x = 3, \bullet\\[0.5em] \mapsto_E & \bullet \triangleright \circ\ \vert\ \eta_1 \succ (\texttt{If}\ (\texttt{Less}\ x\ (\texttt{N}\ 2))\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1))))\\ \mapsto_E & (\texttt{If}\ \square\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1)))) \triangleright \bullet \triangleright \circ\ \vert\ \eta_1 \succ (\texttt{Less}\ x\ (\texttt{N}\ 2))\\[0.25em] & \text{Skipping some steps...}\\[0.25em] \mapsto_E & (\texttt{If}\ \square\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1)))) \triangleright \bullet \triangleright \circ\ \vert\ \eta_1 \prec \texttt{False}\\ \mapsto_E & \bullet \triangleright \circ\ \vert\ \eta_1 \succ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1)))\\ \mapsto_E & (\texttt{Apply}\ \square\ (\texttt{Minus}\ x\ (\texttt{N}\ 1))) \triangleright \bullet \triangleright \circ\ \vert\ \eta_1 \succ f\\ \mapsto_E & (\texttt{Apply}\ \square\ (\texttt{Minus}\ x\ (\texttt{N}\ 1))) \triangleright \bullet \triangleright \circ\ \vert\ \eta_1 \prec \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle\\ \mapsto_E & (\texttt{Apply}\ \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle\ \square) \triangleright \bullet \triangleright \circ\ \vert\ \eta_1 \succ (\texttt{Minus}\ x\ (\texttt{N}\ 1))\\[0.25em] & \text{Skipping some steps...}\\[0.25em] \mapsto_E & (\texttt{Apply}\ \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle\ \square) \triangleright \bullet \triangleright \circ\ \vert\ \eta_1 \prec 2\\ \end{array}$

$\scriptsize\begin{array}{cl} & \text{Let \eta_2 be the environment: } f = \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle, x = 2, \bullet\\[0.5em] \mapsto_E & \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \succ (\texttt{If}\ (\texttt{Less}\ x\ (\texttt{N}\ 2))\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1))))\\ \mapsto_E & (\texttt{If}\ \square\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1)))) \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \succ (\texttt{Less}\ x\ (\texttt{N}\ 2))\\[0.25em] & \text{Skipping some steps...}\\[0.25em] \mapsto_E & (\texttt{If}\ \square\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1)))) \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \prec \texttt{False}\\ \mapsto_E & \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \succ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1)))\\ \mapsto_E & (\texttt{Apply}\ \square\ (\texttt{Minus}\ x\ (\texttt{N}\ 1))) \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \succ f\\ \mapsto_E & (\texttt{Apply}\ \square\ (\texttt{Minus}\ x\ (\texttt{N}\ 1))) \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \prec \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle\\ \mapsto_E & (\texttt{Apply}\ \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle\ \square) \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \succ (\texttt{Minus}\ x\ (\texttt{N}\ 1))\\[0.25em] & \text{Skipping some steps...}\\[0.25em] \mapsto_E & (\texttt{Apply}\ \langle\!\langle\bullet ; f.x.\ \cdots\triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \prec 1\\[0.5em] & \text{Let \eta_3 be the environment: } f = \langle\!\langle\bullet ; f.x.\ \cdots\rangle\!\rangle, x = 1, \bullet\\[0.5em] \mapsto_E & \eta_2 \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_3 \succ (\texttt{If}\ (\texttt{Less}\ x\ (\texttt{N}\ 2))\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1))))\\ \mapsto_E & (\texttt{If}\ \square\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1)))) \triangleright \eta_2 \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_3 \succ (\texttt{Less}\ x\ (\texttt{N}\ 2))\\[0.25em] & \text{Skipping some steps...}\\[0.25em] \mapsto_E & (\texttt{If}\ \square\ (\texttt{N}\ 0)\ (\texttt{Apply}\ f\ (\texttt{Minus}\ x\ (\texttt{N}\ 1)))) \triangleright \eta_2 \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_3 \prec \texttt{True}\\ \mapsto_E & \eta_2 \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_3 \succ (\texttt{N}\ 0)\\ \mapsto_E & \eta_2 \triangleright \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_3 \prec 0\\ \mapsto_E & \eta_1 \triangleright \bullet \triangleright \circ\ \vert\ \eta_2 \prec 0\\ \mapsto_E & \bullet \triangleright \circ\ \vert\ \eta_1 \prec 0\\ \mapsto_E & \circ\ \vert\ \bullet \prec 0\\ \end{array}$

### 1.2 Closures

Give an example of a program that evaluates to one result if closures are not used with an environment semantics, and a different result if closures are used. You may use the MinHS dialect used in your assignment.

$\mathbf{let}\ x = 2\ \mathbf{in}\ (\mathbf{let}\ x = 3\ \mathbf{in}\ (\mathbf{recfun}\ f\ y = x))\ 1$

Evaluates to 3 with closures, and 2 without.

### 1.3 Tail Calls

Consider the following two programs:

sumInt :: Int -> Int
sumInt 0 = 0
sumInt n = n + (sumInt (n-1))

sumInt' :: Int -> Int
sumInt' n = sum2 0 n
where
sum2 m 0 = m
sum2 m n = sum2 (m+n) (n-1)


In a strict (call-by-value) language, the first program would lead to a stack overflow if applied to a sufficiently large number, but the second would not.

1. Explain how tail-call elimination can be applied to these examples.
2. How can we change the definition of our E-Machine to optimize tail-calls?
3. In Haskell, the second version will still exhaust all available memory if applied to a sufficiently large number. Why is this the case?

1: The first example is not tail-recursive, in that the last computation done by the function body is an addition, not a recursive function call.

In the second example, the last thing performed by the inner computation is a recursive function call, which means the stack frame allocated can be re-used for the function call, without allocating any more memory.

2: The pattern produced by tail calls in the E-Machine is a series of environments sitting on the stack with no intermediate computations, as in the above example.

Changing the rule for function application to include a special case when an environment is already on the stack (and not saving the current environment in that case) just leaves the environment that was first pushed onto the stack, and doesn't bother to save the rest:

$\small \dfrac{}{ (\mathtt{Apply}\ \langle\!\langle \eta_f; f.x.\ e \rangle\!\rangle\ \square) \triangleright \eta_s \triangleright s\ \vert\ \eta \prec v \mapsto_E \eta_s \triangleright s\ \vert\ f=\langle\!\langle \cdots \rangle\!\rangle, x=v, \eta_f \succ e }$

3: Haskell, being lazily evaluated, does not bother to evaluate the accumulator parameter until it is pattern matched on:

sum2 0 10 = sum2 (0 + 10) (10-1)
= sum2 (0 + 10) 9          -- evaluated from pattern match
= sum2 (0 + 10 + 9) (9-1)
= sum2 (0 + 10 + 9) 8      -- pattern match
= sum2 (0 + 10 + 9 + 8) (8-1)


As can be seen, the accumulator is constantly growing in size, as it is never matched on.

GHC can be fooled into evaluating the accumulator by doing a pointless pattern match:

sum2 0 0 = 0
sum2 m 0 = 0
sum2 m n = sum2 (m + n) (n - 1)


But a more idiomatic way is to use BangPatterns:

sum2 !m 0 = 0
sum2 !m n = sum2 (m + n) (n - 1)


Or, if extensions are not desired, the seq combinator, which forces evaluation of the left hand side before returning the right:

sum2 m 0 = 0
sum2 m n = let m' = m + n
in m' seq sum2 (m + n) (n - 1)


2018-11-16 Fri 19:37