Out: Tuesday, 11 March 2008
Due: 5 PM Friday, 21 March 2008
Submission: Individual
This assignment is to be done individually, not in pairs.
One purpose of this assignment is to get experience writing code that manipulates a particularly important class of tree-structured data: abstract syntax trees for programs. Another purpose is to explore different kinds of program transformations and understand what sorts of transformations are guaranteed to preserve observable program behavior. By the end of this assignment, you should be comfortable writing programs that manipulate syntax trees.
transform-diff-zero-simple
and transform-diff-zero*; the first illustrates
the core operation of a simple transformation on an
EXPLICIT-REFS expression,
-( exp1 , 0 ) ==> exp1while the second illustrates one way to generalize that transformation so that it is applied repeatedly to an entire source expression (and returns an unchanged copy of the input expression if the transformation is inapplicable).
transform-diff-zero*,
there is a comment:
;; Note we check applicability using rgt* rather than rgt.
;; What would happen if we instead checked applicability
;; using rgt below?
Determine how the behavior of transform-diff-zero*
would change if one were to make that change to its source code
(that is, if we were to do (exp-to-mnum rgt)
instead of (exp-to-mnum rgt*) in the test
of the cond clause),
and describe the change to its behavior in mp6.txt.
transform-diff-consts-simple,
which illustrates the core of the following transformation
-( num1 , num2 ) ==> num3where
num3 = num1 - num2.
transform-diff-consts-simple,
when given the input expression -(3,1),
should return an abstract syntax tree for the expression 2.transform-diff-consts-simple,
when given the input expression -(a,2),
should return #f.
Usually transformations return
abstract syntax trees rather than booleans,
but transform-diff-consts-simple
is only meant to illustrate the core of the transformation.
transform-diff-consts*,
which generalizes the transformation from Task 2 by applying
the core transformation repeatedly everywhere in an input expression until
the transformation is no longer applicable.
let x = 3 in -(5,4)
should be transformed into the expression
let x = 3 in 1.let f = proc (x) -(7,5) in (f 8)
should be transformed into the expression
let f = proc (x) 2 in (f 8).let x = -(5,-(3,2)) in x
should be transformed into the expression
let x = 4 in x.let x = 3 in -(5,x) should be left alone,
as the transformation is inapplicable.For this task, your function should produce an unchanged copy of the input expression when the transformation is inapplicable.
transform-rename,
which takes an input expression exp
and two symbols, old-id and new-id, as
arguments, and has the following behavior:
exp contains any occurrence
of new-id, transform-rename signals an error.exp contains a free occurrence
of old-id, transform-rename signals an error.transform-rename returns an expression
exp' where every occurrence of old-id
is replaced with new-id.
old-id is x
and the new-id is y):
let x = 3 in proc(w) x
should be transformed into the expression
let y = 3 in proc(w) y.let w = 3 in proc(x) x
should be transformed into the expression
let w = 3 in proc(y) y.let z = 3 in z
should be transformed into the expression let z = 3 in z
(which happens to be the same as the input).let x = 3 in proc(y) x
should signal an error.proc(w) let z = x in w
should signal an error.letrec x = proc(w) (y w) y = proc(w) (y 2) in (x 3)letrec x (w) = (y w) y (w) = (y 2) in (x 3)
should signal an error.letrec x = proc(w) (z w) z = proc(w) (z 2) in (x 3)letrec x (w) = (z w) z (w) = (z 2) in (x 3)
should be transformed to the
expression
letrec y = proc(w) (z w) z = proc(w) (z 2) in (y 3)letrec y (w) = (z w) z (w) = (z 2) in (y 3).
Note that you can write tests to check that your function signals an error
on particular inputs, by using the symbol error as an outcome in the test;
see the error-illustration tests in mp6-test.scm.
transform-constprop*
that implements the following transformation
let x = n in e1 ==> e2where
e2 is e1 with
every free occurrence of
the variable reference expression x replaced
with the constant expression n.
let w = 3 in w
should be transformed to the expression 3.let w = let x = 3 in x in proc (y) w
should be transformed to the expression proc (y) 3.
let w = let w = y in 3 in w
should be left alone, as the transformation is inapplicable.
let w = 3 in let f = proc (w) w in (f w)
should be transformed to the
expression let f = proc (w) w in (f 3).
Hint: the transformations above may appear simple, but take
care in how you implement them. In particular, make sure you
properly observe the scoping rules for letrec
expressions.
It also may be useful to define some environment-like data structure
to track the mapping relationship between variables and the known constants.
You are given the following interpreters:
The easiest way to copy the interpreters into one of your own
directories is to use the cp command on a CCIS Solaris
machine:
cp -r /course/csg111/.www/interps/explicit-refs .
mp6.txt that contains
your answer for task 1.
mp6.scm.
This module should be written in the language
(lib "eopl.ss" "eopl"),
require the module "lang.scm",
and should
provide the procedures you wrote for tasks 2 through 5,
in addition to the procedures provided in the
staff-supplied mp6.scm.
(You may define help procedures as well, but they
should not be provided.)
"mp6-test.scm".
The module should be written in the language
(lib "eopl.ss" "eopl"), require
the modules "drscheme-init.scm",
"lang.scm"
and "mp6.scm",
and should test all of the procedures provided by
mp6.scm.
mp6-test module,
in a file named mp6-test-output.txt.
One way to do this is to take the contents of the
DrScheme interaction window and paste it into a
fixed-width text processor.
There is also a "Save Interactions as Text..." command, under
the "Save Other" submenu of DrScheme's File menu.
Whatever technique you use, make sure you double-check that the
submission is just plain text and that it matches the output you see
when you run the mp6-test module.
Last modified: 20 March 2008