Taking Back Control (Flow) of Reactive Programming

A short position paper that tries to motivate managed time by contrasting it with data flow approaches; to be presented at SPLASH's REBLS workshop; abstract:

Event-driven programming avoids wasting user and CPU time, but is difficult to perform since program control flow is necessarily inverted and twisted. To make reactive programming easier, many advocate burying control flow within abstractions that are composed via data flow instead. This might be a mistake: data-flow has issues with expressiveness and usability that might not pan out. Instead, control flow could be re-invented to hide the adverse affects of CPU time while preserving expressiveness and directness

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

edit

'must "switched" in a way'

should probably be

'must be "switched" in a way'

Thanks. Looks like I need to

Thanks. Looks like I need to do a grammar pass :p

I'd say that traditional FRP

I'd say that traditional FRP architectures and immediate mode fit extremely well together, since they are both essentially synchronous programming models. (In fact, there's a theorem that any transducer definable in FRP is equivalent to a state machine, and vice-versa.)

The traditional FRP programming model has not fit gracefully into event-based architectures, precisely because the point of event-based programming is that different event streams are not necessarily synchronized -- IMO, this is the fundamental reason why FRP-based GUI toolkits are thin on the ground.

However, the true missing link is a model that puts immediate and retained mode APIs coherently together. You want to avoid the overhead of a retained mode architecture if the display changes frequently (e.g., in a video game), but retained mode really saves work if it changes infrequently (e.g., in a text editor), and you want to present an API that lets the programmer do both without abstraction inversions.

You want to avoid the

You want to avoid the overhead of a retained mode architecture if the display changes frequently (e.g., in a video game), but retained mode really saves work if it changes infrequently (e.g., in a text editor), and you want to present an API that lets the programmer do both without abstraction inversions.

That would be ideal. Something like Two for the Price of One seems like a nice balance with a pseudo-immediate mode interface.

Still, even immediate mode alone isn't too bad for the slow update case. You're basically just performing a bunch of pointer comparisons. With some internal cachine, you also could dynamically throttle the refresh rate as a function of the incoming event frequency.

retained/immediate

the true missing link is a model that puts immediate and retained mode APIs coherently together

I think that this could be achieved very straight forwardly: You can have a retained mode element that represents an immediate mode procedure, and an immediate mode procedure that draws a retained element.

If you look at the IMGUI effort, you'll see a very functional approach to UIs (explicit identities, external state) implemented with an effectual traversal. Meanwhile, the internals are very similar to React.js, in which you're returning "the next frame" value tree from a pure function. The two models rely on common insights in to the nature of UI state, and share implementation strategies accordingly.

I think that having the two together could be very powerful, since some things fit one model or the other better. For example Bret Victor's Drawing Dynamic Visualizations records user inputs to capture imperative drawing procedures. By contrast, drawing a menu bar may be much more declarative.

It's also worth mentioning that Microsoft's WPF covers all the basis, but at a great and unnecessary increase in API surface area. For example, there are retained and immediate representations of rectangles:

(to say nothing of the other structures from the GDI libraries in System.Drawing)

You can host an immediate mode drawing in a retained context with DrawingVisual. I assume the other way works somehow to by capturing the "visual tree" that comes out of the expanded retained "logical tree".

I'd rather have a single Rectangle value type for use in both immediate and retained contexts.

But ideally, you'd only have one "Rectangle" value type, one "Drawing" value type to describe a procedure, and one "DrawElement" operation for those procedures. Then adding a new type of thing would have 1/3rd the linear cost in defining and implementing immediate and retained renderings.

I believe IMGUI simply

I believe IMGUI simply redraws the entire UI on a change; its only optimization is not redrawing when no events being listened to come in. Immediate mode APIs fall down by their complete inability to encapsulate UI state (like slider values in the paper), which was a flaw that we unfortunately did not address in our PLDI paper.

I do all my work in WPF, but have basically blown off most of its retained dependency property model for my own stuff. Not everything is available in the immediate mode API, oddly enough, and some things are quite difficult...but I have a managed time system and gosh darn, I'm going to use it.

Rect is not really a rectangle, but a point + a size; Rectangle is a shape with dependency properties and all that, and even then it has little relation to Rect.

Also, even DrawingContext in WPF is deceptively only partially immediate: all operations are recorded on an on-render call, and some of those operations can be animated via a clock (so you can do a blinking cursor and such). In general, pure immediate-mode programming is impossible to do in WPF because the rendering thread is completely off limits (though what they provide is good enough for me).

caching and encapsulation

its only optimization is not redrawing when no events being listened to come in

Only because it comes from games and drawing is cheap if you're already pumping the screen 60fps. It's simply not worth the engineering effort. You've got to think like a game dev. If a particular UI element is expensive to draw, you immediate-mode render it to a texture and stick a pointer to that texture in the global state. Then draw that. If it's not null on the next frame, use the cached texture. Poof: retained mode optimizations! No graphics engineer would think twice about doing that in a handful of lines of code.

Immediate mode APIs fall down by their complete inability to encapsulate UI state (like slider values in the paper)

This of course is not a limitation of the model, but of the typical implementations. However, I view React.js as an immediate mode renderer with a retained mode interface. It does manage to encapsulate component state using path structured IDs that are opaque to the user (as I've described elsewhere). There's no reason you couldn't do the same in the context of a C++ game IMGUI style API. In fact, I believe Unity's UI system does exactly that.

even DrawingContext in WPF is deceptively only partially immediate

I'm aware of that, but my previous comment was already running long :-) Anyway, I think it strengthens the argument that immediate and retained are not at odds, but rather complementary.

Only because it comes from

Only because it comes from games and drawing is cheap if you're already pumping the screen 60fps. It's simply not worth the engineering effort.

Yep. However, it does limit how immediate mode APIs can be used, and increases complexity when you need to start caching things like that.

It does manage to encapsulate component state using path structured IDs that are opaque to the user (as I've described elsewhere).

Sure, this is of course how I handle the problem in Glitch.

Anyway, I think it strengthens the argument that immediate and retained are not at odds, but rather complementary.

As described in the paper, I think we can get the benefits of both with a new programming model.

Bitsquid has a dual-mode gui

Bitsquid has a dual-mode gui that seems fairly simple, although they don't explain how they handle storing/querying the state of a UI elem.

http://bitsquid.blogspot.com/2010/08/bitsquids-dual-mode-guis.html

One Bit Review: 1

I'm a big fan of this line of work, Sean. It aligns very closely with some stuff I've been pursuing in my spare time, although you have obviously gotten a lot further. :)

My biggest critique of this position paper is that it doesn't really come across that "managing time" is the crux of the problem. Even when you introduce the concept of "managed time," the motivation is about being able to express identity and encapsulated state in reactive programs. The focus of the introductory examples here is more on control flow; perhaps the change in title represents a change in focus?

The comment about the complexity of "switching" in pure FRP approaches, and how this relates to extensibility is *really* important. FRP, by its nature, wants everyting to be parametric, while a more imperative or even OOP style can build things in a more ad hoc fashion.

For what its worth, this is the angle from which I came to the problem: by way of my shading language work. That is another domain where the conceptual simplicity of "wiring" things in terms of functional/dataflow programming belies the fact that the way things are modularized, and the ways that they evolve, are much more ad hoc. Having to re-do a ton of "wiring" in order to make a trivial change starts to make you question the value of treating wiring as the fundamental model for composition.

So, instead, this work (and my conceptual model of the space) starts out with the idea that a behavior is not a "T-valued signal," but rather something closer to an actor (or a concurrent thread) that can impose a T value on a signal via constraints/bindings. It is also then natural to let these behaviors introduce new T-values signals/cells (with identity), which other (separately expressed) behaviors might then impose values on.

Which brings us to my second main critique, which is that the semantics of how constraints are composed here ("just re-evaluate things until they converge") is perhaps overly simple. The fact that contradictory constraints cannot be ruled out statically, but constitute a run-time error seems like an inhibitor for composition. The unpredicable performance of repeated evaluation also sounds worrying for anything that needs to be responsive and low-latency.

I can't remember if I've mentioned it here before, but I would argue that a better mental model for composition of constraints/bindings would be something like layering or "alpha blending" as it appears in graphics, including almost all nonlinear animation tools. I would argue that part of the reason why Fran worked so well in the first place is that it leaned heavily upon the natural ability to compose images via the "over" operator. FRP tends to work best in contexts where a natural composition operator exists ("over" for images, "add" for audio signals, "union" for 3D scenes), which leads me to think that these operators need to be given more attention.

So, my third critique of the work would be that while it can express:

- sequential composition of instantaneous imperative statements (in event responses), and

- concurrent composition of on-going reactive behaviors,

what seems to be missing from this is any way to compose reactive behaviors sequentially. There is no (immediately obvious) way to say "do A, then do B."

I could imagine using a "tick" event and building such things in user-space, but it feels to me like sequential composition is important enough to merit more direct support.

This has been quite a long response, and I apologize if it is hard to digest. I'm genuinely very interested in this space, which makes it hard to keep things concise.

These are great detailed

These are great detailed comments, it should really help when I present all of this next week, thanks! Replies below:

The focus of the introductory examples here is more on control flow; perhaps the change in title represents a change in focus?

This paper is more about the fact that control flow is suitable for reactive programming if we redefine it. "Managed time" is actually orthogonal to "control flow"...one could see data flow systems as managing time also (as well as rule-based systems, and so on). Of course, I've conflated everything, so that is not obvious.

Having to re-do a ton of "wiring" in order to make a trivial change starts to make you question the value of treating wiring as the fundamental model for composition.

Yes! This is an argument I'm trying to make more clear: whether you go with data flow or control flow has important implications on the modularity of your code...viscosity also becomes opposed to explicitness.

Which brings us to my second main critique, which is that the semantics of how constraints are composed here ("just re-evaluate things until they converge") is perhaps overly simple. The fact that contradictory constraints cannot be ruled out statically, but constitute a run-time error seems like an inhibitor for composition. The unpredicable performance of repeated evaluation also sounds worrying for anything that needs to be responsive and low-latency.

I agree and definitely Glitch doesn't satisfy all use cases. The idea is to be very low effort to the programmer: the semantics are simple and they don't have to jump through any hoops to write their code; on the other hand, this means the implementation doesn't get very many guarantees from the programming model! But this really compares against the way garbage collectors work: they are low effort (for the programmer) and make performance unpredictable. You also need to be careful about GC in very responsive, low latency, and real-time systems (either by not using GC, or by using more restricted GC that requires more effort from the programmer). We start with this analogy in the conference paper, but unfortunately didn't follow it through to this conclusion.

FRP tends to work best in contexts where a natural composition operator exists ("over" for images, "add" for audio signals, "union" for 3D scenes), which leads me to think that these operators need to be given more attention.

Well, I could never figure out what those operators were for a compiler. Perhaps there is wisdom to be found in parser combinators and such. But I guess my point is that in the general case, those operators might not exist. We know there are some fundamental high-level operator patterns (e.g. monads, list comprehensions), but that isn't very useful here.

what seems to be missing from this is any way to compose reactive behaviors sequentially. There is no (immediately obvious) way to say "do A, then do B." I could imagine using a "tick" event and building such things in user-space, but it feels to me like sequential composition is important enough to merit more direct support.

Correct. Actually, we can handle it with a dimension orthogonal to time (you'd still want such sequencing to work between times, so the new dimension is essential), BUT although we could express bubble sort or a lexer if we wanted to, it wouldn't be very incremental, so I wonder if there is a better way to do this. It requires much more thought, which is why I'm deferring it for now.

I'm starting to understand better

Actually, we can handle it with a dimension orthogonal to time (you'd still want such sequencing to work between times, so the new dimension is essential), ...

Of course. Yes, "simulation time" obviously needs to be a dimension separate from "computer time" (the time dimension you are "managing"). You might still need some guarantee of monotonicity for "simulation time," just as FRP tends to require, so "orthogonal" might not be the exact right word.

My bias is so strong toward games/simulation that I tend to forget many applications don't have a natural "time" axis. :)

One tangent that comes up along that line is that once (simulation) time is in the picture, there is an obvious link from this work back to Simula/Beta/GBeta. The flavor of how behavior is expressed here has a lot of similarity to how discrete event simulation works in those systems (which also "manage time" by virtue of doing lightweight thread/coroutine switching).

And the Simula/Beta tangent raises this question I forgot to ask before: how do I decide whether to use def or trait in this system? It seems like there is a lot of overlap between what the function-like and class-like abstractions can do (and I know you are already familiar with that overlap). In my own toy work I have found it useful to keep function-like and class-like abstractions separate in the language, even if their implementations are largely unified. I wonder if you've got any advice to share based on your experience.

But this really compares against the way garbage collectors work: they are low effort (for the programmer) and make performance unpredictable. You also need to be careful about GC in very responsive, low latency, and real-time systems (either by not using GC, or by using more restricted GC that requires more effort from the programmer).

Strangely enough, this description is probably the first time the "managed time"/"managed memory" parallel clicked for me. I now understand that I am uncomfortable with both, but for largely the same reasons.

And I agree that the trade-offs will be different in different domains. Once again, you are trying to approach this as a general-purpose programming language, while I'm still viewing everything through my narrow "games games games" lens.

Well, I could never figure out what those operators were for a compiler. Perhaps there is wisdom to be found in parser combinators and such. But I guess my point is that in the general case, those operators might not exist. We know there are some fundamental high-level operator patterns (e.g. monads, list comprehensions), but that isn't very useful here.

One thing I'd note is that the "over" operator for images isn't commutative (and neither is "union" for 3D scenes, when you get down to the nitty-gritty). So, if you abandon the idea that your composition rules need to be commutative/order-independent, it should be clear that there is a very general composition operator that applies in all cases: unambiguous choice.

That is, if you compose behaviors A and B, and both A and B try to bind values to the same cell, always favor B. That's what you did for the "Coding at the Speed of Touch" work. That policy works regardless of type of the cell (although you might have a better type-specific operator in some cases). In fact, it is even less constrained than what you currently have in Glitch, since your iterative constraint solver needs types to support equality comparisons so that it knows when it is done.

The down side, of course, is that now order matters, and you need to make sure that users can reason about it. One could make the argument that resolving contradictory constraints by (what might appear to be) fiat is going to lead to an undebuggable mess, compared to just giving me a runtime error when I ask for something contradictory.

I'm (tentatively) okay with that trade-off but, again, the more narrow domain I'm concerned with might make it easier to accept.

And the Simula/Beta tangent

And the Simula/Beta tangent raises this question I forgot to ask before: how do I decide whether to use def or trait in this system?

Both def and trait can involve launching new tasks (the former for the body, the latter for the initializer), but a trait can decorate an object with fields and methods, while the former is limited to its own body, even if that body is continuously executing and can define local state (that cannot escape without returning an object at any rate). The distinction is basically the same as in Scala. All public members defined in a trait go into the global symbol table (global namespace for members is another idea I stole from Jonathan and push in my "maze of twisty classes" paper), so what traits your object extends depends on what members you want to use :)

One thing I'd note is that the "over" operator for images isn't commutative (and neither is "union" for 3D scenes, when you get down to the nitty-gritty). So, if you abandon the idea that your composition rules need to be commutative/order-independent, it should be clear that there is a very general composition operator that applies in all cases: unambiguous choice.

Note that effects in Glitch have to be commutative with respect to their execution order; we can still support operators that are not commutative with respect to their arguments. (I don't think you are confused, but just to be very clear).

So if "over" creates a new object rather than modify an existing object, we are OK; I'm certain this is what Fran does. Now say we want to modify an existing image: then as a strict cell-like binding we are kind of screwed, but it could still work as an aggregation (i.e. the effects simply compose!); e.g.:

object x is Image 
x.over(y)
x.over(z)

Just think of "over" as something like "+=" that composes y and z into the image x. We can even use the execution tree positions of the "over" calls to order them in Z-space, like how "log" works in ordering debug statements in the console. But note, this is not execution order mattering, but the order of a path that is completely reproducible on execution (so you re-execute some code, the run-time reproduces paths with the same global ordering relationships). So the order is consistent and fixed with respect to your statement order and call tree.

Incidentally, these paths are used for lots of other things: they are used to memoize effects and objects (since we can reproduce them). The are also used to consistently resolve cell binding conflicts; so the bindings that fail are always located in the same locations, rather than being randomly assigned. These paths can also form the basis for a dimension that I said was orthogonal to time (since all points have a complete ordering that is not time dependent). Note that this "execution dimension" basically already exists and is used for tasks where some order is desirable (e.g. in ordering log statements). I just haven't really explored how to push it further into the language yet to improve expressiveness.