﻿ The Caret and the Stick Functions

Recreational APL
Eugene McDonnell
June 1978

The Caret and the Stick Functions

 The power of using logical expressions as arithmetic operands is very great, as has been shown by Iverson. — George Radin and Paul Rogoway, “NPL: Highlights of a New Programming Language”, CACM 8, 1965 But voluntarie signes, it is inoughe to knowe that this thei doe signifie. And if any manne can divise other, more easie or apter in use, that maie well be received. — Robert Recorde, The Whetstone of Witte, 1557

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 (1510-1558) in 1557 [2]. Recorde writes:

 And to avoide the tedioufe repetition of thefe woordes : is equalle to : I will fette as I doe often in woorke ufe, a paire of paralleles, or Gemowe (i.e., twin) lines of one lengthe, thus: == , bicaufe noe.2. thynges, can be moare equalle.

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 relational statement (α R β) is a logical variable which is true (equal to 1) if and only if α stands in the relation R to β.

The Englishman Thomas Harriot (1560-1621), 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 (1707-1783) seems to have been the first to use the not-equal 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, namelyand , 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” andfor “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]:

 One view of simplicity might exclude as redundant those functions which are easily expressed in terms of others. For example, ... ∧/l may be written as ~∨/~l . From another viewpoint it is simpler to use a more complete or symmetric set of primitives, since one need not remember which of a pair is provided and how to express the other in terms of it. In APL, completeness has been favored. For example, symbols are provided for all of the non-trivial logical functions, although all are easily expressed in terms of a small subset of them.

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 wereandoverstruck 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 hadand .

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:

 0 1 2 3 empty 0 0 0 0 0 0 vector 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

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 two-variable 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]:

 ⍺ ⍵ 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 > < ≠ = ≥ ≤

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 hasappended to it.

The publication points out:

 ... any boolean expression of two arguments ⍺ and ⍵ can be replaced by a simple APL expression as follows: evaluate the expression for the four possible cases, locate the corresponding column in the table, then use the function symbol at the foot of the column, or, if none occurs, use ⍺ or ⍵ or ~⍺ or ~⍵ or 0 or 1 as appropriate.

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:

 a <\a ≤\a =\a ≥\a >\a ≠\a ∨\a ∧\a ⍱\a ⍲\a 000 000 011 010 010 000 000 000 000 010 011 001 001 011 011 011 000 001 001 000 011 011 010 010 011 001 000 000 011 011 000 001 011 011 010 011 000 000 000 010 011 000 001 011 100 100 101 101 111 111 111 111 100 100 110 101 100 101 100 111 111 110 111 100 100 110 110 100 110 110 111 100 100 111 110 100 100 111 100 111 111 111 101 101 111 111 100 101 4 4 8 4 4 8 4 4 4 4

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’sand , 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 thesymbol, 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

1a.  The relational functions are not the only non-Boolean functions that become Boolean when their arguments are restricted to 0 and 1. Multiplication, for example, is Boolean (as George Boole showed in 1848 [10]). What other non-Boolean scalar functions become Boolean under this restriction of arguments?

b.  It’s possible to define some Boolean functions on an extended domain. What extended definitions are suitable for the functions in the table below?

 Symbol Function Reference ~ not Boole [10] ∧ and McDonnell [11] ∨ or McDonnell [11] ⍲ nand unsolved problem ⍱ nor unsolved problem

2a.

As shown by Pierce (1880) and Sheffer (1913), the nor function can be used by itself to generate all 16 dyadic Boolean functions. Given a←0 0 1 1 and b←0 1 0 1 , for example, the intrinsic vector for the and function can be obtained by (a⍱a)⍱b⍱b . Provide the shortest expression possible for each intrinsic vector, 0 0 0 0 through 1 1 1 1 , using only the symbols a , b , , ( , and ) and usingat least once. The shortest expressions known for each intrinsic vector (shown below evaluated in base 2) are the following:

 2⊥intrinsic vector 0  1  2  3  4  5  6  7 length 5  9  5  9  5  9 15  9 2⊥intrinsic vector 8  9 10 11 12 13 14 15 length 3 13  3 13  3 13 21 13

b.

Afterward, Sheffer also showed that the nand function can be used by itself to generate all 16 dyadic Boolean functions. Given the same a and b as in 2a., provide the shortest possible expression for each intrinsic vector (as in 2a.), but using only the symbols a , b , , ( , and ) and usingat least once. The shortest expressions known for each intrinsic vector (again shown evaluated in base 2) are as follows:

 2⊥intrinsic vector 0  1  2  3  4  5  6  7 length 13  9 13  9 13  9 13  9 2⊥intrinsic vector 8  9 10 11 12 13 14 15 length 21 15  3  5  3  5  3  5

3.  The stick function scans on Boolean arguments are information preserving: you can tell uniquely what the argument was if you see the result. Furthermore, if you apply one of the stick scans often enough, you will obtain your original argument. How many times, in terms of ⍴v , does a stick function scan have to be applied, in general, to a Boolean vector v in order to get v back again?

4.  The “trivial” Boolean dyadic functions (for which APL provides no symbols) have some interesting properties. What is the number of distinct rows in the scans, using the trivial functions, of a truth table of order n ?

References

 1 McDonnell, E.E. The caret functions. Proc. of the Sixth International APL User’s Conference, Anaheim, Calif., 1974. 2 Cajori, F. A History of Mathematical Notations, Vol. I, Notation in Elementary Mathematics, Open Court, LaSalle, Ill., 1928. 3 Iverson, K.E. A Programming Language. Wiley, New York, 1962. 4 Ball, W.W.R. A Short Account of the History of Mathematics. Dover, New York, 1960. 5 Quine, W.V.O. Mathematical Logic. Harper Torchbooks, New York, 1962. 6 Tarski, A. Some observations on the concept of ⍵-consistency and ⍵-completeness. Translated from the original paper: Einige Betrachtungen über die Begriffe der ⍵-Widerspruchsfreiheit und der ⍵-Vollständigkeit, Monatshefte für Mathematik und Physik 40, (1933), 97-112. 7 Falkoff, A.D., and Iverson, K.E. The design of APL. IBM Journal of Research and Development 17, (1973), 324-334. 8 Calingaert, P. Private communication. 9 APL Language. IBM Publication GC26-3847, Jan. 1976. 10 Boole, G. An Investigation of the Laws of Thought. Dover, New York. 11 McDonnell, E.E. A notation for the GCD and LCM functions. APL 75 Congress Proc. (Pisa), ACM, New York, 1975.

Puzzle Solutions

(The following solutions refer to problems posed in the March 1978 issue of APL Quote Quad, pp. 43, 46-7.)

Page 43 — You were asked to write a function that prepares a table of all patterns of1’s and ⍵-⍺ 0’s, for ⍺≥0 and ⍵≥⍺ .

T.P. Holls of Poughkeepsie, New York, gives (in 0-origin):

`   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

 1 The inverse of 16807, mod 2147483647, is 1407677000. 2 In APL\360 and its descendants, the technique for computing ?n for n>2*31 uses two successive values of ⎕rl to produce the desired result. Thus, ?2*32 will advance ⎕rl by two steps. 3 The “Petals Around the Rose” problem was solved by T.P. Holls (1-origin): ` a←(d-1)+.×2|d←?5⍴6` If you were unable to determine by inspection how to solve the problem, you might have done the following: assume the result is linearly related to the roll of the dice. Then, if m is the 16 by 5 matrix whose rows are the values of the dice as shown in the problem, and x is the vector of corresponding answers shown, the expression (1-origin) ` r←x⌹+/[2]m∘.=⍳6` gives a six-element vector result r , where r[i] is the value associated with the appearance of a die with i dots on it in the result. That is, we have solved an overdetermined linear system, a set of 16 simultaneous equations in 6 unknowns. The expression ` (⎕ct<|r)×r` gives ` 0 0 2 0 4 0` showing that a die with a value of 3 is counted as 2, and a die with a value of 5 is counted as 4. You must figure out the significance of the name “Petals Around the Rose” for yourself.

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: ⌊*19-7+8 . Roger Hui of Edmonton, Alberta, provided seven better solutions:

```17  6  19|-78
36  7  1⊥⍳97⌊8
38  7  19×⌈7⍟8
45  7  1⊥⍳9⌊78
54  8  1⌈9×7|-8
55  7  1⊥9-7↑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 9-character solutions.

E. E. McDonnell
Palo Alto, California

First appeared in APL Quote-Quad, Volume 8, Number 4, 1978-06. 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 .

last updated: 2009-08-26 17:00