[PRL] compiling `return'

[Joe Marshall]

John Clements <clements at brinckerhoff.org> writes:

> On Jun 22, 2005, at 9:33 PM, Dave Herman wrote:
>
>> If you're compiling an imperative language with `return' into
>> Scheme, is the easiest implementation of tail call elimination to
>> capture an escape continuation (or raise an exception) that expects
>> a thunk and then apply the thunk in tail position? E.g.:
>>
>>     [[ proc(x1 .. xn) { ... return e; ... } ]]
>>   = (lambda (x1 .. xn)
>>       (let ([thunk (let/ec return
>>                      ...
>>                      (return (lambda () [[ e ]]))
>>                      ...)])
>>         (thunk)))
>
> I remember talking with Joe Marshall about this at one point.  It
> seems to me that the "nice" thing to do would be to compile the code
> in such a way that no escape continuation was necessary.  That is, the
> return should be the end of the control flow for the procedure.  In
> the simplest case
>
> (begin M0 M1 (if (= x 0) (return e)) M2 ...)
>
> becomes
>
> (begin M0 M1 (if (= x ) e (begin M2 ...)))
>
> I claim that you can always perform such a translation; it gets most
> painful in the presence of macros that expand into lambda's, where the
> (return) should end not just one procedure but many of them, in which
> case you wind up doing a partial CPS.

It can get very painful in the presence of simple loops.

> On the other hand, perhaps escape continuations are just as fast.  I
> think Joe would know more about this.

It is likely that a `normal' return would be faster than using let/ec,
but let/ec is likely to be quite a bit faster than a full-blown
call/cc.