Team work

Bringers of gifts

The procedure gifts - which was used to build up the series of lines making up the body of each verse of A partidge in a pear tree - provides a simple example of a succession of recursive calls co-operating to develop an object which is eventually output by the parent (or better ancestor) procedure. Here is the definition again as a reminder:

to gifts :today
if :today = 0 [op []] 
op fput thing thing :today gifts :today - 1 
end

By using the expression thing thing :today, each clone of gifts has direct access to just one of the gifts. For example, if :today is 1, then, given the way in which the variables are inter-nested, thing :today is "first and thing thing :today outputs [a partridge in a pear tree]. What the each clone must ensure, therefore, is that the particular gift which it (alone) is able to retrieve in this way becomes part of the full list of gifts to which its team-mates all contribute.

The order of the gifts in the verse matters, of course. The first of the gifts which is listed in any verse is always the new gift of the current day and it is followed by the full list of gifts offered on the previous day or, putting it differently, by the gifts for each preceding day in turn down to the gift for the very first day. If gifts is called with :today set at 7, it must ensure, therefore, that it ouputs the gift which it retrieves, at the head of a list which corresponds to the gifts which are output when :today is set at 6.

But, clearly, this is only barely disguised Logo-speak:

output firstput today's gift gifts yesterday

Today's gift, we know, is thing thing :today and yesterday is undoubtedly :today -1. If we simply replace the italicised phrases by the corresponding Logo expressions we have immediately the final instruction of gifts.

op fput thing thing :today gifts :today - 1

You can see clearly now why we are calling such a pattern an indirect call to a clone? Gifts(n+1) is not called on by op directly to provide an object for immediate output. Instead, the parent procedure, Gifts(n), uses fput to hold onto the latest gift (as its first input) until gifts(n+1) (the recursive call) comes up with the second input and thus provides the list into which the first input is then placed. Only at that stage is the newly expanded list passed to op (and the outside world).

You can also see that, although the recursive call is contained within the last instruction of gifts, Logo needs to ensure that control is handed back to the caller - who has fput waiting with a first input at the ready - so that the necessary processing can be completed. This procedure is therefore not tail recursive. Fortunately, with only twelve verses to handle, there is little depth to the recursion and the dreaded OUT OF STACK SPACE won't be seen.

Alternative packaging

If you view the use of fput in gifts as a technique for building a package of some sort recursively, then you will want to investigate other procedures which might be put to similar use. Amongst the primitives, se and word are two obvious contenders and you will find examples of both being used for just this purpose in two simple operations explode and implode. The first 'explodes' a word into a list of characters and the second 'implodes' a list of characters into the corresponding word.

Hang on

The other way to think of the function of fput (and se and word) is as a mechanism for literally hanging onto some stranded object until the recursion unwinds and the object can be integrated into some larger construct. In this frame of mind you might want to investigate other ways in which objects can hung onto during recursion. Take a look, then, at this fairly primitive syllabifier which uses two tricks to hang onto developing structures - a stranded input and a systematically changing input variable.
Ron Brasington
Department of Linguistic Science
The University of Reading
Reading
UK

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

ÿ