SICP

# SICP 1.3.4 Exercises

December 18, 2013 08:43

### 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^{4} 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 *n*th 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.