It may not yet be clear to you why lisp and scheme include symbols as one of the base types. Yet they are the key to the enormous popularity of these languages for certain types of applications. This assignment concentrates on these sorts of symbolic processing applications. The first three problems build up to a stripped down implementation of the original function calculator language. The last two problems implement a symbolic differentiation routine.
The solutions will often be suprisingly short and to the point. Using s-expressions as the object syntax within a meta-language designed around s-expressions is a huge win. The trade off is that you won't have types to help you catch some errors and may for example find yourself cdr'ing off the end of a list at runtime (which you could never do in ML).
The solutions to the first three problems build on one another and the last two problems will also likely share some support functions with the first three. You should submit a single file containing the solutions to all of the problems you complete. Use the mini-scheme comment character (a semicolon will comment the remainder of a line) to add comments as appropriate. Place each support function just before the first function which uses it, and place a comment (preferably a line of dashes) before the beginning of the solution to each problem.
Problem 1 -- A Simple Calculator:
Write a function called eval which takes an s-expression representing a numerical
expression built up from numbers and the pre-fix binary operators +, -,
*, /, and ^, and calculates the value of the expression.
The operator ^ is for exponentiation. Since this is not a built-in in our mini-scheme
you will need to write a function to evaluate it. You may assume that the exponent is an integer,
but make sure you deal correctly with negative exponents. Call the evaluation function
eval1 to distinguish it from the versions to be written below.
Here are a few examples:
>(eval1 3) 3 >(eval1 '(+ 4 5)) 9 >(eval1 '(^ 2 3)) 8 >(eval1 '(^ 2 -3)) 0.125 >(eval1 '(+ 4 (* (- 2 5) (/ 1 2)))) 2.5
If an error occurs during evaluation (i.e. if a string or symbol turns up where a number should be, or something other than one of the 5 built-in operators appears in operator position), you should print an error message, but then continue as though the erroneous subexpression had the value 0 (since our mini-scheme language does not include any sort of error/exception mechanism). For example:
> (eval1 'x)
(Error -- Symbol in expression: x)
0
> (eval1 '(+ 3 x))
(Error -- Symbol in expression: x)
3
> (eval1 '(+ 3 "3"))
(Error -- String in expression: "3")
3
> (eval1 '(+ 3 ()))
(Error -- Null in expression: ())
3
> (eval1 '("+" 3 4))
(Undefined operator in expression: ("+" 3 4))
0
> (eval1 '(+ 3 ("+" 3 4)))
(Undefined operator in expression: ("+" 3 4))
3
The easiest way to deal with the errors is to write a function like the one below, which prints its argument and then returns 0.
(defun (error err)
(sequence (write err)
(newline)
0))
Then within the evaluation function (which will be structured as a large cond testing
the structure of the given expression) you could include lines like:
(cond ((null? exp) (error (list 'Error '-- 'Null 'expression: exp)))
((string? exp) (error (list 'Error '-- 'String 'in 'expression: exp)))
((number? exp) exp)
...
One thing that will make writing solutions to all these problems
substantially easier is to
notice that in an s-expression representing an expression consisting of an operator applied to
two operands, the operator may be found by taking the car of the s-expression,
the first argument by taking the cadr, and the second argument by taking the
caddr. It would help considerably, therefore, to define support functions such as:
In the absence of ML's type constructors and pattern matching, this can at least help to make your code easier to read and understand. It is strongly recommended that you define and make use of these three functions. They will make your code much easier to develop, understand, and modfiy.(defun (opr_of exp) (car exp)) ; or (define opr_of car) (defun (arg1_of exp) (cadr exp)) ; or (define arg1_of cadr) (defun (arg2_of exp) (caddr exp)) ; or (define arg2_of caddr)
Problem 2 -- A Simple Calculator with Variables:
Modify the solution to the last problem so that eval takes a list of variable assignments
as well as the expression, which may now include variables as well as numbers. The list
of variable assignments is just a list of two-element lists. The first element is the
variable name, the second is its value. Call the evaluation function eval2.
If you encounter a variable that is not in the assignment list, you should print an error message, but then continue as though the variable had the value 0. In the examples below I have put the variable lookup table on one line and the expression to be evaluated on the next line for clarity:
> (eval2 '((x 2) (y 3)) >> 3) 3 > (eval2 '((x 2) (y 3)) >> 'x) 2 > (eval2 '((x 2) (y 3)) >> 'z) (Unknown variable z) 0 > (eval2 '((x 2) (y 3)) >> '(+ 4 x)) 6 > (eval2 '((x 2) (y 3)) >> '(+ 4 (* (- 2 y) (/ 1 x)))) 3.5 > (eval2 '((x 2) (y 3)) >> '(+ 4 (* (- z y) (/ 1 x)))) (Unknown variable z) 2.5
Problem 3 -- A Simple Calculator with Variables and Functions:
Modify the solution to the last problem so that eval also takes a list of function definitions.
Defined function names may now appear in function position in addition to the five arithmetic
primitives. A function definition is a three element list: the first element is the function name,
the second element is the list of formal parameters, and the third element is the body of the function.
Call the evaluation function eval3.
As before, errors (such as undefined functions or functions applied to the wrong number of arguments) should lead to errors being printed and to the sub-expression that caused the error having the value 0. For example:
> (eval3 '((x 2) (y 3)) >> '((f (x) (+ x 1)) (g (x) (+ y x))) >> '(f 3)) 4 > (eval3 '((x 2) (y 3)) >> '((f (x) (+ x 1)) (g (x) (+ y x))) >> '(f y)) 4 > (eval3 '((x 2) (y 3)) >> '((f (x) (+ x 1)) (g (x) (+ y x))) >> '(g x)) 5 > (eval3 '((x 2) (y 3)) >> '((f (x) (+ x 1)) (g (y) (+ y 2))) >> '(+ (f 4) (* (- 2 y) (/ 1 (g x))))) 4.75 > (eval3 '((x 2) (y 3)) >> '((f (x) (+ x 1)) (g (y) (+ y 2))) >> '(+ 4 (* (- (z 2) y) (/ 1 x)))) (Unknown function z) 2.5
One thing to note: Due to the lack of a way to define mutually-recursive functions in mini-scheme,
it is not possible to write a function such as apply_defuned as we did in the ML
implementation (since it would have to be mutually recursive with eval3).
Therefore the fuctionality of apply_defuned will need to be rolled directly into the
code for that case of eval3.
Problem 4 -- Symbolic Differentiation of Polynomials:
In problem 2, evaluation amounted to computing the numerical value of a polynomial over the defined variables, given values for those variables. While this sort of numerical calculation is interesting, Lisp's strength is in symbolic processing. The key is to note that "evaluation" need not replace an expression with a number. It can just as easily replace an expression with another expression. In this problem you will take advantage of this idea to write a function which takes a polynomial and returns the first derivative of the polynomial with respect to some variable.
Write a function called diff_wrt which takes two arguments. The first
argument is a symbol: the name of the variable you want to differentiate with respect to.
The second argument is an s-expression representing a polynomial in that variable. The
syntax used for polynomials is the same as that used for expressions with variables in problem 2.
Any symbol (i.e. name, or number) other than the given variable should be assumed to be a constant
value for the purposes of differentiation.
The function should analyze the structure of the expression it is given in much the same way as the evaluation functions written earlier. However, it should simply apply the standard rules for symbolic differentiation. It should not attempt to evaluate anything (that is it should never apply the mini-scheme arithmetic operators). The manipulation being done is purely symbolic.
The examples below begin by building a partial application of diff_wrt customized
for differentiating with respect to x.
>(define dx (diff_wrt 'x)) dx <- ...> (dx 5) 0 > (dx 'x) 1 > (dx '(+ x 5)) (+ 1 0) > (dx '(+ x c)) (+ 1 0) > (dx '(+ x y)) (+ 1 0) > (dx '(+ x x)) (+ 1 1) > (dx '(+ x (+ x x))) (+ 1 (+ 1 1)) > (dx '(* 3 x)) (+ (* 3 1) (* x 0)) > (dx '(* 4 (^ x 3))) (+ (* 4 (* (* 3 (^ x (- 3 1))) 1)) (* (^ x 3) 0)) > (dx '(+ (^ x 3) (+ (^ x 2) (+ x 1)))) (+ (* (* 3 (^ x (- 3 1))) 1) (+ (* (* 2 (^ x (- 2 1))) 1) (+ 1 0)))
Problem 5 -- Simplifying a Polynomial:
Notice that the results produced by the last problem are quite hard to read. It would
be nice to have some procedure to simplify them. For this problem you are to write
a function called reduce which attempts to reduce the complexity of a polynomial
by simplifying some sub-expressions.
At a minimum, your function should recognize when both of the arguments to one of the
five arithmetic operators are both numbers, and if so, actually evaluate the operator.
Reduction should be done recursively on the argument expressions first, so that
expressions like (+ 1 (* 2 3)) (in which the second argument is an expression,
not a number) will be properly reduced. The reduction function should also take advantage of
the fact that addition and subtraction behave in special ways when one of their arguments is 0 (even
when the other argument is not a number), and that the other operators often behave in special ways
when one of their arguments is 0 or 1.
Notice that when a polynomial consists only of numbers, the function behaves just like the evaluator written in problem 1.
> (reduce '(+ 3 (* 3 5))) 18 > (reduce '(+ x (* 3 5))) (+ x 15)> (define it (dx '(+ x 5))) (+ 1 0) > (reduce it) 1
> (define it (dx '(+ x x))) (+ 1 1) > (reduce it) 2
> (define it (dx '(+ x (+ x x)))) (+ 1 (+ 1 1)) > (reduce it) 3
> (define it (dx '(* 3 x))) (+ (* 3 1) (* x 0)) > (reduce it) 3
> (define it (dx '(* 4 (^ x 3)))) (+ (* 4 (* (* 3 (^ x (- 3 1))) 1)) (* (^ x 3) 0)) > (reduce it) (* 4 (* 3 (^ x 2)))
> (define it (dx '(+ (^ x 3) (+ (^ x 2) (+ x 1))))) (+ (* (* 3 (^ x (- 3 1))) 1) (+ (* (* 2 (^ x (- 2 1))) 1) (+ 1 0))) > (reduce it) (+ (* 3 (^ x 2)) (+ (* 2 x) 1))
The result of just this simple reduction scheme is quite an improvement, but it is far from perfect.
Notice how in the second to last example it was unable to reduce the result to
(* 12 (^ x 2)) which would have been a better answer. To do this would require
analyzing the structure of the
arguments in the cases when they are not both numbers (and neither is 1 or 0).
For no particular extra credit, feel free to submit a version of reduce which attempts to
apply richer reduction heuristics. In general the problem of finding the "best" reduction
is quite hard (in part because the definition of "most reduced" representation may differ from
setting to setting), but every additional heuristic will improve the results a bit.
Programs like Mathematica and Maple contain a significant amount of code related to expression reduction.
This is an observation, not part of the assignment:
Notice that because we have chosen the same object syntax in the two applications,
symbolic and numerical calculation can easily be combined. For example, once could easily add an
operator named diff to the calculator which, given the name of a unary
function and a value, first calls diff_wrt to find the symbolic derivative of the
expression in the body of the function's definitition (with respect to whatever variable was stored
as the function's formal parameter) and then evaluates the resulting polynomial in an environment
where the variable is bound to the second argument of diff. For example:
> (eval4 nil >> '((f (x) (+ (^ x 3) (^ x 2)))) >> '(f 2)) 12> (eval4 nil >> '((f (x) (+ (^ x 3) (^ x 2)))) >> '(diff f 2)) 16
 |
This page copyright ©1998 by Joshua S. Hodas. It was built on a Macintosh. Last rebuilt on Fri, Apr 10, 1999 at 3:15 PM. |
http://cs.hmc.edu/~hodas/courses/cs131/projects/project09.html | |