Personal tools

Old-reactive

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Abstract: added purely functional aspect, in contrast with DataDriven)
(Category:Reactivity removed (overlap with FRP), Category:Event removed (it is for meetings))
 
(23 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[Category:Events]]
 
[[Category:Reactivity]]
 
 
[[Category:FRP]]
 
[[Category:FRP]]
 
[[Category:Packages]]
 
[[Category:Packages]]
Line 6: Line 4:
 
== Abstract ==
 
== Abstract ==
   
'''Reactive''' is a simple foundation for programming reactive systems functionally. Like Fran/FRP, it has a notions of (reactive) behaviors and events. Like [[DataDriven]], Reactive has a data-driven implementation. The main difference between Reactive and DataDriven are
+
'''Note:''' I have retired the old version of Reactive on darcs.haskell.org.
* Reactive builds on STM-based IVars, while DataDriven builds on continuation-based computations; and
+
Please use the new [[Reactive]].
* The algebra of Events and reactive values (called "sources" in DataDriven) are ''purely'' functional. I couldn't figure out how to accomplish that in DataDriven.
 
   
The inspiration for Reactive was Mike Sperber's [[http://www-pu.informatik.uni-tuebingen.de/lula/deutsch/publications.html Lula]] implementation of FRP. Mike used blocking threads, which I had never considered for FRP. While playing with the idea, I realized that I could give a very elegant and efficient solution to caching, which DataDriven doesn't do. (For an application <hask>f <*> a</hask> of a varying function to a varying argument, caching remembers the latest function to apply to a new argument and the last argument to which to apply a new function.)
+
----
   
As with [[DataDriven]], Reactive provides instances for Monoid, Functor, Applicative, and Monad.
+
'''Reactive''' is a simple foundation for [[Functional Reactive Programming|programming reactive systems functionally]]. Like Fran/FRP, it has a notions of (reactive) behaviors and events. Like [[DataDriven]], Reactive has an efficient, data-driven implementation. The main difference between Reactive and DataDriven are
  +
* Reactive provides and builds on "functional futures", which in turn build on [[GHC/Concurrency|Concurrent Haskell]] threads, while DataDriven builds on continuation-based computations; and
  +
* The algebras of events and reactive values (called events and sources in DataDriven) are ''purely'' functional. I couldn't figure out how to accomplish that in DataDriven.
  +
* Reactive manages (I hope) to get the efficiency of data-driven computation with a (sort-of) demand-driven architecture. For that reason, Reactive is garbage-collector-friendly, while DataDriven depends on weak references (because [[DataDriven#GC_favors_demand-driven_computation|GC favors demand-driven computation]].)
  +
* Reactive elegantly and efficiently ''caches'' values.
  +
* Reactive uses the term "reactive values" (<hask>Reactive</hask>), where DataDriven uses "sources" (<hask>Source</hask>).
  +
  +
The inspiration for Reactive was Mike Sperber's [http://www-pu.informatik.uni-tuebingen.de/lula/deutsch/publications.html Lula] implementation of FRP. Mike used blocking threads, which I had never considered for FRP before a conversation with him at ICFP 2007. While playing with the idea, I realized that I could give a very elegant and efficient solution to caching, which DataDriven doesn't do. (For an application <hask>f <*> a</hask> of a varying function to a varying argument, caching remembers the latest function to apply to a new argument and the latest argument to which to apply a new function.)
  +
  +
As with [[DataDriven]], Reactive provides instances for <hask>Monoid</hask>, <hask>Functor</hask>, <hask>Applicative</hask>, and <hask>Monad</hask>.
   
 
Besides this wiki page, here are more ways to find out about Reactive:
 
Besides this wiki page, here are more ways to find out about Reactive:
* Read [http://darcs.haskell.org/packages/reactive/doc/html/reactive the Haddock docs].
+
* Read [http://darcs.haskell.org/packages/reactive/doc/html the Haddock docs].
* Get the code repository: '''<tt>darcs get http://darcs.haskell.org/packages/reactive</tt>'''.
+
* Get the code repository: '''<tt>darcs get http://darcs.haskell.org/packages/old-reactive/</tt>'''. (Old version, to be replaced in September 08.)
* Install from Hackage (''coming'').
+
* Install from [http://hackage.haskell.org Hackage].
 
* See the [[Reactive/Versions| version history]].
 
* See the [[Reactive/Versions| version history]].
   
Please leave comments at the [[Talk:Reactive|Talk page]].
+
Also, the paper ''[http://conal.net/papers/simply-reactive/ Simply Efficient Functional Reactivity]'', and its [http://conal.net/blog/posts/simply-efficient-functional-reactivity/ blog post with discussion], describe a (not-yet-released) successor to Reactive that solves the determinacy problem mentioned below.
  +
  +
== Modules ==
  +
  +
=== Data.Future ===
  +
  +
A ''[http://en.wikipedia.org/wiki/Futures_and_promises future]'' is a value that will become knowable only later. Primitive futures can be things like "the value of the next key you press", or "the value of LambdaPix stock at noon next Monday". The term "[http://en.wikipedia.org/wiki/Futures_and_promises promise]" might be more fitting.
  +
  +
Composition is via standard type classes: <hask>Functor</hask>, <hask>Applicative</hask>, <hask>Monad</hask>, and <hask>Monoid</hask>.
  +
* <hask>Monoid</hask>: <hask>mempty</hask> is a future that never becomes knowable. <hask>a `mappend` b</hask> is whichever of <hask>a</hask> and <hask>b</hask> is knowable first.
  +
* <hask>Functor</hask>: apply a function to a future. The result is knowable when the given future is knowable.
  +
* <hask>Applicative</hask>: <hask>pure</hask> gives value knowable since the beginning of time. <hask>(<*>)</hask> applies a future function to a future argument. Result available when ''both'' are available, i.e., it becomes knowable when the later of the two futures becomes knowable.
  +
* Monad: <hask>return</hask> is the same as <hask>pure</hask> (as always). <hask>(>>=)</hask> cascades futures. <hask>join</hask> resolves a future future value into a future value.
  +
  +
The current implementation is nondeterministic in <hask>mappend</hask> for futures that become knowable at the same time or nearly the same time. I want to make a deterministic implementation.
  +
  +
==== Garbage collection of futures ====
  +
  +
Baker & Hewitt's 1977 paper ''[http://citeseer.ist.psu.edu/baker77incremental.html The Incremental Garbage Collection of Processes]'' discusses using garbage collection to prevent the useless threads from consuming resources. In particular, consider <hask>Future</hask>'s <hask>mappend</hask> (sometimes called "parallel or"). Once one thread completes, the other threads are then useless, and some might consume resources forever. My current implementation kill the losing threads. Baker & Hewitt suggest instead using garbage collection. I'm stumped about how to GC non-winning threads in a race between futures ("parallel or"). The winner-kills-loser approach seems to work fine, though is potentially dangerous w.r.t locked resources. Still, the elegance of a GC-based solution appeals to me.
  +
  +
==== Concurrent Haskell vs STM ====
  +
  +
Futures are implemented using Concurrent Haskell's <hask>MVar</hask>s. I first tried using STM and <hask>TVar</hask>s, simply using <hask>orElse</hask> to implement <hask>mappend</hask> for futures. However, I didn't see how to avoid nesting <hask>atomically</hask>, which yielded a run-time error.
  +
  +
=== Data.SFuture ===
  +
  +
A target denotational semantics for Data.Future -- simple, precise, and deterministic, in terms of time/value pairs.
  +
  +
=== Data.Reactive ===
  +
  +
This module defines ''events'' and ''reactive values''. An event is stream of future values in order of availability. A reactive value is a discretly time-varying value. These two types are closely linked: a reactive value is defined by an initial value and an event that yields future values; while an event is simply a future reactive value.
  +
<haskell>
  +
data Reactive a = a `Stepper` Event a
  +
newtype Event a = Event (Future (Reactive a))
  +
</haskell>
  +
  +
This <hask>Reactive</hask> representation can be thought of a ''reactive weak head normal form'', to which arbitrary reactive expressions may be rewritten. The rewrite rules and their justification in terms of simple denotational semantics will be described in an upcoming paper.
  +
  +
Many of the operations on events and reactive values are packaged as instances of standard classes, as described below. See the module documentation for the other operations.
  +
  +
==== Instances for Event ====
  +
  +
* '''<hask>Monoid</hask>''': <hask>mempty</hask> is the event that never occurs, and <hask>e `mappend` e'</hask> is the event that combines occurrences from <hask>e</hask> and <hask>e'</hask>. (Fran's <hask>neverE</hask> and <hask>(.|.)</hask>.)
  +
* '''<hask>Functor</hask>''': <hask>fmap f e</hask> is the event that occurs whenever <hask>e</hask> occurs, and whose occurrence values come from applying <hask>f</hask> to the values from <hask>e</hask>. (Fran's <hask>(==>)</hask>.)
  +
* '''<hask>Applicative</hask>''': <hask>pure a</hask> is an event with a single occurrence, available from the beginning of time. <hask>ef <*> ex</hask> is an event whose occurrences are made from the ''product'' of the occurrences of <hask>ef</hask> and <hask>ex</hask>. For every occurrence <hask>f</hask> at time <hask>tf</hask> of <hask>ef</hask> and occurrence <hask>x</hask> at time <hask>tx</hask> of <hask>ex</hask>, <hask>ef <*> ex</hask> has an occurrence <hask>f x</hask> at time <hask>max tf tx</hask>.
  +
* '''<hask>Monad</hask>''': <hask>return a</hask> is the same as <hask>pure a</hask> (as always). In <hask>e >>= f</hask>, each occurrence of <hask>e</hask> leads, through <hask>f</hask>, to a new event. Similarly for <hask>join ee</hask>, which is somehow simpler for me to think about. The occurrences of <hask>e >>= f</hask> (or <hask>join ee</hask>) correspond to the union of the occurrences of all such events. For example, suppose we're playing Asteroids and tracking collisions. Each collision can break an asteroid into more of them, each of which has to be tracked for more collisions. Another example: A chat room has an "enter" event, whose occurrences contain new events like "speak".
  +
  +
==== Instances for Reactive ====
  +
  +
The instances for <hask>Reactive</hask> can be understood in terms of (a) a simple semantics of reactive values as functions of time, and (b) the corresponding instances for functions. The semantics is given by the function <hask>at :: Reactive a -> (Time -> a)</hask>.
  +
* '''<hask>Monoid</hask>''': a typical lifted monoid. If <hask>o</hask> is a monoid, then <hask>Reactive o</hask> is a monoid, with <hask>mempty = pure mempty</hask>, and <hask>mappend = liftA2 mappend</hask>. In other words, <hask>mempty `at` t == mempty</hask>, and <hask>(r `mappend` s) `at` t == (r `at` t) `mappend` (s `at` t).</hask>
  +
* '''<hask>Functor</hask>''': <hask>fmap f r `at` t == f (r `at` t)</hask>.
  +
* '''<hask>Applicative</hask>''': <hask>pure a `at` t == a</hask>, and <hask>(s <*> r) `at` t == (s `at` t) (r `at` t)</hask>.
  +
* '''<hask>Monad</hask>''': <hask>return a `at` t == a</hask>, and <hask>join rr `at` t == (rr `at` t) `at` t</hask>. As always, <hask>(r >>= f) == join (fmap f r)</hask>.
  +
  +
==== Continuous reactive behaviors ====
  +
  +
Although the basic <hask>Reactive</hask> type describes ''discretely''-changing values, ''continuously''-changing are defined simply by composing <hask>Reactive</hask> and a simple type functions of time (see below).
  +
<haskell>
  +
type Time = Double
  +
type ReactiveB = Reactive :. Fun Time
  +
</haskell>
  +
Because the combination of <hask>Reactive</hask> and <hask>Fun Time</hask> is wrapped in a [[TypeCompose|type composition]], we get <hask>Functor</hask> and <hask>Applicative</hask> instances for free.
   
== IVars ==
+
The exact packaging of discrete vs continuous will probably change with more experience. Perhaps I'll fold <hask>Fun Time a</hask> into the <hask>Reactive</hask> type, making a dynamic rather than static distinction.
   
== Events and reactive values ==
+
=== Data.Fun ===
   
== Constant-optimized functions ==
+
This module defines a type of functions optimized for the constant case, together with instances of <hask>Functor</hask>, <hask>Applicative</hask>, <hask>Monad</hask>, and <hask>Arrow</hask>.

Latest revision as of 10:40, 17 July 2011


Contents

[edit] 1 Abstract

Note: I have retired the old version of Reactive on darcs.haskell.org. Please use the new Reactive.


Reactive is a simple foundation for programming reactive systems functionally. Like Fran/FRP, it has a notions of (reactive) behaviors and events. Like DataDriven, Reactive has an efficient, data-driven implementation. The main difference between Reactive and DataDriven are

  • Reactive provides and builds on "functional futures", which in turn build on Concurrent Haskell threads, while DataDriven builds on continuation-based computations; and
  • The algebras of events and reactive values (called events and sources in DataDriven) are purely functional. I couldn't figure out how to accomplish that in DataDriven.
  • Reactive manages (I hope) to get the efficiency of data-driven computation with a (sort-of) demand-driven architecture. For that reason, Reactive is garbage-collector-friendly, while DataDriven depends on weak references (because GC favors demand-driven computation.)
  • Reactive elegantly and efficiently caches values.
  • Reactive uses the term "reactive values" (
    Reactive
    ), where DataDriven uses "sources" (
    Source
    ).
The inspiration for Reactive was Mike Sperber's Lula implementation of FRP. Mike used blocking threads, which I had never considered for FRP before a conversation with him at ICFP 2007. While playing with the idea, I realized that I could give a very elegant and efficient solution to caching, which DataDriven doesn't do. (For an application
f <*> a
of a varying function to a varying argument, caching remembers the latest function to apply to a new argument and the latest argument to which to apply a new function.) As with DataDriven, Reactive provides instances for
Monoid
,
Functor
,
Applicative
, and
Monad
.

Besides this wiki page, here are more ways to find out about Reactive:

Also, the paper Simply Efficient Functional Reactivity, and its blog post with discussion, describe a (not-yet-released) successor to Reactive that solves the determinacy problem mentioned below.

[edit] 2 Modules

[edit] 2.1 Data.Future

A future is a value that will become knowable only later. Primitive futures can be things like "the value of the next key you press", or "the value of LambdaPix stock at noon next Monday". The term "promise" might be more fitting.

Composition is via standard type classes:
Functor
,
Applicative
,
Monad
, and
Monoid
.
  • Monoid
    :
    mempty
    is a future that never becomes knowable.
    a `mappend` b
    is whichever of
    a
    and
    b
    is knowable first.
  • Functor
    : apply a function to a future. The result is knowable when the given future is knowable.
  • Applicative
    :
    pure
    gives value knowable since the beginning of time.
    (<*>)
    applies a future function to a future argument. Result available when both are available, i.e., it becomes knowable when the later of the two futures becomes knowable.
  • Monad:
    return
    is the same as
    pure
    (as always).
    (>>=)
    cascades futures.
    join
    resolves a future future value into a future value.
The current implementation is nondeterministic in
mappend
for futures that become knowable at the same time or nearly the same time. I want to make a deterministic implementation.

[edit] 2.1.1 Garbage collection of futures

Baker & Hewitt's 1977 paper The Incremental Garbage Collection of Processes discusses using garbage collection to prevent the useless threads from consuming resources. In particular, consider
Future
's
mappend
(sometimes called "parallel or"). Once one thread completes, the other threads are then useless, and some might consume resources forever. My current implementation kill the losing threads. Baker & Hewitt suggest instead using garbage collection. I'm stumped about how to GC non-winning threads in a race between futures ("parallel or"). The winner-kills-loser approach seems to work fine, though is potentially dangerous w.r.t locked resources. Still, the elegance of a GC-based solution appeals to me.

[edit] 2.1.2 Concurrent Haskell vs STM

Futures are implemented using Concurrent Haskell's
MVar
s. I first tried using STM and
TVar
s, simply using
orElse
to implement
mappend
for futures. However, I didn't see how to avoid nesting
atomically
, which yielded a run-time error.

[edit] 2.2 Data.SFuture

A target denotational semantics for Data.Future -- simple, precise, and deterministic, in terms of time/value pairs.

[edit] 2.3 Data.Reactive

This module defines events and reactive values. An event is stream of future values in order of availability. A reactive value is a discretly time-varying value. These two types are closely linked: a reactive value is defined by an initial value and an event that yields future values; while an event is simply a future reactive value.

data Reactive a = a `Stepper` Event a
newtype Event a = Event (Future (Reactive a))
This
Reactive
representation can be thought of a reactive weak head normal form, to which arbitrary reactive expressions may be rewritten. The rewrite rules and their justification in terms of simple denotational semantics will be described in an upcoming paper.

Many of the operations on events and reactive values are packaged as instances of standard classes, as described below. See the module documentation for the other operations.

[edit] 2.3.1 Instances for Event

  • Monoid
    :
    mempty
    is the event that never occurs, and
    e `mappend` e'
    is the event that combines occurrences from
    e
    and
    e'
    . (Fran's
    neverE
    and
    (.|.)
    .)
  • Functor
    :
    fmap f e
    is the event that occurs whenever
    e
    occurs, and whose occurrence values come from applying
    f
    to the values from
    e
    . (Fran's
    (==>)
    .)
  • Applicative
    :
    pure a
    is an event with a single occurrence, available from the beginning of time.
    ef <*> ex
    is an event whose occurrences are made from the product of the occurrences of
    ef
    and
    ex
    . For every occurrence
    f
    at time
    tf
    of
    ef
    and occurrence
    x
    at time
    tx
    of
    ex
    ,
    ef <*> ex
    has an occurrence
    f x
    at time
    max tf tx
    .
  • Monad
    :
    return a
    is the same as
    pure a
    (as always). In
    e >>= f
    , each occurrence of
    e
    leads, through
    f
    , to a new event. Similarly for
    join ee
    , which is somehow simpler for me to think about. The occurrences of
    e >>= f
    (or
    join ee
    ) correspond to the union of the occurrences of all such events. For example, suppose we're playing Asteroids and tracking collisions. Each collision can break an asteroid into more of them, each of which has to be tracked for more collisions. Another example: A chat room has an "enter" event, whose occurrences contain new events like "speak".

[edit] 2.3.2 Instances for Reactive

The instances for
Reactive
can be understood in terms of (a) a simple semantics of reactive values as functions of time, and (b) the corresponding instances for functions. The semantics is given by the function
at :: Reactive a -> (Time -> a)
.
  • Monoid
    : a typical lifted monoid. If
    o
    is a monoid, then
    Reactive o
    is a monoid, with
    mempty = pure mempty
    , and
    mappend = liftA2 mappend
    . In other words,
    mempty `at` t == mempty
    , and
    (r `mappend` s) `at` t == (r `at` t) `mappend` (s `at` t).
  • Functor
    :
    fmap f r `at` t == f (r `at` t)
    .
  • Applicative
    :
    pure a `at` t == a
    , and
    (s <*> r) `at` t == (s `at` t) (r `at` t)
    .
  • Monad
    :
    return a `at` t == a
    , and
    join rr `at` t == (rr `at` t) `at` t
    . As always,
    (r >>= f) == join (fmap f r)
    .

[edit] 2.3.3 Continuous reactive behaviors

Although the basic
Reactive
type describes discretely-changing values, continuously-changing are defined simply by composing
Reactive
and a simple type functions of time (see below).
type Time = Double
type ReactiveB = Reactive :. Fun Time
Because the combination of
Reactive
and
Fun Time
is wrapped in a type composition, we get
Functor
and
Applicative
instances for free. The exact packaging of discrete vs continuous will probably change with more experience. Perhaps I'll fold
Fun Time a
into the
Reactive
type, making a dynamic rather than static distinction.

[edit] 2.4 Data.Fun

This module defines a type of functions optimized for the constant case, together with instances of
Functor
,
Applicative
,
Monad
, and
Arrow
.