The Reflex/Commute Operator

The monadic operator is defined and modeled as follows:

     f⍨ ⍵  ←→  ⍵ f ⍵
   ⍺ f⍨ ⍵  ←→  ⍵ f ⍺

   {⍺←⍵ ⋄ ⍵ ⍺⍺ ⍺}

Reflex

Some common well-known functions can be written as f⍨ where f is itself a well-known function:

   +⍨    double
   ×⍨    square
   ?⍨    random permutation
   ⍳⍨    self-index, APL Amuse-Bouche 3

See http://www.jsoftware.com/jwiki/Essays/Reflexive for further examples.

Awareness of the importance of the reflexive case might have led us to avoid the mistake in the definition of the dyadic case of . That is, if

   ⍺⍋⍵ ←→ ⍺⌷⍨⊂⍋⍵

then ⍋⍨⍵ would be sort. Ken Iverson seemed to have had this awareness because that’s how he defined the dyadic case of in J. (I say “seemed” because he expressed surprise when first shown this use of ⍋⍨.)

The monadic case f⍨ came relatively late. It was not in Operators and Functions (1978) nor Rationalized APL (1983), and only introduced in A Dictionary of APL (1987). It came to Ken Iverson when he explicitly looked to natural languages for inspiration, whence it became “obvious”: f⍨⍵ ←→ ⍵ f ⍵ is the reflexive voice (je m’appelle Roger) and ⍺ f⍨ ⍵ ←→ ⍵ f ⍺ is the passive voice (the programming competition was won by a 17-year-old student vs. a 17-year-old student won the programming competition), both having evolved in natural languages for effective communication and elegant expression.

Commute

The alternative definition of ⍺⍋⍵ above, while illustrating the importance of the reflexive case (f⍨ ⍵), also illustrates the passive case (⍺ f⍨ ⍵). ⍺⌷⍨⊂⍋⍵ can be read and understood as “ indexed by the enclosed grade of “, a different (and in my mind a better) emphasis than (⊂⍋⍵)⌷⍺, “the enclosed grade of , indexed into “.

I note that Arianna Locatelli, winner of the 2015 APL Problem Solving Competition but an APL beginner, used twenty-one times in her presentation at Dyalog ’15. For example, was used in the computation of the standard deviation (slide 13):

   sol5←{a←,⍵ ⋄ ⊃0.5*⍨(⍴a)÷⍨+/2*⍨a-(⍴a)÷⍨+/a}

I believe this formulation comes naturally because can be used to write functions in the order that they are applied. Another way to put it is that reduces the need for long-scope parentheses. For example:

   (2×a) ÷⍨ (-b) (+,-) 0.5 *⍨ (b*2)-4×a×c
   ((-b) (+,-) ((b*2)-4×a×c)*0.5) ÷ 2×a

That is easy to implement, {⍺←⍵ ⋄ ⍵ ⍺⍺ ⍺}, is neither here nor there; its value as a tool of thought is easily demonstrated.

Parallel Programming with Futures/Isolates

DSC05195Morten Kromberg went right to it with his well-prepared workshop on the prototype features that were introduced in version 14.0 of Dyalog APL. The features are still partly modelled in APL to allow the first wave of users to pass judgement on the design. Throughout the workshop, we were asked for feedback, to ensure that the new primitives will be as well implemented as possible.

Everyone is encouraged to apply the new tools in practice so they can be adjusted and possibly get expanded functionality based on feedback from actual use-cases.

There is no denying the the obvious performance gains that Morten demonstrated: He was able to let the computer waste 9 idle seconds in only slightly more than 3 seconds!

Joking aside, one practical example that showed how useful parallel processing can be, was collating character counts from online news sites. Because of latency in loading these pages over the internet, starting many parallel threads that each requested a page greatly reduced the wait time. DSC05197 One workshop participant volunteered a piece of code that needed to be parallelized got up and pair programmed this with immediately achieving significant performance gains.

The idea of Futures is allowing the continuation of other work before an asynchronously launched calculation is finished. All selection and structural functions can be used on an array containing futures without blocking to wait for the result, as long as no actual data values are required. Meanwhile, other processes (or computers!) could be finishing the evaluation in the background.

It was captivating to observe output being printed and check the status while the calculation work progressed, or accessing parts of an array while other parts still reported as in progress. Morten even had a graphical representation of how load is distributed across processor cores.

Maybe the most exciting thing about all this is that we will soon welcome several new APL squiggles; Isolate (¤) and Parallel (). And at the end of the day, Morten even pulled a pet (pun intended) card out of his sleeve: A Schrödinger’s cat operator! The symbol is of course a question mark in a box (), signifying how the evaluation of the cat’s life (or in our case – the result) does not even begin until actually queried. This is a novel way to specify specific lazy evaluation.

All in all, an exciting look at what possibilities for parallelism the future will bring.

Permutations

I started composing a set of APL exercises in response to a query from a new APL enthusiast who attended Morten’s presentation at Functional Conf, Bangalore, October 2014. The first set of exercise are at a low level of difficulty, followed by another set at an intermediate level. One of the intermediate exercises is:

Permutations

a. Compute all the permutations of ⍳⍵ in lexicographic order. For example:

   perm 3
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

b. Write a function that checks whether is a solution to perm ⍺, without computing perm ⍺. You can use the function assert. For example:

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

pcheck←{
  assert 2=⍴⍴⍵:
  assert (⍴⍵)≡(!⍺),⍺:
  …
  1
}

   6 pcheck perm 6
1

   4 pcheck 2 4⍴0 1 2 3, 0 1 3 2
assertion failure
pcheck[2] assert(⍴⍵)≡(!⍺),⍺:
         ∧

c. What is the index of permutation in perm ⍺? Do this without computing all the permutations. For example:

   7 ip 1 6 5 2 0 3 4    ⍝ index from permutation
1422

(The left argument in this case is redundant, being the same as ≢⍵.)

d. What is the -th permutation of ⍳⍺? Do this without computing all the permutations. For example:

   7 pi 1442             ⍝ permutation from index
1 6 5 2 0 3 4

   (perm 7) ≡ 7 pi⍤0 ⍳!7
1

The Anagram Kata

Coincidentally, Gianfranco Alongi was attempting in APL the anagrams kata from Cyber Dojo:

Write a program to generate all potential anagrams of an input string.

For example, the potential anagrams of “biro” are
biro bior brio broi boir bori
ibro ibor irbo irob iobr iorb
rbio rboi ribo riob roib robi
obir obri oibr oirb orbi orib

This is essentially the same program/exercise/kata, because the potential anagrams are 'biro'[perm 4]. You can compare solutions in other languages to what’s here (google “anagrams kata”).

Spoiler Alert

Deriving a Solution

I am now going to present solutions to part a of the exercise, generating all permutations of ⍳⍵.

Commonly, in TDD (test-driven development) you start with a very simple case and try to extend it successively to more general cases. It’s all too easy to be led into a dead-end because the simple case may have characteristics absent in a more general case. For myself, for this problem, I would start “in the middle”: Suppose I have perm 3, obtained by whatever means:

   p
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

How do I get perm 4 from that? One way is as follows:

   p1←0,1+p
   (0 1 2 3[p1]) (1 0 2 3[p1]) (2 0 1 3[p1]) (3 0 1 2[p1])
┌───────┬───────┬───────┬───────┐
│0 1 2 3│1 0 2 3│2 0 1 3│3 0 1 2│
│0 1 3 2│1 0 3 2│2 0 3 1│3 0 2 1│
│0 2 1 3│1 2 0 3│2 1 0 3│3 1 0 2│
│0 2 3 1│1 2 3 0│2 1 3 0│3 1 2 0│
│0 3 1 2│1 3 0 2│2 3 0 1│3 2 0 1│
│0 3 2 1│1 3 2 0│2 3 1 0│3 2 1 0│
└───────┴───────┴───────┴───────┘

So it’s indexing each row of a matrix m by 0,1+p. There are various ways of forming the matrix m, one way is:

   ⍒⍤1∘.=⍨0 1 2 3
0 1 2 3
1 0 2 3
2 0 1 3
3 0 1 2

(Some authors waxed enthusiastic about this “magical matrix”.) In any case, a solution obtains readily from the above description: Form a matrix from the above individual planes; replace the 0 1 2 3 by ⍳⍵; and make an appropriate computation for the base case (when 0=⍵). See the 2015-07-12 entry below.

The Best perm Function

What is the “best” perm function I can write in APL? This “best” is a benchmark not only on my own understanding but also on advancements in APL over the years.

“Best” is a subjective and personal measure. Brevity comes into it but is not the only criteria. For example, {(∧/(⍳⍵)∊⍤1⊢t)⌿t←⍉(⍵⍴⍵)⊤⍳⍵*⍵} is the shortest known solution, but requires space and time exponential in the size of the result, and that disqualifies it from being “best”. The similarly inefficient {(∧/(⍳⍵)∊⍤1⊢t)⌿t←↑,⍳⍵⍴⍵} is shorter still, but does not work for 1=⍵.

1981, The N Queens Problem

    p←perm n;i;ind;t
   ⍝ all permutations of ⍳n
    p←(×n,n)⍴⎕io
    →(1≥n)⍴0
    t←perm n-1
    p←(0,n)⍴ind←⍳n
    i←n-~⎕io
   l10:p←(i,((i≠ind)/ind)[t]),[⎕io]p
    →(⎕io≤i←i-1)⍴l10

It was the fashion at the time that functions be written to work in either index-origin and therefore have ⎕io sprinkled hither, thither, and yon.

1987, Some Uses of { and }

   perm:  ⍪⌿k,⍤¯1 (⍙⍵-1){⍤¯ 1 k~⍤1 0 k←⍳⍵
       :  1≥⍵
       :  (1,⍵)⍴0

Written in Dictionary APL, wherein: ⍪⌿⍵ ←→ ⊃⍪⌿⊂⍤¯1⊢⍵ and differs from its definition in Dyalog APL; is equivalent to in dfns; ⍺{⍵ ←→ (⊂⍺)⌷⍵; and ¯ by itself is infinity.

1990-2007

I worked on perm from time to time in this period, but in J rather than in APL. The results are described in a J essay and in a Vector article. The lessons translate directly into Dyalog APL.

2008, http://dfns.dyalog.com/n_pmat.htm

   pmat2←{{,[⍳2]↑(⊂⊂⎕io,1+⍵)⌷¨⍒¨↓∘.=⍨⍳1+1↓⍴⍵}⍣⍵⍉⍪⍬}

In retrospect, the power operator is not the best device to use, because the left operand function needs both the previous result (equivalent to perm ⍵-1) and . It is awkward to supply two arguments to that operand function, and the matter is finessed by computing the latter as 1+1↓⍴⍵.

In this formulation, ⍉⍪⍬ is rather circuitous compared to the equivalent 1 0⍴0. But the latter would have required a or similar device to separate it from the right operand of the power operator.

2015-07-12

   perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}

For a time I thought the base case can be ⍳1 0 instead of 1 0⍴0, and indeed the function works with that as the base case. Unfortunately (⍳1 0)≢1 0⍴0, having a different prototype and datatype.

Future

Where might the improvements come from?

  • We are contemplating an under operator whose monadic case is f⍢g ⍵ ←→ g⍣¯1 f g ⍵. Therefore 1+∇ ¯1+⍵ ←→ ∇⍢(¯1∘+)⍵
  • Moreover, it is possible to define ≤⍵ as ⍵-1 (decrement) and ≥⍵ as ⍵+1 (increment), as in J; whence 1+∇ ¯1+⍵ ←→ ∇⍢≤⍵
  • Monadic = can be defined as in J, =⍵ ←→ (∪⍳⍨⍵)∘.=⍳≢⍵ (self-classify); whence ∘.=⍨⍳⍵ ←→ =⍳⍵

Putting it all together:

   perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,∇⍢≤⍵)⌷⍤1⍒⍤1=⍳⍵}

We should do something about the ,[⍳2] :-)​​

Type Comments

I’ve taken to commenting the closing brace of my inner dfns with a home-grown type notation pinched from the Functional Programming community:

    dref←{                  ⍝ Value for name ⍵ in dictionary ⍺ 
        names values←⍺      ⍝ dictionary pair
        (names⍳⊂⍵)⊃values   ⍝ value corresponding to name ⍵
    }                       ⍝ :: Value ← Dict ∇ Name

I keep changing my mind about whether the result type should be to the left (Value ← ...) or to the right (... → Value). The FP crowd favours → Value but I’m coming around to Value ← because:

* In contrast to (say) Haskell, APL’s function/argument sequences associate right.
* Value ← mirrors the result pattern in a tradfn header and so looks familiar.
* The type of function composition f∘g is simpler this way round.

Such comments serve as an aide-mémoire when I later come to read the code though, with some ingenuity, the notation might possibly be extended to a more formal system, which could have value to a compiler or code-checker. We would need:

Glyphs for Dyalog’s three primitive atomic data types. For no particularly good reason, I’ve been using:

# number
' character
. ref

Glyphs for a few generic (polymorphic) types. These could be just regular lower-case letters a b c … though I currently prefer greek letters:

⍺ ∊ ⍳ ⍴ ⍵ ...

Some constructors for type expressions. This is the most contentious part. For what it’s worth, I’ve been using:

::  is of type ...
∇  function
∇∇  operator
←  returns
[⍺] vector of ⍺s
{⍺} optional left argument ⍺

For example:

foo :: ⍵ ← {⍺} ∇ ⍵

implies:
foo is an ambi-valent function whose
– result is of the same type () as its right argument and whose
– optional left argument may be of a different type ().

I can abstract/name type expressions with (capitalised) identifiers using :=. For example:

Dict   := [Name][Value]        ⍝ dictionary name and value vectors
Eval   := Expr ← Dict ∇ Expr   ⍝ expression reduction
List ⍵ := '∘' | ⍵ (List ⍵)     ⍝ recursive pairs. See
list
Name   := ⍞                    ⍝ primitive type: character vector

The type: character vector ['] is used so frequently that the three glyphs fuse into: . This means that a vector-of-character-vectors, also a common type, is [⍞].

Primitive and derived function types.
If we’re not too nit-picky and ignore issues such as single extension and rank conformability, we can give at least hints for the types of some primitive functions and operators.

 ⍳ :: # ← ⍺ ∇ ⍺              ⍝ dyadic index-of
 ⍴ :: ⍺ ← [#] ∇ ⍺            ⍝ reshape (also take, transpose, ...)

The three forms of primitive composition have interesting types:

∘ :: ⍴ ← {⍺} (⍴ ← {⍺} ∇ ⍳) ∇∇ (⍳ ← ∇ ⍵ ) ⍵     ⍝ {⍺}f∘g ⍵
:: ⍴ ←                 ⍺ ∇∇ (⍴ ← ⍺ ∇ ⍵ ) ⍵   ⍝ A∘g ⍵
:: ⍴ ←      ((⍴ ← ⍺ ∇ ⍵) ∇∇ ⍵ )⍺             ⍝ (f∘B)⍵

It follows that:

f :: ⍴ ← {⍺} ∇ ⍳
g :: ⍳ ←     ∇ ⍵
=> f∘g :: ⍴ ← {⍺} ∇ ⍵          ⍝ intermediate type ⍳ cancels out

and for trains:

A :: ⍳                  ⍝ A is an array of type ⍳
f :: ⍳ ← {⍺} ∇ ⍵
g :: ⍴ ← {⍳} ∇ ∊
h :: ∊ ← {⍺} ∇ ⍵
=> f g h :: ⍴ ← {⍺} ∇ ⍵        ⍝ fgh fork
=> A g h :: ⍴ ←     ∇ ⍵        ⍝ Agh fork
=>   g h :: ⍴ ← {⍺} ∇ ⍵        ⍝ gh atop

For a more substantial example, search function joy for :: and := in a recent download of dfns.dws.

Muse:
This notation is not yet complete or rigorous enough to be of much use to a compiler but there may already be enough to allow the writing of a dfn, which checks its own and others internal consistency. In the long term, if a notation similar to this evolved into something useful, it might be attractive to allow optional type specification as part of the function definition: without the comment symbol:

    dref←{                  ⍝ Value for name ⍵ in dictionary ⍺ 
        names values←⍺      ⍝ dictionary pair
        (names⍳⊂⍵)⊃values   ⍝ value corresponding to name ⍵
    } :: Value ← Dict ∇ Name

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 (see Special Cases below) 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.