On Accidental Time Travel and Delimited Continuations

A number of my Grace^ implementations using the AST embedding I introduced recently are in continuation-passing style, either because they have to be (Haskell) or to avoid blocking. In combination with Grace's block semantics and non-local returns, the naïve implementation of this inadvertently enables "time travel": the program can "go back in time" to return from a function that already returned, continuing execution from then again. This leads to some interesting outcomes.

What this looks like is a block containing a return statement { x -> return x } that is stored into a variable somewhere. The method it's inside returns normally, but later on, the block is applied— and the method returns again, and the program keeps going. This is a bug in those implementations, not a Grace language feature, but it arises in an interesting-enough way to be worth discussing. The next sections will briefly introduce the Grace semantics and the core of continuation-passing style, then explore what falls out of these on simple CPS implementations.

Grace blocks

Grace is a "curly-brace" language, but control structures like if and for are actually Smalltalk-style multi-part method names. if (true) then { x } else { y } is a three-part method name if-then-else with three parameters, a boolean and two "blocks": first-class lambdas that can be applied (or not) later, or repeatedly. These result in more-or-less normal-looking imperative code, while user-defined structures can be on par with those shipped with the language. Part of supporting that is non-local returns: a block can contain a return statement, which determines the return value not of the block itself but of the lexically-enclosing method. That allows, for example, an early return from a search loop:

method does(lst) contain(value) {
    for (lst) do { x ->
        if (x == value) then {
            return true
        }
    }
    return false
}

The "then" block above will return from the whole does-contain method, just as would happen in typical curly-bracket languages like Java. In doing so, it jumps over the stack frame of the block itself, of if-then, of the outer block, and of for-do, exiting the method itself. With normal code, everything here just works as expected and nobody notices anything out of the ordinary. Blocks can be used for control structures, event handlers, and anything else where reifying a piece of code is useful.

On the implementation side these non-local returns are a bit tricky, depending on the paradigm of the host platform:

• Minigrace C used setjmp/longjmp and manually tracked the returnable scopes.
• Minigrace JavaScript, Kernan, and the Java wg implementation throw special exceptions, and every method body is essentially wrapped in a try-catch that matches a unique identifier of the activation and performs a return, using the host platform's stack unwinding.
• Hopper, and wg's Haskell, JavaScript, and CPS-Java implementations, use continuation-passing style everywhere, and so return corresponds to invoking the return continuation of the method where the block was created.

It's the last of these that we're looking at here.

Continuation-passing style

In brief, this implementation style models every step of computation as a function that has access to another function representing the next step of the program. These represent the continuation of the program and so are called "continuations". At least conceptually, the result of any (sub)step is passed as an argument to the next function, and there's a straightforward translation from SSA form: for every assignment, the right-hand side is the "first" function, and its continuation is the assignment itself; the assignment's continuation is the next line's right-hand side, and so on. When calling a function, it's given the continuation of where it was called from to return to. Some languages (mostly Lisps) allow reifying those continuations, but Grace isn't (intended) to be one of them.

Accidental time travel

While Grace doesn't allow obtaining or storing a continuation, Grace blocks are first-class, storable values. The also have two^ exit paths: their own return value (which gives a value to the code that requested the apply method on the block), and returning from the method the block was written within (giving a value back to the code that requested that method). In combination, under a continuation-passing implementation, it's possible to store a value that can attempt to return from a method that has already finished:

var blk
method test {
    blk := { x -> return x }
    return 1
}


var n := test
print(n)
blk.apply(n + 1)

The code above is, surprisingly, an infinite loop^. It prints out an unbounded list of integers. That's because when blk is applied to an argument, it invokes the return continuation of the test method it was created in — resuming execution in the var n := test line and continuing from there, with a new value in n and eventually reaching the blk.apply line again to jump back one more time. Changes to any visible mutable state persist between invocations, but the call chain and program counter (which line of code we're currently at) resets.

On its own, this is unlikely code to write and just a worse way of obtaining while (true)^. It's surprising, but perverse, and probably you'd never run into it in practice. However, it would be possible to make deliberate use of it for speculative angelic non-determinism, for example. The implementations where this works probably ought to detect and reject it, but it's uncommon enough to write and complex enough to detect that none of them do so far.

Building delimited continuations

We can even construct standard shift-reset–style delimited continuation operators, which will allow any of the many structures definable on those to work. The definitions are a little awkward, but they're remarkably short for what they're doing.

var resetPoint := { x -> x }
method reset(blk) {
    def origReset = resetPoint
    resetPoint := { val ->
        resetPoint := origReset
        return val
    }
    def v = blk.apply
    resetPoint.apply(v)
}


method shift(blk) {
    def cont = { val -> return val }
    def origReset = resetPoint
    def v = blk.apply(object {
        method apply(v) {
            resetPoint := { val -> return val }
            cont.apply(v)
        }
    })
    resetPoint := origReset
    origReset.apply(v)
}

These methods work on any of the CPS implementations, and are used like:

reset {
    print(1 + shift { k ->
            k.apply 10
            k.apply 20
        })
}

Here k is the reified continuation: whenever it's applied, shift will return that value, and control flow continues until the end of the enclosing reset, whereupon it will jump back to right after after k.apply. The code above will print 11 21. For a single small use like this it's obviously not useful, but we can create McCarthy's amb operator trivially too:

method amb(many) {
    shift { k ->
        many.do(k)
    }
}

Whenever this function is used within a reset, it will return each of the values in many in turn, and execution will continue from that return each time. The code will treat amb as returning a single value — which it does, in any given timeline — and doesn't need to be layered in a loop. When the control flow reaches the enclosing reset, amb will return the next value in a new timeline, or we can abort by returning to outside the reset scope. There can be multiple amb calls and they will all fork the timeline when reached.

Consider the following Pythagorean triple finder:

method pythag {
    reset {
        def a = amb [2, 3, 4, 5, 6]
        def b = amb (2..14)
        def c = amb (2..14)
        if (((a * a) + (b * b)) == (c * c)) then {
            return object {
                def l1 = a
                def l2 = b
                def l3 = c
            }
        }
    }
}
def sol = pythag
print "Solution is {sol.l1}^2 + {sol.l2}^2 = {sol.l3}^2"

This will return the first correct Pythagorean triple in that range (3, 4, 5). If we add a print "{a} {b} {c} right above the if, it will show that all the prior values were tested, and those timelines abandoned because they didn't correspond to triples. When one was found, the return chose the current timeline as the one to continue, and only one set of values came out of pythag so only one solution is printed^. Later combinations were not evaluated at all because we abandoned the reset.

This is a fairly standard demonstration for delimited continuations, and not so remarkable on its own. What's interesting about this result is that we obtained it "for free": it comes via not performing some checks on blocks' non-local returns. A block, naïvely implemented, provides the primitive for building out these structures in a language that didn't intend to have them (and probably doesn't want them).

Coroutines

We could also build a simple coroutine system.

var next := done
reset {
    shift { k -> next := k }
    print(1)
    shift { k -> next := k }
    print(2)
    shift { k -> next := k }
    print(3)
}


print "A"
next.apply(done)
print "B"
next.apply(done)
print "C"
next.apply(done)

The code above will output, in order, "A 1 B 2 C 3", with execution passing back and forth between the code within and outside the reset with each shift or next.apply. These could be wrapped up into objects affording a tidier interface, potentially built out of the non-locally-returning blocks directly (i.e. using them as unrestricted continuations) instead of via shift-reset.

Discussion

Experimentally, I've added native shift and reset to most of the wg CPS implementations, so the examples above will work even without defining your own methods, but if they are defined then they will override the built-in control structures and verify that the lifting really does work as described. The native implementations are generally a little faster and in some cases keep better track of stack traces for use in exceptions and other reporting.

Probably, exposing continuations at all is not suitable for a language like Grace; potentially some of the things that can be built out of them are worthwhile to promote to language features. For now, though, creating reified unrestricted continuations through this strange dance with blocks is a path to experimentation.

CPS implementations of other programming languages might inadvertently expose the same loophole. The main unusual requirement is the non-local return semantics; if there are first-class lambdas and non-local return then it should in principle be possible to reconstruct a reified continuation out of them. Where the underlying continuations are single-shot, the strangest outcomes above are out of reach, though a single time travel might still be possible. If they are multi-shot, either deliberately or by default (e.g. because they are composed straightforwardly out of functions), the full range should in principle be possible. Except when this is deliberately part of the language semantics, return continuations should probably at least be invalidated upon first use, in effect turning those single-shot, though this isn't quite enough to escape all the issues.