Conal Elliott

Functional programming abounds with recursively defined data types. We often draw these structured values as trees with the root at the top and the leaves at the bottom. Lazy functional programming allows values (structures) of these types to be “bottomless”, meaning we can descend forever. There are many examples of how supporting such values gives an enormous boost to modularity. (See, e.g., John Hughes’s classic paper Why Functional Programming Matters.) We usually refer to these values as “infinite”, but I’d like to suggest “bottomless” as a more specific alternative, and to point out a limitation that perhaps is not widely noticed.

Although we can descend infinitely in lazy functional programming, we can only ascend finitely. If I’m traversing a lazy list, there may be infinitely many elements on my right (yet to be visited) but only finitely many on my left (already visited). While traversing a tree, there may be infinite paths below but only a finite one above (leading to my current position).

In other words, our data is bottomless, but not topless. What would it be like to go beyond our usual merely uni-infinite data and program with bi-infinite data instead? With data that is both bottomless and topless?

In what sense are our current lazy data types only uni-infinite, i.e., “topped” rather than topless. What does it even mean to ascend in a data structure, when all of the pointers are downward (from parent to child)? I’m thinking of recursively defined functions, in which each descension is a recursive call (passing in a structure’s component), and each ascension is a return. The topped nature of data is reflected in the finiteness of the call stack at every point.

What keeps our call stacks finite? I guess that the stack starts out empty, and each deepening step (function call) takes some time. In contrast, the data depth can start out infinite.

To get topless data, start with an infinite stack.

To apply this idea in an existing language, say Haskell, start by reifying the control stack into a lazy data structure of some sort. For instance, a lazy list (stream). Or a zipper! As pointed out in Another angle on zippers, these two ideas are very close together. A zipper can be represented as a list of derivatives (one-hole contexts), together with a sub-structure of focus:

type Context t = [Der (PF t) t]

type Zipper t = (Context t, t)

This Context type uses a list to allow for topped data. For purely topless types (as in the example below), we can use a more precise type of infinite-only lists:

type Context t = Stream (Der (PF t) t)

where Stream comes from Wouter Swierstra‘s Stream package:

data Stream a = Cons a (Stream a)

Using Stream, we can eliminate the only failure mode in the zipper operations of Another angle on zippers, namely going up with an empty context.

Now let’s look at an example of a purely topless data type.

Representing images

I’ve noticed functional programming’s bottomless vs topless disparity over the years when thinking about functional imagery. I like formulating imagery as functions over continuous and infinite space, i.e., infinite in detail and infinite in extent. These properties make images more simply and generally composable than the usual implementation-oriented approach to images (discrete and finite). (Ditto for behavior, as functions of continuous and infinite time.)

An easy way to implement the function-of-space model of images is directly as functions of space, i.e., use the computable functions from our programming language to represent the mathematical functions in the semantic model. In Pan and a few following systems, I used a variant of this simple implementation approach, using Haskell functions that generate expressions to be compiled into highly optimized low-level code.

Representing functions as functions has the benefit of simplicity. Ironically, however, functional programming penalizes the use of functions as a representation. Other than functions, data representations cache their components. For instance, if I extract the second element of a triple twice, that element will be computed only once. In contrast, if I apply a function twice to the second value in a three-value domain (e.g., Cold, Medium, Hot), then the result will be computed twice, not once.

One way to avoid this penalty is memoization, which is the conversion of functions into data structures. However, I think memoization isn’t quite what I’m looking for to implement imagery or behavior. In those cases, the function domains are continuous, and the likelihood of a repeated sampling at exactly the same domain points is vanishingly small. Well, that statement isn’t true, as it assumes uniformly random sampling over time & space, but often some repeated sampling occurs by construction, and caching has been useful in function-based FRP implementations.

For imagery, I like to pan, zoom, and rotate interactively. The simplest implementation model I know samples an image once for each pixel. A variation, e.g. used in Pan and Pajama, is to sample several times per pixel for progressive, stochastic anti-aliasing. One could perhaps go even further and use something like exact numeric integration to anti-alias perfectly.

Being function-centered, these implementation styles have tremendous waste, computing each display frame (sampling in discrete time & space) from scratch, reusing no sampling work from previous frames, even though the resulting images are very similar while interactively perusing. Modern graphics hardware can pan, zoom, and rotate (PZR) discrete finite samplings (“bitmaps”) with modest filtering very fast.

I want to exploit that hardware without compromising the simple denotational model of continuous & discrete images. An idea I’ve been playing with is to use an image pyramid, which is a stack of progressively higher resolution samplings, as in hardware mip-maps. Those samplings can be organized into an infinite quadtree. Each quadtree level has a texture map (bitmap stored in graphics memory), and all texture maps have the same of samples (pixels), e.g., 256 × 256. In addition to a texture map, each quadtree has four subtrees, corresponding to four spatial subquadrants. Abstracting out the texture map, we might write

data Quadtree a = Quadtree a (Quad (Quadtree a))

type Quad t = (t,t,t,t)

It’s fairly easy to write a lazy functional recursive renderer that converts a function-style image into a quadtree. The recursive argument to this renderer is a square region of space. To display such a tree interactively, at each frame pick a level that suits the current zoom factor, e.g., so that one sample corresponds roughly to one pixel. Rendering a single frame involves choosing a subset of the quadtree’s texture maps and displaying them with hardware-accelerated adjustments for PZR.

As an important optimization, reject any subtrees that are outside of the current view window, given the current view transformation (pan vector, zoom factor, and rotation angle). Thanks to laziness, this structure will get computed and filled in only as it’s accessed. Warren Burton explored lazy functional quadtrees in the 1980s. See, e.g., Functional programming and quadtrees by F. W. Burton and J. G. Kollias in IEEE Software 6(1):90-97, January 1989.

There’s a problem with this idea of using quadtrees for infinite continuous images. The image representation captures the continuous aspect but not the infinite aspect. Or more precisely, it captures infinite resolution but not infinite extent. Descending in a spatial quadtree doubles the resolution (in each direction) and halves the extent. Conversely, ascending halves the resolution and doubles the extent. To find a collection of texture maps of a desired resolution and spatial region, ascend high enough to encompass the region, and then descend low enough to get the required resolution.

So, just as bottomlessness gives rise to infinite resolution, toplessness would give rise to infinite extent.

For functions of continuous & infinite time, the domain is 1D instead of 2D, so replace quadtrees and their zippers by binary trees and their zippers. (See Sequences, segments, and signals for related remarks.)

Aside: thought tools

I have a prototype implementation of the lazy quadtree scheme in Objective C for the iPhone OS. Given the clumsiness of Objective C for functional programming, and particularly the language’s weak compile-time typing and lack of parametric polymorphism, I switched to Haskell to work out the zipper aspect.

Once I was writing Haskell, the imperative machinery faded from view and I couldn’t help but start seeing essential patterns. Tinkering with those patterns led me to new insights, including the ones described in my recent series of posts on higher-order types, derivatives, and zippers. I am grateful to have this higher-order lazy language with rich static typing as a thought tool, to help me gain insights and weed out my mistakes. It’s a bonus to me that the language is executable as well.

Conclusion

This idea of topless data (with its infinite call stacks) has been bumping around in my mind for 15 years or so. It was probably inspired in part by Mitch Wand’s 1980 paper Continuation-Based Program Transformation Strategies, which I read in grad school. That article is on my short list of research writings that have most influenced me. If you haven’t read it, or haven’t read it recently, please do.

In finishing this blog post, I’m a little uncomfortable with the fuzziness of what I’ve presented. Buckminster Fuller said “I call intuition cosmic fishing. You feel a nibble, then you’ve got to hook the fish.” Topless data has been a helpful intuition for me. I’m not sure I’ve quite hooked the fish, but perhaps you’ll catch something useful to you in this post anyway.

Functional programming abounds with recursively defined data types. We often draw these structured values as trees with the root at the top and the leaves at the bottom. Lazy functional...