2013-07-15

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末段实现了这一功能：

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的：

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的逻辑是：

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 y，y得到参数x后的效果是把x x的代码打印出来。而打印x x需要打印以code形式存在的x和与之关联的以data形式存在的x。考虑到参数传递给y的参数是一个固定值x即y，我们不需要写一个通用的能打印任意代码的程序，只需要针对这个特例，实现一个特例。在这里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.rb里puts的内容就跟着.gsub(/[HJK^`X]/)等一长串代码。src/code-gen.rb里在puts前添加了PROLOGUE，用来规整化第一个Ruby程序看到的下一段代码字符串。比如用N代替换行符，B代替反斜杠等，而e、E、d、D、Q等则是各语言里字符串内特殊字符的转义方式，在CodeGen各子类的hello-world模板代码里用到了这些转义函数。

其他

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

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》都值得一读。