In Praise of Magic Functions: Part II

Part I of this post was concerned with the development speed and execution speed of magic functions and should be read before this post.

Benefitting from Future and Past Improvements

Looking at the magic function for key in Part I, we see that its performance depends on the following APL primitives, listed with information on when they were last improved (or when they will be improved):

expression factor version
⍋i 2-18 12.1
⎕DR 1-3.8 14.1
⍳⍨x 2-4 14.1
⍳⍨i 3-6 14.1
↑x 5-12 15.0
⊂[a]x 1-1.75 15.0
b⊂[⎕IO]x 1.3-42 14.1

Key was introduced in version 14.0 and x{⍺,f⌿⍵}⌸y is currently computed by the general case. Comparing the speed in version 14.0 to 15.0 as of June 2015:

   x←?1e6⍴5e4
   y←?1e6⍴0

   1 1 cmpx 'x{⍺,+/⍵}⌸y'    ⍝ 14.0
0.1735

   1 1 cmpx 'x{⍺,+/⍵}⌸y'    ⍝ 15.0
0.12855

   0.1735 ÷ 0.12855
1.34967

a factor of 1.3 improvement without touching the key code. Special code had been planned for {⍺,f/⍵}⌸, and we can get an idea of the amount of speed up:

   cmpx 'x{⍺,+/⍵}⌸y' '(∪x),⍤0⊢x{+/⍵}⌸y'    ⍝ 15.0
 x{⍺,+/⍵}⌸y       → 1.25E¯1 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
 (∪x),⍤0⊢x{+/⍵}⌸y → 1.16E¯2 | -91% ⎕⎕⎕

Perhaps the special code for {⍺,f/⍵}⌸ can be a magic function?

Magic functions also benefit from past improvements. The primitive ⍕b (in the Suggestivity subsection below) has a magic function implementation: MAGIC("(¯1+2×≢⍵)⍴(2 2⍴'0 1 ')[⍵;]⊣⎕io←0"). Then I thought, why not get an extra level of performance by doing it in native C? Benchmarks done after that work showed that the native C implementation was faster by a factor of 25 but the magic function was faster by a factor of 40. What happened? On reflection, the speed of the code depends crucially on the speed of x[b;…;] and it turned out that x[b;…;] was previously sped up (version 13.2). Apparently the x[b;…;] code is faster than a casually-written C program.

Finally, I expect magic functions are prime candidates for being fed to the APL compiler when it becomes possible to do so.

APL as a Tool of Implementation

Being APL code, magic functions have the characteristic terseness of APL and all that that entails. K.E. Iverson’s 1979 Turing Lecture Notation as a Tool of Thought lists five important characteristics of notation. We examine how they play out in this context.

Ease of Expression
Notation as a Tool of Thought entitles this characteristic as “ease of expressing constructs arising in problems”, explicated as follows (§1.1):

If it is to be effective as a tool of thought, a notation must allow convenient expression not only of notions arising directly from a problem, but also of those arising in subsequent analysis, generalization, and specialization.

For magic functions, the analogous concept would be facility in program development, debugging, tracing, profiling, benchmarking, and other activities required in implementation. Dyalog APL has these in spades.

Suggestivity
It was first identified that ⍕b can be sped up by doing (¯1+2×≢⍵)⍴(2 2⍴'0 1 ')[⍵;]⊣⎕io←0, the idea being that if f is an expensive function and x is from a small domain D, then f x can be computed by (f D)[⍵;]. (A similar idea is described in §4.3 of Notation as a Tool of Thought.) For the idea to be effective, f does not have to be very expensive, just more expensive than indexing, and x is sufficiently large. A few speed-ups in the pattern have been identified:

⍕b
x⍕b
float ⍳ b
float ⍳ int8
scalar×b and b×scalar
scalar*b

All of these can be implemented by magic functions. As well, the utility of the pattern (f D)[i;] motivates extra attention on x[i;…;]. Fortuitously, x[b;…;] has previously been made fast.

Subordination of Detail
Writing in APL means not having to deal with many details involved in writing in C in the interpreter, including:

  • workspace compaction
  • arrays changing their internal datatype
  • call by name
  • allocating and releasing memory
  • index errors AKA memory read and write exceptions
  • different numeric types
  • different character types
  • loops and nested loops
  • declarations
  • etc.

Economy
Economy refers to the size of the vocabulary and the complexity of the grammar. Here, the comparison is not just between APL and C (in which comparison APL wins), but between APL and the collection of programs, utilities, macros, data structures, typedefs, calling conventions, …, accumulated by the C source code over the years. These have not been as rigorously defined and executed as APL.

Amenability to Formal Manipulation
The opening paragraph of the present text had a different magic function for ∧.= in a previous version. In repeated readings of the MSS and in meditation on the ideas I realized that the line of code can be made simpler:

MAGIC("((≢⍺)↑i)∘.=(≢⍺)↓i←⍺⍳⍺⍪⍉⍵");    ⍝ old version
MAGIC("(≢⍺)(↑∘.=↓)⍺⍳⍺⍪⍉⍵");           ⍝ current version

I daresay that such simplification would be harder to conceive with a more verbose statement of the algorithm.

In Praise of Magic Functions: Part I

A magic function is an APL-coded (dfn) computation in the C source of the interpreter. For example, some cases of ∧.= are coded as MAGIC("(≢⍺)(↑∘.=↓)⍺⍳⍺⍪⍉⍵"). The rubric “magic function” includes magic functions and magic operators.

Acknowledgments. Magic functions in Dyalog are made possible due to work done by John Scholes and Richard Smith.

Development Speed

A magic function implementation takes an order of magnitude less time to write than a C-coded implementation. A case in point is ∘.≡ (and ∘.≢) on enclosed character vectors, as recounted in the blog post A Speed-Up Story. The chronology is recovered from the G-mail, Mantis and SVN systems.

2014-10-27 04:24 Nicolas initial e-mail describing the problem
2014-10-27 07:33 Roger proposes i∘.=i←a⍳a as a solution
2014-10-27 07:36 Jay objects that solution should check ⎕CT
2014-10-27 07:40 Roger responds to objection
2014-10-27 10:29 Roger creates Mantis issue
2014-10-27 13:57 Roger SVN commit
2014-10-27 18:12 Roger reports factor 6-64 speed-up and submits blog post
2014-10-28 16:33 Roger SVN commit to fix a bug

After checking that ⎕CT is not required, the main processing in the C source is as follows:

  • 1 iff a “selfie”, i.e. the left and right arguments are equal as C pointers
  • eq 1 if ∘.≡ ; 0 if ∘.≢
  • 1 iff the right argument has rank 1
#define CASE(x,y,z)  ((x<<2)+(y<<1)+(z))

switch(CASE(c,eq,r))
{
  case CASE(0,0,0): MAGIC("((,⍺)⍳⍺)∘.≠((,⍺)⍳⍵)"); break;
  case CASE(0,0,1): MAGIC("(  ⍺ ⍳⍺)∘.≠(  ⍺ ⍳⍵)"); break;
  case CASE(0,1,0): MAGIC("((,⍺)⍳⍺)∘.=((,⍺)⍳⍵)"); break;
  case CASE(0,1,1): MAGIC("(  ⍺ ⍳⍺)∘.=(  ⍺ ⍳⍵)"); break;
  case CASE(1,0,0): MAGIC("∘.≠⍨(,⍵)⍳⍵");          break;
  case CASE(1,0,1): MAGIC("∘.≠⍨  ⍵ ⍳⍵");          break;
  case CASE(1,1,0): MAGIC("∘.=⍨(,⍵)⍳⍵");          break;
  case CASE(1,1,1): MAGIC("∘.=⍨  ⍵ ⍳⍵");          break;
}

Execution Speed

Development speed for a magic function need not be at the expense of execution speed. As indicated above, ∘.≡ is 6 to 64 times faster than the previous (C coded) implementation. Factors for a few other magic function implementations:

expression factor version
x∘.≡y and x∘.≢y 6-64 14.1
x∧.=y and x∨.≠y 1.5-4 14.1
,/y 1-∞ 15.0
x⊥y 1-26 15.0
x⊤y 1-3.3 15.0

One can always make a magic function faster by hand-translating it from APL into C, and in so doing save on the tokenizing (scanning) and parsing costs. However, the effort increases the development time and the code size for (I argue) not much reduction in execution time. I also expect that such translation can be done automatically by the APL compiler in the future.

Accurate estimates for the amount of speed up obtain readily from APL benchmarks. For example, x⍕b where x is a scalar or 2-element vector and b is a Boolean array, is a candidate for a magic function implementation, and:

   f←{((¯1↓s),(⊃⌽⍴t)×⊃⌽s←⍴⍵)⍴(t←⍺⍕⍪0 1)[⍵;]}

   b←1=?10⍴2     ⍝ small argument
   cmpx '2 f b' '2⍕b'
 2 f b → 5.83E¯6 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
 2⍕b   → 1.23E¯5 | +110% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   b←1=?1e6⍴2    ⍝ large argument
   cmpx '8 2 f b' '8 2⍕b'
 8 2 f b → 9.75E¯3 |     0% ⎕
 8 2⍕b   → 3.35E¯1 | +3339% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

We can say with confidence that x⍕b can be made 2 to 34 times faster before actually proceeding with the implementation.

Magic functions can be used when execution speed is not paramount. For example a problem was reported with !∘y⍣¯1:

   !∘25⍣¯1 ⊢ 1e4
DOMAIN ERROR
   !∘25⍣¯1⊢10000
  ∧

The problem can be solved readily with an APL function using Newton iteration, with a relatively complicated computation for the initial estimate:

   f←{-∘⍵∘⍺⍺{⍵-(⊃t)ׯ0.01÷-/t←⍺⍺ ⍵×1 1.01}⍣≡⊃⍋|⍵-(⍳!⊢)⌊0.5+⍺⍺ 1}
   ⎕←x←!∘25 f 1e4
3.85142
   x!25
10000

General Case vs. Special Cases

Magic functions are well-suited for implementing operators. An operator has potentially tens or hundreds of cases, and it would be onerous, not cost-effective and unnecessary to write code for each case. Instead, the general case can be implemented quickly and succinctly by a magic function, and the saved effort can be devoted to cases deemed worthy of attention. The rank and key operators are done this way. The magic function for the general case of key:

MAGIC(
  "0=⎕nc'⍺':⍵ ∇ ⍳≢⍵    ⋄"  // monadic case: f⌸ x ←→ x f⌸ ⍳≢x
  "⍺ ⍺⍺{⍺ ⍺⍺ ⍵}{        "
  "  ⎕ml←1             ⋄"  // needed by ↑⍵ and ⍺⊂⍵ 
  "  j←⍋i⊣⎕dr i←⍳⍨⍺    ⋄"
  "  ↑ (⊂[1↓⍳⍴⍴⍺]((⍳≢i)=⍳⍨i)⌿⍺) ⍺⍺¨ (2≠/¯1,i[j])⊂[⎕io]⍵⌷⍨⊂j"
  "}⍵                   "
);

Before execution reaches the general case, special cases are detected and are implemented by special code, usually in C. These special cases are:

operand version comment
{f⌿⍵} and ⊢∘(f⌿) 14.0 for f one of + ⌈ ⌊ or (for Boolean right arguments) one of ∧ ∨ = ≠; also / instead of for vector right arguments
{⍺(f⌿⍵)} 15.0 for f as above
{⍺,f⌿⍵} 15.0 for f as above and numeric left arguments
{≢⍵} and ⊢∘≢ 14.0
{⍺(≢⍵)} 14.1
{⍺,≢⍵} 14.1 for numeric left arguments
{≢∪⍵} 14.1
{⍺(≢∪⍵)} 14.1
{⍺,≢∪⍵} 14.1 for numeric left arguments
{⊂⍵} and ⊢∘⊂ 14.0
{⍺⍵} 14.1
{⍺} and 14.1 ⊣⌸x ←→ ∪x if were extended like

Additional special cases can be implemented as required.

Special Cases

Since magic functions are so terse, sometimes it is worthwhile to make special cases which would not be made special cases if the implementation were more verbose and/or require more effort. The implementation of ∘.≡ (in the Development Speed section above) illustrates the point. In general, x∘.≡y ←→ ((,⍺)⍳⍺)∘.=((,⍺)⍳⍵). However, if x is a vector, the two ravels can be elided; moreover, if x and y are equal as C pointers, the two uses of can be reduced to one use (not only that, but to a “selfie” ⍵⍳⍵ if a vector). So instead of the one case:

MAGIC("((,⍺)⍳⍺)∘.=((,⍺)⍳⍵)");

we have

switch(CASE(c,eq,r))
{
    …
  case CASE(0,1,0): MAGIC("((,⍺)⍳⍺)∘.=((,⍺)⍳⍵)"); break;
  case CASE(0,1,1): MAGIC("(  ⍺ ⍳⍺)∘.=(  ⍺ ⍳⍵)"); break;
    …
  case CASE(1,1,0): MAGIC("∘.=⍨(,⍵)⍳⍵");          break;
  case CASE(1,1,1): MAGIC("∘.=⍨  ⍵ ⍳⍵");          break;
}

The extra cases are not too burdensome, and their detection is done in scalar code at which C is better than APL. The following benchmarks illustrate the difference that the special cases make:

   t ←' zero one two three four five six seven eight nine'
   t,←' zéro un deux trois quatre cinq six sept huit neuf'
   t,←' zero eins zwei drei vier fünf sechs sieben acht neun'
   u←1↓¨(' '=t)⊂t

   x←u[?300⍴≢u]    ⍝ vector selfie vs. non-selfie
   y←(⍴x)⍴x
   cmpx 'x∘.≡x' 'x∘.≡y'
 x∘.≡x → 1.48E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
 x∘.≡y → 1.93E¯4 | +30% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   x1←(1,⍴x)⍴x     ⍝ matrix selfie vs. non-selfie
   y1←(⍴x1)⍴x1
   cmpx 'x1∘.≡x1' 'x1∘.≡y1'
 x1∘.≡x1 → 1.50E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
 x1∘.≡y1 → 1.97E¯4 | +31% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

To be continued…Part II will describe the benefits from future improvements and APL as a tool of implementation.

Response to Name Colouring for Dfns

This post contains comments to John Scholes’ post on name colouring; please continue to post any further comments with the original post.

This is a very interesting topic – as the discussion has already showed, there are many different needs. It seems to me that some of the suggestions that have been made are forms of highlighting that you would want to turn on briefly in order to search for something specific or highlight structures while editing code. For example:

  • to verify the structure (highlight the matching parenthesis or bracket, or rainbow colouring of parentheses/brackets)
  • highlight all uses of a particular name or small group of names.

I don’t think I would really want any of these enabled for any length of time; some of them can probably work very well if they are turned on and off as the cursor moves through the text (when on a parenthesis, highlight the other half of the pair, when on a name, highlight all uses of that name, etc).

Making it easier to read statements through highlighting of “kinds” feels more like something that I might well want to have enabled all the time. However, I find colouring to be quite distracting – it breaks the flow for me. I would certainly want the colours to be as calm as possible for the most common kinds, getting more exciting for the “exotic ones”. So I would suggest:

 Array
 Function
 MonOp
 DyOp

For example:

   r←(foo dop 1 2 3) mat hoo mop vec

I find that syntax colouring is much more effective in a bold font:

   r←(foo dop 1 2 3) mat hoo mop vec 

But…looking at the above, I personally find the colours to be quite distracting; they make it hard for me to read the expression as a “sentence”. How about if we experiment with emphasis instead, for example we could make functions italic, monadic operators bold, and dyadic operators both.

   r←(foo dop 1 2 3) mat hoo mop vec

This is very subjective of course, but this is much more readable to me than the coloured version.

Further comments with the original post please.

Name Colouring for Dfns

APL is sometimes criticised because expressions that include names cannot, in general, be parsed without knowing whether the names represent functions or variables. For example, the name thing in the expression thing⍳3 could reference an array (in which case the is dyadic) or it could reference a function (making the monadic).

An APL expression becomes completely parsable if we distinguish each name with one of four colours, depending on the “kind” of its referent: array, function, monadic operator, dyadic operator. Now, with a bit of practice, we can at least parse thing⍳3 vs thing⍳3 without recourse to the definition of thing. Notice how kind differs slightly from APL’s name-class, which does not distinguish monadic from dyadic operators.

Names whose definitions are external to the code under consideration and so cannot be classified would be given a distinct colour, say red, which would at least draw attention to them. Colouring a number of interdependent functions at the same time should help with such issues.

Name-colouring can co-exist with the more superficial token-colouring ( green for comments and so forth) though we would probably want to configure the two schemes separately.

There’s a related argument for colouring parentheses to show the kind of value they contain: (~∘(⊂'')). This would mean that we could always determine the valency of a function call, or the kind of a hybrid token, such as /, by looking at the colour of the single token immediately to its left. Finally, we should probably kind-colour curly braces: {}, {⍺⍺ ⍵}, {⍵⍵ ⍵}.

Yeah but how?

In the following, where appropriate, “function” is a shorthand for “function or operator”.

Most generally, we want to process a number of definitions at the same time, so that inter-function references can be coloured. Such a set of functions may be considered as internal definitions in an anonymous outer function so, without loss of generality, we need consider only the case of a single multi-line nested function.

A function can be viewed as a tree, with nested subfunctions as subtrees. The definitions at each lexical level in the function comprise the information stored at each node of the tree.

The colouring process traverses the tree, accumulating a dictionary of (name kind) pairs at each level. At a particular level, definitions are processed in the same order as they would be executed, so that the (name kind) entries from earlier definitions are available to inform later expressions. Visiting each node before traversing its subtrees ensures that outer dictionary entries are available to lexically inner functions. Prefixing dictionary entries for inner functions ensures that a left-to-right search (à la dyadic iota) finds those names first, thus modelling lexical name-shadowing.

Each assignment expression adds one or more names to the dictionary. The kind of the assignment is inferred by looking at the defining expression to the right of the assignment arrow. This sounds heavy, but if we examine the expression from right-to-left then we can often stop after examining very few tokens. For example, an arbitrarily long expression ending in (… function array) must, if it is syntactically correct, reduce to an array value, while (… function function) must be a function (train). A sequence in braces {…} resolves to a function, monadic operator or dyadic operator, depending only on whether there are occurrences of ⍺⍺ or ⍵⍵ at its outermost level.

This approach, while relatively simple, is not perfect. It takes no account of the order in which names are defined relative to their being referenced. The assumption is that all definitions at an outer level are available to its inner levels. The following small function illustrates the problem:

    {
        M{A}      ⍝ this A correctly coloured function
        N{A}⍵     ⍝ this A should be coloured unclassified
        A←÷          ⍝ A defined as a function
        M N          ⍝ application of function to array
    }

It remains to be seen whether this would be a problem in practice or whether, if name-colouring proved popular, people might adjust their code to avoid such anomalies. The problem does not occur if we avoid re-using the same name for items of different kinds at the same lexical level – which IMHO is not a bad rule, anyway.

Implementation Status

I would like to experiment with name-kind colouring for the dfns code samples on the Dyalog website.

This project is under way, but has rather a low priority and so keeps stalling. In addition, I keep wavering between processing the tokens as a list with tail calling and the dictionary as an accumulating left argument, or in more classic APL style as a vector, developing parallel vectors for lexical depth and masks for assignment arrow positions and expression boundaries, etc.

In the meantime, here is an artist’s impression of what name- and bracket- coloured code might look like, with colours: array, function, dyadic-operator.

    eval{
        stk I(op ops)←⍵
        op in⊃⍺:⍺ prt stk I((dref op)cat ops)
        f(fr rr)f rstk
        c{op≡⍵~' '}
        c'dip ':⍺('*⌷'rgs{prt rr I(f cat fr ops)})
        ...

Notice how functions stand out from their arguments. For example, at the start of the third line: op in⊃⍺:, it is clear that in is a function taking ⊃⍺ (first of alpha) as right argument and op as left argument, rather than a monadic function op taking in⊃⍺ (in pick of alpha) as right argument. Other interpretations of the uncoloured expression op in⊃⍺: include:

    op in⊃⍺:    op in is a vector (array), so is pick.
    op in⊃⍺:    both op and in are monadic function calls, so is first.
    op in⊃⍺:    in is a monadic operator with array operand op.
    op in⊃⍺:    in is a dyadic operator with function operands op and .

I’m keen to hear any feedback and suggestions about name-colouring for dfns. What d’ya think?

A Dialog on APL

A discussion between Nicolas Delcros and Roger Hui

Nicolas, Prologue: From a language point of view, thanks to Ken Iverson, it is obvious that you want grade rather than sort as a primitive. Yet from a performance point of view, sort is currently faster than grade.

Can one be “more fundamental” than the other? If so, who’s wrong…APL or our CPUs? In any case, what does “fundamental” mean?

Roger: Sorting is faster than grading due to reasons presented in the J Wiki essay Sorting versus Grading, in the paragraph which begins “Is sorting necessarily faster than grading?” I can not prove it in the mathematical sense, but I believe that to be the case on any CPU when the items to be sorted/graded are machine units.

Nicolas, Formulation 1: Now, parsing ⍵[⍋⍵] (and not scanning the idiom) begs the question of how deeply an APL intepreter can “understand” what it’s doing to arrays.

How would an APL compiler resolve this conjunction in the parse tree? Do you simply have a bunch of state pointers such as “is the grade of” or “is sorted” or “is squozen” or “axis ordering” etc. walking along the tree? If so, do we have an idea of the number of such state pointers required to exhaustively describe what the APL language can do to arrays? If not, is there something more clever out there?

Roger: I don’t know of any general principles that can tell you what things can be faster. I do have two lists, one for J and another for Dyalog. A big part of the lists consists of compositions of functions, composition in the mathematical sense, that can be faster than doing the functions one after the other if you “recognize” what the composed function is doing and write a native implementation of it. Sort vs. grade is one example (sort is indexing composed with grade). Another one is (⍳∘1 >) or (1 ⍳⍨ >). The function is “find the first 1″ composed with >. These compositions have native implementations and:

      x←?1e6⍴1e6

      cmpx '5e5(1 ⍳⍨ >)x' '(5e5>x)⍳1' 
5e5(1 ⍳⍨ >)x → 0.00E0  |       0%
(5e5>x)⍳1    → 1.06E¯2 | +272100% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

      cmpx '¯1(1 ⍳⍨ >)x' '(¯1>x)⍳1' 
¯1(1 ⍳⍨ >)x → 2.41E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
(¯1>x)⍳1    → 4.15E¯3 | +71% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

If you get a “hit” near the beginning, as would be the case with 5e5, you win big. Even if you have to go to the end (as with ¯1), you still save the cost of explicitly generating the Boolean vector and then scanning it to the end.

Another one, introduced in 14.1, is:

      cmpx '(≢∪)x' '≢∪x'
(≢∪)x → 4.43E¯3 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
≢∪x   → 1.14E¯2 | +157% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

This is the tally nub composition, used often in a customer application. If you “know” that you just want the tally of the nub (uniques), you don’t actually have to materialise the array for the nub.

I am not conversant with compiler technology so I don’t know what all an APL compiler can do. I do know that there’s a thing call “loop fusion” where, for example, in a+b×c÷2, it doesn’t have to go through a,b,c in separate loops, but can instead do

    :for i :in ⍳≢a ⋄ z[i]←a[i]+b[i]×c[i]÷2 ⋄ :endif

saving on the array temp on every step. You win some with this, but I think the function composition approach wins bigger. On the other hand, I don’t know that there is a general technique for function composition. I mean, what general statements can you make about what things can be faster (AKA algebraically simpler)?

Nicholas: I sort of see…so jot is a “direct” conjunction. An indirect conjunction could be ⍵[⍺⍴⍋⍵] where the intermediate grade is reshaped. We “know” that grade and shape are “orthogonal” and can rewrite the formula to ⍴⍵[⍋⍵].

So if we can establish a list of flags, and establish how primitives touch these flags, and how these flags affect each other, then we can extend to any path of the parse tree, provided that the intermediate nodes don’t destroy the relationship between the two operations (here grade + indexing provides sort, independently of the reshape).

Of course we can spend our lives finding such tricks. Or we could try and systemise it.

Roger: What you are saying above is that reshape and indexing commute (i.e. reshape indexing ←→ indexing reshape). More generally, compositions of the so-called structural functions and perhaps of the selection functions are amenable to optimisations. This would especially be the case if arrays use the “strided representation” described in Nick Nickolov’s paper Compiling APL to JavaScript in Vector. I used strided representation implicitly to code a terse model of ⍺⍉⍵ in 1987.

Nicolas, Formulation 2: On which grounds did the guys in the ’50s manage to estimate the minimal list of operations that you needed to express data processing?

Roger: APL developed after Ken Iverson struggled with using conventional mathematical notation to teach various topics in data processing. You can get an idea of the process from the following papers:

In our own humble way, we go through a similar process: We talk to customers to find out what problems they are faced with, what things are still awkward, and think about what if anything we can do to the language or the implementation to make things better. Sometimes we come up with a winner, for example . You know, the idea for (grade) is that often you don’t just use ⍋x to order x (sort) but you use ⍋x to order something else. Similarly with , you often don’t want just x⍳y but you use it to apply a function to items with like indices. The J Wiki essay Key describes how the idea arose in applications, and then connected with something I read about, the Connection Machine, a machine with 64K processors (this was in the 1980s).

Nicolas, Formulation 3: Do we have something with a wider spectrum than “Turing complete or not” to categorise the “usefulness and/or efficiency” of a language?

Roger: Still no general principles, but I can say this:

  • Study the languages of designers whom you respect, and “borrow” their primitives, or at least pay attention to the idea. For example, =x is a grouping primitive in k. Symbols are Arthur Whitney’s most precious resource and for him to use up a symbol is significant.

    =x ←→ {⊂⍵}⌸x   old k definition

    =x ←→ {⍺⍵}⌸x   current k definition

    Both {⊂⍵}⌸x (14.0) and {⍺⍵}⌸x (14.1) are supported by special code.

  • Study the design of machines. For a machine to make something “primitive” is significant. For example, the Connection Machine has an instruction “generalised beta” which is basically {f⌿⍵}⌸. Around the time the key operator was introduced, we (Ken Iverson and I) realised that it’s better not to build reduction into a partitioning, so that if you actually want to have a sum you have to say +⌿⌸ rather than just +⌸. The efficiency can be recovered by recognising {f⌿⍵}⌸ and doing a native implementation for it. (Which Dyalog APL does, in 14.0.)

Roger, Epilogue: To repeat Nicolas’ question in the opening section, what does “fundamental” mean? (Is grade more fundamental than sort?)

In computability, we can use Turing completeness as the metric. But here the requirement is not computability but expressiveness. I don’t know that there is a definitive answer to the question. One way to judge the goodness of a notation, or of an addition to the existing notation such as dfns or key or rank, is to use it on problems from diverse domains and see how well it satisfies the important characteristics of notation set out in Ken Iverson’s Turing lecture:

  • ease of expressing constructs arising in problems
  • suggestivity
  • subordination of detail
  • economy
  • amenability to formal proofs

I would add to these an additional characteristic: beauty.

Do Functions Know Their Own Names?

Going back a long way when John Scholes and I were writing version 0 of Dyalog there was a big discussion about whether functions knew their own names. This discussion still surfaces, with John taking the side that they don’t and me taking the side that they do.

Essentially, John would argue that after A←2, the “2″ does not know that it is called “A”. So after (in modern parlance):

      add←{
          ⍺+⍵
      }

the part in {} does not know that it is called “add”.

The real question here can be put in different terms: Is the symbol + representing the addition function itself or is it one of the possible names of the addition function.

From an APL perspective, does this matter? Most of the time it makes no difference. However, when you view your SI stack it does. Consider:

      add←{
          ⍺+⍵
      }
      times←{
          ⍺×⍵
      }
      inner←{
          ⍺ ⍺⍺.⍵⍵ ⍵
      }

Now if we trace into

      1 2 add inner times 3 4

and stop on inner[1] what do we want to see when we type ⍺⍺ in the session. There are two possibilities:

Either you see:

{
    ⍺+⍵
}

or you see:

∇add

Which of these is more useful?

Being more provocative, try putting the functions in a capsule:

[0] foo
[1] 1 2{
[2]     ⍺+⍵
[3] }{
[4]     ⍺ ⍺⍺.⍵⍵ ⍵
[5] }{
[6]     ⍺×⍵
[7] }3 4

and repeatedly trace until [6]:

      )SI
#.foo[6]*
.
#.foo[4]
#.foo[1]

Compare this with the following:

[0] goo
[1] add←{
[2]     ⍺+⍵
[3] }
[4] inner←{
[5]     ⍺ ⍺⍺.⍵⍵ ⍵
[6] }
[7] times←{
[8]     ⍺×⍵
[9] }
[10] 1 2 add inner times 3 4
      )SI
#.times[1]*
.
#.inner[1]
#.goo[10]

In my view, the latter is much more communicative in a debugging environment.

Going back to the version 0 discussion: We didn’t have dfns or dops, so everything was traditional. The discussion was centred around:

∇r←a add b
[1] r←a+b
∇

∇r←a times b
[1] r←a×b
∇

∇ r←a (f inner g) b
[1] r←a f.g b
∇

Now trace this:

      1 2 add inner times 3 4

until at times[1]

The key question at the time was whether )SI should show this:

      )SI
#.times[1]*
.
#.inner[1]

or this:

      )SI
#.g[1]*
.
#.inner[1]

We choose the first of these options as more informative.

So naming things is good and using those names when reporting state information is also good. When the issue was disputed, David Crossley (who was managing the development of Dyalog) resolved it using the argument about the )SI output.

These days it might not be so obvious. In those days we were essentially thinking in terms of a scrolling paper terminal. It pre-dates the full screen experience that even the tty version gives you. We had to wait for Adam Curtis to join the team before we got that. With the context display whilst tracing there is a stronger argument that the eyes using the debugging information do not need the names. Whilst I admit to the weakening I don’t think it actually changes the balance of the case.

We use a lot of C macros in the interpreter. On Linux, gdb gives us access to those macros when we debug the C code – lldb on MAC, dbx on AIX and Visual Studio on Windows all do not have that information and are, therefore, far less helpful.