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