Due date: 11/23 @ at the beginning of class

The goal of this problem set is to experiment with the CESK machine for ISWIM.

Warning: The second and third problem of this problem set depend on a solution of the first problem.

Problem 0:

Construct a Redex model of the CESK machine for one of the three variants of ISWIM (from problems 5(1), 5(2), or 5(3)). Your model's eval function must produce the same results as the standard reduction semantics.

Problem 1:

Equip the Redex model of problem 0 with a garbage collector:

1. specify the garbage collector as a reduction rule;
2. develop a the garbage collector; and
3. validate the garbage collector against the rule.

The choice of validation method is left to you but it should represent a strong effort.

Problem 2:

Equip the Redex model of problem 0 with a new kind of values: logged cells. A logged cell is like a one-field structure that comes with three operations:

1. cll, which is applied to one value and returns a cell;
2. set, which consumes a cell and a value v, sets the cell to v, and returns the value in the cell;
3. log, which returns a log of all changes to the cell. A log is a function from integers to values. Specifically, 0 is mapped to the number of changes the cell has undergone. If a log returns n at 0, then applying it to i between 0 and n, it produces the ith value that occupied the cell. For any other value, it produces 0.

It is appears possible to implement the cell operations as macros or as native ISWIM-Cell functions. Discuss in one paragraph (at most 57 words) which alternative you consider the better one and why.