Consider the following three procedures. functions. The first computes the sum of the integers from a through b:
Original | JavaScript |
(define (sum-integers a b) (if (> a b) 0 (+ a (sum-integers (+ a 1) b)))) | function sum_integers(a, b) { return a > b ? 0 : a + sum_integers(a + 1, b); } |
Original | JavaScript |
(define (sum-cubes a b) (if (> a b) 0 (+ (cube a) (sum-cubes (+ a 1) b)))) | function sum_cubes(a, b) { return a > b ? 0 : cube(a) + sum_cubes(a + 1, b); } |
Original | JavaScript |
(define (pi-sum a b) (if (> a b) 0 (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b)))) | function pi_sum(a, b) { return a > b ? 0 : 1 / (a * (a + 2)) + pi_sum(a + 4, b); } |
These three procedures functions clearly share a common underlying pattern. They are for the most part identical, differing only in the name of the procedure, function, the function of a used to compute the term to be added, and the function that provides the next value of a. We could generate each of the procedures functions by filling in slots in the same template:
Original | JavaScript |
(define ($\langle name \rangle$ a b) (if (> a b) 0 (+ ($\langle term \rangle$ a) ($\langle name \rangle$ ($\langle next \rangle$ a) b)))) | function $name$(a, b) { return a > b ? 0 : $term$(a) + $name$($next$(a), b); } |
The presence of such a common pattern is strong evidence that there is a
useful
abstraction waiting to be brought to the surface. Indeed,
mathematicians long ago identified the abstraction of
summation of a series and invented sigma
notation,
for example
\[\begin{array}{lll}
\displaystyle\sum_{n=a}^{b}\ f(n)&=&f(a)+\cdots+f(b)
\end{array}\]
to express this concept. The power of sigma notation is that it allows
mathematicians to deal with the concept of summation itself rather than only
with particular sums—for example, to formulate general results about
sums that are independent of the particular series being summed.
Similarly, as program designers, we would like our language to be powerful
enough so that we can write a
procedure
function
that expresses the concept of summation itself rather than only
procedures
functions
that compute particular sums. We can do so readily in our
procedural
functional
language by taking the common template shown above and transforming the
slots
into
formal parameters:
parameters:
Original | JavaScript |
(define (sum term a next b) (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) | function sum(term, a, next, b) { return a > b ? 0 : term(a) + sum(term, next(a), next, b); } |
Original | JavaScript |
(define (inc n) (+ n 1)) (define (sum-cubes a b) (sum cube a inc b)) | function inc(n) { return n + 1; } function sum_cubes(a, b) { return sum(cube, a, inc, b); } |
Original | JavaScript |
(sum-cubes 1 10) 3025 | sum_cubes(1, 10); 3025 |
Original | JavaScript |
(define (identity x) x) | function identity(x) { return x; } |
Original | JavaScript |
(define (sum-integers a b) (sum identity a inc b)) | function sum_integers(a, b) { return sum(identity, a, inc, b); } |
Original | JavaScript |
(sum-integers 1 10) 55 | sum_integers(1, 10); 55 |
Original | JavaScript |
(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)) | function pi_sum(a, b) { function pi_term(x) { return 1 / (x * (x + 2)); } function pi_next(x) { return x + 4; } return sum(pi_term, a, pi_next, b); } |
Original | JavaScript |
(* 8 (pi-sum 1 1000)) 3.139592655589783 | 8 * pi_sum(1, 1000); 3.139592655589783 |
Once we have sum, we can use it as a building block in formulating further concepts. For instance, the definite integral of a function $f$ between the limits $a$ and $b$ can be approximated numerically using the formula \[ \begin{array}{lll} \displaystyle\int_{a}^{b}f & = & \left[\,f\!\left( a+\dfrac{dx}{2} \right)\,+\,f\!\left(a+dx+\dfrac{dx}{2} \right)\,+\,f\!\left( a+2dx+\dfrac{dx}{2}\right)\,+\,\cdots \right] dx \end{array} \] for small values of $dx$. We can express this directly as a procedure: function:
Original | JavaScript |
(define (integral f a b dx) (define (add-dx x) (+ x dx)) (* (sum f (+ a (/ dx 2)) add-dx b) dx)) | function integral(f, a, b, dx) { function add_dx(x) { return x + dx; } return sum(f, a + dx / 2, add_dx, b) * dx; } |
Original | JavaScript |
(integral cube 0 1 0.01) 0.24998750000000042 | integral(cube, 0, 1, 0.01); 0.24998750000000042 |
Original | JavaScript |
(integral cube 0 1 0.001) | integral(cube, 0, 1, 0.001); 0.249999875000001 |
Original | JavaScript |
function inc(k) { return k + 1; } function simpsons_rule_integral(f, a, b, n) { function helper(h) { function y(k) { return f((k * h) + a); } function term(k) { return k === 0 || k === n ? y(k) : k % 2 === 0 ? 2 * y(k) : 4 * y(k); } return sum(term, 0, inc, n) * (h / 3); } return helper((b - a) / n); } |
Original | JavaScript |
(define (sum term a next b) (define (iter a result) (if ?? ?? (iter ?? ??))) (iter ?? ??)) | function sum(term, a, next, b) { function iter(a, result) { return $\langle{}$??$\rangle$ ? $\langle{}$??$\rangle$ : iter($\langle{}$??$\rangle$, $\langle{}$??$\rangle$); } return iter($\langle{}$??$\rangle$, $\langle{}$??$\rangle$); } |
Original | JavaScript |
//recursive process function product_r(term, a, next, b) { return a > b ? 1 : term(a) * product_r(term, next(a), next, b); } //iterative process function product_i(term, a, next, b) { function iter(a, result) { return a > b ? result : iter(next(a), term(a) * result); } return iter(a, 1); } |
Original | JavaScript |
(accumulate combiner null-value term a next b) | accumulate(combiner, null_value, term, a, next, b); |
Original | JavaScript |
//recursive process function accumulate_r(combiner, null_value, term, a, next, b) { return a > b ? null_value : combiner(term(a), accumulate_r(combiner, null_value, term, next(a), next, b)); } function sum_r(term, a, next, b) { function plus(x, y) { return x + y; } return accumulate_r(plus, 0, term, a, next, b); } function product_r(term, a, next, b) { function times(x, y) { return x * y; } return accumulate_r(times, 1, term, a, next, b); } //iterative process function accumulate_i(combiner, null_value, term, a, next, b) { function iter(a, result) { return a > b ? result : iter(next(a), combiner(term(a), result)); } return iter(a, null_value); } function sum_i(term, a, next, b) { function plus(x, y) { return x + y; } return accumulate_i(plus, 0, term, a, next, b); } function product_i(term, a, next, b) { function times(x, y) { return x * y; } return accumulate_i(times, 1, term, a, next, b); } |
Original | JavaScript |
function filtered_accumulate(combiner, null_value, term, a, next, b, filter) { return a > b ? null_value : filter(a) ? combiner(term(a), filtered_accumulate(combiner, null_value, term, next(a), next, b, filter)) : filtered_accumulate(combiner, null_value, term, next(a), next, b, filter); } |