About Array Theory

Array theory is a one-sorted theory of nested rectangular arrays that combines the Zermelo-Fraenkel concept of nested sets with the vectors, matrices, and multi-axis arrays of Iverson and Falkoff’s programming language APL. As every element of a set is again a set in set theory, every item of an array is again an array in array theory. The consequent unbounded depth of nesting ultimately terminates in arrays that have no axes and hold themselves as sole items. Such self-containing “atoms” include numbers, truth-values, characters, and indivisible strings of characters called phrases and faults. For example, the number 2 is a 0-axis array in which the sole item is the number 2.

The flat arrays of APL, a language implemented and extensively applied in the late 1960s, had many similarities to the flat, tensor representing, “n-way matrices” that Gabriel Kron introduced into electrical engineering in the 1930s and 1940s. On joining the APL Design Group at IBM’s Yorktown Research Center in 1968, Trenchard More originated array theory by combining multi-axis arrays with set-theoretic nesting and Quine’s controversial concept of self-containment. The search for a maximal number of universally valid equations while preserving consistency led More through successive versions of the theory. Later versions benefited from implementations first by Willard Bouricius at Yorktown, and then when More moved to the IBM Cambridge Scientific Center in 1974, by Anthony Hassitt, Leonard Lyon, and Robert Creasy at the IBM Palo Alto Scientific Center.

Mike Jenkins, an IBM Visiting Scientist who had been actively studying tree-like extensions to APL at Queen’s University, joined More at the Cambridge Center in 1979. Over the next 5 years they collaborated on the design of Nial and the refinement of array theory. The Q'Nial interpreter was developed at Queen's during this time and released in 1983 as Version 4 of Q'Nial. To avoid contradiction, the most controversial result was that there are as many different empty arrays of a given shape as there are arrays themselves. Arrays of the same shape differ according to their virtual items. A list of no 2s differs from a list of no 3s!

This initial version of Q'Nial reflected the desire to stay close to More’s theoretical ideas, while providing procedural control, flexible file handling and interactive input/output. The intent of the design was to follow More’s equations as well as those Jenkins developed to support the implementation functionality.

After ten years of feedback from programmers using Q’Nial, Jenkins undertook a major redesign of the language and its implementation. The resulting Version 6 of Q’Nial sacrificed some of the generality of the functional model and modified More’s theory by requiring that there be only one empty array of any given shape. One can now compare an abstract Version 4 of array theory with a more conventional, conformal Version 6.

Jenkins continues to support Version 6.0 of Q'Nial. He also provides binary versions that support the array theory used in Version 4 on request. Contact him at jenkins@nial.com to request the Version 4 binary.

More continues to develop the abstract version of the theory. He is developing a web site to provide more information on array theory. A link to his site will be added here when it is completed.

Last Modified: Nov 2006