Lambda the Ultimate

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).

Bret Victor's The Future of Programming looks at the promising future of programming as it presented itself in 1973 and what we should expect it to be 40 years later, i.e., today. A lot of things that seemed crazy (GUI, Prolog, Smalltak, the Internet) became reality but we might be still held back today by the same skepticism over what constitutes programming as in 1973. At the same time, engineering seems to have carried us a lot farther than Bret Victor is willing to admit. Victor advocates four changes to move programming into the future:

1. from coding to direct manipulation of data
2. from procedures to goals and constraints
3. from programs as text dump to spatial representations
4. from sequential to parallel programs

If nothing else, this an entertaining and well-produced video of his presentation.