DataDriven
From HaskellWiki
Contents |
1 Abstract
I recommend Reactive rather than DataDriven. I wasn't able to get DataDriven's interface to be purely functional (Warning: The Haddock docs are not ready yet. I'm trying to get a working haddock 2.0 running (on my windows machine).
DataDriven is a library for functional events and time-varying values ("sources"). The ideas and interface come mainly from functional reactive programming (FRP). Most FRP implementations I'm aware of have a demand-driven implementation, while the implementation of DataDriven is data-driven (surprise). This library is a resurrection of some ideas from an old, incomplete Fran reimplementation that also became the basis of Meurig Sage's FranTk. This time around, I've been particularly interested in using standard classes as much as possible, most centrally <div class="inline-code">Besides this wiki page, here are more ways to find out about DataDriven.
- Read the Haddock docs (with source code, additional examples, and Comment/Talk links).
- Get the code repository: darcs get http://darcs.haskell.org/packages/DataDriven, or
- Grab a distribution tarball.
- See the version history.
- See the use of events and sources in Phooey and Eros.
Please leave comments at the Talk page.
2 Events
2.1 Background
The heart of the library is a notion of functional, composable events, with a data-driven implementation. Most of the ideas and vocabulary are borrowed from Fran, when Fran's events came to mean multiple occurrences (see Declarative Event-Oriented Programming, rather than the initial ICFP '97 publication). As in Fran, you can think of an event as a stream of "occurrences", each of which has a time and a value. The implementation, however, is radically different from Fran's, being data-driven rather than demand-driven. And in some cases, the functions are not pure. There are also several event-related functions, to create time-varying values.
2.2 A first look at the interface
Some of the useful event operations come through standard classes.
- :Functoris the event that occurs wheneverfmap f eoccurs, but whose occurrence values come from applyingeto the values fromf. (Fran'se.)(==>)
- :Monoidis the event that never occurs, andmemptyis the event that combines occurrences frome `mappend` e'ande. (Fran'se'andneverE.)(.|.)
- :Monadis an event with a single occurrence. This one doesn't quite fit the original semantics, as the occurrence is delivered immediately on "listening" to an event (discussed later). Inreturn a, each occurrence ofe >>= fleads, throughe, to a new event. Similarly forf, which is somehow simpler for me to think about. The occurrences ofjoin ee(ore >>= f) 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".join ee
As a simple example, the following function transforms and combines two events:
show2 :: (Show a, Show b) => Event a -> Event b -> Event String show2 ea eb = showE ea `mappend` showE eb where showE e = fmap show e
2.3 Events as continuations
Thenewtype Cont o a = Cont { runCont :: (a -> o) -> o }
type Event = Cont (IO ())
- Subscribing tolhas no effect, since thememptyis guaranteed never to occur.mempty
- Subscribing tolsubscribesea `mappend` ebto each oflandea.eb
- Subscribing tolsubscribesfmap f etol . f.e
- Subscribing tolsubscribes tojoin ea listener that subscribes to every event generated bye. (Similarly fore.)e >>= f == join (fmap f e)
3 Sources
Sources are time-varying values, akin to Fran's "behaviors". They are built up mainly from constant values and application (via the3.1 Composing Sources
Like events, sources have a more general, and surprisingly simple, form:
type SourceG change m = ((,) change) `O` m
\begin{code} type SourceG' change m a = (change, m a) \end{code}
One of the delightful properties of functors and of applicative functors is that they compose. That is, two functors compose to a functor and two AFs compose to form an AF. For any monoidtype SourceC o m = SourceG (Cont (m o) ()) m
Still more specifically
type Source = SourceC () IO
3.2 Sources and events
As an example of event-based sources, the following function makes a source with an initial value and changing at every occurrence of an event. The resulting source remembers the event's most recent occurrence value.
mkStepper :: a -> Event a -> IO (Source a)
mkAccumS :: a -> Event (a -> a) -> IO (Source a)
snapshot :: Event a -> Source b -> Event (a,b)
4 Ephemeral values
4.1 GC favors demand-driven computation
The purpose of garbage collection is to keep services alive as long as they are useful to clients and then free up the services' computational resources (effort and memory). Conventional garbage collection works very well for demand-driven (pull-based) computation, but not for data-driven (push-based) computation.
Consider a piece of information supplied by a service and used by a client. In a demand-driven scenario, the client has a pointer to the service and uses that pointer to get more of the information. The client keeps the serice alive. When the client get GC'd, its pointer to the service goes away. If there are no more pointers to the service, then it will also get GC'd. Both the computational effort and the memory are freed up for other uses. GC did its job.
The situation is reversed for data-driven computation. Here, the service pushes information to the client, so the service has a pointer to the client. This pointer means that the service keeps the client alive and keeps computing even when the client is no longer of any use. GC fails to satisfy its purpose.
4.2 Caching and weak pointers
Various forms of caching have this same problem. Suppose we use a hash table to memoize an expensive function. Even though the hash table is in service to function's arguments, the table's key/value entries keep the key values (function arguments) from ever getting reclaimed. Ideally, the situation would be reversed: the key would keep its table entry alive, and when the key was GC'd, they entry would shortly follow. Unfortunately, the direction of pointers, from entry to key, means that the entries keep the values alive, wasting space and slowing down search for useful entries.
The classic solution to this problem is to use "weak" pointers, i.e., pointers that the GC disregards in its decision about whether to retain a previously allocated object. For more discussion of these issues, see the <div class="inline-code">4.3 Ephemeral listener
What does all this have to events and sources? Recall that an event is simply a means of registering a "listener" (continuation) to be invoked on every occurrence. The event must have some kind of reference to the listener in order to invoke it. It must not keep the listener alive, however, since the event is the service and the listener is the client. The solution is for events to hold their clients weakly, i.e., point to them via weak references. Once a listener's strong pointers all disappear, the GC nulls out ("tombstones") the event's weak pointer. The next time the event occurs, it finds that it no longer has a live pointer, so it stops notifying the listener.
One of the (currently four) functions inephemeral :: (WeakM m, Monoid o) => o -> m o