61A Homework 10

Due by 11:59pm on Wednesday, 4/10

Submission. See the online submission instructions. We have provided a starter file for the questions below.

Readings. Section 3.5 of the online lecture notes.

To complete this homework, you will need to use the stk interpreter installed on the instructional machines. You can download stk for your home computer.

You can load the starter file by: stk -load hw10.scm.

Scheme does not have a built-in unit testing framework. To verify behavior, we will use the following assert-equal procedure. Conventionally, the desired value is v1 and the result to be checked is v2:

(define (assert-equal v1 v2)
  (if (equal? v1 v2)
    (print 'ok)
    (print (list v2 'does 'not 'equal v1))))

Q1. Define the procedures cadr and caddr, which return the second and third elements of a list, respectively:

(define (test-q1)
  (define counts (list 1 2 3 4))
  (assert-equal 2 (cadr counts))
  (assert-equal 3 (caddr counts)))

(define (cddr s)
  (cdr (cdr s)))

(define (cadr s)
  'YourCodeHere)

(define (caddr s)
  'YourCodeHere)

Conditional expressions. The cond special form is a general conditional expression, similar to a multi-clause conditional statement in Python. The general form of a conditional expression is:

(cond

(<p1> <e1>)

(<p2> <e2>)

...

(<pn> <en>)

(else <else-expression>))

consisting of the symbol cond followed by pairs of expressions (<p> <e>) called clauses. The first expression in each pair is a predicate: an expression whose value is interpreted as either true or false.

Conditional expressions are evaluated as follows. The predicate <p1> is evaluated first. If its value is false, then <p2> is evaluated. If <p2>'s value is also false, then <p3> is evaluated. This process continues until a predicate is found whose value is true, in which case the interpreter returns the value of the corresponding consequent expression <e> of the clause as the value of the conditional expression. If none of the <p>'s is found to be true, the interpreter returns the value of the else expression.

The word "predicate" is used for procedures that return true or false, as well as for expressions that evaluate to true or false.

Q2. Define a procedure sign that returns -1 for negative arguments, 0 for zero, and 1 for positive arguments:

(define (test-q2)
  (assert-equal -1 (sign -42))
  (assert-equal 0 (sign 0))
  (assert-equal 1 (sign 42)))

(define (sign x)
  'YourCodeHere)

Differentiation. The following problems develop a system for symbolic differentiation of algebraic expressions. The derive Scheme procedure takes an algebraic expression and a variable and returns the derivative of the expression with respect to the variable. Symbolic differentiation is of special historical significance in Lisp. It was one of the motivating examples behind the development of the language. Differentiating is a recursive process that applies different rules to different kinds of expressions:

; Derive returns the derivative of exp with respect to var.
(define (derive exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable? exp var) 1 0))
        ((sum? exp) (derive-sum exp var))
        ((product? exp) (derive-product exp var))
        ((exponentiation? exp) (derive-exponentiation exp var))
        (else 'Error)))

To implement the system, we will use the following abstract data types. Sums and products are lists, and they are simplified on construction:

; Variables are represented as symbols
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

; Numbers are compared with =
(define (=number? exp num)
  (and (number? exp) (= exp num)))

; Sums are represented as lists that start with +.
(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list '+ a1 a2))))
(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))

; Products are represented as lists that start with *.
(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))
(define (product? x)
  (and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))

(define (test-sum)
  (assert-equal '(+ a x) (make-sum 'a 'x))
  (assert-equal '(+ a (+ x 1)) (make-sum 'a (make-sum 'x 1)))
  (assert-equal 'x (make-sum 'x 0))
  (assert-equal 'x (make-sum 0 'x))
  (assert-equal 4 (make-sum 1 3)))

(define (test-product)
  (assert-equal '(* a x) (make-product 'a 'x))
  (assert-equal 0 (make-product 'x 0))
  (assert-equal 'x (make-product 1 'x))
  (assert-equal 6 (make-product 2 3)))

Q3. Implement derive-sum, a procedure that differentiates a sum by summing the derivatives of the addend and augend. Use the abstract data type for a sum:

(define (test-q3)
  (assert-equal 1 (derive '(+ x 3) 'x)))

(define (derive-sum exp var)
  'YourCodeHere)

Q4. Implement derive-product, which applies the product rule to differentiate products:

(define (test-q4)
  (assert-equal 'y (derive '(* x y) 'x))
  (assert-equal '(+ (* y (+ x 3)) (* x y))
                (derive '(* (* x y) (+ x 3)) 'x)))

(define (derive-product exp var)
  'YourCodeHere)

Q5. Implement a procedure pow for raising the number b to the power of a nonnegative integer n that runs in \(\Theta(\log n)\) time. Hint: Use the built-in predicates even? and odd? and the square procedure to implement the procedure using successive squaring, as we did in lecture:

(define (test-q5)
  (assert-equal 1024 (pow 2 10))
  (assert-equal 243 (pow 3 5)))

(define (square x) (* x x))

(define (pow b n)
  'YourCodeHere)

Q6. Implement an abstract data type for exponentiation: a base raised to the power of an exponent. Simplify the cases when exponent is 0 or 1, or when base is a number and exponent is an integer. Then, implement derive-exponentiation.

Hint: You do not have to handle the case where the exponent is not a number in derive-exponentiation; return 'unknown in that case. If the exponent is a number, then \(\frac{d}{dx} [expr]^n = n \cdot [expr]^{n-1} \cdot \frac{d}{dx} [expr]\) .

(define (test-q6)
  (let ((x^2 (make-exponentiation 'x 2))
        (x^3 (make-exponentiation 'x 3))
        (xy+x^2 (make-exponentiation (make-sum (make-product 'x 'y) 'x) 2)))
    (assert-equal 'x (make-exponentiation 'x 1))
    (assert-equal 1 (make-exponentiation 'x 0))
    (assert-equal 16 (make-exponentiation 2 4))
    (assert-equal (make-product 3 x^2) (derive x^3 'x))
    (assert-equal '(* 2 x) (derive x^2 'x))
    (assert-equal '(* (* 2 (+ (* x y) x)) (+ y 1)) (derive xy+x^2 'x))
    (assert-equal '(* (* 2 (+ (* x y) x)) x) (derive xy+x^2 'y))))

(define (make-exponentiation base exponent)
  'YourCodeHere)

(define (base exponentiation)
  'YourCodeHere)

(define (exponent exponentiation)
  'YourCodeHere)

(define (exponentiation? exp)
  'YourCodeHere)

(define (derive-exponentiation exp var)
  'YourCodeHere)

When you are finished, all tests should pass (printing a long list of ok's):

(test-q1)
(test-q2)
(test-q3)
(test-q4)
(test-q5)
(test-q6)