Wormholes: Introducing Effects to FRP

Authors:

Daniel Winograd-Cort and Paul Hudak

Abstract:

Functional reactive programming (FRP) is a useful model for programming real-time and reactive systems in which one defines a signal function to process a stream of input values into a stream of output values.  However, performing side effects (e.g. memory mutation or input/output) in this model is tricky and typically unsafe.  In previous work, Winograd-Cort et al. introduced resource types and wormholes to address this problem.

This paper better motivates, expands upon, and formalizes the notion of a wormhole to fully unlock its potential.  We show, for example, that wormholes can be used to define the concept of causality.  This in turn allows us to provide behaviors such as looping, a core component of most languages, without building it directly into the language.  We also improve upon our previous design by making wormholes less verbose and easier to use.

To formalize the notion of a wormhole, we define an extension to the simply typed lambda calculus, complete with typing rules and operational semantics.  In addition, we present a new form of semantic transition that we call a temporal transition to specify how an FRP program behaves over time and to allow us to better reason about causality.  As our model is designed for a Haskell implementation, the semantics are lazy.  Finally, with the language defined, we prove that our wormholes indeed allow side effects to be performed safely in an FRP framework.

Bibtex:

 @InProceedings{WinogradCort2012HS,
  author = {Winograd-Cort, Daniel and Hudak, Paul},
  title = {Wormholes: {I}ntroducing {E}ffects to {FRP}},
  booktitle = {Haskell Symposium},
  numpages = {13},
  publisher = {{ACM}},
  year = {2012},
  location = {Copenhagen, Denmark},
  month = {September}
} 

Links:

Winograd-Cort-Wormholes.pdf