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.

See also:

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

See the version data in the lower-right corner of each page. This version was submitted to ICFP 2008. Thanks to Cale Gibbard, Max Bolingbroke, Kenn Knowles, Jake McArthur, and an anonymous reader for pointing out these mistakes.

Version 2008/5/16

Thanks to Jake McArthur, Robin Green, and Florent Balestrieri for catching these mistakes.

Version 2008/8/2

Thanks to Amir Livne Bar-on for catching this mistake.

Version 2008/11/18