Zippers, Part 3: Kiselyov Zippers

So far, we've been talking about zippers as a separate data structure; that is, we've been focusing on representing what our data looks like as we change it. But Kiselyov takes a different tack: he wants to focus on the process of changing a data structure as a whole.

Now, there's one pretty universal method of applying changes to a data structure, though perhaps we don't often think of it as such: mapping a function. After all, suppose I go and write:

map (fn [x] <- * x 2) [1 2 3 4 5]

I can imagine this as crawling along my list and updating each field to be twice its previous value. And if I only want to update one value, say changing the 3 to a 12, I can write:

map (fn [x] <- if (= x 3) 12 x) [1 2 3 4 5]

Of course, this is rather wasteful in terms of runtime and memory usage and such. But it's not altogether incorrect. You might even imagine that we might modify our map function to detect whether we changed a value, and if we don't modify some tail of our list, keep that list the same; this would yield the same performance as our original list-update function.

But we're missing an important difference: with this map-based approach, we can make multiple updates at a time. And if we're making \(O(n)\) updates to a list of length \(n\), we have \(O(1)\) per update (on average).

Of course, the problem is that usually, when we make the first update, we're not too certain what other updates we plan on making. Ideally, we should be able to make a few updates and then "pause", waiting for the remainder of the updates. Hopefully, we'd achieve the same results as for Huet zippers, because we would hopefully "batch up" all of the nearby operations, thus saving us the costs of moving around the structure. This model fits the standard usage of purely functional data structures pretty well.

But how could we "pause" the map midway through?

Continuations are a way of of capturing the future of a computation. That is, it provides a primitive, call/cc, which takes a function with a special object, called a "continuation", as an argument. Calling this function with some argument "returns" that argument as the return value of the call/cc. In languages like Scheme that offer "fully re-entrant" continuations, you could first store this object away and call it plenty of times. I've written about continuations elsewhere.

Delimited continuations are similar, except that instead of capturing the entire future of a computation, we only capture it outward to some point. What do I mean? It means that we write:

context/cc <- fn [ctx] <-
    g <-
        call/cc ctx <- fn [cc] <-
          f <-
              cc arg

In this case, since we call cc with arg, arg will be returned out of call/cc, pass through g, and then, when it reaches the context, control will return from your continuation back to your calling code. Note that we need a way to skip the future if we don't like it, so the convention is that if we return from the argument of call/cc without invoking our continuation, we'll jump to outside our context.. So what ends up happening is f <- g arg. Crazy? Yeah.

Anyway, the most important thing to know about delimited continuations is that they capture the computation from now up until some point in the future.

As remarked in the last part, we can view zippers as a "paused" computation — as us pausing the building of a tree or list or whatever structure. We imagine building the tree from the leaves up, but at some point we pause, compute elsewhere what the value in a certain place should be, and continue. Since this is precisely the job for delimited continuations.

What Kiselyov does is precisely that. He takes the canonical map function and delimits it with context/cc. Then the first argument to map, the function that we're mapping, can use delimited continuations to pause the map function until we have more information. (Recall how above we turned code written g <- f arg into code evaluating as f <- g arg? Here, we want to replace make-decisions <- map f with map <- make-decisions f.)

data Zipper t a = ZDone (t a) 
                | Z a (Maybe a -> Zipper t a)

make_zipper :: T.Traversable t => t a -> Zipper t a
make_zipper t = reset $ T.mapM f t >>= return . ZDone
 where
 f a = shift (\k -> return $ Z a (k . maybe a id))

What our zipper will look like to the outside world is a pair: the current element, and a function next that moves the cursor forward. Because we also want to update the structure as we go, the function next will take an argument. We'll pass it the argument Nothing if we don't want to make an update, and Actually v if we want to replace the current value with v before we move forward.

So our plan is to:

• Wrap the map call in a new context.
• The function we pass as the mapped function will return a pair of current value, next function.
• The next function will examine its argument and call the continuation with whatever the value at that location should become.

; Set up a context
context/cc <- fn [ctx] <-

    ; Start a map
    (flip map) our-list <- fn (elt) <-

        ; Capture the continuation
        call/cc ctx <- fn (cc) <-

            ; Skip *outside* of the context (since we don't execute `cc`)
            ; and return a pair
            [

                ; of the current element
                elt

                ; and the `next` function
                fns <-

                    ; If you pass is `Nothing`, you keep the current element
                    [Nothing]    <- elt

                    ; If you pass `Just a`, you use `a` instead.
                    [(Just ,a)]  <- cc a
            ]

This one takes a while to get, so make sure you clearly understand why the control ends up flowing the way you expect, with pairs returned only one-at-a-time. If you are comfortable with Haskell's syntax, you might prefer Kiselyov's version above.

Now, why might Kiselyov's approach be preferable? After all, there's so much magic and crazy control flow shenanigans involved… One reason is because the construction here is independent of the actual data structure. Instead of having to differentiate the data structure, we use delimited continuations, which are effectively program derivatives, to achieve the same effect. Firstly this is cool in languages such as Haskell, which can express program derivatives but not data derivatives.

But it also hints to a more powerful connection — the connection between state and time. But that's for a web page of its own, some time later.

An obvious deficiency of the above is that it only translates well to a list. In a tree, we'd like to move left and right and up. This can be done by making the mapping function accept two return values: a new value, and a direction to proceed in. This isn't that hard to code up. Similar little hooks can be added for all sorts of useful things.

But another issue we have that we didn't with Huet zippers is that we can't go backwards. To fix this, we'd have to keep around old cursors. But we can do that just by storing a stack of delimited continuations. This can be managed by our map function, or using mutable state external to it.

In this way, we recover all of the features of Huet zippers, but in a convenient generic framework that means that the computer does more work for you. Excellent!

Kiselyov extends his idea in one crucial direction, though. "We have all of these delimited continuations floating around," he says. "They capture the difference between two points; that means we can combine our several updates into one." This yields a great framework for concurrent zippers, where multiple cursors manipulate one data structure.

The idea is that we'll take the continuation delimited by the beginning of a transaction (in one cursor) and the point at which it's committed. Then, we shift the continuation over to the other cursor. We move that cursor to where the first cursor started, execute the continuation, and move it back. This gives us something similar to the transaction push and transaction pull models of databases or distributed version control.

I'm not going to write out code for this approach, because we'd need a nice beefy data structure like a tree to make the examples non-trivial. So you may want to reread the above paragraph until it's vaguely clear. If you're interested in seeing actual code, I'd look up Oleg's original.

Kiselyov zippers exploit a striking dual between program and data differentiation. By recognizing that delimited continuations represent the "difference" of two program states, we realize that a zipper is nothing more than a delimited continuation. This gives us a way to implement zippers in a way that's independent of the data structure we zipper over, by bootstrapping the standard map function into a construction function.

We can extend the same idea to allowing multiple cursors to operate on a single structure by using delimited continuations again to capture a single "transaction" and applying all transactions from other cursors when you "resync". This is a powerful concept that allows us to easily simulate purely functional shared memory.

But Kiselyov's approach to concurrent zippers has the downside that it requires moving each cursor back and forth between the various cursor positions. In the worst case, this could mean walking \(O(n)\) nodes, and this severely limits how granular we can make these transactions — too many transactions and we spend most of our time shuffling back and forth between two locations.

Ideally, there would be some concurrent zipper implementation that would get around these flaws and once again present all its operations as \(O(1)\) with respect to \(n\). Such a method was discovered by yours truly. But that's for part 4…

Update: Joachim Breitner explains how to start with Kiselyov zippers and get back to a normal zipper, using a bit of defunctionalization.