CS212
Structure and Interpretation
of Computer Programs

Computer Science Department
Cornell University
Spring 1998

Problem Set 3
A Symbolic Algebraic Evaluator

Issued: Thursday, February 26
Due: Tuesday, March 10

About Partners and Academic Integrity

You may and are encouraged to work with a (at most one) partner on this problem set. If you do choose to work with a partner, you must hand in one copy of your solutions with both of your names on it. If you do work with a partner, you must work with the same partner on the entire problem set. (You may not work with one person for questions 1 and 2 and another for the rest of the problem set.)

You may not share your code with anyone other than your partner, if you have one. You may not look at anyone else's code.

Many of the problems in this (and later) problem sets require output. The output that you hand in MUST have been produced by the code that you hand in. If your code doesn't work, then you most definitely should not hand in output showing it working. If you write some function (that accepts arguments) and submit its output, please specify which arguments were given to the function to produce the output you are submitting.

You would be amazed at how easy it is to figure out that someone has cheated, either by copying code or handing in spoofed output. Doing so risks failure in the class or worse, including possibly expulsion. See the Cornell Code of Academic Integrity. If you have any questions about what you are or are not permitted to do, feel free to contact the course staff.

Before you start doing the assignment you may want to read a new Noodlle Troubleshooting page that describes the most common Noodlle error messages, known Noodlle bugs and workarounds.

The purpose of this problem set is to gain experience with generic functions and with evaluators for simple languages.

This problem set contains more code than problem sets 1 and 2. Get started early on understanding the code! (This is not a sit down in one night problem set). As before, unless otherwise stated, all problems must be accompanied with relevant output. And remember, don't turn in any code you didn't modify!

About the Evaluator

For this problem set, you will implement a symbolic algebraic evaluator. You will enter expressions into the evaluator; it will evaluate them and print out the result.

An important routine for such an evaluator is the built-in function called read. This function reads from the keyboard an expression typed in by the user and returns it unevaluated. For example, suppose we tell Dylan

? (define x (read))

After we hit ctrl-e, NOODLLE will try to evaluate (read). This causes NOODLLE to pause and wait for us to enter something. If we type an expression and click on eval, then x will be bound to the (unevaluated) expression we typed in. For example, if we type in 42 and click on eval, x will then have value 42. If we type (+ 40 2), x will be bound to a list of length three, with the three given elements. In the latter case the result will be the same as if we had typed

? (define x '(+ 40 2))

Note that this is not the same as giving x the value 42.

You should try the above define, just to see how read works.

The function read is used in the expression evaluator to allow the user to type in expressions, which are then converted into the internal representation of the evaluator using the function parse (which is part of the evaluator).

The basic operation of the evaluator consists of a loop that performs the following steps:

• reads something from the user,
• parses the expression to convert it into the internal interpreter data structures,
• evaluates the converted expression,
• "unparses" the resulting value back to printed form,
• prints the result,
• calls itself tail-recursively to repeat the process.

This is referred to as a read-eval-print loop, because the basic steps are read input, evaluate it, and print the result.

Here is the read-eval-print loop for the expression evaluator.

(define repl 
  (method ((environment <list>))
    (bind ((exp (read)))
      (when (not (= (head exp) 'quit))
            (print "ExpEv? " exp)
            (bind ((z (mini-command (head exp) (tail exp)
                                    environment)))
              (print "==> " (head z))
              (repl (tail z)))))))

The environment is the association of names with values, such as the fact that + refers to an operation for adding numbers, or that a user-defined variable x has some given value. The read-eval-print loop reads in an expression, and as long as it doesn't say to quit, calls the generic function mini-command in order to process the particular command given in the expression. We will cover the types of commands below.

The top-level of most evaluators looks much like this, except that the overall processing they perform on the input is somewhat more interesting. (In fact, Dylan itself is a particularly interesting evaluator. We will look at modifying one in Problem Set 6.)

For this problem set, our algebraic evaluator will read in algebraic expressions, perform some processing on them, and print out the result. We have provided you with a basic algebraic evaluator; your task in this problem set will be to extend it.

The function that gets you into the evaluator is called start-evaluator. It takes no arguments. Once you have done (load ps3), you should be able to do the following:

? (start-evaluator)
Welcome to the CS212 Algebraic Expression Environment
ExpEv? (print (+ (* 2 3) (- 5 1)))
==> (+ (* 2 3) (- 5 1))
ExpEv? (evaluate (+ (* 2 3) (- 5 1)))
==> 10
ExpEv? (quit)
?

Commands

The evaluator understands the following commands from the user:

Expressions

An expression is any one of the following (given here in prefix notation):

Parsing

When the evaluator evaluates a list whose head is the symbol evaluate or print, it expects that the second element of that list will be an expression that must be evaluated or printed. This expression can be a number, a symbol or a list. The expression is not manipulated directly, but rather is passed to the function parse, whose job it is to convert the list to an internal form that the evaluator can work with. For a primitive expression, which is a number or symbol, the parser simply leave s the expression alone. For a compound expression, which consists of an expression in parentheses, the parser converts the expression into an internal form, which is an object of type <exp>. The class <exp> is defined in ps3.dyl. An object of type <exp> has a treelike structure, in which each node contains an operator and the operands.

As currently implemented, the system requires each compound expression to be a binary operator (take exactly two arguments). This is the first thing that we will change, in order to allow functions to take any number of arguments. In doing so, however, we will still require that the primitive operations +, * ,- , /, and mod are stored as binary expressions, by converting from n-ary to binary. This will be important for the simplification rules that will be added later.

Important Routines

There are several key functions that are important for understanding how the evaluator works, and how to add to or modify its behavior.

The generic function parse takes an expression and a format and converts the expression into the appropriate internal representation. For symbols and numbers this just leaves them alone, for compound expressions, it finds the operator and the operands and calls the helper function parse-list. This function takes an operator and a list of operands, and depending on the type of the operator calls parse-operands with the appropriate arguments. Right now, parse-operands simply parses a list of two operands, but you will change it to be more general.

The generic function unparse takes an internal representation of an expression and converts it back into a printable form.

The generic function mini-command handles each possible interpreter command by calling the right combination of functions. For example, the method for handling an evaluate expression calls parse and then eval-exp. You will be adding new methods to mini-command as part of the problem set.

Programming Exercises

For all the programming exercises below, hand in all and only those procedures and class definitions that you write or modify for that particular exercise, together with any output that was requested for that exercise. Do not put extraneous code in the files that you submit.

After loading ps3.dyl, using the command (load ps3), start the command interpreter by evaluating (start-evaluator) at the Dylan prompt. Experiment with the commands described above: evaluate, print, and quit.

Problem 1: Multiple Arguments

Right now we can only input expressions where all the operators are binary (take exactly two operands). In this first problem you will change the evaluator to support n-ary expressions (any number of operands). We have set things up so that much of the support is already in the expression evaluator, you need only modify the procedure parse-operands. Right now parse-operands assumes that it is given a list of exactly two operands, and returns a list formed by parsing both of these operands. You need to change parse-operands to handle 1 or more operands, by converting the list of operands into binary expressions. In the case of 1 operand, there is an identity value, called ident, which you should use in converting a unary expression to binary.

The resulting code for parse-operands is very short, not much longer than what is there. You need to understand parse and parse-list, and how to use them in rewriting parse-operands. For this problem, turn in your definition of parse-operands, its operation on the following test cases, and some other examples of your code working. Do not change or hand in any other code for this problem.

? (unparse (parse '(+ 2 3 (* 4 5 6) 7)))
==> (+ 2 (+ 3 (+ (* 4 (* 5 6)) 7)))
? (unparse (parse '(- 1)))
==> (- 0 1)

Here's a sample session of the expression evaluator exercising this new functionality:

? (start-evaluator)
ExpEv? (print (* (+ 2 3 4) 5 6))
==> (* (+ 2 (+ 3 4)) (* 5 6))
ExpEv? (evaluate (+ 2 3 4))
==> 9
ExpEv? (evaluate (- 1))
==> -1

Problem 2: Functions

The current evaluator does not support user-defined functions. There is a define-function command in the interpreter, but the necessary support is not fully implemented. In particular, the method in the generic apply-func which handles user-defined functions (which are of type <comp>) calls the function extend-env which has not yet been defined. In this problem you will write this missing function. Do not modify or hand in any other code for this problem.

The function extend-env takes 3 arguments, a list of parameters, a list of corresponding values of the parameters, and an environment to extend. The environment is a list of bindings, which must be extended by adding new bindings for the given parameters and their values. For this problem, hand in your code for extend-environment, output showing that the evaluator now handles the case shown below, and some other examples of your code working.

? (start-evaluator)
ExpEv? (define-function square (x) (* x x))
==> square
ExpEv? (evaluate (square 3))
==> 9

Problem 3: Infix Form of Expressions

In this problem you will add the ability to get "better" output using infix form; e.g., (a + b) instead of (+ a b). You will add a new command to the expression evaluator. The command print-infix is analogous to the command print, but it prints the expression in infix rather than prefix form. The form of the command is (print-infix expr).

You don't have to deal with multiple arguments to arithmetic operations since internally all operations are binary. Only the arithmetic operators (+, -, *, /, and mod) should be printed in infix form. User-defined functions should be printed as f(arg1,...,argn) instead of (f arg1 ... argn).

You have to add a generic function unparse-infix similar to the unparse function but modified appropriately in order to produce output in infix form. Then you should add a method to mini-command to handle print-infix.

Turn in your code for unparse-infix and the new mini-command method, and show that it works for the example below and some other examples. Do not change or hand in any other code for this problem.

With your new print-infix command the following should work:

? (start-evaluator)
ExpEv? (print-infix (* (+ 2 3 4) 5 6))
==> ((2 + (3 + 4)) * (5 * 6))

Problem 4: Simplification

Now you will begin to tackle the problem of simplification. Simplification can be thought of as a static operation, while evaluation is dynamic. For example (evaluate (* x x)) will vary depending on what value is stored for x at the time the evaluation is called. Yet (evaluate (* (+ 1 1) x)) can be simplified to (* 2 x) at definition time. This simplification is static, while the evaluation of the expression will have to be dynamic. Such simplification is important in compiler design, and for your program assignment, could be used for simplification of function bodies (although you are not required to implement these improvements.)

For example, we would like expression (+ (* 1 x) (* x 1)) to simplify to (+ x x), since we know (* 1 x) should always return x. Similarly (+ x 0) should always return x.

As another example, if you call (define-constant y 5) and then (define-function foo (x) (+ x y)), a simplifying interpreter would define the body of foo to be (+ x 5). Or a call to (define-function foo(x) (+ x (* y 2))) should ultimately define foo to be (+ x 10). This is a type of code optimization.

Part (a).

The first stage of simplification is reducing defined variables to their constant values. You need to define new methods of simplify which take just symbols as arguments and return appropriate results. In these methods, any undefined variables should just return their variable-name, any numbers or operators should be unchanged. You also need to modify the existing simplify method which takes an expression of type <exp> together with an environment, by forcing it to call simplify on the operands of an expression before passing it to simplify-exp.

For this problem, turn in any new methods of simplify you define. In addition, turn in the one simplify method you change. Sample output is given here.

? (start-evaluator)
ExpEv? (define-constant y 10)
==> y
ExpEv? (simplify y)
==> 10

Part (b).

For the second stage of simplification, you will add five methods to the generic function simplify-exp which will do expression-level simplifications. You need to define one method for each of the five arithmetic operations, which will simplify based on the simple identities below, and in addition will simplify things like (+ 5 2). The structure will be similar to that of parse-list, though you only need to add five methods to simplify-exp. Note that constant-folding looks a lot like evaluation. In fact it is a very special case of evaluation, but evaluation is much more powerful.

Each method of simplify-exp takes the arguments op, args and env, and returns either a number or an internal representation of a compound expression (of type <exp>). Each method specializes on the type of operator, op, which will be +, -, *, /, or mod.

Your simplification methods should implement the following rules:

Important Note: In the last three cases, note that both E's don't necessarily need to be textually equal, just algebraically equal. For example, (- (+ x 3) (+ 3 x)) should evaluate to 0. You need to be able to handle this case (where E is both of the form (op var cst) AND (op cst var)), as well as the less difficult case when both "E's" are textually equal, of the form (op cst var) OR (op var cst). Remember that even though (+ x 3) is equal to (+ 3 x), (- x 3) does not equal (- 3 x), nor does (/ x 3) equal (/ 3 x), etc.

For this problem, hand in the five methods you have added to simplify-exp. Also submit output, showing your code running on these and some other examples:

? (start-evaluator)
ExpEv? (define-constant x 5)
==> x
ExpEv? (simplify (* 3 (+ x 4)))
==> 27
ExpEv? (simplify (+ y (* x 2))
==> (+ y 10)
ExpEv? (simplify (+ (rat 2 1) 1))
==> 3
ExpEv? (simplify (+ (+ x y) (* x 2)))
==> (+ (+ 5 y) 10 )
ExpEv? (simplify (+ y 0))
==> y
ExpEv? (simplify (/ y 1))
==> y
ExpEv? (simplify (- y y))
==> 0
ExpEv? (simplify (mod y 1))
==> 0
ExpEv? (simplify (mod y y))
==> 0
ExpEv? (simplify (mod 0 y))
==> 0
ExpEv? (simplify (/ (+ y 7) (+ y 7)))
==> 1
ExpEv? (simplify (mod (- y 5) (- y 5)))
==> 0
ExpEv? (simplify (- (+ y 1) (+ 1 y)))
==> 0
ExpEv? (simplify (- (- y 1) (- 1 y)))
==> (- (- y 1) (- 1 y))

Problem 5: Classes

In this problem you will implement a simple type hierarchy. Type hierarchies are at the heart of object-oriented languages, and are implemented very nicely in Dylan. It is often the case that developing an appropriate type hierarchy for a given program can be an intellectually challenging design task, yet the effort spent in constructing a good class system for your program will pay for itself many times over as you are writing the rest of your code.

You have seen two different ways of implementing mathematical expressions as classes in Dylan. In the Symbolic Differentiation lecture, an "addition object" like "3+5" was a class <sum> with an addend and augend slot. Here, the addend would be "3", the augend "5". Other binary operators were defined similarly, such as <exp> and <prod>. One could also add <subt> and <div> to this structure by defining new classes similarly. This hierarchy is an example of a "flat" hierarchy -- there is no inheritance of types. Although these mathematical objects all share the same structure -- an operation with two arguments -- the type structure does not exploit this structural similarity. As you know, one of the focuses of this course is to encourage you to exploit similarity whenever possible in your code to avoid redundancy and minimize the likelihood of errors.

The code in ps3.dyl also implements a flat type hierarchy, this one with only one element: the <exp> class. This class has a slot "operator" which contains the arithmetic operator for the expression, but no new types are defined. If we wanted to exploit the structural similarity of arithmetic expressions, we might define <exp> to be a simple parent type, containing only the operands slot, and then defining five subclasses of <exp>: <add-exp>, <sub-exp>, <mul-exp>, <div-exp>, and <mod-exp>, one for each of the five basic operations.

In this problem, convert the class structure given in the code ps3.dyl by redefining <exp> as described above, and defining the five new classes. Secondly, define a generic function "operator" which takes as its sole argument an object whose type is any of these subclasses and returns the operator encoded in the object. For example, if x is of type <add-exp>, then (operator x) ==> the unevaluated symbol for addition. Finally, ensure that all the calls to "make <exp>" are replaced with the appropriate constructor function for the subtypes you defined above.

You do not need to hand in the modifications of the calls to make for this problem, but we need to see that your implementations are correct. You should turn in your new class definitions listed above. You should also submit output for this problem. Your output for this problem should demonstrate that these class changes do not alter the behavior of the evaluator.