Ouroborus Program - quine-relay 分析

Quine Relay

今天上网时看到有人分享了这个项目:quine-relay,点进去看是这样一个程序:一开始是一段Ruby代码,运行后生成Scala代码,后者运行后生成Scheme代码,如此执行,依次生成了Bash、Smalltalk、Tcl等代码,最后又回到最初的Ruby代码。这类程序有个名字,叫ouroborus programs。Ouroborus即衔尾蛇,是一条正在吞食自己尾巴的蛇,在这里刚好表示循环的概念。

分析

项目的有趣之处在于两点:塑型,把代码组成了特定图案;一生二,二生三,三生一,形成循环往复的衔尾蛇效果。

塑型

先谈塑型。

初始的Ruby程序位于项目根目录下的QR.rb,代码自身组织成衔尾蛇和六芒星的造型,这个看上去相当不容易。在一个所有词法单元只占据一个字符且忽略空白字符的语言(比如Brainfuck)中,把代码组织成任意的图案是很容易的。但是对于Ruby等词法单元并非只占据一个字符的语言,直接将代码排版成特定图案是很困难的。quine-relay采用了一个技巧,在字符串中编码了一段程序用于生成下一种语言的代码,调用eval解释这个字符串。这个字符串表示是忽略空白字符的。文件src/QR.rb.gen.rb末段实现了这一功能:

1
2
3
4
5
Tmpl = File.read("uroboros.txt")
code[-1, 0] = "#" * (Tmpl.count("#") - code.size)
code = Tmpl.gsub(/#+/) { code.slice!(0, $&.size) }
File.write("../QR.rb", code)

Tmpl是衔尾蛇图案的模板文件,可以看作一个蒙版,指定了哪些地方填字符,哪些地方为空格或换行,把最终代码塑型成该图案。

衔尾蛇效果

quine-relay想要实现的逻辑可以表达如下:

1
Ruby {\orig_ruby -> print (Scala {print (Scheme {print orig_ruby})})}

其中省去了其他语言的print。Ruby {...}代表一段Ruby代码,{}中的部分是程序的内容。根据这段逻辑得到的Ruby代码就是orig_ruby,并且orig_ruby被自身引用了。

下面分成两部分来解释实现方式:

  • 实现不同语言的print
  • 在代码中引用自身代码(orig_ruby)

实现不同语言的print

执行一下Ruby程序,再执行依次产生的各语言程序,可以发现它们做的事都是print某个特定字符串,而print的字符串自然就是下一个程序的源代码了。各语言如何print一字符串,不少网页都有收集hello-world的例子,比如:

src/code-gen.rb里有大量编程语言输出字符串的模板代码,比如这段OCaml的:

1
2
3
4
5
6
class OCaml < CodeGen
Ext = ".ml"
Cmd = "ocaml QR.ml > OUTFILE"
Apt = "ocaml"
Code = %q("print_string"+E[PREV])
end

PREV之后会被替换为OCaml生成的下一个编程语言的代码,E则是用于字符串的引号转义,并非看懂需要关注非常重要的点,暂时不用理会。

观察src/QR.rb.gen.rb的头几行,可以发现作者在试图构建单链表效果:

1
2
s = '%(eval$s=%q(#$s))'
CodeGen::List[0..-2].each {|c| s = c.gen_code(s).tr(" \\","X`") }

CodeGen::List[0..-2]就是除去开头结尾的Ruby以外其他各编程语言了,每一个都以需要产生的下一个语言的代码为参数,返回用本语言写成的,返回那段字符串的代码。

在代码中引用自身代码

把Ruby以外的其他编程语言的CodeGen子类都注释掉,在src目录下执行rake ../QR.rb,对QR.rb抽丝剥茧后可以观察到这段核心代码:

1
2
3
eval$s=%q(eval(%w(
puts(eval(%q(%(eval$s=%q
(#$s))))))*""))

这段代码是原始的Ruby写成的quine,执行后的标准输出依然为这段代码自身。理解它需要了解Ruby从Perl学习来的语法:general delimited input,即%w%q这些符号,以及Array重载的*操作符的含义:

先看$s,它是%q()构建的字符串,eval它的效果是再次eval下面的字符串:

1
%w(puts(eval(%q(%(eval$s=%q (#$s)))))) * ""

其中使用了Array#*的方法,即Array#join,因此效果是eval下面的字符串:

1
puts(eval(%q(%(eval$s=%q(\#$s)))))

即输出eval$s=%q(后,输出$s的值,再跟)。这段Ruby quine的逻辑是:

1
2
3
4
eval$s=%q(
输出`eval$s=%q(`
输出$s
输出`)`

字符串$s包含了一段需要eval的代码,代码中包含了$s`实现了自指,这可以看作是一种fixed-point combinator:Y combinator,的实现。

定义函数f,它应用参数t的效果是打印t的代码。根据fixed-point theorem,存在代码n使得f(n)=n,也就是说n会打印自身代码。下面说明这段Ruby代码本质上就是n的一种构造。

$s可以看作一个函数:y = \x -> f (x x)$s中的自指以及eval的解释操作,可以看作把自身作为参数应用给自己:y yy得到参数x后的效果是把x x的代码打印出来。而打印x x需要打印以code形式存在的x和与之关联的以data形式存在的x。考虑到参数传递给y的参数是一个固定值xy,我们不需要写一个通用的能打印任意代码的程序,只需要针对这个特例,实现一个特例。在这里data是$s,code是被eval解释的$s,而所要打印的代码则是eval$s=%q(、一段任意字符串和)

y y(\x -> f (x x)) (\x -> f (x x)),应用一次会打印自身代码(副作用)并返回自身。为了表述方便没有严格考虑evaluation strategy的影响,这里应该视为使用了call-by-need,但是最外层的y y应用有一次强制的求值。

另外这段代码的puts前可以执行任意多不影响标准输出的代码,puts的内容(括号里面)也可以接一些代码,比如最终QR.rbputs的内容就跟着.gsub(/[HJK^`X]/)等一长串代码。src/code-gen.rb里在puts前添加了PROLOGUE,用来规整化第一个Ruby程序看到的下一段代码字符串。比如用N代替换行符,B代替反斜杠等,而eEdDQ等则是各语言里字符串内特殊字符的转义方式,在CodeGen各子类的hello-world模板代码里用到了这些转义函数。

其他

另外值得称道的是项目中的一款Whitespace解释器:src/whitespace.rb,词法符号的提取用了\G、named capture、named backreference等高级玩意儿:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
RE = /\G(?<n>[01]+){0}
( 00 (?<push> )\g<n>2
| 010 (?<copy> )\g<n>2
| 012 (?<slide>)\g<n>2
| 020 (?<dup>)
| 021 (?<swap>)
| 022 (?<pop>)
| 1000(?<add>)
| 1001(?<sub>)
| 1002(?<mul>)
| 1010(?<div>)
| 1011(?<mod>)
| 110 (?<set>)
| 111 (?<get>)
| 1200(?<outc>)
| 1201(?<outn>)
| 1210(?<readc>)
| 1211(?<readn>)
| 200 (?<mark>)\g<n>2
| 201 (?<call>)\g<n>2
| 202 (?<jump>)\g<n>2
| 210 (?<jz>)\g<n>2
| 211 (?<jn>)\g<n>2
| 212 (?<ret>)
| 222 (?<end>)
| (?<eof>)\z
| (?<error>)
)/x

x开启free-spacing mode,正则表达式里的空白符号会被引擎忽略。|分割的子表达式每个都表示一个词法结构,用named capture来具体是哪个子表达式匹配成功了。题外话,关于正则表达式,《Mastering Regular Expressions》、《Regular Expressions Cookbook》都值得一读。