🚀 go-pugleaf

IZZYOB9@MVS.OAC.UCLA.EDU (Bob Stocks) writes:
>  I've just written a small
>spiral procedure to teach my 6th grade students about loops
>and it works fine on the apple IIc at school using appleLogo
>but when I run it on MSW Logo I get a message saying "too many
>levels of recursion."

Apple Logo, like every (I think) commercial Logo implementation,
uses a technique called tail call elimination (sometimes called
"tail recursion elimination" but that's just a special case).
This means that if the very last thing your procedure does is to
call another procedure, Logo treats that final procedure call as
if it were a GOTO instead.

This is important because ordinarily every procedure call requires Logo
to save away some information, such as the context to which the called
procedure should return.  But if procedure A calls B, and if B calls C
as its very last act, then instead of C returning to B and then B
immediately returning to A, Logo can set things up so that C returns
directly to A.  (This is a simplified story leaving out a *lot* of
details, but it's good enough to make the point.)

MSWLogo, like its ancestor LSRHS Logo, doesn't know about tail call
elimination.  The WHILE procedure that you're calling is implemented
tail recursively, something like this:

	TO WHILE :CONDITION :ACTION
	IF NOT (RUN :CONDITION) [STOP]
	RUN :ACTION
	WHILE :CONDITION :ACTION
	END

Since the call to WHILE is the last thing in WHILE, tail call elimination
can carry out the specified action any number of times without having to
save any extra information each time.  But in a Logo without tail call
elimination, each time through the WHILE requires saving some context,
and eventually you run out of memory.

P.S.  Berkeley Logo does know about tail call elimination, so you might
try that.  It doesn't have the fancy Windows bells and whistles, though.

As a LogoWriter user, and not having a WHILE primitive, I would have
tackled Bob's problem with a more obvious recursive procedure:

TO SPIRAL :FIRSTLENGTH :ANGLE
if :FIRSTLENGTH < 175 [stop]
fd :FIRSTLENGTH rt :ANGLE
SPIRAL :FIRSTLENGTH + 2 :ANGLE
END

I really appreciated Brian's discussion of how the interpreter treats
"tail recursion" (I now call this feature "iteration" to avoid confusion
with "real" recursion) and his definition of the procedure WHILE.

I'm not sure I really "approve" of Bob's use of "make" as the way of
updating :FIRSTLENGTH; the recursive call to SPIRAL seems a cleaner way to
accomplish the same thing.

Dave Kressen

MswLogo 2.4 (ready, but waiting for approval of distribution of multi-media
help file from microsoft). Has a MUCH larger stack depth. Something like 35 ->
1000. Still finite but still much better.

Eventually MswLogo will handle tail-recursion, probably by inheriting
ucblogo's kernel.