Why program with continuous time?

For me functional reactive programming (FRP) has been mainly about two principles.

One is denotational design (i.e., based on simple, precise denotational semantics), which has been integral to FRP since the first incarnation as ActiveVRML. I’ve written several things recently about denotational design.

My second core principle is continuous time, which has been present since Fran & ActiveVRML’s predecessor TBAG.

Today I read a confusion that I’ve heard many times before about continuous time, which I’d like to bring up, in part because I love continuous time, and in part because there’s a much broader underlying principle of software design.

[...] I don’t see why the lack of continuous streams leaves a “gap”. In the end all streams are discrete.

“In the end”, yes. Just as in the end, numbers are displayed as ascii numerals. However, programming is more about the middle than the end, i.e., more about composition than about output. For that reason, we don’t generally use strings in place of numbers. If we did, composition operations (arithmetic) would be very awkward. Similarly, continuity in space and in time is better for composition/modularity, leaving discreteness to the output step.

Another name for “continuous” is “resolution-independent”, and thus able to be transformed in time and space with ease and without propagating and amplifying sampling artifacts.

As another example, consider the data types in a 3D graphics API. In the end, all graphics is pixels, isn’t it? So what gap is left in a pixel-oriented API that doesn’t address higher-level continuous notions like triangles or curved surfaces? (Hint: it’s not just speed.)

One could go further than strings and pixels, and say that “in the end” my data types will end up as phosphors or electrical impulses, so programming at those levels is perfectly adequate. Again, composability would suffer.

Another example is functional vs imperative programming. It’s all side-effects in the end. Functional programming excels in composability, as explained and illustrated by John Hughes in Why Functional Programming Matters. And I’m not just talking about pure functional programming, but the availability of compound expressions, as introduced in Fortran (controversially), despite that machines just execute sequences of atomic, side-effecting statements in the end.

Another example, and really the heart of John’s paper, is finite vs infinite data structures. We only access a finite amount of data in the end. However, allowing infinite data structures in the middle makes for a much more composable programming style.

Some unsolicited advice to us all: Next time you see someone doing something and you don’t understand their underlying motivation, ask them. Many issues are not immediately obvious, so don’t be shy! Reading papers can help as well.

For more on continuous time:

Edits:

  • 2010-01-03: Trimmed & tweaked the unsolicited advice. Hopefully less peevish/patronizing now. Thanks for the feedback.
  • 2010-01-07: Trimmed quote.

Simply efficient functional reactivity

I submitted a paper Simply efficient functional reactivity to ICFP 2008.

Abstract:

Functional reactive programming (FRP) has simple and powerful semantics, but has resisted efficient implementation. In particular, most past implementations have used demand-driven sampling, which accommodates FRP’s continuous time semantics and fits well with the nature of functional programming. Consequently, values are wastefully recomputed even when inputs don’t change, and reaction latency can be as high as the sampling period.

This paper presents a way to implement FRP that combines data- and demand-driven evaluation, in which values are recomputed only when necessary, and reactions are nearly instantaneous. The implementation is rooted in a new simple formulation of FRP and its semantics and so is easy to understand and reason about.

On the road to efficiency and simplicity, we’ll meet some old friends (monoids, functors, applicative functors, monads, morphisms, and improving values) and make some new friends (functional future values, reactive normal form, and concurrent “unambiguous choice”).

Blending continuity into reactive values