Assignment Elimination

This transformation eliminates the set! form from the incoming expression, translating it from analyzed form to assignmentless form.

This transformation involves changing all instances of the set! special form to calls to the vector-set! primitive, and shadows all bindings of side-effected variables with bindings of that same variable to a vector containing that variable. Basically, this pass selectively boxes all the assigned variables:

(lambda (x)         ==> (lambda (x)
  '(assigned x)           (let ((x (vector x)))
  (set! x (+ x '1)))        (vector-set! x '0
                              (+ (vector-ref x) '1))))

Of course, let isn't really in our language anymore (except for the one holding the heap literals at the top of the expression), and we have to keep the information about free variables current, so this is the real transformation:

(lambda (x)         ==> (lambda (x)
  '(assigned x)           '(free)
  '(free)                 ((lambda (x)
  (set! x (+ x '1)))         '(free)
                             (vector-set! x '0
                               (+ (vector-ref x '0) '1)))
                           (vector x)))

There are three kinds of expressions that are affected by this transformation:

Variable References: If a variable reference foo is a reference to an assigned variable (i.e., if it is in the environment we pass down), then it must be changed to (vector-ref foo '0). Otherwise it should be left alone.
Assignment Expressions: All assignment expressions must be transformed:
(set! foo exp) ==> (vector-set! foo '0 exp)
Lambda Expressions: Any assigned variables in the lambda expression must be shadowed by ``let'' expressions re-binding those variables to vectors containing the values of the variables. Thus:
```
(lambda (x y z)    ==> (lambda (x y z)           
  '(assigned x z)        '(free w)               
  '(free w)              ((lambda (x z)          
  body)                     '(free w y)            
                             body)     
                          (vector x) (vector z)))
```
A sticky issue comes up with this transformation: What are the free variables of the introduced lambda -- in the above example, (lambda (x z) ...)?

Skeleton

The procedure assignmentless-form deals with taking off the let expression binding heap-allocated quotations and then putting it back.

(define assignmentless-form 
  (lambda (exp)
    (let ([qdecls (cadr exp)]
	  [subexp (caddr exp)])
      (let ([new-subexp (assignment-convert subexp '())])
	`(let ,qdecls ,new-subexp)))))

(define assignment-convert
  (lambda (exp env)
    (if (not (pair? exp))
	...
	(record-case exp
	  [quote (obj) ... ]
	  [begin (a b) 
	    (let ([a-exp (assignment-convert a env)]
		  [b-exp (assignment-convert b env)])
	      `(begin ,a-exp ,b-exp))]
	  [if (t c a) ... ]
	  [set! (v e) ... ]
	  [lambda (formals poked free body) ... ]
	  [else ... ]))))

ehilsdal@cs.indiana.edu