Unambiguous choice implementation

older
Re: [Haskell-cafe] Haskell-Cafe...

Bartosz Milewski

23 Jun 2012 23 Jun '12

2:54 p.m.

I'm reading Conal Elliot's paper, Push-Pull FRP. At some point he needs an unambiguous choice operator, essentially to implement select: a future that waits for one of its future arguments to fire. His implementation of unamb creates two threads racing on a shared MVar. By his own admission, this is very inefficient. My question is, is there a better implementation? -- [:Bartosz:]

Attachments:

attachment.html (text/html — 424 bytes)

Show replies by date

Heinrich Apfelmus

24 Jun 24 Jun

10:21 a.m.

Bartosz Milewski wrote:

...

I'm reading Conal Elliot's paper, Push-Pull FRP. At some point he needs an unambiguous choice operator, essentially to implement select: a future that waits for one of its future arguments to fire. His implementation of unamb creates two threads racing on a shared MVar. By his own admission, this is very inefficient. My question is, is there a better implementation?

The thing about unambiguous choice is that it goes beyond the dynamic semantics of the Haskell language. To implement it, you either need a new evaluation model built into the compiler, or you have to fake it somehow and that is likely to be inefficient. Also note that Conal's paper describes just one possible implementation of FRP. My reactive-banana library uses an implementation that doesn't require unambiguous choice at all. For a basic model, see http://hackage.haskell.org/packages/archive/reactive-banana/latest/doc/html/... The key idea is to keep all events synchronous and to reify some cases of "this event does not occur right now". Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

Bartosz Milewski

7:08 p.m.

I'm trying to understand Reactive Banana, but there isn't much documentation to go about. How is RB positioned vis a vis Elliott (and then there is the earlier Elliot and Hudak, and the later Elliot with the push implementation and type classes). Do you have a toy applet that demonstrates the use of Reactive Banana, something like Elliotts Bezier editor, http://research.microsoft.com/pubs/69665/deop-tr.pdf ? --Bartosz On Sunday, June 24, 2012 7:21:07 AM UTC-7, Heinrich Apfelmus wrote:

...

...
I'm reading Conal Elliot's paper, Push-Pull FRP. At some point he needs an unambiguous choice operator, essentially to implement select: a future

Bartosz Milewski wrote: that

...
waits for one of its future arguments to fire. His implementation of unamb creates two threads racing on a shared MVar. By his own admission, this is very inefficient. My question is, is there a better implementation?

The thing about unambiguous choice is that it goes beyond the dynamic semantics of the Haskell language. To implement it, you either need a new evaluation model built into the compiler, or you have to fake it somehow and that is likely to be inefficient.

Also note that Conal's paper describes just one possible implementation of FRP. My reactive-banana library uses an implementation that doesn't require unambiguous choice at all. For a basic model, see

http://hackage.haskell.org/packages/archive/reactive-banana/latest/doc/html/...

The key idea is to keep all events synchronous and to reify some cases of "this event does not occur right now".

Best regards, Heinrich Apfelmus

-- http://apfelmus.nfshost.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Heinrich Apfelmus

25 Jun 25 Jun

4:30 a.m.

Bartosz Milewski wrote:

...

I'm trying to understand Reactive Banana, but there isn't much documentation to go about.

I haven't written any beginner documentation yet because the API is still in flux. The homepage http://www.haskell.org/haskellwiki/Reactive-banana and Stackoverflow http://stackoverflow.com/questions/tagged/frp are great resources, though. Feel free to drop me a line if you have questions as well.

...

How is RB positioned vis a vis Elliott (and then there is the earlier Elliot and Hudak, and the later Elliot with the push implementation and type classes).

The semantics from Elliott (double 't', by the way) and reactive-banana are essentially the same, but I have taken the liberty to modernize many function names. You can pretty much directly translate Conal's examples to reactive-banana, except for those involving the switcher combinator. The approaches to implementation are very different, though. Functional reactive programming is one of the cases where you have to learn the API without understanding its implementation. (But have a look at the Reactive.Banana.Model module, which provides a simplified model implementation.)

...

Do you have a toy applet that demonstrates the use of Reactive Banana, something like Elliotts Bezier editor, http://research.microsoft.com/pubs/69665/deop-tr.pdf ?

Reactive-banana comes with a lot of examples, mentioned here: http://www.haskell.org/haskellwiki/Reactive-banana#documentation By the way, Conal's Bezier editor doesn't make much use of the switcher combinator, so you can directly translate it into reactive-banana. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

Bartosz Milewski

4:36 p.m.

Thanks, Heinrich. I looked at the examples and at the references you provided. I understand the semantic model, so I guess I'm mostly trying to understand the implementation. Conal's paper was mostly about refining data structures in order to provide better implementation. It's all beautiful up to the point where he introduces the unamb hack. How did you manage to work around this problem and implement event merging efficiently? --Bartosz On Mon, Jun 25, 2012 at 1:30 AM, Heinrich Apfelmus < apfelmus@quantentunnel.de> wrote:

...

Bartosz Milewski wrote:

...
I'm trying to understand Reactive Banana, but there isn't much documentation to go about.

I haven't written any beginner documentation yet because the API is still in flux. The homepage

http://www.haskell.org/**haskellwiki/Reactive-banana http://www.haskell.org/haskellwiki/Reactive-banana

and Stackoverflow

http://stackoverflow.com/**questions/tagged/frp http://stackoverflow.com/questions/tagged/frp

are great resources, though. Feel free to drop me a line if you have questions as well.

How is RB positioned vis a vis Elliott (and then there is the earlier

...
Elliot and Hudak, and the later Elliot with the push implementation and type classes).

The semantics from Elliott (double 't', by the way) and reactive-banana are essentially the same, but I have taken the liberty to modernize many function names. You can pretty much directly translate Conal's examples to reactive-banana, except for those involving the switcher combinator.

The approaches to implementation are very different, though. Functional reactive programming is one of the cases where you have to learn the API without understanding its implementation. (But have a look at the Reactive.Banana.Model module, which provides a simplified model implementation.)

Do you have a toy applet that demonstrates the use of Reactive Banana,

...
something like Elliotts Bezier editor, http://research.microsoft.com/** pubs/69665/deop-tr.pdfhttp://research.microsoft.com/pubs/69665/deop-tr.pdf ?

Reactive-banana comes with a lot of examples, mentioned here:

http://www.haskell.org/**haskellwiki/Reactive-banana#**documentation http://www.haskell.org/haskellwiki/Reactive-banana#documentation

By the way, Conal's Bezier editor doesn't make much use of the switcher combinator, so you can directly translate it into reactive-banana.

Best regards, Heinrich Apfelmus

-- http://apfelmus.nfshost.com

______________________________**_________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafe http://www.haskell.org/mailman/listinfo/haskell-cafe

-- You received this message because you are subscribed to the Google Groups "Haskell-cafe" group. To post to this group, send email to haskell-cafe@googlegroups.com. To unsubscribe from this group, send email to haskell-cafe+unsubscribe@** googlegroups.com . For more options, visit this group at http://groups.google.com/** group/haskell-cafe?hl=enhttp://groups.google.com/group/haskell-cafe?hl=en .

-- [:Bartosz:]

Heinrich Apfelmus

26 Jun 26 Jun

4:40 a.m.

Bartosz Milewski wrote:

...

Thanks, Heinrich. I looked at the examples and at the references you provided. I understand the semantic model, so I guess I'm mostly trying to understand the implementation.

Ok. As I mentioned, if you just want to use the library there is no need to understand the implementation.

...

Conal's paper was mostly about refining data structures in order to provide better implementation. It's all beautiful up to the point where he introduces the unamb hack. How did you manage to work around this problem and implement event merging efficiently?

Essentially, Conal implements events as type Event a = [(Time,a)] The trouble is that when merging events, this representation forces you to wait for both events. In other words, the pattern match union ((t1,x1):e1) ((t2,x2):e2) = ... needs to know the times of occurrences of both events before it can return the earlier one. The trouble is that the merge function should have returned the earlier one right away, before knowing exactly when the later one happens. The purpose of the unamb hack is circumvent that problem. Reactive-banana's very simple solution to this problem is to represent events as type Event a = [(Time, Maybe a)] and impose the additional invariant that all events in your program are "synchronized", in the sense that they indicate their occurrences at the same times^1. If they don't occur at that time, they use Nothing . Then, you can implement merge simply as union ((t1,x1):e1) ((t2,x2):e2) = -- we always have t1 = t2 (t1, combine x1 x2) : union e1 e2 where combine (Just x) Nothing = Just x -- only left occurs combine Nothing (Just y) = Just y -- only right occurs combine (Just x) (Just y) = Just x -- simultaneous occurrence combine Nothing Nothing = Nothing -- neither occurs Since the times are given globally, we can also remove them and obtain type Event a = [Maybe a] This is how Reactive.Banana.Model does it. Of course, keeping track of a lot of Nothing is something that can be optimized. The optimization to apply here is to transform the implementation into a push-driven style. I haven't published the details yet, but some design notes can be found here. http://apfelmus.nfshost.com/blog/2011/04/24-frp-push-driven-sharing.html ^1: Note that the times do not need to follow a uniform time step. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

Bartosz Milewski

5:50 p.m.

I see. So you're current implementation is not push, is it? The original pull implementation in Fran also used Maybe events, but that was considered inefficient. How is Reactive Banana better then Fran then? --Bartosz On Tue, Jun 26, 2012 at 1:40 AM, Heinrich Apfelmus < apfelmus@quantentunnel.de> wrote:

...

Bartosz Milewski wrote:

...
Thanks, Heinrich. I looked at the examples and at the references you provided. I understand the semantic model, so I guess I'm mostly trying to understand the implementation.

Ok. As I mentioned, if you just want to use the library there is no need to understand the implementation.

Conal's paper was mostly about refining data

...
structures in order to provide better implementation. It's all beautiful up to the point where he introduces the unamb hack. How did you manage to work around this problem and implement event merging efficiently?

Essentially, Conal implements events as

type Event a = [(Time,a)]

The trouble is that when merging events, this representation forces you to wait for both events. In other words, the pattern match

union ((t1,x1):e1) ((t2,x2):e2) = ...

needs to know the times of occurrences of both events before it can return the earlier one. The trouble is that the merge function should have returned the earlier one right away, before knowing exactly when the later one happens. The purpose of the unamb hack is circumvent that problem.

Reactive-banana's very simple solution to this problem is to represent events as

type Event a = [(Time, Maybe a)]

and impose the additional invariant that all events in your program are "synchronized", in the sense that they indicate their occurrences at the same times^1. If they don't occur at that time, they use Nothing . Then, you can implement merge simply as

union ((t1,x1):e1) ((t2,x2):e2) = -- we always have t1 = t2 (t1, combine x1 x2) : union e1 e2 where combine (Just x) Nothing = Just x -- only left occurs combine Nothing (Just y) = Just y -- only right occurs combine (Just x) (Just y) = Just x -- simultaneous occurrence combine Nothing Nothing = Nothing -- neither occurs

Since the times are given globally, we can also remove them and obtain

type Event a = [Maybe a]

This is how Reactive.Banana.Model does it.

Of course, keeping track of a lot of Nothing is something that can be optimized. The optimization to apply here is to transform the implementation into a push-driven style. I haven't published the details yet, but some design notes can be found here.

http://apfelmus.nfshost.com/**blog/2011/04/24-frp-push-** driven-sharing.htmlhttp://apfelmus.nfshost.com/blog/2011/04/24-frp-push-driven-sharing.html

^1: Note that the times do not need to follow a uniform time step.

Best regards, Heinrich Apfelmus

-- http://apfelmus.nfshost.com

______________________________**_________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafe http://www.haskell.org/mailman/listinfo/haskell-cafe

-- You received this message because you are subscribed to the Google Groups "Haskell-cafe" group. To post to this group, send email to haskell-cafe@googlegroups.com. To unsubscribe from this group, send email to haskell-cafe+unsubscribe@** googlegroups.com . For more options, visit this group at http://groups.google.com/** group/haskell-cafe?hl=enhttp://groups.google.com/group/haskell-cafe?hl=en .

-- [:Bartosz:]

Heinrich Apfelmus

27 Jun 27 Jun

4:44 a.m.

Bartosz Milewski wrote:

...

I see. So your current implementation is not push, is it?

Reactive-banana includes two implementations: a pull-based model implementation that specifies the semantics and a push-based implementation for actual work. So, yes, reactive-banana is push-based. Note that the qualification "push-based" is not straightforward to obtain. For instance, Elm is implementation in a style that looks push-based, but it doesn't optimize the case where no event / change happens, so it has the same efficiency as a pull-based implementation. Conal's unamb combinator may have a similar problem, but I'm not sure.

...

The original pull implementation in Fran also used Maybe events, but that was considered inefficient. How is Reactive Banana better then Fran then?

I don't know much about the implementation of Fran , but if I remember correctly, it uses the representation Behavior a = Time -> a and this introduces other efficiency problems not present in reactive-banana. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

4711

Age (days ago)

4715

Last active (days ago)

List overview

Download

7 comments

2 participants

participants (2)

Bartosz Milewski
Heinrich Apfelmus