Reflexive Data Domains

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

1. Nested Arrays¶

1.1 The idea this time around is to show how the notation defined previously can be used to describe first lists, and then nested arrays in general.

If we define a typical first generation APL data space as

SIMPLE ← (ℍ*ℕ*ℕ)⊕(ℝ*ℕ*ℕ)

then, as in K, (A;B;C) being a three element vector, each of whose elements is a simple array, we can make the assertion

(A;B;C)∊SIMPLE*3 .

This can be extended, of course, so that lists are elements of the domain SIMPLE*ℕ , while the domain of rectangular arrays of rectangular arrays is SIMPLE*ℕ*ℕ.

1.2 This is OK as far as it goes, but we have defined one depth of nesting only:

DEPTH₁   = SIMPLE*ℕ*ℕ.

We can also construct depth-2 nested arrays from depth-1 nested arrays, or, more succinctly,

DEPTH₂   = DEPTH₁*ℕ*ℕ

and, in general,

DEPTHₙ₊₁ = DEPTHₙ*ℕ*ℕ

and so on, and so on, ad infinitum.

Observe that, just as ℝ*ℕ*ℕ included all scalar values from ℝ, so also

the domain of arrays of arrays defined by SIMPLE*ℕ*ℕ
includes, in particular, SIMPLE*ℕ*0
which reduces to SIMPLE*∅
which reduces to SIMPLE

and, by induction, the domain definition at each depth of nesting properly includes all its predecessors.

1.3 The task now is to find an expression which defines the domain of nested arrays, in all its generality. Consider the following:

DEPTH₁   = SIMPLE*ℕ*ℕ
DEPTH₂   = DEPTH₁*ℕ*ℕ
            = (SIMPLE*ℕ*ℕ)*ℕ*ℕ
DEPTH₃   = DEPTH₂*ℕ*ℕ
         = ((SIMPLE*ℕ*ℕ)*ℕ*ℕ)*ℕ*ℕ

This way lies madness: either we have an infinite number of domain definitions, or we have a domain definition of infinite length. What we really need is some way of expressing this infinite recursion.

1.4 We first define a function ENCLOSE, acting on a domain D, such that

ENCLOSE(D)  = D*ℕ*ℕ

which can then be used to rewrite the above as a recurrence relation

DEPTH₀   = SIMPLE
DEPTHₙ₊₁ = ENCLOSE(DEPTHₙ) .

This is classic tail recursion, and can equally well be represented by repeated function application:

DEPTHₙ   = ENCLOSE(ENCLOSE...ENCLOSE(SIMPLE)...)

What we want, the set of all nested arrays, is the closure of SIMPLE, with respect to the ENCLOSE function, and this we can write as

(ENCLOSE*ℕ) SIMPLE.

This may require some justification. (If you find all this intuitively obvious, then feel free to skip to the next section — the next bit is detailed but not difficult.)

1.5 A set D is closed with respect to a function f , if

for all x, x ∊ D implies that f(x) ∊ D as well.

For example, taking the square of a natural number will always give us a natural number, so we say that "the natural numbers are closed with respect to the squaring operation". They are not closed with respect to the square-root operation, however: 2 is a natural number, but √2 is not.

Obviously, if f(x) ∊ D, then f(f(x)) ∊ D by definition.
And so is f...f(f(f(x)))...) .

Instead of using repeated function application, we could write the same thing using function composition. Using the conventional notation of (f∘g) to denote the composition of f with g, then f(f(x)) can be rewritten as (f∘f)(x) . For instance, if f is the squaring function, then the derived function (f∘f) raises its argument to the fourth power.

If we denote the set of all functions by _, then f∊_ and (f∘f)∊(_⊗_) .

1.6 Repeated function composition is frequently written using exponentiation¹, thus:

f⁰(x)  = x
f¹(x)  = f(x)
f²(x)  = (f∘f)(x)
f³(x)  = (f∘f∘f)(x)
:
fⁿ(x)  = (f∘...f∘f∘f)(x)

and, following this convention, we can state that

f⁰  = ∅
f¹  ∊ _
f²  ∊ _⊗_
f³  ∊ _⊗_⊗_
:
fⁿ  ∊ _*n , etc, etc.

This is starting to look familiar: just as ℝ*ℕ is the set of all finite-length vectors of real-valued numbers, so _*ℕ is the set of all finite-length vectors of function definitions.

To put it another way, _*ℕ is the closure of the set _ under composition and, in particular, f*ℕ (where f∊_, and so f*ℕ is a subset of _*ℕ) is the closure of the set {f} under composition. What we want is something slightly different: an expression for the closure of the set {x} under the function f.

1.7 If a vector of function definitions is applied to an argument, then (conceptually) the serial composition of those functions is first constructed, and the resultant derived function is then applied to the argument in question.

For example, if COMPO∊_*ℕ , then we know what is meant by COMPO(x) , where x is a single argument. (That is, COMPO(x) means (i) the composition of the functions in COMPO, followed by (ii) the application of the derived function to x - although, in practice, this would probably be achieved through successive application of the individual functions. The difference is a matter of pragmatics, not semantics.)

We now adopt the convention that a set of functions applied to the same single argument produces a set of results.

With that convention, the expression (ENCLOSE*ℕ) SIMPLE denotes the domain sum of the series obtained by the application of each element of ENCLOSE*ℕ to the argument SIMPLE, i.e:

DEPTH₀  = (ENCLOSE*0)SIMPLE
        =  SIMPLE
DEPTH₁  = (ENCLOSE*1)SIMPLE
        =  ENCLOSE(SIMPLE)
DEPTH₂  = (ENCLOSE*2)SIMPLE
        = (ENCLOSE∘ENCLOSE)SIMPLE
DEPTH₃  = (ENCLOSE*3)SIMPLE
        = (ENCLOSE∘ENCLOSE∘ENCLOSE)SIMPLE
:
DEPTHₙ  = (ENCLOSE*n)SIMPLE
        = (ENCLOSE∘ENCLOSE∘ ... ∘ENCLOSE)SIMPLE
:

and finally:

NESTED  = (ENCLOSE*ℕ)SIMPLE.

Normally, the notation would imply that we take the domain sum of all earlier values in the series,

NESTED  = ∑ DEPTHᵢ ,
         i∊ℕ

but we already know that each element in the series includes all arrays of lesser depth, so the domain sum of all items in the series is the same as the last item generated by the series, so you are free to think of it as

NESTED  = Lim DEPTHₙ
          n→∞
        = Lim (ENCLOSE*n)SIMPLE
          n→∞

should that prove more congenial or convenient.

2. Other Approaches¶

2.1 Even after that mind-numbing display of pedantry, the notation may prove a trifle awkward later.

The convention that "a set of functions applied to the same single argument produces a set of results" implies that we can always distinguish the cases where this convention applies. Functions are themselves sets, so we are claiming the ability to recognise a certain type of set of sets. This may not always be possible — when _ is an operand, for example — but we can worry about that later. There are no difficulties with the syntax defined so far.

2.2 Secondly, there is the need to name the ENCLOSE function.

Bear in mind that the ability to name an entity and the need to name an entity are different things. In "Stack Operations", we commented on the interesting question of what entities could be given names. The other side of the coin is equally interesting: what entities must be given names. Assembler programming, for instance, can be quite irritating because of the recurrent need to name all sorts of transient entities. K, Lisp and Perl allow the definition of anonymous functions²: APL requires a function definition to be given a name. Lisp and Perl take their inspiration from the lambda calculus, and so shall we, but without going into the subject in any depth.

If we examine a simple sample definition, like

ARRAY_OF ← λD.(D*ℕ*ℕ)

we find

i)

λ, the lambda itself, introducing a list of the names of the formal parameters;

ii)

D, the list (a very short list, in this case) of names of formal parameters;

iii)

the dot, marking the end of the list of names;

iv)

(D*ℕ*ℕ) , the "function body".

This definition can be assigned, thus:

ARRAY_OF ← λD.(D*ℕ*ℕ)

and applied by name, by prefixing it to its actual parameter, thus:

ARRAY_OF ℝ

or applied anonymously, thus:

(λD.(D*ℕ*ℕ)) ℝ.

The result of applying the function is obtained by substituting the actual parameter for the formal parameter throughout the function body, thus:

(ℝ*ℕ*ℕ) .

And that, for the time being, is all there is to it. Fans of one-liners can now rewrite our earlier definition as

NESTED   ← ((λD.(D*ℕ))*ℕ) (ℍ*ℕ)⊕(ℝ*ℕ) .

2.3 Another device often used is to name the domain, and include a reference to that name within its own definition, so that the definition becomes self-referencing, or recursive. Defining the domain of simple arrays in the normal way:

SIMPLE ← (ℍ*ℕ*ℕ)⊕(ℂ*ℕ*ℕ)

we could then use that definition in our named definition of nested arrays:

NESTED = SIMPLE ⊕ (NESTED*ℕ*ℕ) .

Note that the domain definition for simple arrays could be assigned. The "equals" sign in the definition of NESTED, however, is more problematic. It is not — it cannot be — assignment, and it is most certainly not the boolean test for equality, but something closer to "equals by definition", for which we lack a defined symbol.

2.4 What we want here is some equivalent to the "self" reference, making it clear that a domain definition is contemplating itself, and the obvious candidate is ◎, the "circle-jot" or "navel" symbol.

We can now write an anonymous, recursive, data domain definition for nested arrays, as follows:

SIMPLE ⊕ (◎*ℕ*ℕ)

which can therefore be assigned, thus:

NESTED ← SIMPLE⊕(◎*ℕ*ℕ) .

2.5 Problem solved? Not yet. There are problems with left recursion vs. right recursion, very like those encountered in the lexical phase of compiler writing.

The problem arises from the fact that infinite domains are not representable. Tests of domain membership can, of course, still be evaluated, by rewriting within the interpreter. An expression like X∊ℍ⊕ℂ, for example, would be converted into (X∊ℍ)∨(X∊ℂ), which can then be interpreted using built-in tests for membership of the primitive data domains.

Within a compiler, a typical finite state recogniser, proceeding from left to right, can handle right recursion without difficulty. Left recursion, however, will send the recogniser into an infinite loop, and must first be removed (before the recogniser is written, usually), using special techniques to convert left recursion into right recursion.

Here in APL-land, the other side of the Looking Glass, the rewriting system will be able to handle left recursion without difficulty, but, given an expression like X∊NESTED, it will need to convert the definition of NESTED from right recursion to left recursion. We can save the machine that difficulty, by re-arranging our definition, as follows:

NESTED ← (◎*ℕ*ℕ)⊕SIMPLE.

2.6 The universal data domain for a typical 2nd-generation APL, then, could be written:

𝔼 = (◎*ℕ*ℕ)⊕(ℂ*ℕ*ℕ)⊕(ℍ*ℕ*ℕ).

This still suffers from the drawback that the "navel" symbol is not well-defined. It is not difficult to construct a compound expression where the referent is less than obvious, unless some sort of scope rules are added to its definition.

3. Some Sample Descriptions¶

3.1 K

LIST_OF   ← λD.(D*ℕ)
SIMPLE    ← (ℍ*ℕ*y) ⊕ (ℝ*ℕ*y)   ⍝ see note 3
NESTED    ← (LIST_OF*ℕ)SIMPLE

The note³ explains y.

K is lean and mean. It recognises only atoms, drawn from the primitive data domains ℍ and ℝ, and lists, whose elements may be atoms or lists. These lists are precisely the "vectors" of APL, where the term includes all vectors of vectors, etc. Within the K lexicon, the word "matrix" is applied to lists meeting certain conditions of "rectilinearity". K does distinguish homogeneous arrays, and if this homogeneity is lost (following an indexed assignment, for instance), the array is automatically converted to a list of lists.

Syntactically, it uses pure parenthesis-and-semicolon notation to define these lists, and there is never any need for enclose or disclose operations.

3.2 mainframe APL

Ideally, we would hope to find a similar simplicity in the definition of APL. Something like this, for instance:

ARRAY_OF ← λD.(D*ℕ*ℕ)
SIMPLE   ← ARRAY_OF(ℍ⊕ℝ)
NESTED   ← (ARRAY_OF*ℕ)SIMPLE

but there are problems. The simple data space may be variously defined as

SIMPLE   ← ARRAY_OF(ℍ⊕ℝ)
SIMPLE   ← (ARRAY_OF ℍ)⊕(ARRAY_OF ℝ)
SIMPLE   ← (ARRAY_OF ℍ)⊕(ARRAY_OF ℂ)

but that is not the real problem. The main difficulty is the definition of nested arrays. Mainframe implementations typically define an enclose function, which converts an array to a boxed item (of rank 0), and nested arrays can then be built up from boxed items. The interesting thing is that these boxed items can exist independently. The following (failed) attempt illustrates the difficulty:

ARRAY_OF ← λD.(D*ℕ*ℕ)
SIMPLE   ← (ARRAY_OF ℍ)⊕(ARRAY_OF ℝ)
ENCLOSE  ← λA.(A)
BOXED    = ENCLOSE(SIMPLE⊕NESTED)
NESTED   = ARRAY_OF(BOXED) .

The last couple of lines do not deliver assignable results: we need that "equals by definition" again, for which we still lack a defined symbol. Also, the BOXED and NESTED domains are indirectly recursive, which is fine for declaratives, but we do not have any defined semantics for a declarative environment. The way out is to compose ARRAY_OF and ENCLOSE , and apply the function thus derived, allowing unlimited depth of recursion. Finally, we define the domain of boxed items separately - a necessary step only because boxed items are first class objects within the target language.

ARRAY_OF ← λD.(D*ℕ*ℕ)
SIMPLE   ← (ARRAY_OF ℍ)⊕(ARRAY_OF ℝ)
ENCLOSE  ← λA.(A)
NESTED   ← ((ARRAY_OF∘ENCLOSE)*ℕ)SIMPLE
BOXED    ← ENCLOSE(SIMPLE⊕NESTED)

Notice that the definition given for ENCLOSE fails to capture the differences in definition between the Sharp APL and the APL2 implementations.

4. Enclose, Disclose, etc.¶

4.1 Recall that, for a domain ℝ*J*K, K defines the rank of the array, and J*K defines the shape, thus when K=0, and J*K is empty, it is intuitively obvious (that is, after sufficiently long exposure to APL conventions, it becomes intuitively obvious) that the domain consists of the scalar reals. Similarly, for any other domain, A, when K=0, the domain A*J*K is identically equal to A.

To put it another way, if a non-empty array X is built from elements of the domain A, then the result of (⍳0)⍴X must necessarily be an element of A. Likewise, the result of LIST[I] for integer I. There is no need for a separate disclose function.

4.2 Going the other way is more tricky, however. The only time an automatic enclose is triggered is when a semicolon is encountered in the code. A corollary of this is that the list thus in progress of definition has a minimum of two elements. Single-element lists and zero-element lists are permitted, it is just that there is no immediate way of defining them — they must be derived.

A separate enclose would be an convenience. The precise syntax is not important as this stage, but one promising candidate is a $ function, monadic and dyadic, which applies to depth of nesting in a manner analogous to the ⍴ function. Something like 1$SIMPLE to construct a single-element vector, perhaps.

4.3 Monadic ⍴ would (continue to) give the shape of the array at the top level of nesting. Analogous to the monadic ⍴ , monadic $ could be used to give the depth of the deepest object. (Such a definition has the nice feature that both monadic functions are interrogative in mood, while the dyadic definitions are imperative in mood.)

K provides a # function which gives the length of the topmost list, followed recursively by the length of the lists at the next level - provided they are all of the same length. It therefore functions as an indicator of rectangularity, providing useful information which is not otherwise easily obtainable.

4.4 Other members of the group of "convenient but not indispensable" functions, monadic head and tail functions could also be defined (co-incidentally, bringing APL a little closer to Lisp).

For a vector drawn from domain D, the domain of head would be D↤(D*ℕ), and its definition would be

↑V   ↔   (⍳0)⍴V

while the domain of tail would be (D*ℕ)↤(D*ℕ), with definition

↓V   ↔   1↓V .

Note that head will fail if V is empty, and that if V is a vector of enclosed items, the scalarisation process will automatically disclose the first item, after the fashion of the first function defined in APL2 and Dyalog APL.

5. Summary¶

5.1 By consistently following the existing syntax, and consistently applying our semantic rules, we have seen how nested arrays can be deemed to be a part of the language, with the minimum impact on the syntax and semantics of 1^st-generation APL.

That this gives us a neat and concise definition of a large and useful domain is due to in part to the power and elegance of the syntax for domain definition, and in part to the regularity and consistency of APL data structures.

5.2 We have only considered the transient data space so far: the persistent data space is a little different. This needs to be explored briefly, before we proceed with the study of how nested arrays can be included within the domain of existing primitives.

6. References¶

6.1 R D Tennent (1981), Principles of Programming Languages, Prentice Hall.

Once again, the idea presented above is a very close copy of Tennent’s Chapter 3, except that here it has been applied to APL rather than Lisp, and uses (a slight extension of) the notation introduced for simple data domains.

6.2 David Gries (1971), Compiler Construction for Digital Computers, Wiley.

The particular problem of direct left recursion in regular grammars is covered in pp 93-94, and almost all other books on compiler writing, as well. Indirect left recursion is more difficult.

6.3 Manfred von Thun
http://www.latrobe.edu.au/www/philosophy/phimvt/j00syn.html

References on most other languages are easily available, and in any case, are not essential for an understanding of APL domains, but Joy may be less well-known than most, so the above reference is given for those open-minded persons who like to take a different world view occasionally.