| Due date: 10/1 @ at the beginning of class
The goal of this problem set is to understand reduction relations in
the spirit of chapter I.1 of the Redex book, both in theory and in
practice. The latter continues the introduction to systematic program
design.
Problem 1:
Solve exercises 1.2, 1.4, and 1.6.
Problem 2:
Develop a data representation for language B in Racket.
Design the following functions:
-
bullets#, which consumes a "program" in B and counts the
number of bullets it contains;
-
swap, which consumes a "program" in B and replaces
t with f and vice versa; and
-
eval->, which implements the semantics-via-reduction for
B of section 1.6 (second box on page 11). For eval->
to implement the reduction semantics of B means to produce
specified outcome for every single program. How would you prove
that your implementation is equivalent to the specified semantics?
This is a bit of a challenge, and you may wish to design several
different implementations. Contemplate why.
You may wish to look over those sections in HtDP that deal with
evaluating Scheme and you may wish to read Part V, on Generative
Recursion.
If you think Racket poses a problem, let me know which language you'd
rather use instead. I'll probably approve it.
|
|