Subject: Re: mentioned tail call elimination feature/declaration?
From: rpw3@rpw3.org (Rob Warnock)
Date: Sat, 06 Dec 2003 07:02:26 -0600
Newsgroups: comp.lang.lisp
Message-ID: <p5GcnbratY7_TkyiXTWc-g@speakeasy.net>
David Golden  <david.golden@oceanfree.net> wrote:
+---------------
| It might be nice to have a de-facto-standard agreed experimental feature
| :x-common-tail-call-elim or whatever that meant that you could 100% rely on
| a defined (ahem) safe-for-space behaviour in certain common situations and
| presumably given certain caveats, at least when a new declaration like
| x-please-common-tail-call-elim was active.
+---------------

Just a reminder that proper tail call optimization does *NOT* by itself
guarantee safe-for-space behavior -- you need a lot of other implementation
design choice to have been made in certain ways as well. [This is well-
known in the Scheme community, by the way.] For example, the standard
technique of implementing displays as linked lists of vectors of lexicals
(one vector per level of closure nesting) can interact with tail calls
to produce unsafe-for-space behavior, since closing over one lexical
variable can cause the values of other variables, unused by the closure,
to be retained after they're no longer accessible. There are ways around
that, e.g., make closures use "flat" environments[1], but one must pay
attention to more than *just* proper tail call optimization to guarantee
safe-for-space behavior. The following paper discusses some of the issues
(especially the closure environments representation issue):

	<URL:http://flint.cs.yale.edu/flint/publications/escc.html>

We also talked about it here at some length last April, IIRC...


-Rob

[1] Which requires rewriting some lexicals -- those that are both
    further closed over *and* mutated -- into a pointer to a boxed
    heap value, including rewriting all forms like (setf foo (bar foo))
    into (setf (box-ref %%fake-foo) (bar (box-ref %%fake-foo))), etc.

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607