Conal Elliott

Simply efficient functional reactivity

4th April 2008, 02:27 pm

I submitted a paper Simply efficient functional reactivity to ICFP 2008.

Abstract:

Functional reactive programming (FRP) has simple and powerful semantics, but has resisted efficient implementation. In particular, most past implementations have used demand-driven sampling, which accommodates FRP’s continuous time semantics and fits well with the nature of functional programming. Consequently, values are wastefully recomputed even when inputs don’t change, and reaction latency can be as high as the sampling period.

This paper presents a way to implement FRP that combines data- and demand-driven evaluation, in which values are recomputed only when necessary, and reactions are nearly instantaneous. The implementation is rooted in a new simple formulation of FRP and its semantics and so is easy to understand and reason about.

On the road to efficiency and simplicity, we’ll meet some old friends (monoids, functors, applicative functors, monads, morphisms, and improving values) and make some new friends (functional future values, reactive normal form, and concurrent “unambiguous choice”).

Tags: applicative functor, continuous, discrete, events, FRP, functional reactive programming, functor, future value, icfp, implementation, joinMaybes, monad, monoid, multi-threading, normal form, paper, reactive behavior, reactive value, semantics, time, type class, type class morphism, type composition | Comment (RSS) | Trackback

33 Comments

Cale Gibbard:

In your definition of ‘before’ at the top of page 4, it appears that the parameters are swapped.
5 April 2008, 12:18 am
conal:

Thanks, Cale. I’ve added an errata section to the paper’s web page.
5 April 2008, 8:15 am
anonymous:

Great paper! Small typos: On page 8, in the definition of adjustTop, the constructors should be named “Ev” resp. “Fut”, not “Event” resp. “Future”. Also, on page 3, in the semantic Monoid instance definition for Event, the “O” constructor should either not be used, or be introduced earlier.
5 April 2008, 1:10 pm
Max Bolingbroke:

Just finished reading your paper Conal: great to see that FRP is still getting some love! I did notice some minor things which may be errors: – In the newtype declation for Future, I’m don’t think that FTime should have a “t” after it – On page 6, I think it says “Applicative Behavior” where it should say “Applicative Reactive” – On page 7, I think “will have to block the” should read “will have to block until the” – Similarly on pagc 8, “do some work based partial applications” should be “do some work based upon partial applications” – The Monad instance for Events in section 7.2.2 says “instance Monad Reactive” at the top of it – On page 9 “image to display window” should probably read “image to a display window” – In the conclusion on page 12, “paper allows retains” should probably just read “paper retains”

Am I right in thinking that because of the way the Applicative instance for Reactive is defined, if we have a reactive function like “f e1 e2″ and e1 changes, e2 will be re-sampled? Does this have performance implications? I suspect that this doesn’t actually matter, but I don’t have it totally straight in my head yet.

One thing I would like to see incorporated into FRP systems is a notion of diffs, so if e.g. an underlying data structure is modified in just one place (imagine a user pasting into the middle of a text buffer) the system can use the diff to efficiently recompute outputs that depend on that data structure (e.g. just adding the length of the inserted text onto the current cursor position rather than working it out from scratch). I don’t what machinery would be required to make this work, but I feel it would involve zippers to let you recover diffs in a principled way.

A use case I have in mind for this is modelling a build system as a FRP system where the files (e.g. java source files) are what vary over time and outputs (e.g. class files) are the result of applying the “javac” function to the files. The difficulty here is that the javac compiler can avoid recomputing some things if it has the OLD class files as input. So you get something similar to this:

class_files = javac (source_files :: [JavaSource]) (class_files :: [JavaClass])

So you need some way for FRP to tie the knot by feeding back in the cached previous value or in general an actual diff.

This is pretty ill-informed speculation, as I’m sure you can see, but maybe you can recover something useful from my rambling
6 April 2008, 9:40 am
conal:

Max,

Thanks very much for catching these mistakes. I’ve updated the errata.

Am I right in thinking that because of the way the Applicative instance for Reactive is defined, if we have a reactive function like “f r1 r2″ and e1 changes, r2 will be re-sampled? […]

(I’ve changed your variable names.) I think you want to know, given f<$>r1<*>r2, whether the value of r2 will get recomputed when r1 changes). (By the way, (<$>) and (<*>) are left-associative.) No, it won’t (nor vice versa), because reactive values have an all-data, no-function representation, and so we get the usual caching property for data structures. Just like lists: the head gets computed the first time you look but reused the second time. This lovely caching property is what I was trying to get at in the end of section 7.1.2.

One thing I would like to see incorporated into FRP systems is a notion of diffs, […]

I’ve been tinkering with this idea as well. I haven’t yet seen how to make it simple, general and useful. It’ll come, I think.

A use case I have in mind for this is modelling a build system as a FRP system where the files (e.g. java source files) are what vary over time and outputs (e.g. class files) are the result of applying the “javac” function to the files.

Yes! Purely functional make is one of the applications I really want to tackle. I think we can do a much better job of correctness and efficiency than a standard build system can, and with no redundant specification (code + makefile) to boot. I have a partial prototype on the back burner.

I don’t think you’d want knot-tying exactly in your example (assuming you mean classes = javac<$>sources<*>classes), since the knot would be at each moment, while you want the new output to be influcenced by a previous output. In that case, one of the accumulator combinators (Section 12) would probably do the trick.

Better yet, I’d like to open up the structure of source code, compilers (linkers, etc), and object code and embed FRP throughout, to bring much more incrementality to compilation (etc).
6 April 2008, 12:32 pm
Tom Davies:

Hi Conal,

Is there any source code available for the concepts discussed in this paper? As a relative FP neophyte I find papers very terse and can usually understand better by looking at more comprehensive code as I read them.

Off topic, I watched on youtube the interesting tangible values talk you gave at Google. Another visual FP environment is Business Object’s ‘Gem Cutter’ (http://openquark.org/Open_Quark/Welcome.html).

It is a conventional boxes and lines model, but you can ‘burn’ one of the inputs to a function, which converts its output from a value to a function, allowing you to connect the box to a function input on another function.
7 April 2008, 1:56 pm
conal:

Hi Tom,

I haven’t released my library yet, as it’s a bit unstable at the moment, and I want to study & tune the performance. I then want to hook it up to functional GUI systems like Phooey and TV/GuiTV, as well as 2D and 3D animation, as in Fran. If you watch the Hackage What’s New feed, you’ll see these libraries appear. Or try Phooey & GuiTV now, which are both implemented on top of an earlier version of the code described in the paper (as well as wxHaskell).
7 April 2008, 2:54 pm
Conal Elliott » Blog Archive » Simplifying semantics with type class morphisms:

[…] About « Simply efficient functional reactivity […]
8 April 2008, 8:22 pm
Raoul Duke:

Re: “Yes! Purely functional make is one of the applications I really want to tackle.”

That would be very interesting to see. Coming from a completely different angle, more of a software engineering perspective, I would like to be able to use interesting properties I’d hope might be obtained from the purely functional approach.

http://therightabstractions.wikispaces.com/BSL
10 April 2008, 5:08 pm
Ryan Ingram:

Overall this is a really fun to read paper, and it seems to build in very clear steps towards a neat result. But there’s one thing that seems missing: how do you implement “compare” for future times? Do you have some sort of global “what time is it?” variable that you check to know for sure that one future won’t be filled with the same value as the other?

Did I overlook something obvious?
18 April 2008, 11:31 am
conal:

Hi Ryan. I’m glad you liked the paper. I might not be understanding your question. (<=) on future times, and on improving values in general, is described in section 10 and figure 3, using unamb, compareI, and exact. If you really want compare instead of (<=), the definition would be very similar to (<=) from section 10.
18 April 2008, 11:58 am
Ryan Ingram:

Right, I got all that. The steps I see in the paper:

1) “dumb” improving values which contain a large number of “non-occurrence” events. 2) make implementation better assuming the existence of compareI 3) ?? somehow compareI gets implemented ?? 4) Profit!

So step 3 is the bit I feel is missing. How can you implement compareI efficiently without some way to know “time X has passed! I know I won’t get filled before time X”?
18 April 2008, 3:02 pm
Ryan Ingram:

To be clear, there is one implementation of compareI in the paper, for “exactly”; but I was thinking about how to use the system for a real application, where events are generated by an external source. In such a system you would have to define something like the following:
```
    waitForNextEvent :: IO (Time, Input) -- given

    input :: IO (Event Input)
    input = do
        (t, e) <- unsafeInterleaveIO waitForNextEvent
        return $ Ev $ Fut (?, e `seq` Stepper e input)
```
But what goes in the ? above?
18 April 2008, 3:23 pm
conal:

Ryan: Now I get your question: how to implement compareI on primitive externally-based events (rather than exactly and those made by min and max). Yes, I did leave that bit out of the paper. Here’s one answer.

Let ta be the (initially unknown) value of the primitive time. Then to compare the future time to a time t, try ta `compare` t, but that tactic will hang until ta is known, possibly long after t passes. We’ll get the right answer (unless ta == infinity), but perhaps much too late. So, make a second concurrent test that waits until it can prove ta > t (without knowing ta). How can we make this last test? Create a new IVar (write-once synchronization variable), which will be filled in with ta when ta is known (if ever). Then
```
impT :: IVar T -> Improving T
impT v = Imp ta ( t -> assuming (unsetAt v t) GT `unamb`
                        (ta `compare` t))
 where
   ta = readIVar v
 
unsetAt :: IVar a -> T -> Bool
unsetAt v t = unsafePerformIO $ waitFor t >> isEmptyIVar v
```
where assuming is as defined in the paper (figure 4 and section 11). I’m treating readIVar as pure, since it can yield only one value.

I’m assuming that waitFor t waits not just until time t, but until all of external futures (occurrences of external events) at or before t to have been captured (had their times written to their respective IVars). This assumption is necessary to justify the use of unsafePerformIO and the correctness of impT.
18 April 2008, 4:39 pm
Ryan Ingram:

A simplifying assumption that seems to remove a lot of the complexity involved here:

Given b :: B a, and t :: Time, (b t) is not allowed to depend on events that occur at time > t.

Then, while evaluating b t, we can assume that any events that occur at or before t are safe to evaluate and access directly, and any event that happens after time t can be ignored.

Then you can implement future times with the following interface:
```
newtype Future t a = Fut (t -> Maybe (AddBounds t, a))
```
which takes the current time and returns Nothing if an event hasn’t happened yet, or Just (actualTime, a) if the event has happened, with the invariant that when it is evaluated, the time passed in must be at or before the current time.

Deterministic futures (like exactly) are trivial to implement with this interface, and min/max (for “merge”) also seems simple. You can set up input from external sources pretty easily as well:
```
asFuture :: IVar (AddBounds t, a) -> Future a
asFuture v = Fut $ t -> unsafePerformIO $ do
     empty <- isEmptyIVar v
     if empty         then return Nothing
         else do
             (ta, a) <- readIVar v
             if ta <= NoBounds t
                 then return (Just (ta, a))
                 else return Nothing -- event is still in the future
```
This requires a similar rule as your “waitFor” which is that all IVars for futures at time t must be filled before evaluating (b t). But this exactly corresponds to the usual imperative loop: read input, evaluate state, render output.

If I’m correct, this would allow you to go back to a simpler, single threaded execution model and avoid potential non-determinism and the need for unamb entirely.

Also, a question/comment: does this implementation of “race” work (without the extra MVar):
```
a `race` b = do
    v <- newEmptyMVar
    let run io tid = forkIO $ do
        x <- io
        putMVar v x
        killThread tid -- other thread may be blocked in putMVar here
    mdo ta <- run a tb
        tb <- run b ta
        return ()
    takeMVar v
```
I think you might still end up with double kill (takeMVar frees both threads to kill each other) but it doesn’t matter because they are both immediately exiting after the kill anyways.
18 April 2008, 5:29 pm
conal:

Hi Ryan — I’m glad to see this work is engaging your interest!

First, your simplifying assumption is indeed guaranteed (or preserved) by the semantics of the behavior constructs in the paper, so no problem there. (Even a bit stronger: b t doesn’t depend on occurrences at t.)

Second, about race, maybe so. I don’t trust my judgment about imperative concurrency.

On to idea about Future:

My main goal in this work is data-driven (event-driven) evaluation, in contrast with the previous pure FRP implementations, which are demand-driven. I believe the representation of Future you suggest would work fine and has a simple connection with the semantic model. And I don’t know how to use it in a data-driven implementation. Demand-driven implementations are simple enough that I probably wouldn’t bother introducing the Future abstraction.

If I’m correct, this would allow you to go back to a simpler, single threaded execution model and avoid potential non-determinism and the need for unamb entirely.

While reactive normal form came to me in a flash, ensuring determinism was the trickiest piece of the puzzle for me. I like the idea of finding of a simpler determinacy solution than mine. And I don’t have a compelling reason to believe that concurrency is necessary for pure, data-driven (determinate) FRP. While FRP semantics is highly concurrent, the implementation concurrency here (in unamb) doesn’t seem to be there for the semantic concurrency.
18 April 2008, 6:47 pm
Ryan Ingram:

I think I get it now. And I do think some form of concurrency is necessary for all but the trivial case; consider, for example, purely functional make where the main function is of the type
```
type Command = String -- to send to shell
make :: Event FileSystemChange -> Event Command
```
Clearly there has to be someone processing occs $ make $ getFsEvents in order to spawn commands, and also clearly there has to be someone generating the filesystem events, and those can’t be running on the same thread; occs is going to block until a new command comes in, so no filesystem events could get generated.

Now, whether that means you need concurrency in the innards, I’m not sure. But it seems likely, or at least some way of polling all the event sources in the system.

I have an idea for a more elegant implementation using slightly modified types for B and E; I’ll see if I can put it together & let you know how it turns out.

Thanks for the interesting ideas & food for thought!
18 April 2008, 9:05 pm
Ryan Ingram:

Here’s a new representation for Future that gives you the data-driven behavior you want:
```
data Future a = Fut
  { waitFor :: Time -> STM ()
  , value :: STM (Time, a)
  }
```
The main inspiration I had was that each future can live in a different universe, with its own concept of time. mappend on futures represents entwining two universes’ timelines together. Using STM’s “retry” and “orElse” combinators, we can wait for multiple universes simultaneously & efficiently in a single thread.

There’s an article on my blog that goes into more detail.
20 April 2008, 6:27 pm
conal:

Ryan: I read your post and have some questions:
- Does your Future a type have the same denotation as in my paper, namely (Time,a)? Does firstFuture have the same semantics as my mappend (picking the earlier future)?
- What use do you make of waitFor? Related: what’s the semantics of firstFuture, and what do its calls to waitFor accomplish? I see the comment “start over if something changes in the meantime”, but I don’t see how the waiting influences the returned value, so I don’t know how you could get determinate semantics. Does waitFor sometimes retry?
- What’s your implementation of fmap and (<*>) on your Future representation, and have you checked whether it re-applies functions each time the result is accessed? My first implementation used STM in a similar way, and I realized that the obvious (to me) fmap and (<*>) implementations failed to cache their values. My fix (and Jake McArthur’s–see comments on your post), used a writer thread.
22 April 2008, 2:13 pm
Ryan Ingram:

Hi Conal, hopefully I can answer your questions satisfactorily.

(1) Absolutely: that was the goal. In particular, here is the implementation of “force”:
```
type FTime t = AddBounds t
type F t a = (FTime t, a)
force :: Future t a -> F t a
force f = unsafePerformIO $ allowNestedTransactions $
             atomically $ value f
```
allowNestedTransactions is a hack I came up with to do, well, what its name says:
```
allowNestedTransactions m = do
    v <- newEmptyMVar
    forkIO (m >>= putMVar v)
    takeMVar v
```
This uses a separate thread to trick the STM runtime into allowing a nested transaction, but the behavior is exactly that of a single-threaded program; the MVar handles control flow and makes sure that the originating thread blocks until the computation on the forked thread completes. Ideally this won’t be necessary in a future implementation of STM. Of course this is only required if “force x” is used as a pure value inside another STM computation, and none of the reactive code calls force except for “occs”. But pure values should act like pure values, so something was required.

(2) Exactly; here are the requirements for a correct future: If f denotes (t0, a), then:
```
waitFor f t ~> return ()
  => forall (s <= t). waitFor f s ~> return ()
-- That is, if waitFor f t doesn't retry, then waitFor f t
--   doesn't retry for earlier t either.

waitFor f t >> maybeSTM (value f) ~> return Nothing
   => t0 > t
-- That is, if waitFor f t doesn't retry, and value f
--  does, then f is not yet available at time t.
```
Another way to look at it is to treat each future as having a universe which has its own current time. Then we have the following rules:
```
now :: Future a -> STM Time -- never retries

waitFor f t = do
    n <- now f
    if (t <= n) then return () else retry
-- In fact, I define "now" for a future as "the largest t
--   such that waitFor f t does not retry"

value f = do
    n <- now f
    if (n >= t0) -- this is the t0 from the denotation of the future
      then return (t0, a)
      else retry

now (pure x) = return maxBound
now (firstFuture f1 f2) = min <$> now f1 <*> now f2
```
So, in “firstFuture”, this code snippet:
```
        (Just (t1, v1), Nothing) -> do
            waitFor f2 t1
            return (t1, v1)
```
says “synchronize this future with f2 until at least time t1″. If (now f2) is less than t1, then this will retry and the transaction should get re-run when either (a) (now f2) >= t1, or (b) the results of maybeSTM (value f2) changes, that is, f2 resolved to a particular value.

(3) I’m sure I haven’t done this properly yet, but it should be pretty easy to solve with a TVar that holds the value of the future once it gets determined; the caching problem seems to apply more to Events (streams of futures) than futures themselves; a future will only ever return its single correct value or retry. I suppose that in the <*> case that the first future could resolve, and then we will go through and re-calculate it when the second future resolves. I’ll think about that and see if I can come up with a good solution.

Overall, STM doesn’t seem -quite- as good a fit as I originally thought; the idea of a value that becomes known through computation and then stays that way is exactly what a pure value does via laziness. I need to think about this problem some more, but it’s been a lot of fun!
22 April 2008, 5:10 pm
Ryan Ingram:

OK, now that I’ve played with this for a while I have a few real comments about the paper:

(1) You’ve lost the “edge” constructors for events:
```
risingEdge :: Behavior Bool -> Event ()
fallingEdge :: Behavior Bool -> Event ()
```
You can implement them for Reactive instead of Behavior, but it’s impossible to do so for Behavior itself. That said, maybe that’s a good thing; they can’t possibly detect the exact edge in any system that lets you define behaviors with fmap or arr. I think it’s possible to implement this less powerful operation:
```
risingEdgeAcrossTick :: Behavior Bool -> Event () -> Event ()
risingEdgeAcrossTick beh tick = ...
```
which filters the “tick” event list to only contain occurrences where the behavior changed from False to True between one tick and the next.

(2) The entire reactive system can be parametrized on the definition of Future; futures need the following operations:
```
type Future t a -- abstract, although assume Eq t, Ord t, Bounded t

-- given the semantics from the paper
instance Functor (Future t)
instance Applicative (Future t)
instance Monad (Future t)
instance Monoid (Future t a) -- mappend = firstFuture, mempty = never
instance MonadPlus (Future t) -- see Monoid

-- plus these additional two operations:
exactly :: t -> a -> Future t a
   -- force (exactly t a) = (t, a)

withTime :: Future t a -> Future t (t,a)
   -- force (withTime f) = withTimeSem (force f) where
   --    withTimeSem (t,a) = (t, (t,a))
```
29 April 2008, 10:58 am
Ryan Ingram:

I knew I forgot something…

(3) merging event streams leaks memory; consider a long-running server application of this type:
```
type Connection = (Event Char, Char -> IO ()) -- TCP
listen :: Int -> IO (Event Connection) -- listen on a TCP port
server :: Event Connection -> Event (IO ()) -- server actions
```
Somewhere inside of “server” there would be an event join which allows the server to extract data from a connection; this eventually results in an mappend between a future connection and a future character from a connection. Once a connection is closed, it can’t possibly give any more events, but the event merge listens to it forever.

This can be solved with this additional operation on futures:
```
whenNever :: Future t a -> Future t b -> Future t b
-- semantics:
-- whenNever never f = f
-- whenNever _     _ = never

mergeE :: Event a -> Event a -> Event a
mergeE (Ev e1) (Ev e2) = Ev $
    -- if e2 is "never", throw it away
    whenNever e2 e1
    -- if e1 is "never", throw it away
    `mappend` whenNever e1 e2
    -- if e1 arrives first, use it
    `mappend` fmap ((Stepper a e1') -> Stepper a $ mergeE e1' (Ev e2)) e1
    -- otherwise use e2
    `mappend` fmap ((Stepper a e2') -> Stepper a $ mergeE (Ev e1) e2') e2
```
Implementing whenNever is tricky, though. The best I’ve done so far is have an explicit representation for futures that are Never; another option is to dynamically allow a future to become “Never” although that could break the axioms of futures. The best solution, I think, is to have whenNever delay the second future to the point at which we can determine the first future is never; if it’s immediately obvious (“pure” never) we can return f directly, otherwise we may delay f’s occurrence. This doesn’t break mergeE at all, but it does complicate the semantics of whenNever.
29 April 2008, 11:12 am
conal:

Hi Ryan. Thanks for the additional comments.

(1) You’ve lost the “edge” constructors for events […] You can implement them for Reactive instead of Behavior, but it’s impossible to do so for Behavior itself.

Agreed, given that a behavior can be any (computable) function of time and the semantics of the edge operations require capturing every transition and capturing it exactly. There are some variations on the Behavior type, such as derivative bounds, that would allow catching each transition, while retaining continuous time.

I think it’s possible to implement this less powerful operation […] which filters the “tick” event list to only contain occurrences where the behavior changed from False to True between one tick and the next.

I don’t know where the idea of a “tick” could fit in FRP’s continuous-time semantics. Perhaps you’re thinking of a temporally discrete variation.

(2) The entire reactive system can be parametrized on the definition of Future; futures need the following operations: […]

I may be missing your point. Are you saying that futures are only used through the Future interface?

(3) merging event streams leaks memory […] Once a connection is closed, it can’t possibly give any more events, but the event merge listens to it forever.

Why do you expect event merge (mappend) to keep listening to an event that knowably cannot have any more occurrences? An event is represented as a future, and that future can have an explicitly infinite (MaxBound) time. (See Section 4.5 and Figure 1.) Since mappend on events works via mappend on futures, and the latter handles infinite time, I think your example would work out easily enough without a space leak, assuming that the event reflects the closed connection with an infinite-time future (analogous to a nil at the end of a list).
29 April 2008, 11:37 am
Ryan Ingram:

For (2), yes. I found it very interesting that given the interface to future could be that minimal (four small typeclasses & two or three additional operations) and all of the “definition”-side of behavior/reactive/event could be specified in terms of that minimal interface.

Of course you need to plumb into the implementation details when you are writing the interpretation functions (occs/sinkE/sinkR), unless you take waitFor and force as primitive as well, which severely constrains the design of Future. But most client code can absolutely ignore that and use the behavior/reactive/event abstraction.

(3) From your definition of mappend on events:
```
u `mergeu` v = (inFutR (`merge` v) <$> u)
           <+> (inFutR (u `merge`) <$> v)
   where
       inFutR f (r `Stepper` Ev u0) = r `Stepper` Ev (f u0)
```
Consider the case where v = never. The rhs of <+> goes away, but we still call “merge” in the lhs, and pass v again. So any storage held by v cannot be reclaimed, and there’s also a time leak as <+> keeps getting called needlessly.

The more merges that happen, the worse the leak gets.
29 April 2008, 2:23 pm
conal:

Ryan: I see what you mean, now. I think the following two special cases fix this problem, inserted before the one in the paper (quoted in your most recent comment):
```
Future (Max MaxBound,_) `mergeu` v = v
u `mergeu` Future (Max MaxBound,_) = u
```
I just added these lines to the implementation. Thanks for pointing out the leak.
29 April 2008, 3:29 pm
Josef Svenningsson:

I have a very small question about the race function defined at the end of the paper. Is the lock MVar really necessary? I think not but maybe I’m just missing something. In the run function couldn’t you just write to the v MVar first and then kill the other thread. Then double kill will be prevented because the other thread will block when trying to assing to the MVar and will never reach the killThread before being killed himself.
```
a `race` b =
  do  v <- newEmptyMVar
      let run io tid = forkIO $ do x <- io
                                   putMVar v x
                                   killThread tid
      mdo ta <- run a tb
          tb <- run b ta
      readMVar v
```
Well, maybe this issue is moot anyway since you and Ryan Ingram seem to have come up with some nicer way of doing this.
30 April 2008, 7:57 am
conal:

Hi Josef,

I started out with that simpler definition. Here’s what I think is a problem with it: Concurrent Haskell has no atomic operation for reading an MVar. The readMVar action instead does a takeMVar followed by a putMVar. After the reader’s takeMVar and before its putMVar, the race-loser could unblock and do its putMVar. This second putMVar to the same MVar would break the pure semantics and would cause the reader to block instead of completing its readMVar. I hadn’t considered this possibility until Ivan Tomac pointed it out.
30 April 2008, 11:13 am
Jake McArthur:

I discovered an error on page 8. Your definition of joinR:
```
joinR :: Reactive (Reactive a) -> Reactive a
joinR :: ((a `Stepper` Ev ur) `Stepper` Ev urr) =
         a `Stepper` Ev u
     where u = ((`switcher` e')  ur) `mappend` (join  urr)
```
Before completing the definition of u, you say that it is the first of either (`switcher` Ev ur) <$> ur or join urr.

In actual definition of u in your paper, you use e', which was never bound. I believe e' is supposed to be Ev urr. Before completing the definition of u, your intermediate code ((`switcher` Ev ur) <$> ur) uses neither e' nor Ev urr, but uses Ev ur instead.
7 May 2008, 8:32 am

conal:

Thanks, Jake! There were two mistakes. Errata and paper source updated. Here’s the correct code:

joinR ((a `Stepper` Ev ur) `Stepper` Ev urr) =
  a `stepper` Ev u
 where
   u = ((`switcher` Ev urr) <$> ur) `mappend` (join <$> urr)

7 May 2008, 9:23 am

Max:

So, when are you going to release the library that goes with this paper? I’m really looking forward to playing around with this stuff!
30 August 2008, 1:37 am
Conal Elliott » Blog Archive » Why classic FRP does not fit interactive behavior:

[…] The Arrow style required multiple behaviors to be bunched up into one. That combination appears to thwart efficient, change-driven evaluation, which was the problem I tackled in Simply efficient functional reactivity. […]
9 December 2008, 10:45 pm
ivan:

Could you post a changelog between the most recent version of this paper and the new push-pull functional reactive programming paper, please?
30 June 2009, 7:57 am
conal:

Hi Ivan. I don’t have easy access to the detailed differences. There was very little change (lots of revision already). Mainly:
- Simplified the definition of joinE in 7.2.2
- Simplified (a bit) the unamb “reference implementation” in Figure 4, noting that it is not an efficient implementation.
30 June 2009, 10:52 am

Simply efficient functional reactivity

33 Comments

Cale Gibbard:

conal:

anonymous:

Max Bolingbroke:

conal:

Tom Davies:

conal:

Conal Elliott » Blog Archive » Simplifying semantics with type class morphisms:

Raoul Duke:

Ryan Ingram:

conal:

Ryan Ingram:

Ryan Ingram:

conal:

Ryan Ingram:

conal:

Ryan Ingram:

Ryan Ingram:

conal:

Ryan Ingram:

Ryan Ingram:

Ryan Ingram:

conal:

Ryan Ingram:

conal:

Josef Svenningsson:

conal:

Jake McArthur:

conal:

Max:

Conal Elliott » Blog Archive » Why classic FRP does not fit interactive behavior:

ivan:

conal:

Leave a comment

Recent Posts

Recent Comments

Archives

Tags

Tags

Meta