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

Problem Set 2: Abstract Syntax, Evaluation via Reduction

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:

  1. bullets#, which consumes a "program" in B and counts the number of bullets it contains;
  2. swap, which consumes a "program" in B and replaces t with f and vice versa; and
  3. 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.

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