Difference between revisions of "Functional Reactive Programming"

From HaskellWiki
Jump to navigation Jump to search
m
m
(2 intermediate revisions by the same user not shown)
Line 67: Line 67:
   
 
A series of events is most easily represented as a list of <code>Event</code>-values, commonly referred to as an ''event stream'' (or simply a ''stream'').
  
A series of events is most easily represented as a list of <code>Event</code>-values, commonly referred to as an ''event stream'' (or simply a ''stream'').
  +
  +
== Semantic functions? ==
  +
  +
From page 6 of [http://conal.net/papers/icfp97/icfp97.pdf the paper]:
  +
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
  +
An early implementation of Fran represented behaviors as implied in the formal semantics:
  ⚫
<haskell>
  +
data Behavior a = Behavior (Time -> a)
  ⚫
</haskell>
  +
This representation, however, leads to a serious inefficiency [a “space-time” leak].
  +
</div>
  +
  +
So instead of one canonical implementation of FRP, this tendency to "leak" has led to a variety of implementations, each with its own benefit-cost trade-offs.
   
 
== Libraries ==
  
== Libraries ==
Line 131: Line 144:
 
In his thesis [https://core.ac.uk/download/9835633.pdf Functional Real-Time Programming: The Language Ruth And Its Semantics], some parts of the semantics Dave Harrison gives for ''Ruth'' bears a curious resemblance to those for FRP:
  
In his thesis [https://core.ac.uk/download/9835633.pdf Functional Real-Time Programming: The Language Ruth And Its Semantics], some parts of the semantics Dave Harrison gives for ''Ruth'' bears a curious resemblance to those for FRP:
   
−
* from page 48:
 +
* <small>(page 48)</small>
 
:{|
  
:{|
 
|<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
  
|<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
−
A channel is an infinite stream of timestamped data values, or messages, each message denoting an event in the system.
 +
A channel is an infinite stream of timestamped data values, or messages, each message denoting an event in the system. [...]
 
</div>
  
</div>
 
<sup> </sup>
  
<sup> </sup>
 
<haskell>
  
<haskell>
 
type Channel a = [Event a]
  
type Channel a = [Event a]
  +
data Event a = At Time a
 
</haskell>
  
</haskell>
 
|}
  
|}
   
−
* from page 50:
 +
* <small>(page 61)</small>
 
:{|
  
:{|
 
|<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
  
|<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
  +
In the semantics given in Chapter 5 every <i>Ruth</i> program is supplied with a tree of time values (or clock) as suggested in [https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf this paper] and each <i>Ruth</i> process is given a different sub-tree of the clock [...]
−
A unique clock is automatically supplied to each Ruth process at run-time, to provide real-time information, [...]
  
 
</div>
  
</div>
 
<sup> </sup>
  
<sup> </sup>
 
<haskell>
  
<haskell>
  +
type Program = Clock -> ...
 
type Process a = Clock -> a
  
type Process a = Clock -> a
⚫
</haskell>
  
   
−
where a <code>Clock</code> value is a tree of time-values, rather than the direct use of time-values in FRP:
  
⚫
<haskell>
  
−
-- from page 61
  
 
type Clock = Tree Time
  
type Clock = Tree Time
  +
left :: Clock -> Clock
⚫
type Time = Integer -- must be zero or larger
  
  +
right :: Clock -> Clock
−  
  +
</haskell>
  +
<sup> </sup>
  +
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
  +
A clock tree is composed of a node holding a non-negative integer denoting the current time and two sub-trees containing the times of future events. As the tree is (lazily) evaluated each of the nodes is instantiated with the value of system time <i>at the time at which the node is instantiated</i>, thus giving programs reference to the current time. [...]
  +
</div>
  +
<sup> </sup>
  +
<haskell>
  ⚫
type Time = Integer -- must be zero or larger
 
data Tree a = Node { contents :: a,
  
data Tree a = Node { contents :: a,
 
left :: Tree a,
  
left :: Tree a,
 
right :: Tree a }
  
right :: Tree a }
  +
  +
currentTime :: Clock -> Time
  +
currentTime = contents
 
</haskell>
  
</haskell>
 
|}
  
|}
   
  +
Regarding Harrison's semantics:
−
As a ''Ruth'' process runs, the nodes of the clock are used incrementally:
  
  +
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote"><small>(page 53)</small>
−
* to ascertain the current time (<code>contents</code>), and
  
  +
−
* to provide other clocks for use elsewhere (<code>left</code> and <code>right</code>).
  
  +
The semantics of <i>Ruth</i> given in Chapter 5 assume a normal order evaluation strategy such as is provided by the technique of lazy evaluation [...]. Consequently <code>whererec</code> can be used to define infinite data structures.
  +
</div>
   
 
[[Category:FRP|*]]
  
[[Category:FRP|*]]

Revision as of 07:45, 17 August 2022

Functional Reactive Programming (FRP) integrates time flow and compositional events into functional programming. This provides an elegant way to express computation in domains such as interactive animations, robotics, computer vision, user interfaces, and simulation.


Introduction

The original formulation of Functional Reactive Programming can be found in the ICFP 97 paper Functional Reactive Animation by Conal Elliott and Paul Hudak. It introduces the following semantic functions:

  • at : Behaviorα → Time → α
  • occ : Eventα → Time × α

to provide a formal description of operations on values now commonly known as behaviors and events. But what are they?

Behaviors

Traditionally a widget-based user interface is created by a series of imperative actions. First an action is invoked to create an edit widget, then additional actions can be invoked to read its current content, set it to a specific value or to assign an event callback for when the content changes. This is tedious and error-prone.

A better way to represent an edit widget's content is a time-varying value, called a behavior. The basic idea is that a time-varying value can be represented as a function of time: 

newtype Behavior a =
    Behavior {
      at :: Time -> a
    }

myTodoList                :: Behavior Text
yesterday                 :: Time
myTodoList `at` yesterday :: Text

This is only a theoretical model, because a time-varying value can represent something impure like the content of an edit widget, the current value of a database entry as well as the system clock's current time. Using this model the current content of an edit widget would be a regular first class value: 

myEditWidget :: Behavior Text

In most frameworks there is an applicative interface for behaviors, such that you can combine them easily: 

liftA2 (<>) myEdit1 myEdit2

The result is a time-varying value that represents the concatenation of myEdit1 and myEdit2. This could be the value of a third widget, a label, to display the concatenation. The following is a hypothetical example: 

do edit1 <- editWidget
   edit2 <- editWidget
   label <- label (liftA2 (<>) edit1 edit2)
   {- ... -}

Without behaviors you would have to write event callback actions for the edit widgets to update the label's content. With behaviors you can express this relationship declaratively.

Events

While behaviours work well for describing properties which are continuous (e.g. the motion of an animated object), other properties are more discrete (e.g. what button on the mouse was clicked or the screen position where it happened). Events more easily accommodate information like this, by associating the data value of interest with a particular time: 

newtype Event a =
    Event {
      occ :: (Time, a)
    }

mouseInWindowNow     :: Event Bool
occ mouseInWindowNow :: (Time, Bool)

A series of events is most easily represented as a list of Event-values, commonly referred to as an event stream (or simply a stream).

Semantic functions?

From page 6 of the paper:

An early implementation of Fran represented behaviors as implied in the formal semantics: 

data Behavior a = Behavior (Time -> a)

This representation, however, leads to a serious inefficiency [a “space-time” leak].

So instead of one canonical implementation of FRP, this tendency to "leak" has led to a variety of implementations, each with its own benefit-cost trade-offs.

Libraries

A simple, practical comparison between FRP libraries is done by frp-zoo

Publications and talks

Books

Blog posts

People

History

A possible predecessor?

In his thesis Functional Real-Time Programming: The Language Ruth And Its Semantics, some parts of the semantics Dave Harrison gives for Ruth bears a curious resemblance to those for FRP:

  • (page 48)

A channel is an infinite stream of timestamped data values, or messages, each message denoting an event in the system. [...] 

type Channel a = [Event a]
data Event a   = At Time a
  • (page 61)

In the semantics given in Chapter 5 every Ruth program is supplied with a tree of time values (or clock) as suggested in this paper and each Ruth process is given a different sub-tree of the clock [...] 

type Program = Clock -> ...
type Process a = Clock -> a

type Clock = Tree Time
left  :: Clock -> Clock
right :: Clock -> Clock

A clock tree is composed of a node holding a non-negative integer denoting the current time and two sub-trees containing the times of future events. As the tree is (lazily) evaluated each of the nodes is instantiated with the value of system time at the time at which the node is instantiated, thus giving programs reference to the current time. [...] 

type Time   = Integer  -- must be zero or larger 
data Tree a = Node { contents :: a,
                     left     :: Tree a,
                     right    :: Tree a }

currentTime :: Clock -> Time
currentTime = contents

Regarding Harrison's semantics:

(page 53)

The semantics of Ruth given in Chapter 5 assume a normal order evaluation strategy such as is provided by the technique of lazy evaluation [...]. Consequently whererec can be used to define infinite data structures.

Retrieved from "https://wiki.haskell.org/index.php?title=Functional_Reactive_Programming&oldid=65316"