We have seen that procedures are, in effect, abstractions that describe compound operations on numbers independent of the particular numbers.
One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly.
- Procedures operations on numbers are powerful, but we can go further.
- To abstract more general programming patterns, we need to write procedures that take other procedures as arguments and return new procedures.
- These are called higher-order procedures.
Procedures as Arguments#
Procedures that compute a sum all look the same:
(define (name a b)
(if (> a b)
0
(+ (term a)
(name (next a) b))))This is a useful abstraction, just as sigma notation is useful in math because the summation of a series is so common.
The power of sigma notation is that it allows mathematicians to deal with the concept of summation itself rather than only with particular sums.
Exercises: 1.29, 1.30, 1.31, 1.32, 1.33
Constructing Procedures Using Lambda#
#!scheme lambda creates anonymous procedures. They are just like the procedures create by #!scheme define, but without a name: #!scheme (lambda (formal-parameters) body).
A lambda expression can be used as the operand in a combination. It will be evaluated to a procedure and applied to arguments (the evaluated operands). The name comes from the $\lambda$-calculus, a formal system invented by Alonzo Church.
Using let to create local variables#
We often need local variables in addition to formal parameters. We can do this with a lambda expression that takes the local variables as arguments, but this is so common that there is a special form #! scheme let to make it easier.
The general form of a let-expression is:
(let ((var1 exp1)
(var2 exp2)
...
(varn expn))
body)This is just syntactic sugar for:
((lambda (var1 var2 ... varn)
body)
exp1
exp2
...
expn)- The scope of a variable in a let-expression is the body. This allows variables to be bound as locally as possible.
- The variables in the let-expression are parallel and independent. They cannot refer to each other, and their order does not matter.
- You can use let-expressions instead of internal definitions.
Exercises: 1.34
Procedures as General Methods#
So far, we have seen:
- Compound procedures that abstract patterns of numerical operators (mathematical functions), independent of the particular numbers.
- Higher-order procedures that express a more powerful kind of abstraction, independent of the procedures involved.
Now we will take it a bit further.
Finding roots of equations by half-interval method#
- The half-interval method: a simple but powerful technique for solving $f(x) = 0$
- Given $f(a) < 0 < f(b)$, there must be at least one zero between $a$ and $b$.
- To narrow it down, we let $x$ be the average of $a$ and $b$, and then replace either the left bound or the right bound with it.
(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))))))
(define (close-enough? x y)
(< (abs (- x y)) 0.001))
(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 not of opposite sign" a b)))))We can use #!scheme half-interval-method to approximate $\pi$ as a root of $\sin x = 0$:
(half-interval-method sin 2.0 4.0)
-> 3.14111328125Finding fixed points of functions#
- A number $x$ is fixed point of a function if $f(x) = x$.
- In some cases, repeatedly applying the function to an arbitrary initial guess will converge on the fixed point.
- The procedure we made earlier for finding square roots is actually a special case of the fixed point procedure.
(define tolerance 0.00001)
(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 use #!scheme fixed-point to approximate the fixed point of the cosine function:
(fixed-point cos 1.0)
-> 0.73908222985224023Exercises: 1.35, 1.36, 1.37, 1.38, 1.39
Procedures as Returned Values#
Passing procedures as arguments gives us expressive power. Returning procedures from functions gives us even more. For example, we can write a procedure that creates a new procedure with average damping:
(define (average-damp f)
(lambda (x) (average x (f x))))If we use #!scheme average-damp on #!scheme square, we get a procedure that calculates the sum of the numbers from 1 to $n$:
((average-damp square) 10)
-> 55
(+ 1 2 3 4 5 6 7 8 9 10)
-> 55In general, there are many ways to formulate a process as a procedure. Experienced programmers know how to choose procedural formulations that are particularly perspicuous, and where useful elements of the process are exposed as separate entities that can be reused in other applications.
Newton’s method#
The square-root procedure we wrote earlier was a special case of Newton’s method. Given a function $f(x)$, the solution to $f(x) = 0$ is given by the fixed point of
[ x \mapsto x - \frac{f(x)}{f’(x)}. ]
Newton’s method converges very quickly—much faster than the half-interval method in favorable cases. We need a procedure to transform a function into its derivative (a new procedure). We can use a small $dx$ for this:
[ f’(x) = \frac{f(x+dx) - f(x)}{dx}. ]
This translates to the following procedure;
(define (deriv f)
(lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))Now we can do things like this:
(define (cube x) (* x x x))
(define dx 0.00001)
((deriv cube) 5)
-> 75.00014999664018Abstractions and first-class procedures#
- Compound procedures let us express general method of computing as explicit elements in our programming language.
- Higher-order procedures let us manipulate methods to create further abstractions.
- We should always be on the lookout for underlying abstractions that can be brought out and generalized. But this doesn’t mean we should always program in the most abstract form possible; there is a level appropriate to each task.
- Elements with the fewest restrictions are first-class:
- They may be named by variables.
- They may be passed as arguments to procedures.
- They maybe returned as the results of procedures.
- They may be included in data structures.
- In Lisp, procedures have first-class status. This gives us an enormous gain in expressive power.