The 2021 APL Problem Solving Competition: Phase I – Best of Breed

By: Stefan Kruger
Stefan works for IBM making databases. He tries to learn at least one new programming language a year, and a few years ago he got hooked on APL and participated in the competition. This is his perspective on some solutions that the judges picked out – call it the “Judges’ Pick”, if you like; smart, novel, or otherwise noteworthy solutions that can serve as an inspiration.


Congratulations to all the winners of the 2021 APL Problem Solving Competition (you can learn more about the phase 2 winners in this article) and well done to Dzintars Klušs who won the Grand Prize. At the recent Dyalog ’21 user meeting, we got to enjoy the runner-up, Victor Ogunlokun, walking us through his solutions live.

In this post I’ll go through some great solutions that were submitted (and some that weren’t submitted) to the Phase I problems so that we can all marvel in the ingenuity and perhaps learn a thing or two. If you’re feeling inspired by the end, go ahead and participate in this year’s round which just launched.

If you’re new to the APL Problem Solving Competition, Phase I problems tend to be short and the expectation is that solutions will be “one-liners” (dfns). However, although it might seem like it from some of the solutions here, this isn’t a code golf competition! Solutions are judged holistically: do they solve the problem, are they efficient, and are they clear? Even though a few test cases are given, there is no guarantee that your solution is correct just because it works for the example data. The judging process involves running the code on many hidden test cases too. Crucially, just because your code is accepted, it doesn’t necessarily mean that you’ll get full marks.

As with my blog post that reviewed the 2020 Phase II solutions, I’ve included a more in-depth examination of one or two problems.

Problem 1: Are You a Bacteria?

Something from the excellent Project Rosalind problem collection, the task is to compute the combined percentage of guanine (G) and cytosine (C) in a given DNA-string.

Efficiency can vary a lot, depending on whether summation or multiplication (or even division!) is performed first. Some solutions were also leading-axis oriented.

Here’s my solution:

      {100×(+⌿⍵∊'CG')÷≢⍵} 'ACGTACGTACGTACGT'
50

which several competitors made more tacit with:

      {100×(+⌿÷≢)⍵∊'GC'} 'ACGTACGTACGTACGT'
50

or even went further:

      (100×≢÷⍨1⊥∊∘'GC') 'ACGTACGTACGTACGT'
50

If you’re unfamiliar with the 1⊥ trick, it’s a way of summing a vector:

      1⊥6 3 9 8 12 62
100

It’s perhaps not immediately obvious why this should work. Here’s one explanation. Assume we want to sum the vector 1 0 2 0 0. We can do this in a very convoluted way by using a sum inner product with a vector of exponentials: [14, 13, 12, 11, 10]:

      (1*4 3 2 1 0)+.×1 0 2 0 0
3

If we expand the exponentials to the left we get a vector of 1s. We can then break apart the inner product by turning +. to a +⌿ to the left:

      +⌿1 1 1 1 1×1 0 2 0 0
3

This is the textbook definition of 1⊥! Look:

      1⊥1 0 2 0 0
3

which, to be clear, is just the sum-reduce-first:

      +⌿1 0 2 0 0
3

Using 1⊥ to sum has two advantages over the more obvious formulation +⌿. Firstly, it’s easier to use in tacit formulations as it doesn’t require an operator, and secondly, it’s usually faster. The reasons for it being quicker is somewhat beyond the scope of this post, but it’s to do with 1⊥ making no guarantees about the ordering of operations, meaning that the interpreter is free to vectorise more efficiently.

Problem 2: Index-Of Modified

This problem wanted us to write a function that behaves like the APL Index Of function R←X⍳Y except that it should return 0 for elements of Y not found in X.

I wrote:

      p2 ← {0@((≢⍺)∘<)⊢⍺⍳⍵}
      2 3 p2 ⍳5
0 1 2 0 0

which is basically saying “change all instances of numbers greater than the length of the argument to zero”, which is how X⍳Y presents values that are not found.

Some very different solutions were submitted, for example:

      p2 ← ⍳|⍨1+≢⍤⊣
      2 3 p2 ⍳5
0 1 2 0 0

which is simply:

      p2 ← {(1+≢⍺)|⍺⍳⍵} ⍝ dfn of the above
      2 3 p2 ⍳5
0 1 2 0 0

Another option would have been to multiply ⍺⍳⍵ with ≢⍺, although no-one submitted exactly this:

      p2 ← ≢⍤⊣(≥×⊢)⍳
      2 3 p2 ⍳5
0 1 2 0 0

which could have been written explicitly as:

      p2 ← {m×(≢⍺)≥m←⍺⍳⍵} ⍝ dfn of the above
      2 3 p2 ⍳5
0 1 2 0 0

Problem 3: Multiplicity

Write a function that:

  • has a right argument Y which is an integer vector or scalar
  • has a left argument X which is also an integer vector or scalar
  • finds which elements of Y are multiples of each element of X and returns them as a vector (in the order of X) of vectors (in the order of Y).

Some test data was provided:

      X ← 2 4 7 3 9
      Y ← 5 7 8 1 12 10 20 16 11 4 2 15 3 18 14 19 13 9 17 6

I wrote something that, in retrospect, looks somewhat clumsy:

      p3 ← {⍵∘{⍵/⍺}¨↓0=⍺∘.|,⍵}
      X p3 Y
┌─────────────────────────┬────────────┬────┬──────────────┬────┐
│8 12 10 20 16 4 2 18 14 6│8 12 20 16 4│7 14│12 15 3 18 9 6│18 9│
└─────────────────────────┴────────────┴────┴──────────────┴────┘

which can be expressed more compactly as:

      p3 ← {/∘⍵¨↓0=⍺∘.|⍥,⍵}
      X p3 Y
┌─────────────────────────┬────────────┬────┬──────────────┬────┐
│8 12 10 20 16 4 2 18 14 6│8 12 20 16 4│7 14│12 15 3 18 9 6│18 9│
└─────────────────────────┴────────────┴────┴──────────────┴────┘

or:

      X (⊢⊂⍤/⍤1⍨0=∘.|⍥,) Y
┌─────────────────────────┬────────────┬────┬──────────────┬────┐
│8 12 10 20 16 4 2 18 14 6│8 12 20 16 4│7 14│12 15 3 18 9 6│18 9│
└─────────────────────────┴────────────┴────┴──────────────┴────┘

although no-one actually submitted that, to everyone’s credit.

Problem 4: Square Peg, Round Hole

Write a function that:

  • takes a right argument which is an array of positive numbers representing circle diameters
  • returns a numeric array of the same shape as the right argument representing the difference between the areas of the circles and the areas of the largest squares that can be inscribed within each circle.

I had to read that many times before it sank in. The key to achieve something snappy is to really work through the maths until it is as compact as possible, which, if you’re anything like me, you didn’t bother to do.

My attempt was:

      p4 ← {(○2*⍨⍵÷2)-2÷⍨⍵*2}

but there are much neater solutions if you did your homework. Here’s one that no-one found:

      p4 ← (○-+⍨)4÷⍨×⍨

and a nice explicit version:

      p4 ← {⍵×⍵×0.5-⍨○÷4}

which can be derived from this simplified mathematical expression, suggested by Rodrigo:


Explanation: The area of the circle is ○r*2, which is ○(⍵÷2)*2, in turn equivalent to ⍵×⍵×○÷4. The area of the square [ABCD] is twice the area of the triangle [ABC]. Given that the area of the triangle is 0.5×⍵×⍵÷2, the area of the square becomes 0.5×⍵×⍵. Putting both together, we get (⍵×⍵×○÷4)-⍵×⍵×0.5, the same as ⍵×⍵×(○÷4)-0.5, which is ⍵×⍵×0.5-⍨○÷4.

Square inside a circle with its diagonal as the circle's diameter

Problem 5: Rect-ify

For this problem, we were asked to plant a number of trees in a rectangular pattern with complete rows and columns, meaning all rows have the same number of trees. That rectangular pattern also needed to be as “square as possible”, meaning there is a minimal difference between the number of rows and columns in the pattern.

Here’s a smart solution, based on the observation that the “most square” choice must have one factor being the largest factor less than or equal to the square root:

      p5 ← {N,⍵÷1⌈N←⌈/0,⍵∨⍳⌊⍵*÷2}

This solution works well on large numbers of trees, too:

      p5 98776512304
280888 351658

Someone even offered up a recursive solution:

      p5rec ← {⍵=0:2⍴0 ⋄ ⍵ {0=⍵|⍺: ⍵,⍺÷⍵ ⋄ ⍺∇⍵-1} ⌊⍵*÷2}

So is one solution better than the other? Well, they both work correctly, but one is a lot faster than the other. Do you want to guess which was faster before we test it?

      'cmpx'⎕CY'dfns'
      cmpx 'p5 98776512304' 'p5rec 98776512304'
  p5 98776512304    → 8.7E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  p5rec 98776512304 → 6.1E¯3 | -94% ⎕⎕⎕

Surprised? I was! So, what is going on here? The non-recursive solution relies on a rather crude way to find the factors, which is a fairly large number to factorise even if it only needs to go up to the square root. The recursive version just tries each number in turn, up to the square root.

Can we be even smarter? This version was offered up by APL Orchard regular @rak1507:

      p5rak1507 ← {a,⍵÷1⌈a←⊃⌽⍸0=⍵|⍨⍳⌊⍵*.5} ⍝ @rak1507
      cmpx 'p5 98776512304' 'p5rec 98776512304' 'p5rak1507 98776512304'
  p5 98776512304        → 8.7E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  p5rec 98776512304     → 6.3E¯3 | -93% ⎕⎕⎕                                     
  p5rak1507 98776512304 → 4.2E¯3 | -96% ⎕⎕

Basically, (⊢∨⍳) is neat as a code-golf trick, but not great in terms of efficiency.

Problem 6: Fischer Random Chess

According to Wikipedia, Fischer random chess is a variation of the game of chess invented by former world chess champion Bobby Fischer. Fischer random chess employs the same board and pieces as standard chess, but the starting position of the non-pawn pieces on the players’ home ranks is randomised, following certain rules.

White’s non-pawn pieces are placed on the first rank according to the following rules:

  • the Bishops must be placed on opposite-colour squares
  • the King must be placed on a square between the rooks.

The task was to write a function that verifies that a given board placement is valid according to these rules.
This was my solution for this:

      q6 ← {(1=+/(⍵⍳'K')>⍸'R'=⍵)∧1=+/2|⍸'B'=⍵}

but there was a lot of variety in the solutions submitted to this problem. For example:

      q6i  ← {≠/2|⍸'B'=⍵}∧'RKR'≡∩∘'RK'        ⍝ Intersection
      q6ii ← {(≠/2|⍸'B'=⍵)∧1=(⍸'R'=⍵)⍸⍵⍳'K'}  ⍝ Interval index
      q6w  ← {(≠/2|⍸'B'=⍵)∧≠/(⍸'K'=⍵)<⍸'R'=⍵} ⍝ Where (similar to mine above)

The last version there is very amenable to Over:

            q6over ← {I←⍸=∘⍵ ⋄ (2|I'B')∧⍥(≠/)'K'<⍥I'R'}

And for masochists, there is always the famous Progressive Dyadic Iota:

      pd ← {((⍴⍺)⍴⍋⍋⍺,⍵)⍺⍺(⍴⍵)⍴⍋⍋⍵,⍺}
      q6pdi ← {(∧/2\</⍵⍳pd'RKR')∧≠/2|⍵⍳pd'BB'}

Problem 7: Can You Feel the Magic?

A square matrix is ‘magic’ if all of its rows and columns and both diagonals sum to the same number.

One hero came up with the following:

      q7 ← (∧/2=/∘∊+/,(+/1 2 2∘⍉))⍉,[0.5]⌽

Here is how it works:

      q7 magic←⎕←3 3⍴4 9 2 3 5 7 8 1 6
4 9 2
3 5 7
8 1 6
1
      q7 nonmagic←⎕←3 3⍴4 9 2 7 5 3 8 1 6
4 9 2
7 5 3
8 1 6
0

The problem statement suggested that dyadic transpose might come in handy, but that’s just showing off! So, how does it work? It’s certainly tacit:

              q7            ⍝ Ouch...
    ┌─────────┴─────────┐
  ┌─┴─┐               ┌─┼─────┐
  / ┌─┼──────┐        ⍉ [0.5] ⌽
┌─┘ 2 ∘    ┌─┼───┐    ┌─┘
∧    ┌┴┐   / , ┌─┴──┐ ,
     / ∊ ┌─┘   /    ∘
   ┌─┘   +   ┌─┘ ┌──┴──┐
   =         +   1 2 2 ⍉

The fork ⍉,[0.5]⌽ takes the argument matrix – a square array of rank-2, shape A A – and returns an array of rank-3, shape 2 A A, where the first cell is the transposed original array and the second is the original array with its rows reversed:

      ]display (⍉,[0.5]⌽) magic
┌┌→────┐
↓↓4 3 8│
││9 5 1│
││2 7 6│
││     │
││2 9 4│
││7 5 3│
││6 1 8│
└└~────┘

We only need to know about the main diagonal of each cell; as you can see, the main diagonal in the second cell is the reverse diagonal of the first cell. We can extract both diagonals with a single dyadic transpose:

      1 2 2⍉(⍉,[0.5]⌽) magic
4 5 6
2 5 8

The same result can be achieved using slightly less showy instead, which has the same byte count but is a little easier to understand when first seen:

      1 1⍉⍤2(⍉,[0.5]⌽) magic ⍝ Diagonals of each major cell love ⍤
4 5 6
2 5 8

The remaining part of the tacit formulation untangles easily. Impressive and creative.

Here’s another good one that is slightly shorter:

      q7 ← (1=≢∘∪)⍉+⌿⍤,⍥(1 1∘⍉,⊢)⌽
      q7 magic
1
      q7 nonmagic
0

How does that work? The phrase 1 1∘⍉,⊢ prepends the diagonal as a column to the argument matrix:

      (1 1∘⍉,⊢)magic ⍝ Explicit: {(1 1⍉⍵),⍵}
4 4 9 2
5 3 5 7
6 8 1 6

Clever application of says “take the matrix, append its reverse over the diagonal-append operation”:

      {⍵,⍥{(1 1⍉⍵),⍵}⌽⍵} magic ⍝ love ⍥
4 4 9 2 2 2 9 4
5 3 5 7 5 7 5 3
6 8 1 6 8 6 1 8

We can emphasise the location of the diagonals by using Partitioned Enclose to make them stand out a bit:

      1 1 0 0 1 1 0 0 ⊂ {⍵,⍥{(1 1⍉⍵),⍵}⌽⍵} magic
┌─┬─────┬─┬─────┐
│4│4 9 2│2│2 9 4│
│5│3 5 7│5│7 5 3│
│6│8 1 6│8│6 1 8│
└─┴─────┴─┴─────┘

Summing along the leading axis gives:

      {+⌿⍵,⍥{(1 1⍉⍵),⍵}⌽⍵} magic
15 15 15 15 15 15 15 15

Finally, check that all items are equal:

      {1=≢∪+⌿⍵,⍥{(1 1⍉⍵),⍵}⌽⍵} magic ⍝ Length of vector of unique values = 1?
1

In summary, there are two things to note here: using to get both diagonals and the use of 1=≢∘∪ to check that all items are equal. If you attended the APL Seeds ’21 conference last March, you’ll recognise this as one of the many ways of solving this problem that Conor Hoekstra presented – see https://dyalog.tv/APLSeeds21/?v=GZuZgCDql6g to watch his presentation.

Any solution that makes use of both of my favourite glyphs ( and ) is a winner in my book.

Problem 8: Time to Make a Difference

Write a function that:

  • has a right argument that is a numeric scalar or vector of length up to 3, representing a number of [[[days] hours] minutes] – a single number represents minutes, a 2-element vector represents hours and minutes, and a 3-element vector represents days, hours, and minutes
  • has a similar left argument, although not necessarily the same length as the right argument
  • returns a single number representing the magnitude of the difference between the arguments in minutes.

Here’s a cool version (several submissions were similar):

      p8 ← |-⍥(1 24 60⊥¯3∘↑)

Nothing too mysterious here. A slight complication is the need to handle a right argument that can be a scalar or a vector of length 2 or 3. The decode function expects the argument vector to always be length 3, so we use the take function, dyadic , with ¯3 as the left argument to ensure that the argument is always a vector of the correct length, padding from the left with zeros as required. The mixed radix vector 1 24 60 as the left argument to decode converts to minutes.

Problem 9: In the Long Run

Write a function that:

  • has a right argument that is a numeric vector of 2 or more elements representing daily prices of a stock
  • returns an integer singleton that represents the highest number of consecutive days where the price increased, decreased, or remained the same, relative to the previous day.

I’d like to compare and contrast two solutions, neither of which are tacit for a change:

      p9a ← {≢⍉↑⊂⍨1,2≠/×2-/⍵}
      p9b ← {⌈/¯2-/0,⍸1,⍨2≠/×2-/⍵} ⍝ Flat efficiency

Starting with the first of the two (p9a), from the right, we use a windowed difference reduction to calculate pairwise differences:

      2-/1 3 5 6 6 6 6 6 3 2 1
¯2 ¯2 ¯1 0 0 0 0 3 1 1

and then apply the direction function, monadic ×, to turn this into a vector of ¯1, 0 and 1 if the corresponding item is negative, zero or positive respectively:

      ×2-/1 3 5 6 6 6 6 6 3 2 1
¯1 ¯1 ¯1 0 0 0 0 1 1 1

Another pairwise windowed reduction, this time with , gives us the points of change:

      2≠/×2-/1 3 5 6 6 6 6 6 3 2 1
0 0 1 0 0 0 1 0 0

Prepending a 1, this Boolean vector can be used as the left argument to partitioned enclose, ; a common pattern. But what of the right argument? We can use the same vector as the right argument by using a clever commute, :

      ⊢m←⊂⍨1,2≠/×2-/1 3 5 6 6 6 6 6 3 2 1 ⍝ Commute to use the same argument left and right
┌─────┬───────┬─────┐
│1 0 0│1 0 0 0│1 0 0│
└─────┴───────┴─────┘

What remains is to find the longest cell in this vector. We could do ⌈/≢¨, but instead this submission found the length of the transpose-mix:

      ≢⍉↑ m
4

A code-golfer’s trick shot, perhaps, and somewhat dubious in terms of efficiency, but certainly cute. If you don’t see why it works, work it through right to left!

The second solution (p9b) uses a lot of the same ideas, but this time we add a 1 to the end of the points-of-change vector:

      {1,⍨2≠/×2-/⍵}1 3 5 6 6 6 6 6 3 2 1
0 0 1 0 0 0 1 0 0 1

and use where, monadic , to get the indices, prepending a 0 so that we can calculate the length of each segment:

      {0,⍸1,⍨2≠/×2-/⍵}1 3 5 6 6 6 6 6 3 2 1
0 3 7 10

The pairwise difference now represents the length of each segment, and by using a negative window we can commute each pair to get a positive number out for each pair:

      {¯2-/0,⍸1,⍨2≠/×2-/⍵}1 3 5 6 6 6 6 6 3 2 1
3 4 3

and so, for the maximum:

      {⌈/¯2-/0,⍸1,⍨2≠/×2-/⍵}1 3 5 6 6 6 6 6 3 2 1
4

Shall we race them? Of course!

      data ← 10000?10000
      cmpx 'p9a data'
  p9a data → 2.7E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  p9b data → 2.1E¯5 | -92% ⎕⎕⎕

The second version is faster for several reasons. We suspected already that the ‘cute’ way to find the longest vector in a nested vector was likely to be slow, as it has to create a huge matrix first, chasing pointers. The second version uses flat numeric vectors throughout, and cuts the work considerably by using where initially to do length calculations on the shorter vector of indices. Flat is fast.

Problem 10: On the Right Side

Write a function that:

  • has a right argument T that is a character scalar, vector or vector of character vectors/scalars
  • has a left argument W that is a positive integer specifying the width of the result
  • returns a right-aligned character array R of shape ((2=|≡T)/≢T),W meaning that R is one of the following:
    • a W-wide vector if T is a simple vector or scalar
    • a W-wide matrix with the same number rows as elements of T if T is a vector of vectors/scalars
  • if an element of T has length greater than W, truncate it after W characters.

The last point is perhaps a bit misleading, but the intention is clear from one of the examples given:

      ⍴⎕←8 (your_function) 'Longer Phrase' 'APL' 'Parade'
r Phrase
     APL
  Parade
3 8

In this case, “truncate after W characters” means “remove from the left”.
Conceptually, we need to (over)take W characters from the right of each element and mix that into a rank-2 array. To make it work for the edge cases, we should ensure that we can always treat the right argument as a vector of character vectors, using nest, monadic . This works because if we take more characters than the vector contains, it gets padded using a character-vector’s prototype element, a space.

            8 {↑(-⍺)↑¨⊆⍵} 'Longer Phrase' 'APL' 'Parade'
r Phrase
     APL
  Parade

An equivalent tacit formulation would be:

            8 (↑-⍤⊣↑¨⊆⍤⊢) 'Longer Phrase' 'APL' 'Parade'
r Phrase
     APL
  Parade

Here’s a slight variation:

            8 {⌽⍉⍺↑⍉↑⌽¨⊆⍵}'Longer Phrase' 'APL' 'Parade'
r Phrase
     APL
  Parade

This starts by reversing each cell, then applies a mix and transpose. We then take items from the left before backing out of the transpose and reverse by applying them again.
It can be done in a flatter manner, too:

            8{⍉(-⍺)↑⍉(⊆⍵)⌽∘↑⍨(⊢-⌈/)≢¨⊆⍵} 'Longer Phrase' 'APL' 'Parade'
r Phrase
     APL
  Parade

If we flip the selfie and add a few spaces it gets a bit easier to see what’s going on:

            8 {⍉(-⍺)↑⍉ ((⊢-⌈/)≢¨⊆⍵) ⌽↑⊆⍵} 'Longer Phrase' 'APL' 'Parade'
r Phrase
     APL
  Parade

From the right, we turn our input into a character array and then Rotate each row by its length minus the length of the longest row, which implements the right alignment:

            {((⊢-⌈/)≢¨⊆⍵) ⌽↑⊆⍵} 'Longer Phrase' 'APL' 'Parade'
Longer Phrase
          APL
       Parade

What remains is the truncation, which follows similar lines to the earlier versions.

For completeness we can race a couple of these variants. Let’s generate a chunkier data set first: 10,000 random strings of varying lengths up to 50:

      data←{⎕A[?(?50)⍴26]}¨⍳10000      'cmpx'⎕CY'dfns'
      cmpx '20{↑(-⍺)↑¨⊆⍵}data' '20{⍉(-⍺)↑⍉(⊆⍵)⌽∘↑⍨(⊢-⌈/)≢¨⊆⍵}data' '20{⌽⍉⍺↑⍉↑⌽¨⊆⍵}data'
  20{↑(-⍺)↑¨⊆⍵}data                 → 9.3E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕             
  20{⍉(-⍺)↑⍉(⊆⍵)⌽∘↑⍨(⊢-⌈/)≢¨⊆⍵}data → 9.0E¯4 |  -3% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕              
  20{⌽⍉⍺↑⍉↑⌽¨⊆⍵}data                → 1.4E¯3 | +46% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

The complex, flat version wins, but not by a significant amount.

With that we’ve reached the end. A nice set of problems, with a lot of creative solutions submitted. Watch this space for a review of the Phase II problems…

Not All Heroes Wear Capes

On Friday 15 October, the SERV S&L was presented with The Queen’s Award for Voluntary Service by the Lord Lieutenant of Surrey. Geoff Streeter was one of 20 volunteer SERV S&L members who attended.

What Is SERV S&L?

SERV S&L (Service by Emergency Rider Volunteers for Surrey and London) are a charity organisation, made up entirely of volunteers, comprising motorbike riders, car drivers, controllers, and fundraisers. They transport blood products, urgent samples, medical supplies, and donated breast milk to hospitals and milk banks across Surrey & London, as well as carrying out a daily delivery of blood to the Air Ambulance service that covers Kent, Surrey, and Sussex. They support the regular delivery rounds that the NHSBT (National Health Service Blood and Transport) have in place; unlike the NHSBT, SERV S&L also operate throughout the night. All of this is provided free of charge to the NHS, releasing more money for patient care.

What Is The Queen’s Award for Voluntary Service?

QAVS (The Queen’s Award for Voluntary Service) celebrates the outstanding work of local volunteer groups across the UK. Created in 2002 for Queen Elizabeth II’s Golden Jubilee, QAVS awards shine a light on the fantastic work of voluntary groups. QAVS awards are the highest awards given to local voluntary groups in the U.K. (they are the equivalent of a personal MBE) and they are awarded for life.

Geoff’s Involvement with SERV S&L

A Personal Recollection

At the end of 1980, Paul McCann had a relation who could not get an urgent sample transported to the testing lab until the next morning. He was frustrated by this and organised a meeting to see what could be done, the result of which was that a group of advanced motor cycle trainers from a (now defunct) group called Star Rider decided to try to run a delivery service for blood/samples at night. I was not at that meeting but I heard about it from a fellow member of the Laverda Owners group; I made it to the second meeting (on 8 December 1980) and have been involved ever since. We obtained a room with a couple of bunks in a wooden building owned by MEFAS (Malden Emergency First Aid Society) and a telephone line, and started operating in early 1981.

The main distribution point for blood is located in Tooting and serves London, Kent, Surrey and Sussex (we have partner organisations in Kent, Sussex and Wessex). We do a main nightly run with typically 6 to 10 boxes down to an arranged change point for Kent and Sussex. We also partner with similar organisations across the U.K., and have occasional relay runs, for example, from Edinburgh to central London (I think that’s the longest that we’ve been involved in). More common are runs from Bristol. We typically shift 20 boxes a night and samples in the other direction and have about 8 riders/drivers on shift every night.

Financially, we get support from some Masonic Lodges and business groups. They prefer to buy bikes for us, and Citroen have given us a car (DS3) on permanent loan. We are in the process of acquiring/refurbishing a scout facility in Sutton to provide a base for the bikes/cars/van as well as for volunteers who live on the periphery of the area. We also raise funds by box waving outside supermarkets, garden centres, Brooklands, Waterloo Station, etc.

I started with the group as a biker, and used my Laverda 750, Laverda 1200 and Honda 650 Turbo to deliver blood and samples from 1981 until 1990, when I switched to car deliveries (which I continued to do until last year). I also acted as Treasurer from 2006 until 2010. I have been one of the controllers right from the start [Ed.: Controllers orchestrate the logistics of a shift; hospitals and partner groups place their orders and riders and drivers are dispatched as required – accurate scheduling and data logging are required to ensure efficient co-ordination and communication so that each run can be completed reliably], a role that has changed a lot over the last 40 years. In the early days controllers needed to be physically present with the one rider and the telephone. Then we moved to using pagers (but still needed to be present in the hut/sports centre) before everything changed with the advent of mobile phones – I now control from home. The expectation is that volunteers do one night a fortnight, but a shortage of volunteers relative to growing demand means that for a few years now I have been doing at least one shift a week.

Final Word

Congratulations Geoff, 40 years of volunteering for such a worthy cause is a fantastic achievement. All of us at Dyalog Ltd are really proud of your contribution.

To find out more about the amazing service provided by SERV S&L, including how to make a donation, visit https://servsl.org.uk/.

Announcing the Beta Programme for Dyalog APL Version 18.2


I am very pleased to be able to announce the start of the Beta testing of the next release of Dyalog APL! As explained in June, we decided to delay the release of version 18.1 in order to take a closer look at some of the optimisations that had been implemented in 18.0 (and were therefore also present in 18.1).

Our analysis of the optimised code concluded that, due to the nature of many of the new algorithms involving modern vector instructions and code generated from templates, we need significantly more time to create tests that will cover absolutely all the different cases that have been implemented. As a result, we do not feel that it is in the best interests of our users to release v18.1 in its current form.

The good news is that the features of modern source code management systems, combined with our collection of regression tests, have allowed us to create a new version of Dyalog APL that contains all of the new features added to versions 18.0 and 18.1. This includes bug fixes made during these two development cycles, but not the optimisations that make us feel uncomfortable. To differentiate this version from the existing version 18.1, we have decided to call the new version 18.2.

Everyone who was signed up for the v18.1 beta programme should now be able to download v18.2 beta. If you are not signed up as a beta tester already but would like to help us with testing, please get in touch. Under Microsoft Windows, testing should be significantly simpler this year, as we have started producing Microsoft Patch files (MSP) as the delivery mechanism for updates – something I have personally been looking forward to since before I joined Dyalog Ltd!

Version 18.2 Performance

One unavoidable consequence of the above is that the performance of v18.2 is closer to that of v17.1 than to v18.0. Our own tests show that we have not been pushed ALL the way back to “square one”: v18.2 appears to be slightly faster than version 17.1. Once v18.2 has been delivered we will work on carefully re-implementing the most valuable optimisations that have been removed. We welcome your input on which primitives you think we should speed up first, so please participate in testing v18.2 and let us know what you think we should prioritise as we start work on version 19.0!

Recommendations regarding Version 18.0

Over the summer, only one additional defect related to performance optimisation was discovered and fixed. We are not currently aware of any outstanding defects in v18.0 caused by recent optimisations. Dyalog Ltd is committed to providing support for version 18.0 until the arrival of the 3rd release following it, in accordance with normal policy.

However, if you have not yet upgraded to v18.0, Dyalog Ltd strongly recommends remaining on your current version and moving directly to v18.2 when it is released. If all goes well, this will happen at the end of 2021 or very early in 2022. If you are already using v18.0, then we recommend that you make plans to start evaluating v18.2 and moving to it as soon as possible.

Conclusion – and Apology

We are painfully aware that the defects found in v18.0 and the resulting uncertainty have seriously inconvenienced some of our users, and I apologise for this. The root cause is the growth and rejuvenation of the Dyalog development team. Our original processes for quality assurance relied on years of tacit knowledge; when enthusiastic new team members break significant new ground, more explicit planning and QA processes are required to make sure that new approaches are safe and stable.

When we resume work on optimisations following the release of v18.2, this will be done according to new guidelines that require the process to begin with a careful risk/benefit analysis of any enhancement to primitive functions. We will do everything that we can to move forward in a way that will allow us all to eventually look back on the events of 2021 as a significant step towards a more capable and reliable development organisation and product.

After all, in another two years it will be time to celebrate 40 years of Dyalog APL!

Essays on APL Since 1978

In June, Mikhail Barash and Anya Helene Bagge published a collection of essays written by the students of the seminar course INF328B on History of Programming Languages that was given at the University of Bergen (Norway) in the Spring term 2021. As an author, I wish to start by thanking Mikhail and Anya and the students for this initiative! It is inspiring to those of us who have been in this game for a while to see young computer scientists who are interested in language design studying history – it definitely makes us feel that the effort put in to writing the paper was worthwhile!

Each essay summarised one paper from the HOPL IV conference (part of ACM SIGPLAN’s PLDI 2021). Two students wrote essays on the paper “APL Since 1978”, by Roger Hui and myself. At the end of each essay, students were encouraged to pose questions to the authors of the HOPL IV papers, and this blog post has essentially been written in response to those questions.

Karl Henrik Elg Barlinn asks:
“I wish to know if there are plans to try and popularize APL within the wider community of programming languages. I ask this because I see how it can be very useful for the mathematical community to write papers and be able to execute the notation.”

The APL community has always seen “evangelism” as an important activity, and that remains true to this day. It is a challenging task because the most successful APL users are neither software engineers nor mainstream mathematicians, but various types of domain experts who are able to apply mathematics and learned enough about programming to write high value applications with a lot of domain-specific content. Typical users have been actuaries and financial experts, operations researchers and planners.

Successful APL users are more likely to write papers at an Actuarial or Chemical Engineering conference, and typically lack the vocabulary and the insight into mainstream computer science to present APL to the “community of programming languages”. They also typically work in highly competitive industries and have little time or inclination (or permission) to publish their work.

The situation is improving: the growing interest in functional programming, and the general recognition by the software engineering community that there is value in combining different paradigms (as opposed to the bad old days when everyone thought that the world would soon standardise on C++ or Java), makes it much easier to interest the new generation in APL.

A new generation of APL users is emerging, who have more insight into Computer Science and are more able to bridge the gap. Examples of recent work include:

Dyalog Ltd recently introduced an event aimed at new users; recordings from the first of these meetings can be found at https://www.dyalog.com/apl-seeds-user-meetings/aplseeds21.htm.

In addition to the marketing efforts, Dyalog is working hard to add tooling that will open APL interpreters up to mainstream “devops” workflows, based on text-based source files. Historically, most big APL shops developed their own home-grown management systems (many of them pre-dating tools like SVN or Git by decades), and there has not been a lot of tooling shared by the community.

“Given unlimited influence, where do you wish to see APL be used? If your answer is everywhere, does that mean APL is fit to do everything? On the other hand if your answer is not everywhere, where is not fit to be used and why?”

Given unlimited influence, I would push APL as a tool for education. I think it could be a useful tool for teaching mathematics – and how to use it to solve problems on a computer – starting with children. The simplicity of APL’s syntax means that it is also a good tool for teaching people of all ages and at all levels of education to manipulate data without just feeding it to ready-made packages. Teaching fundamental algorithms in computer science classes is also a good place to use APL, although the CS establishment will probably question that since APL tries to do most things without loops or type declarations, and sort of “skips over” the lowest level of algorithms.

APL is a useful tool for modelling, prototyping and designing solutions to any kind of problem. Obviously, many domains already have tools specifically designed for common types of problems. For example, Mathematica and MatLab have built-in solutions for many different classes of mathematical or engineering problems, TensorFlow for artificial neural networks, and so on. However, when the time comes to perform a major revision or extension, or there are no pre-built solutions, APL will be a good choice for prototyping.

Although APL is perhaps most valuable during analysis and design, the “executable design” is often used in production because APL interpreters are efficient on the relatively dense data structures that results from array orientation and because the ability of domain experts to write code (and tests) eliminates many sources of errors and poor performance due to unnecessary abstractions.

APL is not always an appropriate choice for the final production system. For example, I would not use APL to implement a real-time system, at least not using existing APL interpreters, which will freeze up to do compactions every now and again. For mission-critical systems, the additional safety provided by strong typing or other mechanisms for verifying correctness, and using teams trained to focus on reliability rather than analytics, may have benefits. If the core algorithms are not array-oriented and require a lot of looping or recursion, an interpreter may not be the right solution, and APL compilers are not yet mature technologies.

Even when the final production system is rewritten in another language, the prototype can be useful as a verification system, especially because the implementation is likely to be radically different, and can therefore almost act as a proof of correctness.

For an example of how APL can add significant value even when it is not used in the final implementation, see Martin Janiczek’s presentation at APLSeeds21, on “How an APL Prototype Helped Designing a Service”: https://dyalog.tv/APLSeeds21/?v=qDl3obmOd58.

“Q: Do you think APL with its glyphs is more fit to be taught in school than J, as special equipment is no longer an issue with UTF being widely adopted?”

There are still some problems related to APL symbols, such as many applications rendering the symbol incorrectly as a followed by a slightly offset / unless a supporting font is used. I suspect that it may be a while before we have handwriting recognition for APL symbols, or support for APL in writing systems for the visually impaired, and so on. On the other hand, one of the benefits of APL (which also holds true for J) is that it is independent of any particular human language, without needing to be translated from English.

Roger Hui commented in the HOPL IV Slack channel: “I am guessing that if the ecosystem for Unicode was more developed at the time (1990) Iverson would have kept the APL glyphs.”

Sondre Nilsen comments:
“If I would have some feedback it’d be to include an “array programming languages for dummies” appendix that could be used to look up foreign concepts, words and phrases that unfamiliar aspiring APL developers may not know.”

Hopefully the APL Wiki (https://apl.wiki) will be a useful resource, along with the (APLCart https://aplcart.info) and the evolving digital version of Mastering Dyalog APL. Please take a look at let us know if you feel more is required!


Roger and Morten’s HOPL IV paper “APL Since 1978”:

Welcome Karta Kooner

Karta joined Dyalog in April, and is yet to meet anybody in person although he’s been told that this is not necessarily a bad thing! After completing his doctoral degree in theoretical physics, Karta stumbled upon Dyalog and APL entirely by happenstance. Being often captivated by things that look unfamiliar to him, and having an interest in most things, it was a code golf question that was answered in a strange, yet mathematical-looking language that took him to the profile of the poster, who happened to mention they were employed by Dyalog and currently hiring. He sent an email enquiring about the opportunity and, several remote interviews later, was happy to be hired as a C/C++ developer working on the interpreter.

Karta is one of the few members of the team that knew no APL whatsoever before joining and has been very impressed by Dyalog and APL thus far; he is very much looking forward to seeing how far the language can be taken, with an eye to further developing and potentially encouraging its use in academia and other technical fields of study.

In his spare time, Karta enjoys expanding his knowledge of both scientific and technical pursuits, and tinkering around with software and hardware systems, amongst his eclectic interests. When not found reading papers or learning an unfamiliar branch of mathematics, he will be caught thinking of a new engineering project to occupy his time, or stumbling through learning a new language, or maybe just delighting in the latest vixra paper.

Thank You Ian Sharp

On July 16th, one of the most influential founders of what we today refer to as the “array language community” died peacefully, a few months after being diagnosed with lung cancer (link: Toronto Globe and Mail).

Ian Patrick Sharp

In 1964, Ian Patrick Sharp formed I.P.Sharp Associates (IPSA), together with six colleagues who were made redundant when Ferranti-Packard closed its computer division in Toronto, Canada. As Ian explains in a wonderful interview that was recorded in 1984 (link: Snake Island website), he was approached by people who wanted to recruit the whole team. Instead, he decided to form a company, since the team obviously had significant value.

The company was involved in the first APL implementation at IBM (APL\360). Subsequently, IBM allowed them to modify and enhance the system, and built a timesharing service that became known as SHARP APL. Roger Moore was a co-founder of IPSA and, in addition to being responsible for the supervisor that made SHARP APL a superior timesharing system, Roger was the chief architect of IPSANET, one of the worlds first packet switched networks.

In the late 1970s the combination of APL and IPSANET was revolutionary, and IPSA quickly attracted business from global corporate clients who used SHARP APL for e-mail, reporting and analytics, and a rapidly-growing collection of financial timeseries data – all completely new technologies at the time. In particular, the transmission of data over telephone lines changed the world. Ian had many absurd encounters with telecom monopolies who tried to protect old business models or profit from the new technology (link: archive.org).

A Stylised Map of the I.P.Sharp Associates APL Time-Sharing Network

Ian’s management style perfectly matched – and drove – the revolutionary technologies. As Ian explains so eloquently and humorously in the interview, IPSA recruited talented people without necessarily having specific tasks in mind. Ian set the tone and direction and then let people get on with it, moving around in the background to get a sense of how things were going and making adjustments without ever making a fuss. IPSA was a fantastic place to work and attracted a wonderfully diverse (in the most modern sense of the word) collection of smart people who developed revolutionary tools, helped a lot of customers, had a lot of fun, and made money.

Ultimately, IPSA was creative, problem-oriented and customer-driven to the extent that it failed to respond to fundamental changes in the market in time. At the end of the 1980s the timesharing revenues suddenly faded, and the company was acquired by Reuters for its timeseries databases and more or less disappeared overnight. However, IPSA had acted as a fantastic breeding ground for technology and talent for a quarter century, and there are hundreds of people who fondly and gratefully remember Ian for the way that he allowed them all to grow.

I don’t think it is a coincidence that so many of the active array language organisations have key players who were once IPSA employees (some of them appearing in more than one place thanks to relationships forged a very long time ago ?).

  • Jsoftware: Roger Hui, Eric Iverson, Chris Burke, Ken Iverson
  • Kx: Arthur Whitney, Simon Garland, Stephen Taylor, Chris Burke
  • Dyalog: Gitte Christensen, Morten Kromberg, Roger Hui, Brian Becker, Dan Baronet
  • Snake Island Research: Robert Bernecky

As always, Roger has collected anecdotes about IPSA, Ian and other people who worked there, which you can find on jsoftware.com/papers/SharpQA.htm.

My Own IPSA Story

In 1978, my dad was moving out of an apartment in Oslo. At the same time, XEROX insisted that IPSA open an office in Oslo to support their international business, and several Canadians arrived there. I helped move some furniture and, sensing a keen interest and real excitement in programming, the IPSA Oslo team offered me a free account to play with APL timesharing, if I was interested. I effectively became a piece of furniture in the IPSA office after school, and had keys to the office so I could come and go as I pleased. After a year or so, they started throwing me bits of real work to do and paying me for my time. I think I was 17 at the time.

In addition to working as an APL consultant and tool builder, one of the things I did in my spare time was to write a tool for myself that would compare the entire contents of the e-mail directory with its state at the end of the previous week. Since IPSA was 100% managed by e-mail groups, this allowed me to know instantly when a new office was opened, a significant new project was started, and, of course, when new employees joined the company. By using this technique of harvesting e-mail addresses and sending unsolicited e-mail when an interesting project or person joined, I found my future partner both at home and the office – Gitte, the current CEO of Dyalog Ltd – only about 500km away in the IPSA Copenhagen branch.

I spent about a decade at IPSA and, after its sudden disappearance, Gitte and I have been trying to recreate the IPSA atmosphere in every team that we have been a member of. In a very real sense, I owe not only my career but almost everything of value about my life to Ian Sharp and the warm and welcoming company that he created.

Thank You, Ian!