Homework Seven

Higher Order Functions

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

1. 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 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 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 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. 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 sqrt-plus-one (compose add1 sqrt))
        (sqrt-plus-one 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?)

3. Data hiding is an important aspect of object-oriented programming. For this problem, your task is by write two functions, set-passwd and check-passwd. The function set-passwd takes as input a symbol passwd and returns a password object. The function check-passwd takes a symbol passwd and a password object and returns true if and only if passwd agrees with the password encapsulated in the object.

   Hint: The password object should be a function created by set-passwd. You may use local if you wish (although it is not necessary). Your representation should be secure in the sense that there is no way that Scheme code can extract a password from a password object (beyond exhaustively testing all possible passwords).