7 Fun with Functions
It’s interesting to consider how expressive the little programming we’ve learned so far can be. To illustrate this, we’ll work through a few exercises of interesting concepts we can express using just functions as values. We’ll write two quite different things, then show how they converge nicely.
7.1 A Little Calculus
If you’ve studied the differential calculus, you’ve come across curious sytactic statements such as this: \[{{d}\over{dx}} x^2 = 2x\] Let’s unpack what this means: the \(d/dx\), the \(x^2\), and the \(2x\).
First, let’s take on the two expressions; we’ll discuss one, and the discussion will cover the other as well. The correct response to “what does \(x^2\) mean?” is, of course, an error: it doesn’t mean anything, because \(x\) is an unbound identifier.
fun square(x :: Number) -> Number: x * x end fun double(x :: Number) -> Number: 2 * x end
d-dx :: ((Number -> Number) -> (Number -> Number))
Let us now implement d-dx. We’ll implement numerical
differentiation, though in principle we could also implement
symbolic differentiation—
In general, numeric differentiation of a function at a point yields the value of the derivative at that point. We have a handy formula for it: the derivative of \(f\) at \(x\) is \[{f(x + \epsilon) - f(x)} \over {\epsilon}\] as \(\epsilon\) goes to zero in the limit. For now we’ll give the infinitesimal a small but fixed value, and later [Combining Forces: Streams of Derivatives] see how we can improve on this.
epsilon = 0.001
fun d-dx(f :: (Number -> Number)) -> (Number -> Number): (f(x + epsilon) - f(x)) / epsilon end
What’s the problem with the above definition?
fun d-dx(f :: (Number -> Number)) -> (Number -> Number): fun(x :: Number) -> Number: (f(x + epsilon) - f(x)) / epsilon end end
d-dx-square = d-dx(square) check: ins = [list: 0, 1, 10, 100] for map(n from ins): num-floor(d-dx-square(n)) end is for map(n from ins): num-floor(double(n)) end end
d-dx(fun(x): x * x end) = fun(x): 2 * x end
7.2 Streams From Functions
People typically think of a function as serving one purpose: to parameterize an expression. While that is both true and the most common use of a function, it does not justify having a function of no arguments, because that clearly parameterizes over nothing at all. Yet functions of no argument also have a use, because functions actually serve two purposes: to parameterize, and to suspend evaluation of the body until the function is applied. In fact, these two uses are orthogonal, in that one can employ one feature without the other. In Sugaring Over Anonymity we see one direction of this: parameterized functions that are used immediately, so that we employ only abstraction and not delay. Below, we will see the other: delay without abstraction.
Let’s consider the humble list. A list can be only finitely long. However, there are many lists (or sequences) in nature that have no natural upper bound: from mathematical objects (the sequence of natural numbers) to natural ones (the sequence of hits to a Web site). Rather than try to squeeze these unbounded lists into bounded ones, let’s look at how we might represent and program over these unbounded lists.
fun nats-from(n): link(n, nats-from(n + 1)) end
Does this program have a problem?
While this represents our intent, it doesn’t work: running it—
This is where our insight into functions comes in. A function, as we have just noted, delays evaluation of its body until it is applied. Therefore, a function would, in principle, defer the invocation of nats-from(n + 1) until it’s needed.
data Stream<T>: |
| lz-link(h :: T, t :: ( -> Stream<T>)) |
end |
ones = lz-link(1, fun(): ones end)
ones = link(1, ones)
fun nats-from(n): lz-link(n, lam(): nats-from(n + 1) end) end
nats = nats-from(0)
Earlier, we said that every list is finite and hence eventually terminates. How does this remark apply to streams, such as the definition of ones or nats above?
A similar reasoning doesn’t apply to lists because the rest of the list has already been constructed; in contrast, placing a function there creates the potential for a potentially unbounded amount of computation to still be forthcoming.
That said, even with streams, in any given computation, we will create only a finite prefix of the stream. However, we don’t have to prematurely decide how many; each client and use is welcome to extract less or more, as needed.
fun<T> lz-first(s :: Stream<T>) -> T: s.h end
fun<T> lz-rest(s :: Stream<T>) -> Stream<T>: s.t() end
fun<T> take(n :: Number, s :: Stream<T>) -> List<T>: if n == 0: empty else: link(lz-first(s), take(n - 1, lz-rest(s))) end end
check: take(10, ones) is map(lam(_): 1 end, range(0, 10)) take(10, nats) is range(0, 10) take(10, nats-from(1)) is map((_ + 1), range(0, 10)) end
fun<A, B> lz-map2(f :: (A, A -> B), |
s1 :: Stream<A>, s2 :: Stream<A>) |
-> Stream<B>: |
lz-link(f(lz-first(s1), lz-first(s2)), |
lam(): lz-map2(f, lz-rest(s1), lz-rest(s2)) end) |
end |
rec fibs = lz-link(0, lam(): lz-link(1, lam(): lz-map2((_ + _), fibs, lz-rest(fibs)) end) end)
check: take(10, fibs) is [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] end
Define the equivalent of map, filter, and fold for streams.
Streams and, more generally, infinite data structures that unfold on demand are extremely valuable in programming. Consider, for instance, the possible moves in a game. In some games, this can be infinite; even if it is finite, for interesting games the combinatorics mean that the tree is too large to feasibly store in memory. Therefore, the programmer of the computer’s intelligence must unfold the game tree on demand. Programming it by using the encoding we have described above means the program describes the entire tree, lazily, and the tree unfolds automatically on demand, relieving the programmer of the burden of implementing such a strategy.
In some languages, such as Haskell, lazy evaluation is built in by default. In such a language, there is no need to use thunks. However, lazy evaluation places other burdens on the language [REF].
7.3 Combining Forces: Streams of Derivatives
When we defined d-dx, we set epsilon to an arbitrary, high value. We could instead think of epsilon as itself a stream that produces successively finer values; then, for instance, when the difference in the value of the derivative becomes small enough, we can decide we have a sufficient approximation to the derivative.
The first step is, therefore, to make epsilon some kind of parameter rather than a global constant. That leaves open what kind of parameter it should be (number or stream?) as well as when it should be supplied.
fun d-dx(f :: (Number -> Number)) -> (Number -> (Number -> Number)): fun(x :: Number) -> (Number -> Number): fun(epsilon :: Number) -> Number: (f(x + epsilon) - f(x)) / epsilon end end end
d-dx-square = d-dx(square)
tenths = block: fun by-ten(d): new-denom = d / 10 lz-link(new-denom, lam(): by-ten(new-denom) end) end by-ten(1) end
check: take(3, tenths) is [list: 1/10, 1/100, 1/1000] end
d-dx-square-at-10 = d-dx-square(10)
lz-map(d-dx-square-at-10, tenths)
Extend the above program to take a tolerance, and draw as many values from the epsilon stream as necessary until the difference between successive approximations of the derivative fall within this tolerance.