Functional Reactive Programming from First Principles

Authors:

Zhanyong Wan, Paul Hudak

Abstract:

This paper gives a denotational semantics to FRP, and discusses the connection between the semantics and a stream-based implementation.

Abstract Functional Reactive Programming, or FRP, is a general framework for programming hybrid systems in a high-level, declarative manner.  The key ideas in FRP are its notions of behaviors and events.  Behaviors are time-varying, reactive values, while events are time-ordered sequences of discrete-time event occurrences.  FRP is the essence of Fran, a domain-specific language embedded in Haskell for programming reactive animations, but FRP is now also being used in vision, robotics and other control systems applications.

In this paper we explore the formal semantics of FRP and how it relates to an implementation based on streams that represent (and therefore only approximate) continuous behaviors.  We show that, in the limit as the sampling interval goes to zero, the implementation is faithful to the formal, continuous semantics, but only when certain constraints on behaviors are observed.  We explore the nature of these constraints, which vary amongst the FRP primitives.  Our results show both the power and limitations of this approach to language design and implementation.  As an example of a limitation, we show that streams are incapable of representing instantaneous predicate events over behaviors.

Bibtex:

 @InProceedings(wan00:frp,
  author =	 "Zhanyong Wan and Paul Hudak",
  title =	 "{F}unctional {R}eactive {P}rogramming from First
                  Principles",
  year =	 2000,
  booktitle =	 "Proc. {ACM} {SIGPLAN'00} Conference on Programming
                  Language Design and Implementation ({PLDI'00})"
) 

Links:

frp-1st.pdf