Problem Set Six, CS 257

Due at 10pm on Wed Mar 24, 1999
It is vain to do with more what can be done with fewer.
- William of Occam, 14th-century
The lyf so short, the craft so long to lerne.
--- Chaucer

5 points each:

  1. Define expand-and which takes an and special form and translates it to a form with the same semantics that uses other constructs. For instance (expand-and '(and a b c)) might return (if a (if b c #f) #f).

  2. Define expand-cond which takes a cond special form and translates it into an expression with the same semantics that uses simpler forms. Be sure to handle all the different kinds of clauses, and be sure that things are not evaluated more times than they should be. Eg (expand-cond '(cond (a b) (c => car) (else 'nada))) might return (if a b (let ((temp c)) (if temp (car temp) 'nada))).

  3. Define the higher-order function nintegrate which takes a one-dimensional numeric function, a lower bound, an upper bound, and a number of steps, and returns the numeric approximation of the integral of the given function by evaluating it at the given points in the given region. (The number of steps must be an integer and cannot be less than two.)

    Use the trapezoidal rule, which means the two points at the end get 1/2 the weight that the ones in the middle do.

    Eg (nintegrate exp 3.0 5.0 11) would calculate (exp 3.0), (exp 3.2), (exp 3.4), ..., (exp 4.8), (exp 5.0), and would add them all up (except only adding in half of (exp 3.0) and (exp 5.0) because they're at the ends), multiply by the step size (in this case 0.2) and return that result. To numerically integrate sin(x)/exp(x) between zero and 5, you could use (nintegrate (lambda (x) (/ (sin x) (exp x))) 0.0 5.0 100). To make ff the numeric indefinite integral of f, you could go

    (define ff (lambda (x) (nintegrate f 0.0 x 1000)))
    

    For a bit of extra credit, make a version nintegrate-s which uses Simpson's rule.

  4. Use your nintegrate, along with lambda, to easily define nintegrate2, a two-dimensional numeric integration function, which takes a numeric function of two variables, an x lower- and upper-bound, a number of steps in the x direction, a y lower- and upper-bound, and a number of steps in the y directions, and approximates the two-dimensional integral.

    Eg

    (nintegrate2 (lambda (x y) (* x (cos (+ x y))))
                 10.1 12.2 20
    	     1.0 10.0 30)
    
    would numerically calculate the integral of that function over the rectangular interval x=(10.1:12.2), y=(1.0:10.0), at the 20x30 array of points (ie x steps through 20 points, y steps through 30 points).

  5. Extra credit: how and why does this return what it does? Discuss the significance.
    ((lambda (f) (f f 100))
     (lambda (g n)
       (if (= n 0)
           1
           (* n (g g (- n 1))))))
    

Submission

Turn in this problem set by running ~cslab/bin/cs257-handin file.scm.
Barak Pearlmutter <bap@cs.unm.edu>