Generating outputs recursively

Where do all the outputs go

Since both commands and operations may be recursive, you could well be wondering why we are taking an exclusive interest, here, in operations. Well, it was in the interests of simplicity that we introduced the notion of recursion by working throught the definition of the simple recursive command vprint.

When each new vprint clone is called, as long as its input is not empty, it simply has to do its own little job of printing the first element of the input before calling yet another clone. And if its input is empty it just stops. Things are, however, rather more complicated in the case of recursively defined operations.

As you know, all operations create outputs and, as you also know, all outputs must be mopped up somehow - at least, if you want to avoid complaints from Logo. If an operation is called by another procedure it will be the calling procedure which is expected to accept the output and deal with it. Take, for example, the expression word first "cat butfirst "sow. Here, word mops up the output from the operation first - which it has called - by accepting it as its first input. In similar fashion, it accepts the output of butfirst as its second input. At that point word is in a position to pass on to some other procedure the word created by glueing together its two inputs. But, given that caller and called have identical definitions, what happens to the outputs of recursive operations when the recursive call is returned?

In the case of operations, you will probably find that it is useful to distinguish between direct and indirect recursive calls. Of course, as far as the parent procedure is concerned, a recursive invocation of an operation can never be as direct as a recursive invocation of a command. To form a complete instruction within the body of a procedure definition, a command like vprint needs only to be accompanied by an input. An operation, on the other hand, must not only be accompanied by any inputs it requires, it must also be preceded by a command which can accept an input. What we are going to assume, therefore, is that a direct recursive call of an operation occurs in those cases where the operation is preceded by the command op. Why op? Well, as an input to op, the object which is returned is simply retramsmitted without modification. That is a direct enough call by any standards.

As for indirect calls, these will be calls which are immediately initiated by some subordinate procedure which necessarily engages in further processing of its input(s) before its output is passed to the final op.

We will look at direct calls on this page and indirect calls on the next.

Direct calls - or passing the buck

Imagine a dictionary set up as a list of lists, where each sublist represents a word. Let us further suppose that this dictionary list is known by the name "dictionary - i.e. that thing "dictionary, or alternatively :dictionary, would output the whole list.

You may remember that in discussing the use of conditionals, we proposed the following type of structure for a French dictionary:

[ . . . . [ [orthography fromage] [category noun] [gender masculine] [means cheese]] . . . . ]

At that stage, we took it for granted that it would be possible to define a procedure called entry which would retrieve the complete dictionary entry for any word if it was given the orthographic representation of the word as input. We are now in a postion to define entry.

As you saw in Non-numerical targets, recursive procedures are ideally suited to winding their way through lists until some specific target object is reached. For entry to work as required, it obviously needs to wind through :dictionary until the chosen target (the key-word represented by the procedure input) is found somewhere inside one of its sublists. At this point entry should output the whole sublist - i.e. the entry for the word.

Given the dictionary structure we are adopting, in order to locate the orthographic form of a word within its dictionary entry, our procedure must look for the last of the first of the list which represents that entry. If you are hesitating, just verify that "fromage is what is retrieved (i.e. output) by:

last first [ [orthography fromage] [category noun] [gender masculine] [means cheese]]

Of course, entry needs to look at more than one sublist of :dictionary. It needs to work through all of the sub-lists of the entire dictionary . Let us suppose, then, that it makes this search from the beginning of the dictionary. The first word in the dictionary is first :dictionary and from this perspective, the orthographic form of that word is, therefore, last first first :dictionary If, by some chance, last first first :dictionary matches (is equal to) the word being looked for, then entry must output first :dictionary (i.e. the complete entry for the word).

But what if the match is not made? Well, in that case, entry gives up and calls on a clone of itself to provide the required output. While it passes on to the clone the original key-word, it gives it, however, only a truncated dictionary - butfirst :dictionary - to work with. (The clone obviously has no idea that it is not looking at the complete dictionary and like its parent attempts to match the key-word against the first of its own :dictionary. We only need to spell out the terminating condition - the end of the dictionary is reached before a successful match - and the definition of entry is complete:

to entry :orthographic.word :dictionary 
if empty :dictionary [op []] 
if :orthographic.word = last first first :dictionary [op first :dictionary] 
op entry :orthographic.word butfirst :dictionary 
end

Click here for some things to do with entry

Back along the line

The question we posed at the beginning of this page was: Where do all the outputs go? In the case of entry, it turns out that in the end only one object is ever output - either the list representing a word successfully matched or an empty list representing the failure to find a match. This object is always provided by the very last clone in the series - the one which succeeds in the task (or meets the terminating condition). Between it and the original entry, this object is simply passed back along the line. In other words, while all of the clones of entry provide an output - as indeed they should being operations - all but the last do this simply by immediately outputting (re-directing) whatever they receive back from the clone called by op.

Like entry, many other recursive operations use a direct invocation of the subordinate procedure. And since nothing is really done when the call is returned, most Logo implementations recognize this particular pattern as tail recursive and behave according to avoid problems with the stack.

When a task can only be performed by the collaborative effort of a whole series of clones, however, a different strategy is required. Look here to see how indirect recursive calls may be made.



Ron Brasington
Department of Linguistic Science
The University of Reading
Reading
UK

E-mail: ron.brasington@rdg.ac.uk