Recreational APL The Caret and the Stick Functions
In a postscript to an earlier paper of mine
[1],
I very briefly covered a topic of some recreational significance,
namely “the whirling caret”.
In the present article, I give a more extended treatment
of the same subject, which is the design and use
of the relational and Boolean function symbols used in APL.
History Of the relational and Boolean function symbols in APL, the first used was the equal sign (=), which was introduced by the Englishman Robert Recorde (15101558) in 1557 [2]. Recorde writes:
There is some speculation that he was adapting to a mathematical context a symbol used by medieval scribes to indicate “est” (the Latin “is”). There is also some evidence that this sign was also in use in Bologna to mean the same thing. In any event, the sign was intended to permit assertions to be made regarding the equality of two expressions. Its use as a symbol for a function with value 1 or 0 was formalized by Iverson, for whom it was a generalization of the Kronecker delta, written δ_{jk} , which had the value 0 if j and k were unequal, and 1 otherwise. Iverson also extended the idea to include all the relational functions, writing [3]:
The Englishman Thomas Harriot (15601621), the first surveyor of Virginia and North Carolina (when he accompanied Sir Walter Raleigh to America), invented the symbols < and > to mean “less than” and “greater than” [4]. These appeared in his Artis Analyticae Praxis, first printed in 1631. The Swiss Leonhard Euler (17071783) seems to have been the first to use the notequal sign formed by placing a slash through the equal sign (≠) [4]. This is significant because it showed a way of turning a symbol into its negative. Euler employed the same device in forming the signs and for “not greater than” and “not less than” [4]. These are not the symbols used in APL, but I believe they should be, because they clearly show the relationship to the direct form of the function. The symbols that are used in APL for these two functions, namely ≤ and ≥ , were introduced by the Frenchman Pierre Bouguer in 1734. The form of the symbol used by Bouguer showed both bars of the equal sign as in and [4]. I do not know who introduced the single bar symbols. A long time elapsed between the introduction of the last relational symbol and the first logical symbol. Symbolic logicians, beginning with George Boole, had used a variety of notations to signify the functions they needed in their work. It was the English mathematicians Alfred North Whitehead and Bertrand Russell who, in 1909 introduced the signs ~ for “not” and ∨ for “or”. Quine [5] suggests that the tilde (~) was an abbreviation of the script letter “n” and that the vee (∨) was derived from the first letter of the Latin word for “or”, namely “vel”. Whitehead and Russell used the dot (.) for “and”, in common with many other authors — the same dot they used for multiplication. In current symbolic logic, the symbol & is often used for “and” — perhaps because the symbol is available on many typewriters, and it is an abbreviation of the Latin “et”, meaning “and”. The symbol used in APL for “and” appears to have come into use in symbolic logic sometime after 1928, the date of the first printing of my latest reference [2]. The earliest use I can find of the inverted vee (∧) to denote the “and” function is in a paper by the Pole Alfred Tarski published in 1933 [6]. The last of the symbols we shall be concerned with are those for the joint denial and alternative denial functions, that is, the “nor” and “nand” functions. These are quite important functions, because either one of them can be used as the building block for all the others (see Problems). Quine [5] used the symbol for “nor” and said, “the vertical mark in '' may be thought of as having the same canceling effect upon the sign '∨' ; it is like the vertical mark in the inequality sign '≠' of arithmetic.” Quine was certainly going in the right direction, although it seems clear that the canceling mark need not have a vertical orientation. The initial implementation of APL\360 did not have the nand and nor functions. I don’t have a record of when they were introduced, but it was probably sometime in 1967. Their introduction was suggested by Peter Calingaert, who was then at Science Research Associates in Chicago and is now at the University of North Carolina. Calingaert wanted them because they would complete the set of the nontrivial Boolean functions of two variables. We shall discuss the meaning of “nontrivial” later, but just now we can say that “nontrivial” is the same as “essentially dyadic” and not merely formally so. The APL design group at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York, was receptive to the suggestion, for reasons which have best been stated by Falkoff and Iverson [7]:
Calingaert’s comment when I asked him about this episode was,
“As I recall, the proposal was accepted without discussion”
[8].
In the APL design group there was some experimentation
with the symbols to be used for the functions.
It is interesting that the initial symbols
were ∧ and ∨ overstruck
with a minus sign () .
This choice was much like the one Euler made in
negating < and > .
Unfortunately, the particular geometries of the characters
on the APL printing element made these combinations unpleasant,
and so eventually the tilde was used in place of the minus sign,
and thus we had ⍱ and ⍲ .
Theory The input to a Boolean function of n variables can be represented as a Boolean vector of n elements representing the values of the arguments for a particular execution of the function. Because the arguments can have only the values 0 or 1, there are 2*n possible sets of distinct argument values. For example, for a Boolean function of 0, 1, 2, or 3 variables, there are 1, 2, 4, or 8 possible sets of argument values, respectively. These are shown below:
The result of the function for each of these possible argument values can be represented by a Boolean vector of length 2*n (one element for each set of argument possibilities). The Boolean function is completely defined by this vector of function results, which is called the intrinsic vector [3] of the function. Since there are 2*2*n distinct intrinsic vectors, there are 2*2*n distinct functions of n variables. Suppose that the intrinsic vector for a twovariable function is 0 1 1 1 ; this means that when the argument values are both 0, the result is 0; for any other combination of argument values, the result is 1. In fact, 0 1 1 1 is the intrinsic vector for the “or” function. The following table is adapted from one given in APL Language [9]:
The rows headed ⍺ ⍵ represent the four possible sets of arguments that a dyadic Boolean function can have. Each column of the table to the right is the intrinsic vector for one of the 16 dyadic Boolean functions. For the nontrivial functions, the corresponding APL function symbol is appended. Note, for example, that the column with elements 0 1 1 1 has ∨ appended to it. The publication points out:
For example, suppose we set a←0 0 1 1 and b←0 1 0 1 (this gives us in the corresponding elements of a and b all pairs of arguments). Then the result of the expression a<b≤a=b≥a>b≠a∨b∧ab is 1 0 0 0 . Looking in the table, we find that the column with value 1 0 0 0 has appended to it, so it must be that the long expression is replaceable by ab , and such is the case. The ten dyadic functions we’ve been discussing
are called the nontrivial Boolean dyadic functions,
but there is a sense in which everything
connected with logic is trivial.
The medieval curriculum comprised the seven liberal arts.
These were classified into two groups.
The higher group contained the four subjects
of geometry, astronomy, arithmetic,
and music and was called the quadrivium.
The elementary group contained the three subjects
of grammar, logic, and rhetoric and was called (are you ready?)
the trivium, from whence comes the adjective trivial.
Now, at Last, for the Recreation Part Now that we have the ten dyadic Boolean function symbols, the urge to classify arises and must be appeased. If you were asked to sort the symbols into two piles based on their geometry, how would you do it? The chances are good that some of you would put the symbols with a caret shape in one pile and those without a caret in the other, thus creating a caret pile and a stick pile. You know from the history I’ve given you how arbitrary the association is that groups the caret functions together, however, it is possible to show more intrinsic groupings. Suppose you were asked to sort the symbols into two piles based on their intrinsic vectors. Again, I believe that some of you would consider the parity of the vector sums as a way of classification. Doing this, you would find that the even sums correspond to the trivial and stick functions, and that the odd sums correspond to all the caret functions. Is that all? No, it isn’t. Consider further the behavior of each of the functions when used to scan a truth table. Observe the following figure:
Below a is a truth table of order 3. Next to it are the ten results of scanning a using each one of the Boolean dyadic functions as shown. If you check this closely, you will find that the number of distinct rows in the result is given by the number at the bottom of the result, that the stick functions each return as many distinct rows as there are rows in the truth table (eight in this case, 2*n in general), and that the caret functions return one more than the number of columns (n+1 in general). Thus we have found three distinct ways of showing how the Boolean dyadic functions can be categorized into the caret functions and the stick functions. I’ll end with an illustration of the unity of the caret functions which I came across many years ago and which I call the “Whirling Caret”. Let’s take the caret function symbols, using Euler’s and in place of Bouguer’s ≤ and ≥ , and place them in a four by four square, which has its rows indexed by the first half of the intrinsic vectors and its columns indexed by the second half. For example, we would enter the ∨ symbol, which has intrinsic vector 0 1 1 1, at the entry having row label 0 1 and column label 1 1 . Doing this for all eight symbols gives us: Observe that the caret symbol is rotated clockwise 90 degrees from box to box, going clockwise about the edges of the square, and that below the “equator”, the symbol is negated. I won’t do any more than to say that the symbols for
the functions appear to have been chosen
with an aptitude bordering, like Cleveland, on eerie.
Problems
References
Puzzle Solutions (The following solutions refer to problems posed in the March 1978 issue of APL Quote Quad, pp. 43, 467.) Page 43 — You were asked to write a function that prepares a table of all patterns of ⍺ 1’s and ⍵⍺ 0’s, for ⍺≥0 and ⍵≥⍺ . T.P. Holls of Poughkeepsie, New York, gives (in 0origin): f: ⍉(⍺=+⌿r)/r←(⍵⍴2)⊤⍳2*⍵ This is correct, but liable on many systems to use a large amount of space. The following doubly recursive function is more compact: g: (0,⍺g⍵1),[⎕io]1,(⍺1)g⍵1: ⍺∊0,⍵:(1,⍵)⍴⍺=⍵ Page 46
Correction —The answer given
for the cosine problem (page 48) should have
read ○/99⍴2 ,
not ∘/99⍴2 .
Supplement — Some additional entries were received for the “Puzzle of the Year, 1978”. Paul Penfield of MIT provided a solution for 54: ⌊*197+8 . Roger Hui of Edmonton, Alberta, provided seven better solutions: 17 6 1978 36 7 1⊥⍳97⌊8 38 7 19×⌈7⍟8 45 7 1⊥⍳9⌊78 54 8 1⌈9×78 55 7 1⊥97↑8 92 8 1⊥9↑7+⍳8 and Alan Perlis of Yale also attacked 54,
coming up with 1⌈9×7×8 .
Hui’s solution for 92 and all three solutions for 54 eliminated
the last 9character solutions.
E. E. McDonnell First appeared in
APL QuoteQuad, Volume 8, Number 4, 197806.
The text requires the APL385 Unicode font, which can be
downloaded from
http://www.vector.org.uk/resource/apl385.ttf .
To resolve (or at least explain) problems with displaying
APL characters see
http://www.vector.org.uk/archive/display.htm .
