61A Homework 8

Due by 11:59pm on Tuesday, 11/12

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

Readings. Section 3.2 of Composing Programs.

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 hw8.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 (list 3 4) (cddr counts))
  (assert-equal 2 (cadr counts))
  (assert-equal 3 (caddr counts)))

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

(define (cadr s)

(define (caddr s)

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:


(<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. Using cond, 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)

Q3. Define the procedure gcd that uses the Euclidean algorithm to find the greatest common divisor of two positive integers:

(define (test-q3)
  (assert-equal 4 (gcd 12 8))
  (assert-equal 4 (gcd 12 16))
  (assert-equal 8 (gcd 16 8))
  (assert-equal 6 (gcd 24 42))
  (assert-equal 5 (gcd 5 5)))

(define (gcd m n)

Q4. Implement a procedure pow for raising the number b to the power of 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-q4)
  (assert-equal 1024 (pow 2 10))
  (assert-equal 1000 (pow 10 3))
  (assert-equal 243 (pow 3 5)))

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

(define (pow b n)

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)))

Q5. 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-q5)
  (assert-equal 1 (derive '(+ x 3) 'x)))

(define (derive-sum exp var)

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

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

(define (derive-product exp var)

Q7. Implement an abstract data type for exponentiation: a base raised to the power of an exponent. You can simplify the cases when exponent is 0 or 1, or when base is a number and exponent is an integer by returning numbers from the constructor make-exponentiation. In other cases, you can represent the exponentiation as a triple (^ base exponent):

(define (test-q7)
  (let ((x^2 (make-exponentiation '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 '(^ x 2) x^2)
    (assert-equal 'x (base x^2))
    (assert-equal 2  (exponent x^2))
    (assert-equal #t (exponentiation? x^2))
    (assert-equal #f (exponentiation? 1))
    (assert-equal #f (exponentiation? 'x))

; Exponentiations are represented as lists that start with ^.
(define (make-exponentiation base exponent)

(define (base exponentiation)

(define (exponent exponentiation)

(define (exponentiation? exp)

Q8. Implement derive-exponentiation, which uses the power rule to derive exponentiations:

(define (test-q8)
  (let ((x^2 (make-exponentiation 'x 2))
        (x^3 (make-exponentiation 'x 3)))
    (assert-equal '(* 2 x) (derive x^2 'x))
    (assert-equal '(* 3 (^ x 2)) (derive x^3 'x))
    (assert-equal '(+ (* 3 (^ x 2)) (* 2 x)) (derive (make-sum x^3 x^2) 'x))

(define (derive-exponentiation exp var)

When you are finished, all tests should pass (printing a long list of ok's). You can run an individual test by calling a test procedure interactively: