有趣的自產生程式

有辦法寫個程式，執行後產生這個程式的原始碼嗎？產生器可以是任何形式，最簡單的就是在終端機顯示原始碼！很多人會想到，不就是讀取原始碼顯示出來嗎？不！這被認為是作弊的行為，而且程式本身不一定知道原始碼檔案在哪，或者不一定有原始碼，例如，若寫了一個.java，編譯後將.java刪除，執行.class檔也要能顯示原始碼，當然，反組譯也是作弊的行為！

因此，簡單來說，自產生程式（Quine）的限制是，不能有任何形式的輸入，程式運行本身就要能複製自己！看到這段文字時，請暫停閱讀這篇專欄，試著先寫個Quine吧！

寫個Quine

你繼續閱讀了，試著寫出Quine了嗎？通常第一次嘗試寫出Quine時，會覺得這是個不可能的題目。

以Python為例，我們若寫了程式碼print()，想顯示這段程式碼，直覺上，此時我們就會寫為print('print()')，然而，因為程式碼多了'print()'，print()接受的字串必須增加描述，也就是變成print('print(\'print()\')')，這下子，程式碼又變成長了，又要print('print(\'print(\'print()\')\')')……沒完沒了這？

實現Quine的方式，關鍵點在於，將程式描述與程式執行分開，例如，code代表程式碼，'code'代表程式碼的文字描述，Quine的實現結構就是'code'code。若以Python具體實現，print(t)是程式碼，t是以字元描述整個程式碼的字串（包含t變數的建立），如果這麼撰寫：

t = 't=\'\'\nprint(t)'
print(t)

如此就完成一半任務了，接下來，要如何能顯示「t='print()'」呢？

而從現在開始，為了避免出現自我指涉的狀況，要先取下t的部份描述，來組合出要顯示的資料，例如，print(t[0:3]+t[5:]+t[3]+t[4:])，就能顯示「t='print(t)'」換行後再顯示「print(t)」，將't[0:3]+t[5:]+t[3]+t[4:]'放入t的描述，這樣也不會有問題了，接下來，就是加入\等字元描述，小心地修改描述的讀取與組合，就可以完成任務，例如：

t = 't=\'\\n\nprint(t[0:3]+t[0:2]+t[3]+t[2]+t[3]*2+t[4]+t[3:5]+t[6:]+t[2]+t[5]+t[6:])'
print(t[0:3]+t[0:2]+t[3]+t[2]+t[3]*2+t[4]+t[3:5]+t[6:]+t[2]+t[5]+t[6:])

為什麼叫Quine？

方才的Quine建構是最保守的方式，事實上，Quine是個有趣的題目，吸引許多開發者用各自熟悉的語言，寫出最短的Quine，以測試自身對語言的認識為樂。

例如，Python的Quine簡短實現版本，可以是r='r=%r;print(r%%r)';print(r%r)。若有興趣看看各種語言的Quine實現，我們可以查閱〈The Quine Page〉；只要是圖靈完備（turing complete）語言都能實現Quine，甚至還有Brainfuck的版本。

這類程式最初是由Douglas Hofstadter，以哲學家Willard Van Orman Quine之名來命名，哲學家Quine有個知名的悖論：

"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.

想理解這個悖論，我們可以先認識〈說謊者悖論〉。事實上，「說謊者聲稱自己正在說謊」這句話自我矛盾，如果他確實在說謊，那麼，他說的就是真的；但如果他說的是真的，那麼，他就不是說謊者。

Quine的悖論更為細緻，文字中沒有自我指涉，從原文來思考會是比較好的，如果真要用中文來協助理解該悖論，大概會是「"該句引用在前為假"該句引用在前為假」；這邊不是要探討這個悖論，而是這句話的結構，就類似方才談到的'code'code結構，Douglas Hofstadter因而以此為名。

回到程式實現Quine本身，只要是圖靈完備，都可以簡單地實現Quine，而所謂的簡單，指的是不需要特別的演算法。如方才示範的，程式主要分兩大部份：一個是程式的文字形式描述，也就是資料；另一個就是程式本身，不必用上特別的技巧，程式本身就像個磁帶機，來回地讀取資料中的字元並顯示，就能實現。

以生物細胞的複製來比喻的話，就像DNA包含了細胞的資料，細胞本身是個程式，能讀取DNA來複製出另一個細胞。如果從程式面來看，更簡單來說，就是先將程式碼編碼為資料，然後有另一個解碼程式來還原出程式。

執行環境的不動點

Quine感覺就像是先有雞或是有蛋的問題，類似的疑問，令人聯想到開發者可能也接觸過的另一題目：「如何令遞迴函式能夠匿名？」遞迴函式必須有名稱，然而，又要求遞迴函式是匿名，這看似自我矛盾，其實可以實現Y Combinator，指定匿名函式，Y Combinator可以為它產生遞迴函式。

假設y函式是Y Combinator的實現，y(fact => n => n < 2 ? 1 : n * fact(n - 1))可以產生遞迴函式，那麼，傳給fact參數的是什麼？有興趣可以看看〈拖延的 Y〉，傳給fact的是個稱為不動點的函式。

若有個函式f(x)，有個值v令f(v)結果仍為v，v就是f(x)的不動點，例如，0和1是函式f(x)=square(x)的不動點，Y Combinator產生的也是不動點，不管怎麼遞迴，傳給fact的始終都是同一個函式。

在維基百科〈Quine〉條目中，就明白地指出，Quine就是執行環境的不動點，若將執行環境視為一個函式，將程式作為輸入，總是產生同一個程式，只不過這樣的程式有什麼作用呢？

將程式編碼為文字描述，感覺可以隱藏某些意圖，而自我複製聽起來就像病毒之類的惡意軟體，確實地，可以基於Quine的原理來寫後門程式，Ken Thompson曾在一場演講〈Reflections on Trusting Trust〉，談到如何透過自產生程式，對編譯器植入後門，然而程式碼上又看不出任何問題。

有趣的Quine

撇開實用性不談，大部份對Quine產生興趣的開發者，多半動機很單純：「這是怎麼辦到的？」然後也想要用自己熟悉的語言來挑戰看看，要問Quine為什麼有趣，嗯……回答大概就是「它就很有趣」，實現一個Quine很有趣，思考探究Quine的原理（虐一下自己的腦袋）也很有趣，接著，你還想看看更有趣的嗎？看看quine-relay，從Ruby產生Rust，從Rust產生Scala…總共128種語言，最後又產生相同的Ruby。

在Quine的探究過程中，我遇過最有趣的一個作法，是HTML版的Quine，瀏覽器繪製出來的頁面「幾乎」就是HTML原始碼本身，作者在頁面中解釋了這是怎麼辦到的，也談到style本身避不掉（因此是「幾乎」），然而這也夠令人讚嘆了。

最有趣的就是作者的動機，因為頁面中從一開始就談到，他最愛的就是有創意地誤用技術，在不打破規則的情況下打破規則。

嗯……能夠掌握規則，然後去打破規則，感覺就滿hack，這不是很有趣嗎？！