Wednesday, January 21, 2009

Distributed zipper

In looking over the key-value db links as a part of an investigation of a scalability architecture i was reminded of a thread of inquiry i briefly discussed with Oleg Kiselyov. For some time, now, Oleg has been investigating the breadth and depth of applicability of delimited continuations. One of the computational phenomena Oleg applied delimited continuations to is zipper. One way to see zipper is as a means of automatically generating structure navigation mechanism from data structure description. Oleg shows that this mechanism maps nicely onto delimited continuations.

What has not been reported on, to the best of my knowledge, is that delimited continuations have a close relationship to a certain generalized Linda tuple-space access and control regime. Moreover, they look like a certain discipline maintained on a collection of inter-related pi-calculus processes. As i understand it, in their researches Oleg and his colleagues had discovered an intriguing naming discipline related to delimited continuations.

This fits into the work i have been doing on generating query technology as follows. First, offerings like HBase and CouchDB and Project Voldemort are extremely limited in the kinds of data structure they can distribute. Zipper, on the other hand, is quite general in the kinds of data it can handle. The mapping from zipper to delimited continuations sets up a compilation scheme that allows one to distribute the data. More specifically we have the following maps

D -- zipper --> Navigate D -- delimited cont --> NavigateUsingTupleSpace D -- distribution scheme for tuple space --> NavigateUsingDistributedTupleSpace D

As you can see, this fits well into the sort of comprehension-based stuff i've been thinking about. Specifically, the pattern language generation can be beefed up to provide zipper-style context support. That is, we get a notion of cursor for free! Of course, while this works in diagram-chasing mode, it remains to be seen if
  • it can be made to perform
  • what sorts of extra information must be provided to get a good distribution scheme
  • what sorts of extra information must be exposed back to the user to have meaningful failure handling/reportage when distributed mechanism fails
One body of work i have investigated to address these concerns is Fortress. The Fortress design makes it clear that Guy Steele has thought about these very issues in the context of monads and monad transformers. i don't know if he was taking advantage of the delimited continuation work, however. i do not recall seeing a notion of cursor.


chasm said...

Even with my piss poor understanding of zippers, delimited continuations, and monads, this sounds like the shit. So when will you have a stable, working implementation with decent documentation? :-)

Fortress looks pretty cool. And it's *open source*, which means maybe you should take your discussion there and see if they're interested in building it into the language (as a core library, of course). That would seriously rock.

leithaus said...


Thanks for the feedback. i'm looking to build out this technology in an open source base. It requires putting together a team of zealouts who want to do this for fun and (then eventually) profit. You're welcome to join!

i'm not sure Fortress' status after it lost some key bake-offs. Steele & co did a really remarkable job of pulling together some really cool ideas. i hope that some of them can come to life. That said, they don't quite have the right mix of language features to do this the way i'm envisioning. i really need a language with do/for-notation sugar.