### 13` `Functions as Data

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.

#### 13.1` `A Little Calculus

\begin{equation*}{\frac{d}{dx}} x^2 = 2x\end{equation*}

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—

\begin{equation*}\frac{f(x + \epsilon) - f(x)}{\epsilon}\end{equation*}

epsilon = 0.001

fun d-dx(f :: (Number -> Number)) -> (Number -> Number): (f(x + epsilon) - f(x)) / epsilon end

Do Now!

What’s the problem with the above definition?

fun d-dx(f :: (Number -> Number)) -> (Number -> Number): lam(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(lam(x): x * x end) = lam(x): 2 * x end

\begin{equation*}{\frac{d}{dx}} [x \rightarrow x^2] = [x \rightarrow 2x]\end{equation*}

#### 13.2` `A Helpful Shorthand for Anonymous Functions

{(a): b}

{(x): x * x}

fun d-dx-short(f): {(x): (f(x + epsilon) - f(x)) / epsilon} end

#### 13.3` `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

Do Now!

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, lam(): ones end)

ones = link(1, ones)

rec ones = lz-link(1, lam(): ones end)

Exercise

Earlier we said that we can’t writeones = link(1, ones)

What if we tried to writerec ones = link(1, ones)

instead? Does this work and, if so, what value is ones bound to? If it doesn’t work, does it fail to work for the same reason as the definition without the rec?

rec ones = lz-link(1, {(): ones})

fun nats-from(n :: Number): lz-link(n, {(): nats-from(n + 1)}) end

nats = nats-from(0)

Do Now!

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 lz-first<T>(s :: Stream<T>) -> T: s.h end

fun lz-rest<T>(s :: Stream<T>) -> Stream<T>: s.t() end

fun take<T>(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 lz-map2<A, B, C>( |

f :: (A, B -> C), |

s1 :: Stream<A>, |

s2 :: Stream<B>) -> Stream<C>: |

lz-link( |

f(lz-first(s1), lz-first(s2)), |

{(): lz-map2(f, lz-rest(s1), lz-rest(s2))}) |

end |

rec fibs = lz-link(0, {(): lz-link(1, {(): lz-map2({(a :: Number, b :: Number): a + b}, fibs, lz-rest(fibs))})})

check: take(10, fibs) is [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] end

Exercise

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].

#### 13.4` `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)): lam(x :: Number) -> (Number -> Number): lam(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)

Exercise

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.