Lambda the Ultimate

Hi Sean,

1. ...

2. I think this view makes sense for synchronous dataflow (i.e., sample values always exists at each discrete timestep), so questions of frequency don't arise by fiat. In this case, many composition operators (such as zip and append) are always well-defined. There's also a good deal of work on the clock calculus to handle the more general cases you describe -- however, I am mostly unfamiliar with it.

In addition to timing, imperative streams have the usual aliasing issues you have to watch out for (e.g., you can't zip an iterator with itself to produce a sequence of tuples). IMO, these bugs are possible because the denotational semantics of dataflow form traced monoidal categories, and monoidal categories imply a linear type discipline would be natural.

3. This is where this style of design really shines, IMO. On top of the basic infrastructure of event streams, we can implement event transducers which we can use to convert streams of low-level events into streams of high-level events. Furthermore, we can (a) give programmers an FRP interface to program event transducers with the standard equational semantics, but (b) still use the efficient imperative implementation. I've got an upcoming TLDI workshop paper that's about this.

This doesn't give you a complete GUI story, IMO, because this style tells us how to do event handling, but there's still a question about how to present the widget tree/DOM/etc to the programmer, while retaining both a simple equational theory and the usual efficient implementation techniques.

As for 2, I sort of understand the semantics behind the composition operators, they just don't seem to be very useful; e.g., why would I ever want to zip up mouse events? As for 3, transducers don't seem to really help with practical UI programming tasks that I can think of, can the move from the micro-example stage? Maybe a couple of common UI challenge problems are in order. Both are common variations of basic mouse drag:

1. Warmup: in WPF, you would never ever do drag without capturing the mouse on the target UI element--otherwise weird things happen like missing move and up events. On mouse down, you have to capture the mouse which you then release on mouse up. Now, how is:
   
var mouseDragPoints = from md in e.GetMouseDown()
let startpos=md.EventArgs.GetPosition(e)
from mm in e.GetMouseMove().Until(e.GetMouseUp())
select new {
StartPos = startpos,
CurrentPos = mm.EventArgs.GetPosition(e), };

   elegantly fixed to correctly do mouse capture? In other words, on that mouse up I need to do capture, and on mouse down I need to do uncapture. I guess we could cheat by implementing capture behavior outside of this definition (just subscribe directly to MouseDown and MouseUp), but capture is often intertwined with drag, and special drag conditions might cause different capture behavior.

2. Advanced: mouse input often drives a state machine. On mouse down, you go to a ready state, then after say 400 milliseconds, you automatically go to the mouse hold state and initiate hold behavior until mouse up. If there is a mouse up before 400 milliseconds, you emit a click event, while if the mouse moves before 400 milliseconds or a mouse up, you go to the drag state and initiate drag behavior until mouse up. In all three cases, capture is maintained from mouse down until mouse up.

I've studied the event stream problem when I was doing my SuperGlue work. I found that representing an event stream as a discrete FRP signal (Fran-style) doesn't really help out with real UI programming that much because the abstraction doesn't match problem space; e.g., we need state machines rather than high-level event streams. Anyways, looking at Rx and its examples has gotten me to think about these problems again, otherwise I think this project is pretty cool!

In the C# case, there's nothing stopping you from building a state machine into the subscription expression; there are the hints of one already in the sample code (the let captures the state of the stream at the moment of the MouseDown event). Since mouse capture is a side effect, you have to treat it as such; you're modifying the state of the monad holding the mouse events.

I'll take a stab:

1. Careful, IObservable isn't intrinsically an "event stream" (and IEnumerable isn't intrinsically an "element stream"), though it's a natural expression for it (and Rx has a great deal of support for wrapping .NET events in IObservable). They're both just "streams", with IObservable's semantics using "push" (and therfore requiring processing in reactive style) and IEnumerable's semantics using "pull". At that level, I can imagine IObservable being seen as an overly-complex way of handling LINQ's .ForEach(). The benefit of IObservable's inversion of control is simply that the reactive style lets control flow be implicitly directed by the elements in the stream, rather than having explicit "consumers" and "producers" who must stay coordinated to avoid stalls. "Events" and "elements" mean nothing to IObservable and IEnumerable (in early work, before IObservable existed, IEnumerable's semantics were stretched to cover events, and it worked -- albeit a bit awkwardly, since it's harder to write in reactive style from that "angle")
2. Collections aren't intrinsically composable, either, except via explicitly-stated behaviours. IEnumerable works perfectly well with infinite sequences (since it's how LINQ supports lazy evaluation of streams). Even worse, IEnumerable has always enabled arbitrary computation between "elements", which means that the issue of "synchronisation" between IEnumerable streams has already been a problem. Since consumers determine the semantics of composition, though, it seems nobody has really noticed; the naïve view that IEnumerables are fully-materialised collections of elements is usually correct enough, and composition usually works intuitively. Usually.
3. I think others have covered this better than I could here, but I'll point out that the "canonical" example code for Rx is in fact an implementation of drag-and-drop.

I'm wondering if Rx is really FRP in the style of Yampa, FrTime, or Flapjax. The basic premise, that IObservable is the dual of IEnumerable, is new and not something you'd see in an FRP system. A couple of other comments:

One thing to note about FrTime is that Greg was careful to only support implicit lifting of computations over behaviors -- there are *too many* valid interpretations of lifting over events.

SuperGlue followed the same approach, but went even further to separate the two concepts completely (behaviors and events). Its always preferable to stay in the continuous declarative world as possible, since the event world essentially requires hooking specific points in time, which I would say by definition is not declarative. The only way to do any thing with events is to process them into behaviors (but I should go back and reread my dissertation).

State machines....My answer then was: if you want a state machine, then don't use something else! However, it's nice to see how they fit together.

This is a reasonable answer. I seem to spend most of my time when processing events writing state machines...so what I need are state machines. Event streams can drive state transitions, and entering/exiting a state can also act like an event stream, then maybe we could have a nice abstraction for composing state machines, which surely has been done before. However, I'm wondering if state machines are an enhancement to FRP or orthogonal?

I see that Zhanyong Wan's work on Real-Time FRP has been cited on LtU before, but I just found a paper on Event-Driven FRP that you might find useful.

Sean might be referring to these, but I couldn't understand Neel's response enough to figure out if that's what was meant (but I don't think so -- it seems to be on the side of viewing all such situations as bugs).

As a matter of taste, I strongly dislike operations with nondeterministic semantics. However, I do think nondeterminism is occasionally essential, so I can't in good conscience call it a "bug".

In your example, I would expect the types to go something like this (using A ~> B to mean a stream transducer from a stream of As to a stream of Bs).

   mouseUp   : ui_event ~> bool
   mouseDown : ui_event ~> bool
   count     : bool ~> int
   lift      : ('a -> 'b) -> ('a ~> 'b) 
   (+)       : int * int -> int
   (**)      : ('a ~> 'b) -> ('a ~> 'c) -> ('a ~> 'b * 'c)
   (|)       : ('a ~> 'b) -> ('b ~> 'c) -> ('a ~> 'c)

with your example getting written like

   ((mouseUp | count) ** (mouseDown | count)) | (lift (+)) 
   : ui_event ~> int

Note that the type here is not a stream; it's a stream transducer. So this is in the style of "arrowized FRP", where streams are not explicitly manipulated by user code -- the clients write stream transducers, which are then fitted into to the program's event loop. (So that's why I said "written like" and not "lifted to", since I don't know if you can always do an automatic lifting into an arrowized style.)

I think this style is especially well-suited for imperative reactive implementations, because it means that user code can't introduce aliasing bugs via sampling an imperative stream twice in the same time step (and thereby changing some state more than you should).

It's also nice for accomodating state machines, since state machines are a form of stream transducer themselves (e.g., Mealy and Moore machines). However, since state machines are a limited subclass of stream transducers, they support extra operations which aren't well-defined in general for all stream transducers. (For example, you can support introspection on state machines, whereas you can't for arbitrary code.)

I think we're in agreement for the most part. I alluded to Greg's work as showing automatic lifting has a clear meaning for operations over behaviors and used my example for showing there are too many sensible ways to lift for their dual of event streams (e.g., one rewrite your rewrite to use ** and lift). I don't think the problem of a case of nondeterminism but ambiguity: there are many seemingly reasonable interpretations to evaluate such typically rejected programs, and while we could pick a deterministic strategy for which to use, I don't think that'd be intuitive. I have similar feelings about several attempts to make 'deterministic' languages: the formalism won't sufficiently match the human perception. Supporting that exact code sample, with a deterministic or non-deterministic interpretation, is wrong.

Further... I'm not sure transducers are the best way to think about FRP unless they're first-class, at which point I think they might even become a universal model of computation. (... Arrows? ;-)) They're a good way to explain synchrony, however. Similarly, a lot of the FRP I enjoy has funny operators like "delay" that don't quite fit this model, especially when it's overloaded with a more stringent notion of synchronization (e.g., Edward Lee's definition of Synchronous Data Flow / SDF).

Finally... I alluded to this a bit before: I've seen many areas of FRP that, under traditional embeddings and/or semantics, are rejected (e.g., the implementations lead to feedback loops) or are not even syntactically expressible, but this is due to implementations dictating semantics. My example of lifting '+' to event streams *was not* intended to be an example of this (and is almost a counter-example!).

You can have multiple ways to lift functions of more than 1 argument over streams.

I think I'm a bit lost -- how is IEnumerable not pull? IEnumerable isn't a collection (and it's not list), although collections can certainly be seen as IEnumerables (that is, one can certainly apply pull semantics to a collection of elements).

I had a related misunderstanding in understanding Rx. I just assumed IEnumerable was always going to represent a collection of finite/determined elements, but this isn't the case, an IEnumerable could represent an unbounded buffer or stream that blocks when you try to pull the next element in. But then IEnumerable is just an interface, and blocking/laziness/pull has always been a part of the interface, even if these features are rarely used in many application domains (e.g., UI programming).

If I accept IEnumerable has basically being sync pull (and therefore block), then I definitely accept IObservable as being async push. Its just that...I've never used IEnumerable for block/pulling before in UI programming, where its much easier to use Dispatcher.Invoke for sync calls and Dispatcher.BeginInvoke for async calls.

Why must the pull be blocking? Or you mean locally, just on whoever needs the result of the pull?

Agreed about not writing pull-based code very much for such programs, but, then again, I think mostly about how to implement browsers, GUI, and rich media apps. That doesn't mean pull isn't useful for other places C# is / could be used.

I think I'm a bit lost -- how is IEnumerable not pull? IEnumerable isn't a collection (and it's not list),

I was trying to figure that out. So IEnumerable is 'pullable', so really a generator interface. Thanks.

although collections can certainly be seen as IEnumerables (that is, one can certainly apply pull semantics to a collection of elements).

I agree, just as you can imagine converting a list to a stream (which I wrote), you can convert a list to a bounded generator of items.

My understanding now that is that Rx uses LINQ as a common basis for manipulating push/pull/flat data, where comprehensions may be used over any data type. Flat data (what SQL normally operators over), generators (pullable IEnumerables), and streams (pushing IObservables) can be manipulated by them. My comments like 'push + pull = push' is about when we combine these different types -- which is what the Ptolemey environment tried to address.

However... in Rx/LINQ's attempt to unify these notions, I suspect something was lost. The comprehension language seems weak: I don't know if there's an analogue to operators like 'switch', the F in FRP -- what happens when we have an IEnumerable of IEnumerables or IObservables? For that matter -- what if something is both IEnumerable and IObservable? Finally, the R part of FRP has a lot to do with glitch-freedom; I suspect the use of LINQ's comprehensions makes it a non-issue by not supporting desirable operators that'd lead to glitches if done incorrectly.

Hopefully that makes more sense.

Switch is implemented as monadic bind (called SelectMany in LINQ). Can you give an example of what you mean by glitches?

Edit: I was wrong. SelectMany isn't like Switch. I created a simple toy lib in F# where Switch *is* implemented as monadic bind:

http://fsharpcells.codeplex.com/

Bind is implemented in a very simple way:

member b.Bind(c,f) = flatten (map f c)

Map maps a function over a stream and flatten flattens a stream of streams.

Flatten is implemented like this:

let flatten (nestedC : Cell) : Cell = 
    let flatC = new Cell()
    let handler = new Handler(fun s a -> flatC.Set(a))
    let oldC = ref (new Cell())
    (nestedC :> IEvent).Add(
        fun newC -> (!oldC :> IEvent).RemoveHandler(handler)
                    (newC :> IEvent).AddHandler(handler)
                    oldC := newC)
    flatC

Is this what you mean by switch? Flatten listens to a stream of streams and forwards the values of the most recent stream to the output stream.

Is this what you mean by switch?

Yes. There are subtleties with handling of old streams that might not be addressed -- the old stream should be collectable. Alos, the semantics of this collection if the old-stream has side-effects is unclear for embeddings that support them.

I don't know the relationship of this library to LINQ however. It looks like normal dataflow/binding/frp to me (with more of an emphasis on cells?).

Can you give an example of what you mean by glitches?

See 3.2 of "Embedding Dynamic Dataflow in a Call-by-Value Language". Similarly, how if-statements are handled. The GC and 'turning-off' off old streams in the switch above is related.

I'm far out of my depth here (as is usual for me on LtU), but based on the paper you cite, I think what you're looking for in Rx for glitch-prevention might be .Let(); that is, a side-effect-free subcription binder.

I can't find the documentation for Rx (the devlabs site points to the blog which points to the devlabs site..). So not sure.

I just looked, and apparently the documentation isn't online at the moment; it's included in the library package installers, though.

That is a very interesting paper.

Your flatten is Rx's IObservable<IObservable<T>>.Switch(), I believe.

... so I guess IObservable is a funny name for 'Event' in FRP. So, yes, Rx is Erik Meiejer's embedding of FRP into LINQ. There seem to be unclear nuances (e.g., glitch handling) so he gave the abstraction a slightly different name. Some reason I thought there was something bigger going on..

The 'dual' is push vs pull terms except with weird terminology. There is definitely a practical breakthrough, FRP for the C# crowd, and, in some senses, a sweet embedding of these different models.

I think that was the point: LINQ is usually seen (even by those who use it most) as "just a query mechanism". It's really a way to embed functional programming in .NET, and subsume traditional database-style querying in the process. Rx is just extending that work to enable FRP, but in doing so, map event processing back into those same DB-style queries (if you so desire).

"Programming with Rectangles, Triangles, and Circles" is what set all this off, after all. We're trying to get them all unified someday!

Funny -- my interpretation of LINQ was that it was meant to revisit System R-era assumptions about how to mix database and program logic. The functional stuff, in theory, was just a matter of time due to being a CLR language (see F#) and a rethinking of Java (.. which is also getting closures) and thus relegating it to LINQ would be awkward. Perhaps this interpretation is just due to the other stuff I was reading at the time :)

Anyways, continuing under this perspective, Rx is interesting not for the functional capabilities but for more flexible data language capabilities (where we now have data = collections, generators, and streams). We may claim "code = data", but there are pragmatics involved.

I think you have the functional stuff backwards. The CLR "grew" the necessary support for functional out of the drive to support LINQ; the database story for LINQ was the Trojan Horse to make it palatable.

In any case, I agree that Rx is interesting not simply because it's an implementation of FRP, but because it's an implementation built directly on the same expression mechanism that drives LINQ. That immediately "glues" it to all the other ways LINQ is expressed, such as the parallel extensions and LINQ-To-Expressions (the code-manipulation mechanism in LINQ).

i kinda worry that that approach lead to more painful syntax and semantics than if they'd just been able to admit up front that fp doesn't suck?

I'm not sure it's a matter of "admitting" that FP "doesn't suck" -- I'm not aware that anyone was saying at the time that it did, let alone holding it as an official position.

And yes, it does lead to syntax and semantics tangles, occasionally. On the other hand, it's easier to get a large crowd of people to do something slightly painful but somewhat familiar than it is to get them to do something less painful but much less familiar. And Microsoft has always tried to reach the largest population of programmers it could.

believe me, (at least some) people said fp sucked. :-) (note that i'm not talking about MSR, and i'm glad to see MSR's enlightened perspective not being squelched, quite the contrary, to my surprise and relief.)

You have to be careful of the .NET model for iterators and yielding control in the presence of multiple threads... that was a learning gotcha for me with .NET 2.0.