Tilting at Windmills: a New Attack on Nested Arrays

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 135

Abstract¶

This article is a proposal for a new notation for nested arrays, a notation the author feels is more consistent with the simple array APL concepts used before nested arrays were implemented. The proposal is to have all simple array APL functions work at the simple array level just as scalar functions work at the scalar level. An operator would be used to make simple array functions into nested array functions which would work on the simple array elements of nested arrays in ways similar to the way the simple array functions worked on the scalar elements of simple arrays. Motivations for the proposal are discussed.

Simple Arrays¶

Back in the days before nested arrays, there were only objects which I will refer to as simple arrays. The elements of simple arrays were scalars, usually of uniform data type. Scalar functions were defined for arrays as working element-by-element through the arrays, that is at the lowest level of the array. Scalar expansion was defined by saying that the scalar argument would be used for each of the scalar elements in the array. The functions which manipulate simple arrays, like rho or ravel or iota, I will call simple array functions. Simple array functions are defined to include operator-derived functions like inner and outer product.

Nested Arrays¶

I will define nested arrays as arrays in which each element is a simple array or scalar. Just as scalar functions work at the scalar level, I define simple array functions to work at the simple array level. This means that simple array functions work element-by-element through nested array arguments. Below, I will refer to this definition as Rule 1.

A simple array argument could be expanded by saying that the simple array argument would be used for each of the simple array elements in the nested array. Below, I will refer to this definition as Rule 2.

I need to expand the definition of nested arrays by saying that nested arrays may have elements that are themselves nested arrays. Rule 1, simple array functions, and Rule 2, simple array expansion, would then be applied recursively until a simple array was reached.

For ease in illustrating, I will display nested arrays as enclosed in braces, with simple arrays separated by semi-colons. For example, if A,B,C and D are simple arrays, then {A;B} + {C;D} is defined as {A+C;B+D} according to Rule 1. Similarly, Rule 1 indicates that +/{A;B;C} is defined as {+/A;+/B;+/C} because +/ is a simple array function. Simple array expansion means that A,[1]{B;C} is defined as { A,[1]B ; A,[1]C } according to Rule 2.

To illustrate the recursive use of Rules 1 and 2 I will use {A;{B;C}} to indicate a nested array in which the first element is the simple array A, and the second element is a nested array of simple arrays B and C. Then if D and E are simple arrays {A;{B;C}}-D is defined as {A-D;{B-D;C-D}} by applying Rule 2 recursively. Similarly, {A;{B;C}}-{D;E} is defined as {A-D;{B-E;C-E}} using both rules.

Nested Array Functions¶

Nested array functions will be derived from simple array functions with a left operator, the dollar sign. I think $ is a good choice because it is a widely available character that currently isn’t being used for anything by APL. A derived nested array function is defined as working on nested arrays in a way similar to the way the simple array function works on simple arrays. For example:

{A;B} $, {C;D} is defined as {A;B;C;D}
just as 1 2, 3 4 is 1 2 3 4.

A little bit more complex,

{A;B} $+.= {C;D} resolves to (A=C)+(B=D)
just as 1 2+.=3 4 is (1=3)+(2=4).

It should be noted that $⍴ {A;B;C} is defined as 3 but
⍴{A;B;C} is defined as {⍴A;⍴B;⍴C} which is not the same.

The definition of $ above allows making a nested array containing two nested array elements, that is of depth greater than 2 using enclosure, that is

(⊂{A;B}) $, ⊂{C;D} defined as {{A;B};{C;D}}.

A New Null Element¶

One of the implications of this scheme is that there will be a null nested array with a nested length of 0. The notation for this would be defined so that

{A;B} $, 0 $⍴ X gives {A;B} as a result where X is any scalar, simple array or nested array.

The depth of the null nested array is 2. It’s not clear what the simple array rho of the null nested array should be. Perhaps zero would be convenient.

Simple Array Indexing¶

It may be redundant but I feel compelled to start my discussion of indexing by reminding the reader that {A;B}[C] is defined as {A[C];B[C]} because indexing is a simple array function which according to Rule 1 applies element by element to a nested array. For a nested array index to a simple array Rule 1 implies that A[{B;C}] is defined as {A[C];B[D]}. I think that similar methods can easily be used to resolve simple indexing in higher dimension objects for nested arrays. I will leave this elaboration to the student as an exercise. (I always wanted to say that.) It then seems logical to look at simple indexed assignment in similar fashion:

{A;B}[C]←D is defined as {A[C]←D;B[C]←D} using both Rule 1, the indexed assignment applying to the elements of the nested array, and Rule 2, the simple array being expanded.

For the more complex case {A;B}[C]←{D;E} is defined as {A[C]←D;B[C]←E} where A, B, C, D and E are simple arrays.

For the trickiest case, if F is also a simple array then {A;B}[{C;D}],←{E;F} is defined as {A[C],←E;B[D],←F} using Rule 1 element-by-element for the nested array index as well as the other nested array arguments.

Nested Array Indexing¶

Nested array indexing works on nested arrays in a fashion similar to the way simple indexing works on simple arrays. Indexing a nested array with a simple array index gives nested array results whose simple array elements are positioned like the scalar elements would be for a simple array indexed by a simple array. For example, {A;B;C;D}$[1 3 1 4] is defined as {A;C;A;D} just as 'ABCD'[1 3 1 4] would be 'ACAD'. In a special case, the result of a nested array indexed by a scalar is a simple array just as a simple array indexed by a scalar is a scalar. For example, {A;B;C}$[1] is defined as A a simple array result, just as the result of 'ABC'[1] is a scalar 'A'.

For a nested array index to a nested array, the most useful definition is not obvious. I think that the best thing to do is to define it as a nested array of the results from each simple array element of the index applied to the nested array. This definition would mean, for example, that {A;B;C;D}$[{{1 3};{2 4}}] would be {{A;C};B;D}}.

For the multi-dimension case, the result would be a nested array which exhausted every combination of simple array elements. If we define, for example, NN as a nested matrix then NN$[{A;B} ; {C;D}] would be 2 2$⍴{NN$[A;C];NN$[A;D];NN$[B;C];NN$[B;D]} where each of the indexing operations on NN would follow the method for simple array indexes of nested arrays. This definition is consistent with the case where if A is a simple matrix then A[1 2;3 4] is 2 2⍴A[1;3],A[1;4],A[2;3],A[2;4].

User Functions¶

Should user-defined functions be simple array functions or nested array functions? Probably the user should have the option to define them either way. If a dollar sign appeared in the header just before the function name, the function would always be a nested array function. If called with nested array arguments, such a function would be passed the arguments as nested arrays.

The default should be that all user functions would be assumed simple array functions. Such functions would use Rule 1 to process nested arguments. If UFUN is a user-defined function without a $ in the header, then UFUN {A;B} would be {UFUN A;UFUN B} and UFUN itself would not be able to see that it had been called with a nested argument.

The nesting operator should work for user functions as well as native interpreter functions. The operator $ placed before a user function name would feed the nested array argument into the function instead of calling it repeatedly using Rule 1. It would then be possible to define functions that could work either as simple array functions or nested array functions.

Why Bother?¶

I think this scheme is "more APL-like" than current nested array implementations and would therefore be less confusing and easier to learn. Let me expand on this point.

I have felt for some time that the shift from simple array APL to nested array APL is needlessly confusing. I think the confusion comes from the difference between the behaviour of scalar functions on arrays and the need to disclose nested array elements to work on them. If scalar functions worked on simple arrays the way most functions work on nested arrays, then you would write A+¨B to add all the elements of simple arrays A and B together. Unconsciously, the student expects that the "for each" will be assumed for nested arrays just as it is for scalar functions working on simple arrays.

This confusion is NOT a figment of my imagination nor the result of a unique personal learning difficulty. Since I first wrote about this in 1982, I have had the opportunity to talk to lots of APLers about nested arrays. Most thought learning them difficult. Some found them so confusing they don’t use them at all. Even several APL fanatics at the APL91 conference admitted to me that they don’t use nested arrays because they’re too confusing to be worth the trouble.

The scheme I propose has a lot of educational economy built into it. It builds on the methods of handling simple arrays to introduce nested arrays. You already know how nested array index or nested array catenate is going to work because it works just like the simple array function does. A similar method was used to add networking commands to UNIX. The UNIX remote copy command, rcp, works just like the ordinary copy command, cp, except that it works using somebody else’s machine. Think of the leading "r" as an operator.

In contrast with the scheme I propose, current methods have negative educational economy. All current methods of nested array implementation have formerly predictable simple array functions doing seemingly arbitrary things with nested arrays. These behaviours when applied to unintentional nested arrays created by strand notation can get even experienced APL programmers into deep debugging doo-doo. Here I speak from personal experience of working with 5- to 20-person APL teams for over 5 years. As the "debugger of last resort" I tracked down a lot of these problems for everyone from the beginners to APLers who had years’ more practical experience than I did.

I think this state of affairs is unfortunate because it is limiting our ability to teach APL to the masses. It used to be that APL required the student to learn only as much as was required for the problem at hand. What he didn’t know couldn’t hurt him because he wouldn’t use it accidentally. The current implementations of nested arrays with strand notation make what the student doesn’t know dangerous, causing problems with objects he will be unable to identify, let alone fix on his own.

Where Do We Stand Now?¶

I have great confidence that this proposal has merit. I first wrote about it in March of 1982. While I have refined the idea a lot since then, I have not changed the basic scheme much at all.

I do not have any confidence at all that this proposal will receive any serious consideration from implementers, the APL Standards Committee, or anybody influential or powerful. The reactions of all of these people when I discussed this with them have not changed in the last 13 years. It is uniformly assumed that (a) I have an obvious learning disability because I can’t learn to love nested arrays as they are; (b) I am extremely silly to suspect that people of superior intellect, such as those who designed nested array implementations, could be as fallible as any ordinary mortal, such as myself; and (c) I am naive in the extreme to expect that the greedy capitalists who pay the bills for implementers would ever write off the investment made in implementing the current design.

Standards Deadlock Broken¶

At APL91, the Standards Committee representatives jubilantly reported that they had reached agreement on a standard for nested arrays. All previous disagreement had been resolved miraculously. How did this miracle happen? Did the Lord come to all the members in a dream and tell them what the standard should be? Unfortunately, the result seems to have been far closer to the "Barebones" Parliament of Cromwellian England. It seems that all of the representatives who had argued in past deliberations against the position the committee approved were not present at the meeting where the proposal was adopted. Their companies were no longer interested, having left the APL language field.

I’m not convinced that exhaustion necessarily means that the issue has been optimally settled. While I realize that it is commercially a dead issue for now, I hope that the process of "creative destruction" capitalism is famous for may eventually yield a better result. Until then, tilting at windmills is good exercise.

Reference¶

This article is a re-statement and expansion of "A Notation for Nested Arrays" published in "The Special Character Set, Number 3", the then official newsletter of the APL Special Interest Group of the Digital Equipment Computer Users Society, March 15 1982, pp. 14–16. It is unlikely to be still in print, but hopefully is not necessary for understanding this paper. The DECUS APL SIG has since merged into a Languages and Tools SIG.

Douglas R. Bohrer
Kemper Securities Inc.
77 West Wacker Drive
Chicago, Illinois 60601-1994, USA