Monday, June 27, 2005

Tail-applicative continuations

In a recent discussion on the plt-scheme mailing list, I learned that the application of a captured continuation in tail position--even an escape continuation--is not a tail call. This means, for example, that if you use let/ec to encode constructs from C-like languages such as return, break, and continue, that applications of these continuations will not be tail calls.

Ryan and I came up with a trampoline-like implementation of what I'm calling let-tail-continuation (or let/tc for short), which captures the current continuation, binds it to a local variable, and implements applications of that variable as tail calls. Here's a simplified version:
(define-syntax let/tc
(syntax-rules ()
[(let/tc k body)
(let ([thunk (let/cc return
(let-syntax ([k (syntax-rules ()
[(k e)
(return (lambda () e))])])
(lambda () body)))])
The trampoline evaluates the body, which is required to evaluate to a thunk, and then applies the thunk in tail position. If the body invokes the captured continuation, it wraps the argument to the continuation in a thunk so that it gets evaluated by the trampoline, again in tail position.

We can observe that applications of the capture continuation are in tail position using the trick I described the other day:
(define (f n)
(let/tc return
(if (zero? n)
(continuation-mark-set->list (current-continuation-marks)
(return (with-continuation-mark 'test n
(f (sub1 n)))))))
; => (1)
Whereas if we apply the recursive call in a non-tail position with respect to the captured continuation, we see the control stack grow:
(define (g n)
(let/tc return
(if (zero? n)
(continuation-mark-set->list (current-continuation-marks)
(return (with-continuation-mark 'test n
(values (g (sub1 n))))))))
; => (1 2 3 4 5 6 7 8 9 10)
For the more robust version, I've allowed arbitrarily many body expressions and use an identifier macro to allow the continuation variable to be used in operand position as well.

Update: Thank you Felix for the correction--that's an important point. The salient issue is not whether the application of a continuation itself is in tail position but whether its subexpression is. The let/tc form allows applications of the continuation to evaluate their subexpression in tail position; another way to put this is that continuation applications are tail contexts (or tail context frames).


Felix said...

(Just picking terminology nits.)

The application of the continuation is in tail position. The problem is that you still need to evaluate the arguments passed to the continuation before you evaluate the application itself, and therefore they are not in tail position.

For example, in this expression: (let loop () (let/ec k (k (loop)))), the application of k is in tail position. The problem is that it has to evaluate its arguments, and so it is the application of loop that is not in tail position, and that is what leads to the space blowup.

Peter Bex said...

Marc Feeley observed the same thing and proposed a "better" API for continuations. His paper is a short and easy read. Hope this is useful to you!