Teaching G7400 F'10 Assignments Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10

### Problem Set 9: State and Garbage

 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: specify the garbage collector as a reduction rule; develop a the garbage collector; and 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: `cll`, which is applied to one value and returns a cell; `set`, which consumes a cell and a value `v`, sets the cell to `v`, and returns the value in the cell; `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 `i`th 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.

 last updated on Sun Nov 21 19:38:23 EST 2010 generated with PLT Scheme