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

### Problem Set 6: The AST Machine

 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 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; the --> relation still allows statements to be reduced everywhere in the program; simplify the constraints and their auxiliary functions as much as possible, deleting useless definitions; and 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.

 last updated on Wed Nov 7 10:09:15 EST 2012 generated with Racket