Ex 1.40

This is straightforward, and merely requires an understanding of what the Newton’s method solver requires. It needs the calculation of the function, or rather a procedure that calculates the value of a function. This means that the cubic procedure must return a procedure that takes one argument. A lambda expression that sums the terms of the cubic equation, with all coefficients included, is the answer.

Ex 1.41

Since the result of double is to be a procedure, that means we have to create one with a lambda expression. Applying the procedure twice is the body of the new procedure, and we act on the single argument which is both what the original procedure accepts and what the returned procedure from double accepts.

For the second question one can easily find the answer by testing with the interpreter, but is better understood by working through mentally first. In the innermost parentheses, the double double returns a procedure that applies double twice to one argument, or (double (double x)). Then the double causes that process to be doubled, which is the same as (double (double (double (double x)))). The argument inc is then passed to this procedure, and it will be doubled 2⁴ times, or 16 times. This is now a procedure equivalent to (inc (inc (inc ... (inc x)))... that increments the initial argument 16 times. Finally, that is given the argument 5, and returns 5 + 16 or 21.

Ex 1.42

Another easy application of procedures. We must return a procedure, so it starts with a lambda expression that will take the argument x. Then, since f and g are both procedures, we simply use g(x) as the argument to f, and that is our composed answer. It does not look any different from composed functions written in any conventional mathematical format.

Ex 1.43

The previous exercises provide some hints about the sort of expression we want to end up with and how to build it. In 1.41, it was a case of repeated application of double for 4 times. From 1.42 we know compose can be used to build expressions like that, since in compose the argument f and g can both be the same function. compose inc inc, for instance, would get us the same as saying (inc (inc x)), or two applications. Applying compose again to the result of that would yield the same as (inc (inc (inc x))), or three.

The last step is to get the correct number of repeats involved and make it generic. Applying compose repeatedly is accomplished by recursion. Each time through, the result is one more application of the procedure passed as the argument, until the proper number of repeated applications have been achieved. One more thing to note is that in the base case (n = 1), we can simply return the procedure f, since one ‘repeated’ application is identical to (f x).

Ex 1.44

Once again we want the returned value of our procedure to be a procedure. Inside the lambda expression is simply a bit of calculation. To get the average, we sum f(x – dx), f(x), and f(x + dx), and then divide by three. In this case I used the value dx which was defined earlier for the Newton’s Method solver. This is a possibly questionable practice, since once it’s hard-coded into smooth we can’t change it without changing both smooth and newtons-method. On the other hand, there are some points in favor of using this as a global ‘smallest value’, in that we’ll know what’s in effect for all functions that use it. In this case, it was more a matter of convenience in that it was already defined.

Making a function n-fold smooth is very easy to do thanks to the repeated procedure. This example shows how powerful it can be to allow the manipulation of procedures with other procedures. Doing anything n times is a simple matter of using repeated on the procedure.

Ex 1.45

The tools for easily creating a procedure to find roots are in place, and this allows for easy experimentation. The fixed-point can be used with an expression that finds the root, and average-damp can have its value changed in order to determine one that converges. Once we know k, our desired damping factor, we can produce an nth root of using the fixed point of (x / y ^{n – 1}).

I admit I don’t have a complete grasp of the underlying mathematics here in order to come up with the values that work. However, by simply increasing the value of n for the root and adjusting the average damping factor, it’s possible to find a pattern. Every time that n increases past the next power of 2, another level of damping is required. This implies that when n is less than or equal to 2 ^k, the damping will be sufficient. The value of k can be computed from n using the logarithm (base 2). Since most flavors of Scheme only define the natural logarithm, we use that to calculate our k. The formula is k = (ln n / ln 2).

Putting it all together, we use a let statement to set the value for k, and then use a fixed-point solver on the damped function. The damped function is created using repeated to damp k times, and since repeated requires a procedure as argument we have to create it using a lambda expression.

There is what can be considered a possible bug in my procedure, in that 0 cannot be used as a value for n. That could be handled by treating 0 as a special case (it only fails because the calculation of k requires positive n). Rational (non-integer) roots are an additional special case, but are effectively excluded from the problem by the use of n as the argument name, which implies an integer.

Ex 1.46

The final exercise in this chapter is a recognition of the abstraction that can be applied to the problems we’ve been solving in the last few sections. Using procedures (and specifically math functions implemented as procedures) as arguments is what allows this abstraction to work. Once the abstraction is realized, it’s not hard to implement: iterative-improve can use good-enough? in the test of an if statement, and if it fails, it simply iterates on the next generated value, using the last one.

While in similar problems we were able to simply construct a lambda expression and have it be our returned value, in this case an internal define is required. Take a look at rec and named-lambda for other ways to do it This is because we need to recurse, and in order to do that we must have some way of referring to the procedure. A lambda expression has no name, and so define is used instead.

Solutions 1.3.4