Lambda the Ultimate

I know he works for them. I tried using prezi once, the results weren't pretty.

as if edward tufte has never existed.

is this relevant?

Elm vs. Bacon.js

That discussion seems germane.

I thought it was the SAC community that always ignored FRP, but it's hard to get enough context on the other in either community's papers. ideologically, one is concerned with reactivity and the other with performance. Since the problem domains don't tend to overlap, they exist in separate bubbles.

I don't believe SAC supports full dynamism, it isn't able to deal with arbitrary changes (like code changes).

Yeah, "full dynamism" is something of an overstatement. To be clear, I think you can use dynamically-loaded code to extend an FRP calculation in a language like OCaml that supports it. But I don't quite know what "full dynamism" even means, so that maybe makes it an overstatement on its own.

I do think that neither community looks at the other problems. I think the domains differ, but the implementations are structured in very similar ways, and I think that they are really thought of best as different points on the same spectrum, which makes me think it's a mistake for these communities not to connect more.

would love to eavesdrop on a conversation between Umut Acar and Conal Elliott. But some of us look at both, but we belong to neither community :).

I'm working on a system that handles arbitrary changes (including to code) via a somewhat constrained programming model (but still allows for semi-imperative updates), and am still trying to figure out how it relates to SAC (FRP is pretty obvious).

One way to construe the relationship between a reactive language that allows arbitrary code changes (such as Glitch) and one that only allows data changes (such as SAC) is to treat one as object language and the other as meta-language, i.e. use the latter to implement the former. Matt Hammer's Adapton paper does this for a simple language for arithmetic expressions. In extending this to a general purpose programming language, a critical question would be whether (and under what circumstances) the object language would inherit the incremental behaviour of the meta-language.

Maybe it's possible to give a "direct" incremental operational semantics for a language that supports arbitrary code changes, but the requirement to treat the syntax of the program as mutable data does seem to invite a staged approach.

Ya, I've been talking to Matt over email. From what I understand, Adapton is mostly about memoization, which still has a gap when it comes to reactivity. But there is a huge design space there that Matt is exploring (e.g. nominal vs. structural memoization).

Glitch doesn't require (or support) any special incremental operational semantics, instead relying on commutativity and undoability for everything. It also doesn't really memoize in the traditional sense, instead trying to minimize the amount of "damage" occurs (requiring less repair). Of course, most languages still don't fit this mold, but subsets do (so we can write a compiler using Glitch, and could live program the compiler if we wanted to).

I would say you're effectively giving an incremental operational semantics (of sorts) when you specify which effects are undone and which redone during an update. This is similar to imperative SAC, which propagates changes by rewinding the trace and undoing/redoing effects idempotently. But as you mentioned before, the SAC problem definition is essentially concerned with incremental performance, i.e. obtaining an update time bounded by the delta size. Like you, I prefer to keep separate the (declarative) notion of *what* was damaged from the (algorithmic) notion of how to efficiently repair the damage.

Are you familiar with the work on execution indexing? (I don't recall seeing this mentioned in your paper, but I haven't gone back to check.) If not, there's a brief overview of the literature and some discussion in my thesis, sections 3.12 and intro to chapter 6. Execution indexing is also concerned with what changes, not how to use that information for efficient update.

Has anyone had very much success in computing precise deltas based on a change? It works for simple problems (I.e. using subtract to remove an element from a sum), but in most domains I've seen (e.g. graphics), some form of replay rules the roost in one way or another.

Thanks for the tip on execution indexing, I'll look into it (and I always wondered what Bin did after he left Utah). Btw, are you coming to splash this year?

Here's my take on it (and it seems your philosophy in Glitch is similar). Rather than try to to "discover" precise deltas given arbitrarily differing executions, let's use the program delta to derive the execution delta, via a form of "differential" execution. Not only is computing a delta computationally hard (given only two executions represented as trees or graphs), but it kind of misses the point, namely that the execution changed for a very specific reason: because the program changed. (Assuming determinism.)

One approach (that I found worked reasonably well) is to decorate every node in the original program with a unique label and then combine these labels deterministically during execution so that every node in the execution is decorated with a composite label tracing it to the original source code. Under some but not all circumstances, this can yield very precise deltas: as you shuffle bits of code around, the corresponding parts of the execution shuffle around. By contrast, trying to "discover" efficient execution deltas without exploiting the program delta is not only hard, but not even what we want.

And this approach works fine for GUIs: you compute changes in the visualisation by using your differential execution on the visualisation code. A nice opportunity here is to animate UI updates by exploiting specific information in the delta such as moves. But as always, there's a big difference between knowing how to compute a precise delta and knowing how to compute it efficiently.

Yes, I'll be at SPLASH. Looking forward to your talk!

I don't understand very clearly, but let me drag out a couple of examples of what I think is analogous to what you are talking about.

In graphics (well, in math also) there are two ways to compute a derivative (to do things like lighting). If you have access to the expression and it is simple enough, you can get a precise derivative via symbolic differentiation (see Conal's Vertigo paper on this, really cool). However, often you just wind up sampling two points to compute a cheap but imprecise slope. However, in this case of an incremental programming model, I'm not even sure what we would even do with the derivative.

Or consider physics. A physics engine is basically a very flexible incremental constraint solver. If you express your programs as physical constraints, changing the program will cause the engine to start with the existing solution and compute (over time) a new solution that is completely animated. So if I add a spring to constrain the movement of a particle, that spring probably starts very extended as the particle was previously not under its influence. Then the spring pulls it, possibly oscillating a bit, and eventually reaching a stable properly constrained state. Or things could go horribly wrong (the system isn't stable, or is over constrained).

I've mentioned before that a physics engine could be the basis for a live programming-enabled computer, but this is like saying "constraint programming models" would be appropriate, and they have some real limitations in terms of the programs that could be expressed.

SAC has some overhead, e.g. for keeping extra state about previous values, and for comparing said values. To benefit from SAC requires that this overhead pay for itself by resulting in less redundant computation, e.g. perhaps we need to limit updates to 10% of the graph before it pays for itself. (This cost-benefit threshold will vary based on the implementation.)

It turns out that, for many domains to which FRP is applied - e.g. robotic control loops, simulations, animations, or music generation - a significant portion of the graph is necessarily recomputed, to an extent that a general application of SAC is a dubious proposition.

AFAICT, this is the main reason SAC hasn't made much headway with FRP. It isn't as though FRP developers are unfamiliar with the idea (we've all used spreadsheets). And we're certainly interested in performance.

Ad-hoc applications of SAC, specific to some problems or domains, remain useful. Many FRP implementations do offer some means to explicitly address the recomputation issue, e.g. in terms of memoizing computations or filtering events. Something based on automatic profiling of the application might be nice, but FRP systems generally haven't matured enough to explore that possibility.

For GUIs, it turns out we can get 80% of the benefits for 20% of the effort by using something like React or D3 - e.g. computing a minimal change-set (a diff) for rendering. Other relatively stable systems can also benefit from such techniques, e.g. minimizing the change in a constraint solver's solution as the constraints vary reactively.

Interesting comments! I find it striking that the motivation seems to come from GUIs, given that it seems to me that SAC and FRP should both have applications far outside of GUIs.

One disagreement: I think "general application of SAC" is a clear reality, from the simpler version that shows up in spreadsheets, from more complex versions that show up in our work at Jane Street, at least. And I've discussed with people in other companies (Twitter, for one) that have developed similar libraries.

Has any work on SAC addressed reactivity?

Change propagation is the reactive component of SAC. The usual story (as told originally in Acar's thesis) is that change propagation is "dual" to memoisation. I don't know whether that can be cashed out in any formal sense, but certainly the two seem to be complementary. The incremental semantics starts by propagating changes through the stale trace, until it encounters a memo-miss. Then it switches to fresh evaluation until it encounters a memo-hit, i.e. code it ran last time. But the memo-hit may yield a trace which is stale, and so the update switches back to change propagation. These two modes work somewhat like coroutines which together incrementally repair the computation. (Matt will do a better job of explaining it, though.)

Have you checked out Froc? http://ambassadortothecomputers.blogspot.nl/2010/05/how-froc-works.html

"general application of SAC" is a clear reality

SAC certainly has applications to a lot of different problems. But SAC is a lot like parallelism: to improve performance, SAC must be applied at the right boundaries, with the right granularity, sensitive to update frequencies and which values tend to change together, is not especially compositional, etc.. You won't improve performance if you slather SAC over every algorithm like a secret sauce. I would describe effective application of SAC as ad-hoc, not general.

He's a former student of Umut Acar's, who has worked on SAC and is also very interested in interactive programs. Here's a link to his webpage.

I've had some very interesting conversations with him, and while his thinking has likely evolved since then, one takeaway I had from him is that the natural API to SAC is imperative. Basically, each computation naturally gives rise to a dependency graph, and the innovation of SAC is to let you name, store, and refer back to the nodes of that graph, so that you can control precisely which recomputations should (or should not) happen. Some early work on SAC put these nodes in automatically into a functional program as part of compilation, but to get exactly the right efficiency story, it really helps to make changeability explicit.

In contrast, FRP tries to offer a pure interface to interactive programs -- you want to say, "FRP is just ordinary functional program with a slightly peculiar typing, so most of your FP instincts carry over unchanged". This is in tension with what SAC wants you to do. It's not an impossible tension to overcome (my LICS 2011 paper with Nick Benton essentially uses one of the early versions of SAC as the implementation layer for an FRP system), but IMO taking a pure FRP view does not let you use SAC to its best advantage.

IOW, a fully satisfying story on integrating SAC and FRP has yet to be told.