A to B or not A to B?
Vector 7:3, page 27
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 27
Such a title leaves the reader in no doubt as to the intended pun! But what about the subject matter? Well I decided that an article on program design might be appropriate, not that I am an expert - far from it. However in teaching students using APL, it does seem to me that much of their confusion is caused by a lack of thought about design: just what the program should do and how it should do it. These thoughts should be expressed, if possible in plain English. Then and only then follows the task of translating these thoughts into machine-readable form and then checking whether the results conform to the design specified.
To illustrate this process, and to show how involved it can become even for a simple program, look at the problem of designing a useful INDEX function; a generalisation of the APL monadic function ⍳. In other words I would like to be able to produce sequences such as 3 4 5 6 7 8, or 9 10 11 12.
The syntax of the function is a major consideration. Do I wish to type NAME 3 8 for the first example, and NAME 9 12 for the second? If so, perhaps a suitable NAME might be BETWEEN. Alternatively we might prefer to use the word TO and type statements such as 3 TO 8.
Such considerations determine whether the function should have a right argument only or both a left and right argument. A further consideration is whether the function is required only to print out results or whether the result of the function should be ‘returned’ so that further processing can be done using it. The latter should almost invariably be the case, although functions which do not return any result are sometimes appropriate (e.g. for written reports).
When these questions have been answered, we are in a position to specify the function in the following form:
Name: TO
Left Argument: A: an integer
Right Argument: B: an integer
Result: R: a sequence of integers from A to B
Suppose A←3 and B←8. Then we need to add the vector ⍳6 (where 5←1+B-A) to the starting point 2 (equal to A-1). Assuming index origin 1, this suggests the expression:
Hence we have our first function TO.
So now to check the function. This is where you need somebody else to play a devil’s advocate role. Certainly 3 TO 8 works as does 2 TO 10. But nothing in the specification mentioned that A should be less than B.
The error message of the APL interpreter points clearly to the problem area: it refuses to use the iota function ⍳ on a negative integer. If we wish the function to take sequences from high to low as well as low to high, modification is needed. The signum function (monadic ×) plays an important role here, as does the modulus function |. Here are some examples:
Piecing these tools together gives the updated function and some test results.
∇ R←A TO B;S
[1] ⎕IO←1 ⋄ S←-×B-A
[2] R←S+A-S×⍳1+|B-A
∇
3 TO 8
3 4 5 6 7 8
5 TO ¯3
5 4 3 2 1 0 ¯1 ¯2 ¯3
So all seems to work well. Incidentally, the checking of the first TO did not use a negative A or B at all, which was rather naughty. Also we ought to have checked what happens when A equals B.
This last result shows that TO always returns a vector, a design feature we didn’t mention, though possibly of crucial importance in some applications. (Also note that the intermediate variable used S is declared to be a local variable when the function has been tested.)
So much for TO? No, there’s more to come. Suppose we didn’t want to index using consecutive integers, but rather jumping in steps? (Rather like the BASIC statement FOR I=2 TO 10 STEP 2.) Perhaps the simplest design for such a function is to allow the right argument to be two-element vector, with the second element (if present) specifying the step size. Here is the third possibility.
∇ R←A TO B_ST;B;STEP
[1] ⎕IO←1 ⋄ B←1↑B_ST←,B_ST
[2] STEP←(1,¯1↑B_ST)[1+1<⍴B_ST]
[3] R←(-STEP)+A+STEP×⍳1+⌊(B-A)÷STEP
∇
2 TO 10 2
2 4 6 8 10
3 TO 10 3
3 6 9
The second example illustrates a hole in the design specification - I didn’t specify what should happen if the end-point is missed - do we under-shoot or over-shoot? Again either choice is easy to program, but not to decide is dangerous when the function is to be used by other people.
And finally, another possible design for an index function, which poses an interesting problem for APL programmers (using first generation APL), is to allow more than one sequence of index numbers. For example:
Without the luxury of nested arrays that second-generation APL interpreters allow, this is tricky, but not impossible. Here is the approach: the largest run is of length 5, and three runs are required. Hence generate the matrices:
Denote A←1 5 15, B←3 8 19, N←1+⌈/B-A (5 in this case), and D←(⍴A),N. The three matrices are then given by D⍴⍳N, D⍴N/A-1 and (1+B-A)∘.≥⍳N
Adding the first two matrices gives more than the numbers required, and the rows of the third matrix tell you which of the elements to keep and which to throw away. With the use of ‘,’ to catenate matrices into vectors, we get
Here is the final version of TO:
Or is it? Perhaps we should allow decreasing sequences here too, e.g.
in which case we need to modify TO above to be
∇ R←A TO B
[1] ⎕IO←1 ⋄ N←1+⌈/|B-A ⋄ D←(⍴A),N
[2] R←(,(1+|B-A)∘.≥⍳N)/,((D⍴⍳N)×⍉(⌽D)⍴×B-A)+D⍴N/A-×B-A
∇
And finally, perhaps you too have your own favourite (A) TO B?