What’s Your Favourite Beautiful Squiggle?

Roger’s post speculating on Ken Iverson’s favourite APL expression reminded me that one of the delegates at Dyalog ’14 conducted a quick survey to find the most popular primitive (thanks to Alex Weiner for taking the initiative here!). His findings are reproduced below:

9 votes:
8 votes:
6 votes:
4 votes: ⍠ ⍟ * ⎕
3 votes: ⌽ ¨ ⍎
2 votes: ⍺ ∇ ≢ ← ⊃ ⊢ ⍬
1 vote: ⍉ , ∊ ⍋ ∘ ∧ ⍲ ⊥ ⌈

Unfortunately there were no reasons given…is it because it’s a shape that’s pleasing to the eye, a really nifty piece of functionality or something more esoteric?

As for me, it’s easy – my favourite is the Log glyph (). Not for a technical reason, although it performs a very useful function, nor due to its rather pleasing visual symmetry, but rather because of the way I was introduced to it. An APL virgin when I joined Dyalog 20 months ago, my first exercise was to familiarise myself with APL’s “beautiful squiggles”. When it came to the Log glyph I asked one of my colleagues a question and they dictated a line of APL to me to experiment with. As soon as they referred to by its informal name of “splat” that was it, I was entranced. Any language that is so powerful, so concise and yet can make adults have passionate discussions involving the word “splat” has got me for life.

Ken Iverson’s Favourite APL Expression?

What was Ken Iverson’s favourite APL expression? I don’t know that he had one and if he had I don’t know what it was, but if I have to guess …

From Sixteen APL Amuse-Bouches:

The expression (0,x)+(x,0) or its commute, which generates the next set of binomial coefficients, is present in the document that introduced APL\360 in 1967 [20, Fig.1] and the one that introduced J in 1990 [21, Gc&Gd]; in Elementary Functions: An Algorithmic Treatment in 1966 [22, p.69], in APL\360 User’s Manual in 1968 [23, A.5], in Algebra: An Algorithmic Treatment in 1972 [24, p.141], in Introducing APL to Teachers in 1972 [25, p.22], in An Introduction to APL for Scientists and Engineers in 1973 [26, p.19], in Elementary Analysis in 1976 [27, ex.1.68], in Programming Style in APL in 1978 [28, §6], in Notation as a Tool of Thought in 1980 [29, A.3], in A Dictionary of APL in 1987 [30, m∇n], and probably others.

The expression in action:

   ⎕←x←,1
1
   ⎕←x←(0,x)+(x,0)
1 1
   ⎕←x←(0,x)+(x,0)
1 2 1
   ⎕←x←(0,x)+(x,0)
1 3 3 1
   ⎕←x←(0,x)+(x,0)
1 4 6 4 1
   ⎕←x←(0,x)+(x,0)
1 5 10 10 5 1
   ⎕←x←(0,x)+(x,0)
1 6 15 20 15 6 1

It is easily seen from the expression that the n-th vector of binomial coefficients is a palindrome and that its sum is 2*n.

Musings on Reduction

In one man’s humble opinion, reduction () is the Queen of Operators.

Each (¨) comes a close second, but doesn’t get the cigar because each can be written in terms of reduction.

Two special cases are of interest: reduction along axes of length 1 (or reduction of a scalar) and reduction along axes of length 0.

With a length-1 axis (or scalar), the operand function is not applied (+⌿'A' → 'A'). This can be useful as an implicit no-op – see DFS video on YouTube.

With a length-0 axis, a primitive operand returns its right identity item – but only if one is defined (⌊⌿⍬). Otherwise: DOMAIN ERROR.

Another way to think about the 0-length axis case is that a right identity item (if there is one) is catenated to the argument prior to the reduction. Functional Programming languages tend to define reduction in this way by supplying an explicit initial value (ival) to the reduction:

    fold fn ival [] = ival
    fold fn ival (x:xs) = fn x (fold fn ival xs)

We can write such a variant of in APL, supplying the initial value as right operand ⍵⍵:

      fold ← {⍺⍺⌿⍵⍪⍵⍵}        ⍝ right operand ⍵⍵ is initial value

      × fold 1 ⊢2 3 4         ⍝ same as regular ×⌿
24

      {⍺×⍵}fold 1 ⊢2 3 4      ⍝ non-primitive operand function
24

      {⍺×⍵}fold 1 ⊢⍬          ⍝ initial value returned for empty argument
1

Whilst it doesn’t provide the no-op trick for length-1 axes, fold gives us better control for null cases than does primitive reduction, which relies on the single prototypical item of its argument array:

      ⊢mat ← 2 3 ∘.+ 0(0 0)
┌─┬───┐
│2│2 2│
├─┼───┤
│3│3 3│
└─┴───┘

Notice the discontinuity in the depth of the result with regular +⌿ as the number of rows reaches 0:

      +⌿ 2↑mat
┌─┬───┐
│5│5 5│
└─┴───┘

      +⌿ 1↑mat
┌─┬───┐
│2│2 2│
└─┴───┘

      +⌿ 0↑mat              ⍝ Eh?
0 0

Supplying the variant with a prototypical row produces a more uniform convergence:

      +fold 0(0 0) ⊢2↑mat
┌─┬───┐
│5│5 5│
└─┴───┘

      +fold 0(0 0) ⊢1↑mat
┌─┬───┐
│2│2 2│
└─┴───┘

      +fold 0(0 0) ⊢0↑mat   ⍝ Ah!
┌─┬───┐
│0│0 0│
└─┴───┘

A similar discontinuity can be seen even for axes of length 1, with non-scalar primitive operand functions:

      ⊢mat ← 3 3⍴⍳9
1 2 3
4 5 6
7 8 9

Now:

      ,⌿ 3↑mat              ⍝ join reduction
┌─────┬─────┬─────┐
│1 4 7│2 5 8│3 6 9│
└─────┴─────┴─────┘

      ,⌿ 2↑mat
┌───┬───┬───┐
│1 4│2 5│3 6│
└───┴───┴───┘

      ,⌿ 1↑mat              ⍝ Tsk!
1 2 3

      ,⌿ 0↑mat              ⍝ Bah!
DOMAIN ERROR

But:

      ,fold(⊂⍬) ⊢3↑mat
┌─────┬─────┬─────┐
│1 4 7│2 5 8│3 6 9│
└─────┴─────┴─────┘

      ,fold(⊂⍬) ⊢2↑mat
┌───┬───┬───┐
│1 4│2 5│3 6│
└───┴───┴───┘

      ,fold(⊂⍬) ⊢1↑mat      ⍝ Ooh!
┌─┬─┬─┐
│1│2│3│
└─┴─┴─┘

      ,fold(⊂⍬) ⊢0↑mat      ⍝ Aah!
┌┬┬┐
││││
└┴┴┘

Although we have no specific plans to do so, it is conceivable that this definition of fold could be introduced as a variant of primitive reduction:

        nums ← ⍠(⊂⍬)        ⍝ possible variant for numeric reduction

      ,⌿nums 1↑mat          ⍝ Ooh!
┌─┬─┬─┐
│1│2│3│
└─┴─┴─┘
      ,⌿nums 0↑mat          ⍝ Aah!
┌┬┬┐
││││
└┴┴┘
      ,/nums 3 1↑mat        ⍝ Mmm! reduction along last axis
┌─┬─┬─┐
│1│4│7│
└─┴─┴─┘

Notice that the left and right arguments of a reduction’s operand function need not be of the same kind. Using an informal type notation:

      ⌿ :: (⍺ ∇ ⍵ → ⍵) ∇∇ [⍺]⍪⍵ → ⊂⍵

which, given an argument of uniform kind, collapses to:

      ⌿ :: (⍺ ∇ ⍺ → ⍺) ∇∇ [⍺] → ⊂⍺

I hope to say more about this style of polymorphic type notation in a future posting. In the meantime, the significant point is only that, in the general case, the operand function is of “kind” (⍺ ∇ ⍵ → ⍵), which means that the kind of its left argument may differ from that of its right argument and result. See more discussion on this idea in the notes for foldl in dfns.dws.