Lambda the Ultimate

IObservable is just an interface that indicates push-based, reactive, asynchronous communication. Whether glitches can occur is dependent on HOW you use the interface.

The authors are clearly referring to the default implementation in Rx.NET, with the guarantees Rx is supposed to provide (there are some properties relating to thread-local data, multithreading, etc.). Certainly if you write an entirely new implementation based on expression trees, you can get any behaviour you want out of it.

From my understanding of its semantics, Rx.NET can glitch.

The authors use the phrase glitches to communicate what happens when the system does not guarantee safe re-entrancy, and they require complex machinery for avoiding glitches.

I don't think safe re-entrancy is synonymous with "glitches". A glitch is a temporary violation of a dataflow invariant. Thus, "embracing glitches" seems like a very bad idea, particularly in the presence of side-effects which may depend on those invariants.

In practice, glitch-freedom costs some time and space in overhead, so glitchy implementations are faster, but only usable if your domain can tolerate glitches.

From my understanding of its semantics, Rx.NET can glitch.

How? The state is encapsulated in the monad. It is only when you try to pull the state out of the monad that you can run into problems, such as a deadlock.

And, again, IObservable is just an interface. Observable just implements a bunch of extension methods. Some extension methods are unsafe and can do such evil things as cause a deadlock if the person writing them isn't careful.

Certainly if you write an entirely new implementation based on expression trees, you can get any behaviour you want out of it.

There are really two levels of problems that can occur with expression trees, too.

The first is improper metadata design to govern what happens to the expression tree internally. For example, Linq 2 SQL DataLoadOptions metadata would only allow you to specify one relationship edge for a given table<->table in a query. The net effect was that if one table joined to another table in multiple ways, it would just drop one of the two tables arbitrarily and eagerly load just one. The rewriting using the metadata is nondeterministic, and doesn't allow the developer to actually control the meaning. Since Linq 2 SQL is lazy by default, there was literally no way to fix this (this may have changed, though).

The second is improper rewriting. The rewriting is deterministic, but it doesn't preserve the intended meaning.

Thus, "embracing glitches" seems like a very bad idea, particularly in the presence of side-effects which may depend on those invariants.

By "embracing glitches" I am referring to asynchronous constraint solving or something like Sean McDirmid's Bling.

In this situation, it's best to work with an example. All observers are processed in some arbitrary order, but they are all notified about something of interest in the subject. The first observer in this arbitrary order reacts to this "something of interest" and does something to the subject. The subject has now re-entered the section of code dealing with "something of interest", and might do something that changes what all other observers see. In this way, the observers may observe a glitch, in particular if they are expecting a set of values to come, say, in pairs, and instead they see the same value twice. That's a glitch due to unsafe re-entrancy.

You can also have glitches due to the Brock-Ackerman Anomaly, in general.

How? The state is encapsulated in the monad.

A monadic interface doesn't guarantee glitch freedom, the implementation must actually provide a glitch-free evaluation strategy via breadth-first, transactional expression updates (as this paper does).

Some extension methods are unsafe and can do such evil things as cause a deadlock if the person writing them isn't careful.

The whole point of the reactive framework is to eliminate complex threading issues by providing an embedded dataflow language without needing to resort to locks. Deadlocks should be a thing of the past, and I'm skeptical that any composition of IObservable combinators are inherently unsafe, unless you also start introducing your own locks (by the intended semantics, not the implemented semantics of course).

All observers are processed in some arbitrary order [...]

This is exactly what dataflow, FRP and the reactive extensions like as detailed in this paper avoid. Glitch-freedom means breadth-first update, not depth-first update where earlier observers can modify the state before later observers even get a chance to run.

It's also worth noting that event loop languages like E can also avoid this problem by using turn-based evaluation, where those updates would occur in a later turn, after the turns where the observers are notified.

The whole point of the reactive framework is to eliminate complex threading issues by providing an embedded dataflow language without needing to resort to locks. Deadlocks should be a thing of the past, ...

Threads (mechanism) and deadlocks (induced bug) are a bit of a red herring. E.g., event-oriented programming, such as with callbacks and event loops, or slightly better, continuations, have similar problems as most of the computation is represented with effects and is thus not reasonable. The type signatures speak for themselves: the return type of an event is void and few people write heap-less continuation code.

This is exactly what dataflow, FRP and the reactive extensions like as detailed in this paper avoid. Glitch-freedom means breadth-first update, not depth-first update where earlier observers can modify the state before later observers even get a chance to run.

I didn't get all of this from your writing, but a deterministic semantics is distinct from a glitch-free semantics. An example would be 'patcher' dataflow languages like Max that are deterministic but do not provide glitch freedom. However... the importance of glitch-freedom really depends on the domain as it will stress different parts of your FRP system. I think it needlessly wastes programmer effort by not including it, but developers can work around its absence.

It's also worth noting that event loop languages like E can also avoid this problem by using turn-based evaluation, where those updates would occur in a later turn, after the turns where the observers are notified.

What I believe you're attributing to E as a reasonable event system might be traced to the 'synchrony hypothesis' for embedded systems where each event should be handled in one step before moving to the next (which gets state updates before it begins executing); I think Esterel would be a more canonical citation (a seminal synchronous imperative event-oriented system). What it means to synchronously handle multiple spawned events is an interesting question with many different answers.

I should go back to thinking about data parallel FRP ;-)

I didn't get all of this from your writing, but a deterministic semantics is distinct from a glitch-free semantics.

Agreed, and I wasn't requiring determinism, but I was requiring no "plan interference". Glitches are a type of plan interference.

Wat I believe you're attributing to E as a reasonable event system might be traced to the 'synchrony hypothesis' for embedded systems where each event should be handled in one step before moving to the next (which gets state updates before it begins executing)

I don't believe E traces its ancestry from synchronous languages, but rather more from taming actors and event-loop programming. One of E's primary goals was to prevent plan interference among mutually suspicious programs, which it achieves via the aforementioned turn-based evaluation.

First, for clarity, I assume you mean E's ordering for something like JavaScript+eventloop, not for FRP scheduling (which doesn't make much sense to me this late at night).

You're right that I don't think E's ordering and the synchrony hypothesis are usefully related; I thought you meant something like a nested form of synchronous updates. However, I disagree about practical applicability to the synchronization problems addressed by FRP. Finally reading that part of Mark's thesis, I believe you're referring to E-ORDER:

When Alice passes Bob a reference to Carol, this reference provides Bob only the authority to cause messages to be delivered to Carol after prior messages already sent by Alice on this reference have been delivered. E-ORDER is sufficiently strong to enforce the restriction Alice needs, and sufficiently weak to be cryptographically enforceable among mutually suspicious machines.

E-ORDER is a step above the typical almost-no-assumptions distributed scenario. However, it does not solve the interfering side-effects problem: the side-effects are still there. E.g., clicking on an object starts a 'wiggle animation and mousing away runs a 'droop' animation: E-ORDER allows any interleaving and thus there might be some incorrect interaction of state (... and, often, there actually is). Perhaps another way to look at it is that most (sequential) GUI systems with event loops obey E-ORDER yet still suffer ("19.4 -- CAUSAL Order is Too Strong" in Mark's thesis) -- E-ORDER is tackling a different problem.

E-ORDER is tackling a different problem.

I'm not referring to E-order, but rather to E's messaging semantics. This link is sufficiently descriptive, and describes precisely the plan interference inherent to the traditional observer pattern, and how E solves it.

Ah, you meant a vat handling a message to completion (by not allowing blocking calls to other vats and instead requiring asynchronous ones) -- that wasn't clear at all from your original links!

I've debated with others about this type of approach in a slightly different context (adding continuations or FRP to JavaScript to support postMessage -- this example also hopefully suggests to you that this is a known pattern outside of E, even if not all designers know it, such as the original IE ones). You actually *do* get the synchrony hypothesis -- an event gets handled synchronously. However... to get synchronous protocols across vats, you're forced to find your own solution as the language only gives you uncoordinated interactions. As noted above, this is made more palatable by continuations (giving you direct-style programs over multiple steps), but I still think FRP is more reasonable as you don't worry about continuations interfering with each other. Note that adding continuations to a language like E is a big deal as it violates another design goal of E (and actually, the synchrony hypothesis!).

Edit: I'm wondering if there's a more canonical name or description for Mark's setup. E.g., non-blocking.

but I still think FRP is more reasonable as you don't worry about continuations interfering with each other.

I agree, but E's messaging semantics are the minimum necessary to avoid glitches/plan interference with the observer pattern.

Edit: I'm wondering if there's a more canonical name or description for Mark's setup. E.g., non-blocking.

Do you mean the async send? IIRC, EROS and E distinguishes blocking from non-blocking as a "call" for the former, and a "send" for the latter.

E's messaging semantics are the minimum necessary

How is it minimal and what is the proof that it prevents glitching across multi-vat interactions? I think the claim is actually fairly subtle.

Do you mean the async send? IIRC, EROS and E distinguishes blocking from non-blocking as a "call" for the former, and a "send" for the latter.

I meant for the overall model. You cited the turn-style naming here, but I suspect this is another ocap-ism where there's a more canonical naming (even if less nuanced for E or ocap particulars). E.g., from actor language papers for high-performance servers and OSs or CSP-style stuff.

How is it minimal and what is the proof that it prevents glitching across multi-vat interactions? I think the claim is actually fairly subtle

I should clarify that I'm only speaking in terms of single-vat programs, which is why I was confused when you brought up E-order. I believe you're right that E-order prevents making this guarantee for multi-vat interactions, unless you change the semantics of notifications such that old update notifications are simply discarded and never processed. This is the semantics David prefers IIRC.

I'll also note that I don't know what E developers or any other ocap enthusiasts believe on this subject, so this is just my opinion: to express glitch free compositions, one need only equip a program with a message send operation that does not steal control flow from the sender, so the sender may protect itself from client interference. As you noted, messages must also be totally ordered, unless you go with the altered semantics.

So by "minimal", I meant that adding an async send which simply enqueues the message and delivers it a well-defined later time is a minimal extension once you've already assumed message passing.

I meant for the overall model. You cited the turn-style naming here, but I suspect this is another ocap-ism where there's a more canonical naming (even if less nuanced for E or ocap particulars). E.g., from actor language papers for high-performance servers and OSs or CSP-style stuff.

Good question. Some quick searches on the history of event loops doesn't turn anything up. The only similar concept would be "transaction", and the similarity is most apparent when you note that they both consist of an atomic unit of work from the runtime's perspective.

So "turn-based event loops" could also be read as "transactional message passing", where the transactions have a strictly defined extent in the operational semantics.

So by "minimal", I meant that adding an async send which simply enqueues the message and delivers it a well-defined later time is a minimal extension once you've already assumed message passing.

Ah, I thought you meant something along the lines of 'necessary but sufficient'. I'm still not even sure about the sufficient side of things (the example shows a particular case of the bug in the observer pattern, but I suspect there are other forms that can arise).

So "turn-based event loops" could also be read as "transactional message passing", where the transactions have a strictly defined extent in the operational semantics.

'Transactional' has become so (semantically) diluted that (as an admitted outsider) it means little (to me, at least). In this case, it actually does seem like the synchrony hypothesis style reasonability. A bit to my chagrin, the reasonability I've been advocating would be across events and seems like an open problem, e.g., Jonathan Edward's work with 'coherence'.

I'm currently implementing a multi-vat approach in Haskell, for a paradigm closely related to the observer pattern.

Inter-vat consistency is a significant concern, and glitch-freedom is a precondition for consistency. I'm currently using several techniques to help control inter-vat consistency:

• temporal logic: each vat experiences a series of 'instants'. One may schedule events for a future instant, or within the current instant. Within an instant, observables are constant.
• Instants serve as a unit for atomic inter-vat update: updates from one instant are processed by other vats as an atomic package. This ensures "different views" of observables are glitch-free assuming you view observables through the lens of just one vat.
• Per vat eventual consistency: In addition to regular instants, I introduced phases between instants to handle the cases where update begets update. A vat is forced to "settle" internal observables before it may advance to the next instant. This ensures that remote vats see 'settled' states rather than transition states, or at least that transition states are explicitly made observable via scheduling to a future instant. (Eventual consistency should also occur between vats, but vats necessarily see the intermediate updates.)
• Vats with clocks and bindings with history: vats are asynchronous and do not interfere with one another, but they will still be "roughly" synchronized by best-effort to keep a logical 'instant' clock within an error-window of a shared clock (such as universal time). A multi-binding that crosses objects from different vats will receive 'straggler' updates. Performing FFI/UI/etc. outputs based on the updates of a few milliseconds past would be much more stable than using the bleeding edge.
• Stabilize inter-vat delay: variability in delay between vats is the primary source of indeterministic system behavior. Most of this variability can be masked by adding a fixed delay from the time a message is issued. This is another useful trade of latency for consistency.

Having shared clock among vats, observables, and observers is also useful because it allows observations to be continuous functions of time in a manner that composes with modular bindings. One can integrate, interpolate, model physical systems. One can also predict and plan based on a rich, cooperative model of anticipated future.

My earlier attempt to use STM for glitch-freedom proved extremely problematic: it was too difficult to also control logical delay, ensure consistency (re: intermediate or transitory states), ensure progress of critical sub-programs, and integrate with IO.

old update notifications are simply discarded and never processed. This is the semantics David prefers IIRC.

I've since changed my mind. I now prefer the explicitly timed approaches, where every 'update' carries a model of present, recent past, and anticipated future... e.g. using (t->r) instead of scalar 'r'. This gives you nearly all the neat features of FRP (excepting determinism), and allows you to precisely access state at a given 'time' without concern for which bindings updated 'first'.

Bindings keep a sliding window of these updates, releasing the past after you observe it - perhaps keeping a bit extra if you ask nicely. Assuming progress, the sliding window prevents space-leaks.

A monadic interface doesn't guarantee glitch freedom

No more than it should!

The whole point of the reactive framework is to eliminate complex threading issues by providing an embedded dataflow language without needing to resort to locks. Deadlocks should be a thing of the past, and I'm skeptical that any composition of IObservable combinators are inherently unsafe, unless you also start introducing your own locks (by the intended semantics, not the implemented semantics of course).

That is not the point of the Rx framework, at least as I've heard Wes Dyer, Jeffrey van Gogh, Bart de Smet & Erik Meijer describe it.

Also, it is not that the composition of any IObservable operators is unsafe. It is that some are unsafe, because they are really blocking operations (IEnumerables masquerading as IObservables). They are effectively like an unsafePerformIO. Bottom line: If you block on the same thread that you are waiting for a reply on, then nothing gets done. There's nothing you can do to prevent this within C#, other than to not design things that way. But if you happen to be writing a WPF application, you have to explicitly guard against calling blocking operations on the UI thread, especially if you are waiting for something that is waiting on something related to the UI thread's resources, since it is single-threaded. Otherwise, you have a deadlock. And this is true regardless of whether you are using Rx framework or bare bones WPF callbacks. It is the resource model that is the challenge, not the interface.

It's also worth noting that event loop languages like E can also avoid this problem by using turn-based evaluation

It is not necessarily about avoiding the problem. It is about making clear the communication protocol. The standard Observer pattern in GoF only supports the Update() interface. You can 'solve' this limitation by taking note of what the GoF authors note (page 296) and making sure the Observer wrapper properly handles referential integrity:

Consequences
[...]
3. Unexpected Updates. Because observers have no knowledge of each other's presence, they can be blind to the ultimate cost of changing the subject. A seemingly innocuous operation on the subject may cause a cascade of updates to observers and their dependent objects. Moreover, dependency criteria that aren't well-defined or maintained usually lead to spurious updates, which can be hard to track down.

This problem is aggravated by the fact that the simple update protocol provides no details on what changed in the subject. Without additional protocol to help observers discover what changed, they may be forced to work hard to deduce the changes.

So one of the weaknesses highlighted here is that Subjects anticipate that Observers will want to do something back to them in response to a notification. If you don't explicitly model this dependency, then of course you will have a referential integrity problem. It shouldn't matter if you are using a GoF Observer UML diagram or Rx code. Temporal dependencies are harder (more work) to capture structurally due to requiring 6th normal form and bitemporal relations.

In other words, you can decouple a Subject from its Observers by using any number of strategies, such as sticking a Registrar inbetween the Subject and Observer:

[Subject]
     | *
     |
     | R1
     |
     | notifies
     | 1
[Registrar]
     | 1
     | registers with
     |
     | R2
     |
     | relays request to
     | *
[Observer]

The Registrar now handles message passing between the Subject and the Observers. Since the Observers do not possess the capability to perturb the Subject directly, we can implement something like E's turn-based evaluation strategy.

The advantage of this Scala implementation over that is that this Scala library is primarily a safer alternative to the CLI event model. The disadvantage is that Subject and Observers are not decoupled as much. It would be nice to have a middle ground here where the type system mediated more of the exchange, thus supporting better code reuse (traits and mixins) and fewer static productions required so that any given problem context will have a less ad-hoc solution. The common theme is that we want to preserve the fact observers don't need to know that they are all sharing a mutual subject, but we want to vary the levels of cooperation and competition between the subject and its observers.

As for glitch freedom implementation techniques, I've never read the perfect paper on this issue. Guaranteeing glitch freedom all the way down to the bare metal is something I'm interested in, but acknowledge I don't know enough about.

[Note: I'm heading on vacation now, so I'll see you in 2 weeks, and will also respond to your questions about data grids in the other thread.]

That is not the point of the Rx framework, at least as I've heard Wes Dyer, Jeffrey van Gogh, Bart de Smet & Erik Meijer describe it.

Asynchrony was often implemented via (poorly controlled) concurrency. Rx now provides an alternate means to express such asynchronous operations, thus delegating the responsibility for managing concurrency to the Rx runtime (which implements well-defined schedulers and a decent standard semantics).

So eliminating complicated threading issues is effectively what Rx achieves IMO, along with a more natural expression of reactive programs of course.

Enjoy your vacation!

In practice, glitch-freedom costs some time and space in overhead, so glitchy implementations are faster, but only usable if your domain can tolerate glitches.

In the FRP systems I've seen -- both high-level and low-level -- there are much bigger (and easier) fish to fry for performance. Not providing glitch-freedom should be done after providing poses to be a performance problem.

Disagreed.

Making a model robust with respect to glitches can be cheaper than avoiding the glitches themselves. There are many cases where avoiding glitches is really just too expensive or impossible to do in an elegant way, just try looking at indirect signal accesses (list.selected.temperature) or reactive collections! Throw in physical constraints and you are basically living in a very glitchy world, where the glitches themselves become a significant part of the semantics (glitches in physics essentially create animation!).

Making a model robust with respect to glitches can be cheaper than avoiding the glitches themselves.

A general statement I can always agree with, but not necessarily useful :)

There are many cases where avoiding glitches is really just too expensive or impossible to do in an elegant way

Same as above. An example is n-body simulations where we often miss some far apart interactions for better isolation and thus parallelism.

However, I suspect you can still get and want glitch-freedom. Compiler technology is very far behind the theory side of FRP. Your example of collections is one where I think glitches are a red-herring (throw in parallel and speculative execution, get rid of message passing, reexamine memoization approach, etc. -- then talk about weakening the semantic model for faster performance). The physics cases are interesting in that you likely also have very restricted targets like GPUs and the premise is the algorithms (like n-body) are glitchy (but, at least in this case, glitch-free locally!).

When you guys support glitch-free collections and indirect signal access in an FrTime or FlapJax-like system, I'll give you more credit here. Throwing in all that stuff doesn't really solve the problem, or if it does I haven't seen the solution yet. Its not about milking performance, you just can't have it at all, or you can't have it without extreme cost. SuperGlue needed to support these features, which is why I decided to embrace glitches rather than try to avoid them (the other option was to drop the features). This was more about complexity of the system, performance never even entered the picture, I didn't make that clear in my comment.

My comment on physics...inconsistency (glitches) is a part of the semantics of an iterative solver and unrelated to whether we use a GPU or not. If we have a spring with a certain elasticity attached to a mass, the mass's position will not be inconsistent (all constraints aren't met) until the spring can bring the mass to within the spring's distance constraint with no momentum. Higher elasticity allows us to have more springs (constraints), since inelastic springs won't allow us to arrive at the nice compromise solutions. This comes at the expensive of having the mass bounce around more as the springs are doing their work.

Once we have embraced glitches, we can start using iterative methods to solve constraints. The focus of FRP on glitch-free semantics holds it back, guarantees that settle on eventual consistency would provide much more flexibility, expressiveness, lead to simpler systems, and perhaps provide more performance.

Once we have embraced glitches, we can start using iterative methods to solve constraints. The focus of FRP on glitch-free semantics holds it back, guarantees that settle on eventual consistency would provide much more flexibility, expressiveness, lead to simpler systems, and perhaps provide more performance.

I think there's a big difference between embracing glitches, as necessary for animation semantics, and tolerating them, as for eventual consistency.

Iterative constraint solutions in FRP could be expressed with explicit time - though I suspect you'd need a denotational FRP rather than the operational variation favored by FrTime and Flapjax.

Assuming tolerating glitches is desirable for the reasons you've outlined, how do you tame side-effecting operations so that glitches don't trigger those side-effects spuriously?

In SuperGlue, the system is always stable (no glitches) when side effecting operations are executed (on each turn, re-evaluate circuits until evaluation of other circuits doesn't change their results). This would probably not work with physics, since the stable state is probably more than few time steps away. In the physics apps I've dealt with so far, side-effect operations either occur out of band (via non-physical input) or on the basis of some discrete event (collisions).

When you guys support glitch-free collections and indirect signal access

Your example of "list.selected.temperature" doesn't require indirection outside of typical FRP -- perhaps I'm not understanding it. E.g., a selectable list for this API is a function of selection events and the list itself, and when the selection (or list) changes, in current push approaches, the query is remade, at which point the list data structure determines complexity (O(1), O(n), O(logn) under 3 different common encodings). Glitch freedom doesn't come into play.

This example also shows why I think the issue (in most domains) *isn't* one of glitch-freedom but of collections and general compiler optimizations for incremental computing. For example, we might want to memoize selections for hotspots -- so, even without fancy list data structures in general, we still get o(1) in hot traces for regular accesses. As another, we might want to push the select query down to where the list is getting created (much earlier in the code). Neither of these approaches require changing semantics.

Once we have embraced glitches, we can start using iterative methods to solve constraints.

I totally agree, hence the n-body example. My point is that these are the exception, not the rule. If you work where these are common (such as in simulations), it may not seem so, but perhaps suggesting it's the case is that there's a good chance you won't see them in the typical ugrad cs education.

I am with Leo here. In my view, in a general purpose embedded reactive programming language, glitches undermine scalability and compositionality. How would a user work around glitches in an FRP-like system without having support from the framework or knowing too much context? If you want to live with glitches, you'd have to make sure that your functions better be total or you need to know what glitch can happen in which situation and be sure your functions can handle them.

For iterative solvers, it seems to me that one could make a compromise by restricting the visibility of intermediate solutions to certain subgraphs of your dependency graph and only expose the end points, i.e., still guarantee the absence of glitches to clients working with the end points. What I don't get is why glitches in physics create animation or why that would be a good thing. Maybe I am misreading something.

Let me try and think this out.

We can minimize the problem of glitching by eliminating intermediate state; i.e., signals do not cache or otherwise store their current value, so any expression is simply evaluated whole until state is hit. Obviously, no state means no glitches, or we can be more specific than that: no state that feeds back into the signal world means no glitches. So input and output are often not a problem, though we might have to deal with some UI widgets where input and output are related in some way (e.g., selection as an output in a UI list that takes a list as an input, changes in the input list can affect selection). What state can really cause glitches then? Well:

• Caching expression evaluations for performance or historical reasons; e.g., we want to memoize type information in a incremental compiler.
• Detecting and reacting to discrete changes in expression evaluations. Since signals don't have state, extra state has to be allocated to detect the point at which a boolean expression goes from true to false or false to true.
• Any value that we want to manipulate imperatively; e.g., the position of a sprite in a game where position is controlled by the user's keyboard.

That's it. If you have some kind of transactional semantics in your system, you can re-evaluate your state elements but not commit them until all dirtiness is known. You might evaluate expressions that are inconsistent, but that's ok because you will re-evaluate the expressions again. When your system is consistent (all your state values are updated), then you can execute your side effects. This is what I mean by embracing glitches. Possibly the only difference here between a tradition FRP system is that I advocate dynamic dependency management to eliminate a stateful explicit dependency graph, which can just lead to more glitches especially when collections or indirect signal accesses are considered. But I won't argue about that unless anyone is interested in that problem.

Physics is something different entirely: all your properties will be stateful and consistency with constraints is defined over time, consider two springs that constrain x:

x = 5;
x = 10;

Obviously, x can't be both 5 or 10, but the springs (if equally strong) will pull x to around 7.5 eventually. Animation occurs because x, on its journey to its right value, will change incrementally, and hence we can animate its movement.

If you have some kind of transactional semantics in your system, you can re-evaluate your state elements but not commit them until all dirtiness is known.

Interesting. Let's say you have a deep dependency tree, with the root emitting spurious values. You are saying, you reevaluate everything until none of the nodes are emitting changes any more. It seems to me, that could quickly become more expensive than avoiding glitches from the start unless you can give some guarantees of how often or in which pattern glitches can occur.

But I won't argue about that unless anyone is interested in that problem.

consider two springs that constrain x:
x = 5;
x = 10;
Obviously, x can't be both 5 or 10, but the springs (if equally strong) will pull x to around 7.5 eventually. Animation occurs because x, on its journey to its right value, will change incrementally, and hence we can animate its movement.

In the spring example, if you specify that you return the equilibrium but also return intermediate values, then these are glitches and you don't want animation. If you specify that you animate the springs, they are not glitches - given you get your physics right. For another example, consider a solver that would glitch by first letting rigid bodies penetrate each other before it handles contact forces/impulses. It would still create an animation but that animation would not make much sense (unless you are trying to demonstrate the iterations of the solver, which is another story). Am I making sense?

Me :) Here you go!

Say try supporting JTable or JTree in Swing with row/node selection, maybe with the email example in my 2006 ECOOP paper. When you have an indirect signal access a.b and you are maintaining an explicit dependency graph, what happens when a changes? In Swing, you'll have to uninstall your observer on a_old.b and install it on a_new.b. This can be very tricky if many changes are occurring at once, and adding state to patch things up means the potential for glitching becomes more massive. Now add dealing with the addition and removal of rows and nodes: how to install observers on the new rows and remove them from the old rows? Even more state is needed... From my experience, I believe that the explicit graph method is just not scalable.

Well, in that sense, every glitch, not only in physics, creates animation. Whether that animation is desired or sensible depends on your solver and what you are doing. It seems to me though that desired animation is rarely created by glitches.

To me, the fact that the physical properties are not always consistent with their constraints is similar to the property of a glitch. How you solve your constraints (like by impulses) is actually the implementation detail, while the path to a solution is interesting to us as animation. The constraints themselves often don't have a time component, although they can, in which case you have both animation from your solver and animation from your changing constraints (dizzy).

In the spring example, if you specify that you return the equilibrium but also return intermediate values, then these are glitches and you don't want animation. If you specify that you animate the springs, they are not glitches - given you get your physics right. For another example, consider a solver that would glitch by first letting rigid bodies penetrate each other before it handles contact forces/impulses. It would still create an animation but that animation would not make much sense (unless you are trying to demonstrate the iterations of the solver, which is another story). Am I making sense?

Your physics will never be right, it will just have some degree of accuracy right? Penetration occurs in most physics engines, but the rendering step would hopefully occur when penetration was not occurring; i.e., after multiple rounds of collision detection and reaction. My impression about many FRP approaches is that even transient glitches are bad and avoided, even if they don't matter to the ultimate results.

Say try supporting JTable or JTree in Swing with row/node selection, maybe with the email example in my 2006 ECOOP paper.

Hi Sean,

I've been working on implementing higher-order FRP in terms of dataflow graphs, and while I have theoretical reasons to think I have something in the right ballpark, I've been worried about the practical applicability. The examples in your paper are really a big help, so thanks!

On a large scale (distributed), one cannot have glitch-freedom, availability, and partitioning tolerance. Pick two. Glitch-freedom is a form of global consistency.

But one can still control glitches. E's vats and message ordering together can prevent glitches for communication patterns involving fewer than three vats. My own work at a modular FRP produced RDP, for which I've been assuming that observations by individual agents will be free of glitches but cross-agent communications would not be. That said, I'm contemplating use of a vat-like system for multiple agents, to further control inconsistency.

That said, I'm quite hesitant to embrace the examples offered by Sean. Use of software transactional memory, persistent collections, and explicit time could eliminate many of the glitches described above. I agree with Leo, also, that there are several optimizations (involving granularity for recomputes, intermediate caching, lifting, lowering, runtime specialization and JIT, etc.) that can improve performance by several orders of magnitude, and without introducing glitches.

Rather than glitches for performance, I much rather accept glitches for effective distribution.

I somehow missed the middle part of this comment...

Probably my biggest gripe is that the authors abuse the phrase "Observer Pattern" to refer to a very low-level concept: how Observers are reified in object-oriented languages today. That is not the point behind a pattern,

I am not following. We are referring to the observer pattern from the Gang of Four book as we mention in the intro. As most design patterns are, it is specific to a certain paradigm, in this case OOP. Maybe I am missing your point here?

the idea of deprecating a pattern is a joke

Why? Deprecating a function, method, class, etc usually goes like this: clients use a method, turns out there are ways to do it better, so you add a new method (or whatever it takes) and deprecate the old one since you don't want to break existing code. That way you give clients some time to adapt all of their code. Compare that to: clients use a pattern, turns out there are ways to do it better so you tell them to use the new instead of the old pattern but you also give them some time and the proper means to gradually adapt their programming model.

I am not saying that our presentation is perfect. I admit, we have to work on it, but I don't understand what would be so ridiculous about deprecating a pattern, even though that term was intended to be slightly figurative.

In my definition, something is mainstream iff it is used widely. By that measure, FRP is not mainstream and I suspect FRP alone never will be. As I argue in the paper, I believe one of the reasons is that FRP introduces a breaking change in methodology. I am a little stuck here though. What exactly is and what isn't FRP? For example, I don't think our continuation based core language in scala.react is FRP. It's rather a tool to implement FRP or event-processing state machines, just like imperative programming is often used as a tool to implement functional collections in languages such as Scala or C#.

So what distinguishes FRP from other reactive/dataflow approaches? In my view, FRP's two distinctive properties are (1) first-class reactive entities (behaviors, events, signals, signal functions) composed with (2) functional combinators (map, filter, switch, hold, ...). Now, different implementations can add their own flavors to it, e.g., continuous vs discrete semantics, behaviors vs signal functions, push vs pull vs push-pull vs mark and sweep (which are not only implementation details but influence the semantics), and so on. They would never drop first-class/higher-order dependency nodes or a combinator based approach though. To my knowledge, that would include all implementations that call themselves FRP but would exclude (even a higher-order) Lustre or the base language in scala.react.

I'd be very interested to hear about other views.

BTW, I'd appreciate any pointers to continuation-based FRP implementations.

Ingo,

Can you comment at all on scala.react's status? I'd like to play with it, but I'm a bit concerned that it doesn't even seem to be in EPFL's Subversion repo, much less becoming "productized" or whatever the term would be for "achieving the same status as Scala itself." Is it something that we can expect to become available as something other than a tarball/snapshot of work in progress? :-)

Definitely. We are slowly moving to git anyways, so I didn't bother to put it on SVN. I'll post a link on my website as soon as it is up on github.

... and (almost) back from vacation :)

Yampa, if I recall correctly, is continuation-based (but not delimited). I believe there was a (more syntactically transparent) Scheme version at one point as well. More generally, you can repeat the lessons from incremental functional and imperative computing elsewhere, e.g., one of Oleg's recent excursions posted here showed this for incrementalizing parsers (which I suspect is closer to your approach; not sure yet as your paper has been on my queue for when I get back to my office!).

I am aware of the continuation-based incremental computing work. There should be a reference in the paper somewhere. For Yampa, I had the impression that it is no more based on continuations as any other FRP system that has a switch combinator. I guess I have to read that again.

(Slightly edited)

In this context, a glitch is the occurrence of a value that does not reflect the current state correctly. For example, because previous and current state was mixed up or because of leaking intermediate solutions as in Sean's iterative solver example. A canonical example for the former would be:

a = true
b = !a
c = a && b

Suppose a, b and c are time varying values and a is changed to false. If b is not updated before c, c might be true, which is not desirable when you are part of the "ban the glitches" camp. In many languages, one can easily come up with examples where glitches can lead to crashes unless you deliberately plan for them or the system has some means to protected you from that (global undo, default values for everything, ...).

BTW, wikipedia's entry isn't too bad: http://en.wikipedia.org/wiki/Glitch. In the context of reactive programming, its meaning is most closely related to what is called an electronics glitch in the article as this is where the term is taken from AFAIK.

Let us assume that, at some point in time, 'x' changes from 3 to 4.

In this circumstance, an expression of the form x*(x+2) should change from 15 to 24.

However, a naive implementation of the reactive pattern might see an intermediate value such as 18 or 20 - i.e. 3*(4+2) or 4*(3+2). This is 'inconsistent' because the single value 'x' has two different values for a single observation.

This is called a 'glitch'. Glitches are problematic when they are observed by side-effects - they are, essentially, race conditions. They can also cause spurious div-by-zero faults and such.

Is a glitch still a glitch if its never observed? Maybe I'm using terminology wrong, and the only difference between FRP and SuperGlue's approach is that the latter embraces transient glitches but never does anything with them. So...ya, for x * (y + 2), when x changes from 3 to 4 and y changes from 2 to 3, x * (y + 2) might be evaluated inconsistently to 15 or something rather than 12 to 20, but the system would work the glitch out using dynamic dependence graphs until the expression was just 20, at that point you go to native code.

"Is a transitory inconsistency a 'glitch' if it is never observed?"

I'd say 'no' (philosophically). If there's no event I (an observer) can point at and call a 'glitch', then I say there was no glitch. Temporary inconsistency, if kept well hidden, is called an 'implementation detail'.

The question of 'glitch freedom' is whether you might observe a glitch. There is a qualitative difference between a system where you will never observe a glitch by design, vs. one where you happen to never observe a glitch by coincidence.

for x * (y + 2), when x changes from 3 to 4 and y changes from 2 to 3

It is unclear how a 'glitch' is possible in this example. Is there a dependency relationship between x and y? Is there an assertion that updates to x,y are atomic? Are you annotating these with explicit time or branching time, as for xT * (yT+1 + 2)?

For x * (x + 2), the evaluation is trivial and will be glitch free....unless we are caching/storing intermediate computations as state (e.g., x + 2 is state), which I hope would be avoided anyways (SuperGlue 1 did that b/c I was incredibly naive, SuperGlue 2+ don't). The glitch in x * (y + 2) occurs if x and y should change together (they are related) but somehow don't because of some state somewhere; say if y is really x + 10 but we are memoizing for performance reasons (in that case, we are back to the problem of stateful signals).

For x * (x + 2), the evaluation is trivial and will be glitch free...

Avoiding glitches for that expression is not trivial in a concurrent programming environment. If 'x' could be changing while you are performing the evaluation you'll need to do some multi-version concurrency control, or otherwise keep copies of all the state you've visited, in order to prevent glitches.

If this is trivialized in SuperGlue, it is only because you have architected it to be so, perhaps by reducing concurrency. And there will be plenty other consequences from that architecture.

Yes, that is true. x * (x + 2) is trivial because I have made it so, but then this whole discussion about glitches has been based on artifacts of certain implementations!

But really, memoizing ALL of your expression tree nodes is a bit crazy. Not only does it add a lot of state to your system, but perf will be worse since (a) you can't generate a big block of code and (b) memoization is more expensive than just redoing the computation (e.g., x + 2) . This doesn't include the glitch issue, but there is state that is necessary in your system and we have to deal with it one way or the other. SuperGlue doesn't deal with a glitch on x * (x + 2), but it can deal with a glitch on x * (y + 2). In any case, the choices for dealing with the glitch are similar.

I agree with you about concurrency. I've thought about memoizing some nodes in the tree (at larger granularities) and then using the same logic I use to resolve glitches (dynamic dependency tracking) to keep things consistent. Basically, if a depends on b but a and b are processed concurrently then we detect that a is invalid after b is done processing and reprocess it.

I've not suggested 'memoizing ALL your expression tree nodes'. I'd certainly advise against that, for the reasons you mention. I'd much prefer memoization be the domain of programmer annotations or profiler decisions.

I'd go the opposite direction. For example, if you say that 'y' is currently bound to 'x+10', I would like to see runtime specialization that translates the code x * (y + 2) into x * ((x + 10) + 2), then JITs it if it is used often enough to warrant that attention. And if the implementation can guarantee that 'y' is final or single assignment, one doesn't even need to track invalidation of the specialized code.

Concurrency does not imply memoization. MVCC helps, but is not the same as memoization of intermediate computations. For example, MVCC might apply only for the stateful elements that can change independently.

trivial because I have made it so

My point was more along the lines of: this non-trivial issue was resolved by your non-trivial architectural decisions.

this whole discussion about glitches has been based on artifacts of certain implementations!

We can understand glitches as a semantic artifact of observational delay, especially in branching time.

Once we attempt to scale FRP to distributed systems, there is no real means to avoid glitches entirely. I say this because the error is treating glitches as artifacts of the implementation; it would be more accurate to say that glitches are fundamental to physics, because we must assume many observers and time is relative to the observer.

Thank you. I gathered it was something specific, but it's such a widely used term, I couldn't figure out what it referred to.