Glitch: A Live Programming Model

A short 3 page workshop paper* submission. I've written to briefly describe Glitch. It has been a long journey from FRP signals to a model where I can actually write programs that I want to write.

Abstract:

Input changes are often handled by reactive and incremental constructs that are tedious to use and/or inexpressive, while changes to program code are not typically handled at all during execution, complicating support for "live programming." We propose that change in code and input should be managed automatically, similar to how garbage collection eliminates memory management as an explicit programmer concern. Our programming model, Glitch, realizes such managed time by progressively re-executing nodes of program execution when they become inconsistent due input/code state changes. Unlike many reactive models, Glitch supports expressive shared-state procedural programming, but with one caveat: operations on shared state must be undoable and commutative to ensure re-execution efficiency and eventual consistency. Still, complex programs like compilers can be written in Glitch using mundane programming styles.

* Apologies for using SkyDrive, it was just convenient. Use the download link and ignore the horrid Office 365 PDF viewer.

Lightweight Time Warp

In the paper you describe your use of 'undo' as a means to limit cascading rework and checkpointing as is experienced by Time Warp systems.

Aspects of my own designs were also inspired by Time Warp, but from the more recent Lightweight Time Warp (LTW) variations (Qi Liu, 2008-9). LTW uses a higher degree of modularity - more precise tracking of which messages must be eliminated, which subgraphs must be re-executed. (My RDP uses point-to-point time-varying signals instead of fire-and-forget messages. Since point-to-point signals naturally involve tracking long-lived relationships, precise dependency tracking was already implied.)

One nitpick: I don't like how you're using the phrase 'managed time'. You get to use that description after you're actually managing time. Right now, "Glitch currently assumes that execution is timeless".

By dmbarbour at Sun, 2013-08-11 18:18 | login or register to post comments

I wonder if my virtual time

I wonder if my virtual time comparison holds up in the long run. They are really quite different systems.

Managed change then?

I agree, time isn't really managed yet, just eliminated. Not until we have a story about events do we really have managed time.

By Sean McDirmid at Sun, 2013-08-11 20:02 | login or register to post comments

Managed change works well.

By dmbarbour at Sun, 2013-08-11 21:16 | login or register to post comments

non monotonic

I found a new problem with my model, actually I should have expected it given my foolishness in encoding iterative data flow analysis; consider:

a = true
if a or b: 
  c = true

if c:
  b = true

So c is true (because a is) and b is true (because c is).

Now we change the code:

a = false
...

When we re-execute the node, c is still true (because b is), while b remains true (because a is). Classic problem with non-monotinicity (e.g. datalog with negation). So David was right.

I've been able to deal with this problem before by having a negative phase that destroys relationships (undo only, no fresh do's) before moving onto a normal positive phase that does both, but in this case, b would still stick to true. The only solution is to apply order to what effects can be seen (using ordered stable addresses we have already) and forgo the ability to do a one pass compiler encoding or iterative data-flow analysis. We can then throw in time steps (as David suggested) to allow the assignment of "c" at "t" to only depend on the assignment of "b" at "t - 1", meaning b was never true at "t - 1" and we avert the cycle.

By Sean McDirmid at Sun, 2013-09-15 08:26 | login or register to post comments

Conditional state changes in

Conditional state changes in a reactive model can trap information. I used this pattern recently when describing sequencing of widgets in a reactive UI.

Naturally, it could be avoided if you ask developers to stick with straight expressions. (c = a or b; b = c;). When I need stateless reactive conditions, I model choice using sum types.

By dmbarbour at Sun, 2013-09-15 14:43 | login or register to post comments

We can avoid trapping state

We can avoid trapping state by not allowing for cycles; i.e. by lexically ordering all operations linearly and preventing earlier ordered reads from seeing later writes; this isn't easy if re-execution order isn't fixed and must be enforced directly in the runtime through an address comparison (we already use addresses to sort affects for presentation purposes in the trace log).

Now, we can allow earlier reads to see later writes by just bumping up t, a read at t + 1 can see all writes at t, so when the read is made, we notice that there is a difference between t and t + 1, and divide the node in time accordingly. Its not that difficult.

By Sean McDirmid at Mon, 2013-09-16 02:26 | login or register to post comments

Any conditional update in a

Any conditional update in a reactive system can 'trap' state. Reactivity is an implicit cycle.

Also, time will enable your system to trap state consistently, formally, and deterministically - which are all great properties. But if your primary goal is to "avoid trapping state", I'm not sure what you believe you're gaining from time.

By dmbarbour at Mon, 2013-09-16 02:57 | login or register to post comments

Maybe we are talking about

Maybe we are talking about different things. I'm just trying to ensure that if their a consistent interpretation of the program, that is what Glitch will eventually find. So when state goes from true to false, you want an interpretation of the program that is consistent with the state always being false (if a global time change). It all works out if we add support for time.

By Sean McDirmid at Mon, 2013-09-16 03:42 | login or register to post comments

Time for consistency is a

Time for consistency is a good idea. I recall arguing in favor of that point with you in another topic. :)

When you say: "interpretation of the program that is consistent with the state ALWAYS being false" - I am reminded of my designs for stateless stability. I.e. you're aiming for a resolution that is stable but ignorant of history, accepting the cost: non-determinism.

But that still can't happen if you have conditional state assignments.

By dmbarbour at Mon, 2013-09-16 03:55 | login or register to post comments

Time for consistency is a

Time for consistency is a good idea. I recall arguing in favor of that point with you in another topic. :)

I totally give you credit.

I am reminded of my designs for stateless stability. I.e. you're aiming for a resolution that is stable but ignorant of history, accepting the cost: non-determinism.

But my system, I think, completely deterministic...eventually. The only problem is getting rid of state cycles (using time) so stale state can be purged from the system.

By Sean McDirmid at Mon, 2013-09-16 04:01 | login or register to post comments

Lambda the Ultimate

User login

Navigation