布尔扫描的对称性

# 布尔扫描中的对称性 来源：https://ap29600.github.io/boolean_scans.html 像APL这样的数组语言以大量精巧的符号表示内置函数而闻名。这些符号被称为"原语"，与用户定义的函数不同，因为解释器能够识别它们并对其进行高级优化，例如识别特殊组合[1](https://ap29600.github.io/boolean_scans.html#_footnotedef_1)。APL程序员已经依赖这些优化，例如某些组合（如`\+/`（求和））的向量化处理。如果你将函数`\{⍺+⍵\}/`（在功能上等同于`\+/`[2](https://ap29600.github.io/boolean_scans.html#_footnotedef_2)，因为`\{⍺+⍵\}`只是对`\+`的dfn[3](https://ap29600.github.io/boolean_scans.html#_footnotedef_3)包装）输入给典型的APL解释器，其执行速度会慢得多——不仅因为执行抽象层会对每个元素进行两次函数调用（一次调用dfn，一次调用原语`\+`），更因为它确实需要执行这些调用。任何正规的APL实现都会为这种特定组合配备一个用原生代码实现的紧密循环，这也是APL有时能够与编译为原生代码的语言相媲美的原因。 ## 目录 - [扫描与折叠](#scans-and-folds) - [算法奥秘](#algorithmic-esoterica) - [案例分析：解析引号](#case-study-resolving-quotes) - [布尔扫描：我们真正需要多少？](#boolean-scans-how-many-do-we-really-need) - [扫描组合规则](#scan-composition-rules) - [真值表变换](#truth-table-shuffles) - [结论](#conclusion) - [附录A：头脑风暴与观察](#appendix_a_brainstorming_and_observations) - [真值表作为有限状态机](#truth_tables_as_finite_state_machines) - [给定变换下的不变量](#invariants_under_the_given_transformations) - [附录B：布尔扫描的高效实现](#appendix_b_efficient_implementation_of_boolean_scans) - [异或](#xor) - [与](#and) - [小于](#less_than) ## 扫描与折叠 - `fold` 是一个高阶函数，概括了迭代遍历有序集合的概念：反复调用一个二元函数，该函数接收累加器和集合中的元素作为输入，并返回新的累加器。 - `scan` 与折叠相同，但不是返回累加器的最终值，而是返回累加器在迭代过程中取值的所有中间值的集合。 在这两种情况下，初始值可以提供也可以不提供。在后一种情况下，第一个元素被视为初始值，原样返回，并与剩余集合的扫描结果拼接。APL用运算符`/`和`\`表示这些函数，因此： ``` 10 = +/ 1 2 3 4 1 3 6 10 = +\ 1 2 3 4 ``` 在本文剩余部分，我将使用一个虚构的APL方言（具有更好行为的折叠和扫描语义[4](https://ap29600.github.io/boolean_scans.html#_footnotedef_4)）来书写一些函数方程。如果你不了解APL，请别担心，可以将其视为任何传统函数式语言（如Lisp、Haskell、Ocaml等）中的扫描。主要方程也会同时翻译成Haskell。 ## 算法奥秘 当我说APL程序员依赖这些时，我确实是认真的！扫描、折叠、反向扫描，配合min、max、加、乘等运算符，对于熟悉numpy的普通Python程序员来说都是熟悉甚至常规操作，因为它们确实非常有用。从右折叠（折叠）与减法结合可以给出交错求和，这很有趣。但APL程序远不止于此。用小于函数扫描会怎样？用不等于扫描呢？用……取模折叠呢？[5](https://ap29600.github.io/boolean_scans.html#_footnotedef_5) 问题在于，APL需要"逃逸舱"来处理算法中的数据依赖，一方面是因为在APL中写循环语法笨拙，另一方面是因为与原生函数运行速度相比，在APL中显式遍历数组慢得令人发指。扫描和折叠是积累信息并在数组中"移动"信息的非常通用的方式，也是APL中最惯用的方法。 ## 案例分析：解析引号 假设你有一个包含引号字符的文本字符串，你想判断字符串中哪些位置位于一对引号内部：如果用C语言编写，代码大致如下： ```c bool in_quotes = false; for (size_t i = 0; i < n; ++i) { if (string[i] == '"') { in_quotes = !in_quotes; } } ``` 而在APL中，你会这样写，其结果是一个数组，包含上例中`in_quotes`的值。其思想是扫描字符串中每个字符与`"`字符比较的布尔结果。要理解这为何有效，我们可以让C版本变得无分支，将`if`语句编码为算术运算；为了更清晰地展现相似性，我们可以在`0`和`1`的值上使用`\!=`（在这些值上，它与`^`作用相同）： ```c bool in_quotes = false; for (size_t i = 0; i < n; ++i) { in_quotes = in_quotes != (string[i] == '"'); } ``` ## 布尔扫描：我们真正需要多少？ APL有很多原语。它是我所知的唯一内置所有非平凡二元布尔函数的语言：以下是它们及其真值表： | 通用名 | 00 | 01 | 10 | 11 | 符号 | |--------|----|----|----|----|------| | 与 | 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 | `⍲` | 这对实现者来说是个问题，因为众多原语意味着众多组合，为每个组合编写优质代码需要投入人力，并增加可执行文件大小（从而影响指令缓存）。此外，对布尔扫描来说，"优质代码"的标准远高于我之前展示的代码段：APL使用打包位向量表示布尔数组，这意味着这些操作每个CPU周期可能处理数十个元素，而快速基准测试显示，朴素实现每个周期大约只能处理0.6个元素[6](https://ap29600.github.io/boolean_scans.html#_footnotedef_6)。 仅从真值表判断哪些操作真正有用并不简单，而且作为用户，当你发现精确解决你问题的操作实现得糟糕时，感觉真的很糟。有没有什么办法可以在不牺牲性能的情况下减少实现工作量？ ## 扫描组合规则 扫描`⍺ f\ ⍵`的结构如下： 扫描基础结构 假设我们想用函数`g`进行一些预处理来改变扫描的行为：最终的数据流将是这样的： 扫描预处理 观察这一点的动机在于，用一元标量函数预处理布尔数组几乎是我们能做的最廉价操作，实际上只有一个非平凡布尔一元标量函数：布尔取反。让我们先把这个观察放在一边，问问自己：这个操作仍然是扫描吗？如果是，扫描应该取什么函数操作数才能产生这个结果？ 很明显，`f`的右参数在每次迭代中都通过`g`进行传递，因此答案是`\{⍺ f \(g ⍵)\}`，这导出了简单的等式： 等价Haskell代码： ```haskell scanl f x (map g ys) = scanl (\x y -> f x (g y)) x ys ``` 如果`g`是任意函数，其中`∘`是APL的组合运算符"jot"（满足……），那么后处理`g`的效果可能更复杂： 扫描后处理 这看起来和之前一模一样，但注意每次后续`f`调用的输入与发送到输出数组的值不同，因此这不是扫描！为了修正这一点，我们假设`g`有左逆`g\-1`，并在每对调用之间插入它： 扫描复合结构 这是使用函数`\{g \((g⍣-1) ⍺\) f ⍵\}`的扫描图，只是初始值`x`已经用`g`预处理过。这给出等式： ``` g ⍺ f\ ⍵ ←→ (g ⍺) (g⍤(g⍣-1⍛f))\ ⍵ ``` 等价Haskell代码： ```haskell map g (scanl f x ys) = scanl (\x y -> g (f (ig x) y)) (g x) ys ``` 这里再次使用了一些组合运算符： ``` (g⍣-1) g ⍵ ←→ ⍵ ⍝ APL有时能自己找到逆元！ ⍺ (g⍤f) ⍵ ←→ g (⍺ f ⍵) ⍺ (g⍛f) ⍵ ←→ (g ⍺) f ⍵ ``` 最后，我们可以将这两个关系结合起来找到第三个： ``` g ⍺ f\ g ⍵ ←→ (g ⍺) g⍤(g⍣-1⍛f∘g)\ ⍵ ``` 等价Haskell代码： ```haskell map g (scanl f x (map g ys)) = scanl (\x y -> g (f (ig x) (g y))) (g x) ys ``` ## 真值表变换 具体来说，我们感兴趣的是查看哪些原语对通过这三种关系之一相关联，其中`g`是取反函数`~`。我们从原语的真值表开始，分析它们在上述变换下如何变化。我们将所有真值表一次性表示为形状`10 2 2`的数组`a`： ```apl 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│ └└~──┘ ``` 用`~`组合右参数等同于用`⌽`函数反转最后一轴： 取反输出只需将表中每个条目取反；如果我们这样做，也必须取反左参数，方法是反转每个真值表的首轴（这里是中间轴）。当然，我们可以同时执行这两种变换。现在，我们可以通过在原始数组中搜索变换后的真值表来找出谁与谁相关： ```apl index ← ↑(⊂a)⍳̈a pre post both ``` ```apl ┌→──────────────────┐ ↓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│ └~──────────────────┘ ``` 现在我们知道这一点，就可以索引到真值表对应的符号列表： ```apl ┌→─────────┐ ↓∧><≠∨⍱=≥≤⍲│ │>∧⍱=≥<≠∨⍲≤│ │≥∨⍲≠>≤=∧⍱<│ │∨≥≤=∧⍲≠><⍱│ └──────────┘ ``` 现在，如何解释这个结果？顶行是原始符号；第二行是通过我们推导的第一个扫描方程（即`⍺ p\ ~⍵ ←→ ⍺ q\ ⍵`）与顶行相关的符号。第三和第四行类似地通过`~ (~⍺) p\ ⍵ ←→ ⍺ q\ ⍵`和`~ (~⍺) p\ ~⍵ ←→ ⍺ q\ ⍵`与第一行相关。 ## 结论 我们可以看到集合`∧`、`<`、`≠`至少覆盖了所有列一次，因此如果我们为这些提供快速实现，就可以通过应用这些对称性推导出其他操作的良好实现。这减少了实现时间和可执行文件大小，而不会完全牺牲性能。顺便说一句，这些并非全新内容。技巧`⍺ ≠\ ⍵ ←→ ⍺ =\ ~⍵`在K程序员中广为人知，因为K没有内置不等于运算符。同样地，CBQN解释器对较少见的组合也使用了许多这样的快捷方式(https://github.com/dzaima/CBQN/blob/af583e19566a032b89e0077b866b0ba0dcc2a365/src/builtins/scan.c#L328)。 ## 附录A：头脑风暴与观察 我最初在APL farm discord服务器上讨论了这个话题，一些用户发表了有趣的评论： ### 真值表作为有限状态机 在K语言中，形式`x f\ y`等价于`x a\ y`形式，其中`a`是一个矩阵，包含`f`在非负整数对上的值。这种形式根据`a`中定义的状态转换在序列`y`上推进状态机[7](https://ap29600.github.io/boolean_scans.html#_footnotedef_7)。在这种解释下，我们应用于真值表的具体变换取代了我们定义的原始方程中的组合运算符。 ```apl ( x a\ ~y) = x ( |'a)\ y (~ x a\ y) = (~x) (~| a)\ y (~ x a\ ~y) = (~x) (~||'a)\ y ``` 等价Haskell代码： ```haskell runFsm a x ys = scan (\x y -> (a !! x) !! y) x ys runFsm a x $ map (1 -) ys = runFsm x ( map reverse a) ys map (1 -) $ runFsm a x ys = runFsm (1 - x) (map (map (1 -)) $ reverse a) ys map (1 -) $ runFsm a x $ map (1 -) ys = runFsm (1 - x) (map (map (1 -)) $ map reverse $ reverse a) ys ``` ### 给定变换下的不变量 我们给出的变换会排列表的行或列，和/或取反条目。这意味着表中1的数量要么保持等于2，要么在1和3之间翻转[8](https://ap29600.github.io/boolean_scans.html#_footnotedef_8)。此外，由于变换可交换且是自逆的，我们的关系是等价关系；我们推断`=`和`≠`属于自己的等价类，其中一个变换固定两个操作，其他变换至少填充两个更多。对于这些，可以应用变换`~⌽[0]a`使得有3个0，然后应用`⌽[1]a`确保单个`1`条目出现在第二列。仅有的两种可能性通过`1`值是在`a[1;1]`（给出`∧`）还是`a[0;1]`（给出`<`）来区分。 ## 附录B：布尔扫描的高效实现 ### 异或 机器字上的异或扫描可以通过典型的前缀加倍技术（类似于Bit Twiddling Hacks(https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel)描述的方法）用几条指令高效实现： ```c uint64_t xorscan_word (uint64_t word) { word ^= word << 1; word ^= word << 2; word ^= word << 4; word ^= word << 8; word ^= word << 16; word ^= word << 32; return word; } ``` 我们只需要处理前一个字的进位。典型的做法是将它与`word`的第一位异或，但这实际上不是最优的：注意`carry`在每次迭代开始时需要，但只在最后更新，这将所有迭代捆绑在一个很长的依赖链中。 ```c void xorscan_bad (bool initial, uint64_t *words, size_t n) { uint64_t carry = (uint64_t)initial; for (size_t i = 0; i < n; ++i) { uint64_t word = xorscan_word(words[i] ^ carry); carry = word >> 63; words[i] = word; } } ``` 这编译成以下核心循环，运行速度约为每周期3-4位（所有计时都是针对缓存中热数据的，否则内存延迟将主导运行时间）： ```asm .loop: xor (%rdx),%rdi add $0x8,%rdx lea (%rdi,%rdi,1),%rax xor %rdi,%rax lea 0x0(,%rax,4),%rcx xor %rcx,%rax mov %rax,%rcx shl $0x4,%rcx xor %rcx,%rax mov %rax,%rcx shl $0x8,%rcx xor %rcx,%rax mov %rax,%rcx shl $0x10,%rcx xor %rcx,%rax mov %rax,%rcx shl $0x20,%rcx xor %rcx,%rax mov %rax,%rdi mov %rax,-0x8(%rdx) shr $0x3f,%rdi cmp %rdx,%rsi jne .loop ``` 在具有超标量执行的CPU上，如果我们能将前一个结果的使用延迟到尽可能晚的时间点会很好。幸运的是，异或满足结合律，因此我们只需将进位位广播到最终结果的每个位置：现在CPU可以在上一个结果就绪之前自由地开始执行下一个迭代的`xorscan_word`。 ```c void xorscan_good (bool initial, uint64_t *words, size_t n) { uint64_t carry = - (uint64_t)initial; for (size_t i = 0; i < n; ++i) { uint64_t word = carry ^ xorscan_word(words[i]); carry = - (word >> 63); words[i] = word; } } ``` 这快得多，每个周期可处理多达10.5位。