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:

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.(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)))])

(thunk))]))

We can observe that applications of the capture continuation are in tail position using the trick I described the other day:

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 (f n)

(let/tc return

(if (zero? n)

(continuation-mark-set->list (current-continuation-marks)

'test)

(return (with-continuation-mark 'test n

(f (sub1 n)))))))

; => (1)

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.(define (g n)

(let/tc return

(if (zero? n)

(continuation-mark-set->list (current-continuation-marks)

'test)

(return (with-continuation-mark 'test n

(values (g (sub1 n))))))))

; => (1 2 3 4 5 6 7 8 9 10)

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).

## 2 comments:

(Just picking terminology nits.)

The application of the continuation

isin tail position. The problem is that you still need to evaluate the arguments passed to the continuation before you evaluate the application itself, and thereforetheyare not in tail position.For example, in this expression:

(let loop () (let/ec k (k (loop)))), the application ofkis in tail position. The problem is that it has to evaluate its arguments, and so it is the application ofloopthat is not in tail position, and that is what leads to the space blowup.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!

Post a Comment