A magic function is an APLcoded (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 Ccoded implementation. A case in point is ∘.≡
(and ∘.≢
) on enclosed character vectors, as recounted in the blog post A SpeedUp Story. The chronology is recovered from the Gmail, Mantis and SVN systems.
20141027 04:24  Nicolas  initial email describing the problem 
20141027 07:33  Roger  proposes i∘.=i←a⍳a as a solution 
20141027 07:36  Jay  objects that solution should check ⎕CT 
20141027 07:40  Roger  responds to objection 
20141027 10:29  Roger  creates Mantis issue 
20141027 13:57  Roger  SVN commit 
20141027 18:12  Roger  reports factor 664 speedup and submits blog post 
20141028 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:
c
1 iff a “selfie”, i.e. the left and right arguments are equal as C pointerseq
1 if∘.≡
; 0 if∘.≢
r
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 
664  14.1 
x∧.=y and x∨.≠y 
1.54  14.1 
,/y 
1∞  15.0 
x⊥y 
126  15.0 
x⊤y 
13.3  15.0 
One can always make a magic function faster by handtranslating 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 2element 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 wellsuited for implementing operators. An operator has potentially tens or hundreds of cases, and it would be onerous, not costeffective 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. nonselfie
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. nonselfie
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.