Time and time agin I read that tail call elimination is not part
of the ANSI standard and that recursive itteration should be avoided.
But is there actually a compiler/interpreter out there
that does not support it?
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Hello!
John Thingstad <··············@chello.no> wrote:
>Time and time agin I read that tail call elimination is not part
>of the ANSI standard and that recursive itteration should be avoided.
>But is there actually a compiler/interpreter out there
>that does not support it?
Depending on compiler settings many do *not* eliminate tail calls.
For example with a high debug setting it makes much sense to keep
the call frames for tail calls too.
Check the documentation of your favourite Lisp implementation to see
with which settings which tail calls are eliminated, and how tail
calls are defined, anyway.
For example:
(defvar *variable*)
(defun foo (x)
(let ((*variable* x))
(if (some-condition x)
(foo (1+ x))
(bar x))))
Here, the recursive call is probably not a tail call, as there must
be code to undo the dynamic binding of *variable* after the return
from the recursive call, just as if the code where something like this
(thread behaviour *not* taken into account!)
(defun foo (x)
(push-special-binding '*variable* x)
(unwind-protect
(if (some-condition x)
(foo (1+ x))
(bar x))
(pop-special-binding '*variable*)))
Kind regards,
Hannah.
>>>>> "Hannah" == Hannah Schroeter <······@schlund.de> writes:
Hannah> Here, the recursive call is probably not a tail call, as
Hannah> there must be code to undo the dynamic binding of
Hannah> *variable* after the return from the recursive call, just
Hannah> as if the code where something like this (thread behaviour
Hannah> *not* taken into account!)
There are ways to optimize proper tail calls with dynamic scope.
Brian Harvey, author of Berkeley Logo
(http://www.cs.berkeley.edu/~bh/), was recently kind enough to give me
some help understanding how he does it.
The method, using shallow binding, is to continue extending the
current stack frame of to-restore dynamic bindings rather than
starting a new one when making a tail call. A new stack frame is
allocated only before a non-tail call. When binding a dynamic
variable, if an old value to be restored is already in the current
stack frame, just clobber the existing global binding. If not, stash
the current value in the current stack frame and overwrite the global
binding. When returning, all of the saved bindings in the current
stack frame are restored.
Andru
--
Andru Luvisi
Quote Of The Moment:
Those who cannot remember the past are condemned to repeat it.
-- George Santayana
Those who study history are doomed to stand by and watch it
be repeated in real time.
-- Marty Schrader
Andru Luvisi <······@andru.sonoma.edu> writes:
> Brian Harvey, author of Berkeley Logo
> (http://www.cs.berkeley.edu/~bh/), was recently kind enough to give me
> some help understanding how he does it.
> [...] When binding a dynamic
> variable, if an old value to be restored is already in the current
> stack frame, just clobber the existing global binding. If not, stash
> the current value in the current stack frame and overwrite the global
> binding.
Hmm, is that compatible with how CL supporting threads handle LET and
dynamic variables in the presence of threads?
Regards,
Jorg Hohle
Telekom/T-Systems Technology Center
>>>>> "Joerg" == Joerg Hoehle <······@users.sourceforge.net> writes:
Joerg> Hmm, is that compatible with how CL supporting threads
Joerg> handle LET and dynamic variables in the presence of
Joerg> threads?
I don't see why it wouldn't be. Here's a quick stab at a rework:
"assignment to global binding" becomes "rebind in thread-local
environment, adding if
necessary"
The information stored in the stack frame would need to be of two
potential types: "restore this value to the thread-local binding" or
"remove the thread-local binding"
Disclaimer:
So far I have implemented neither a multi-threaded lisp nor a tail
call optimizing dynamically scoped one. Therefore, I wouldn't be at
all surprised to find out that doing both at once has complicating
factors which I am overlooking.
Andru
--
Andru Luvisi
Quote Of The Moment:
Quidquid latine dictum sit, altum viditur.
( Whatever is said in Latin sounds profound. )
John Thingstad wrote:
> Time and time agin I read that tail call elimination is not part
> of the ANSI standard and that recursive itteration should be avoided.
> But is there actually a compiler/interpreter out there
> that does not support it?
>
Bill Clementson has a great article about this here :
http://home.comcast.net/~bc19191/blog/040613.html
I've use trampolines like he describes in place of tail calls, because
i've never been bothered to figure out what SBCL will eliminate.
This is one of the things i really love about lisp. Regardless of
"language support", one can always find a way, and
with-sufficient-macrology, integrate it into the language. I use
continuations every day, and there are no continuations in the ANSI
standard. One could, given the skill and desire, hack together something
that transforms 'proper' tails into a trampoline style in the same way
UncommomWeb does for CPS.
Or read your implemetations docs to see where it does TCE ... infact
that's probably a simpler approach. But a transformer would be more fun,
and probably give you some insight into -why- CL does not mandate TCE.
drewc