*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) '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.** 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) 'YourCodeHere)

**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) 'YourCodeHere)

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

**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) 'YourCodeHere)

**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) 'YourCodeHere)

**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) 'YourCodeHere) (define (base exponentiation) 'YourCodeHere) (define (exponent exponentiation) 'YourCodeHere) (define (exponentiation? exp) 'YourCodeHere)

**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) 'YourCodeHere)

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:

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