有辦法寫個程式,執行後產生這個程式的原始碼嗎?產生器可以是任何形式,最簡單的就是在終端機顯示原始碼!很多人會想到,不就是讀取原始碼顯示出來嗎?不!這被認為是作弊的行為,而且程式本身不一定知道原始碼檔案在哪,或者不一定有原始碼,例如,若寫了一個.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,這不是很有趣嗎?!

作者簡介


熱門新聞

Advertisement