Some Exercises in APL Language Design

Roger K.W. Hui
 

Introduction

0-origin throughout.

Some of the ideas can not be implemented in a given APL because they are not backward compatible. In such cases treat them as thought experiments. There are often no right or wrong answers, or there is more than one right answer. Some of the questions were considered and decisions made years ago, but the original discussions were not recorded anywhere and I was not privy to them.

Some sections do not have an explicitly stated exercise. Treat them as ideas for meditation. Make up your own exercises.
 

0. Function Syntax

In APL, a monadic function has the function symbol or name preceding its argument and a dyadic function has it between its arguments. Write each APL primitive scalar function in conventional mathematical notation. For example, n!m in conventional mathematical notation is  .
 

1. Elision of Times Sign

In conventional mathematical notation, the function symbol for multiplication is often elided: xy means x times y. APL eliminates this elision and thereby makes possible the use of multi-character names — qty×price . What is another beneficial effect of this rule? Compare your answer to that given here (§4).
 

2. Order of Evaluation

Why doesn’t APL have an order of evaluation (operator precedence), for example × and ÷ before + and - ? Why is it “right to left”? Compare your answer to that given here.
 

3. Polynomials

In conventional mathematical notation multiplication is done before addition and power is done before multiplication. Falkoff and Iverson speculated in The Design of APL 1973 that the rules are to obviate the use of parentheses in writing a polynomial.

If vectors c and e are the coefficients and corresponding exponents of a polynomial, write a parenthesis-free APL expression for evaluating the polynomial at x .
 

4. Nouns, Verbs, Adverbs

J uses terms from natural languages instead of from mathematics or computer science (the practice started with A Dictionary of APL):

The natural language terms are an extended and useful metaphor. They are more approachable for a wider audience and more suggestive. For example, there is usually a hiccup when explaining operator to a non-APL programmer or mathematician (in APL, an operator is different from a function; it’s an operator in the sense of Heaviside; it’s a higher-order function; etc.) An adverb, however, can be be more readily grokked: think quickly, run quickly, eat quickly; think quickly, think slowly, think sensibly, think originally. See the Reflexive section below for another example.
 

5. Valence

The APL\360 development group had a deep and abiding interest in words, in their correct use and in their etymology. For example:

The number of arguments that a function takes is its valence. The use of “adicity” or “arity” to denote the same should be avoided because those words, like supercalifragilisticexpialidocious, are all affixes and rootless.

An ambivalent function is one which can take one or two arguments.
 

6. Order of Arguments

The order of the arguments in many primitive dyadic functions, when not constrained by firmly-established custom, is such that ⍺∘f is a sensible monadic function. List the functions which follow this principle.
 

7. Negate/Minus

Why should - be a primitive when it can be defined succinctly as {⍺←0 ⋄ ⍺+¯1×⍵} (or, at worst, {⍺←0 ⋄ ⍺+¯1×⍵}¨) ?
 

8. Imaginary/Complex

J has the scalar function j. defined by {⍺←0 ⋄ ⍺+0j1×⍵} . If complex numbers are in the language and symbol proliferation is not a problem, would you specify j. as a primitive?

Compare your answer to the one given below.
 

9. Floor and Ceiling

⌈x , the ceiling of x , can be readily defined in terms of the floor of x : ⌈x ←→ -⌊-x . (Moreover, x⌈y ←→ -(-x)⌊(-y) ; with the under operator, ⌈ ←→ ⌊⍢- for both the monadic and the dyadic cases.) So why are both included as primitives?

Compare your answer to the one given here (§4).

Floor and ceiling figure in two anecdotes from the early days of APL:

Brooker: It is not obvious to me that these two symbols for FLOOR and CEILING have a great deal of mnemonic value.

Iverson: Yes, but once you have read it, you can remember it.

Iverson, Formalism in Programming Languages, 1964

Another notational step that was taken at that time, and this has to do with cleaning up the syntax, was the dropping of the closing symbol for absolute value, floor, and ceiling. I have observed that in certain ivory towers of pure mathematics they have adopted the floor and ceiling symbols still with the pair about them, and I estimate that in roughly another decade they will get around to dropping the second.

Falkoff, APL\360 History, 1969

10. What is an Array?

What is an array? Compare your answer to the one given here.
 

11. Is a Scalar an Array?

Is a scalar an array? Compare your answer to the one given here.
 

12. Infinite Arrays

McDonnell and Shallit 1981 proposed to add to APL ∞ and infinite arrays, arrays having ∞ as the length of a dimension.

How can you have an infinite array in a finite computer? One way is to consider an array as a function on the natural numbers such that (for example) v←⍳∞ has an associated function vf such that v[i] is vf i . (vf is the identity function ⊢ in this case.) If u and v are infinite vectors, g1 a scalar monadic function, and g2 a scalar dyadic function, then g1 v is also an infinite vector and its associated function is the composition g1∘vf ; and u g2 v is an infinite vector and its associated function is the fork (uf g2 vf) . Moreover, 1.5 = +/3*-⍳∞ and (*⍵) = (⍵*⍳∞)+.÷!⍳∞ .

J has a few infinite arrays in disguise: p: i is the i-th prime and f t. i is the i-th coefficient in the Taylor series expansion of f .

Infinite vectors can be used to prove Euler’s Identity.
 

13. Scalar Encoding

In the fuss and fury of floating vs. grounded arrays it is easy to forget that the enclose of an array is just a scalar encoding (AKA scalar representation) of it. For some purposes there are much more efficient scalar encodings than enclose, such as x⍳x instead of ↓x or (⊂⍤¯1)x .

Devise an invertible encoding for a vector of integers as a single integer. Such an encoding is used in the proof of Gödel’s incompleteness theorems.
 

14. Is 1 a Prime?

A prime number is sometimes defined as a number divisible only by 1 and itself. With this definition 1 qualifies as a prime. What are the disadvantages if 1 is a prime? (Some older math texts did consider 1 to be a prime.) Compare your answer to the one given here.

I have an argument supporting ⎕io←0 based on this.
 

15. 0÷0

In APL\360 0÷0 is 1 , justified as being the limit of x÷x when x approaches 0 . Some have argued that it should be 0 . Should 0÷0 be 0 , 1 , or an error? Compare your answer to the one given here.
 

16. 0*0

Why is 0*0 equal to 1 ? Some mathematicians consider 0*0 to be indeterminate.

Compare your answer to Knuth 1992, page 6.
 

17. Scalar and Single Extension

Let f be a scalar dyadic function. In scalar extension, the conformability rules are (⍴⍺)≡⍴⍵ or 0=⍴⍴⍺ or 0=⍴⍴⍵ ; in single extension, the conformability rules are (⍴⍺)≡⍴⍵ or 1=×/⍴⍺ or 1=×/⍴⍵ .

18. Agreement

Scalar extension can be extended in at least two different ways:

In suffix agreement, the conformability rules are (⍴⍺)≡(⍴⍵) or one is a suffix of the other. In prefix agreement, the conformability rules are (⍴⍺)≡(⍴⍵) or one is a prefix of the other. By back formation, scalar extension can also be called scalar agreement, where (⍴⍺)≡(⍴⍵) or one is the empty vector.

⍝ suffix agreement

   x          y             x + y
1  2  4     0  1  2       1  3  6
8 16 32     3  4  5      11 20 37

            6  7  8       7  9 12
            9 10 11      17 26 43
 
           12 13 14      13 15 18
           15 16 17      23 32 49

           18 19 20      19 21 24
           21 22 23      29 38 55

⍝ prefix agreement

   x                   y            x × y
 0  1  2  3  4      1 2 4 8        0   1   2   3   4
 5  6  7  8  9                    10  12  14  16  18
10 11 12 13 14                    40  44  48  52  56
15 16 17 18 19                   120 128 136 144 152

In its early days J had suffix agreement, but in 1992 changed to prefix agreement and has prefix agreement to this day. The rank operator in Dyalog APL uses scalar agreement. The possibility remains to extend it to use suffix or prefix agreement.
 

19. Not Found

The answer for ⍺⍳⍵ is ⎕io+≢⍺ if ⍵ is not found in ⍺ . What are some other plausible choices? Why is the current choice advantageous?
 

20. Major Cell

A major cell of an array ⍵ is a subarray of rank ¯1+⍴⍴⍵ on the leading dimension of ⍵ . What primitives in Dyalog APL were defined in terms of major cells before the introduction of ⍤ and ⌸ and the extension to ⍳ ?
 

21. Dyadic Grade

When dyadic ⍋ was introduced in the late 1970s the left argument specified a collating sequence for the grade. Dyalog APL follows this definition. In J, dyadic ⍋ is defined instead as the equivalent of (⊂⍋⍵)⌷⍺ . What is the major advantage of the J definition?
 

22. Sorting Complex Numbers

In college calculus and analysis classes we are taught that the complex numbers can not be ordered. (The proof hinges on that 0j1 can neither be positive nor negative, but is not 0 .) So does that rule out complex numbers being in the domain of ⍋ ?
 

23. Total Array Ordering

Define an ordering on arrays, denoted here by ≼, such that for arrays x , y , and z ,

Compare your answer to those given here and here. Can the existing function ≤ , suitably extended, play the role of ≼?

Dyalog APL can not really have a total array ordering because it permits arrays of namespaces, which can have circular references.
 

24. A Design Mistake?

Rationalized APL 1983 and A Dictionary of APL 1987 defined the from ({) primitive which is roughly (⊂⍵)⌷⍺ and is implemented in J. From has a serious design mistake, or at least missed a golden opportunity.

From has as a main design goal of completely replacing bracket indexing, a[i₀;i₁;…;i_n], and in such attempt used “triple enclosure” to indicate “complementary indexing”. From J:

   A
abcde
fghij
klmno
pqrst
   $ A
4 5

   (<1;4 3){A
ji
   (<(<1);4 3){A
ed
on
ts

The first example is equivalent to A[1;4 3] and the second to A[(⍳4)~1;4 3] . The (⍳4)~1 is complementary indexing: the indices you specify indicate the positions that you don’t want. The crucial point of complementary indexing is this:

   (<(<'');4 3){A
ed
ji
on
ts
   (<a:;4 3){A
ed
ji
on
ts
   a:
┌┐
││
└┘

In bracket indexing, you can elide the index for a dimension and it would select every position in that dimension. So the above examples are equivalent to A[;4 3] . It is not apparent in the J examples, but in the APL dictionary ∘ is defined to be the enclose of ⍳0 (spelled a: in J), so that the above examples would read, if you had the APL Dictionary and the APL character set and you have ; as the link primitive (; is in J but is spelled ⊃ in Dictionary APL), you’d have A[;4 3] ←→ (<∘;4 3){A , and more generally A[;i;;j;;k] ←→ (<∘;i;∘;∘;j;∘;k){A .

What is the design mistake AKA missed golden opportunity? From could have, should have, used enclosure to indicate reach indexing (and abandon elided indices or at least do something else to get it). APL2 people would probably phrase it (“used enclosure”) differently, but I think you get the point about reach indexing.
 

25. Squad Indexing

As indicated in the previous section, from is roughly (⊂⍵)⌷⍺ . Why wasn’t it defined as ⍵⌷⍺ ? There was a debate about this in 1986/1987 within IPSA.
 

26. Array Indices

In x[y] the indices y can be an entire array. Of course. I remember that this was a revelation to me when I was learning APL.

It is instructive to read in APL\360 History about the evolution of the notation for indexing from subscripts and superscripts to the A[i;j;k;l] notation.
 

27. Array Index Bounds

Early editions of A Dictionary of APL extended the domain of permissible array indices by using n|i as the actual indices, where n is the length of the axis. The final edition restricted the indices from -n to n-1 . Is the final restriction a good idea?
 

28. Array Logic

   x← 5 ¯2.7 0 6

   (x>0)-(x<0)
1 ¯1 0 1

   x × (x>0)-(x<0)
5 2.7 0 6

The expression (x>0)-(x<0) is probably the first APL one-liner ever written (A Programming Language, 1962, §1.4). What make it work are that propositions have result 0 or 1 rather than true or false and that functions work on entire arrays rather than just on scalars.

Falkoff and Iverson explained the 0-1 definition in The Design of APL in characteristically plain but telling language:

A very general and useful set of functions was introduced by adopting the relation symbols < ≤ = ≥ > ≠ to represent functions (i.e., propositions) rather than assertions. The result of any proposition was defined to be 0 or 1 (rather than, say, true or false) so that it would lie in the domain of other arithmetic functions. …

The adoption of the relation symbols as functions does not preclude their use as assertions in informal sentences. For example, although one might feel compelled to substitute “x≤y is true” for “x≤y” in the sentence “If x≤y then (x<y)∨(x=y)”, there is no more reason to do so than to substitute “Bob is there is true” for “Bob is there” in the sentence which begins “If Bob is there then …”.

Knuth wrote enthusiastically about this (the 0-1 thing, not the array thing) in TNN 1992, calling it Iverson’s convention or Iverson brackets and saying that it led to “substantial improvements in exposition and technique”. If the worked examples in TNN look familiar it’s because the simplification steps resemble APL golfing.
 

29. Design Mistake II

In APL\360 ⍺∊⍵ is equivalent to ⍺∊,⍵ . Why is this a mistake?
 

30. Forks

J defines fork, (f g h) , a train of 3 functions in isolation, as follows:

     g          g
    / \        / \ 
   f   h      f   h
   |   |     / \ / \
   y   y     x y x y 

Why is this not equivalent to the following?

     (f g h) y  ←→  (f y) g (h y) 
   x (f g h) y  ←→  (x f y) g (x h y)

31. Scalar Operators

In Operators and Functions 1978 Iverson proposed, for each primitive scalar dyadic function (such as +), a scalar operator whose symbol is formed by “overstriking” the function symbol with an overbar (∓) . The definition is illustrated by that for ∓ :

Discuss the pros and cons of scalar operators vs. forks.
 

32. Strand Notation

Do you still have APL2 (APL2, Dyalog APL, NARS2000, …) if you take away strand notation?

“Have APL2” in the sense of, you still have APL2 if you added dfns to it. (Or do you?)
 

33. Dfns and Explicit Definition

Compare dfns (Dyalog APL) and explicit definition (J), two ways of defining functions and operators.
 

34. Sigma, Pi, etc.

Suppose symbol proliferation is not an issue. What are the pros and cons of defining Σ ←→ +⌿ , Π ←→ ×⌿ , etc.?
 

35. Operators in APL in 1978

In his 1978 Turing lecture (§8) Backus wrote “APL has exactly three functional forms, called inner product, outer product, and reduction.” At the time APL had two other functional forms AKA operators. What were they?
 

36. Operators in J

J has 11 monadic and 27 dyadic operators. Which of them would you include in your APL?
 

37. Operator Encoding Efficiency

Among other things, operators economize on the number of symbols needed to encode functionality. Suppose you have 10 symbols.

If you use all of them to denote functions, then you have 10 functions.

If you use 5 of them to denote functions and 5 to denote monadic operators, then you have 5 primitive functions and 25 derived functions.

If you use 5 of them to denote functions and 5 to denote dyadic operators, then you have 5 primitive functions and 125 derived functions.

These are in addition to the possibilities afforded by array operands.
 

38. Key

The key operator was introduced in J no later than November 1991; it was introduced in Dyalog APL in 2013 (version 14.0).

In J, the key operator x u/. y is defined as: items of x specify keys for corresponding items of y and u is applied to each collection of y having identical keys. (In J, item means major cell.)

In Dyalog APL, the key operator x u⌸ y is defined as: major cells of x specify keys for corresponding major cells of y and u is applied to each unique key and each collection of y having that key.

Discuss the pros and cons of each definition.
 

39. Under

Under is a dyadic operator ⍢ defined as follows:

   f⍢g x   ←→ g⍣¯1 f g x
   x f⍢g y ←→ g⍣¯1 (g x) f (g y)

(g⍣¯1 is the inverse of g .) For examples, x×y ←→ x+⍢⍟y . Find other examples of using under. Compare your answers to the ones given here.
 

40. Reflexive

The monadic case of the function f⍨ x derived from the commute operator is defined as x f x . Find examples of useful functions that can be defined as f⍨  (for example double is +⍨). Compare your answers to the ones given here.

The commute operator is called reflexive/passive in J, underscoring the correspondence to the reflexive and passive cases in natural languages and its usefulness for deft expression in contexts wider than programming and mathematics.
 

41. Scan

Scan in APL has reduction built in; the use of reduction ensures that computations such as partial sums can be effected by primitive function arguments to the operator, and that the overall result can be properly assembled in APL\360. Once this is realized, the alternative prefix and suffix operators suggest themselves. These apply the monadic case of the operand to the arguments. In J:

   <\  3 1 4 1 5 9 26     NB. enclose prefixes
┌─┬───┬─────┬───────┬─────────┬───────────┬──────────────┐
│3│3 1│3 1 4│3 1 4 1│3 1 4 1 5│3 1 4 1 5 9│3 1 4 1 5 9 26│
└─┴───┴─────┴───────┴─────────┴───────────┴──────────────┘
   <\. 3 1 4 1 5 9 26     NB. enclose suffixes
┌──────────────┬────────────┬──────────┬────────┬──────┬────┬──┐
│3 1 4 1 5 9 26│1 4 1 5 9 26│4 1 5 9 26│1 5 9 26│5 9 26│9 26│26│
└──────────────┴────────────┴──────────┴────────┴──────┴────┴──┘

   +/\  3 1 4 1 5 9 26    NB. sum prefix
3 4 8 9 14 23 49
   +/\. 3 1 4 1 5 9 26    NB. sum suffix
49 46 45 41 40 35 26

42. Reduction Style

ISO/IEC 13751:2001(E) speaks of two “reduction styles”: enclose reduction style (Dyalog APL, APL2, etc.) and insert reduction style (SHARP APL, J, etc.) Discuss the pros and cons of the two reduction styles.
 

43. A Combinatorial Operator

Bob Smith proposed in 2016 a combinatorial operator for computations on combinations, permutations, partitions, etc. Would you include it as a primitive operator in your APL?
 

44. Cut, Tessellate, Tile, Stencil

A monadic operator is proposed for Dyalog APL in 2016, in which a rectangular window is moved over the data and the operand is applied to the data so framed. The window size and the movement are independent in each dimension. One of the things to be decided is a name for the operator.

Another question to be settled is a symbol for the operator. The current proposal is ⌺ , quad diamond, Unicode U233A.
 

45. Small-Range, 1-, and 2-Byte Integers

An integer array x is small-range if its range, r←(⌈/,x)-(⌊/,x) , is small. How small is “small”? It depends on the particular primitive, but usually r<2×≢,x and sometimes even r<4×≢,x would be small-range. Having special code for small-range data makes a significant difference in efficiency. Define:

x1←2e9+?1e6⍴120
x2←2e9+?1e6⍴2e4
x4←    ?1e6⍴2e9

and compare the times in takes to do ⍋ , {⍵[⍋⍵]} , and ⍳⍨ on each of the three vectors.

Dyalog APL has 1- and 2-byte integers with automatic promotion and demotion between them and other numeric datatypes and, of course, it is immediate whether they are small-range. Having these datatypes makes a significant difference in efficiency. Define:

x1←?1e6⍴120
x2←?1e6⍴2e4
x4←?1e6⍴2e9

and compare the times in takes to do ⍋ , {⍵[⍋⍵]} , and ⍳⍨ on each of the three vectors.

The functions ⍋ , {⍵[⍋⍵]} , and ⍳⍨ are implemented to best of current knowledge for small-range, 1-, and 2-byte integers. Each of them should be faster on such arguments; if not, a possible speed-up has been left on the table.
 

46. Tolerant Comparison

Tolerant comparison ameliorates the ugly realities of finite-precision representation and arithmetic. For example, 7 is not exactly equal to 100×0.07 nor to the square of the square root of 7 :

   7 - 100 × 0.07
¯8.88178E¯16
   7 - (7*0.5)*2
¯8.88178E¯16

Equality with a tolerance t is defined as follows: for finite x and y , x=y is 1 if the magnitude of x-y does not exceed t times the larger of the magnitudes of x and y . In Dyalog APL, the tolerance is specified in ⎕ct whose value in a clear workspace is 1e¯14 . An upper bound is imposed on acceptable values of the tolerance; historically, the upper bound was chosen to be small enough that tolerance has no effect on comparisons involving 32-bit integers.

Compare your answers to those given here and here.
 

47. assert

assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}

assert is an APL utility function I use extensively in the Dyalog APL QA suite. The definition is subtle and chock-full of technical arcana; the main thing is that propositions to be evaluated are stated in the positive sense: assert 0=1+*○0j1 .

The utility has counterparts in APL interpreters where it is defined as a C macro and used 700 times in Dyalog APL and 1000 times in J. Again, the main thing is that the required condition is stated in the positive sense:

  #define ASSERT(p,stmt)  {if(!(p)){stmt;}}

  ASSERT(2>=r, EVRANK);
  ASSERT(xn==yn, EVLENGTH);
  ASSERT(t==APLSINT||t==APLINTG||t==APLLONG, EVDOMAIN);

Absent ASSERT , the above C code would be coded in variations of the following, repeated hundreds of times:

  if(!(2>=r))EVRANK;
  if(xn!=yn)EVLENGTH;
  if(!(t==APLSINT||t==APLINTG||t==APLLONG))EVDOMAIN;

  if(2<r)EVRANK;
  if(!(xn==yn))EVLENGTH;
  if(t!=APLSINT&&t!=APLINTG&&t!=APLLONG)EVDOMAIN;

48. Why Functional Programming Matters

In Why Functional Programming Matters John Hughes and Mary Sheeran list four salient characteristics of functional programming.

49. Notation as a Tool of Thought

In Notation as a Tool of Thought Iverson listed five important characteristics of notation.

Sample Answer

The Imaginary/Complex section above says:

J has the scalar function j. defined by {⍺←0 ⋄ ⍺+0j1×⍵} . If complex numbers are in the language and symbol proliferation is not a problem, would you specify j. as a primitive?

My answer:

Complex numbers can be constructed as ordered pairs of real numbers, similar to how integers can be constructed as ordered pairs of natural numbers and rational numbers as ordered pairs of integers. For complex numbers, j. plays the same role as - for integers and ÷ for rational numbers.
 

Further Reading