Due date: 10/19 @ at the beginning of class

Purpose: The goal of this problem set is to turn the "calculational" model of simple-lang into a "standard reduction" model. The latter is like a deterministic (not finite) state machine with programs as states and reduction rules as instructions.

---

Background:

The module 5.rkt provides a solution for problem set 5 to get you started here. Copy the file and rename it.

Problem 1:

Rename the provided reduction relation to ->simple-lang.v3 and modify is so that

1. the ==> relation applies only to the first statement in a block and so that two blocks are merged only when the inner's statement sequence is exhausted;
2. the --> relation still allows statements to be reduced everywhere in the program;
3. simplify the constraints and their auxiliary functions as much as possible, deleting useless definitions; and
4. create an example, called s-graph, for which this relation still generates a proper graph, not just a linear sequence of transition steps.

Problem 2:

Define the metafunction eval-c, which consumes a simple-lang s and produces a result r according to ->simple-lang.v3. You may assume a consistency theorem for the reduction relation.

Problem 3:

Create the standard reduction relation from ->simple-lang.v3. Call it ->sl-standard. Confirm that the standard reduction relation does not generate a graph for s-graph.

Problem 4:

Define a metafunction eval-s that consumes a simple-lang s and produces a result r according to ->sl-standard . You may assume a standard reduction theorem.

Problem 5:

Formulate a conjecture concerning the relationship of eval-c and eval-s.

Deliverable:

Send in a single Racket file. Its name should consist of the two last names in alphabetical order separated with a hyphen; its suffix must be .rkt.

Your file must start with the following two lines:

  ;; NameOfPartner1, NameOfPartner2 
  ;; email@of.partner1.com, email@of.partner2.com

appropriately instantiated of course. Also separate problems with lines of the shape ";; " followed by 77 "-". That gives you a width of 80 chars. Try to stick to this width for all of your code; it ensures basic readability.