On Wed 18 Jan 2012 20:58, Mark H Weaver <m...@netris.org> writes:
> Andy Wingo <wi...@pobox.com> writes:
>
>> "continuation marks". We might be able to reuse their strategy in our
>> with-fluids implementation.
>
> I don't see how continuation marks could solve this problem. They avoid
> adding more frames to the stack, but that's not enough. The R5RS says:
>
> A Scheme implementation is properly tail-recursive if it supports an
> unbounded number of active tail calls. A call is _active_ if the
> called procedure may still return.
>
> Therefore, even if you save the old value of (current-module) cleverly
> somewhere other than the stack, these old values would still in general
> use O(n) space, where N is the number of active calls to `eval'.
There's the rub! I believe that the way this works is to consider every
continuation as having "marks" associated with them. For example in
(+ (eval '(eval 'bar mod2) mod1))
the continuation may be written as
(+ [ ])
where [ ] signifies a hole. (Consider it to be a previous frame
pointer, coupled with a return address, if you like.)
(current-module) looks at the 'module continuation mark (or equivalent)
on a continuation. Call-with-continuation-marks does create a new
continuation to pop marks, but only if marks are not set on that
continuation already. If the continuation already has marks,
call-with-continuation-marks just adds/sets marks on the existing
continuation, instead of creating a new one.
So to translate it back to our world, something like
(with-fluids ((a 2)) (with-fluids ((a 3)) (tail)))
^ this doesn't create a new continuation, it just
overrides the marks on the previous one
It seems to be a dynamic construct (i.e., at runtime, not compile-time),
but it works for the purposes of proper tail calls.
AIUI anyway :)
Andy
--
http://wingolog.org/
