The Meta-Circular Evaluator (1998)

CS212

Structure and Interpretation

of Computer Programs

Computer Science Department

Cornell University

Spring 1998

Problem Set 6: The Meta-Circular Evaluator

Issued: Tuesday, April 14, 1998.

Dueish: Friday, May 1, 1998.

We will accept late problem sets with no penalty (just as if you'd turned it in by May 1) until Friday, May 8, 4pm .

Note: the concepts and problems that dealt with in this assignment are the sorts of things practically guaranteed to show up on the second prelim and on the final. Make sure you understand every problem -- now is not the time to rely on a partner heavily.

Contents

• How The Interpreter Works
  • Brenda-Apply and Function Representation
  • Environment Manipulation
  • Classes and Type-Checking
  • Hints for Changing the Interpreter
• • Problem 5: Folding Constants
  • Problem 6: Folding Booleans
  • Problem 7: Folding Ifs
  • Problem 8: Variable substitution
  • Problem 8: Unbound Variable Error Detection

Loading the Interpreter

In a fresh NOODLLE, evaluate (load ps6) . Just to get familiar with the problem set, try evaluating (+ 1 2) in the interpreter. Read below for listings of the special forms and primitives you have been given.

How the Interpreter Works

In this problem set you will modify a program that evaluates expressions in a Dylan-like language. To keep the language the evaluator is written in and the language the evaluator evaluates distinct, we will call the interpreted language Brenda. The evaluator repeatedly reads in expressions from the user, evaluates the expression according to the rules of the Brenda programming language, and prints out the evaluated expression. We call this loop the read-eval-print loop. Below is the Dylan code for the read-eval-print loop in the Brenda interpreter:

<tt>(define read-eval-print-loop (method ()
  (bind ((raw (read))
         (result (brenda-eval raw *brenda-global-environment*)))
    (print "Brenda? " raw)
    (print "Brenda==> " result)
    (read-eval-print-loop))))</tt>

At this level the interpreter is very easy to understand, but to understand it in more detail, we will need to understand two things: the brenda-eval generic-function, and the structure of the *brenda-global-environment*.

Brenda-Eval

The brenda-eval generic function provides much of the functionality of the meta-circular evaluator. As you will recall from the environment model of expression evaluation, different kinds of objects are evaluated in different ways. Most objects evaluate to themselves, like <string> s, <number> s, <empty-list> s and <boolean> s, regardless of the environment in which they are being evaluated. When <symbol> objects are evaluated, the interpreter looks up their value in the environment in which they are being evaluated. Finally, <pair> objects (combinations or non-empty lists) are evaluated by evaluating the first element of the combination, and applying the function to the rest of the elements in the combination. This functionality is handled by brenda-apply . Here is the code from brenda.dyl for brenda-eval.

<tt>(define-generic-function brenda-eval ((obj <object>) (env <brenda-frame>)))

;; Most kinds of objects evaluate to themselves.
(add-method brenda-eval (method ((obj <object>) (env <brenda-frame>)) obj))

;; Evaluating symbols causes their associated value to be looked up.
(add-method brenda-eval (method ((obj <symbol>) (env <brenda-frame>))
  (lookup obj env)))

;; Evaluating a pair calls brenda-apply.
(add-method brenda-eval (method ((obj <pair>) (env <brenda-frame>))
  (brenda-apply (brenda-eval (head obj) env) (tail obj) env)))</tt>

As you can see, the code for brenda-eval is extremely short. Notice that brenda-apply is called with a list of unevaluated arguments! (This is so that we can implement special forms correctly.)

Brenda-Apply and Function Representation

The brenda-apply generic-function is called by brenda-eval whenever a combination is evaluated. In Brenda, as in Dylan, there are three kinds of objects that can be at the head of a combination: user-defined methods, special forms, and primitive methods. We will represent these different kinds of functions in Brenda with Dylan classes. Here are the type definitions for these objects:

<tt>;; All objects to which arguments can be applied are functions
(define-class <brenda-function> (<object>))

;; Methods have a fixed number of typed parameters and evaluate their args
(define-class <brenda-method> (<brenda-function>)
  (params <list>))

;; User methods are methods created with the method special form
(define-class <brenda-user-method> (<brenda-method>)
  (body <list>)
  (env <brenda-frame>))</tt>

<tt>;; Primitives are low-level functions that the user cannot express in Brenda.
(define-class <brenda-primitive> (<brenda-method>)
  (calls <function>))</tt>

<tt>;; Special forms (like define) do not follow normal evaluation rules.
(define-class <brenda-special-form> (<brenda-function>)
  (calls <function>))</tt>

Notice that both <brenda-primitive> s and <brenda-user-method> s must be instances of <brenda-method> because they both evaluate their arguments. Objects that are instances of <brenda-method> have a params slot which is a list of the parameters the method has. Primitive methods are simulated by Dylan code. The calls slot of a <brenda-primitive> is a Dylan function that can simulate the functionality of the particular primitive. Because primitives always evaluate their arguments, we call the Dylan function with the evaluated Brenda arguments. A <brenda-special-form> object has a calls slot like a <brenda-primitive> . This slot refers to a Dylan function that simulates the functionality of the special form. This Dylan function is called with the unevaluated Brenda arguments.

A <brenda-user-method> is a Dylan implementation of the closure objects we have been using in the environment model. They have three slots, params , body , and env . Params is simply a list of the parameters the method has. Body is a list of expressions to be evaluated when the method is applied. Env is the environment in which the method was defined. The ways in which environments are manipulated is discussed below.

Brenda-apply then is a generic function with three main cases, one for each of the function object types in Brenda. Here is the code for each of the cases of brenda-apply :

<tt>(define-generic-function brenda-apply ((obj <object>) (args <list>) (env <brenda-frame>)))


;; The default case is an error
(add-method brenda-apply (method ((obj <object>) (args <list>) (env <brenda-frame>))
  (brenda-error "Apply : First element in combination isn't a function." obj)))

;; Primitives
;; Evaluate the arguments in the environment in which the primitive is being
;; called. Apply the Dylan function that performs the work of the primitive
;; only after verifying the arguments satisfy the type constraints of the
;; parameters.
(add-method brenda-apply (method ((obj <brenda-primitive>) (args <list>) 
                                  (env <brenda-frame>))
  (bind (((evaluated-args <list>) (map (method (x) (brenda-eval x env)) args)))
    (args-params-match? (params obj) evaluated-args)
    (apply (calls obj) evaluated-args))))

;; Special Forms
;; Just apply the Dylan function that performs the work of the special form
;; without evaluating the arguments. Assume the special form will perform
;; type checking.
(add-method brenda-apply (method ((obj <brenda-special-form>) (args <list>) 
                                  (env <brenda-frame>))
  ((calls obj) args env)))

;; User methods
;; Extend the environment the method was defined in with a frame containing
;; the arguments bound to the parameters. Evaluate the body in this new
;; environment.
(add-method brenda-apply (method ((obj <brenda-user-method>) (args <list>) 
                                  (e <brenda-frame>))
  (bind (((evaluated-args <list>) (map (method (x) (brenda-eval x e)) args)))
    (args-params-match? (params obj) evaluated-args)
    (bind ((new-env (expand-environment (params obj) evaluated-args (env obj))))
      (eval-sequence (body obj) new-env)))))</tt>

Each of the brenda-apply cases are quite simple, with the exception of application of a user-defined method. Application of a user method is performed in two steps. First the environment in which the method was defined is extended with a new frame containing the variables bound to the parameters. Then the body of the method is evaluated in this new environment. The brenda-apply code makes use of some helper functions, like eval-sequence , brenda-error , and args-params-match? , which are defined inbrenda.dyl.

Environment Manipulation

In the environment model, an environment is defined as an ordered list of frames. A frame is defined as an unordered set of bindings, and a binding is an association of a name (symbol) and a value (object). Given these definitions, we can provide a fairly natural implementation of environments with the following code from classes.dyl:

<tt>(define-class <brenda-frame> (<object>)
  (bindings <list>))

(define-class <brenda-local-frame> (<brenda-frame>)
  (previous <brenda-frame>))

(define-class <brenda-global-frame> (<brenda-frame>))

(define-class <brenda-binding> (<object>)
  (variable <symbol>)
  (value <object>))</tt>

Although our definitions for frames are simple, there are a number of operations we want to perform on our environment structures, such as looking up a binding, looking up a name, and changing the value of a binding. In the fileframes.dyl there are a number of definitions and helper functions that provide this functionality. Below is a summary of the functionality provided for you inframes.dyl:

find-binding	Finds a <brenda-binding> object with a given name in an environment structure. Returns #f if not found.
lookup	Finds the value associated with a given name in an environment structure. Generates an error if not found.
set-binding!	Destructively changes a binding given a name and a new value.
define-binding!	Destructively changes the *brenda-global-environment* to have a new binding.
define-primitive!	Destructively changes the *brenda-global-environment* to have a new primitive function.
expand-environment	Given an environment, and list of arguments, and a parameter list, returns a new environment built on top of the given one with the arguments bound to the parameters.

Classes and Type Checking

Inside the interpreter we must have a way to enforce type constraints within method , define and bind statements. Unfortunately, some of the objects within the interpreter are represented with their corresponding Dylan object, and some are represented more abstractly using Dylan structures. For instance, a symbol in Brenda is represented with a Dylan <symbol> object. A Brenda method is not represented with a Dylan <method> object; it is represented with a <brenda-user-method> instance.

Because we have objects in the interpreter represented with different kinds of Dylan objects (some native data, some Dylan structures) we will map each type of object to an associated Brenda class object. Brenda class objects will be represented with Dylan structures, and will have one slot: super-classes , which will refer to its super classes:

<tt>(define-class <brenda-class> (<object>)
  (super-classes <list>))</tt>

<tt>(define make-brenda-class (method ((sc <list>))
  (make <brenda-class> super-classes: sc)))</tt>

We will define global variables in Dylan for each kind of class we'll need within Brenda:

<tt>(define brenda-object-class (make-brenda-class ())) ;; Type <object>
(define brenda-type-class (make-brenda-class ;; Type <type>
  (list brenda-object-class)))
(define brenda-class-class (make-brenda-class ;; Type <class>
  (list brenda-type-class)))</tt>

<tt>;; number classes
(define brenda-number-class (make-brenda-class ;; Type <number>
  (list brenda-object-class)))
(define brenda-integer-class (make-brenda-class ;; Type <integer>
  (list brenda-number-class)))
(define brenda-float-class (make-brenda-class ;; Type <float>
  (list brenda-number-class)))</tt>

<tt>;; symbol classes
(define brenda-symbol-class (make-brenda-class ;; Type <symbol>
  (list brenda-object-class)))</tt>

<tt>;; method classes
(define brenda-function-class (make-brenda-class ;; Type <function>
  (list brenda-object-class)))
(define brenda-method-class (make-brenda-class ;; Type <method>
  (list brenda-function-class)))</tt>

<tt>;; boolean class
(define brenda-boolean-class (make-brenda-class ;; Type <boolean>
  (list brenda-object-class)))</tt>

<tt>;; list classes
(define brenda-list-class (make-brenda-class ;; Type <list>
  (list brenda-object-class)))
(define brenda-pair-class (make-brenda-class ;; Type <pair>
  (list brenda-list-class)))
(define brenda-empty-list-class (make-brenda-class ;; Type <empty-list>
  (list brenda-list-class)))</tt>

<tt>;; string classes
(define brenda-string-class (make-brenda-class ;; Type <string>
  (list brenda-object-class)))
(define brenda-character-class (make-brenda-class ;; Type <character>
  (list brenda-object-class)))</tt>

Then we'll have a generic function brenda-get-class to tell us which of the above classes should be associated with each kind of data the interpreter uses. For instance, brenda-function-class would be the Brenda class associated with a <brenda-special-form> and brenda-symbol-class would be the Brenda class associated with a <symbol> .

<tt>(define-generic-function brenda-get-class (obj))
(add-method brenda-get-class (method ((obj <object>)) brenda-object-class))
(add-method brenda-get-class (method ((obj <brenda-class>)) brenda-class-class))
(add-method brenda-get-class (method ((obj <brenda-primitive>)) brenda-method-class))
(add-method brenda-get-class (method ((obj <brenda-special-form>)) brenda-function-class))
(add-method brenda-get-class (method ((obj <brenda-user-method>)) brenda-method-class))
(add-method brenda-get-class (method ((obj <boolean>)) brenda-boolean-class))
(add-method brenda-get-class (method ((obj <character>)) brenda-character-class))
(add-method brenda-get-class (method ((obj <pair>)) brenda-pair-class))
(add-method brenda-get-class (method ((obj <empty-list>)) brenda-empty-list-class))
(add-method brenda-get-class (method ((obj <float>)) brenda-float-class))
(add-method brenda-get-class (method ((obj <integer>)) brenda-integer-class))
(add-method brenda-get-class (method ((obj <string>)) brenda-string-class))
(add-method brenda-get-class (method ((obj <symbol>)) brenda-symbol-class))</tt>

Now given any object within the interpreter, we can find out which <brenda-class> it is associated with. Before we get to how type checking works, we need to define another helper function called subclass? . Subclass? takes two <brenda-class> es, and determines if the first is a subclass of the second.

<tt>(define subclass? ;; is B a subclass of A?
  (method ((a <brenda-class>) (b <brenda-class>))
    (if (id? a b)
    #t
    (orn (map (method (a1) (subclass? a1 b)) (super-classes a))))))</tt>

Now to determine if an object o within the interpreter is an instance of some <brenda-class> x , we find the class of the object o and check to see if the class of o is a subclass of x :

<tt>(define brenda-instance? (method ((obj <object>) (bc <brenda-class>))
  (subclass? (brenda-get-class obj) bc)))</tt>

We use brenda-instance? to enforce type constraints within the interpreter. We do not have to enforce singleton types because Brenda does not support them.

Hints for Changing the Interpreter

With seven different source files, it can be confusing as to which you need to change to implement some new functionality in Brenda. Here is a quick summary of what is in each of the files:

ps6.dyl	Loads the other files, prints out diagnostic messages as it works.
classes.dyl	Dylan class definitions, Brenda class definitions
frames.dyl	Environment manipulation code.
brenda.dyl	Read-eval-print loop, brenda-eval , brenda-apply
primitives.dyl	Code for + , - , * , / , = , pair , head , tail
special-forms.dyl	Code for if , method
utilities.dyl	Simple, generally useful functions.

Make sure you've read the sources! Often times you'll only have to write a short piece of code that combines the functions we've given you in new ways. If you get the interpreter into a state where it won't load, watch the diagnostic messages that print during startup so you can figure out roughly where the problem is. If that doesn't help you, introduce your own brenda-debug-print lines so you can refine where the problem is.

Although it is time consuming, reload the entire interpreter each time you make a significant change in a fresh NOODLLE. This will prevent duplicate class definitions from conflicting, and will reduce the problems you experience in general. The Brenda interpreter can be slow to load, so try to work on the fastest system available to you.

Above all, think about how you are going to solve a problem before you dive into it. Doing this on this problem set more than ever will serve you well.

Change the stack limit to 5000 before you do anything. You won't make through even one addition unless you do.

Problem 0: Quote

For this problem you will add the special form quote ( ' ) to the interpreter. Quote should take one argument and simply return it unevaluated. (Hint: this is pretty much the easiest-to-define special form in existence. This should not take a lot of code.)

Sample output:

Brenda? (quote foo)
Brenda==> foo
Brenda? (quote 3)
Brenda==> 3
Brenda? (quote foo bar)
Quote : Takes 1 argument only.

Problem 1: Define

For this problem you will add the special form define to the interpreter. Define should take two arguments: a variable specifier, and an expression. The variable specifier should either be of the form symbol or (symbol <type>) . The expression should be evaluated in the global environment, and the global environment should be destructively modified to contain a new binding. If the binding exists, it should be reset. If the optional type is present, then you should check the the result of evaluating the expression satisfies the type constraint. If it does not, you should signal an error.

Sample output:

Brenda? (define x 12)
Brenda==> x
Brenda? (define (y <integer>) (+ 1 (* x x)))
Brenda==> y
Brenda? (define (z <number>) "hello")
Argument doesn't conform to type.
Brenda? x
Brenda==> 12
Brenda? y
Brenda==> 145
Brenda? (define x)
Define : Too few arguments.
Brenda? (define x 2 3)
Define : Too many arguments.
Brenda? (define null? (method ((x <list>)) (= x (quote ()))))
Brenda==> null?
Brenda? (null? (quote (1)))
Brenda==> #f
Brenda? (null? (quote ()))
Brenda==> #t

Problem 2: Bind-methods

For this problem you will add the bind-methods special-form to Brenda. Bind-methods should accept two or more arguments; the first should be a list of method bindings, and the rest should be a series of one or more Brenda expressions. Each binding should be of the form (name parameters body) . Name should be a symbol. You should examine the code for the method special-form. Using the helper functions provided, you should parse each of the method bindings, and construct a <brenda-user-method> from each. Then bind each of the methods into a frame and associate them with their name. Your code should handle mutually recursive functions, that is, functions that call each other. All the methods will have to be define in the same frame in order to support mutually recursive functions.

Sample Output

<tt>Brenda? (bind-methods ((f (x) (+ x 2))) (f 3))
Brenda==> 5
Brenda? (bind-methods ((f x (+ x 2))) (f 3))
Bind-Methods : Badly formed parameter list.
Brenda? (bind-methods 
          ((f (x) (if (= x 0) 1 (g (- x 1))))
           (g (y) (* 2 (f y))))
          (g 3))
Brenda==> 16
Brenda? (bind-methods ((g ((y <integer>)) (* 2 (+ 1 y)))) (g 3.4))
Argument doesn't conform to type.
Brenda? (bind-methods 
          ((f (x) 39 x 6)     ;;; hint:  make sure that you treat this differently from
                              ;;;        (39 x 6) -- it's easy to do 39 x 6 in this case, too.
           (g (y) (* 2 y)))
          (+ (g 3) (f 42)))
Brenda==> 12</tt>

Problem 3: Streams

In this question, you will implement streams in Brenda, with streams behaving exactly as covered in lecture. There are many ways to do this, but the one that we're going to pick is to add a special form to the language. Implement the special forms cons-stream , head-stream , and tail-stream . The contract for these functions is exactly the same as for cons , head , and tail . Unlike regular old lists, however, streams can be infinitely long.

To do this problem, you will need to have some method of doing delayed evaluation . This is similar to what happens with the special form if , for example -- the second or third argument is evaluated after the first. In this case, however, we need a much more general way of doing this. Delayed evaluation can be achieved in a variety of ways: we can use macros, or we can use a concept called thunks . These are basically equivalent, but since you've seen macros before, we'll use thunks.

A thunk is a class with four slots -- it stores the expression which is to be evaluated later, and it stores the environment in which the expression is to be evaluated, a boolean flag to indicate whether the expression has already been evaluated, and the value if it has been.

For this problem you will need to do the following:

• Define the class <thunk> .
• Add a new special form or function cons-stream to Brenda. (Hint: this doesn't require much code.)
• Add a new special form or function tail-stream to Brenda. (Hint: this doesn't require much code.)
• Add a new special form or function head-stream to Brenda. (Hint: this requires even less code.)

In order to do tail-stream , you will probably find it useful to add a method to brenda-eval for thunks. Also, if you implement thunks in such a way as to not require special forms for any of those the three stream operations, implement them as functions.

Hint: this problem can get very, very frustrating if you don't think about what you're doing before you actually do it. The amount of code you have to write is minimal; the amount of thinking you have to do is not. One way to get started is to ignore the part about saving values of evaluated thunks -- it can be added quite easily later.

Sample Output

Brenda? (define (integers-from <function>)
                   (method (n)
                     (cons-stream n (integers-from (+ n 1)))))
Brenda==> integers-from
Brenda? (define integers (integers-from 0))
Brenda==> integers
Brenda? (head-stream integers)
Brenda==> 0
Brenda? (head-stream (tail-stream integers))
Brenda==> 1
Brenda? (define nth
          (method ((p <object>) (n <integer>))
            (if (= n 0)
               (head-stream p)
               (nth (tail-stream p) (- n 1)))))
Brenda==> nth
Brenda? (nth integers 5)
Brenda==> 5
Brenda? (nth integers 10)
Brenda==> 10

You may assume that all streams are infinite.

Warning (again): this question requires very little coding. If you find yourself writing a lot, stop writing and start thinking.

Problem 4: More streams

Note: the code for problem 4 should be written in Brenda, not in Dylan.

In this problem, you will be asked to write a few functions to operate on streams. First, write a function merge that, given two streams s = (s1 s2 ... ) and t = (t1 t2 ... ) , returns a stream (s1 t1 s2 t2 ...) , alternating elements between the two input streams. Then write a function intersect that takes two ordered streams of numbers and returns a stream containing all the items that occur in both streams, still in order. You may assume that both streams are infinite.

Next, write a function map-stream that does to a stream exactly what map does to a list. That is, (map-stream f s) should return a stream s2 such that (f (nth s i)) == (nth s2 i) . Along the higher-order functions line, write a function filter-stream that does the equivalent of filter : (nth (filter-stream f s) i) is the i th element of s that satisfies f . You may assume that the input stream is infinite for both functions.

Hint: you may need a helper function or two to implement this properly.

Sample Output

Brenda? (define (mult-stream <function>)
               (method (stream factor)
                 (cons-stream (* factor (head-stream stream))
                              (mult-stream (tail-stream stream) factor))))
Brenda==> mult-stream
Brenda? (define divis-by-3 (mult-stream integers 3))
Brenda==> divis-by-3
Brenda? (define divis-by-5 (mult-stream integers 5))
Brenda==> divis-by-5
Brenda? (define divis-by-15 (intersect divis-by-3 divis-by-5))
Brenda==> divis-by-15
Brenda? (head-stream divis-by-15)
Brenda==> 0
Brenda? (head-stream (tail-stream divis-by-15))
Brenda==> 15
Brenda? (head-stream (tail-stream (tail-stream divis-by-15)))
Brenda==> 30

Brenda? (map-stream (method ((x <integer>)) (* x x)) integers)
Brenda==> (0 1 4 9 16 25 ... )

Brenda? (define odd-ints (filter-stream (method (x) (not (= (* 2 (/ x 2)) x))) integers))
Brenda==> odd-ints == (1 3 5 7 9 ... )
Brenda? (define even-ints (map-stream (method (x) (+ x 1)) odd-ints))
Brenda==> even-ints
Brenda? (define ints (merge odd-ints even-ints))   ;; what would happen if we intersected instead?
Brenda==> ints  == (1 2 3 4 5 ... )

Part 2: The compiler

Note (to avoid confusion): you are now done with Brenda. This next chunk of the problem set is about transforming Dylan programs to Dylan programs. (More precisely, a subset of Dylan programs to a subset of Dylan programs.)

For this entire section of the problem set, we are limited to the functional subset of Dylan -- there are no set! s in the code that you will be optimizing. (And, as always, you shouldn't use side-effects unless you have to.) You may also assume that bind s have been nested so that only one variable is bound at a time.

The major portion of this section of the problem set involves optimization. Optimization consists of taking in a Dylan expression and producing another Dylan expression with the same behavior, but can be evaluated more quickly. We have given you the skeleton of an optimizer right now -- what the optimizer does currently is to return exactly its input. Note that this does fit the contract -- it returns Dylan code that computes the same value as the original -- but is not very useful. When you're done, though, that will change. (Hopefully what will change is that it will become useful, not that it will violate the contract!)

Loadps6-opt.dyl to get started.

Problem 5: Constant Folding

Suppose that you have the Dylan expression (+ 1 2) . Since you know the values for each of + , 1 , and 2 , you can determine that this expression will behave exactly the same way as the expression 3 , except it will take more time to compute. So we'd like to replace all expressions of this form with something of the form 3 . To do this, write a function const-fold that, given an expression e1, will return a new expression e2, such that all arithmetic expression with known operator and numerical (known) operands are replaced by their values.

Sample output:

? (const-fold '(+ 1 2))
==> 3
? (const-fold '(* x 1))
==> (* x 1)
? (const-fold '(+ (* 3 4) x))
==> (+ 12 x)
? (const-fold '(/ x 0))
==> (/ x 0)
? (const-fold '(/ 1 0))
==> {Error : "Binary/ : Attempt to divide by zero."}
? (const-fold '(* (+ 1 2) (/ (+ x (* 2 4.2)) 18)))
==> (* 3 (/ (+ x 8.4) 18))

Now, add calls to your const-fold to the optimizer so that optimize now does constant folding. After you've done this, we'll have:

? (optimize '(+ 1 3))
==> 4
? (optimize '(if (= (* 2 2) (+ 2 2)) (- x 3) (- 9 3)))
==> (if (= 4 4) (- x 3) 6)
? (optimize '(method (x) (+ 1 2)))
==> (method (x) 3)

Problem 6: Folding Booleans

Now optimizer does constant folding, but only for numerical constants. Thus for example, it does not optimize expressions like (= 3 4) or (not t). On the other hand, folding booleans is just like folding numerical expressions, except you have to account for different symbols. (Hint: it should be fairly easy to extend your solution to problem 5 to handle booleans as well.)

Warning: due a bug in NOODLLE, attempting to apply the special form and or the special form or does not work. However, apply ing (method (x y) (and x y)) does work. If (hint, hint) you might want to apply one of these, apply the second form instead. You can assume only binary uses of and and or .

? (optimize '(= 3 4))
==> #f
? (optimize '(not #f))
==> #t
? (optimize '(not (> 5 6)))
==> #t
? (optimize '(if (= (* 2 2) (+ 2 2)) (- x 3) (- 9 3)))
==> (if #t (- x 3) 6)

For this problem, hand in the listing of all procedures that you modified, as well as the output from the above test cases.

Problem 7: Folding if s

By now the optimizer folds all primitive applications. In order to make it more powerful, we should also examine the possibilities of folding other expressions. In particular, let's examine if. When it is possible to evaluate the condition, the if statement reduces to either consequent or alternate. In either case it is possible to eliminate if altogether, keeping just the portion of the code which will be evaluated. Modify the procedure optimize-op which handles if statements to do this folding.

? (optimize '(if (> 3 4) (+ 3 4) (* 3 4)))
==> 12  
? (optimize '(if (> a b) 1 2))
==> (if (> a b) 1 2)
? (optimize '(if (> a b) (+ 1 2) (- 1 2)))
==> (if (> a b) 3 -1)
? (optimize '(if (= (* 2 2) (+ 2 2)) (- x 3) (- 9 3)))
==> (- x 3)

For Problem 7 hand in the listing of your modified optimize-op along with the output proving that your if folding works on the above examples.

Problem 8: Substituting for binds

We've now done a pretty decent amount of optimization -- so much so that we may have made something that the programmer did seem pretty, well, dumb. We could now be down to a binding of the form (bind ((x 3)) b) for some body b . If the 3 had been a complicated expression that was optimized down, this could actually happen. We'd like to replace this simple binds by just substituting the values for the variables in the succeeding body. You've now heard about alpha-conversion: to make your lives simpler, you may assume that alpha conversion has been performed on the input code before this optimization occurs. Note that if this step is not performed, then trying to substitute 3 for x in

(bind (((identity <function>) (method (x) x))) identity)

is tricky. You certainly don't want this to have the value

(bind (((identity <function>) (method (3) 3))) identity)

since this is a syntax error. For that matter, you don't want

(bind (((identity <function>) (method (x) 3))) identity)

either, because the x that got replaced was actually a different x , the parameter to the identity function.

Write a function substitute that will take a symbol (the thing to replace), some object (the thing to replace it with), and a source program (any old object).

? (substitute 'x 3 '(bind ((y x)) x))
==> (bind ((y 3)) 3)
? (substitute 'x 'y '(define (identity <function>) (method (x) x)))
==> (define (identity <function>) (method (y) y))
? (substitute 'x 'not-gonna-happen '(bind ((z y) (y z)) 42))
==> (bind ((z y) (y z)) 42)

Now, add (an) appropriate call(s) to substitute in your optimizer such that whenever a variable gets bound to a constant value, the return value is instead the result of substituting the value for the variable in the body. [Possibly worth some extra credit: why are we limiting ourselves to constant values? Give an example where doing more would be a bad idea.]

? (optimize '(bind ((x 3)) x))
==> 3
? (optimize '(bind ((x 'foo)) (bind ((y 2)) (bind ((z (bar y))) (z x)))))
==> (bind ((x (quote foo))) (bind ((z (bar 2))) (z x)))
? (optimize '(bind ((val (/ 22 7)))
               (bind ((test (> val 3.14)))
                   (bind ((result 2.71828))            
                       (if test result (- result))))))
==> -2.71828

Hand in your code for substitute and any methods you've modified for this problem. Also hand in an example program that would be broken by the "optimization" if we were not limited to the functional subset of Dylan.

Problem 9: Detecting Unbound Variable Errors

One of the simplest sorts of errors that one can make when programming is to refer to a variable that doesn't exist. If x isn't defined in the global environment, then

(define (inc <function>) (method (y) (+ x 1)))

will generate an error when it's applied. It may seem like this is an error that you'd never make, but suppose you decided to change the name of a parameter and then forgot to change in the body of your function. We'd like to write a checker function that will confirm that a given program will never run across an unbound variable error.

To do this, write a function all-bound? that will return #f just in case there is an unbound variable occurring somewhere in the input function. That is, all-bound? will be a function taking a program as input. For our purposes, a program may be any sort of object (remember that 3 is a legal program).

Here are some rough ideas on what you'll need to do to write this function:

• start with some initial top-level environment. This should include the symbols + - * / , and maybe some others. These will be the symbols that are always defined.
• start looking through the input program, maintaining a list of the currently-defined symbols. When you run across a symbol in the program check to make sure that it's in your list of defined symbols. If it's not, die. If it is, keep going.
• method s can allow more symbols to be defined (the parameters) as can bind s. When you run across these, add to your list of currently-defined symbols.
• bind-methods is tricky. You need to recall that mutually recursive functions are legal, so that one function can refer to the name of another function defined later in the bind-methods .
• You do not need to concern yourself with define s.

This is a hard question -- sit down and think about all of this for a while before you start coding.

? (all-bound? 3)
==> #t
? (all-bound? '(method (x) x))
==> #t
? (all-bound? '(bind ((x y)) x))
==> #f
? (all-bound? '(bind-methods ((f (x) (g x)) (g (y) (f y))) (f g)))
==> #t
? (all-bound? '(bind-methods ((f (x) (h x)) (g (y) (f y))) (f g)))
==> #f

Last modified 4/26/1998 by AYN.