MCS-287 Chapter 5 Homework (Spring 2000)

  1. 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:
  2. 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