Re: Eval, tail calls, (current-module), and backward compatibility

[Andy Wingo <wingo@pobox.com>]

On Wed 18 Jan 2012 20:58, Mark H Weaver <mhw@netris.org> writes:

> Andy Wingo <wingo@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/