Homework Seven

Higher Order Functions

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 [x_i ,x_i+1] for i = 0, 1, ..., n-1, where x₀ = a, x_n = b; and
   2. Approximate the area of each subinterval [x_i ,x_i+1] by the area of the trapezoid with the four corners (vertices) (x_i ,0), (x_i+1 ,0), (x_i+1 , f (x_i+1)), (x_i ,f (x_i)).
   Then the approximate value for the entire integral is the sum of the areas of the trapezoids for the intervals [x₀ ,x₁], ..., [x_n-1 ,x_n]. To compute the area A of the trapezoid with corners (x_i ,0), (x_i+1 ,0), (x_i+1 , f (x_i+1)), (x_i ,f (x_i)), multiply the base times the average height: A = (x_i+1 - x_i) * (f (x_i+1) + f (x_i))/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 [x_i ,x_i+1] and the sum of the trapezoid areas for [x_i ,x_mid] and [x_mid , x_i+1] -- where x_mid is the midpoint of [x_i ,x_i+1] -- is less than (x_i+1 - x_i)*epsilon. The constant epsilon is called the ``unit error bound''; you can see that the overall error of the final answer will hopefully¹ not be larger than epsilon(b-a).

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

   • f: the mathematical function to be integrated;
   • a: the left endpoint of the integration interval [a,b],
   • b: the right endpoint of the integration interval [a,b],
   • epsilon: the approximate unit error bound for the computed result.
   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⁽ⁿ⁾.) (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.