call/cc and proper tail recursion

[Marc Feeley <feeley@IRO.UMontreal.CA>]

>    Date: Mon, 16 Nov 92 20:44:24 EST
>    From: Marc Feeley <feeley@IRO.UMontreal.CA>
> 
>    A naive implementation of dynamic binding will make call/cc non-tail
>    recursive.
> 
> Not to argue, but could you explain this?  I've written many naive
> implementations and as far as I know they don't break
> call-with-current-continuation.  But then, they all look like this:
> 
> (define (call-with-current-continuation proc)
>   (let ((state (get-dynamic-state)))
>     (primitive-cwcc (lambda (k)
> 		      	(proc (lambda (x)
> 				(set-dynamic-state! state)
> 			        (k x)))))))
> 
> I've often wondered whether this implementation breaks tail recursion,
> but usually I convince myself that it doesn't.  I could be wrong
> though.
> 
> Thanks
> Jonathan

The naive implementation I was talking about is:

(define (call-with-current-continuation proc)
  (let ((state (get-dynamic-state)))
    (let ((result (primitive-cwcc proc)))
      (set-dynamic-state! state)
      result)))

IMO, your definition is tail-recursive.  Note that the following
definition is probably better since fewer variables need to be consed
into the closures:

(define (call-with-current-continuation proc)
  (primitive-cwcc (lambda (k)
                    (let ((state (get-dynamic-state)))
		      (proc (lambda (x)
			      (set-dynamic-state! state)
			      (k x)))))))

While I'm on the subject, one of the things that bugs me about the
definition of call/cc is that these two definitions are not
equivalent:

(define (foo) (call/cc (lambda (k) (f x))))
(define (foo) (call/cc (lambda (k) (k (f x)))))

Although the value returned by foo is the same for both definitions,
the second form may run out of space when the first doesn't (for
example if f tail-recurses into foo).  In the second definition, the
implicit continuation passed to the body of the lambda is not needed
(i.e. is garbage) but there is no way to express this fact directly
in Scheme.  Even if the user knows that the current continuation is
garbage (because some other continuation is going to be called next),
the continuation will be preserved until the argument to the new
continuation has been computed and the new continuation is called.

A new "continuation invoking" mechanism would be needed to solve
this problem.  In addition to call-with-current-continuation there
would be a procedure (say resume-continuation) taking two arguments:
a continuation and a thunk to compute the value to send to the
continuation.  The second definition above would thus be:

(define (foo) (call/cc (lambda (k) (resume-continuation k (lambda () (f x))))))

The advantage of this is that now the implicit continuation passed to
resume-continuation can be garbage collected as soon as
resume-continuation is entered.  Resume-continuation simply restores k
and jumps to the thunk.  Note that resume-continuation is not really
needed (its functionality could be integrated into k).

Comments?

Marc