Due date: 10/19 @ at the beginning of class
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.
The module 5.rkt provides a solution for
problem set 5 to get you started here. Copy the file and rename it.
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.
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.
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.
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.
Formulate a conjecture concerning the relationship of eval-c and
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:
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.
;; NameOfPartner1, NameOfPartner2
;; firstname.lastname@example.org, email@example.com