The Azimuth Project
Functional reactive programming

Contents

Idea

Functional reactive programming (FRP)

The core idea of FRP is to use abstract data types that already include a notion of time.

FRP defines two core types, the Behavior and the Event.

A Behavior is simply a value that varies in time. You can think of it as a function that maps each moment in time to the corresponding value.

type Behavior a = Time -> a

An Event is a sequence of event occurrences. Think of it as an (infinite) list of occurrences, which are pairs: the first component indicates when the occurrences happens and the second component is a value tagged to this occurrence.

type Event    a = [(Time,a)]

In words, a Behavior is like a continuously varying value, say the position
of a ball that is being thrown by a basketball player, while an Event is a
sequence of occurrences, for instance keeping track of whenever said ball
falls through the basket.

Several combinators allow us to make new Behaviors and Events from old ones,
thus giving us a new way to program with time-dependent data. 

Details

Functional hybrid modelling

Hybrid systems combine discrete events and continuous behaviours eg. structural changes at discrete points in time. Behaviours are time-varying signals.

Non-causal modelling

Languages such as Simulink and Ptolemy II employ a causal model of computation in which the direction of signal flow is explicit, while languages such as Dymola and Modelica adopt an non-causal approach to infer causality from the interconnection of system components.

A causal or block-oriented model is an ODE in the explicit form:

$$x' = f(x,u,t)$$

where the cause-effect relationship has to be supplied by the modeller.

Non-causal modelling does not commit users to a specific notion of causality. This is claimed to improve the modularity and reusability of models.

A non-causal model is a system of differential algebraic equations (DAEs).

But current non-causal modelling languages lack the flexibility at reacting to system change as a response to extern signals. Functional Hybrid Modeling (FHM), a combined paradigm of functional programming and non-causal modeling, has been proposed to allow the description of structurally dynamic models. FHM is closely related to prior work on FRP. This framework was embodied in a language called Yampa as an extension of Haskell.

  • Hia Liu, Hydra: a functional hybrid modeling language (2006) (Hydra206Liu.pdf)

Arrows and signals

Arrowized FRP is defined as having a purely conceptual notion of behaviours.

Arrows are a more general construct than monads and more specific than functors.

A computation takes inputs of some type and produces outputs of another type.

Hence John Hughes defined a Haskell class of binary type constructors:

class Arrow a where
   arr :: (b -> c) -> a b c
   -- Each function may be treated as a computation.

arrow

(>>>) :: a b c -> a c d -> a b d
  -- Computations may be composed, by connecting the output of the first to
     the input of the second.

compose

first :: a b c -> a (b,d) (c,d)
-- A computation may be applied to part of the input, with the rest copied
through to the output.

first

with a number of axioms.

In particular they allow notions of computation that may be partially static (independent of the input) or may take multiple inputs.

Arrows can be used to map physical systems to signal functions and signal relations in a direct and composable manner.

The original Arrows paper by John Hughes introduced two new keywords:

proc (arrow abstraction)

is a kind of lambda, except that it constructs an arrow instead of a function.

(-<) (arrow application)

feeds the value of an expression into an arrow.

If you think of proc as lambda and -< as application, the above looks very much like the do-notation for monads.

Bear in mind however that behind the notation lie the more general arrows, as can be seen in the Haskell translation:

addA f g = arr (\ x -> (x, x)) >>>
             first f >>> arr (\ (y, x) -> (x, y)) >>>
             first g >>> arr (\ (z, y) -> y + z)

Arrows are less exacting than monads.

Arrows are equivalent to Freyd-categories or (more generally) premonoidal notions of computation.

Examples

Elm

Elm aims to make front-end web development more pleasant. It introduces a new approach to GUI programming that corrects the systemic problems of HTML, CSS, and JavaScript. Elm allows you to quickly and easily work with visual layout, use the canvas, manage complicated user input, and escape from callback hell.

Paywalled

FrTime

Abstract:

Functional Reactive Programming (FRP) supports the declarative construction of reactive systems through signals, or time-varying values. In this paper, we present a new language called FrTime, which provides FRP-style signals atop a dialect of Scheme. We introduce the language with a few examples and discuss its implementation. Unlike previous FRP systems, FrTime uses impure features, such as state and asynchronous communication, to model time and to control evaluation. The use of such features yields a scalable, event-driven implementation with several important advantages. Specifically, it eases integration with other systems, supports distribution of signals across a network, and permits various benign impurities. To illustrate the language’s expressive power, we present a concise implementation of a networked paddle-ball game in FrTime.

Flapjax

Abstract

This paper presents Flapjax, a language designed for contemporary Web applications.
These applications communicate with servers and have rich, interactive interfaces. 
Flapjax provides two key features that simplify writing these applications.
First, it provides event streams, a uniform abstraction for 
communication within a program as well as with external Web services. 
Second, the language itself is reactive: it automatically tracks data 
dependencies and  propagates updates along those dataflows. 
This allows developers to write reactive interfaces in a declarative 
and compositional style.

Flapjax is built on top of JavaScript. 
It runs on unmodified browsers and readily interoperates with existing
JavaScript code. 
It is usable as either a programming language (that is compiled to
JavaScript) or as a JavaScript library, and is designed for both uses. 
This paper presents the language, its design decisions, and illustrative 
examples drawn from several working Flapjax applications.

(best student paper)

Dependencies

  • JQuery

Bacon

A small functional reactive programming lib for JavaScript.

Turns your event spaghetti into clean and declarative feng shui bacon, by switching from imperative to functional. It’s like replacing nested for-loops with functional programming concepts like map and filter. Stop working on individual events and work with event streams instead. Combine your data with merge and combine. Then switch to the heavier weapons and wield flatMap and combineTemplate like a boss.

It’s the _ of Events. Too bad the symbol ~ is not allowed in JavaScript.

Hydra

Hydra is a high level, declarative language for modelling and simulation of physical systems. Systems in Hydra are being modelled using implicitly formulated (undirected) Differential Algebraic Equations (DAEs). While physical modelling is our main focus any domain is fine where problems can be formulated using DAEs.

The language provides constructs for definition and composition of model fragments that enable modelling and simulation of large, complex, hybrid and highly structurally dynamic systems.

The first outline of Hydra was given by Nilsson et al. in the framework called

Functional Hybrid Modelling (FHM). Subsequently, a number of papers has been published about the design and implementation of Hydra that can be accessed from the following web page:

Dependencies

ghc llvm sundials

Grapefruit

Grapefruit has the following important features:

a push-based FRP implementation where signals

  • can be memoized using ordinary variable bindings
  • can be merged without doubling of simultaneous events
  • cannot behave differently by starting them at different times

a record system which makes it possible that

  • input signals can be left out to get default behavior

  • output signals can be left out to ignore uninteresting data

  • output signals can be chosen and fetched by pattern matching

  • Heinrich Apfelmus, FRP tutorial slides

Dependencies

ghc gtk

Reactive Banana

Dependencies

ghc wxWigets

Netwire

Dependencies

ghc SDL

Agda

An implementation of Functional Reactive Programming for building HTML applications in Agda.

To build and application, start with an HTML file:

<html xmlns='http://www.w3.org/1999/xhtml'> <head> Hello World <script data-main='agda.frp.main' src='require.js'></script> </head> <body>

A greeting

</body> </html>

This is just a regular old HTML file, which loads the agda.frp.main JavaScript module (using require.js, but any AMD-compliant JavaScript module loader should work). The important part is:

The “agda” class and data-agda attribute indicates that an Agda program should be executed inside the annotated node.

Now write an Agda program:

open import FRP.JS.Behaviour using ( Beh ; [] ) open import FRP.JS.DOM using ( DOM ; text ) open import FRP.JS.RSet using ( ⟦⟧ )]

module Demo.Hello where

main : ∀ {w} → ⟦ Beh (DOM w) ⟧ main = text [Hello, world.]

This program creates a text node whose content is always “Hello, World.”

Compile (using the darcs snapshot of Agda 2.2.11):

agda –js Demo/Hello.agda

this will create a bunch of js files such as jAgda.Demo.Hello.js.

Put all the .js files (including require.js and the agda.frp..js files) in the same directory as hello.html.

Load hello.html in a browser, and enjoy.

There are unit tests in FRP.JS.Test, which link against John Resig’s QUnit (http://docs.jquery.com/QUnit). To run the tests, first “make tests”, then load build/tests.html in a browser.

Dependencies

agda ghc

Sodium

Dependencies

ghc GLURaw GLUT OpenGL OpenGLRaw OpenAL stb_image : https://nothings.org/stb_image.c

Questions

References

Hydra

  • Hia Liu, Hydra: a functional hybrid modeling language (2006) (Hydra206Liu.pdf)
  • Nilsson, H., Peterson, J. and Hudak, P. 2003. Functional Hybrid Modeling. In Proceedings of PADL’03: 5th International Workshop on Practical Aspects of Declarative Languages, 376-390.
  • David, R. and Alla, H. 2001. On hybrid Petri nets. Discrete Event Dyn. S. 11, 9-40.
  • Nilsson, H., 2003. Functional automatic differentiation with dirac impulses. In Proceedings of the eighth ACM SIGPLAN inter- national conference on Functional programming, page 153-164, Up- psala, Sweden.
  • Nilsson, H., Courtney, A. and Peterson J., 2002. Functional re- active programming, continued. In Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell’02), pages 51-64, Pittsberge, Pennsylvania, USA.
  • Nilsson, H., Peterson, J. and Hudak, P. 2003. Functional Hybrid Modeling. In Proceedings of PADL’03: 5th International Workshop on Practical Aspects of Declarative Languages, 376-390.

Grapefruit

  • Wofgang Jeltsch, Towards a common categorical semantics for linear-time temporal logic functional reactive programming (2012)

    Linear-time temporal logic (LTL) and functional reactive programming (FRP) are related via a Curry–Howard correspondence. Based on this observation, we develop a common categorical semantics for a subset of LTL and its corresponding flavor of FRP. We devise a class of categorical models, called fan categories, that explicitly reflect the notion of time-dependent trueness of temporal propositions and a corresponding notion of time-dependent type inhabitance in FRP. Afterwards, we define the more abstract concept of temporal category by extending categorical models of intuitionistic S4. We show that fan categories are a special form of temporal categories.

  • Wolfgang Jeltsch, Improving push-based FRP (2008)

    Push-based implementations of Functional Reactive Programming allow for writing reactive programs in a declarative style and execute them efficiently. Previous approaches in this area are not able to combine simultaneously occuring internal events. This may lead to efficiency problems and introduction of inconsistent intermediate states. Most of these implementations also lack declarative means to describe systems with feedbacks. We limit ourselves to the dataflow aspects of FRP and present an implementation which does not suffer from these deficiencies. This leads to a foundation for FRP which is more declarative than previous solutions and more efficient at the same time.

Interaction with the environment is described by circuits. A circuit has an input and an output, both of which are typically tuples of discrete signals.3 A circuit may produce occurences in its output and change the outside world in response to occurences in its input and external events. A circuit with input type i and output type o is a value of type Circuit i o. Circuit is an instance of Arrow and ArrowLoop [11] which allows complex circuits to be composed out of simpler ones. Arrow syntax [11] is typically used for this.

  • Wolfgang Jetsch, Signals not generators, Chapter 22 (2009)

    Functional Reactive Programming (FRP) uses signals to describe temporal behavior. Push-based FRP implementations avoid recomputation of signal values in certain cases by taking data dependencies into account. However, they typically do not provide signals directly. Instead, signals are produced by signal generators. Using the same generator multiple times leads to repeated computation and dependence on generation time. This reduces scalability and complicates semantics. This paper presents a push-based implementation approach which does not have these problems. Its keys to success are lazy evaluation, rank-2 polymorphism, and impredicative polymorphism. Our work results in a scalable FRP system which gives the user direct access to the key concept of FRP: the signal.

Arrows