Some spaghetti are less tangled than others

They say if you can’t explain it to a six year old, you don’t understand it yourself. Supposedly it was Einstein who said that. Though he also said he didn’t say half of what they say he did. Anyway, how would one explain to a six year old delimited continuations implemented in terms of the standard call/cc?

Respectable scholarly expositions typically relate to the underlying CPS-transformed structure to explain the logic. The metacontinuation is a fine concept, but explaining interaction of obscure concepts in terms of an obscure metaconcept has its drawbacks.

I am going to show a two-layered (three if you count the syntactic sugar) implementation of delimited continuations aimed not at affinity with theoretical models, or efficiency, but at making clear the mechanics of what’s really happening. It’s the result of refactoring what originally was very similar to the implementation in the paper.

We start with “stackable labels”, a helper control mechanism with two primitives: label! and jump!. The latter may sound like the good old goto, though as we’ll see it actually has more in common with return.

The label! expression, shown in this example as part of a larger expression

(+ (label! (foo)) (bar))

evaluates its argument (foo) and returns the result, so the whole expression is almost the same as simply

(+ (foo) (bar))

The difference is that as a side effect label! remembers the spot in the evaluation where the result of its invocation was expected. We call this spot a label (a noun; label! is meant as a verb). Note that I say it’s a spot in the evaluation and not in the code. A label! expression may be evaluated multiple times, and the label it creates each time corresponds to that specific evaluation of label!. If this sounds vague, the examples below will clarify the difference. (And if this sounds like continuations, it’s because that’s what labels are below the surface–but labels! and jump! are there to hide and manage the underlying continuations, so we will avoid peeling back this abstraction).

A label created by an evaluation of label! is pushed onto an implicit label stack. A jump! expression such as

(jump! 42)

removes the top label from the stack and jumps to it. Jumping has the effect of the corresponding label! invocation returning with the value passed to jump!. The jump! expression itself never returns.

Here are two examples to build up some intuition about labels and jumps. They use Racket’s non-standard but obvious printf function. First the basic mechanics:

> (printf "got: ~s~n" (label! (+ 3 4)))
got: 7

The result of (+ 3 4) got through to printf as expected, though as a side effect we’ve also saved a label:

> labels
'(#<continuation>)

We can now jump to that label:

> (jump! "hello")
got: "hello"

which has the effect of returning from label! again and proceeding with printf, this time with "hello" as the value to print. The jump also consumed the label and the label stack is now empty:

> labels
'()

The second example is just a slight variation on the first, but the interaction of two labels! expressions makes it quite a bit more interesting. It drives home the point about a label marking a spot in the evaluation and not just in the code.

> (printf "first: ~s second: ~s~n" (label! 1) (label! 2))
first: 1 second: 2
> labels
'(#<continuation> #<continuation>)

So far this is very much like the first example, except we’ve evaluated two label! expressions and pushed two labels onto the stack.

> (jump! 3)
first: 1 second: 3
> labels
'(#<continuation>)

The last label pushed was the one for (label! 2), so jumping to it proceeded with printf, this time with 3 as the second value to print. At this point the first value was already ready to go, so 1 and 3 were printed. We’ve also consumed one of the labels and are left with the other one which marks the return of the result of (label! 1). This is where it gets more interesting.

> (jump! 4)
first: 4 second: 2
> labels
'(#<continuation>)

Now we supplied 4 to the point where the first value to print was expected. However, at that point the second value was not yet available, so (label! 2) was evaluated again, producing 2. It also pushed a new label replacing the one the jump! consumed, so we still have one label on the stack and can jump again:

> (jump! 5)
first: 4 second: 5
> labels
'()

Now the jump emerged from (label! 2) evaluated in the previous step, with 4 supplied by the previous jump ready to go as the first value to print. Now we get 4 and 5 and have finally consumed all the labels.

The implementation of label! and jump! is pretty much a direct transcription of what we said they do. There is a stack of labels (continuations), label! pushes its own continuation onto it, and jump! pops the stack and passes its argument to the popped continuation.

(define labels '())

(define-syntax label!
  (syntax-rules ()
    ((push-label! expr)
     (call-with-current-continuation
       (lambda (k)
         (set! labels (cons k labels))
         expr)))))

(define (jump! v)
  (let ((k (car labels)))
    (set! labels (cdr labels))
    (k v)))

The explicit stack of continuations in labels directly corresponds to *meta-continuation* of the scholarly presentation and the structure of nested closures it contains. While less glamorous, the explicit stack is easier to follow and inspect.

Now, armed with stackable labels, the implementation of reset and shift (or rather their core as higher-order functions; syntactic sugar is unimportant) is trivial.

(define (reset/0 body)
  (label! (jump! (body))))

(define (shift/0 body)
  (call-with-current-continuation
    (lambda (k)
      (jump! (body (escaper k))))))

(define (escaper k)
  (lambda (v)
    (label! (k v))))

OK, maybe it’s not completely trivial. But it’s reduced to the bare essentials, and with control transfers abstracted by stackable labels the structure is much easier to explain. Especially if we do that in the following not very precise but very helpful imperative terms.

Stackable labels can be seen as an auxiliary call stack. The state of evaluation saved on it using label! stays available for returning into regardless of the “regular” calls and returns and their stack. The jump! operator is a “special return” for returning into the saved state.

In the beginning, reset/0 enters a “special call” because it’s entire body is wrapped in label!. Evaluation of both reset and shift bodies ends with a “special return”. If a shift never invokes its escape function, as in either of the fragments

(reset (+ 3 4))            ; => 7
(reset (+ 3 (shift k 4)))  ; => 4

the auxiliary stack only has an entry corresponding to reset. So, the bodies of both shift and reset return out of reset.

If a shift does invoke its escaper function, as in

(reset (* 2 (shift k (+ (k 3) (k 4))))  ; => 14

the escaper pushes a new entry onto the auxiliary stack. It then returns its argument from the shift expression by invoking the continuation k captured by shift/0 (not part of the stackable labels scheme). Now the reset body is proceeding with that as the value of the shift expression. When the reset body completes, it “special returns” to the escaper invocation on top of the stack and not out of reset as it would do otherwise.

These are the two base cases. More complex structures, such as

(reset
  (display (shift k (k "a") (k "b")))
  (display (shift k (k 1) (k 2))))  ; prints "a12b12"

are simply a combination of these two scenarios.

Could a six year old understand this? Mine couldn’t. But in any case, refactoring continuations-based code builds character and makes one a better person. I think it was Einstein who said that.

The full source with sugar and examples

Hopscotch presentation video from lang.net

Gilad gave a talk about Hopscotch last week at lang.net 09. In his blog post about it he modestly speaks in detail only about the talks of others, but since his is the first properly recorded demo of Hopscotch available online, I want to specially mention it here. It features the latest and the greatest version of the tools, so it’s even better than what could be seen at Smalltalk Solutions, WASDeTT and ECOOP last year.

Update: A non-Silverlight (WMV) version is available here.

I’m feeling lucky

Just a few months ago I never would have thought I’d work on anything other than Newspeak for the foreseeable future. Working with Gilad, Peter, and others was a fantastic experience, and building a programming platform almost from scratch without political and marketing baggage attached was not a job you find every day on monster.com. But it turns out sometimes the foreseeable future runs out sooner than you expect.

The end of full-time Newspeak work is a sad thing, but I’m not writing this to cry over spilt milk. They say new beginnings bring new opportunities, and this is how I want to look at it. I have just finished my first week working for Google.

On UI Layout

Michael Lucas-Smith posted an interesting summary of UI layout models. I tried to leave the following as a comment, but the blog server swallowed it without posting. Fortunately, I half-expected this and copied the text before submitting. I’m posting it here instead, with some further edits.

Overall, this is a good summary, but there is a very important model it misses.

The model is a variant of constrained-based layout called linear constraints. In that model widget positions are expressed as a system of linear equations. This more formalized approach, unlike “intuitive” models with springs, wires and other pseudo-real life accessories, isn’t fiddly at all. There are algorithms (Cassowary is the most famous) to efficiently solve such constraint systems.

Also, importantly, many other models: fixed, relative, stacked and grid layouts are special cases of linear constraints. Only flow cannot be expressed this way. Thus, the models are not all incompatible. Also note that I’m listing “relative” as an additional model, which is the correct way to describe the VW approach (first proposed, most likely, by Luca Cardelli). (“Fixed” would be the case when the widget’s bounds are expressed as coordinates in some coordinate system, usually relative to the containing widget’s top left corner).

I’m not sure what it means to say that layout should not be part of the widget framework proper, without first defining the proper. One extreme is Windows which provides no automatic layout capabilities at all. That is indeed the pure fixed model. The other are frameworks with container visuals. In those frameworks the specific layout model is indeed dictated by the container. But still, the only difference between the two is that something like Qt has containers that do layout and Windows doesn’t. In neither of them layout is part of widgets (by widgets I mean atomic leaf components such as buttons or list views).

The important question is how hard or easy it is to introduce new containers with different layout models, but it is a matter of the overall framework design. The main complication here are performance constraints. The framework should reasonably quickly respond to incremental layout changes, and reconciling that need with pluggability of containers and their layout policies is where the devil lies. I’d estimate about 70% (if not more) of Brazil design effort has had something to do with layout management.

I’m done, it says

Good battery, yay!I normally work on a Mac, but my “official” work laptop runs Windows (ok, it also has Linux on it) and I’ve been using it lately to be able to run Strongtalk. So I turn it on today and out of the blue pops up this message.

I think I’ll just go home now.

right click – select – do it

Two months ago I left Cincom, to reset and refresh a number of things in my work and life. For those few who might care, so far it’s been working out great. Neat things to write about come up like never before, and this looks like the perfect time for a new blog unaffiliated with any particular company or product.

Many thanks to Bob Westergaard for helping me brainstorm the idea of a sufficiently non-committal and yet vaguely relevant title. I like how 3 + 4 and the magical number 7 are related to my interest and involvement with languages and interfaces. They are the creations different and yet very much alike in being two of the many things that try and often fail to make us smart.