Symmetries in boolean scans

Array languages like APL are famous for using many pretty squiggles for representing built-in functions. These are called "primitives" and are different from user-defined functions, because the interpreters know about them and can do fancy optimizations with them, like recognizing special combinations [1]. APL programmers have come to rely on these optimizations, for example the vectorization of some combinations like +/ (sum). if you were to feed your typical APL interpreter the function {⍺+⍵}/ - which is functionally equivalent to +/ [2] since {⍺+⍵} is just a dfn [3] over + - the interpreter would execute it much slower, not just because executing the abstraction does two function calls per element (one for the dfn, one for the primitive +) but because it does any at all. Any respectable APL has a tight loop implemented in native code dedicated to this exact combination, which is why APL can sometimes compete with languages that compile to native code. Table of Contents Scans and folds Algorithmic esoterica Case study: Resolving quotes Boolean scans: how many do we really need? Scan composition rules Truth table shuffles Conclusion Appendix A. Brainstorming and observations Truth tables as finite state machines Invariants under the given transformations Appendix B. Efficient implementation of boolean scans Xor And Less-than Scans and folds fold is a higher order function generalizing the concept of iterating over an ordered collection repeatedly calling a binary function that takes as inputs an accumulator and an element of the collection, and returns a new accumulator. scan is the same, but instead of returning the final value of the accumulator it returns a collection of all intermediate values the accumulator took over the course of the iteration. In both cases an initial value may or may not be provided, and in the second case the first element is treated as an initial value, and is returned unchanged, concatenated with the scan of the rest of the collection. APL represents these functions with the operators / and \, so that 10 = +/ 1 2 3 4 1 3 6 10 = +\ 1 2 3 4 In the rest of this article, I’ll be using a fantasy dialect of APL modified to have better behaved fold and scan semantics [4] to write some functional equations. If you don’t know APL, don’t worry about it, just pretend this is the scan from any traditional functional language like Lisp, Haskell, Ocaml, etc. The main equations will also be translated to Haskell. Algorithmic esoterica When I say APLers rely on these, I really mean it! scans, folds, reverse scans, with the operators min, max, plus, times are all familiar, if not even routine operations for the average python programmer who is comfortable with numpy, because they really are useful. Folding (from the right) with subtraction gives an alternating sum, that’s cute. APL programs go beyond that. What does scanning with the less-than function do? scanning with not-equal? folding with… modulo? [5] The issue here is that APL needs escape hatches to handle data dependencies in algorithms, both because it’s syntactically awkward to write loops and because explicitly iterating over an array in APL is mind-numbingly slow when compared to the speed at which the primitive functions run. Scans and folds are a very general way to accumulate information and "move it around" in the array, and they’re APL’s most idiomatic way to do so. Case study: Resolving quotes Say you have a string of text containing quote characters, and you want to tell which positions in the string are inside a pair of quotes or not: if you were to write that in C you’d do something like this: bool in_quotes = false; for (size_t i = 0; i < n; ++i) { if (string[i] == '"') { in_quotes = !in_quotes; } } While in APL you would write the following, where the result is an array containing the values of in_quotes from the previous example. The idea is to scan over the boolean results from comparing each character in the string with the " character. in_quotes ← ≠\string='"' To see why this works, let’s make the C version branchless by encoding the if statement into arithmetic; to make the similarity more apparent we can write != where ordinarily ^ would be more natural, on the values 0 and 1 they do the same thing. bool in_quotes = false; for (size_t i = 0; i < n; ++i) { in_quotes = in_quotes != (string[i] == '"'); } Boolean scans: how many do we really need? APL has a lot of primitives. it’s the only language I know of which has all non-trivial binary boolean functions built in: here they are, next to their truth tables. Common name 00 01 10 11 ∧ and 0 0 0 1 > greater than 0 0 1 0 < less than 0 1 0 0 ≠ not equal (xor) 0 1 1 0 ∨ or 0 1 1 1 ⍱ nor 1 0 0 0 = equal 1 0 0 1 ≥ greater than or equal 1 0 1 1 ≤ less than or equal (implication) 1 1 0 1 ⍲ nand 1 1 1 0 This is an issue on an implementer’s side, because many primitives mean many combinations, and writing decent code for each of them costs in labour as well as executable size (therefore instruction cache). Moreover, what qualifies as decent code for a boolean scan is a much higher bar than the snippet I showed above: APL uses packed bit vectors to represent boolean arrays, meaning that these operations have the potential to consume tens of elements per CPU cycle, while by a quick benchmark a naive implementation would handle about 0.6 elements per cycle [6] Telling which of these are really useful only looking at the truth tables is not trivial, and it really sucks as a user to learn that the operation that precisely solves your problem is shoddily implemented. Is there some way that we can reduce the implementation work without sacrificing the performance? Scan composition rules The structure of the scan ⍺ f\ ⍵ is as follows: Suppose we want to do some pre-processing with a function g to alter the behaviour of the scan: what we’d end up with is a data flow of this kind: The motivation for looking at this is that preprocessing a boolean array with a unary scalar function is just about the cheapest thing we could do, in fact there is only one non-trivial boolean unary scalar function: boolean negation. Let’s keep this observation aside for now, and ask ourselves: is this operation still a scan? If so, what function operand should scan take to produce this result? It’s apparent that the right argument to f is being fed through g at each step in the iteration, so the answer is {⍺ f (g ⍵)}, which brings us to the simple equation ⍺ f\ g¨ ⍵ ←→ ⍺ (f∘g)\ ⍵ Equivalent Haskell scanl f x (map g ys) = scanl (\x y -> f x (g y)) x ys If g is any function, where ∘ is APL’s composition operator "jot" that satisfies ⍺ f∘g ⍵ ←→ ⍺ f (g ⍵) It’s a little trickier to see what effect post-processing with g would have: It may look exactly like before, but notice that the input to each subsequent f call is not the same as the value that is sent to the output array, so this is not a scan! To fix this, let’s assume that g has a left inverse g-1 and insert it in between each pair of calls: This is a scan diagram using the function {g ((g⍣¯1) ⍺) f ⍵}, except the initial value x has been preprocessed with g. this gives the equation: g¨ ⍺ f\ ⍵ ←→ (g ⍺) (g⍤(g⍣¯1⍛f))\ ⍵ Equivalent Haskell map g (scanl f x ys) = scanl (\x y -> g (f (ig x) y)) (g x) ys Again some composition operators have been used: (g⍣¯1) g ⍵ ←→ ⍵ ⍝ APL can sometimes find inverses by itself! ⍺ (g⍤f) ⍵ ←→ g (⍺ f ⍵) ⍺ (g⍛f) ⍵ ←→ (g ⍺) f ⍵ And finally we can put these two relations together to find a third. g ⍺ f\ g ⍵ ←→ (g ⍺) g⍤(g⍣¯1⍛f∘g)\ ⍵ Equivalent Haskell map g (scanl f x (map g ys)) = scanl (\x y -> g (f (ig x) (g y))) (g x) ys Truth table shuffles In particular, we are interested in seeing which pairs of primitives are related by one of these three relations, where g is the negation function ~. We start with the truth tables of our primitives and analyze how they change under the transformations described above. We represent all of the truth tables at once as the array a with shape 10 2 2 a ┌┌→──┐ ↓↓0 0│ ││0 1│ ││ │ ││0 0│ ││1 0│ ││ │ ││0 1│ ││0 0│ ││ │ ││0 1│ ││1 0│ ││ │ ││0 1│ ││1 1│ ││ │ ││1 0│ ││0 0│ ││ │ ││1 0│ ││0 1│ ││ │ ││1 0│ ││1 1│ ││ │ ││1 1│ ││0 1│ ││ │ ││1 1│ ││1 0│ └└~──┘ Composing on the right argument with ~ is the same as reversing the last axis with the ⌽ function: pre ← ⌽[2] a Negating the output is just a matter of negating each entry of the table; if we do this, we must also negate the left argument, which we do by reversing the first axis of each truth table (the middle axis here). post ← ~ ⌽[1] a And of course we can do both transformations at once both ← ~ ⌽[1] ⌽[2] a Now we can find out who’s related to whom by searching for the truth tables we got in the original array: index ← ↑(⊂a)⍳¨a pre post both ┌→──────────────────┐ ↓0 1 2 3 4 5 6 7 8 9│ │1 0 5 6 7 2 3 4 9 8│ │7 4 9 3 1 8 6 0 5 2│ │4 7 8 6 0 9 3 1 2 5│ └~──────────────────┘ Now that we know this, we can index into the list of the symbols the truth tables referred to: '∧><≠∨⍱=≥≤⍲'[index] ┌→─────────┐ ↓∧><≠∨⍱=≥≤⍲│ │>∧⍱=≥<≠∨⍲≤│ │≥∨⍲≠>≤=∧⍱<│ │∨≥≤=∧⍲≠><⍱│ └──────────┘ Now, how do we interpret this? along the top row are the original symbols; the second row are the symbols that are related to the top row by the first scan equation we derived above, i.e. ⍺ p\ ~⍵ ←→ ⍺ q\ ⍵. The third and fourth row, similarly, are related to the first via ~ (~⍺) p\ ⍵ ←→ ⍺ q\ ⍵ and ~ (~⍺) p\ ~⍵ ←→ ⍺ q\ ⍵ Conclusion We can see that the set ∧, <, ≠ covers all columns at least once, therefore if we provide fast implementations of each of these, we can derive decent implementations of the others by just applying these symmetries. This cuts down on implementation time and executable size, without completely sacrificing performance. None of this is completely new, by the way. The trick ⍺ ≠\ ⍵ ←→ ⍺ =\ ~⍵ is well known among K programmers, since K doesn’t have a builtin not-equal operator. In the same vein, many of these shortcuts