*Due by 5pm on Friday, 11/2*

**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 hw9.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 '(+ (* x y) (* y (+ x 3))) (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 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`:

(define (test-q6) (let ((x^2 (make-exponentiation 'x 2)) (x^3 (make-exponentiation 'x 3))) (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)))) (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)