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.

Quicksort in APL

Quicksort is a classic sorting algorithm invented by C.A.R. Hoare in 1961 [0, 1]. It has been known for some time that quicksort has a terse rendition in APL [2]. To get right to it, here is the code:

Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}

The “pivot” ⍵⌷⍨?≢⍵ is randomly chosen. ((∇<S)⍪=S⍪(∇>S)) is a fork, selecting the parts of which are less than the pivot, equal to the pivot, and greater than the pivot. The function is recursively applied to the first and the last of these three parts.

      ⎕io←0 ⋄ ⎕rl←7*5

      ⎕←x←?13⍴20
3 2 19 16 11 4 18 17 9 17 7 3 1
      Q x
1 2 3 3 4 7 9 11 16 17 17 18 19

The variant Q1 obtains by enclosing each of the three parts. Its result exhibits an interesting structure. The middle item of each triplet is the value of the pivot at each recursion. Since the pivot is randomly chosen, the result of Q1 can be different on the same argument, as illustrated below:

      Q1←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((⊂∘∇<S)⍪(⊂=S)⍪(⊂∘∇>S))⍵⌷⍨?≢⍵}

      Q1 x
┌──────┬───┬────────────────────────────────────┐
│┌─┬─┬┐│3 3│┌─┬─┬──────────────────────────────┐│
││1│2│││   ││4│7│┌┬─┬─────────────────────────┐││
│└─┴─┴┘│   ││ │ │││9│┌──┬──┬─────────────────┐│││
│      │   ││ │ │││ ││11│16│┌─────────┬──┬──┐││││
│      │   ││ │ │││ ││  │  ││┌┬─────┬┐│18│19│││││
│      │   ││ │ │││ ││  │  ││││17 17│││  │  │││││
│      │   ││ │ │││ ││  │  ││└┴─────┴┘│  │  │││││
│      │   ││ │ │││ ││  │  │└─────────┴──┴──┘││││
│      │   ││ │ │││ │└──┴──┴─────────────────┘│││
│      │   ││ │ │└┴─┴─────────────────────────┘││
│      │   │└─┴─┴──────────────────────────────┘│
└──────┴───┴────────────────────────────────────┘

      Q1 x
┌───────────────────────┬─┬─────────────────────────┐
│┌──────────────────┬─┬┐│9│┌──┬──┬─────────────────┐│
││┌┬─┬─────────────┐│7│││ ││11│16│┌───────────┬──┬┐││
││││1│┌┬─┬────────┐││ │││ ││  │  ││┌┬─────┬──┐│19││││
││││ │││2│┌┬───┬─┐│││ │││ ││  │  ││││17 17│18││  ││││
││││ │││ │││3 3│4││││ │││ ││  │  ││└┴─────┴──┘│  ││││
││││ │││ │└┴───┴─┘│││ │││ ││  │  │└───────────┴──┴┘││
││││ │└┴─┴────────┘││ │││ │└──┴──┴─────────────────┘│
││└┴─┴─────────────┘│ │││ │                         │
│└──────────────────┴─┴┘│ │                         │
└───────────────────────┴─┴─────────────────────────┘

The enlist of the result of Q1 x is the same as Q x, the sort of x:

Q1 x
1 2 3 3 4 7 9 11 16 17 17 18 19
      Q x
1 2 3 3 4 7 9 11 16 17 17 18 19

This note is meant to explore the workings of a classical algorithm. To actually sort data in Dyalog, it is more convenient and more efficient to use {⍵[⍋⍵]}. Earlier versions of this text appeared in [3, 4].

References

  1. Hoare, C.A.R, Algorithm 63: Partition, Communications of the ACM, Volume 4, Number 7, 1961-07.
  2. Hoare, C.A.R, Algorithm 64: Quicksort, Communications of the ACM, Volume 4, Number 7, 1961-07.
  3. Hui, Roger K.W., and Kenneth E. Iverson, J Introduction and Dictionary, 1991-2014; if. entry.
  4. Hui, Roger K.W., Quicksort, J Wiki Essay, 2005-09-28.
  5. Hui, Roger K.W. Sixteen APL Amuse-Bouches, 2014-11-02.

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.