Machine Problem 6: Program Transformations

Out: Tuesday, 11 March 2008

Due: 5 PM Friday, 21 March 2008

Submission: Individual

This assignment is to be done individually, not in pairs.

Purpose

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.

Tasks

  1. [1pt] (A warm-up exercise) Read over the provided mp6.scm source code, along with its tests in mp6-test.scm.
    In particular, make sure you understand both the specification and implementation of the procedures 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 ) ==> exp1
    
    while 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).
    In the source code for 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.
  2. [3pts] (A second warm-up exercise) Define a procedure transform-diff-consts-simple, which illustrates the core of the following transformation
      -( num1 , num2 ) ==> num3
    
    where num3 = num1 - num2.
    Examples:
    • 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.
  3. [6pts] Define a procedure 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.
    Examples:
    • The input expression let x = 3 in -(5,4) should be transformed into the expression let x = 3 in 1.
    • The input expression let f = proc (x) -(7,5) in (f 8) should be transformed into the expression let f = proc (x) 2 in (f 8).
    • The input expression let x = -(5,-(3,2)) in x should be transformed into the expression let x = 4 in x.
    • The input expression 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.

  4. [10pts] Define a procedure transform-rename, which takes an input expression exp and two symbols, old-id and new-id, as arguments, and has the following behavior:
    • If exp contains any occurrence of new-id, transform-rename signals an error.
    • If exp contains a free occurrence of old-id, transform-rename signals an error.
    • Otherwise, transform-rename returns an expression exp' where every occurrence of old-id is replaced with new-id.

    Examples (for the following examples, the old-id is x and the new-id is y):
    • The input expression let x = 3 in proc(w) x should be transformed into the expression let y = 3 in proc(w) y.
    • The input expression let w = 3 in proc(x) x should be transformed into the expression let w = 3 in proc(y) y.
    • The input expression 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).
    • The input expression let x = 3 in proc(y) x should signal an error.
    • The input expression proc(w) let z = x in w should signal an error.
    • The input expression 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.
    • The input expression 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.

  5. [10pts] Define a procedure transform-constprop* that implements the following transformation
      let x = n in e1  ==> e2
    
    where e2 is e1 with every free occurrence of the variable reference expression x replaced with the constant expression n.
    Examples:
    • The input expression let w = 3 in w should be transformed to the expression 3.
    • The input expression let w = let x = 3 in x in proc (y) w should be transformed to the expression proc (y) 3.
    • The input expression let w = let w = y in 3 in w should be left alone, as the transformation is inapplicable.
    • The input expression 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).
    For this task, your function should return an unchanged copy of the input expression when the transformation is inapplicable.

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.

Infrastructure

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 .

Deliverables

  1. A text file mp6.txt that contains your answer for task 1.
  2. A PLT Scheme module 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.)
  3. A PLT Scheme module "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.
  4. The output obtained by running your 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.
  5. A Development Diary

Back to Machine Problems

Felix S Klock II

Last modified: 20 March 2008

Valid XHTML 1.0!