Simply efficient functional reactivity

LambdaPix technical report 2008-01

April 2008

Conal Elliott

Note: Superceded by the paper Push-pull functional reactive programming, 2009 Haskell Symposium.

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").

Paper (232K PDF) (version 2008/11/18). Remember, this version has been superceded. Please refer to the newer paper.

• Blog post, with reader comments
• Lambda-the-Ultimate page, with discussion

BibTex

  @TechReport{Elliott2008-reactive,
    author      = {Conal Elliott},
    title       = {Simply efficient functional reactivity},
    institution = {LambdaPix},
    year        = 2008,
    number      = {2008-01},
    month       = apr,
    url         = {http://conal.net/papers/simply-reactive/},
  }

Errata

Version 2008/4/2

• Page 3, section 2.2.1: in the semantic Monoid instance definition for Event, drop the “O” constructor.
• Page 4, top left (section 2.3): In the definition of before, the parameters are swapped.
• Page 5, section 4.5, second bullet: “∞” → “-∞”
• Page 5, section 4.5: “FTime t” → “FTime”
• Page 6, section 5.2: “Applicative Behavior” should be “Applicative Reactive”
• Page 7, section 6, second-to-last sentence: “will have to block the” → “will have to block until the”
• Page 8, section 7.1.2, last sentence: “do some work based partial applications” → “do some work based upon partial applications”
• Page 8, section 7.1.3, after “If the inner arrives first, switch and continue waiting for the outer”: “(`switcher` Ev u_r)” → “(`switcher` Ev u_rr)”.
• Page 8, section 7.1.3, in the full definition of u: “e'” → “Ev u_rr”
• Page 8, section 7.2.2: “instance Monad Reactive” → “instance Monad Event”
• Page 8, bottom right (section 7.2.2), in the definition of adjustTop, the constructors should be named “Ev” resp. “Fut”, not “Event” resp. “Future”.
• Page 9, last paragraph of 7.2.2: “The use of max instead a” → “The use of max instead of a”
• Page 9, section 8: “image to display window” → “image to a display window”
• Page 12, conclusion, last paragraph, “paper allows retains” → “paper retains”

Version 2008/5/16

• Page 1, footnote: use more current URL for FRP info.
• Page 9, last paragraph of 7.2.2: “The use of max instead a” → “The use of max instead of a”
• Page 3, section 2.1.2: “instance_sem Applicative Reactive” → “instance_sem Applicative Behavior” (was correct in 2008/4/2)

Version 2008/8/2

• Page 7, middle of the left column. “at :: Reactive a → R_a” → “at :: Behavior a → B_a”.

Version 2008/11/18

• fixed/simplified the race function.