Push-Pull Functional Reactive Programming
📜 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 a new implementation, 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”).
✨ Summary
The paper develops a hybrid implementation model for functional reactive programming that combines push-based evaluation for discrete changes with pull-based evaluation for continuous time. Its central decomposition represents reactive behaviors as reactive values composed with time functions. Reactive values expose discrete phase changes and can be evaluated and cached incrementally, while time functions retain demand-driven sampling for continuously varying quantities.
The paper also gives a denotationally grounded interface based largely on standard algebraic abstractions, including functors, applicative functors, monoids, and monads. It represents events as future reactive values, introduces improving values to expose partial information about future times, and uses concurrent “unambiguous choice” to obtain faster results while preserving deterministic semantics. Monotonic sampling further avoids repeatedly searching through past event occurrences when behaviors are sampled in chronological order.
Subsequent work and implementations explicitly reference these ideas. The scalaz-reactive library describes itself as a high-performance functional reactive library and adopts core representations corresponding to behaviors, events, reactive values, future values, and time functions. (github.com) The PureScript hareactive library states that it is highly inspired by this paper and implements higher-order FRP with continuous time. (pursuit.purescript.org) A later implementation thesis identifies the paper’s separation of discrete and continuous signals as the basis for implementing a hybrid system intended to improve performance and reaction latency. (newtraell.cs.uchicago.edu) FRP educational and research materials also cite the paper as a useful account of mapping FRP’s semantic model to an applicative and functor-based API. (github.com)