Case Conversion: Mapping and Folding

Dyalog v18.0 introduced ⎕C, which converts the case of characters in an array by mapping to lower case, mapping to upper case, or folding. This superseded an earlier experimental I-beam (819⌶) that could map to lower or upper case but not fold – this I-beam is currently deprecated and will be removed in Dyalog v20.0.

There’s often confusion about the difference between mapping and folding. Mapping is used when you want characters in an array to be in a particular case, whereas folding is used when you want to eliminate case to perform case-insensitive comparisons. The confusion arises because case insensitive comparisons can usually be done well by mapping to lower case rather than folding – indeed, on first inspection, mapping to lower case and folding appear to be the same thing.

The difference is best illustrated through some examples. Used monadically, the I-beam maps to lower case and ⎕C folds:

      819⌶'Hello'
hello
      ⎕C'Hello'
hello

A case-insensitive match function that uses 819⌶ to map both arguments to lower case before checking if they match might look like this:

      cc←≡⍥(819⌶)

In many cases it will appear to work without issues:

      'hello' cc 'HELLO'
1
      'hello' cc 'GOODBYE'
0

However, it doesn’t always work. Greek, for example, has two different lower-case sigma characters (σ and ς) but only one upper case (Σ). ίσως and ΊΣΩΣ are case-insensitively equal, but the function does not work:

      'ίσως' cc 'ΊΣΩΣ'
0

This is because when these two arrays are mapped to lower case they become ίσως and ίσωσ respectively, which do not match. If we use folding instead:

      cc←≡⍥⎕C

the comparisons work as expected:

      'hello' cc 'HELLO'
1
      'hello' cc 'GOODBYE'
0
      'ίσως' cc 'ΊΣΩΣ'
1

This works because folding converts the Greek words to ίσωσ and ίσωσ respectively – every different sigma character, even the lower-case ones, have been changed to σ, and now the two arrays match.

The main use of case conversion is to perform caseless comparisons, so you might wonder why mapping to upper and lower case is supported at all. There are still occasions where you might need that – most notably, when formatting text for display.

If you are still using 819⌶ to perform caseless comparison you should change to using ⎕C to get correct behaviour. And do not forget that 819⌶ will not be supported beyond Dyalog v19.0.

Want to learn more? Adám Brudzewsky explains mapping and folding in this webinar, beginning at 00:06:33.

Formal Proposal for APL Array Notation – Seeking Feedback

One of the defining features of the APL language is the ability to denote numeric vectors directly through juxtaposition — separating the elements by spaces, as in 0 1 1 2 3 5 8. The notation for character “vectors” is similar to that for “strings” in most other languages, using quotes to denote the start and end of a list of characters. When generalised arrays were added to the language in the early 1980s, the most popular APL dialects extended the vector notation to allow nested arrays to be written using so-called strand notation, allowing the juxtaposition of sub‑expressions producing arrays to form a one-dimensional array — as in:

      (2+2) (FOO 42) MAT

Strand notation works well for small, relatively simple one-dimensional arrays. As soon as arrays are too large to be represented on a single line of code, deeply nested, rank greater than one, or (in APL systems that support them) contain namespaces or objects, APL requires the use of primitives or system functions to assemble them from simple components.

The flexibility of the APL language has allowed many APL programmers to work around the issue, either by implementing custom array notations or by using the ability of most APL interpreters to simply store arrays within saved workspaces without having an actual source form of the data. Within specific applications, domain specific notations can be very successful, but readability is poor for anyone not trained in the specific variation used — or who is missing the tooling required to interpret them — as well as sometimes having significant run-time cost.

Recently, the need for a better notation for arrays has grown within the Dyalog APL community:

  • The switch to text-based sources means that arrays that represent constants, enumerations or initial values — that arguably constitute part of the source of an application — need a textual representation if they are to be managed using the same tools as functions and operators.
  • The increased use of namespaces and name/value pairs as arguments to both user-defined and system functions makes the lack of a good notation for namespaces painful.

Dyalog Ltd intends to implement core language support for a notation that makes it possible to write most arrays literally, without requiring the use of primitive functions, over multiple lines of source where this increases readability. It can be used to write nested arrays, and arrays of rank greater than one. The notation also describes many namespaces/objects, providing both inline and anonymous definitions.

Acknowledgements

Although I used the word “recently” above, the foundations for the notation which gradually evolved into the proposal that we are publishing today were laid by Phil Last at Dyalog’15 in Sicily. At Dyalog, Adam Brudzewsky has been the torch bearer and is the author of the current proposal. We would also like to recognise the contributions of Marshall Lochbaum and dzaima, who have acted as sounding boards and have implemented notations similar to that proposed here in the APL-derivative BQN and in dzaima/APL respectively.

Download the full proposal document

Experimentation within Dyalog APL

Experimental implementations using APL models are available within some tools in the Dyalog eco-system, such as the Link tool (which supports the representation of code and data in Unicode text files) and the functions Serialise and Deserialise within the namespace ⎕SE.Dyalog.Array. You can also try it out in the interactive online sandbox.

Providing feedback

Dyalog Ltd is keen to have feedback from the array language community on the notation proposed here, so that we can feel confident about the design before we proceed with our implementation. Our hope is that we will be able to keep the differences between future array notations within the family of array languages to a minimum.

You can leave feedback below or in the APL Orchard chatroom, the APL Farm’s #apl channel, the r/apl and r/apljk subreddits, and the comp.lang.apl newsgroup, all of which we will monitor. (See APL Wiki for information about these forums.) In addition, we have created a topic in our own forum. If you prefer not to comment publicly, then please send comments by e-mail. We will update the discussion page for APL Wiki’s Array notation design considerations article to contain a record of significant feedback.

Structural vs. Mathematical “Under”

The APL Farm has recently hosted discussions about the proposed under operator, asking “why Dyalog hasn’t implemented it a long time ago”. I claimed that an important reason was that Roger Hui wasn’t a big fan of the proposed extension known as “structural under”. Stefan Kruger then asked me why that was so. Since Roger isn’t able to respond himself, I’ll do my best to explain my own understanding of the issues.

For anyone not familiar with the concept of under, or dual as it was known when first implemented in SHARP APL, it is an operator that provides a way to express a common mathematical pattern, where a computation or proof is simplified by first translating the input domain, applying a function, and then performing the inverse transformation. For example, if we use the symbol to denote under, have the translation function as the right operand, and the function that applies to the translated domain as the left, then we could use +⍢⍟ to demonstrate that multiplication is equivalent to addition under logarithm, which is why slide rules work:

      1 2 3 4 (× ≡ +⍢⍟) 0.1 1.1 17 100
1

Another example of simplifying multiplication using dual is the use of Fast Fourier Transforms to multiply very large numbers, as explained in the notes about xtimes in the dfns workspace.

It is easy to find examples of dualities outside the mathematical domain, such as midnight snacking: (open refrigerator door, remove food, close door) or Roger’s favourite example of medical surgery: apply anaesthetic to greatly simplify the operation, perform surgery and (very important) back out the anaesthetic.

I believe that Roger was of the opinion that under/dual should be restricted to functions that have well-defined inverses using the “mathematical” definition used in SHARP APL and the J language. We can model this with a defined operator, let us call it Um:

   Um←{⍺←{⍵ ⋄ ⍺⍺} ⋄ ⍵⍵⍣¯1⊢(⍵⍵ ⍺)⍺⍺(⍵⍵ ⍵)}

The extension known as structural under allows the transformation function to be a structural function, even though such functions do not have inverses in the mathematical sense. In this case, the left operand is applied to the subset of items selected from the right argument by the structural function. This is easy to model using a feature of some APLs known as selective specification, in which you can have a function to the left of an assignment whereby the assignment only modifies items selected from an array using so-called “structural” functions – those functions that select or reorder items of an array without doing math, such as ↑ ↓ ⍉ ⌽ ∊.

Let us call this Us:

   Us←{⍺←{⍵ ⋄ ⍺⍺} ⋄ w←⍵ ⋄ ((⍵⍵)w)←(⍵⍵ ⍺)⍺⍺(⍵⍵ ⍵) ⋄ w}

This is very useful, for example, we could negate all items of an array except the first two by writing:

      - Us (2∘↓) ⍳5
1 2 ¯3 ¯4 ¯5

The big question is whether Us and Um can be combined into the same operator, or two separate operators are needed. One problem is that already has a defined inverse in Dyalog APL, which pads with zeros, so Um returns something different:

      - Um (2∘↓) ⍳5
0 0 ¯3 ¯4 ¯5

If we want to combine the two into one, then we need a rule that allows us to decide which definition to use. Marshall Lochbaum‘s BQN language has a table of structural primitive functions; it performs a structural under when possible (according to an extensively described rule), and otherwise attempts a mathematical under.

Personally, this sort of conditional logic in the definition of a key primitive makes me very uneasy, and I think Roger was struggling with this as well. Unfortunately he passed away before we were able to finish argdiscussing the design. Another reason for feeling that the two operators are different is that, while it often makes sense for the transformation to apply to both arguments in the mathematical case, it is extremely rare for structural under. You cannot do:

       1 + Us (2∘↓) ⍳5

because when you apply (2∘↓) to the left argument, you get an empty vector. Instead, you need to turn the left operand into a monadic function to add one to the three trailing elements:

       1∘+ Us (2∘↓) ⍳5
1 2 4 5 6

This increases my personal unease about combining the two into a single operator. Even though this would work “just fine” most of the time, it would still make it difficult to explain exactly what is going on.

It is my opinion that APL needs to remain a rationalised mathematical notation if it is to remain useful and relevant in the long term. Deciding whether to implement a strict mathematical operator, a combined operator, or two separate operators (or do nothing for a while longer), is one of the key design decisions that we will be faced with in the near future.

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:

      ⎕IO←0
      ]Box on -style=max
┌→────────────────┐
│Was ON -style=max│
└─────────────────┘
      0 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)≡⍬⊤⍬
1

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
      :Else
          :Continue
      :EndTrap
      :If eval≡target
          r ,← ⊂combo
      :EndIf
  :EndFor
∇

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:

      +⌸⍬
┌⊖┐
⌽0│
└~┘

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:

      {⎕←⍺}⌸⍬
0

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

      {⎕←⍵}⌸⍬
┌⊖┐
│0│
└~┘

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:

      0>⍬
┌⊖┐
│0│
└~┘
      >⌸⍬
┌⊖┐
⌽0│
└~┘

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
┌⊖┐
│0│
└~┘

or take and drop, ↑↓:

      0↑⍬ ⍝ Take no elements from the beginning of the empty vector
┌⊖┐
│0│
└~┘
      0↓⍬ ⍝ Drop no elements from the end of the empty vector
┌⊖┐
│0│
└~┘

However, gives us a dyadic transpose – and, perhaps unexpectedly, this one is ⎕IO-dependent:

      0⍉⍬
┌⊖┐
│0│
└~┘

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:

      ⎕IO←1
      0⍉'Same for the dyadic form. Sometimes.'
DOMAIN ERROR
      0⍉'Same for the dyadic form. Sometimes.'
       ∧

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

      /⌸⍬
┌⊖┐
⌽0│
└~┘

will end up as:

      0/⍬ ⍝ zero empty vectors
┌⊖┐
│0│
└~┘

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

      0⍴⍬ ⍝ zero empty vectors
┌⊖┐
│0│
└~┘

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

      0⊤⍬
┌⊖┐
│0│
└~┘

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
┌⊖────┐
│ ┌⊖┐ │
│ │0│ │
│ └~┘ │
└∊────┘

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

      ↑⍸0
┌⊖┐
⌽0│
└~┘

What About 0⍴⊂⍬?

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

      (⍸0)≡0⍴⊂⍬
1

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
┌⊖────┐
│ ┌⊖┐ │
│ │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'
┌→─────────┐
│HelloWorld│
└──────────┘

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
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.

Towards Improvements to Stencil

Background

The stencil operator was introduced in Dyalog version 16.0 in 2017. Recently we received some feedback (OK, complaints) that (a) stencil does padding which is unwanted sometimes and needs to be removed from the result and (b) stencil is too slow when it is not supported by special code.

First, stencil in cases supported by special code is much faster than when it is not. The special cases are as follows, from Dyalog ’17 Workshop SA3.

   {⍵}      {⊢⍵}      {,⍵}      {⊂⍵}
{+/,⍵}    {∧/,⍵}    {∨/,⍵}    {=/,⍵}    {≠/,⍵}  
    
{  +/,A×⍵}    {  +/⍪A×⍤2⊢⍵}
{C<+/,A×⍵}    {C<+/⍪A×⍤2⊢⍵}
C:  a single number or variable whose value is a single number
A:  a variable whose value is a rank-2 or 3 array
The comparison can be < ≤ ≥ > = ≠
odd window size; movement 1; matrix argument
 

You can test whether a particular case is supported by using a circumlocution to defeat the special case recognizer.

   )copy dfns cmpx

   cmpx '{⍵}⌺3 5⊢y' '{⊢⊢⍵}⌺3 5⊢y' ⊣ y←?100 200⍴0
  {⍵}⌺3 5⊢x   → 4.22E¯4 |      0%                               
  {⊢⊢⍵}⌺3 5⊢x → 5.31E¯2 | +12477% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '{⌽⍵}⌺3 5⊢y' '{⊢⊢⌽⍵}⌺3 5⊢y'
  {⌽⍵}⌺3 5⊢y   → 2.17E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  {⊢⊢⌽⍵}⌺3 5⊢y → 2.21E¯1 | +1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

If the timings are the same then there is no special code.

Padding and performance improvements will take a lot of work. For example, for padding (i.e. the treatment of cells at the edge of the universe) multiple options are possible: no padding, padding, wrap from opposite edge, etc. While working on these improvements I hit upon the idea of writing a stencil function which produces the stencil cells. It only works with no padding and only for movements of 1 (which I understand are common cases), but turns out to be an interesting study.

A Stencil Function

⍺ stencell ⍵ produces the stencil cells of size from  , and is equivalent to {⍵}⌺⍺⊢⍵ after the padded cells are removed.

stencell←{
  ⎕io←0                 ⍝ ⎕io delenda est!
  s←(≢⍺)↑⍴⍵
  f←1+s-⍺               ⍝ frame AKA outer shape
  m←⊖×⍀⊖1↓s,1           ⍝ multiplier for each axis
  i←⊃∘.+⌿(m,m)×⍳¨f,⍺    ⍝ indices
  (⊂i) ⌷ ⍵ ⍴⍨ (×⌿(≢⍺)↑⍴⍵),(≢⍺)↓⍴⍵
}

For example, stencell is applied to x with cell shape 3 5 .

   ⊢ x←6 10⍴⍳60                    ⍝ (a)
 0  1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59

   c←3 5 stencell x                ⍝ (b)
   ⍴c
4 6 3 5

   c ≡ 1 2 ↓ ¯1 ¯2 ↓ {⍵}⌺3 5 ⊢x    ⍝ (c)
1

   ⊢ e←⊂⍤2 ⊢c                      ⍝ (d)
┌──────────────┬──────────────┬──────────────┬──────────────┬──────────────┬──────────────┐
│ 0  1  2  3  4│ 1  2  3  4  5│ 2  3  4  5  6│ 3  4  5  6  7│ 4  5  6  7  8│ 5  6  7  8  9│
│10 11 12 13 14│11 12 13 14 15│12 13 14 15 16│13 14 15 16 17│14 15 16 17 18│15 16 17 18 19│
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│10 11 12 13 14│11 12 13 14 15│12 13 14 15 16│13 14 15 16 17│14 15 16 17 18│15 16 17 18 19│
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
│40 41 42 43 44│41 42 43 44 45│42 43 44 45 46│43 44 45 46 47│44 45 46 47 48│45 46 47 48 49│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
│40 41 42 43 44│41 42 43 44 45│42 43 44 45 46│43 44 45 46 47│44 45 46 47 48│45 46 47 48 49│
│50 51 52 53 54│51 52 53 54 55│52 53 54 55 56│53 54 55 56 57│54 55 56 57 58│55 56 57 58 59│
└──────────────┴──────────────┴──────────────┴──────────────┴──────────────┴──────────────┘

    ∪¨ ,¨ e-⍬⍴e                    ⍝ (e)
┌──┬──┬──┬──┬──┬──┐
│0 │1 │2 │3 │4 │5 │
├──┼──┼──┼──┼──┼──┤
│10│11│12│13│14│15│
├──┼──┼──┼──┼──┼──┤
│20│21│22│23│24│25│
├──┼──┼──┼──┼──┼──┤
│30│31│32│33│34│35│
└──┴──┴──┴──┴──┴──┘
(a)  The matrix x is chosen to make stencil results easier to understand.
(b) stencell is applied to x with cell shape 3 5 .
(c) The result of stencell is the same as that for {⍵}⌺ after cells with padding are dropped.
(d) Enclose the matrices in c (the cells) to make the display more compact and easier to understand.
(e) Subsequent discussion is based on the observation that each cell is some scalar integer added to the first cell.

Indices

The key expression in the computation is

   ⊃∘.+⌿(m,m)×⍳¨f,⍺ 

where

   m:  10 1;  multiplier for each axis
   f:  4 6;  multiplier for each axis
   ⍺:  3 5;  multiplier for each axis
 

We discuss a more verbose but equivalent version of this expression,

   (⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨⍺)

and in particular the right half, ⊃∘.+⌿m×⍳¨⍺ , which produces the first cell.

   ⍳⍺               ⍝ ⍳3 5
┌───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│
├───┼───┼───┼───┼───┤
│1 0│1 1│1 2│1 3│1 4│
├───┼───┼───┼───┼───┤
│2 0│2 1│2 2│2 3│2 4│
└───┴───┴───┴───┴───┘
   (⍴⍵)∘⊥¨⍳⍺        ⍝ 6 10∘⊥¨ ⍳3 5
 0  1  2  3  4
10 11 12 13 14
20 21 22 23 24

Alternatively, this last result obtains by multiplying by m the corresponding indices for each axis, where an element of m is the increment for a unit in an axis. That is, m←⊖×⍀⊖1↓s,1 where s←(≢⍺)↑⍴⍵ is a prefix of the shape of  . The multipliers are with respect to the argument because the indices are required to be with respect to the argument  .

   ⍳¨⍺              ⍝ ⍳¨3 5
┌─────┬─────────┐
│0 1 2│0 1 2 3 4│
└─────┴─────────┘
   m×⍳¨⍺            ⍝ 10 1×⍳¨3 5
┌───────┬─────────┐
│0 10 20│0 1 2 3 4│
└───────┴─────────┘
   ∘.+⌿ m×⍳¨⍺       ⍝ ∘.+⌿ 10 1×⍳¨3 5
┌──────────────┐
│ 0  1  2  3  4│
│10 11 12 13 14│
│20 21 22 23 24│
└──────────────┘
   ((⍴⍵)∘⊥¨⍳⍺) ≡ ⊃∘.+⌿m×⍳¨⍺
1

This alternative computation is more efficient because it avoids creating and working on lots of small nested vectors and because the intermediate results for ∘.+⌿ grows fast from one to the next (i.e., O(⍟n) iterations in the main loop).

The left half, ⊃∘.+⌿m×⍳¨f , is similar, and computes the necessary scalar integers to be added to the result of the right half.

   ⊃ ∘.+⌿ m×⍳¨f     ⍝ ⊃ ∘.+⌿ 10 1×⍳¨4 6
 0  1  2  3  4  5
10 11 12 13 14 15
20 21 22 23 24 25
30 31 32 33 34 35

The shorter expression derives from the more verbose one by some simple algebra.

(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨⍺)    ⍝ verbose version
⊃∘.+⌿(m×⍳¨f),m×⍳¨⍺             ⍝ ∘.+ is associative
⊃∘.+⌿(m,m)×(⍳¨f),⍳¨⍺           ⍝ m× distributes over ,
⊃∘.+⌿(m,m)×⍳¨f,⍺               ⍝ ⍳¨ distributes over ,

I am actually disappointed that the shorter expression was found ☺; it would have been amusing to have a non-contrived and short expression with three uses of ∘.+ .

Cells

Having the indices i in hand, the stencil cells obtain by indexing into an appropriate reshape or ravel of the right argument  . In general, the expression is

   (⊂i) ⌷ ⍵ ⍴⍨ (×/(≢⍺)↑⍴⍵),(≢⍺)↓⍴⍵

specifies the cell shape. If (≢⍺)=≢⍴⍵ , that is, if a length is specified for each axis of  , the expression is equivalent to (⊂i)⌷,⍵ or (,⍵)[i] ; if (≢⍺)<≢⍴⍵ , that is, if there are some trailing unstencilled axes, the expression is equivalent to (,[⍳≢⍺]⍵)[i;…;] (the leading ≢⍺ axes are ravelled) or ↑(,⊂⍤((≢⍴⍵)-≢⍺)⊢⍵)[i] (as if the trailing axes were shielded from indexing). The general expression covers both cases.

Application

stencell makes it possible to workaround current shortcomings in . The alternative approach is to use stencell to get all the stencil cells, all at once, and then work on the cells using  , +.× , and
other efficient primitives.

The following example is from Aaron Hsu. In the original problem the size of x is 512 512 64 .

   K←?64 3 3 64⍴0
   x←?256 256 64⍴0

   t←1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x
   ⍴t
256 256 64

   cmpx '1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x'
6.76E0 

The computation is slow because the cells are rank-3, not supported by special code. Aaron then devised a significant speed-up using a simpler left operand to create the ravels of the cells (but still no special code):

   t ≡ (1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K
1
   cmpx '(1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K'
1.67E0 

Use of stencell would improve the performance a bit further:

   t ≡ (,⍤3 ⊢3 3 stencell x)+.×⍉⍪K
1
   cmpx '(,⍤3 ⊢3 3 stencell x)+.×⍉⍪K'
1.09E0 

   cmpx '3 3 stencell x'
6.10E¯2

The last timing shows that the stencell computation is 6% (6.10e¯2÷1.09e0) of the total time.

Materializing all the cells does take more space than if the computation is incorporated in the left operand of  , and is practicable only if the workspace sufficiently large.

   )copy dfns wsreq

   wsreq '1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x'
110649900
   wsreq '(1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K'
647815900
   wsreq '(,⍤3 ⊢3 3 stencell x)+.×⍉⍪K'
333462260

Performance

stencell is competitive with {⍵}⌺ on matrices, where it is supported by special code written in C, and is faster when there is no special code. The benchmarks are done on a larger argument to reduce the effects of padding/unpadding done in {⍵}⌺ .

   y2←?200 300⍴0
          
   cmpx '3 5 stencell y2' '1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y2' 
  3 5 stencell y      → 1.85E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕           
  1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y → 2.91E¯3 | +57% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '3 5 stencell y' '{⍵}⌺3 5⊢y' 
  3 5 stencell y → 1.85E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* {⍵}⌺3 5⊢y      → 1.04E¯3 | -45% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕             

   y3←?200 300 64⍴0

   cmpx '3 5 stencell y3' '1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y3' 
  3 5 stencell y3      → 8.90E¯2 |    0% ⎕⎕⎕                           
  1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y3 → 7.78E¯1 | +773% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '3 5 stencell y3' '{⍵}⌺3 5⊢y3' 
  3 5 stencell y3 → 9.38E¯2 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕                      
* {⍵}⌺3 5⊢y3      → 3.34E¯1 | +256% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

There is an interesting question of whether the shorter version of the key computation (in the Indices section above) is faster than the more verbose version.

   m←10 1 ⋄ f←4 6 ⋄ a←3 5

   cmpx '⊃∘.+⌿(m,m)×⍳¨f,a' '(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨a)'
  ⊃∘.+⌿(m,m)×⍳¨f,a            → 3.75E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  (⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨a) → 5.20E¯6 | +38% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

In this case, it is faster, and I expect it will be faster for cases which arise in stencil calculations, where the argument size is larger than the cell size. But it is easy to think of arguments where ∘.+⌿ is slower than ∘.+ done with a different grouping:

   cmpx '((⍳0)∘.+⍳100)∘.+⍳200' '(⍳0)∘.+((⍳100)∘.+⍳200)' '⊃∘.+/⍳¨0 100 200'
  ((⍳0)∘.+⍳100)∘.+⍳200   → 7.86E¯7 |     0% ⎕⎕                            
  (⍳0)∘.+((⍳100)∘.+⍳200) → 1.05E¯5 | +1234% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕  
  ⊃∘.+/⍳¨0 100 200       → 1.11E¯5 | +1310% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

This question will be explored further in a later post.

Ascending and Descending

Lexicographic Ordering

Lexicographic ordering is what the APL primitives and provide:

   ⎕io←0     ⍝ ⎕io delenda est
   ⎕rl←7*5   ⍝ to get reproducible random results

   a←?11 3⍴3

   a          a ⌷⍨⊂ ⍋a
2 1 0      0 1 0
0 2 2      0 2 2
1 1 1      1 0 0
1 0 0      1 0 1
1 1 1      1 0 1
1 2 1      1 1 0
1 0 1      1 1 1
1 0 1      1 1 1
1 1 0      1 2 1
0 1 0      1 2 2
1 2 2      2 1 0

First order by column 0, resulting in groups of rows with the same values in column 0. Then, within each group, order by column 1, getting subgroups with the same values in columns 0 and 1. Then, within each subgroup, order by column 2, getting subsubgroups with the same values in columns 0, 1, and 2. In general, for each subsub…subgroup, order by column k, getting groups with identical values in columns ⍳k.

The preceding discourse is descriptive rather than prescriptive—algorithms for can use more efficient and more straightforward approaches. As well, for ease of understanding, the description is for a matrix and speaks of columns and rows. In general, any non-scalar array can be ordered, whence instead of rows, think major cells, instead of column, think item in a major cell. Symbolically and more succinctly, ⍋⍵ ←→ ⍋⍪⍵.

can be used if the orderings in the process are all ascending, or if all descending. The problem to be solved here is where the orderings are a mix of ascending and descending.

Numeric Arrays

Since ⍒⍵ ←→ ⍋-⍵ if is numeric, for such multiply each descending column by ¯1 and each ascending column by 1, then apply . This induces a “control array” having the same shape as a major cell of the argument, with a ¯1 for descending and a 1 for ascending.

   adn←{⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ⊢⍵}

For the array a in the previous section:

   a              1 ¯1 1 adn a        ¯1 1 1 adn a
2 1 0          0 2 2               2 1 0  
0 2 2          0 1 0               1 0 0  
1 1 1          1 2 1               1 0 1  
1 0 0          1 2 2               1 0 1  
1 1 1          1 1 0               1 1 0  
1 2 1          1 1 1               1 1 1  
1 0 1          1 1 1               1 1 1  
1 0 1          1 0 0               1 2 1  
1 1 0          1 0 1               1 2 2  
0 1 0          1 0 1               0 1 0  
1 2 2          2 1 0               0 2 2  

In 1 ¯1 1 adn a, column 0 is ascending, and within that, column 1 is descending, and within that, column 2 is ascending. In ¯1 1 1 adn a, column 0 is descending, and within that, column 1 is ascending, and within that, column 2 is ascending.

Ordinals

An array to be sorted can be converted to an order-equivalent integer array by assigning to each item an ordinal (an integer) which has the same ordering relationship as the original item relative to other items in the array:

   sort    ← {(⊂⍋⍵)⌷⍵}
   ordinal ← {⎕ct←0 ⋄ ⍵⍳⍨sort,⍵}

That is, the ordinals obtain as the indices of the original array in the sorted list of the ravelled elements, using exact comparisons. (Exact comparisons are used because sorting necessarily uses exact comparisons.)
For example:

   ⊢ d←¯1 'syzygy' (3 ¯5) 1j2 'chthonic' (¯1)
┌──┬──────┬────┬───┬────────┬──┐
│¯1│syzygy│3 ¯5│1J2│chthonic│¯1│
└──┴──────┴────┴───┴────────┴──┘
   ordinal d
0 5 3 2 4 0

In the example, the data items are ¯1, 'syzygy', 'chthonic', 3 ¯5, 1j2, and ¯1 again. With respect to ordering, these data items are perfectly represented by the ordinals (numbers) 0, 5, 3, 2, 4, and 0, respectively. That is, ⍋d ←→ ⍋ordinal d.

   ⍋ d
0 5 3 2 4 1
   ⍋ ordinal d
0 5 3 2 4 1

As the example illustrates, it is imperative that identical ordinals are assigned to identical items, else the ordering relationships would be changed. For example, if b←0,⍪2 1 and the 0s are assigned different ordinals,

   ⊢ b←0,⍪2 1               
0 2
0 1
   ordinal b                 ⊢ bo←0 3,⍪1 2  ⍝ faux ordinals
0 3                       0 3
0 2                       1 2
   ⍋ ordinal b               ⍋ bo
1 0                       0 1
   ⍋ b
1 0

Computation of ordinals is greatly facilitated by the total array ordering introduced in Dyalog APL version 17.0.

Non-Numeric Arrays

A general solution for the ordering problem obtains by first converting the array to an order-equivalent integer array through the use of ordinals.

   ado ← {⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ordinal ⍵}

For example:

   ⎕rl←7*5   ⍝ to get reproducible random results

   x0← ?19⍴4                            
   x1← (⊂?19⍴2) ⌷ 'alpha' 'beta'          
   x2← (⊂?19⍴3) ⌷ 'abc'                   
   x3← (⊂?19⍴3) ⌷ 'able' 'baker' 'charlie'

   x ← x0,x1,x2,⍪x3

   ordinal x
13 49 19 42
10 49 32 68
13 49 63 68
 4 49 63 42
 0 27 19 23
13 49 32 42
 0 49 19 42
10 49 32 68
10 27 32 23
 4 49 32 68
 4 49 32 68
 4 27 32 23
 4 49 32 68
 0 49 63 68
13 49 63 68
 0 49 32 42
13 27 32 23
 4 27 63 42
13 49 19 42

   (⍋x) ≡ ⍋ ordinal x
1

Suppose x is to be sorted ascending in columns 0 and 2 and descending in columns 1 and 3. The control array is 1 ¯1 1 ¯1, and:

   x                       1 ¯1 1 ¯1 ado x
┌─┬─────┬─┬───────┐     ┌─┬─────┬─┬───────┐
│2│beta │b│baker  │     │0│beta │a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │0│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │0│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│b│baker  │     │0│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │b│charlie│     │0│beta │c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │a│baker  │     │0│alpha│c│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│charlie│     │1│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│baker  │     │1│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│able   │     │1│alpha│c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │a│able   │     │2│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │2│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│alpha│c│able   │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│charlie│     │3│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│alpha│c│baker  │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│2│beta │a│baker  │     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │c│charlie│     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │3│alpha│b│baker  │
└─┴─────┴─┴───────┘     └─┴─────┴─┴───────┘

Finally

   (ordinal x) ≡ ordinal ordinal x
1

That is, ordinal is idempotent. Actually, this is kind of obvious, but I never miss an opportunity to use the word “idempotent”.☺