Symmetries in Boolean Scan

The piece analyzes how scan and fold operators behave when applied to Boolean binary primitives in array languages, building algebraic rules for composing scans with preprocessing and postprocessing functions. It shows that applying negation to inputs or outputs and reversing argument order permutes truth tables in predictable ways, producing an equivalence relation that clusters many Boolean operators together; equality and inequality form a distinct singleton class while other operators fall into a few transformable families. The derivations are expressed both in APL-style notation and equivalent Haskell scan/map identities, and a practical example - tracking whether characters lie inside quotes - demonstrates how these composition rules turn data-dependency problems into idiomatic scans.

The work then turns to implementation: a systematic search over truth-table permutations identifies which primitives need distinct native support, and low-level implementations are provided for fast XOR- and AND-scans on 64-bit words. XOR scanning is optimized by broadcasting carry bits and, where available, using carry-less multiply, yielding up to about 10.5 bits processed per CPU cycle; an AND-scan uses the trick word & ~(word+1) and an array-level shortcut so only one word requires a full scan, achieving roughly 8.8 bits per cycle. Assembly snippets and performance figures support the claim that fewer, well-chosen primitives plus symmetry-based rewriting give both conceptual simplification and measurable speedups.