Lambda the Ultimate

Two things came to mind:

- the "sprout" method feels like a dual version of (call/cc (lambda (x) x)), current continuation and world state being roughly duals of one another.

- The commit mechanism reminded me of STM. It wouldn't surprise me if different worlds could be executed in parallel and synchronized only via STM-like commits.

I also have a feeling that commit might be dual to actually calling the continuation, or something like that.

Cool paper! It had me at the backtracking example. Making a largish python application exception-safe is pretty much impossible...

Cool. I can hardly believe my favorite language is now becoming a language to do PL research in.

I've played with similar ideas, though in my design worlds were finer-grained, more elaborated models, which allowed for complete redefinition of world semantics from within the language itself, e.g. you can redefine methods for reading and writing cells, the atoms of worlds. This may seem to run into trouble with circularity, but this is where reifying worlds as objects in themselves comes to the rescue: if you want to redefine the semantics for world W1, you simply have the redefinition code execute within another independent world W2; independent, meaning that an access to W2 may not delegate, directly or indirectly, to W1, or you run afoul of circularity (which would manifest as infinite recursion). You can have one sibling world redefine the semantics for another sibling, or you can have a parent world redefine the semantics for a newly cloned child world; the commonest case I've found to be the latter, which is analogous to redefining the semantics of level N in a reflective tower of interpreters from level N+1.

With this design you can easily implement transaction logging and rollback and many other such things, without having them be hard-coded pieces of functionality. Reactive programming is simple: redefine the cell reader method to track dependencies and the cell writer method to propagate changes to dependents. Transparent persistence is possible without further ado, and also Smalltalk-style become() and freezing (protecting selected cells from change for some duration). Worlds do not even natively support delegation to other worlds in a child-parent fashion, or cloning; you implement this yourself as library code. An initial system-supplied world is all that's required to bootstrap. You have enormous flexibility in customizing both the back-end implementation strategies of worlds and their front-end features. An aggressively inlining and run-time specializing compiler makes it possible to compete in performance with a more traditional native implementation of the same functionality.

My ideas surrounding this originally grew out of wanting to have the flexibility of a full reflective tower (in the Lisp tradition) but without the headaches. Limiting the semantic hacking to state, i.e. worlds, and reifying worlds turned out to make the problem easily tractable while letting me do all that I wanted to do. In my first attempt I did not fully reify worlds as objects: the contents of a world were reified, but not the world itself, which thus remained half-implicit. This meant that I had to add a bunch of apparatus to the language to handle the problem of circularity during redefinition. Once I came upon the idea of reifying the whole world as a unity, all these problems vanished: you could then gradually stage the changes in world semantics without effecting them immediately.

If either of the paper's authors comes across this thread, I'd be curious to hear if they have considered similar ideas, or what they think of them in any case.

I don't have much experience with monads, but a World strikes me as a monad with all the language's primitives lifted into it, and where commit is a tail call into the target monad (thus replacing the previous program/World with the new program/World).

Of course, many of the advantages of Worlds for imperative languages simply mimic functional programming (produce new state, don't mutate old state -- Worlds simply updates all the old state in one atomic step).

Here's an old paper I wrote on this subject a while back:

J. G. Morrisett. Refining first-class stores. In Proceedings of the ACM SIGPLAN Workshop on State in Programming Languages, pages 73-87, 1993.

These ideas seem to me to be largely prefigured in or subsumed by the notions of "object history", "pseudo-temporal environment", and "possibility" described in Dave Reed's 1978 dissertation (MIT-LCS-TR-205); moreover, Kay has previously presented other work (Croquet) based on Reed's ideas.

What then is nature of the contribution made by the "Worlds" paper? Is it simply that one tiny fragment of the functionality enabled by these more primitive (and powerful) ideas can be conveniently wrapped up, rebranded, and added today to a familiar language like Javascript?

A variation on this idea of scoping side effects appeared this year at the ACM Dynamic Language Symposium: contextual values, ie. values that actually depend on the context in which they are looked at and modified. It is basically a generalization of the idea of thread-local values (and so has no such thing as a "commit"). Also, compared to "worlds", the granularity is finer (per value) and more general (a "world" is but one kind of context). A construct similar to "in", called scoped assignment regions, is also described. However, worlds seem to give a better structure when it comes to reasoning about a given context.

(Thanks Michael and Greg for the pointers on early related work)