Problem Set 6, CS 257

No matter what happens, the U.S. Navy is not going to be caught napping.

-Secretary of the Navy Frank Knox
December 5, 1941

1. Do the following problems from the book:

   17.6
   19.6
   19.7
   19.8
   

2. Write and* and or*, which are just like and and or except that they're regular functions and thus can't short-circuit the evaluation of their arguments. This means

   (let ((n 0))
     (or (= n 0)
         (= (/ 12 n) 4)))   ; returns #t
   
   (let ((n 0))
     (or* (= n 0)
          (= (/ 12 n) 4)))  ; gets an ERROR - division by zero
   

   Observe that and* and or* must handle a variable number of arguments.

   Examples:

   (or* #f #f 'a 'b)     ; a
   (and* #f #f 'a 'b)    ; #f
   (or* 'a 'b 'c 'd)     ; a
   (and* 'a 'b 'c 'd)    ; d
   (or* 'a 'b 'c #f)     ; a
   (and* 'a 'b 'c #f)    ; #f
   (or* 'whatever)       ; whatever
   (or* #f)              ; #f
   (and* 'anything)      ; anything
   (and* #f)             ; #f
   (and*)                ; #t
   (or*)                 ; #f
   

3. Define a function expr1 which takes as a single argument an ``arithmetic expression'' and returns the number it evaluates to.

   An ``arithmetic expression'' is an s-expression which is either: a number, or a list of length three, of which the first element is an ``arithmetic operator,'' one of the symbols +, *, - or /, and the remaining two elements are themselves arithmetic expressions.

   Examples:

   (expr1 92)                              ; 92
   
   (expr1 '(+ 3 4))                        ; 7
   
   (expr1 '(* 2 (+ 1 3)))                  ; 8
   
   (expr1 '(+ (* (/ 6 2) 5) (- 100 97)))   ; 18
   

   Note: the functions expr1 and expr2 do not need to do any error checking, ie don't worry about the case where the arithmetic expression they're expecting really isn't one. Also note that all operators take two arguments. Including -. So you do not have to worry about an expression like (- 3). (You can get the intended effect with (- 0 3) or (* -1 3) anyway.)

   Note: you may not use eval in your definition of expr1 or expr2.

4. Define a function expr2 which takes two arguments: an ``arithmetic expression'' and an ``environment,'' and returns the result of evaluating the given arithmetic expression in the given environment.

   An ``arithmetic expression'' is here extended to also consider symbols (like x, y or blorf) to be arithmetic expressions.

   The ``environment'' is a mapping from symbols to numbers, represented as an association list.

   Examples:

   (expr2 92 '((a 1)(b 2)))                                ; 92
   
   (expr2 'a '((a 1)(b 2)))                                ; 1
   
   (expr2 '(+ b 3) '((a 1)(b 2)))                          ; 5
   
   (expr2 '(* b (+ a 3)) '((a 1)(b 2)))                    ; 8
   
   (expr2 '(+ (* (/ 6 blorf) (+ blorf (+ blorf 1))) (- c d))
          '((c 100) (blorf 2) (a 1) (d 97)))               ; 18
   

   Note: you can assume that all symbols appearing in the expression are listed in the environment.

5. Define simplify, which takes an arithmetic expression as defined above and returns a ``simplified'' arithmetic expression. You should try to do a good job of simplification, but at the very least any addition of 0, multiplication by 0 or 1, division by one, or subtraction of 0 should be simplified away.

   Examples:

   (simplify '(+ (* 1 (+ 0 (* (/ a a) (+ x 2)))) 10))     ; (+ x 12)
   

   (or some different but equivalent result.)

   Note: Don't try to get too fancy for this or the next problem. It is sufficient to do a rough job, so that in the output there is no arithmetic operation on two numbers, a symbol is not divided by itself, things are not added to zero, zero isn't subtracted from things, things aren't multiplied or divided by zero or one. Doing a better job than just these minimal requirements will get some extra credit, and more importantly the inner peace that only comes from a Zen programming experience.

6. Define sym+, sym-, sym* and sym/ which each take two simplified arithmetic expressions and return an arithmetic expression which is respectively the symbolic sum, difference, product, or quotient of the given arguments.

   Examples:

   (sym+ 'a 'b)                ; (+ a b)
   (sym+ 'a 'a)                ; (* 2 a)
   (sym+ 1 2)                  ; 3
   (sym+ 1 '(+ a 19))          ; (+ a 20)
   (sym/ 'c '(/ a b))          ; (/ (* c b) a)
   

   (or different but equivalent results.)

   Note: you probably want to define simplify in terms of these.

7. Define diff which takes two arguments: an arithmetic expression and a symbol, and returns the symbolic derivative of the expression with respect to the given variable.

   Examples:

   (diff 57 'x)                   ; 0
   (diff 'a 'x)                   ; 0
   (diff '(+ a b) 'x)             ; 0
   (diff 'x 'x)                   ; 1
   (diff '(* a (* x x)) 'x)       ; (* a (* 2 x))
   (diff '(/ x a) 'x)             ; (/ 1 a)
   (diff '(/ a x) 'x)             ; (* a (/ -1 (* x x)))
   (diff '(+ a (* x x)) 'x)       ; (* 2 x)
   (diff '(* (+ x 1) (+ x 2)) 'x) ; (+ (+ x 2) (+ x 1))
   

   (or different but equivalent results.)

8. Extra Credit: Make new versions of the functions in 4, 5, 6 and 7 that

   1. can handle expression in which the operators + and * take a variable number of operands (arguments).

   2. always return expressions in ``simplified rational expression'' form, in the sense that simplify always returns an SRE, and sym+ and friends return an SRE assuming that their arguments were SREs.

   An SRE is defined to be an expression that is either (a) an SRE polynomial, or (b) the quotient of two SRE polynomials. An SRE polynomial is an expression that is either a single term, or the sum of some terms. And a term is either a number, a variable, or the product of a number (optional) with one or more variables. Note that an SRE cannot contain the subtraction operator. Examples:

   ;;; These are some "terms".  (They are also valid albeit degenerate
   ;;; SREs and "SRE polynomials.")
   
   (* x x 13 y z x)
   
   24
   
   z
   
   (* -1 z)
   
   ;;; These are some "SRE polynomials" (They are also valid albeit
   ;;; degenerate SREs.)
   
   (+ (* x x 13 y z x) y 24 (* -2 z))
   
   (+ (* y y y) (* 6 y y) (* 4 y) 7)
   
   (* -1 z)
   
   92
   
   (+ 92 (* -1 z))    ; this is like (- 92 x) except that SREs have no -'s
   
   ;;; This is an SRE
   
   (/ (+ (* x x 13 y z x)
         y
         24
         (* -2 z))
      (+ (* y y y)
         (* 6 y y)
         (* 4 y)
         7))
   

The file should be legal scheme code, with comments indicating which fragment of code corresponds to which problem.