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:

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

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!

Code Golf: Generating Empty Arrays

By: Stefan Kruger

Recently, I was looking for a Dyalog problem to pit my wits against, and I asked in the APL Orchard if AdΓ‘m could make one up:

A CMC, if you’re unfamiliar with the APL Orchard, is a Chat Mini Challenge – typically an informal code golf challenge to produce the shortest possible bit of code that solves the set problem. Code golf practitioners usually delve into the dustiest corners of a language and, if practiced diligently, this can lead to a deep mastery over time, even if some dirty hacks techniques employed may be frowned upon in production code.

Anyway. AdΓ‘m responded with the following:

The Mysterious Case of 0 0⍴0

Hmm. What even is that thingβ€½ It’s only 5 characters already – not much scope to shrink that, surely? Let’s have a look at it with full boxing:

      ]Box on -style=max
β”‚Was ON -style=maxβ”‚
      0 0⍴0

In the boxed output, the ⌽ tells us that the leading axis has length 0, the βŠ– means that the trailing axis has length 0, and the ~ means that the array is non-nested.

This is a simple numeric array of two dimensions, each of length 0 – think of it as a spreadsheet or table before you’ve put any rows or columns of data in it.

I found this problem difficult to get started with, so I searched for the expression on APL Cart, and discovered that:

      ]Box off
Was ON
      ]APLCart 0 0⍴0   ⍝ Dyalog 18.1 has APLCart built in! Fancy.
X,Y,Z:any M,N:num I,J:int A,B:Bool C,D:char f,g,h:fn ax:axis s:scal v:vec m:mat
⍬⊀⍬  zero-by-zero numeric matrix                                               
Showing 1 of 1 matches                                                         
      ]Box on
β”‚Was OFFβ”‚

Surely not? Let’s try that suggestion:

      (0 0⍴0)β‰‘β¬βŠ€β¬

Well, it clearly works, but why? Let’s see if we can figure that one out.

In the basic case for encode, X⊀Y, if X and Y are vectors, the result will have one column for each element in Y and one row for each element in X. Using the example from the language bar:

      2 2 2 2 ⊀ 5 7 12 ⍝ Convert decimal to binary
↓0 0 1β”‚
β”‚1 1 1β”‚
β”‚0 1 0β”‚
β”‚1 1 0β”‚

we have a shape of 4 3, as the length of the vector to the left (2 2 2 2) is 4 and the length of the vector to the right (5 7 12) is 3.

Returning to ⍬⊀⍬, given the above, we can deduce that the result should have a rank of 2 with a shape of 0 0 which, of course, is what we wanted to achieve:

      ⍴⍬⊀⍬ ⍝ Shape 0 0
β”‚0 0β”‚

Disappointingly, I had to cheat by looking up the answer. However, are there any more length-3 solutions? Apparently, ⍬⊀⍬ is “reasonably well known”. I decided to write a simple brute-force search function to look for any other solutions.

This works as follows:

  1. Create all possible length-3 combinations of APL glyphs
  2. Evaluate each in turn, skipping those that error
  3. Save those that evaluate to 0 0⍴0

Here’s what I ended up with:

βˆ‡ r←Bruter target;glyphs;combo;eval 
  glyphs ← '0⍬+-Γ—Γ·*βŸβŒΉβ—‹|⌈⌊βŠ₯⊀⊣⊒=≠≀<>β‰₯β‰‘β‰’βˆ¨βˆ§β²β±β†‘β†“βŠ‚βŠƒβŠ†βŒ·β‹β’β³βΈβˆŠβ·βˆͺ∩~/\βŒΏβ€,βͺβ΄βŒ½βŠ–β‰Β¨β¨β£.∘⍀β₯@βŒΈβŒΊβŽβ•Β―'
  r ← ⍬
  :For combo :In ,∘.,⍣2⍨glyphs
      :Trap 0
          eval ← ⍎combo
      :If eval≑target
          r ,← βŠ‚combo

I decided to leave out a few glyphs that I guessed would be unlikely to feature (β†β†’βŽ•β βžββ‹„), and I only added the number 0. Let’s see what that generates:

      7 5⍴Bruter 0 0⍴0 ⍝ 7Γ—5 layout added for clarity after the fact
↓ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚β¬βŠ€β¬β”‚ β”‚+βŒΈβ¬β”‚ β”‚-βŒΈβ¬β”‚ β”‚Γ—βŒΈβ¬β”‚ β”‚Γ·βŒΈβ¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚*βŒΈβ¬β”‚ β”‚βŸβŒΈβ¬β”‚ β”‚β—‹βŒΈβ¬β”‚ β”‚|βŒΈβ¬β”‚ β”‚βŒˆβŒΈβ¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚βŒŠβŒΈβ¬β”‚ β”‚βŠ€β¨β¬β”‚ β”‚βŠ€βŒΈβ¬β”‚ β”‚βŠ’βŒΈβ¬β”‚ β”‚=βŒΈβ¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚β‰ βŒΈβ¬β”‚ β”‚β‰€βŒΈβ¬β”‚ β”‚<βŒΈβ¬β”‚ β”‚>βŒΈβ¬β”‚ β”‚β‰₯βŒΈβ¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚βˆ¨βŒΈβ¬β”‚ β”‚βˆ§βŒΈβ¬β”‚ β”‚β²βŒΈβ¬β”‚ β”‚β±βŒΈβ¬β”‚ │↑⍸0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚β†‘βŒΈβ¬β”‚ β”‚β†“βŒΈβ¬β”‚ β”‚β·βŒΈβ¬β”‚ β”‚βˆ©βŒΈβ¬β”‚ β”‚/βŒΈβ¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚βŒΏβŒΈβ¬β”‚ β”‚β΄βŒΈβ¬β”‚ β”‚βŒ½βŒΈβ¬β”‚ β”‚βŠ–βŒΈβ¬β”‚ β”‚β‰βŒΈβ¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚

Wow! There are 35 of them (for βŽ•IO←0)!

There are clearly patterns here – we can see our friend ⍬⊀⍬ right at the beginning, and also its equivalent ⊀⍨⍬. We can also see ↑⍸0 which, in retrospect, perhaps I should have thought of in the first place.

The remaining 32 solutions all feature key. The majority of those have a scalar function operand; we can treat this whole group as equivalent. Let’s tackle that group first, with the operand + as the example:


Let’s recap what key does. The operand dyadic function is called with each unique element of the argument in turn as its left argument, and a vector of indices of occurrences as its right. Key then returns a rank 2 array of the results. For example:

      {⍺ ⍡}⌸'Mississippi'
↓   β”Œβ†’β”        β”‚
β”‚ M β”‚1β”‚        β”‚
β”‚ - β””~β”˜        β”‚
β”‚   β”Œβ†’β”€β”€β”€β”€β”€β”€β”€β” β”‚
β”‚ i β”‚2 5 8 11β”‚ β”‚
β”‚ - β””~β”€β”€β”€β”€β”€β”€β”€β”˜ β”‚
β”‚   β”Œβ†’β”€β”€β”€β”€β”€β”€β”  β”‚
β”‚ s β”‚3 4 6 7β”‚  β”‚
β”‚ - β””~β”€β”€β”€β”€β”€β”€β”˜  β”‚
β”‚   β”Œβ†’β”€β”€β”€β”     β”‚
β”‚ p β”‚9 10β”‚     β”‚
β”‚ - β””~β”€β”€β”€β”˜     β”‚

With an argument of the empty vector ⍬, in the operand function, ⍺ will always be 0 – the prototype element of our empty numeric vector:


What about ⍡? Well, it must be an empty numeric vector (no found indices):


So, with a scalar function like + as the operand, we end up with 0+⍬. Key returns an array where each major cell is the result of the function applied to the unique element and its indices, which in this case is an array with major cells of the structure ⍬. How many such major cells? 0. So the result is 0⌿1 0⍴⍬, which is, of course, 0 0⍴0.

So for 0 f ⍬ for any scalar dyadic function f, the above holds. For example:


Then we have a lot of non-scalar operands, like βŠ–/⍷↑↓. All we need to understand is why they produce ⍬ when applied as 0 f ⍬, as key will call them. Some of these are pretty obvious, like find, ⍷:

      0⍷⍬ ⍝ Find all locations of 0 in the empty vector

or take and drop, ↑↓:

      0↑⍬ ⍝ Take no elements from the beginning of the empty vector
      0↓⍬ ⍝ Drop no elements from the end of the empty vector

However, ⍉ gives us a dyadic transpose – and, perhaps unexpectedly, this one is βŽ•IO-dependent:


At first glance, this made no sense to me. The reason this works is that transposing a vector is an identity operation:

      ⍉'Transposing a vector returns the vector'
β”‚Transposing a vector returns the vectorβ”‚

A vector has a single axis, so “reordering the axes” doesn’t do anything. The same holds true for the dyadic form, assuming the left argument is βŽ•IO:

      0⍉'Same for the dyadic form. Sometimes.'
β”‚Same for the dyadic form. Sometimes.β”‚

This is the reason why this only works for βŽ•IO←0: Key always provides 0 for the left argument. For βŽ•IO←1 we will get a DOMAIN ERROR:

      0⍉'Same for the dyadic form. Sometimes.'
      0⍉'Same for the dyadic form. Sometimes.'

A few others stand out. Replicate (and its sibling replicate-first), for example:


will end up as:

      0/⍬ ⍝ zero empty vectors

in the left operand – zero empty vectors is still the empty vector. Reshape is similar:

      0⍴⍬ ⍝ zero empty vectors

Encode tries to express ⍬ in the 0 radix; also an empty vector:


My favourite, though, is probably ↑⍸0, and, as I said earlier, I’m a bit disappointed I didn’t find that before resorting to brute force and ignorance. Where (⍸) returns a vector of indices with 1 for its Boolean array right argument. If we call it with a right argument of 0, we’ll get an empty vector of empty numeric vectors. This is because the one (and only) valid index into a scalar is the empty vector, and none of them (!) are non-zero.

β”‚ β”ŒβŠ–β” β”‚
β”‚ β”‚0β”‚ β”‚
β”‚ β””~β”˜ β”‚

Trading depth for rank, we get the shape we want:


What About 0β΄βŠ‚β¬?

The expression ⍸0 above is the only length-2 way to produce an empty vector of empty numeric vectors:


However, there are several interesting length-3 solutions. Deploying the Bruter again:

      8 7⍴res←Bruter 0β΄βŠ‚β¬
↓ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚0βŠ‚0β”‚ β”‚0βŠ‚β¬β”‚ β”‚0βŠ†β¬β”‚ β”‚β¬βŠ‚0β”‚ β”‚β¬βŠ‚β¬β”‚ β”‚β¬βŠ†β¬β”‚ β”‚+⍸0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚-⍸0β”‚ │×⍸0β”‚ │÷⍸0β”‚ β”‚*⍸0β”‚ β”‚βŸβΈ0β”‚ │○⍸0β”‚ β”‚|⍸0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚βŒˆβΈ0β”‚ β”‚βŒŠβΈ0β”‚ β”‚βŠ£βΈ0β”‚ β”‚βŠ’βΈ0β”‚ β”‚βŠ‚β¨0β”‚ β”‚βŠ‚β¨β¬β”‚ β”‚βŠ†βΈ0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚βŠ†β¨β¬β”‚ β”‚βŒ·βΈ0β”‚ │⍳¨⍬│ │⍸00β”‚ │⍸0.β”‚ │⍸+0β”‚ │⍸-0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ │⍸×0β”‚ │⍸○0β”‚ │⍸|0β”‚ β”‚βΈβŒˆ0β”‚ β”‚βΈβŒŠ0β”‚ β”‚βΈβŠ£0β”‚ β”‚βΈβŠ’0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ │⍸≑0β”‚ │⍸≒⍬│ │⍸↑0β”‚ │⍸↓0β”‚ β”‚βΈβŠ‚0β”‚ β”‚βΈβŠƒ0β”‚ β”‚βΈβŠƒβ¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚βΈβŠ†0β”‚ β”‚βΈβŒ·0β”‚ β”‚βΈβŒ½0β”‚ β”‚βΈβŠ–0β”‚ │⍸⍉0β”‚ │⍸.0β”‚ │⍸¯0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚βˆͺ⍸0β”‚ β”‚~⍸0β”‚ β”‚,⍸0β”‚ │⍴¨⍬│ β”‚βŒ½βΈ0β”‚ β”‚βŠ–βΈ0β”‚ │⍉⍸0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚

Most are ⍸0 combined with an additional primitive that has no effect, or selfie-mirrors, so let’s restrict ourselves to the interesting subset:

      4 2⍴res/⍨~'⍸⍨'∘(∨/∊)¨res ⍝ Skip variants of ⍸0 and selfies
↓ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚0βŠ‚0β”‚ β”‚0βŠ‚β¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚0βŠ†β¬β”‚ β”‚β¬βŠ‚0β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ β”‚β¬βŠ‚β¬β”‚ β”‚β¬βŠ†β¬β”‚ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚
β”‚ β”Œβ†’β”€β”€β” β”Œβ†’β”€β”€β” β”‚
β”‚ │⍳¨⍬│ │⍴¨⍬│ β”‚
β”‚ β””β”€β”€β”€β”˜ β””β”€β”€β”€β”˜ β”‚

We can see a few patterns again – partition (βŠ†) or partitioned enclose (βŠ‚), with 0 as left or right argument and ⍬ as left or right argument, plus two variants using each (Β¨) on ⍬. Let’s look at βŠ‚ first.

Partitioned enclose groups, or partitions, stretches its right argument as specified by its Boolean vector left argument, with each new partition starting on 1, and returns a nested vector of the resulting partitions:

      1 0 0 0 0 1 1 0 0 0 0βŠ‚'Hello World'
β”‚ β”Œβ†’β”€β”€β”€β”€β” β”Œβ†’β” β”Œβ†’β”€β”€β”€β”€β” β”‚
β”‚ β”‚Helloβ”‚ β”‚ β”‚ β”‚Worldβ”‚ β”‚
β”‚ β””β”€β”€β”€β”€β”€β”˜ β””β”€β”˜ β””β”€β”€β”€β”€β”€β”˜ β”‚

In the first case, 0βŠ‚0, we’re saying that we want 0 partitions of 0 (which gets treated as a 1-element vector), returned as a nested vector – in other words, exactly the “empty vector of empty numeric vectors” that we’re after. In fact, βŠ‚ with a 0 as its left argument returns an empty vector of empty vectors of the prototype element of the right, which also helps to explain our 0βŠ‚β¬:

      0βŠ‚'hello world' ⍝ Empty vector of empty character vectors
β”‚ β”ŒβŠ–β” β”‚
β”‚ β”‚ β”‚ β”‚
β”‚ β””β”€β”˜ β”‚
      0βŠ‚1 2 3 4 5 ⍝ Empty vector of empty numeric vectors
β”‚ β”ŒβŠ–β” β”‚
β”‚ β”‚0β”‚ β”‚
β”‚ β””~β”˜ β”‚
      0βŠ‚β¬ ⍝ Empty vector of empty numeric vectors
β”‚ β”ŒβŠ–β” β”‚
β”‚ β”‚0β”‚ β”‚
β”‚ β””~β”˜ β”‚

Swapping the order of that last expression:

β”‚ β”ŒβŠ–β” β”‚
β”‚ β”‚0β”‚ β”‚
β”‚ β””~β”˜ β”‚

is really the same thing: the left side is still a numeric vector with no 1s.

What about βŠ†? If we restrict ourselves to a Boolean left argument again, partition is similar to replicate, but instead of just skipping elements of the right side corresponding to 0s in the left side, it encloses groups of elements corresponding to 1s, and skips the rest:

      1 1 1 1 1 0 1 1 1 1 1βŠ†'Hello World'
β”‚ β”Œβ†’β”€β”€β”€β”€β” β”Œβ†’β”€β”€β”€β”€β” β”‚
β”‚ β”‚Helloβ”‚ β”‚Worldβ”‚ β”‚
β”‚ β””β”€β”€β”€β”€β”€β”˜ β””β”€β”€β”€β”€β”€β”˜ β”‚

Compare with replicate:

      1 1 1 1 1 0 1 1 1 1 1/'Hello World'

As with βŠ‚, βŠ† returns a vector of vectors and, by the same reasoning, if the left argument contains no 1s, then the inner vector will be an empty vector of the prototype element of the right argument:

      0βŠ†1 2 23 34 
β”‚ β”ŒβŠ–β” β”‚
β”‚ β”‚0β”‚ β”‚
β”‚ β””~β”˜ β”‚

We should understand the remaining βŠ† variant, β¬βŠ†β¬, too. You might wonder why there is no 0βŠ†0, analogous to the 0βŠ‚0 we saw earlier; a fair question. However, it results in an error:

      0βŠ†0 ⍝ RANK ERROR
      0βŠ†0 ⍝ RANK ERROR

The reason for this is that βŠ† is IBM’s APL2 primitive, supplied for compatibility reasons. It simply doesn’t treat a scalar right argument as a 1-element vector, unlike βŠ‚.

What remains are the two variants using the each operator: ⍳¨⍬ and ⍴¨⍬. Each always returns an array of the same shape as its right argument, in which each element is the result of applying the operand to the corresponding element in the argument.

By that reasoning, with an argument of ⍬ we’ll always end up with an empty vector. The prototype element is itself a vector, as both ⍳ and ⍴ returns vectors – and, in our specific case, empty numeric vectors, as given the argument ⍬.

Closing Remark

Many people – certainly including myself – find reasoning about the behaviour of empty arrays in Dyalog APL difficult. Going through exercises such as these can help to make this clearer.

News and Recommendations Regarding Dyalog Versions 17.1, 18.0 and 18.1


Dyalog version 18.0 contained the largest number of optimised algorithms in the history of Dyalog APL. Unfortunately, since its release, we have found that our process for review and testing of optimisations was insufficient to cope with the quantity and nature of the optimisations. Many of the new algorithms had edge cases that escaped both the existing regression tests and the new tests that were written as part of development.

In August 2020, after the issues were reported following the release of Dyalog version 18.0, we issued a caution against the use of version 18.0 in production. We added significant additional testing during September and October, and subsequently lifted the caution in November. In April 2021, a user encountered an additional defect leading to incorrect results in a rare case of membership (∊), and in June a crash in an extremely rare case of “where” (monadic ⍸). Since then, our own internal testing has found a defect in interval index (dyadic ⍸).

Current Status

We have made patches available as defects have been detected and fixed, and “Issue 4” of version 18.0, made available to all users on 22 June 2021, includes fixes for all known issues with optimised code.

Download Dyalog version 18.0 Issue 4: Commercial users  Non-commercial users

At this time, we are executing two high priority projects, one aimed at increasing safety in the short term, the other at completely eliminating problematic optimisations within a few months:

  • We have further increased our internal testing of version 18.0, to verify the correctness of the optimisations that are still in the distributed product.
  • We are holding back the release of version 18.1, which was originally scheduled for release this month, while we remove most of the optimisations that went into version 18.0. We hope to release version 18.1 before the end of the 3rd Quarter of 2021, but will not let it out the door until we have complete confidence in this new version.


Dyalog Ltd recommends that users of Dyalog APL take the following action:

  • If you are using version 17.1 or earlier, plan to skip version 18.0 and upgrade directly to version 18.1 when it becomes available.
  • If you are using version 18.0, apply the latest patches or reinstall using Issue 4 when it becomes available. Continue to monitor our DSS e-mail broadcasts and apply patches quickly if we should find and fix any further issues that you think might impact your application. When version 18.1 becomes available, plan to upgrade to it at your earliest convenience.

Support for Versions 17.1 and 18.0

Considering this extraordinary situation, we have decided to extend support for version 17.1 for one additional release cycle. In other words, version 17.1 will be supported until we release the 4th subsequent version of Dyalog APL. Note that we are about to provide an updated version 17.1 installer (“Issue 3”) which collects all updates to version 17.1 since the original release.

Version 18.0 will be supported for the normal number of cycles, that is, until we release the 3rd following version. However, Dyalog Ltd recommends upgrading to version 18.1 as soon as it becomes available and you are able to schedule the upgrade.

Non-Commercial Versions

Given the nature of these defects, it is our intention to update our non-commercial distributions of version 18.0, although this process may lag behind the distribution of patches to clients paying for support by some weeks.


We apologise for the significant inconvenience that we know this is causing for some of you and thank you for your patience. We have made significant changes to our internal procedures regarding risk assessment, verification, and testing requirements for changes to existing primitive functions, to avoid a recurrence.

We do expect to re-apply those optimisations that we believe provide significant performance benefits to justify the risk of making changes over the next few releases, using new processes.


Morten KrombergCTO, Dyalog Ltd.

2020 Problem Solving Competition – Phase II highlights

With Dyalog’s APL Problem Solving Competition 2021 in full swing, it’s time to highlight some of the excellent solutions that were submitted to last year’s edition.

Stefan Kruger works for IBM making databases. While he tries to learn at least one new programming language a year, 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.

This blog post is also available as an interactive Jupyter Notebook document.

By Stefan Kruger

I’ll show a cool solution or two to each Phase II problem and dive into the details of a couple. If you need to refresh your memory with what the problems looked like, there’s a PDF of the Phase II problems.

Oh, and note that at the time of writing there is still plenty time to take part in the current edition of the competition (and really, who knew bowling was so complicated?) – there are some juicy cash prices to be won.

Problem 1: Take a Dive (1 task)

Level of Difficulty: Low

So let’s kick off with problem 1. The task was to calculate the score of an Olympic dive, consisting of a technical difficulty rating and a vector containing either 3, 5 or 7 judges’ scores. Only the central three ordered judges’ scores should be considered, which should be summed and multiplied by the technical difficulty rating.

Here is a cunning trick that wasn’t at all obvious:

βˆ‡ score←dd DiveScore scores;sorted;cenzored;rotator
  ⍝ 2020 APL Problem Solving Competition Phase II
  ⍝ Problem 1, Task 1 - DiveScore
  ⍝  0 1 2 rotates score indexes to 123, 23451 or 3456712
  ⍝  So three center values always goes first
  ⍝  51 = (0 1 2∧.= 3 5 7 ∘.|⍳100) ⍳ 1
      2.9 2.6 2.7 DiveScore¨(7 7.5 6.5 8 8 7.5 7)(9.5 8 8.5)(7.5 7 7 8.5 8)
63.8 67.6 60.75

This contestant figured out that if a vector of length 3, 5 or 7 is rotated 51 steps, then the original central three items will always end up at the beginning. No, really. It turns out that 51 is the first number X such that 0 1 2≑3 5 7|X. They tabulated the options and picked the first solution, guessing that it’d be less than 100:

      ⍸0 1 2∧.=3 5 7∘.|⍳100

But there is another way – this is one of those situations where the Chinese Remainder Theorem comes in handy, especially since it’s available on APLcart:

      3 5 7 {m|⍡+.×⍺(βŠ£Γ—βŠ’|βˆ˜βŠƒ{0=⍡:1 0 β‹„ (β΅βˆ‡β΅|⍺)+.Γ—0 1,βͺ1,-⌊⍺÷⍡})¨⍨⍺÷⍨m←×/⍺} 0 1 2 ⍝

If you figured that out, award yourself a well-deserved pat on the back. For us mortals, we probably all did something rather more pedestrian:

DiveScore ← {
    d ← 2-2÷⍨7-≒⍡       ⍝ How many items should we drop each side?

Problem 2 – Another Step in the Proper Direction (1 task)

Level of Difficulty: Medium

Problem 2 builds upon Problem 5 from Phase I. In short, we are asked to write a function Steps that takes a two-element vector to the right, defining a start and end value, and an optional left integer argument that tweaks how we generate values from start to end. The complexity here comes from the many combinations of behaviours from what exactly is given as the left argument: integer or float? positive or negative? Also, the range must be inclusive, even if a floating-point step size means that the end point is overshot. I took this on thinking it would be trivial – it wasn’t.

Here’s a great solution that manages to combine this functionality with a call to a single dfn:

βˆ‡ steps←{p}Steps fromTo;segments;width
  width ← |-/fromTo
  :If 0=βŽ•NC'p' ⍝ No left argument: same as Problem 5 of Phase I
      segments ← 0,⍳width
  :ElseIf p0 ⍝ p is the step size
      segments ← p {β΅βŒŠβΊΓ—0,⍳⌈⍡÷⍺} width
  :ElseIf p=0 ⍝ As if we took zero step
      segments ← 0
  ⍝ Take into account the start point and the direction.
  steps ← fromTo {(βŠƒβΊ)+(-Γ—-/⍺)×⍡} segments

I ended up with something more convoluted, with a few ugly special cases, and shamelessly borrowing from dfns.iotag:

Steps ← {
    range ← {
        r ← ⍺-sΓ—βŽ•IO-⍳⌊1-(⍺-βŠƒβ΅)Γ·s←×/1↓⍡,(⍺>βŠƒβ΅)/Β―1 ⍝ "inspired" by dfns.iotag
        (βŠƒβ΅)β‰ βŠƒβŠ–r: r,βŠƒβ΅ β‹„ r   ⍝ Ensure endpoint is included – yeuch :(
    ⍺ ← ⍬
    (b e) ← ⍡
    ⍺≑⍬: b range e        ⍝ No ⍺
    ⍺=0: b                ⍝ Zero step; return start point
    ⍺>0: b range e ⍺      ⍝ Positive ⍺
    len ← (e-b)Γ·countβ†βŒŠ-⍺ ⍝ Negative ⍺
    len=0: b/⍨1+count     
    b range e len

Problem 3 – Past Tasks Blast (1 task)

Level of Difficulty: Medium

The task here was to scrape the Dyalog APL Problem Solving Competition webpage to extract all links to PDF files. We get the suggestion to use either Dyalog’s HttpCommand or shell out to a system mechanism for fetching a web page.

To use HttpCommand, we first need to load it:

      ]load HttpCommand

Here’s a slightly tweaked competition submission, showing great flair in how to process XML:

PastTasks ← {
    url ← ⍡
    r ← (HttpCommand.Get url).Data  ⍝ get page contents
    (d n c a t) ← β†“β‰βŽ•XML r          ⍝ depth; name; content; attributes; type
    (k v) ← ↓⍉ βŠƒβͺ/ ((,'a')βˆ˜β‰‘Β¨n)/a   ⍝ extract key-value pairs of <a> elements
    urls ← ('href'βˆ˜β‰‘Β¨k)/v           ⍝ get URLs
    pdfs ← ('.pdf'βˆ˜β‰‘Β¨Β―4↑¨urls)/urls ⍝ filter .pdfs
    base ← βŠƒβŒ½βŠƒ('base'βˆ˜β‰‘Β¨n)/a        ⍝ base URL

The problem statement suggests that a regex-based solution might be tolerable. Here’s a stab at that approach:

PastTasks ← {
    body ← (HttpCommand.Get ⍡).Data
    pdfs ← '<a href="(.+?\.pdf)"'βŽ•S'\1'⊒body
    base ← '<base href="(.+?)"'βŽ•S'\1'⊒body

So which is the “better” solution? Well, the first approach has a number of advantages: firstly, is much more robust (provided that the web page is valid XHTML, which we are told is a given), meaning that we can abdicate responsibility for dealing with markup quirks (single vs double quotes, whitespace etc) to the built-in βŽ•XML system function, and secondly, there is that (in)famous quote from Jamie Zawinski:

Some people, when confronted with a problem, think β€œI know, I’ll use regular expressions.” Now they have two problems. – jwz

Mixing in a liberal helping of regular expressions in with APL is perhaps not helping APL’s unfair reputation for being write-only.

However, when dealing with patterns in textual data, as we unquestionably are here, regular expressions – even in a powerful language like APL – are sharp tools that are hard to beat, and any programmer worth their salt owes it to themselves to master them. In the case above, had the data not neatly been parseable as XML, it would have been more awkward to solve a problem like this relying only on APL primitives.

Problem 4 – Bioinformatics (2 tasks)

Level of Difficulty: Medium

The two tasks making up Problem 4 are borrowed from Project Rosalind, which is a Bioinformatics problem collection that often has great APL affinity:

and a hint that one benefits from understanding modular multiplication, as this isn’t built into Dyalog APL.

Here is a great example:

revp ← {                    ⍝ r ← revp dna
   dnaNum ← 'ACGT'⍳⍡        ⍝ Convert to 1..4 so that A+T = C+G = 5
   FindRevp ← {             ⍝ Given chunk size, extract positions and build the output format
       chunks ← ⍡,/dnaNum
       isRevp ← (βŠ’β‰‘5-⌽)Β¨chunks
   βŠƒβͺ/FindRevpΒ¨4 6 8 10 12  ⍝ Test against all chunk sizes and collect results
sset ← {          ⍝ r←sset n
   bin ← 2βŠ₯⍣¯1⊒⍡  ⍝ Binary digits
   arr ← ⌽2*bin   ⍝ Repeated squaring: Starting from MSB and 1, square ⍡, multiply ⍺, modulo m
   mod ← 1000000

This contestant also saw fit to include their test suite; a nice touch! Roger Hui’s version of assert has become the de facto standard, and the contestant puts it to good use:

Assert ← {⍺←'assertion failure' β‹„ 0∊⍡:⍺ βŽ•SIGNAL 8 β‹„ shy←0} ⍝ Roger Hui's Assert
RevpTest ← {
   ans ← revp s
   Assert 8 2≑⍴ans:
   Assert 5 4 7 4 17 4 18 4 21 4 4 6 6 6 20 6β‰‘βˆŠans:
   header ← 'Contest2020/Data/'  ⍝ Change as needed
   data1 ← ∊1β†“βŠƒβŽ•NGET (header,'rosalind_revp_1_dataset.txt') 1
   ans1 ← β†‘βŽΒ¨βŠƒβŽ•NGET (header,'rosalind_revp_1_output.txt') 1
   data2 ← ∊1β†“βŠƒβŽ•NGET (header,'rosalind_revp_2_dataset.txt') 1
   ans2 ← β†‘βŽΒ¨βŠƒβŽ•NGET (header,'rosalind_revp_2_output.txt') 1
   Assert ans1 ≑ revp data1:
   Assert ans2 ≑ revp data2:
   'Test passed'
SsetTest ← {
   Assert 8 = sset 3:
   Assert 551872 = sset 857:
   Assert 935424 = sset 870:
   'Test passed'

Problem 5 – Future and Present Value (2 tasks)

Level of Difficulty: Medium

Problem 5 is some hedge fund maths, or something where my eyes glazed over before I fully understood the ask. What is this, Kβ€½

This solution is impressively compact – I removed the comments to highlight the APL artistry on display: no less than three scans, count ’em!

rr ← {ARΓ—+\⍺÷AR←×\1+⍡} 
pv ← {+/⍺÷×\1+⍡}

Here’s how the competitor outlined how their solution works:

This can be calculated elegantly with the following operations:

  1. Find the accumulated interest rate (AR) for each term (AR←×\1+⍡).
  2. Deprecate the cashflow amounts by dividing them by AR. This finds the present value of all the amounts.
  3. Accumulate all the present values of the amounts to find the total present value at each term.
  4. Multiply by AR to find future values at each term.

This way the money that was invested or withdrawn in a term is not changed for that term, but the money that came from the previous terms is multiplied by the current interest rate for each term arriving to the correct recurrent relation:

Step 2) amounts[i]/AR[i] ⍝ ≑ PV[i]
Step 3) amounts[i]/AR[i] + APV[i-1]
Step 4) amounts[i] + APV[i-1]Γ—AR[i]
amounts[i] + APV[i-1]Γ—AR[i-1]Γ—(1+rate[i])
amounts[i] + r[i-1]Γ—(1+rate[i]) ⍝ ≑ r[i]

Problem 6 – Merge (1 task)

Level of Difficulty: Medium

Mail merge – gotta love it. Your spam folder is full of bad examples of this: “Dear $FIRSTNAME, do you want to purchase a bridge?” We’re given a template file with patterns such as @firstname@ which are to be replaced with values stored in a JSON file. Here’s a smart approach from a competitor who knows their way around the @ operator:

Merge ← {
   templateFile ← ⍺
   jsonFile ← ⍡
   template ← βŠƒβŽ•NGET templateFile
   ns ← βŽ•JSONβŠƒβŽ•NGET jsonFile

   getValue ← {
       0=⍴⍡:,'@'   ⍝ '@@'         β†’ ,'@'
       6::'???'    ⍝ ~⍡∊ns.βŽ•NL Β―2 β†’ '???'
       ⍕ns⍎⍡       ⍝  ⍡∊ns.βŽ•NL Β―2 β†’ ⍕ns.⍡
   ∊getValueΒ¨@(⍴⍴1 0⍨)'@'(1↓¨=βŠ‚βŠ’)template

The key insight here is that since each template starts and ends with the same marker, we can partition the data on sections beginning with @ and then we’ll have a vector where every other element is a template to be substituted. Here’s an example of this:

      ↑('@'(1↓¨=βŠ‚βŠ’) '@title@ @firstname@ @lastname@, would you be interested in the Brooklyn Bridge?') (1 0 1 0 1 0)
β”‚titleβ”‚ β”‚firstnameβ”‚ β”‚lastnameβ”‚, would you be interested in the Brooklyn Bridge?β”‚
β”‚1    β”‚0β”‚1        β”‚0β”‚1       β”‚0                                                β”‚

I added the second row for clarity to show the alternating templates. Cool, huh? However, this only works correctly if the data leads with a template. Consider:

      '@'(1↓¨=βŠ‚βŠ’) 'Dear @firstname@ @lastname@, or maybe the Golden Gate?'
β”‚firstnameβ”‚ β”‚lastnameβ”‚, or maybe the Golden Gate?β”‚

We still have the alternating templates, but the prefix (Dear ) is lost. We can tweak the Merge function a bit to cater for this if we need to:

Merge ← {
    templateFile ← ⍺
    jsonFile ← ⍡
    template ← βŠƒβŽ•NGET templateFile
    ns ← βŽ•JSONβŠƒβŽ•NGET jsonFile
    first ← templ⍳'@'
    first>β‰’templ: templ    ⍝ No templates at all
    prefix ← first↑templ   ⍝ Anything preceding the first '@'?

    getValue ← {
        0=⍴⍡:,'@'   ⍝ '@@'         β†’ ,'@'
        6::'???'    ⍝ ~⍡∊ns.βŽ•NL Β―2 β†’ '???'
        ⍕ns⍎⍡       ⍝  ⍡∊ns.βŽ•NL Β―2 β†’ ⍕ns.⍡
    ∊prefix,getValueΒ¨@(⍴⍴1 0⍨)'@'(1↓¨=βŠ‚βŠ’)template

Now, the competition is pitched such that “proper array solutions” are preferred – and for good reasons, most of the time. However, it’s hard to overlook some industrial regex action in this case. Strictly for Perl-fans:

Merge ← {
    mrg ← βŽ•JSONβŠƒβŽ•NGET ⍡
    keys ← mrg.βŽ•NLΒ―2
    vals ← mrg.⍎¨keys

    ('@',Β¨(keys,'' '[^@]+'),Β¨'@')βŽ•R((⍕¨vals),'@' '???')βŠƒβŽ•NGET ⍺

Problem 7 – UPC (3 tasks)

Level of Difficulty: Medium

Problem 7 had us learning more about bar codes than we ever thought necessary. Read them, write them, verify them, scan them – forwards and backwards no less. Good scope for stretching your array muscles on this one. The eagle-eyed amongst you may have spotted that the verification aspect is a simplified version of Luhn’s algorithm, which a certain Morten Kromberg used to illustrate APL’s array capabilities at JIO a while back.

Here’s a good solution:

CheckDigit ← (10|∘-+.Γ—βˆ˜(11⍴3 1))          ⍝ Computes the check digit for a UPC-A barcode.

UPCRD ← 114 102 108 66 92 78 80 68 72 116 ⍝ Right digits of a UPC-A barcode, base 10.
bUPCRD ← ⍉2∘βŠ₯⍣¯1⊒UPCRD                    ⍝ Bit matrix with one right digit per row.
WriteUPC ← {
   ⍝ Writes the bits of a UPC-A barcode.  
   ~((11∘=β‰’)∧(∧/0βˆ˜β‰€βˆ§β‰€βˆ˜9))⍡: Β―1            ⍝ Check for simple errors
   b ← bUPCRD[⍡,CheckDigit ⍡;]  
   1 0 1, (,~6↑b), 0 1 0 1 0, (,6↓b), 1 0 1 
ReadUPC ← {
   ⍝ Reads a UPC-A barcode into its digits.
   ~(∧/0βˆ˜β‰€βˆ§β‰€βˆ˜1)⍡: Β―1                 ⍝ Input isn't a bit vector
   95≠≒⍡: Β―1                         ⍝ Number of bits must be 95
   (b l m r e) ← ⍡ βŠ‚β¨ (∊¯1βˆ˜β†“,⌽) (3↑1)(42↑1)(5↑1)
   b ∨β₯(β‰’βˆ˜1 0 1) e: Β―1               ⍝ Wrong patterns for the guards
   m≒0 1 0 1 0: ¯1
   bits ← ↓12 7⍴ l,r
   C ← (↓bUPCRD)∘⍳ ~@(⍳6)            ⍝ Convert bits to digits
   tf ← ~∧/10 > nums ← C bits        ⍝ Should we try flipping the bits?
   nums ← (numsΓ—1-tf) + tfΓ—CβŒ½β†“βŒ½β†‘bits
   ∨/10=nums: ¯1                     ⍝ Bits simply aren't right
   (Β―1↑nums)β‰ CheckDigit 11↑nums: Β―1  ⍝ Bad check digit

Problem 8 – Balancing the Scales (1 task)

Level of Difficulty: Hard

Our task is to partition a set of numbers into two groups of equal sum if this is possible, or return ⍬ if not. This is a well-known NP-complete problem called The Partition Problem and, as such, has no polynomial time exact solutions. The problem statement indicates that we only need to consider a set of 20 numbers or fewer, which is a bit of a hint on what kind of solution is expected.

This problem, in common with many other NP problems, also has a plethora of interesting heuristic solutions: polynomial algorithms that whilst not guaranteed to always find the optimal solution will either get close, or be correct for a significant subset of the problem domain in a fraction of the time the exact algorithms would take.

However, it’s clear that Dyalog expects us to give an exact solution, and has given us an upper bound on the input data length. Finally, we’re offered the cryptic advice that

Understanding the nuances of the problem is the key to developing a good algorithm.

Yes, thank you, master Yoda.

Here’s a great, efficient solution:

   2|sum: ⍬   ⍝ Lists with an odd sum cannot be split into equal parts.
   ⍝ A partitioning method based on the algorithm by Horowitz and Sahni.
   ⍝ The basic idea of the algorithm is to split the input into two parts,
   ⍝ and then generate all subset sums for these parts. Then the problem
   ⍝ becomes finding a sum of two subset sums from different parts
   ⍝ equal to the desired value. Instead of sorting the sums and comparing
   ⍝ them like in the original algorithm, standard APL searching primitives
   ⍝ ∊ and ⍳ are used. Another key idea is to generate the subset sums
   ⍝ in a specific order, so that the nth subset sum in the vectors a and b
   ⍝ is the sum of the elements chosen by the binary representation of n.
   ⍝ This means that we can get the elements of the solution sum
   ⍝ without having to generate anything but the sums.
       s←⍡(↑{⍺⍡}↓)⍨⌊2÷⍨≒⍡                          ⍝ Split the input.
       a bβ†βŠƒΒ¨(⊒,+)/Β¨s,Β¨0                           ⍝ Generate the subset sums.
       indexes←a {(⊒,⍡⍳⍺⌷⍨(≒⍺)⌊⊒)1⍳⍨⍺∊⍡} halfsum-b ⍝ Search for solution indexes.
       indexes[2]>β‰’b: ⍬
       ⍡ {(⍺/⍨~⍡)(⍡/⍺)} ∊(2⍴¨⍨≒¨s)⊀¨indexes-1      ⍝ Get the solution from the indexes.
   ⍝ A simple exhaustive search. It uses the same binary representation
   ⍝ idea as the horowitzsahni function.
       i>2*≒⍡: ⍬
       ⍡ {(⍺/⍨~⍡)(⍡/⍺)} (2⍴⍨≒⍡)⊀i-1

   ⍝ The exhaustive method performs better than the Horowitz-Sahni method
   ⍝ for small input sizes. 14 seems to be a reasonable cutoff point.
   14>≒⍡: exhaustive ⍡
   horowitzsahni ⍡

There are a number of clever touches here – there are actually two different solutions, an exhaustive search and an implementation of the algorithm due to Horowitz and Sahni, which, although still exponential, is known to be one of the fastest for certain subsets and input sizes. A switch based on input size checks for the crossover point and chooses the fastest option. And this is fast – five times faster than that of the Grand Prize winner, and four orders of magnitude faster than the slowest solution.

Such a performance spread is intriguing, so there are clearly lessons to be learned here. When I tried this problem, I ended up with a pretty straight-forward (a.k.a. naive) brute force search:

Balance ← {βŽ•IO←0
    total ← +/⍡
    2|total: ⍬             ⍝ Sum must be divisible by 2
    psum ← totalΓ·2         ⍝ Our target partition sum
    bitp ← ⍉2∘βŠ₯⍣¯1⍳2*≒⍡    ⍝ All possible bit patterns up to ≒⍡
    idx ← ⍸<\psum=bitp+.×⍡ ⍝ First index of partition sum = target
    ⍬≑idx: ⍬               ⍝ If we have no 1s, there is no solution
    part ← idx⌷bitp        ⍝ Partition corresponding to solution index
    (part/⍡)(⍡/⍨~part)     ⍝ Compress input by solution pattern and inverse

If you come to APL from a scalar language, that approach must seem incredibly wasteful: make all bit patterns. Try all sums. Search for the right one, if it exists. But as it turns out, this is APL home turf advantage. Let’s try to demonstrate this point. If you did this “loop and branch”, you’d iterate over the bit patterns and stop once you find the first solution – in fact, for the test data in the problem specification, the first solution appears at around the 1500th bit pattern if you generate them as I do above. The vector version would need to consider the whole space of around


a million or so, so quite a difference. Surely, in this case the scalar approach should be way faster? Only one way to find out. We can make a scalar version in several ways – here’s the “Scheme” version:

BalanceScalar ← {βŽ•IO←0     ⍝ Warning: this is not the APL Way, as we shall see.
    total ← +/⍡
    2|total: ⍬             ⍝ Sum must be divisible by 2
    psum ← totalΓ·2         ⍝ Our target partition sum
    data ← ⍡
    bitp ← ↓⍉2∘βŠ₯⍣¯1⍳2*≒⍡   ⍝ Pre-compute the bit patterns
    {                      ⍝ Try one sum after the other, halt on first solution
        0=⍡: ⍬
        patt ← β΅βŠƒbitp
        psum=patt+.Γ—data: (patt/data)(data/⍨~patt) ⍝ Exit on first solution found
    } Β―1+β‰’bitp

Dyalog’s got game when it comes to tail call optimisation, right? OK, let’s race:

      d ← 10 81 98 27 28 5 1 46 63 99 25 39 84 87 76 85 78 64 41 93
      cmpx 'Balance d' 'BalanceScalar d'
  Balance d       β†’ 2.7EΒ―2 |   0% βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•            
* BalanceScalar d β†’ 3.9EΒ―2 | +43% βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•

Vectorisation, Boolean vectors and primitive functions wins the day. We didn’t go completely scalar, to be fair, as we still pre-computed all the binary patterns.

But back to the task at hand – let’s pit ourselves against the intellectual might of Horowitz and Sahni:

    2|sum: ⍬   ⍝ Lists with an odd sum cannot be split into equal parts.
    s←⍡(↑{⍺⍡}↓)⍨⌊2÷⍨≒⍡                          ⍝ Split the input.
    a bβ†βŠƒΒ¨(⊒,+)/Β¨s,Β¨0                           ⍝ Generate the subset sums.
    indexes←a {(⊒,⍡⍳⍺⌷⍨(≒⍺)⌊⊒)1⍳⍨⍺∊⍡} halfsum-b ⍝ Search for solution indexes.
    indexes[2]>β‰’b: ⍬
    ⍡ {(⍺/⍨~⍡)(⍡/⍺)} ∊(2⍴¨⍨≒¨s)⊀¨indexes-1      ⍝ Get the solution from the indexes.
      cmpx 'horowitzsahni d' 'Balance d' 'BalanceScalar d'
  horowitzsahni d β†’ 4.7EΒ―5 |      0%                                         
* Balance d       β†’ 2.8EΒ―2 | +59266% βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•            
  BalanceScalar d β†’ 4.0EΒ―2 | +84466% βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•

Ouch! Well, told you my exhaustive search was naive. An impressive performance from the competitor – but also an impressive performance from Dyalog APL – even my knocked up exhaustive search runs in a pretty decent 25–30ms or so, about half the time of my shoddy Python attempt (although out-speeding Python is a low bar). I’m keeping the above implementation of Horowitz/Sahni handy for next edition of Advent of Code, where this problem always seems to crop up in some shape or form.

Problem 9 – Upwardly Mobile (1 task)

Level of Difficulty: Hard

And so for the final question. We were offered strong hints that a neat array-oriented solution might not be possible, but that the judges were prepared to be proven wrong.

Here’s a nicely compact, recursive solution:

βˆ‡ weights ← Weights filename;diag;FindWeights;start
    diag ← ↑(β‰ βˆ˜(βŽ•UCS 10)βŠ†βŠ’)βŠƒβŽ•NGET filename
    FindWeights ← {
        'β”Œβ”β”‚'βˆŠβ¨βŠƒβ΅: βˆ‡1↓⍡                    ⍝ if on any of these, go down        
        βŽ•AβˆŠβ¨βŠƒβ΅: βŽ•A=βŠƒβ΅                      ⍝ if on a letter, give weights
        r_disp ← '┐'⍳⍨0⌷⍡                  ⍝ otherwise, (i.e. on 'β”΄'), find the displacement of right branch,
        l_disp ← -1+'β”Œ'⍳⍨⌽0⌷⍡              ⍝ ...and the left branch
        wts ← ↑(βˆ‡r_disp⌽⍡)(βˆ‡l_disp⌽⍡)      ⍝ recurse,
        +⌿wtsΓ—[0]⌽(+/wts)Γ—r_disp (-l_disp) ⍝ ...and calculate new weights
    start ← diag⌽⍨⍸'β”΄β”‚'∊⍨0⌷diag            ⍝ starting position attained by ⌽'ing to 'β”΄' or 'β”‚'
    weights ← (~∘0÷∨/)FindWeights start    ⍝ remove 0s and get lowest weights

Finally, someone took the suggestion that an array-based solution might not be possible as a personal challenge and produced the following:

Weights ← {
    m  ← ↑(βŽ•UCS 10)(β‰ βŠ†βŠ’)βŠƒβŽ•NGET ⍡ ⍝ no empty lines midway through so this is fine
    fm ← m='β”΄'               ⍝ fulcrum mask
    ER ← {+\1-⍡\Β―2-⌿0βͺ⍸⍡}    ⍝ distance to closest 1 to the left
    wa ← +/,mβˆŠβŽ•A             ⍝ weight amount
    wi ← (⍳wa)@{⍡} mβˆŠβŽ•A      ⍝ weight indexes
    fa ← +/,fm               ⍝ fulcrum amount
    fir← wa + ⍳fa            ⍝ fulcrum indexes (reduced)
    fi ← fir@{⍡} fm          ⍝ fulcrum indexes
    ai ← fi+wi               ⍝ all indexes
    ai+← ⍉(m∊'β”Œβ”') {⍺\⍡/⍨⍡≠0}⍀1β₯⍉ 0@1⊒ai ⍝ extend indexes upwards to the β”Œβ”s that need them (exclude top β”΄ as it isn't matched)
    ld ←  ER⍀1⊒ m='β”Œ'        ⍝ distance to left
    rd ← ⌽ER⍀1⌽ m='┐'        ⍝ distance to right
    xp ← (⍴m)⍴⍳2βŠƒβ΄m          ⍝ x position
    fml← ↓fm                 ⍝ fulcrum mask & its lines
    ail← ↓ai                 ⍝ all index lines
    GET← {βŠƒ,/ailβŒ·β¨βˆ˜βŠ‚Β¨fml/¨⍡} ⍝ get an item of ai for each fulcrum at x position ⍡
    lir← GET ↓xp-ld          ⍝ left indexes (reduced)
    rir← GET ↓xp+rd          ⍝ right indexes (reduced)
    ldr← fm /β₯, ld           ⍝ left distance (reduced)
    rdr← fm /β₯, rd           ⍝ right distance (reduced)
    in ← β†‘βŠƒ{(+/⍡[⍺])@(βŠƒβΊ)⊒ ⍡}/ (↓⍉↑fir lir rir) , βŠ‚β†“(⍳fa+wa)∘.=⍳wa ⍝ included weights for each index
    cf ← (ldr ×⍀¯1⊒ in[lir;]) - rdr ×⍀¯1⊒ in[rir;] ⍝ coefficients
    ws ← (1,(β‰’cf)⍴0) ⌹ ((2βŠƒβ΄cf)↑1)βͺcf              ⍝ unscaled weights
    (⊒÷∨/) ws                                      ⍝ scale weights to integers

I take my hat off in admiration of the audacity: “An array solution might not be possible, eh? Hold my beer.”

So there we have it, a smΓΆrgΓ₯sbord of clever solutions to serve as an inspiration for us all. The 2020 edition of the competition sported a slightly simplified format where you were expected to tackle every problem instead of the approach in previous years where you had to make a subset selection from themed groups – this new approach remains for the current (2021) edition.

You are taking part, aren’t you?

APL Seeds ’21: Wednesday 31 March

Last Wednesday we hosted APL Seeds ’21, an event for those just starting their APL journey. Although we knew we had a good programme with some exceptional presenters in place, we very quickly had to increase our Zoom webinar limit to accommodate the 287 people who registered to attend! We were surprised and excited by the demographic, spanning 32 countries and with the vast majority having only basic or no APL experience.

The meeting started with a brief introduction from Dyalog’s Managing Director, Gitte Christensen, who shared her initial “Eureka” APL moment and gave some examples of situations in which APL is used today. Richard Park then took us on a whirlwind tour of APL’s past (including the very cool 1975 APL demonstration!) before demystifying the “beautiful squiggles” that define APL and introducing the modern resources that are available for learning APL (for a summary of these see the suggestions for learning resources available on our website).

The main presentations began with Rodrigo GirΓ£o SerrΓ£o giving a basic introduction to APL functions and syntax. Using the example of manually justifying text, he showed just how natural it is to process data in arrays by combining a few functions and operators. His initial exploration using a small snippet of text worked instantaneously and without issue on a whole book. After seeing this, hopefully you’ll feel an urge to learn some more – either because you got hooked (like Rodrigo did!) or simply because you want to learn how to think in an array-oriented way, which is very relevant in many situations today, such as when working with GPUs.

Martin Janiczek used a real-life example from the market insights and consumer trends company that he works for (GWI). Despite being a self-described “APL baby”, having learned APL for only around a month, he was able to get to grips with the tree structures that he wanted to use, and talked about how learning APL led him to change his overall approach to the problem. He achieved a highly-performant working prototype in two weeks and with only 172 lines of code, despite starting from the position of a complete APL beginner. Although ultimately his APL model was not taken into production, it inspired a complete rethink and new approach in the eventual product.

Conor Hoekstra (NVIDIA) describes himself as “not an APLer but a big fan”, and his enthusiasm is obvious and contagious! His explorations in APL are YouTube famous, and here again he deftly shows how APL can be used as a tool of thought to explore problems from many different angles with relative ease. He went through multiple different solutions to writing an All Equals function (is every element in a list the same as every other element?), playing with different primitives and comparing the performance of the solutions.

The final presentation came from Tomas Gustafsson, creator of the stunning Stormwind boating simulator. Tomas introduced the technology behind the 3D engine that he uses for his simulator, explaining the code that makes it all happen, before walking us through creating some simple 3-D shapes (a rotating triangle and an icosahedron) and the pitfalls that this entails. From the comments we know he seemed to inspire several members of the audience to want to know more… so for those of you that do, his code examples will soon be available from the APL Seeds web page.

We hope everyone found the event useful and enjoyable (the feedback seems to indicate that you did – thank you!). Relevant materials have started to be uploaded to the APL Seeds ’21 webpage – this page also includes links to recordings of the presentations, which are all on


Welcome Rodrigo GirΓ£o SerrΓ£o

The story of how Rodrigo got his first internship at Dyalog is, in his opinion, a textbook example of serendipity. As 2020 started, Rodrigo began actively participating in an online code golf community, where people try to solve programming challenges in as few bytes of code as possible. Whilst his golfing skills were possibly lacking, the challenges he posted were usually well accepted. Posting many challenges meant Rodrigo got exposed to answers in all sorts of programming languages, from C, Java, Python and JavaScript, to Jelly, 05AB1E, Husk…and APL. Because of the context and the aspect of it, Rodrigo first thought APL was one of those “esolangs” and not a serious programming language.

Rodrigo’s fascination with APL led him to start frequenting The APL Orchard chatroom, where a small number of brilliant people convened to discuss all things APL. Here he met AdΓ‘m Brudzewsky, who was keen on teaching APL to newcomers, and so began Rodrigo’s journey to learn APL.

His interest in APL kept growing, and he found it to be a simple and expressive language that also incorporated his affinity with mathematics. One day, while lurking in The APL Orchard, AdΓ‘m asked Rodrigo if he would be interested in taking an intern position at Dyalog…a few emails later it was established that Rodrigo would work as a part-time intern at Dyalog during the Summer of 2020. This enabled Dyalog to make the most of Rodrigo’s skills in teaching and technical writing, and meant Rodrigo could indulge his passion for sharing knowledge about mathematics and programming while still finishing his MSc in Applied Mathematics. After his internship, Rodrigo took some time to complete his MSc thesis before returning to Dyalog to finish what he had started and hopefully to take part in many other interesting projects. When he is not working for Dyalog, Rodrigo may be found leading a Portuguese APL meetup, writing a blog post for his website (, or maybe leading a workshop or course. Other than working, Rodrigo likes to spend time with his loved ones, read fantasy books, eat chocolate, and watch silly comedy movies.