Defining pickrandom

Aim

The function of pickrandom is to select either an element at random from a list or a character at random from a word. The procedure will be defined as taking one input called :thing to underline its willingness to accept objects of any type. A user of the procedure will therefore say, for example, pickrandom "bottle to have returned one letter at random from the word "bottle or pickrandom :shopping to have returned some one item from a previously set up list called "shopping.

Breaking the problem down

It is easiest to get to grips with the definition of pickrandom by exploring step by step the various sub-tasks which it is required to handle. This will take a little time but the details are worth digesting.

Before you sit down to define any procedure like pickrandom, which in essence parallels or replicates some human activity, it is always worth stopping to think about how you yourself go about the equivalent task. What seems to be neccessary for picking one object 'randomly' from a set, is first to decide on some characterisation of the objects which allows unique identification of each member of the set and then to adopt some arbitrary technique which is able to pinpoint - in an unprincipled way as far as the objects themselves are concerned - one such particular characteristic. Even when you put your hand into a lucky dip determined to let fate have its way, you will inevitably be using some criterion like 'The first thing my hand touches now as I move it down inside the bag.' or 'The packet nearest my left thumb when I have finished counting to 10'. At a very general level, then, there are two different tasks to cope with in random selection. First there is the act of selection itself. We need to be able to select an element from a set given some identifying characteristic. And secondly we need to be able to arrive at that identifying characteristic in some arbitrary fashion. Let us make a start by approaching the problems in that order.

1. Selecting an item by position

When we deal with words and lists - as opposed to bran tubs - we are dealing with sequentially organised structures. From a general point of view, perhaps the most natural unique identifier for an element in a structure of this sort is its numerical position counting from the left. As you have already discovered, LOGO itself adopts this viewpoint in providing the primitives first and last. More to the point, it also provides a similarly based primitive called item which it seems sensible to take advantage of in the design of pickrandom. Item is an operation requiring two inputs - a number and a word or list. It outputs the element of the word or list found in the position identified by the number. Item 2 "cat, for example, outputs "a and item 3 [a [b c] [d e] ] outputs [d e]. As long as you can specify the object of which it forms a direct constituent and its numerical position within that object, item will extract any element from within any LOGO word or list.

2. Choosing a random position

If our plan is to make use of item's capabilities then clearly - given the way it works - all we need to do now in order to guarantee a random rather than a predetermined selection from its second input, is to ensure that item's first input is a number chosen by some arbitrary technique, a number chosen at random. In other words, putting the ideas together half in LOGO, half in English, we can assume a definition of pickrandom which reads (schematically) as:

to pickrandom :thing
op item (some random number or other) :thing
end

All the randomness of this procedure is located in the choice of position. Once a position index is established item will select in its normal way the object in the corresponding position.
Generating a number randomly in LOGO is not difficult. But for our purposes that number must identify a position within a LOGO object and must therefore start at a particular value and be within a particular range. Before we can get around to replacing the English phrase of our definition schema by a genuine LOGO expression we need once again to tackle the sub-problems step by step.

2.1. Random numbers (using random)

Random (or pseudo random) number generation in LOGO is catered for by a primitive called random. This is an operation taking one input. If you give random an integer N it will return 'randomly' any one of N consecutive integers. From a human point of view its behaviour is strange, however. The range of integers from which it makes a slection always begins at zero. If you give random the number 4, it is true that you will get any at random one of four whole numbers, but the numbers will be 0 or 1 or 2 or 3. If you say random 12, you are returned some unpredictable integer between 0 and 11.

2.2. Setting the start of a random number range

Random's behaviour would perhaps not be a problem if item behaved in the same way. Unfortunately, item, like us, starts counting from 1. It assumes that the first element of an object occurs in position 1. Item 0 :some.word will incite LOGO to complain: ITEM DIDN'T LIKE 0 AS INPUT. Fortunately, although random itself counts from zero it is a simple matter to adjust the output it provides so that the range of random numbers we are operating with begins at whatever integer we wish. All that is required is to add a number to (or subtract a number from) the output. Adding one to pickrandom 4 will give 1+0 or 1+1 or 1+2 or 1+3. Taking 2 from pickrandom 10 will give some number between 0-2 and 9-2 (i.e. some one of the 10 random integers from -2 through 7). In general, adding or subtracting a number - let us call it 'start' - from the output of random, where 'range' is the value of the input to random, will give us at random any one of 'range' numbers starting with 'start'.

2.2.1. Addition and subtraction in LOGO

To implement this idea you need, of course, to know how to add and subtract in LOGO. It will hardly come as a surprise that the primitives for adding and subtracting are written as + and -. These are both operations which take two numbers as inputs, but for our benefit - though abnormally for LOGO - they are written BETWEEN their two inputs. The LOGO expression for 1 + 1 is thus also 1 + 1. In like manner 1 + random 3 is a correctly formed expression which will output randomly 1 or 2 or 3.

The primitives + and - are not only unusual in their syntax; it is also unfortunately necessary to be aware that as a LOGO line is processed by the interpreter these operations take precedence over the more normally placed procedures in the sense that they are dealt with first. 1 + random 3 must be evaluated as indicated above since there is nothing for 1 to be added to until random 3 is itself evaluated. But when you try random 3 + 1, you will find that 3 is added to 1 first and it is the resulting 4 which is then taken as the input to random with quite different results. It is possible to override the precedence assumed by the interpreter by using parentheses in the manner which you no doubt know from mathematics. Any complete LOGO expression may be enclosed between round brackets and the evaluation of complex expressions with multiple parentheses is handled by working progressively from the innermost sub-expressions outwards. It is possible therefore to write (random 3) +1 as an equivalent to 1 + random 3, if for any reason you prefer that order.

(For a little more info on mathematical and logical operations, look here.)

2.3 Setting the top of a random number range

Just as the bottom of the random number range must not be less that 1 if we are to avoid complaints from item, so too the top of the range cannot be a number higher than the number of elements making up the object we need to pick randomly from. In other words it is not possible to cross your fingers and say 1 + random 2000 in the hope that a length of 2000 will be big enough to cope with any object we are likely to meet. Try item 3 "oh and you will get OH ISN'T LONG ENOUGH TO GET ITEM 3. What is evidently needed is to give random as its input a number which is exactly equivalent to the length of the word or list involved. Since this cannot be known in advance of pickrandom itself receiving an input, it will need to be computed on the spot. The LOGO primitive count is provided for just this purpose. Count :thing returns the number of elements directly constituting :thing (i.e the immediate constituents of :thing regardless of whether or not they themselves have complex internal structure). Count [a [b c] d [e f]] thus returns 4, and count "elephant returns 8.

We are now in a position to spell out the details of the expression which we identified as some random number in the schematic version of pickrandom. Given the general pattern we arrived at above for expressions which output random numbers conforming to fixed start and range values - i.e start + random range - if the input to pickrandom is called "thing, then a random number within an appropriate range will be returned by the expression 1+ random count :thing

With this technique for arbitrarily selecting a position sorted out we can now finally replace the English words some random number in the schema op item (some random number) :thing in order to complete an all-LOGO definition of pickrandom:

to pickrandom :thing
op item (1+ random count :thing) :thing
end

The parentheses around the expression which outputs the random number are not necessary. But leaving them in does no harm, and it helps to make sense of the two occurrences of :thing. One is an input to count (which establishes the range), the other is an input to item (to identify the object in which the item must be found).

The following diagram for pickrandom's single instruction shows directly how the constituent primitives interact:

If we now suppose that pickrandom is called with an input "cat - i.e pickrandom "cat - so that :thing is assigned the value "cat, and if we further suppose that random 3 on this particular occasion outputs 2, the question marks (the unknowns) in the diagram can be eliminated to show how the instruction as a whole would result in the procedure outputting the word "t.

Phew! Things can only get better!



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

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