Due by 11:59pm on Thursday, 8/7
Readings: You might find the following references useful:
Submission: See the online submission instructions. We have provided the following starter file: hw12.scm
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)))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 (derive-sum exp var)
)
(define (test-derive-sum)
(assert-equal 1 (derive '(+ x 3) 'x)))
(test-derive-sum)Implement derive-product, which applies the product
rule to differentiate
products:
(define (derive-product exp var)
)
(define (test-derive-product)
(assert-equal 'y (derive '(* x y) 'x))
(assert-equal '(+ (* x y) (* y (+ x 3)))
(derive '(* (* x y) (+ x 3)) 'x)))
(test-derive-product)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. (You can use the built-in function expt in your implementation!) In
other cases, you can represent the exponentiation as a triple (^ base
exponent):
; Exponentiations are represented as lists that start with ^.
(define (make-exponentiation base exponent)
)
(define (base exponentiation)
)
(define (exponent exponentiation)
)
(define (exponentiation? exp)
)
(define (test-exponentiation)
(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))
))
(test-exponentiation)Implement derive-exponentiation, which uses the power
rule to derive
exponentiations:
(define (derive-exponentiation exp var)
)
(define (test-derive-exponentiation)
(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))
))
(test-derive-exponentiation)exp procedure. So, we write the following
recursive procedure:
(define (exp-recursive b n)
(if (= n 0)
1
(* b (exp-recursive b (- n 1)))))Try to evaluate
(exp-recursive 2 (exp-recursive 2 15))You will notice that it causes a segmentation fault in STk, meaning
that STk ran out of memory when trying to evaluate that value. To
fix this, we need to use tail recursion! Implement the exp
procedure using tail recursion:
(define (exp b n)
;; Computes b^n.
;; b is any number, n must be a non-negative integer.
)
(define (test-exp)
(assert-equal 8 (exp 2 3))
(assert-equal 1 (exp 9.137 0))
(assert-equal 1024 (exp 4 5))
(assert-equal 6.25 (exp 2.5 2))
;; A test that would break STk if this was not tail recursive.
;; The output is humongous, so we don't print out the entire output
;; Instead we just get the last two digits.
(assert-equal 56 (remainder (exp 2 (exp 2 15)) 100)))
(test-exp)We now notice that we can write a faster version of exp that
computes its answer much faster using the method of repeated
squaring:
(define (square x) (* x x))
(define (fast-exp-recursive b n)
(cond ((= n 0)
1)
((even? n)
(square (fast-exp-recursive b (/ n 2))))
(else
(* b (fast-exp-recursive b (- n 1))))))The previous exp procedure took a linear number of recursive calls,
because it always reduced n by 1. However, fast-exp halves the
value of n every two recursive calls at most, and so it takes a
logarithmic number of recursive calls. See SICP for more
details.
However, this new procedure is not tail recursive, and as a result can use up a lot of memory. In particular, the following will crash STk after a few seconds of computation:
(fast-exp-recursive 1 (- (fast-exp-recursive 2 20000) 1))Bonus question: Why did we subtract 1? In other words, why doesn't the following crash the interpreter?
(fast-exp-recursive 1 (fast-exp-recursive 2 20000))Back to the original question - write fast-exp using tail recursion
so that this no longer crashes. See SICP, Exercise 1.16, for a
hint.
(define (fast-exp b n)
;; Computes b^n tail recursively by the method of repeated squaring.
)
(define (test-fast-exp)
(assert-equal 8 (fast-exp 2 3))
(assert-equal 1 (fast-exp 9.137 0))
(assert-equal 1024 (fast-exp 4 5))
(assert-equal 6.25 (fast-exp 2.5 2))
;; Takes about a second or so if implemented with a
;; logarithmic number of steps
(assert-equal 36 (remainder (fast-exp 2 (fast-exp 2 20)) 100))
;; Takes about 10 seconds. Will crash if not tail recursive.
(assert-equal 1 (fast-exp 1 (- (fast-exp 2 20000) 1)))
)
(test-fast-exp)