我們這個地球上的人實在太多了，加上上天賦與我們的大腦又過於活躍，以致於時時可以聽聞到，又有什麼人做出了驚人之舉。

幾個禮拜前，無意間得知一個網頁：Random CG Paper Generator。每 reload 這個頁面一次，就會亂數產生一篇圖學論文的標題出來（以假亂真似地）。也許，苦於找不到研究方向的研究生，可以來這個頁面 reload, re-roll your brain，看看有沒有什麼意外的研究靈感可以借用的。

Anyway，借用一個這樣的 random stuff generator 來找點子，實在太冒險也太不明智了，況且，我還處於 non-qualified Ph.D. student，沒啥理由理會這個網站的。除非…

我想知道它是怎麼產生這些以假亂真的論文標題。

在與 Edward 來來回回，反反覆覆的 email 往來後，終於，他了解我的目的了。Ed 建議我用 Lisp 來試著解解看這個問題。一方面 Ed 最近一直在寫 Lisp program，而 Lisp 又是號稱 functional programming languages 裏頭的元老之一，很擅長處理這類 AI 相關，或是 NLP（Natural Language Processing）相關的問題；另一方面，我剛好也在鑽研 FP，想多一些小而美的例子好讓自己的手變得髒一些（黑手），從中了解一下 FP 的特色。於是就開工了。

透過 MacPorts 安裝好 SBCL (Steel Bank Common Lisp) 與 Emacs 後，自 Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp 這本書的網站上，下載了書中提到的一些程式碼。試圖用裏頭的一些函式與方法來解決，或是某種程度上“逼近“我想要處理的這個問題。非常遺憾的，PAIP 的程式碼，似乎是給老舊的 Common Lisp 用的，而 SBCL 與他沒有很合，會一直出現一堆 warnings，得一直按 continue/ignore 之類的@@

ok, 首先，我一點都不懂 AI, NLP. 就算有修過一堂 AI 課，也是以非常低分，只比及格還來得高一點的方式過關。（沒辦法，大二在什麼都不懂的情況下，就跟著同學起鬨去修了許永貞教授的課。我還記得那是堂限定大三以上才可以修的課，但我們一群人居然表現出無比的勇氣與真誠，感動了教授，於是我在懞懂中修完了 ＡＩ，至今還是覺得很後悔，應該大四再去修，收獲比較完整的）加上我也沒看過 ＰＡＩＰ 這本書，一開始想以最快最省事的方式，把玩一下先。

• 下載 PAIP 程式碼，解開至某個資料夾。

• 執行 Emacs interactive shell（或是採用 Emacs + SLIME），根據原網頁上寫的，先載入 auxfns 這個檔

          (load "auxfns.lisp")
  

• 有很高的機會，你會看到如下的一些畫面，持續按 0 (continue) 就對了。（原因是新的 Lisp interpreter 已經內建了 symbol 與 debug 這兩個函式了）

• 麻煩的事來了。接著是按照網頁上的建議，想執行

          (requires "examples")
  

就會遇上另外一些有看沒有懂的 msg：

• 這是 auxfns.lisp 裏的 load-paip-file 這個函式的問題。它原來的程式碼如下：

          (defun load-paip-file (file)
  

  “Load the binary file if it exists and is newer, else load the source.” (let* ((src (paip-pathname file :lisp)) (src-date (file-write-date src)) (bin (paip-pathname file :binary)) (bin-date (file-write-date bin))) (load (if (and (probe-file bin) src-date bin-date (>= bin-date src-date)) bin src))))

裏頭的 file-write-date 這個函式會因為找不到 .binary 這檔而發出類似 exception，中斷了程式的執行之類的。（我亂猜測）作法是直接拿掉 .binary 檔的測試。如下：

            (defun load-paip-file (file)
  (load (paip-pathname file :lisp)))

• 最後，我們重新來一次，順利執行過了 (requires “examples”)，接著輸入

          (do-examples :all)
  

過程中反覆按了不下十次的 0 (continue)，最後好像可以了?（其實還是不行，不過我已經想放棄了…）假設已經可以了好了 = =

這過程讓人很氣餒，一來還搞不清楚，那個 do-examples :all 是在幹麻的（喔喔，我這邊的寫法不算正確，正式來說，應該寫成 (do-examples :all)，你也曉得的，Lisp 最有名的，就是那些括號了，如果拿掉那些括號，程式碼說不定可以減少 1/4 ~ 1/3!!!!），連個鬼影都還沒瞧見就得狂按一堆 continue，但最後居然還是宣告失敗；二來，我們一個 Lisp 的語法都還不懂的情況下，更無法去 trace code，況且 trace code 也不是現在的首要目的。當下最重要的，是確定你的 Lisp 環境運作正常，然後有個例子可以執行~

最後，我們修正了一下我們的目的：

參考 PAIP 的 syntax1.lisp，使用裏頭一個號稱 PSG-based natural language parser。然後自行先隨便兜一個 grammar 出來，然後用這個 grammar 來 parse 一個 randomly generated paper title。這過程的目的在於，小小把玩一下 NLP 裏頭的 parsing by grammar.

為此，拿出事先就已經準備好的一個文字檔來，裏頭的每一行是一筆 random paper title，這個檔是事先用 Python 寫了幾行程式，自動“觀看“那個網址 10,000 次，再把每次得到的 paper title 存起來的結果。途中我一度擔心，是不是會把這個網站給搞掛了，連續 10,000 次的 query，中間一點喘息的時間都沒有，應該是 ok 的吧? 很顯然它活得好好的，網站沒有掛點 :D

開始亂試 grammar 幾分鐘後，我突然意識到一件事。參考 syntax1.lisp 的 grammar 的寫法，算是非常正規的一種作法，就是說，把一個句子拆開來看，然後一個句子可能是由名詞子句 + 動詞子句構成的，然後名詞子句又可以是單單一個名詞，或是一個名詞片語，然後動詞又可以是……就這樣一路下去。然後我也意識到，一般的 paper title，其實不過是一個名詞子句，並非完整的句子。為此，我只要專注在刻出一個名詞子句的樣子，然後最後把會用到的（或者說，會出現的）單字給放上去就行了。

要做到前者這點不難，難的是怎麼挑出會用到的單字，CG 界裏頭常常出現在 title 的單字可能就那些，不過要得到一個清單也是得花些時間的，偏偏對於一位 programmer 來說，最貴的就是時間了，尤其在你只是在寫個 prototype，連真的的目的的一點邊都還沾不上的時間，豈可以花費太多時間在你壓根兒都還不清楚的細節上頭?! 於是我把腦筋動到那 10,000 個 paper titles 上頭。裏頭不是有很多個單字嗎? 直接從中抓出“到底有多少單字有用到“，不就得了?!

最後，我約略胡亂弄出了個 grammar 來：

(defparameter *grammar4*
  '((NP -> (D N))
    (NP -> (N))
    (NP -> (D A+ N))
    (NP -> (A+ N))
    (NP -> (NP PP))
    (PP -> (P NP))
    (N -> (N N))
    (A+ -> (A))
    (A+ -> (A A+))
    (A -> abstract) (A -> adaptive) (A -> anisotropic) (A -> arbitrary) (A -> ambient)
    (A -> bidirectional)
    (A -> distributed) (A -> dynamic)
    (A -> exponential)
    (A -> gaussian)
    (A -> hardware-accelerated) (A -> hierarchical) 
    (A -> intelligent) (A -> interactive) (A -> inverse)
    (A -> linear) (A -> logarithmic)
    (A -> multi-resolution)
    (A -> non-linear) (A -> normal) (A -> normal-mapped)
    (A -> occlusion-mapped) (A -> omnidirectional) (A -> output-sensitive)
    (A -> parameterized) (A -> persistent) (A -> piecewise) (A -> polygonal) (A -> practical) (A -> pre-computed) (A -> precise) (A -> probabalistic) (A -> procedural)
    (A -> real-time) (A -> reflective) (A -> relief)
    (A -> shadow-mapped) (A -> soft) (A -> spherical)
    (A -> texture-mapped)
    (A -> variable) (A -> view-dependent) (A -> volumetric)
    (D -> the) (D -> a) (D -> an)
    (N -> approximation) (N -> attenuation)
    (N -> caustics) (N -> clustering) (N -> compression) (N -> culling)
    (N -> displacement)
    (N -> estimation)
    (N -> fields)
    (N -> geometry)
    (N -> interpolation)
    (N -> light)
    (N -> mapping) (N -> map) (N -> mipmap) (N -> modeling)
    (N -> occlusion) (N -> opacity) 
    (N -> preprocessing)
    (N -> re-meshing) (N -> rendering)
    (N -> sampling) (N -> shadow) (N -> spline) (N -> subsurface scattering) (N -> surface)
    (N -> texture) (N -> texturing)
    (P -> with) (P -> for) (P -> at) (P -> on) (P -> by) (P -> of) (P -> in) (P -> using)
   ))

檔案：

• 整個修改過的程式碼，請執行 main.lisp。
• 10,000 個 randomly generated cg paper titles。
• 同上，但是做過 sort 與 uniq。

最後，我終究是沒有完成 Grammar Induction，只能說是小小玩了一下而已~