[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

call/cc and proper tail recursion



   Date: Mon, 16 Nov 92 20:44:24 EST
   From: Marc Feeley <feeley@IRO.UMontreal.CA>
   Full-Name: Marc Feeley

   It seems that I did not receive the intervening discussion spawned by my
   comment.  Here are a few points I want to make...

   1) From the report (r4rs) I wasn't sure what the correct semantics
   should be.  The first system I tried my example on was MIT-Scheme and
   it ran out of stack/heap space.  The correct semantics should be
   explicited in the next report since call/cc plays a fundamental role.

I don't consider the requirement that you want essential, but I don't
mind it.  It was certainly not a consideration when the current MIT
Scheme code was written.

   2) The thing that got me interested in the tail recursive property of
   call/cc is the implementation of dynamic binding.  For call/cc to work
   properly with dynamic binding, the dynamic environment must be saved
   inside the continuation captured by call/cc (so that the correct
   dynamic environment can be restored when the continuation is resumed).
   A naive implementation of dynamic binding will make call/cc non-tail
   recursive.  I just want the people working on dynamic binding to know
   about this potential problem (is there a group in charge of this
   anyway??).  Note: contrary to the dynamic-wind construct, the dynamic
   binding construct can be tail recursive.

FYI, the current non-tail-recursive behavior of cwcc in MIT Scheme is
not due to DYNAMIC-WIND (or dynamic binding) but to laziness.  The
simplest way to guarantee that the correct interrupt mask (and other
items of state, including interpreter history) are correct when the
continuation is reentered is to push the appropriate "restore" frames
when it is captured.  This is done unconditionally, so a loop through
cwcc pushes a set of those frames per iteration.