Archive for 30th November 2008

Sequences, streams, and segments

What kind of thing is a movie? Or a song? Or a trajectory from point A to point B? If you’re a computer programmer/programmee, you might say that such things are sequences of values (frames, audio samples, or spatial locations). I’d suggest that these discrete sequences are representations of something more essential, namely a flow of continuously time-varying values. Continuous models, whether in time or space, are often more compact, precise, adaptive, and composable than their discrete counterparts.

Functional programming offers great support for sequences of variable length. Lazy functional programming adds infinite sequences, often called streams, which allows for more elegant and modular programming.

Functional programming also has functions as first class values, and when the function’s domain is (conceptually) continuous, we get a continuous counterpart to infinite streams.

Streams, sequences, and functions are three corners of a square. Streams are discrete and infinite, sequences are discrete and finite, and functions-on-reals are continuous and infinite. The missing corner is continuous and finite, and that corner is the topic of this post.

infinitefinite
discreteStream Sequence
continuousFunction ???

You can download the code for this post.

Edits:

  • 2008-12-01: Added Segment.hs link.
  • 2008-12-01: Added Monoid instance for function segments.
  • 2008-12-01: Renamed constructor “DF” to “FS” (for “function segment”)
  • 2008-12-05: Tweaked the inequality in mappend on (t :-># a).

Continue reading ‘Sequences, streams, and segments’ »

Early inspirations and new directions in functional reactive programming

In 1989, I was a grad student nearing completion at Carnegie Mellon. Kavi Arya gave a talk on “functional animation”, using lazy lists. I was awe-struck with the elegance and power of that simple idea, and I’ve been hooked on functional animation ever since.

At the end of Kavi’s talk, John Reynolds offered a remark, roughly as follows:

You can think of sequences as functions from the natural numbers. Have you thought about functions from the reals instead? Doing so might help with the awkwardness with interpolation.

I knew at once I’d heard a wonderful idea, so I went back to my office, wrote it down, and promised myself that I wouldn’t think about Kavi’s work and John’s insight until my dissertation was done. Otherwise, I might never have finished. A year or so later, at Sun Microsystems, I started working on functional animation, which then grew into functional reactive programming (FRP).

In the dozens of variations on FRP I’ve played with over the last 15 years, John’s refinement of Kavi’s idea has always been the heart of the matter for me.

Lately, I’ve been rethinking FRP yet again, and I’m very excited about where it’s leading me.

The semantic model of FRP has been based on behaviors of infinite duration and, mostly on absolute time. Recently I realized that some problems of non-modular interaction could be elegantly addressed by switching to finite duration and relative time, and by adopting a co-monadic approach.

Upcoming post will explore these ideas.