Mr. Spelunx
unread,Sep 14, 2022, 11:57:26 AM9/14/22You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to
I found an additional resource about this from the Logo Exchange archives. This was from the November 1984 issue:
Q and A
by Jim McCauley
Q. I'm really puzzled by OUTPUT and its use in recursive procedures. I was working with a procedure like:
TO ANY.GREATERP :N :LST
IF EMPTYP :LST [OUTPUT "FALSE]
IF (FIRST :LST) > :N [OUTPUT "TRUE]
OUTPUT ANY.GREATERP :N BUTFIRST :LST
END
which checks to see if there are any numbers greater than N in a list called LST. What took me a long time to figure out is this: Not only must you arrange for the procedure to OUTPUT TRUE and FALSE, but you must also OUTPUT the recursive call to ANY.GREATERP! Why? This seems to me to be one of the features of Logo that is not really well documented.
A. Let me open my response by agreeing immediately with your last comment. While there are many examples of this feature of LCSI and MIT Logos in the documentation supplied, it is left to the user to "read between the lines" to pick up on this technique. Indeed, most of the trade books on Logo give it only the lightest treatment. The authors assume that it is "logical" (and it is...), but I agree with you that it is not intuitively obvious.
Let me try to make it a bit more comprehensible. Take a procedure like:
TO ADD.N :N :LST
IF EMPTYP : LST [OUTPUT []]
OUTPUT SENTENCE (FIRST :LST) + :N ADD.N BUTFIRST :LST
END
This adds the number N to every number in the list LST and outputs the modified LST when the job is done. Its operation is classically recursive: until LST is empty, it "holds on" to the first number in LST, adding N to it, then creates another "copy" of itself to send the BUTFIRST of LST for further processing.
Each of the copies creates other copies until LST is empty. The last copy receives an empty LST and outputs it.
Like STOP, OUTPUT halts the execution of a procedure. But, unlike STOP, it returns some information to the procedure that called it into action.
Imagine all of these copies of ADD.N as a chain, each copy linked to the one that called it and the one it called. When LST is empty, the chain "bottoms out," and an emmpty LST is output to the next-to-last copy of ADD.N.
Now that copy OUTPUTs a sentence made of two things: the number to which it added N and the empty LST it received from the last copy of ADD.N.
The LST it outputs is treated by the copy "above" it in a similar way, a process which continues until the "top" copy outputs the reconstructed LST to the primitive or procedure that called ADD.N in the first place. Thus,
SHOW ADD.N 4 [21 14 52]
produces
[25 18 56]
(If you use MIT Logo, change the first line in ADD.N to IF EMPTY? :LST OUTPUT [] or IF :LST = [] OUTPUT [], and test it with ADD.N 4 [21 14 52]. There is no SHOW primitive in MIT Logo.)
I hope this helps you to understand why the last line of ADD.N contains OUTPUT. It is necessary to return the processed LST to all the "higher" copies of ADD.N so that the entire LST can be reconstructed. If you'd like more practice in understanding how this works, Harold Abelson has a nice illustration in Section 8.1 of his Logo primer, Logo (for LCSI), or Logo for the Apple II (for MIT Logo), published by Byte/McGraw Hill.
In your ANY.GREATERP example, things are only slightly different. ANY.GREATERP is not trying to preserve the structure of a list that it will later reassemble; instead, it is simply taking the list apart and looking for a number greater than N. If it finds one, it tells the world by outputting TRUE and dropping the task. If it gets 12 to the end of LST without finding what it's looking for, it outputs FALSE and halts. So it seems a bit unnecessary to OUTPUT the recursive call to ANY.GREATERP, since we don't expect to reconstruct the list that has been torn apart.
ANY.GREATERP is a "tail recursive" procedure, a special type that resembles a loop. It involves a system programmer's trick. Usually, recursive procedures eat up memory like crazy, since there are all those copies lying about, waiting for their "offspring" to return to them with some output.
Often, Logo designers save memory by making the Logo interpreter smart enough to detect when tail recursion is called for. These smart interpreters simply handle such procedures as though they were loops. In order to get the trick to work, though, the syntax must remain consistent, so OUTPUT must appear in the line that makes the recursive call.
Incidentally, some Logo interpreters are smarter than others with respect to this. I've tested all the Logo implementations from LCSI, and they treat both tail recursive operations (procedures that output) and tail recursive commands (procedures that don't output) as I have described. The MIT versions for the Apple from Krell and Terrapin treat tail recursive. commands in this way, but not tail recursive operations.
Usually, this is not a serious limitation, since you'd have to have more than eighty items in a list that was being processed recursively before you ran past the interpreter's capacity to store the previously created copies. I hope this has helped you understand better all that happens when you use OUTPUT recursively. Good luck!