MCS-287 Chapter 5 Homework (Spring 2000)

Do exercise 5.4.2 on page 153. To be more explicit about what exercise 5.1.5 accomplished, and what is on the agenda here:
- In exercise 5.1.3 we eliminated all the definitions given on page 143, from the define-record of prim-proc through the definition of init-env. We replaced those five definitions with the following two:
```
(define apply-proc apply)

(define init-env
  (extend-env '(+ - * add1 sub1)
              (list + - * (lambda (x) (+ x 1)) (lambda (x) (- x 1)))
              the-empty-env))
```
- Now we are going to leave those two definitions alone. In particular, we are not going to use the definition of apply-proc given on page 153.
- We are also going to eliminate the define-record of closure given on page 152. In particular, this means that make-closure will no longer be defined (automagically) as the constructor for this record type, since there will no longer be any such record type.
- Instead, you are to define make-closure as a normal procedure. It will be called from eval-exp as shown on page 153.
Variables that get assigned (mutable variables) need to be represented using cells (or some similar approach), but those that don't get assigned can be handled more simply. Thus it is useful to go through a program and mark all variable occurrences with a boolean flag indicating whether the variable is a mutable one. To illustrate this, I've added varassign to the lambda calculus. (You could do this with a language from lab 1 or 3 instead, if you'd prefer.)
```
> (parse '(lambda (p) ((lambda (x) (varassign x (p x)))
                       (lambda (x) x))))
#(struct:lambda
  p
  #(struct:app
    #(struct:lambda
      x
      #(struct:varassign
        x
        #(struct:app #(struct:varref p) #(struct:varref x))))
    #(struct:lambda x #(struct:varref x))))

> (analyze-mutability 
   (parse '(lambda (p) ((lambda (x) (varassign x (p x)))
                        (lambda (x) x)))))
#(struct:lambda
  #(struct:var p #f)
  #(struct:app
    #(struct:lambda
      #(struct:var x #t)
      #(struct:varassign
        #(struct:var x #t)
        #(struct:app
          #(struct:varref #(struct:var p #f))
          #(struct:varref #(struct:var x #t)))))
    #(struct:lambda
      #(struct:var x #f)
      #(struct:varref #(struct:var x #f)))))
```
Notice that each occurrence of a variable (p or x) has been upgraded from being just a symbol to being a two-element record called a var, containing the name of the variable and the mutability flag:
```
(define-record var (name mutability))
```
Write analyze-mutability. You can do this any way you like, but one interesting approach is to take advantage of mutability of the var record structures. If all the first three occurrences of x get replaced with a single var, then we can turn the mutability flag on once and have it show up three places. See below for an example of turning a flag on:
```
(define sample-var
  (make-var 'x #f)) ;variable called x, not mutable (that we know of yet)

> sample-var
#(struct:var x #f)

(set-var-mutability! sample-var #t) ;set it to mutable

> sample-var
#(struct:var x #t)
```
As a simplification, you may assume that the expression you are analyzing has no free variables.

Instructor: Max Hailperin