Tool of Thought

APL for the Practical Man

Boolean Techniques

May 13, 2023

In a recent post titled Suggestivity and Idioms in APL on his blog Fastidious Elegance Arron Hsu enumerates all the permutations and combinations of logical pairwise reductions on Boolean vectors. There are 10 scalar dyadic relational functions and Aaron throws in and as well for total of 12 functions. With the catenation of 1 or 0 on the front or the back, to keep the result the same shape as the input, there are 12×2×2 or 48 possible combinations.

It would be convenient to be able to describe in short terms what each of these Boolean transformations does. If we can't meaningfully name them, we probably cannot effectively use them. If we are going to search for these expressions on, say, APL Cart, we need to have some way to describe them.

In his 1987 book APL - Advanced Techniques and Utilities, Gary Bergquist uses the terms maps and poles to facilitate discussion of Boolean vectors and techniques:

A "maps" vector is a Boolean vector which consists of sets of contiguous 1s (1-maps) separated by one or more 0s, (0-maps). For example, the following bit vector contains 3 1-maps and 4 0-maps:

0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 0

A "leading" 1-poles vector is a Boolean vector which consists of pairs of 1s separated by zero or more 0s. The 1's are called "poles". The left pole in each pair may be viewed as the starting element of a set of contiguous elements. The right pole in each pair may be viewed as the next element beyond the ending element of the set. For example, the following bit vector contains 3 pairs of leading 1-poles:

0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0  

Notice that 1-maps and leading 1-poles are alternative means of conveying the same information. Basically they identify spans of contiguous elements. 1-maps do so by using 1s to flag the elements within the spans. Leading 1-poles do so by using 1s to flag the starts of spans and the starts of non-spans (hence the word "leading").

We can flip the bits and discuss 0-maps and leading 0-poles as well. These terms do not represent any inherent properties of Boolean vectors, but rather an interpretation of what the 1's and 0's mean. The same Boolean vector could be a 1-maps vector in one context and a 1-poles vector in another context. This, however, does not lessen the usefulness of the terms. With this terminolgy in hand, we can interpret ≠\ as converting leading 1-poles to 1-maps, and =\ as converting leading 0-poles to 0-maps.

How many of Aaron's 48 permutations can be succinctly described with this lexicon? Gary defines and names 6 transformations, using shift-and-compare techniques that pre-date the introduction of n-wise reduction. We can find the corresponding 6 transformations in Aaron's 48 by inspection:

R≠¯1↓0,R {2≠/0,⍵} 1-maps to leading 1-poles
R=¯1↓1,R {2=/1,⍵} 0-maps to leading 0-poles
R>¯1↓0,R {2</0,⍵} 1-maps to first 1 bits
R≥¯1↓1,R {2≤/1,⍵} 0-maps to first 0 bits
R∨¯1↓0,R {2∨/0,⍵} extend 1-maps to right by 1
R∧¯1↓1,R {2∧/1,⍵} extend 0-maps to right by 1

From these, six related ones jump right out:

R≠1↓R,0 {2≠/⍵,0} 1-maps to trailing 1-poles
R=1↓R,1 {2=/⍵,1} 0-maps to trailing 0-poles
R>1↓R,0 {2>/⍵,0} 1-maps to last 1 bits
R≥1↓R,1 {2≥/⍵,1} 0-maps to last 0 bits
R∨1↓R,0 {2∨/⍵,0} extend 1-maps to left by 1
R∧1↓R,1 {2∧/⍵,1} extend 0-maps to left by 1

Aaron may be a bit optimistic when he writes that almost all of the binary relations that we can imagine in use here find some meaningful interpretation, but here we have 12 simple, visually suggestive, well-named expressions using the language of maps and poles. That's a good start. Can we find more?

Don't Trap When You Can Verify

May 11, 2023

The other day I turned trapping off:

      600⌶1
2 

And attempted to run a user command:

      ]display ⍳10
VALUE ERROR: Undefined name: exact
findCmdPos[1] exact←{6::⍵ ⋄ exact}~ASN ⍝ exact match?

...which fails due to a micro trap.

I'm not picking on user commands here, my apps do this all over the place and it's a bad idea. With trap control set to 1, virtually no aspect of my apps will run. I don't think that should be. Error guards are seductive because they are terse. It's a little annoying to write:

      {0=⎕NC 'exact':⍵ ⋄ exact}

But the explicit test is a better practice. Sure, we can turn trap control on and off, we can put a stop flag in a function to get us to the point where we can safely turn trapping off to proceed to the error we are looking for, but it's all messy.

There is virtually no scenario during development where we want a micro trap like this to not work. We are abusing the error guard.

Many times we can avoid micro traps and even guards by refactoring. Micro traps are often a sign of technical debt: we have no idea how or why a certain state arises, but it does, so we trap around it. Regardless, if we must handle the case instead of finding and eliminating the root cause, it is better to explicitly test for it.

So this proscription is now added to the Dyalog APL Dont's

Excel Column Names

May 8, 2023

Phase I, problem 3, of the 2020 Dyalog Programming Contest, Excel-lent Columns is stated thus:

A Microsoft Excel spreadsheet numbers its rows counting up from 1. However Excel's columns are labelled alphabetically — beginning with A–Z, then AA–AZ, BA– BZ, up to ZA–ZZ, then AAA–AAZ and so on. Write a function that, given a right argument which is a character scalar or nonempty vector representing a valid character Excel column identifier between A and XFD, returns the corresponding column number

Hint: The Decode function X⊥Y.

Examples:

      (fn) 'A'
1
      (fn) 'APL'
1104

The solution is concise:

      N2I←{26⊥⎕A⍳⍵}
      N2I¨'A' 'Z' 'AA' 'AZ' 'BA'
1 26 27 52 53

With such a simple solution, one would think the inverse would be fairly easy. That is, given an integer, return the corresponding column name. If decode solves it one way, certainly encode should solve it the other way:

      {(' ',⎕A)[1+26 26⊤⍵]}¨1 26 27 52 53 
 A  A   AA  B   BA 

Clearly not correct. The problem is that the column names are not plain old base-26, but rather bijective base-26, as a recent August 22, 2022 answer to an old question on Stack Overflow makes clear.

This is not handled well by encode. While it may be possible to post-process the result of encode to make this work, I have not found a solution in this direction. From the referenced question and answer we can use recursion to compute the correct answer:

      I2N←{
           ⍺←⎕A
           n←≢⍺
           i←{q←¯1+⌈⍵÷n
              a←⍵-n×q
              q=0:,a
              a,⍨∇ q}⍵
           ⍺[i]
       }
       I2N¨1 26 27 52 53
 A  Z  AA  AZ  BA  

Both of these functions are fairly easy to convert to work on vectors, but it does get a little messy.

The function I2N works for any number of digits, which is nice. But this being APL for the practical programmer, we note that Excel columns don't exceed ZZZ (in fact much less) so it is easy to generate all possible Excel column names:

      n←⊃,/,¨∘.,\3⍴⊂,¨⎕A
      10↑n
 A  B  C  D  E  F  G  H  I  J 
      ¯10↑n
 ZZQ  ZZR  ZZS  ZZT  ZZU  ZZV  ZZW  ZZX  ZZY  ZZZ 

With this in hand, and precomputed if we are worried about performance, we can trivially solve both the original problem and its inverse, with a single self-inverse function:

      ColumnLookup←{
          ⍝ ⍵ ←→ Column Index or Name
          ⍝ ← ←→ Column Name or Index
          ⍺←⊃,/,¨∘.,\3⍴⊂,¨⎕A
          2=≡⍵:⍺⍳⍵
          ⍺[⍵]
          }   
       ColumnLookup 1 26 27 52 53
 A  Z  AA  AZ  BA 
       ColumnLookup ColumnLookup 1 26 27 52 53
1 26 27 52 53

If we precompute the column names, this will be the fastest and the simplest solution, though all the solutions are petty fast, even with an each.

More posts...