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.