Ruby TRICK 2015 银奖作品 ksk_1:一行无分支、无算术代码生成 Collatz 序列的原理剖析-开发者社区

Ruby TRICK 2015 银奖作品 ksk_1:一行无分支、无算术代码生成 Collatz 序列的原理剖析

【免费下载链接】rubyThe Ruby Programming Language项目地址: https://gitcode.com/GitHub_Trending/ru/ruby

本文以 Ruby 官方仓库归档的 TRICK 2015 竞赛银奖作品ksk_1为主体,依据作者 Keisuke Nakano 的亲笔说明文档 remarks.markdown,完整还原这个"没有任何条件分支和算术运算"的 Collatz(3x+1)序列程序的运行方式、混淆结构与底层技巧:它如何仅靠eval、字符串拼接、正则表达式匹配下标这三个语言原语,就模拟出了 HOTPO(Half-Or-Triple-Plus-One)过程中的奇偶判断。读完后,你能理解 Ruby 中%记法、字符串乘法、Array#join、Regexp#=~与反向引用在极端场景下如何组合成"计算",并能看懂这段 106 字符单行源码背后的推导过程。

背景:TRICK 2015 竞赛与"最差代码"的荣耀

该作品位于 Ruby 仓库的sample/trick2015/目录,按 README.md 的说明,此目录收录的是TRICK 2015(第 2 届 Transcendental Ruby Imbroglio Contest,为 rubyKaigi 举办的 Ruby 竞赛)的获奖作品。目录中同时收录了五份获奖程序:kinaba(金奖 "Best piphilology")、ksk_1(银奖 "Most unreadable ALU",最不可读的算术逻辑单元)、monae(铜奖 "Doubling amphisbaena award")、eregon与ksk_2。本仓库中 ksk_1/entry.rb 的作者信息记录在 authors.markdown 中:Keisuke Nakano。

需要特别强调的是,README 对这批文件给出了明确的警示:

THESE ARE BAD EXAMPLES! You must NOT use them as a sample code.

它们的存在意义是展示 Ruby 语言的表达力边界,而不是可维护的工程代码。本文的所有分析都应以这一前提为前提:你应当"看懂"它,但绝不应"模仿"它。

运行方式与已验证的 Ruby 版本

按照 remarks.markdown 的 "Remarks" 一节,程序以一个正整数作为参数运行:

ruby entry.rb 27

原文档给出的已确认可运行的版本如下:

ruby 1.9.3p385 (2013-02-06 revision 39114) [x86_64-darwin11.4.2] ruby 2.0.0p481 (2014-05-08 revision 45883) [universal.x86_64-darwin13] ruby 2.2.3p173 (2015-08-18 revision 51636) [x86_64-linux]

也就是说,作品的验证范围是 2015 年及以前的 Ruby。从源码结构看,当前 Ruby 仓库主线已经演进到 4.0 开发版(include/ruby/version.h 中RUBY_API_VERSION_MAJOR为 4,RUBY_VERSION_PATCHLEVEL为 -1),原文档并未在新版本上复验;不过程序依赖的%记法、eval、正则、字符串乘法等均为长期稳定的核心特性,从语言特性角度判断其在现代 Ruby 上运行的概率较高,但这一点属于推断而非文档确认的事实。

程序语义:打印 Collatz 序列

"Description" 一节定义了程序行为:程序打印以给定数字为起点的 Collatz 序列,即反复对前一个数施加 HOTPO 过程,直到数字变为 1:

如果数字是偶数,除以 2;否则乘以 3 再加 1。

原文档同时交代了数学背景:Collatz 猜想断言无论从哪个数开始,该过程最终都会终止;这至今仍是未解问题,因此程序对某些数可能永不终止。目前已知的结论是,在 2^60 以下不存在反例。

程序输出的效果即:每行打印当前值,然后按 HOTPO 规则更新,直到打印出1后结束。

混淆源码全貌:一行 106 字符

"Internals" 一节开宗明义:

The source code does not contain either conditional branch or arithmetic operation.

整个 entry.rb 只有一行、106 个字节:

%%%while eval '_=%%r%%(.)...\1=%%=~[%%%%,,,,,%%%s ?=]*%%%%%%#"]*%%%%3x+1?%%'.% %%",%*p(_||=eval($**%%%))

肉眼几乎无法阅读。按原文档的描述,这段代码通过以下手段被混淆:

%记法(percent notation,以%作为定界符的字符串/正则/数组字面量);
*(字符串乘法重复、数组 join 等)与%格式化(String#%,支持%s、%r、%%等占位符);
语句结构的重组(restructuring)。

值得注意的是,这一行里没有任何if/case/三元运算符,也没有+、-、*(算术意义上的)、/作用于整数——"乘以 3 加 1"这一核心算术被完全隐藏在了字符串与正则的语义里。这就是它获得 "Most unreadable ALU"(最不可读的算术逻辑单元)银奖的原因。

可读等价形式

原文档给出了一个等价的、可读的程序,它是理解一切技巧的基准:

n = ARGV[0].to_i begin # do nothing end while begin puts n n = (/(.)...\1=/ =~ eval('[",,,,,"'+ '",'*n + ' ?=].join#"].join("3x+1?")')) end

结构上很简单:begin/end while无限循环,每轮先puts n,然后用一行表达式计算n的 HOTPO 后继;当该表达式返回nil(发生在n == 1时)时循环条件为假,循环退出。

整个技巧都浓缩在这一行:

n = (/(.)...\1=/ =~ eval('[",,,,,"'+ '",'*n + ' ?=].join#"].join("3x+1?")'))

它完成了两件事:

构造一个长度和内容都依赖当前n的 Ruby 代码字符串并eval求值,得到一个普通字符串;
用正则/(.)...\1=/对该字符串执行=~。Regexp#=~返回正则首次匹配的起始下标(无匹配则返回nil),这个下标恰好就是 HOTPO 过程应产生的新值:n为偶数时是n/2,为奇数(且大于 1)时是3n+1,n == 1时必须匹配失败返回nil以终止循环。

于是问题被转化为一个纯文本工程问题:如何仅靠字符串拼接,构造出一个让(.)...\1=恰好在n/2或3n+1处命中的字符串。

核心技巧:用双引号的"开/合角色交替"模拟奇偶分支

原文档指出的关键(kew)是:eval表达式中使用了n个长度为 2 的不完整片段",。其中双引号"在 Ruby 源码里交替扮演"字符串开始"和"字符串结束"两种角色——拼接多少个这样的片段,最后一个引号是"开"还是"合",取决于n的奇偶性。这正是整个程序里唯一一处"条件分支":它不是写在代码里,而是写在引号配对的奇偶性里。

偶数情形:eval 结果为逗号串,匹配落在 n/2

当n为偶数时,eval内部的代码字符串等价于:

'[",,,,,"'+ '",' + '",' + '",' + ... + '",' + ' ?=].join#...' # 即拼接后: '[",,,,,"",",",...", ?=].join#...'

由于片段个数为偶数,最后一个双引号扮演的是闭合角色,因此#之后的代码被当作注释忽略。这里用到了一个 Ruby 特性:相邻字符串字面量会自动拼接,"ab""cd"等价于"abcd"。

于是整个eval表达式求值得到一个纯字符串:

",,,,,...,="

其中逗号的个数为5 + n/2。此时正则(.)...\1=在字符串末尾匹配到,,,,,=(捕获组(.)与反向引用\1都是逗号,中间...是任意三个字符),起始下标为:

5 + n/2 - 5 = n/2

于是=~返回n/2——恰好是 HOTPO 的偶数分支结果。

奇数情形:插入 3x+1 填充块,匹配落在 3n+1

当n为奇数时,引号配对发生翻转,拼接结果变为:

'[",,,,,"',",",",...,"', ?=].join#" → 求值后得到: ",,,,,,3x+1?,3x+1?,...,3x+1?, ?=].join#"

与偶数情形相比,字符串中多出了(n-1)/2个,3x+1?填充块。每个块长 6 个字符,恰好对应 HOTPO 中"3n+1"相对"(n-1)/2 个偶数步"的步长贡献。正则(.)...\1=此时在接近末尾处匹配?, ?=(捕获组与反向引用都是?),起始下标为:

5 + (n-1)/2 * 6 - 1 = 3n+1

同样精确等于 HOTPO 的奇数分支结果。

n = 1 的终止条件

循环终止依赖匹配失败:n == 1时,(n-1)/2 = 0,字符串中符号?只出现一次,而(.)...\1=要求捕获字符与反向引用字符相同且紧邻=之前,因此匹配必然失败,=~返回nil,while条件为假,程序退出。原文档特别强调这一失败是构造出来的,而非意外。

为什么填充块叫 "3x+1"

原文档补充了一个细节:代码中的3x+1可以是任意四个字符的词,作者选择3x+1纯粹是因为 Collatz 猜想也被称为 "3x+1 problem"。这是一个彩蛋式的命名,不影响任何语义。

涉及的语言特性与仓库源码对照

这个作品用到的每一个 Ruby 语言特性,都对应仓库中的核心实现文件,读者可沿此路径深入:

语言特性	在本作品中的作用	仓库实现位置
`%`记法(percent 字面量)	整行源码以`%`定界符包裹,实现第一层混淆	parse.y(解析器)
`String#%`格式化(`%s`/`%r`/`%%`)	把正则与字符串参数注入格式化模板	string.c
`String#*`字符串乘法	用`'"'*n`复制`n`个`",`片段,是奇偶开关的"拨片"	string.c
`Array#join`	以`3x+1?`为分隔符拼接数组,构造填充块	array.c
相邻字符串字面量拼接(`"ab""cd"`)	让引号交替开合后字符串无缝合并	string.c
`eval`	把"依赖 n 的源代码字符串"求值成普通字符串	eval.c
`Regexp#=~`与反向引用`\1`	用首次匹配下标"表示"计算结果	re.c(封装 Onigmo 正则引擎)

其中两个语义点是理解全文的钥匙:

Regexp#=~的返回值:它不是布尔值,而是首次匹配的整数下标,或nil。作品把"数值结果"直接编码进"文本下标",是整套技巧的支点。
引号奇偶性即分支:'"'*n复制出的引号序列,使同一段源码文本在n为偶/奇时被解析成两种完全不同的程序结构(字符串闭合位置不同,.join(...)调用是否生效、#是否处于注释位随之改变)。Ruby 的"代码即字符串、字符串经eval又是代码"的二阶性质,在这里被用到了极致。