Chapter 1.3 (Formulating Abstractions with Higher Order Procedures)
Procedures are in fact abstractions that define compound operations on numbers, INDEPENDENT of the particular numbers. If we could only create abstractions whose parameters are numbers, we would still be severely limited. Nothing should stop us to take the abstraction to a next level, and see that we use the same programming pattern, not with similar numbers, but with similar procedures.
To create such an abstraction, we need to be able to construct procedures that can accept procedures as arguments and return procedures as values. Procedures that can do this are called higher order procedures.
1.3.1 Procedures as arguments
Consider the following 3 procedures:
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))
(define (sum-cubes a b)
if (> a b)
0
(+ (cube a) (sum-cubes (+ a 1) b)))
(define (pi-sum a b)
if (> a b)
0
(+ (/ 1.0 (* (a (+ a 2)))
(pi-sum (+ a 4) b))))
These three procedures clearly share a common pattern
(define (<name> a b)
if (> a b)
0
(+ (<term> a) (<name> (<next> a) b))))
The presence of such a pattern is a strong indication that there is a useful abstraction underneath. In this case that is the concept of summation. Mathematics long ago already abstracted this by introducting sigma notation: $\sum$. or more formally:
$$ \sum\limits_{n=a}^{b} f(n) = f(a) + ... f(b) $$But with our newfound wisdom, we can create a procedure to capture this as well, by building a procedure to sum the range between any two numbers, with procedures as input that tell us how to sum and how to get the next index:
(define (sum term a next b)
(if (> a b)
0
(+ (term a) (sum term (next a) next b))))
This would make it easier for us to define multiple procedures that in essence do some kind of summation over a give sequence:
(define (identity x) x)
(define (inc x) (+ x 1))
(define (sum-integers a b)
(sum identity a inc b))
(define (sum-cubes a b)
(sum cube a inc b))
(define (pi-sum a b)
(define (pi-term x)
(/ 1.0 (* x (+ x 2))))
(define (pi-next x)
(+ x 4))
(sum pi-term a pi-next b))
And so on for other summation functions.
And ofcourse, we don’t have to stop there. Having defined sum, we can use it as a building block for more complicated concepts, for example like calculating the integral of a given function between a and b:
$\int\limits_{a}^{b} f=[f(a + \frac{dx}{2}) + f(a + dx + \frac{dx}{2})+ …] dx$
(define (integral f a b dx)
(define (add-dx x)
(+ x dx))
(* (sum f (+ a (/ dx 2.0)) add-dx b)
dx))
Exercise 1.29
Exercise 1.30 The sum procedure above generates linear recursion. Rewrite it so it is performed iteratively.
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ result (term a)))
(iter a 0)))
Exercise 1.31 The sum procedure is the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. a. Write an analogous procedure called product
(define (product term a next b))
(if (> a b)
1
(* (term a) product term (next a) next b))
Show how to define factorial
(define (fact a b)
(define (identity x) (x))
(define (fact-next x) (+ x 1))
(product identity a fact-next b))
b. Rewrite product to generate an iterative process
(define (product term a next b)
(define (prod-iter a result)
(if (> a b)
result
(prod-iter (next a) (* result (term a)))))
(prod-iter a 1))
Exercise 1.32 a. Show that sum and product are both special cases of a more generic accumulate procedure that has the following signature
(accumulate combiner null-value term a next b)
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a) accumulate combiner null-value term (next a) next b)))
Show how sum and product can both be defined as simple calls to accumulate
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
b. Write the same function that uses an iterative process
(define (acc-iter combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner result (term a)))))
(iter a null-value))
Exercise 1.33 You can obtain a more generic version of accumulate by introducing a filter. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument. Write it
(define (filtered-accumulate combiner null-value term a next b predicate)
(if (> a b)
null value
(cond ((predicate a)(combiner (term a) filtered-accumulate combiner null-value term (next a) next b)
(else (filtered-accumulate combiner null-value term (next a) next b predicate))))))
a. The sum-of-squares of prime numbers in the interval a to b. Assume prime? already exists:
(filtered-accumulate + 0 square a inc b prime?)
b. The product of all positive integers less then n
(filtered-accumulate * 1 identity 1 inc (- n 1) rel-prime?)
1.3.2 Construction procedures as lambda
Up until now we have been defining helper procedures either inside the procedure where they were being used or (even more awkward sometimes) otuside those procedures. But if we only use those procedures once, wouldn’t it be nice to just define them, without being burdened by having to name them.
We can do this by introducing the special lambda form:
(lambda (x) (+ x 4))
and
(lambda (x) (/ 1.0 (* x (+ x 2))))
Then our pi-sum procedure would go from:
(define (pi-sum a b)
(define (pi-term x)
(/ 1.0 (* x (+ x 2))))
(define (pi-next x)
(+ x 4))
(sum pi-term a pi-next b))
to:
(define (pi-sum a b)
(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
a
(lambda (x) (+ x 4))
b))
In general, lambda is used to create procedures in the same way as define, we just don’t specify a name:
(lambda (<formal parameters>) <body>)
The fun thing is, (define) uses lambda, we just use some syntactic sugar so we don’t have to write lambda every time.
(define (plus4 x) (+ x 4))
is equivalent to:
(define plus4 (lambda (x) (+ x 4)))
And, like any expression that has a procedure as its value, a lambda epxression can be used as an operator such as
((lambda (x y z) (+ x y (square z))) 1 2 3)
instead of
(define (f x y z) (+ x y z))
(f 1 2 3)
Another use of lambda is to create local variables. We often need variables in our procedures other than those that have been bound as formal parameters. For example, suppose we wish to compute the function:
$f(x, y) = x(1 + xy)^2 + y(1 - y) + (1 + xy)(1 - y)$
Which we could also expres as : $a = 1 + xy$, $b = 1 - y$, $f(x, y) = xa^2 + yb + ab$
If we opt to not use local variables, we could instead create a helper function:
(define (f x y)
(define f-helper a b)
(+ (* x (square a))
(* y b)
(* a b)))
(f-helper (+ 1 (* x y))
(- 1 y)))
We could also ofcourse use a lambda function instead like we just learned:
(define (f x y)
(lambda (a b)
(+ (* x (square a))
(* y b)
(* a b)))
(+ 1 (* x y))
(- 1 y)))
The body then becomes a single call to the lambda procedure. We could further improve this (mainly the readability) by binding a and b using let:
(define (f x y)
(let ((a (+ 1 (* x y)))
(b (- 1 y)))
(+ (* x (square a))
(* y b)
(* a b))))
The general form of a let expression is :
(let ((<var1> <exp1>)
(<var2> <exp2>)
...
(<varn> <expn>))
<body>)
In essence an let expression is syntactic sugar for the underlying lambda application.
One more interesting thing to discuss with regards to let expressions are their scope:
The scope of a variable specified by a let expression is the body of the let. This implies that:
- Let allows one to bind variables as locally as possible to where they are used. For example, if the value of x is 5, the value of the expression:
is 38. The x inside the let body is 3, so the value of the let expression is 33. This is then substituted in the outer scope where x = 5:(+ (let ((x 3)) (+ x (* x 10))) x)(+ 33 x)which results in 38.- The variable’s values are computed outside the let. This matters when the expressions that provide the values for the local variables depend upon variables having the same names as the local variables themselves. For example, if the value of x is 2 outside the let, the expression:
(let ((x 3) (y (+ x 2))) (* x y))will have the value 12, and not 15. This is because inside the body of the let, x will be 3, but y will be 4 (and not 5) as it depends on the outer x instead of the inner x.
Ofcourse (returning to the beginning of this sub-chapter) could have defined f as follows:
(define (f x y)
(define a (+ 1 (* x y)))
(define b (- 1 u))
(+ (* x (square a))
(* y b)
(* x b)))
We prefer however to use let in situations like this and only use internal define for internal procedures.
Exercise 1.34 Suppose we define the procedure:
(define (f g) (g 2))
What happens if we ask the interpreter to evaluate (f f).
It errors, since inside the procedure f is bound to g and it then tries to call (f 2) which cant, since 2 is a number and not a function.
1.3.3 Procedures as General Methods
In this section we discuss two more elaborate examples of procedures used to express general methods of computation, independent of the particular functions involved. The examples will be general methods for finding zero’s and fixed points of functions.
Finding roots of equations by the half-interval method This is a simple but powerful technique for finding roots fo an equation $f(x) = 0$, where $f$ is a continuous function. The idea is that, if we are given points $a$ and $b$ such that $f(a) < 0 < f(b)$, then $f$ must have atleast one zero between $a$ and $b$. To locate a zero, let $x$ be the average of $a$ and $b$ and compute $f(x)$. if $f(x) > 0$, then the zero must be between $a$ and $x$. Otherwise, if $f(x) < 0$ than the zero must be between $x$ and $b$. If $f(x) = 0$, then we have the root. We can keep continuing in this way, getting a smaller and smaller interval, until we reach a point where the interval is small enough.
Since we reduce the uncertainty by half with every step, this method has a complexity of $\theta(log(n))$. This is the procedure that does this:
(define (search f neg-point pos-point)
(let ((midpoint) (average neg-point pos-point)))
(if (close-enough? neg-point pos-point)
midpoint
(let ((test-value (f midpoint)))
(cond ((positive? test-value)
(search f neg-point midpoint))
((negative? test-value)
(search f midpoint pos-point))
(else midpoint)))))
The close-enough? function is very similar to what we previously had:
(define (close-enough? x y)
(< (abs (- x y)) 0.0001))
So, this works, but can be a bit awkward. If we give search two points that do not have the required sign we get a wrong answer. So lets wrap search into something that checks the inputs and calls search correctly.
(define (half-interval-method f a b)
(let ((a-value (f a))
((b-value (f b)))
(cond ((and (negative? a-value) (positive? b-value))
(search f a b))
((and (negative? b-value) (positive? a-value))
(search f b a))
(else (error "values are borked" a b)))))
This way we ensure search gets used correctly without building all that into search itself. And it is also very generic, since it accepts any function that takes 1 input.
Finding Fixed Points of functions A number $x$ is called a fixed point of a function $f$ if $f(x) = x$. For some functions, we can locate a fixed points by repeatedly applying $f$: $f(x), f(f(x)), f(f(f(x))), …$ until the value does not change very much. Lets implement that:
(define tolerance 0.000001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2))
tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
We can then use this as follows:
(fixed-point (lambda (y) (+ (sin y) (cos y))) 1.0)
or with a previously named function:
(fixed-point cos 1.0)
Exercise 1.35 Show that the golden ratio $\phi$ is a fixed point of the transformation $x |-> 1 + 1 /x$
(define golden-ratio (/ (+ 1 (sqrt 5)) 2))
// 1.618
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
// 1.618
Exercise 1.36 Rewrite fixed-point so it prints the sequence it generates
(define tolerance 0.000001)
(define (fixed-point-v f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2))
tolerance))
(define (try guess)
(let ((next (f guess)))
(display next)
(newline)
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
Then find a solution to $x^x = 1000$ by finding a fixed point of
$f(x) = log(1000) / log(x)$
(define (f x) (/ (log 1000) (log x)))
(fixed-point-v f 4.0)
$4 = 4.555535991352336
Procedures as Returned Values
This for me is the most difficult to wrap my head around. So the above were good examples of the ability to pass procedures as arguments to procedures. This significantly enhances the expressive power of a language. But we can create even more expressive power by creating procedures whose returned values are themselves procedures.
We can illustrate this idea by looking again at the fixed-point example where we used average-damp to make the approximates converge. This idea can be expressed as follows:
(define (average-damp f)
(lambda (x) (average x (f x))))
So average-damp is a procedure that takes as its argument a procedure f and returns as its value a procedure that, when applied to a number x, produces the average of $x$ and $f(x)$. So it can be used like this:
((average-damp square) 10)
or
(define (f x) (average-damp square))
(f 10)
Applying this to get the square root, we mentioned that a square root procedure is a special case of Newton’s Method if $g(x)$ is differentiable, then a solution of the equation $g(x) = 0$ is a fixed point of the function $f(x)$ where $f(x) = x - \frac{g(x)}{Dg(x)}$
Allright, in more general terms, Newton’s method is an iterative technique for finding roots ($g(x) = 0$). This is done by iterating using the following formula: $f(x) = x - \frac{g(x)}{g’(x)}$.
The square root procedure is a special case where $g(x) = x^2 - S$. As an example we try to find the Square root of $S = 9$. $g(x) = x^2 - 9 = 0$ $g’(x) = 2x$ $x = x - \frac{x^2 - 9}{2x}$
Start with an initial guess of 4: $x_1 = 4 - \frac{4^2 - 9}{2 * 4}$ = $4 - \frac{5}{8}$ = $3\frac{3}{8}$ = $3.375$ $x_2 = 3.375 - \frac{3.375^2 - 9}{2 * 3.375}$ …. $x_n = 3.000$
So in the example we could easily calculate the derivative. But in order to actually implement Newton’s Method as a procedure, we must express the idea of a derivative. Do note that “derivative” transforms a function into another function. For instance, the derivative of the function $f(x) = x^3$ is $f’(x) = 3x^2$. In general, if $f$ is a function and $dx$ is a small number, then $f’(x)$ is the function whose value at any given $x$ is given by: $f’(x) = \frac{f(x + dx) - f(x)}{dx}$
Example: $f(x) = x^3$ $f’(x) = \lim_{dx -> 0} \frac{(x + dx)^3 - x^3}{dx}$
We expand $(x+dx)^3$
$(x + dx)^3 = x^3 + 3x^2(dx) + 3x(dx)^2 + (dx)^3$ $f’(x) = \lim_{dx -> 0} \frac{x^3 + 3x^2(dx) + 3x(dx)^2 + (dx)^3 - x^3}{dx}$
We subtract $x^3$ and divide by $dx$ =
$f’(x) = \lim_{dx -> 0} 3x^2 + 3x(dx) + (dx)^2$
Take the limit (dx = 0)
$f’(x) = 3x^2$
Thus we can implement the idea of the derivative (taking dx to be 0.00000001) as the procedure:
(define dx 0.000001)
(define (deriv f)
(lambda (x) (/
(- (f (+ x dx)) (f x))
dx)))
Now that we have the derivative, we can express Newton’s Method as a fixed point process:
(define (newton f)
(lambda(x) (- x (/ (f x) ((deriv f) x)))))
Abstractions and first-class procedures In general, programming languages impose restrictions on the ways in which elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the rights and privileges of first-class elements are:
- They may be named by variables
- They may be passed as arguments to procedures
- They may be returned as the results of procedures
- They may be included in data structures.
Procedures in Lisp are all of the above, which makes implementation tricky, but results in massive power gains.