## Commutative Effects

I'm designing/implementing a new semi-imperative programming model called Glitch that is based on optimistic execution and eventual consistency. The idea is that a computation can only performs imperative effects that are undoable and commutative so that (1) they can be rolled back when re-execution deems that they are no longer performed and (2) that an effect can be installed in any order so the computation can be decomposed into parts that can be executed in arbitrary order. Few effects are actually commutative, but we can hack some to act commutatively with extra restrictions or data; examples:

• Adding to a set is naturally commutative.
• Aggregation sub-operations (increment, max) are naturally commutative (though max is not easily undoable...).
• Setting a cell element or map entry are not commutative. However, if we enforce "set once" restrictions dynamically, then they appear commutative with the caveat that a second conflicting effect can fail. We must then associate effects with stable execution addresses to determine which effects are conflicting, and which effects have simply changed in what they do.
• Appending a list (or an output log) is not commutative. However, if we order execution addresses, then we can translate append into commutative insertion into a set whose elements are automatically sorted by effect address.

I was wondering if anyone has used commutative effects before? The closest I have found on this topic concerns "commutative monads" where effect ordering doesn't matter. However, they don't seem to be doing many interesting things with them beyond relaxing ordering constraints for parallel computations, and they also don't seem to talk about many interesting commutative effects (just Maybe and Reader?). Also, I wonder how users would feel if they were given a language that restricted some to just imperative effects...would it be overly restrictive or a nice addition to an otherwise pure-ish language?

I'm still writing this up, but the system has been expressive enough for my live programming work (e.g. it can be used to write a compiler).

## Comment viewing options

### Reactive demand programming

Reactive demand programming (RDP) requires that effects be commutative and idempotent. In some respects, effects in RDP are less expressive than your proposed model (e.g. I can't have "increment"). In other ways, they are more expressive (e.g. no issue recording a "max" value).

Often, new idioms are required to solve old problems - e.g. to model a vote, instead of tallying updates into an incremental sum, I might add a GUID to a relevant collection then compare collection sizes. But I haven't encountered any problems that cannot be solved within these constraints. I imagine you'll experience similar situations with Glitch's constraints.

(Observation: Clever developers manage to get damn far using pure functions. Hypothesis I: Give them some carefully constrained effects and they can accomplish anything. Hypothesis II: If the effects are constrained very carefully, they won't even need to give up FP's equational reasoning.)

I have developed various state models based on RDP's constraints, since imperative state variables are a poor fit. You might encounter similar troubles, e.g. because arbitrary observe-and-update patterns are not commutative.

Re: commutative monads - you might also check out causal commutative arrows, though that paper is more about how you can optimize the resulting program rather than how to model useful systems.

### Effects in glitch are

Effects in glitch are logged, so idempotence is not necessary (re-performing an effect that is already installed is a no-op), though idempotence is of course also achievable with the required support for undo (undo effect, redo effect).

Observe-and-update is indeed a problem, consider this code where A and B are shared state cells:

A = B
B = !A

As the order doesn't matter, the effects will continuously oscillate and prevent the system from becoming eventually consistent. I'm not sure how to tackle this problem yet, so I'm punting. Still, I think relying on shared state and commutative imperative effects is the way to make such systems appealing to traditional programmers.

What can you observe in your language? Could you write out your definition of commutative? I fail to see why it would make sense to reorder the program S.add(b); a := S.max(); in the general case even if the individual operations (add, max) commute with themselves.

Spreadsheet languages contain some limited effectful operations such as getting a random number, which probably falls under your definition of commutative. Non-termination is another commutative effect.

### Defining Commutative Effects

Effects are formally commutative if the expressions that cause them can be listed in any order without affecting the meaning (observable behavior) of the program (i.e. it really means something closer to "commutative expression of effectful subprograms"). Of course, practical systems are modular systems, and we want to achieve commutativity without relying on global white-box analysis. Thus, in practice, effects are commutative if the implementation can process 'updates' in any order and have the same observable result.

Naturally, for the expressions S.add(b); a := S.max() to commute across the ; operator, it must have the same result as a := S.max(); S.add(b). This could be achieved via retroactive correction of a (essentially treating S as a reactive collection, and a as a reactive variable). Alternatively, it could be achieved by formalizing how the sequence operates over time, e.g. S.add(b) @ t; a := S.max() @ t+1; S.add(c) @ t+2 has the same meaning as S.add(c) @ t+2; S.add(b) @ t; a := S.max() @ t+1.

The latter approach potentially violates the practical concerns of modularity and extensibility. In a large program, we'd essentially need to study every expression before selecting the earliest one. In an open system, we never have all the modules, so we'd never know which operation should apply first. But we can compromise just a little, in a manner that doesn't hurt any use-cases. We can guarantee that expressions and updates don't get too far out of temporal order. With this guarantee, open and modular implementations are feasible. We can buffer commands and sort the buffers temporally, or use speculative evaluation with limited rollback and replay.

Spreadsheets tend to address only spatial computations, i.e. they don't readily model how things evolve over time. They aren't very useful for general purpose programming.

(That said, it wouldn't take much to tweak spreadsheets into something general: the formula of each cell could be interpreted as a rule that defines its next state in terms of the current states of referenced cells (with possible indirection, where cells name other cells). Basically, you'd have a fully programmable cellular automaton. Might be a fun project.)

By addressing both space and time, there aren't very many limitations on what can be achieved using languages with commutative effects. We can manipulate tuple spaces, databases, constraint systems, and simple variations of state machines (which label state transitions with logical propositions on a set of signals, instead of atomic events). We can model scene-graphs and render to screen. We can model sounds and compose them. We may need different idioms and designs, but we can accomplish whatever we set out to do.

In my own work, I find idempotence to be the more significant constraint. For example, two independent calls at the same time to new Dog() are commutative, but not idempotent because they return two distinct dogs. To preserve idempotence, I use an idiom closer to get Dog("fido") so I can have more than one dog so long as I give each a distinct name.

Glitch has this restriction also, but is able to satisfy it transparently. Each position in the program's execution has a unique address that remains stable even as code and code execution is added and deleted around it. This address is then used as a key for allocations and effect installations, so we can determine if the effect/allocation exists and can be reused, or if it needs to be created from scratch.

These addresses are also useful in live programming UI, as they provide a map of execution that is consistent across changes.

Max is not naturally commutative, but there are a couple of ways to realize adhoc commutativity:

(a) Insertion into a sorted set, take the last result as the answer.

(b) Keep track of "max" and have all other candidates become read dependencies. When the "max" element changes, invalidate reads and re-run all nodes that proposed candidates.

(a) sacrifices space and (b) sacrifices time.

Note that there is no notion of computational time in Glitch, everything is just data-flow even if re-execution is technically ordered and imperative. So writing A(); B(); is the same as writing B(); A();, if A reads some state modified in B, the node will simply execute twice, preserving effect operations in B so they can be seen by A the second time around. Only data-flow is really relevant, just like in a pure functional language.

There will be a notion of event time in Glitch, but we haven't gotten there yet; the idea is to use some form of Fujimoto space-time memory. This should be lots of fun, as effectful operations will have a start and end event time, as will node re-executions, which can split when the state that they read splits.

Non-termination might be a commutative effect, but I'm not talking about those kinds of effects, I'm only interested in operations that cause imperative updates.

### Stability in presence of dynamic behavior

Idempotence is motivated for many reasons in the design of RDP:

• stability for resource manipulation across changes in dynamic behavior, especially in context of staged programming (where we might deal with macros, scripts, plugins, etc.).
• nice equational reasoning and refactoring properties (between commutativity and idempotence, RDP users have most of the advantages as pure functional programmers)
• a plethora of potential optimizations - eliminating redundant code due to macros, eliminate redundant code caused by code distribution, content delivery network style optimizations, replicating code to improve reliability or control bandwidth

It seems you're interested primarily in the stability issue, but primarily in the context of live programming. (I treat live programming as a useful application of staged dynamic behavior.)

Does Glitch address any causes of code change other than manipulation through the UI? Also, does Glitch support macros, and if so do you have some way to stabilize keys assigned in a macro expansion?

Re: "there is no notion of computational time in Glitch [...] we haven't gotten there yet" - interestingly, in most logical systems, the extensions to support 'time' are more about garbage collection than any other feature. That is, it's always possible to model time in terms of space (using a list, for example) but making the old states go away when you're done with them requires implementation support. :)

### By "stable", I mean that the

By "stable", I mean that the addresses are reporduceable; as long as you don't add a loop around a statement, its address when it executes again in the same calling context will be the same. Glitch only supports code changes thought the editor, though one could imagine external code change support with some extra effort. Glitch is a run-time system, so it doesn't have any notion of macros. The language layered on top of Glitch could, and it is the language's responsibility to provide Glitch with stable addresses (e.g. using Glitch in plain C#, I have to manage all addresses manually).

I'm thinking mostly about "virtual time" and "space-time memory" from the distributed simulations community. There is some point when all state related to time e can be collected, which is when no nodes at or before time e is waiting to be cleaned. Of course, if you want to support live programming, state related to time e can never be collected, but then the program should be finite anyways (e.g. a fixed amount of video frames as input to a Kinect-style program).

### long running live programming

Live programming is often developed with an 'ideal': that the current state is consistent with having run the application from the beginning with the current code. I.e. the code change logically occurs at the beginning of time.

But if our code interacts with external services or resources - database, filesystem, robotic motion, etc. - then naturally we cannot achieve this ideal. We must instead acknowledge that the code changes at some point in time. Given this situation, 'schema' stability for the external state becomes very important. I.e. we can't just rename tables or use brand new naming conventions for files, without losing a lot of work. If we want to change those things, we need to plan a transition.

But, aside from schema transition (which is a painful problem, but one with known solutions) I don't see much difficulty with live programming for long-running applications, tracking when the changes occurred. And there are many use-cases for such systems.

Of course, there is still a role for operating on fixed-sized histories (e.g. last ten video frames). There also might be a role for 'rewinding' the state of an external system while we debug our code.

### Right. Real-time execution

Right. Real-time execution should be treated differently from recorded execution, with different benefits in each. The former can run forever, but history is necessarily deleted and you can't really change the past, just the present and the future. Glitch could also be useful where live programming isn't the goal, to hand incremental change or to run on parallel/distributed hardware, though I haven't really gotten into the latter yet. In that case, you'd want to free the past as soon as it is no longer needed for consistency, though this is necessarily hard in a distributed system (with well know solutions in distributed parallel simulations).

### Update Order

Do you address the update ordering problem in Glitch? It's a common issue in dataflow systems, and reasonably well illustrated in another topic.

For imperative code, it seems we might try to 'learn' dependencies between operations based on previous executions. If we perform a topological sort on the resulting operations (perhaps to some atomic unit, and arbitrarily breaking loops) then we could achieve something near optimal with regards to avoiding redundant computation.

### It is all in the name...

...Glitch! We don't address the update ordering, but keep processing nodes until they converge. Dependencies are traced dynamically, and all we know about a node is whether it might be inconsistent because one of its dependencies changes, or its code could have changed.

No topological sorts are done, so the order of re-processing might not be (and probably is not) optimal, but the system is able to tolerate spurious inconsistencies anyways, and only eventual consistency is guaranteed. For a small change, the redundant computations are not a very big problem, however it is kind of scary when we process a bunch of nodes in mass. I'm not sure what the performance implications are yet, but haven't noticed any real problems yet. We might be able to tweak ordering a bit dynamically, but I haven't tried anything yet.

This is how my work primarily differs with concurrent revisions, self-adjusting computation, and many FRP systems, which see redundant computation as more or less evil and incorrect. Getting rid of this requirement greatly opens up what we can do with the system...including handling code changes.

### Performance for poorly

Performance for poorly chosen update ordering can be exponentially worse than the best case, in a system without loops. With loops, it could be infinitely worse, though it isn't difficult to at least guarantee progress.

In practice, it's often not that bad because (a) dependencies are rarely very 'deep', and because (b) developers often resort to some form of choking to hack around the problem whenever they encounter it. But even so, it can be several times worse, and choking often just slow convergence down.

The worst case I've heard about involved some C++ observer-pattern code in an application that grew organically over years. A few tweaks (leveraging thread ids in some arcane fashion) to track dependencies and smartly choose a callback order was able to achieve two orders of magnitude performance. (As is often the case in industry, nothing was written about it, the motivations weren't documented, and the solution was quietly forgotten when the application was overhauled, and eventually reinvented.)

Even if redundant computations aren't evil or incorrect, they can be inefficient. For now, perhaps just put it on a to-do list. :)

### Right. Lets solve the

Right. Lets solve the problems as we encounter them rather than worry about what could happen. I already have to optimize a bit to eliminate hard state and to make sure operations are distributed evenly in the "right" nodes. None of this would be solved with topological sorting.

There can be cycles in the dependency graph, e.g. For A(); B();, if A depends in an effect made in/by B() and these are in the same node, the node will depend on itself and run at least twice whenever it changes.

### False and Real Loops

As you mention, we can have a sort of "false" loop due to coarse-grained grouping of expressions (e.g. your nodes, or my partitions). We can also have "real" loops due to shared references (e.g. if A() influences something B() observes and vice versa, whether or not they're in the same node).

False loops will tend to resolve themselves. Real loops require some more consideration, and are among my reasons for supporting logical delay. With delay in a loop, I logically know how frequently loops must run, and I can schedule processing accordingly (limiting speculation relative to real-time), rather than just running the loop as fast as the CPU can.

Disciplined developers can avoid a lot of unnecessary 'real loops' by design. But they often exist in various natural use-cases, e.g. if contributing to and searching the same registry or tuple space. This might become an issue for Glitch.

It's already a theoretical problem, but not one in practice yet. A = B, B = !A will put the system into non convergence. I'm still not sure how to deal with it yet, an implicit delay for backward state references would work, but would feel ugly.

### Two relevant works

You probably know about Jonathan Edward's Coherence (e.g. the Onward 2009 paper), but it seems like a fairly relevant reference for related work.

Another is Lindsey Kuper and Ryan Newton's 2013 â€œLVars: Lattice-based Data Structures for Deterministic Parallelismâ€. The idea is that allowing only a monotonic form of update to shared values gives you deterministic concurrent programs. I like to see that as a generalization of Peter Van Roy's deterministic concurrency through logic variable unification (with blocking reads) to arbitrary lattice domains.

There is a correspondence between the usual "order" view of lattices (defined by an order, so monotonicity is natural) and an "algebraic" view where we pick meets (or joins) as the defining operation, that needs to be commutative, associative and idempotent (but not necessarily invertible). That correspondence should allow finer-grained comparisons.

I think it would be interesting to break your notion of effects into separate parts that can be studied separately. I suspect if you temporarily remove cancellability, you get something essentially like this deterministic concurrency.

### Thank you, I was unaware of

Thank you, I was unaware of the LVars work. I think they limit themselves too much by going with monotinicity: going forward has always been easy, that is just iterative data flow analysis. The interesting challenge is removal of information or not necessarily monotonic but expressive computations.

### LVars sounds front-page

LVars sounds front-page worthy. Thanks for bringing it to my attention.

### Two more

While we are on the (off)topic ...

The Bloom language (Berkeley) also supports lattices.

Also of interest: A comprehensive study of Convergent and Commutative Replicated Data Types [PDF] by Shapiro etal

Neither of these help Sean's query though, since he's looking for reversibility as well.

### Thanks! Replicated data

Thanks!

Replicated data types are quite similar to retroactive data types, which include reversibility.

Bloom looks very interesting and related. Its been mentioned to me before, but I haven't taken a good look at it yet.

If we look at Glitch from a lattice perspective, it provides a solution to "information removal" (vs. adding information) that existing iterative lattice-based analyses don't seem to deal with without redoing the analysis from scratch. So glitch is seemingly non-monotonic on additions (given that retraction can occur even if new things are added) but also can deal with removal (which fundamentally requires retraction). I've looked for algorithms that can deal with information removal, but haven't found anything yet.

Non-monotinicity also gets us into trouble though, as a Glitch program isn't guaranteed to terminate, and might loop forever for non-local reasons.

### One can keep monotonicity by

One can keep monotonicity by modeling retraction as taking logical time. The result can still be non-terminating, but at least it can achieve consistency for any given time.

Reversibility features seem like an orthogonal issue - useful for efficient, incremental, or speculative computations, regardless of how retraction is modeled.

I've thought about this. The problem is that your logical time will keep increasing forever without a stable solution given misbehaving sets of constraints (e.g. A = B, B = !A). The problem is then not solved, merely pushed off into time.

### Many problems are solved -

Many problems are solved - well-defined behavior, consistent interaction with other periodic behaviors, effective performance control (by limiting speculative evaluation to a few steps), and so on. The problem of creating a stable system is not solved, but I think that is not the only problem worth solving.

In many domains - those that need to deal with time and interrupts - the instability might not even be a 'problem', but rather a mechanism to express temporal behavior. (This works well if logical time is bound to real time in some manner, e.g. best effort to run at 200Hz, or logical delays recorded as a rational number of seconds.)

### I get what you are saying,

I get what you are saying, but I can solve most of those other problems without the use of time, except of course for the ones (real ordered events) that require time. As soon as general computation requires time, the system becomes much more complicated and loses its nice properties (e.g. those related to debugging). Also, if we are ever going to tackle distributed computing, "consistent at time t" has to mean something.

### The complications you

The complications you attribute to time, I think are more aptly attributed to local state. If state is external to our programs, then updating program code does not directly risk losing information, or introducing uninitialized state, or entering an inconsistent state.

Glitch gets away with using "local state" because Glitch isn't truly stateful: Glitch doesn't accumulate information over time.

Of course, local state does have some nice properties: implementation hiding, exclusivity, a natural ability to embed in a code canvas. But all these benefits can be had without local state. We could instead use uniqueness types to exclusively bind external state.

I think it worth keeping 'time' even if it means taking a critical look at those other complicating factors. As far as I can tell, most problems humans are interested in somehow involve time: sensors, HCI, actuators, world models, user models, and so on. When debugging systems with time, a frozen view isn't all that useful.

Also, "consistent at time t" is a nice ideal but doesn't need to mean anything for distributed computing. There are a number of weaker but sufficiently useful consistency properties. The ability to know that all our inputs for time t will have arrived by time t+8 could be very useful, for example - even if it means rejecting some inputs (modeling a network disruption). Another useful property is snapshot consistency: that updates from a particular source are batched atomically, such that we only see consistent intermediate views per-source (even though this allows larger scale inconsistencies).

### I'm not against time, I'm

I'm not against time, I'm against abuses of time. Glitch has state, state changes over time; but it should not change if time doesn't pass! I suspect we will be talking past each other until I show you a version of Glitch that supports time (as I said before, via space-time memory) and state that changes over time. Then there are the matter of input state that changes based on external stimulus, but kicking encapsulated state out into the external environment is just a bad solution.

Computation should not consume time. Adding in artificial delays and steps is an ugly solution to dealing with non-convergence, and doesn't actually solve the problem, just puts the non-convergence up to successive time steps.

If you want to do anything irrevocable in a distributed system, it has to be done from a consistent frame of reference. t+8 is not consistent for resolving event0 as you must then worry about events 1-7.

### kicking encapsulated state

kicking encapsulated state out into the external environment is just a bad solution

Do you have a convincing reason to make this claim?

Encapsulation isn't intrinsically good; it can be discarded if the benefits it offers are obtained by other means. And they can be.

Further, it seems to me that all state is ultimately part of the external environment, whether we acknowledge it in our models or not. I think a cleaner fit to model it.

Glitch has state, state changes over time; but it should not change if time doesn't pass!

I don't know how to formally define or recognize state without time. Not in a way that would also exclude pure values and constraint models. Do you have such a definition?

Computation should not consume time.

The fundamental difference between 'computation' and 'math' is that computation is a physical process. Of course it takes time. And energy. And money. Similarly, information always has a physical representation. Computation is the mechanical mathematics. We should embrace this.

artificial delays and steps is an ugly solution to dealing with non-convergence

So is Glitch's current solution.

Time is a great way to address non-convergence that is a natural part of the model. We just use a different name for this intentional use of time, such as "temporal recursion". Time won't eliminate errors from the model. But it does make those errors interact much more consistently and deterministically with the correct parts of the model. And that is a very useful property.

t+8 is not consistent for resolving event0 as you must then worry about events 1-7.

Correct. We might not have a guaranteed consistent view of what t+8 should look like until we reach t+16. But at t+8, we do have a stable, consistent view of what t+0 looks like. Therefore, we can safely 'commit' any effects or state associated with t+0. In practice, stability can often be computed at a much finer granularity, i.e. on a per-expression basis. And by use of explicit delay, we can shift the reference time.

Also, waiting on stability is only useful for some problems. For others, even involving irrevocable action, latency might be more important than consistency. Inconsistency can be mitigated if speculated values are often close to the actual values.

### Interesting debate, I'll

Interesting debate, I'll have to let your argument sink into my head more. Also, I think we are making some progress in understanding this area (in addition to Jonathan Edwards), it might make sense to list options in the design space for dealing with time/state/change in more detail.

I don't know how to formally define or recognize state without time. Not in a way that would also exclude pure values and constraint models. Do you have such a definition?

Perhaps I should use the term memory rather than state? The point is that progressive change doesn't make sense without time. If we look at the "state" of a program for one point in time, there is only one of those. This is important to me for debugging reasons, and I think completely achievable.

The fundamental difference between 'computation' and 'math' is that computation is a physical process. Of course it takes time. And energy. And money.

Let's make computation like math then and suck the time component out. This is what pure functional programming does, and this is what Glitch does for a more imperative programming model. It is a very important abstraction that grants programmers a lot of reasoning benefits.

But at t+8, we do have a stable, consistent view of what t+0 looks like.

There is no way to "know" when we will have a consistent view of t+0, so why delay it? Rather t+0 is t+0, if some operation must add time to the computation, then let it do so explicitly as a new event that can then be ordered into the execution. But let's not go crazy and add time in all over the place, that would be very difficult to manage, especially if your system is optimistic.

### There is no way to "know"

There is no way to "know" when we will have a consistent view of t+0, so why delay it?

There are ways to know.

For every primary input stream to a system - every sensor, for example - we can have very precise knowledge about how much of its information is stable (in most cases it's "I don't send you unstable values, stupid" - though speculation all-the-way-down to the hardware would be pretty useful). This information can be metadata as part of every expression to which they contribute. Even connections for remote processes can track this. A late arriving process to a system can simply have its logical connection time delayed a little. Conversely, a remote connection that fails to "keep up" can simply be disconnected - and we can, for consistency, retroactively pretend this happened at t+0.

The reason to 'delay it' is so we have a less hostile, more forgiving environment - one that tolerates hiccups in the scheduler or network, one doesn't disconnect us unless we really mess up or try to ride the bleeding edge for latency.

(Similarly, we should tolerate and forgive a small, controlled amount of inconsistency, when the problem allows it. We don't need a "zero tolerance policy" for inconsistency in most problem domains, but the other extreme is also bad.)

let's not go crazy and add time in all over the place, that would be very difficult to manage, especially if your system is optimistic

Time is only difficult to manage when you use it in a spotty or ad-hoc way. In those cases, programmers must deal with time explicitly. But if time is everywhere it can be shifted into the background, part of the language, implicit (but still formal). It can be managed by the language.

Pervasive use of time is useful for optimistic systems: the scheduler can be aware of time, and can control how much speculation is performed, and focus resources on the processes that seem to be lagging a bit (processing older times). Time is a very easy metric for tracking relative progress.

suck the time component out. This is what pure functional programming does [..] a lot of reasoning benefits

Precisely which reasoning benefits would be lost if we include time with pure functional programming? When I actually take the time to sit down and list what I believe to be the beneficial properties of pure functional programming, I can't find any that depend on the absence of temporal abstraction:

• commutativity - enables laziness, disorder, parallelism, rearrangement of 'let' expressions, easier refactoring and abstraction (especially of behavior templates; frameworks)
• idempotence - enables common sub-expression elimination and factoring; conversely, (together with determinism) also enables replicated computations which can be useful in distributed systems to improve latency or bandwidth at the cost of CPU
• lack of side-effects - enables sub-expressions whose values are not necessary to be removed; conversely, also enables computing values that are not necessary, which can be useful for speculation; dubious benefit, IMO, compared to costs (need to learn and use a separate programming model to support effects, and a separate composition model to integrate open systems)
• referential transparency - enables any expression to be transparently assigned to an intermediate variable without changing the program's meaning
• determinism - same output for same input, very useful for debugging, regression testing, and replicated/mirrored computation

And, indeed, it seems that pure functional programming with time - such as FRP or pure list stream processing - also have these benefits. With RDP, I keep everything but 'lack of side effects' and also eliminate local state. (Pure FP can accumulate state via folds or integrals over time.)

(I also feel that 'composition' is a benefit of FP, but I think that's more a consequence of FP's programmer culture than a fundamental property. However, composition is simplified by the aforementioned properties.)

this is what Glitch does for a more imperative programming model

The imperative programming model does time horribly badly. Since time is implicitly sequential for every operation, you cannot refactor or rearrange subprograms without changing its temporal meanings. Duplicate expressions are implicitly parameterized by different times. You cannot directly express that two operations or transactions should logically occur at the same time.

To study the imperative model and blame time seems analogous to listening to incompetent karaoke then blaming sound. Yeah, Glitch can get some cred for separating time from imperative (together with careful user discipline). However, 'time' is more essential to a wide variety of problem domains than 'imperative' will ever be.

### The reason to 'delay it' is

The reason to 'delay it' is so we have a less hostile, more forgiving environment - one that tolerates hiccups in the scheduler or network, one doesn't disconnect us unless we really mess up or try to ride the bleeding edge for latency.

We are not arguing about whether a decision should be delayed, just if the explicit clock (responsible for event ordering) should always advance even if no external event comes in from the outside. My position is that the clock should only advance in response to an event, we shouldn't be advancing it so we can encode what are essentially flip-flops.

Precisely which reasoning benefits would be lost if we include time with pure functional programming?

Again, I'm not arguing against the inclusion of time, just the inclusion of time to sneak in progressively changing state to computations that otherwise don't need it.

Yeah, Glitch can get some cred for separating time from imperative (together with careful user discipline).

Glitch doesn't require much user discipline, they are limited to a set of primitive operations that conform to commutative/undoable semantics.

However, 'time' is more essential to a wide variety of problem domains than 'imperative' will ever be.

I'm not disagreeing with you here. I just don't think we should add time to cases where it is not necessary, especially when it doesn't even solve the problem at hand (non-convergence). I also do not think "imperative", at least the restricted form I'm using in Glitch (maybe its not reasonable to call that imperative anymore?), really harms the situation either way.

### the clock should only

the clock should only advance in response to an event, we shouldn't be advancing it so we can encode what are essentially flip-flops

I think there are two separate issues:

• should we allow our clients to encode flip-flops?
• if we allow our clients to encode flip-flops, what is the correct way to do it?

My points have regarded the second issue.

I can understand that you might wish to limit the expressiveness of your system. Glitch clearly isn't intended for encoding cellular automata, simulations, control systems, operating systems, video games, and other systems where advancing without a user event is the right course of action.

don't think we should add time to cases where it is not necessary

I believe there are many benefits of using time and state to explicitly step pure batch-processing computations. These include:

• fine-grained logical process control; e.g. ability to pause, persist, resume, or kill a computation without OS-level hacks to bypass the computation model
• fine-grained logical performance control; ability to precisely specify how many resources (steps, etc.) are granted to each computation when there are many to perform concurrently.
• incremental feedback about progress; greater ability to animate and debug the computation process
• well-defined, safe integration with computations that do need time: almost every pure computation is performed on behalf of an impure system that has real-world time constraints. A pretense that the pure subset of computations are instantaneous seems often more harmful than helpful.

Glitch doesn't require much user discipline

It requires less than plain old imperative, for sure. :)

### I can understand that you

I can understand that you might wish to limit the expressiveness of your system. Glitch clearly isn't intended for encoding cellular automata, simulations, control systems, operating systems, video games, and other systems where advancing without a user event is the right course of action.

This isn't true at all, and I said nothing about events being limited to "user events." The whole point of our Deja Vu work was to advance time on each frame of Kinect video input. In a physics simulation, the external event is a simulation tick. That I haven't added time to Glitch yet doesn't mean it won't exist, and we've already talked about how to do it.

### Time is external, like your

Time is external, like your physics simulation tick. What distinction were you imagining?

### Computation does not consume

Computation does not consume time, it rather needs to catch up to it (and its effects).

### In an ideal world, we could

In an ideal world, we could compute an unlimited amount of information in a bounded amount of space and time.

But that is not how things 'are'. It would be silly even to say it's how things 'should be' (like saying "the speed of light 'should be' a million times higher because those latency issues would be so much easier").

Computation does consume time and space - neither of which are internal to the computation. Time is also necessary to consistently model identity in non-monotonic computations, and to integrate time-varying effects. That is our reality. If we pretend otherwise, physics will beat some sense into our computations and leave them in a sorry state.

### I was talking about the

I was referring to the illusion/abstraction that Glitch as a programming model provides to the programmer. Of course computation actually takes time and space, just like memory must be allocated and free, but the garbage collector hides those details from the programmer. I'm not sure if it will work, but I'm trying hard and initial results are decent enough.

Haskell does something fairly similar, except they don't really focus on change and consistency management (beyond FRP and STM).

### It seems like a nice

It seems like a nice illusion. It even works reasonably well at small scales, under conditions where unbounded resource usage and latency isn't a security or safety risk. Glitch will work well enough for Glitch's use-cases.

Nonetheless, I believe that modeling long-running computations (e.g. ray-tracing, sorting large files, never-ending flip-flops, etc.) as explicitly taking time, will ultimately serve those same use-cases (and their programmers) more honestly and effectively.

I have a belief about abstractions: it is not okay to have "false" abstractions. It's okay for abstractions to say less, to be imprecise or polymorphic. But. Abstractions should not be outright wrong. Humans are too happy to buy into a pretty lie.

I feel the FP communities have done a good job of 'keeping it real' for most of their abstractions (monads, pipes, iteratees, etc.). Getting away from lazy IO (unsafeInterleaveIO) was a great move.

(I'm not fond of GC. I'd prefer to see substructural types or environment types used to statically enforce proper manual collections, and use of types to control against introduction of data cycles.)

### leaky abstractions

As Spolsky would say, abstractions usually leak like crazy. GC is a good example: it works well until it doesn't, but many programmers still love it and they even included it in the retro Go language as a must have. Programmers love lies if it makes their life easier...until it makes their lives harder, then they hate them!

In Glitch, the computation can take a long time, the system will still continue in a knowingly inconsistent state...when the computation is done, the result is integrated and the system becomes consistent with it. This is a nice property, and I believe makes the abstraction tolerable for many use cases.

Time can be added artificially to the program as randomly injected events; e.g. we could create an event that represents when a long running computation has been completed, simply so the time when it started can become consistent (and other events in between can be resolved) without the computation completing. There is nothing really wrong with this, but I don't think it should be a enforced transparently by the programming model. The default should be "no time", and then time can be added back as needed (e.g. to ensure potentially conflicting events can be resolved while a big computation is running).

I think our philosophies are a bit different, but its been a good conversation. This is one of my big topics for 2014

### Programmers love lies if it

Programmers love lies if it makes their life easier...until it makes their lives harder, then they hate them!

That's true. :)

The problem is that programmers also love pretty lies when it makes their lives harder. It becomes the 'devil they know' - a love-hate relationship, but one they understand and are reluctant to give up. (I can't imagine many Go programmers have even heard of linear types as an alternative to GC.)

Even when I don't entirely agree with your philosophy, I share some of your vision and I do admire your consistent ability to implement your ideas. I finished proof of concept for RDP six months ago, then I stalled when I found myself reluctant to proceed with Haskell. Now I'm making tons of progress again. Hopefully I'll be pitting my philosophies against yours in a more technical arena, soon. :)

### You really should submit a

You really should submit a paper to Onward! next year, which is a good venue for work like this; the problem with Onward! is that it is not very non-academic friendly like Strangeloop is.

I hit blocks all the time, but since I'm lucky enough that this is my full time job, I have to snap out of it pretty quickly.

### If we look at the "state" of

If we look at the "state" of a program for one point in time, there is only one of those. This is important to me for debugging reasons, and I think completely achievable.

Temporal models also have this property. They also happen to support more than one "point in time". But if we look at the "state" of a program for one point in time, there is only one state.

I agree that this property is useful for debugging. It's still useful for debugging after introducing time (especially if our IDE provides a good way to visualize time). The simplifying factor here seems to be that we don't need to consider the logically sub-temporal "intermediate" transition states because they don't have any long-term consequences.

And by delaying non-monotonic actions, this property is completely achieved, even for systems that will never converge. I am curious how, without time, you plan to "completely achieve" a single state for models like A = B; B = !A?

### Time is quite tricky to

Time is quite tricky to visualize, you wind up manipulating it on a timeline or overlaying different states over time using strobophobic visualizations (as your links point to), and probably some combination of both! Yes we have to deal with it, but no, we don't have to deal with it on every instruction execution!

Non-convergence is a problem, unsolved, that needs to be dealt with. Your idea of adding time to at least expose the problem to the user is definitely reasonable and useful; we could at ticks in the system to deal with write after read (assuming an ordering) situations where non-convergence can arise. The drawback of this approach is that it complicates the display of debugging feedback when non-convergence is not a problem; our nice timeline whose points only represent external events (or explicit frame-like time passage) becomes complicated by pseudo events.

I still have a lot of thinking to do, and I'll definitely take your viewpoint seriously.

### Non-convergence is a

Non-convergence is a problem, unsolved, that needs to be dealt with.

There are ways to address the problem of unwanted/accidental divergence.

Obviously, Glitch won't perform any symbolic analysis. But if you could, the subject of Church-Rosser convergence is very well studied for term rewrite systems.

A technique I've found works well is physics/market inspired: one models a finite resource such as "energy" (or money) and this must be expended during the computation. Energy can be added with each event, and is automatically distributed to downstream nodes. If there is any energy left over, it can feed back to continue waiting computations.

Running out of energy is a 'sign' of non-convergence, not a proof. It works well when there's a human in the loop to add more energy. Further, it could help developers very easily visualize where the "hot spots" are - i.e. highlight in oranges and reds the nodes and states where the most energy is spent.

I've contemplated a design where energy continues to "trickle in" at a continuous rate, e.g. to continuously search for more optimal solutions in weighted constraint models, or as a basis for animated term rewriting. I haven't gotten around to trying this yet.

### Obviously, Glitch won't

Obviously, Glitch won't perform any symbolic analysis. But if you could, the subject of Church-Rosser convergence is very well studied for term rewrite systems.

Nothing in Glitch prevents a symbolic analysis, especially since a global data-flow assignment analysis is already done (efficiently actually) to support type inference. However, without full on dependent typing, the problem is impossible to solve in general, consider:

A[w] = A[v]
A[x] = !A[y]

Whether non-convergence occurs depends on w, v, x, and y. We could be conservative about it, but I'm not sure the false positives are acceptable. I want to get some more experience with some real applications before deciding the best way to solve this problem.