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 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等高級玩意兒：

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