Homework Seven

Higher Order Functions

Comp210

Due: 97.Oct.28 (Wed.) in class

N.B. The postscript version of this homework contains more elegant formatting than is possible with html; I suggest you print the .ps version, and refer to this .html version as second resort.

As usual, you should include contracts, test cases, etc.

  1. (4pts) Given a non-negative function f defined on the closed interval [a,b] of real numbers, the integral of f from a to b is defined as the area enclosed between the curves f (x), the x-axis, and the vertical lines passing through a and b.

    Given the function f, one way to compute an approximate value for the integral of f from a to b is to:

    1. Subdivide [a,b] into many small sub-intervals [xi ,xi+1] for i = 0, 1, ..., n-1, where x0 = a, xn = b; and
    2. Approximate the area of each subinterval [xi ,xi+1] by the area of the trapezoid with the four corners (vertices) (xi ,0), (xi+1 ,0), (xi+1 , f (xi+1)), (xi ,f (xi)).
    Then the approximate value for the entire integral is the sum of the areas of the trapezoids for the intervals [x0 ,x1], ..., [xn-1 ,xn]. To compute the area A of the trapezoid with corners (xi ,0), (xi+1 ,0), (xi+1 , f (xi+1)), (xi ,f (xi)), multiply the base times the average height: A = (xi+1 - xi) * (f (xi+1) + f (xi))/2 .

    The choice of sub-intervals has a significant effect on the accuracy of the approximation. The simplest choice would be to subdivide [a,b] into n equal sub-intervals. Unfortunately, this approach requires a large number of sub-intervals for parts of the function that have sharp peaks and valleys, which is wasteful for the parts of the function that are smooth. Plus, it's not clear how large ``large'' should be, for different functions.

    For this homework, we will use a better method: subdivide [a,b] into intervals in an adaptive manner until the difference between trapezoid area for the interval [xi ,xi+1] and the sum of the trapezoid areas for [xi ,xmid] and [xmid , xi+1] -- where xmid is the midpoint of [xi ,xi+1] -- is less than (xi+1 - xi)*epsilon. The constant epsilon is called the ``unit error bound''; you can see that the overall error of the final answer will hopefully1 not be larger than epsilon(b-a).

    Your assignment is to to write a Scheme function integrate that takes four parameters:

    The result of (integrate f a b epsilon) is the approximate area under the integral according to the adaptive quadrature method described above.

  2. (3pts) Returning functions. The symbols alpha, beta, gamma are type-variables: they stand for any desired type of value (number, symbol, boolean, etc.). As always, show tests which make you confident of correctness.
    1. Write the function compose, which takes two functions f: beta --> gamma and g: alpha --> beta, and returns a function h: alpha --> gamma, where h(x) = f(g(x)). For example,
        (define second (compose first rest))
        (second (list 2 3 4 5))
      = 3
      
        ((compose add1 sqrt) 4)
      = 3
      
    2. Write the function iterate, which takes function f: alpha --> alpha and a natural number n, and returns a function which applies f to its input n times repeatedly. (This is sometimes denoted f(n).) (To consider: What is a function which takes an input and applies f zero times?) Hint: use the template for natural numbers.

  3. (3pts) Data hiding is an important aspect of structured programming. For this problem, your task is to write two functions, create-lock and check-lock. The function create-lock takes as input a symbol passwd and returns a ``lock'', whatever that is. The function check-lock takes a symbol key and a lock, and returns #t if and only if key agrees with the password used to create the lock. Example:
    (define my-passwd (create-lock 'secret-handshake))
     
    (check-lock my-passwd 'is-this-it?)       = #f
    (check-lock my-passwd 'secret-handshake)  = #t
    
    my-passwd
    ;; No interesting information should be printed in drscheme!
    
    Note that using a symbol for the lock would not be secure at all: evaluating the placeholder my-passwd above would reveal the symbol. Your representation should be secure in the sense that if you didn't see my call to create-lock, there is nothing you could type at my drscheme window to get check-lock to answer #t, short of systematically trying all passwords (or making a lucky guess). So what type of Scheme value might a lock be? Well, this is the homework about functions which accept/create/return other functions....

    In writing create-lock, you may use local if you wish, though it is not necessary nor advised.


1 Note that the error bound is not guaranteed, since we are comparing the differences between successive approximations rather the differences between approximations and exact answers. Can you concoct a function where the actual error is greater than the error bound? [back]