The message below is being cross-posted from the LogoForum. Please
reply here at comp.lang.logo and it will be cross-posted back to the
LogoForum. The original author of this message is tomcsanyi@[EMAIL PROTECTED]
11:29 25.1.2008, Pavel Boytchev wrote:
>Bertrand Carette wrote:
> > The question is : does any Logo implement *tail recursion *? and why
not ?
Comenius Logo and Imagine Logo implement tail recursion detection.
It means that there are some tricks in the interpreter to detect when
a procedure may be tail-recursive and in that case the interpreter
does not use stack space.
The point is, as Pavel already pointed it out, that at first glance
it seems to be easy, but it turns quickly to be quite complex.
Just a few ideas:
Ok, we want to run this really infinitely without a "stack overflow"
error:
to turnAndTurn
rt 1
turnAndTurn
end
So the interpreter (or the compiler) needs to detect only if a
procedure calls itself as the last step.
But when we have it already, then something like this comes:
to goAndTurn
fd 1
turnAndGo
end
to turnAndGo
rt 1
goAndTurn
end
This is, in fact also tail recursion, isn't it?
So we must make the rules more complicated: we need to process
specially any cases when a procedure calls another procedure as its
last command. Note that at the moment of processing the call the
interpreter has no idea (and a compiler can have even less idea) if
the call will be actually indirectly recursive or not. So in fact we
do not need to detect *tail recursion*, we need to detect any *tail
call*.
So maybe the above can be still implemented, then what about finite
but very deep recursion:
to goAndTurn
fd 1
turnAndGo
end
to turnAndGo
rt 1
if bl date <> [1 1 2009]
[goAndTurn]
end
(date gives the date in format [day month year weekday], it is
probably specific to Comenius Logo and Imagine Logo)
The call to goAndTurn is embedded in an if statement. So technically
it is not the last statement of the command list of turnAndGo. But
logically it is a tail recursive call and we really want to run it
for nearly one year without exhausting the stack.
To detect this call as a tail call is quite complex and the level of
complexity depends also on the way how the interpreter or compiler is
designed.
In Comenius Logo I was able to implement detection of this kind of
tail call into its interpreter. But Imagine Logo does not detect this
as a tail call.
Among other reasons, why I did not implement it is the fact that the
more experiences on real usage of Logo I gain the more I think that
simple things should be done interactively and that nearly all the
stunning uses of recursion (where it has really sense and is not only
an exercise to do simple things in a more complicated way) are
non-tail ones. But maybe once I will try to implement it.
And there are still some even more tricky situations of tail calls...
Now I see that this is probably a good idea for an article. Maybe I
will try to finish it util EuroLogo 2009 (it is planned to be held in
Paris). :)
Peter
__._,_.___
LogoForum messages are archived at:
http://groups.yahoo.com/group/LogoForum
|
