In 1962 the Canadian Kenneth Iverson, who had taught at Harvard and was then working at IBM, published a book called A Programming Language. Despite the title, it was a book of mathematical notation: a way of writing algorithms concisely and precisely, with new symbols for operations on whole lists and tables of numbers. A few years later IBM itself turned this notation into a language a computer could run, and it took the name of the book: APL.

Floor, ceiling and bracket

Some of Iverson’s signs left APL and entered ordinary mathematics. The best known is the pair floor and ceiling:

$$\lfloor x \rfloor = \text{the largest integer} \le x, \qquad \lceil x \rceil = \text{the smallest integer} \ge x.$$

Before him, people wrote $[x]$ or “integer part of $x$”, and there was no sign for the ceiling. With the two of them, calculations that needed several cases fit on one line: the number of multiples of $7$ between $1$ and $100$ is $\lfloor 100/7 \rfloor = 14$.

Another sign, the Iverson bracket, turns a statement into a number:

$$[P] = \begin{cases} 1, & \text{if } P \text{ is true,} \\ 0, & \text{if } P \text{ is false.} \end{cases}$$

With it, “count the even numbers from $1$ to $n$” becomes an ordinary sum, $\sum_{k=1}^{n} [k \text{ is even}]$, and the sum can be handled with the usual rules. Donald Knuth defended the bracket in 1992 in a paper called Two notes on notation and used it throughout the book Concrete Mathematics, written with Ronald Graham and Oren Patashnik. The Kronecker delta of the previous text is just a special case: $\delta_{ij} = [i = j]$.

The five qualities

In 1979 Iverson received the Turing Award, the highest prize in computing, and gave a lecture whose title became a catchphrase: Notation as a tool of thought. In it he listed five qualities of a good notation:

  1. Ease of expressing the ideas that arise in problems.
  2. Suggestivity: the form of the writing suggests steps and generalisations.
  3. Subordination of detail: what does not matter stays hidden.
  4. Economy: few signs, combined in many ways.
  5. Amenability to proofs: the writing lends itself to formal demonstrations.

It is the same idea this book calls active notation, put by someone who spent his life designing one. APL took it to the extreme: whole programs fitted on one line, written with a special keyboard full of Greek and mathematical symbols. For those who mastered it, it was an extraordinary tool of thought; for everyone else, it looked like a cipher. No one has managed to prove that a denser notation is always better.

The importance of nomenclature, notation, and language as tools of thought has long been recognized.

— Kenneth Iverson, Notation as a Tool of Thought (1980)
Exercise: counting with brackets

Compute $\sum_{k=1}^{30} [3 \mid k]$, where $3 \mid k$ means “3 divides $k$”, and check it with the floor.

The sum is $1$ for $k = 3, 6, 9, \ldots, 30$ and $0$ for the others: there are $10$ terms equal to $1$. By the floor, $\lfloor 30/3 \rfloor = 10$. In general, $\sum_{k=1}^{n} [d \mid k] = \lfloor n/d \rfloor$, and the equality shows Iverson’s two signs talking to each other.

Exercise: floor and ceiling

Compute $\lfloor 2.7 \rfloor$, $\lceil 2.7 \rceil$, $\lfloor -2.7 \rfloor$ and $\lceil -2.7 \rceil$.

$\lfloor 2.7 \rfloor = 2$, $\lceil 2.7 \rceil = 3$, $\lfloor -2.7 \rfloor = -3$ and $\lceil -2.7 \rceil = -2$. The last two show why “integer part” was an ambiguous name: for negative numbers, “chopping off the decimals” gives $-2$, which is the ceiling, not the floor. Iverson’s notation forces one to say which of the two is meant.

Chapter index · ← Tribal conventions: Einstein, Bourbaki and the initiated reader · The equals sign that gives orders: x = x + 1 and programming languages →