趣味算法

https://sandbox.bio/concepts/bwt

递归生成自己的程序，或者递归互相生成的程序。《Hacker's Delight》在序言里的第一题， 想着就头疼，结果至今没看下去的书，对不起当年送我书的叔叔阿姨。

最近看了 Tsoding 的 讲解，终于理解了一点点。我记得当时最初的想法是，直接 print 一个字符串，长度一定小于包含它的程序本身 -> 一定需要某种扩充的办法 -> 只能用 C 宏展开。

实际上，在运行时能展开就行，用变量 + 特殊字符的替换即可，而且这个替换的算法也非 常简单：不动点。让我用一个特殊的栈语言不断来接近 C，来展示为什么可以这样做：

p

其中 p 是一个打印 p 的函数，也就是这门语言在“打印”这件事情上的不动点，那这个 程序就是一个 Quine。现在试着由这门语言逐渐接近 C，让 p 不再能打印自己。在下面 的讨论中，假定这门语言把包含 ? 的 atom 都当成字符串：

? p

这里 ? 是一个符号，~p~ 是一个它函数，当它见到 ? 时，打印 ? p 。这里开始，不 动点由两个东西组成，一个是 ? 这个格式字符串，一个是 p 这个稍微有点特殊的 打印函数。现在让 p 不那么特殊：

?p p

p 基本就是一个普通的打印函数，但是如果见到 ? ，它会把格式字符串打印一遍（是 不是和 C 越来越像），不做任何填充。现在加上一堆可能有副作用但是不会打印东西的操 作 a b （继续无视这门语言里对字符串的神奇解析）：

a a_?b_p b p

因为 a 和 b 对于“打印”这件事情没有任何影响，~p~ 也不打印自身，所以最终会输出 a_a_?b_p_b_p ，就是这段程序本身。

到此为止，已经找到了一个通用的不动点模式：由一个特殊的格式字符串和配套的打印函数 组成，中间可以插入任何不打印东西的语句。也就是说可以加入字符串 quoting 规则和函 数定义：那么再接下来，只需要去掉这门语言解析时对含 ? 的 atom 的特殊处理（也就 是引入常见的字符串和 quoting 规则），和用不原生支持 ? 的 print 实现 p 即可。

由此 Tsoding 提出了两个扩展：

• 因为这个不动点运行前后插入任何不打印的语句，它执行时可以有各种副作用。 self-hosting 的编译器，如 C 的编译器，本质上也是不动点，那么它执行时就可以隐藏 各种副作用，比如持续在编译器里插入后门，而不体现在格式字符串（也就是编译器源码 里），这就是 the Ken Thompsen Hack。
• 可以构成 Quine 的环。其思路是，让 ? 不动点包含环上每个节点的程序内容（也就是 说 N 个节点对应的格式字符串有 N 个 ? ），然后每个节点只扩展下一个节点对应的 那一段格式字符串。Quine 的一个 集大成者，搞了 128 个语言的环。

https://github.com/johnBuffer/StableIndexVector 用三个数组实现 O(1) 的增删改查， 数据结构很好理解。