[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Eval, tail calls, (current-module), and backward compatibility
From: |
Andy Wingo |
Subject: |
Re: Eval, tail calls, (current-module), and backward compatibility |
Date: |
Wed, 18 Jan 2012 22:52:05 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) |
On Wed 18 Jan 2012 20:58, Mark H Weaver <address@hidden> writes:
> Andy Wingo <address@hidden> 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/
- Eval, tail calls, (current-module), and backward compatibility, Mark H Weaver, 2012/01/16
- Re: Eval, tail calls, (current-module), and backward compatibility, David Kastrup, 2012/01/17
- Re: Eval, tail calls, (current-module), and backward compatibility, Mark H Weaver, 2012/01/17
- Re: Eval, tail calls, (current-module), and backward compatibility, Andy Wingo, 2012/01/18
- Re: Eval, tail calls, (current-module), and backward compatibility, Mark H Weaver, 2012/01/18
- Re: Eval, tail calls, (current-module), and backward compatibility,
Andy Wingo <=
Re: Eval, tail calls, (current-module), and backward compatibility, Ludovic Courtès, 2012/01/18
- Re: Eval, tail calls, (current-module), and backward compatibility, Andy Wingo, 2012/01/18
- Re: Eval, tail calls, (current-module), and backward compatibility, Ludovic Courtès, 2012/01/18
- Re: Eval, tail calls, (current-module), and backward compatibility, Andy Wingo, 2012/01/18
- Re: Eval, tail calls, (current-module), and backward compatibility, Ludovic Courtès, 2012/01/18
- Re: Eval, tail calls, (current-module), and backward compatibility, Andy Wingo, 2012/01/18
Re: Eval, tail calls, (current-module), and backward compatibility, David Kastrup, 2012/01/21
- Re: Eval, tail calls, (current-module), and backward compatibility, Mark H Weaver, 2012/01/21
- Re: Eval, tail calls, (current-module), and backward compatibility, David Kastrup, 2012/01/21
- Re: Eval, tail calls, (current-module), and backward compatibility, Mark H Weaver, 2012/01/21