給 Lisp 程序員的 Python 簡介
這是一篇為Lisp程序員寫的Python簡介（一些Python程序員告訴 我，這篇文章對他們學習Lisp也有幫助，盡管這不是我的本意）。基本上，Python可以看作一個擁有“傳統”語法（Lisp社區稱之為“中綴”或者 “m-lisp”語法）的Lisp方言。一個來自comp.lang.python的帖子說到“我一直不明白為什么LISP是一個不錯的想法，直到我開始 玩上了Python”。Python支持除了宏（macros）之外的所有Lisp的關鍵特征，并且你不會太想念宏因為Python擁有求值，運算符重載，和正則表達式解析，所以一些（不是所有）宏的使用場景都被涵蓋了。
我深入學習Python的原因是，我正在考慮把Russel & Norvig的人工智能教材配套的Lisp代碼轉化成Java代碼。一些教師和學生想要Java代碼，因為：
-
那是他們在其他課程中最熟悉的語言。
-
他們希望有圖形應用程序（graphical applications）。
-
少數人想要能在瀏覽器中運行的applets。
-
一些人只是因為在他們可以投入的有限的上課時間內，不能習慣于Lisp的語法。
然而，我們編寫Java版本的第一次嘗試很不成功。Java太羅嗦了，并且書中的偽代碼和java代碼之間的差異太大。我環顧四周，尋找一種和書中偽代碼相近的語言，并最終發現 Python是最接近的。此外，有了Jython，我可以定位于Java的JVM。
我的結論
對于我的使用目的而言，Python是一個非常優秀的語言。它使用簡單（交互式的，沒有“編譯-鏈接-加載-運行”循環），這點對于我的教學目的是很重要 的。雖然Python不滿足被拼寫為J-A-V-A的前提條件，但是Jython已經很接近了。對于沒有其他語言經驗的人而言，Python似乎比 Lisp更容易閱讀。我開發的Python代碼看起來比 Lisp代碼更像書中（獨立開發）的偽代碼。這點是很重要的，因為一些同學抱怨說，他們在把書中的偽代碼和網上的Lisp代碼對應起來的過程中，有一段困難的時間（即使這個過程對Lisp程序員來說是顯然的）。
從我的觀點來看，Python的兩個主要的缺點是：1）只有很少的編譯時的錯誤分析（compile-time error analysis）和類型聲明（type declaration），甚至比Lisp還少。2）運行時間比Lisp慢很多，通常相差10倍（有時100倍，有時1倍）。定性地說，Python和解 釋型的Lisp的速度差不多，但是很明顯地慢于編譯型的Lisp。基于這個原因，對于那些（或者會逐漸變為）計算密集性的應用（除非你愿意把速度瓶頸部分 用c重寫），我不會推薦使用Python。但是我的目的是面向教育的，而不是產品，所以速度不是問題。
Python 簡介
Python既可以看作一個實用（更好的庫）版本的Scheme，也可以看作一個凈化（沒有了“$@&%”符號）版本的Perl。然而Perl的 哲學是TIMTIWTDI（there's more than one way to do it，即都種方法解決同意問題），Python試圖提供一個最小子集，使得人們以同樣的方式使用它（即TOOWTDI，there's only one way to do it，但是如果你努力嘗試的話，通常會有多種方式去解決同一問題）。其中一個具有爭議的Python特征是，用縮進層次代替begin/end或者花括 號，啟發它的哲學思想是：因為這里沒有括號，所以也就沒有了因為如何放置括號而引起的風格戰爭（style wars）。有趣的是，Lisp在這點上有同樣的哲學思想：每個人都用emacs去縮進代碼，所以他們沒有去爭論縮進方式。拿到一個Lisp代碼，對它進 行合理的縮進，刪除行首的左括號（opening parens），以及與之匹配的閉括號（close parens），這樣我們就得到看起來類似Python的程序。
Python有做出明智妥協的哲學思想，使得容易的事情更容易，并且不排除太多困難的事情。在我看來Python做的不錯。簡單的事情簡單，困難的事情逐 漸困難，并且你甚至注意不到這種不一致。Lisp有做出較少妥協的思想：提供一個強大并且完全一致的核心。這讓Lisp很難去學，因為你從一開始就操作在 一個較高的抽象層次上，而且你需要理解你正在做什么，而不是僅僅依靠感覺活著看起來漂亮。但是它同樣意味著更容易為Lisp添加抽象層次和復雜 性；Lisp優化的目標是使得很困難的事情不太困難，而Python優化的目標是使得中等難度的事情更簡單。
這里我從Python.org摘了一段對Python的簡介，并我創造了兩個版本：一個是用藍色斜體顯示的Python，另一個是用綠色粗體顯示的Lisp。其他大部分，兩個語言的共同部分，是黑色的。
Python/Lisp 是一個解釋型的和編譯型的, 面向對象的，高級編程語言，并且擁有動態語義。它的高級的內部數據結構，以及動態類型和動態綁定，使得它對于快速應用開發特別有吸引力，同樣地，Python作為腳本或者膠水語言去鏈接已存在的部分，也是非常有吸引力。Python/Lisp簡單、易學的語法強調的是可讀性，并因此降低程序維護的成本。Python/Lisp支持模塊（modules）和包（packages），這鼓勵了程序的模塊化和復用。Python/Lisp解釋器和廣泛的標準庫在大多數平臺上都是以源碼或者二進制形式發布的，并且可以自由的散發。通常，程序員愛上Python/Lisp是因為它提供地不斷增加的生產力。因為這里沒有分離的（separate）編譯步驟，“編輯-測試-調試”循環難以置信的快。調試Python/Lisp程序很簡單：一個bug或者壞輸入不會造成段錯誤。相反，當解釋器發現一個錯誤，它拋出一個異常。當程序沒有抓獲這個異常時，解釋器將打印棧軌跡。代碼級別的調試允許查看局部和全局變量，求值任意表達式，設置斷點，單步執行，等等。調試器是由Python/Lisp自己寫的，表明了Python/Lisp的自省能力。另一方面，通常最快的調試一個程序的方法是向源碼中添加一些打印語句：快速的“編輯-測試-調試”循環使得這個簡單的方法特別有效。
我只添加下面這句:
盡管有些人對于縮進作為塊結構/括號有原始的抵制，但是大多數人最后喜歡/深深的感激 他們。
想學習更多關于Python的知識，如果你是一個有經驗的程序員，我推薦你去Python.org的下載頁面，下載文檔包，并且特別要注意Python參考手冊和Python庫參考。這里有各種各樣的輔導材料（tutorials）和出版的書籍，但是這些參考是你真正需要的。
下面的表作為一個Lisp/Python轉化的指南。紅色的表項標記了這個位置中的語言，明顯的比較糟糕（我自己的觀點）。粗體標記了這個位置上，兩個語言明顯不同，但是沒有一個方式明顯的好于另一個。用正常字體顯示的表項意味著兩個語言是相似的；語法可能稍有不同，但是概念是相同的，或者非常相近。表后面是一個要點列表和一些Python的示例程序.
| 關鍵特征 | Lisp 特征 | Python 特征 |
| 一切都是對象 | 是 | 是 |
| 對象有類型，變量沒有 | 是 | 是 |
| 支持異構的(heterogenous)列表 | 是 (linked list and array/vector) | 是 (array) |
| 多范式語言 | 是：函數式，命令式，OO，Generic | 是：函數式，命令式，OO |
| 存儲管理 | 自動垃圾收集 | 自動垃圾收集 |
| 包/模塊 | 使用困難 | 使用簡單 |
| 對象，類的自省 | 強大 | 強大 |
| 元編程的宏 | 強大的宏 | 沒有宏 |
| 交互式的REPL（Read-eval-print loop） |
> (string-append "hello" " " "world") "hello world" |
>>> ' '.join(['hello', 'world']) 'hello world' |
| 簡介、富有表達力的語言 |
(defun transpose (m) (apply #'mapcar #'list m)) > (transpose '((1 2 3) (4 5 6))) ((1 4) (2 5) (3 6)) |
def transpose (m): return zip(*m) >>> transpose([[1,2,3], [4,5,6]]) [(1, 4), (2, 5), (3, 6)] |
| 跨平臺可移植性 | Windows, Mac, Unix, Gnu/Linux | Windows, Mac, Unix, Gnu/Linux |
| 實現的數量 | 很多 | 一個主要的，附加一些分支（例如：Jython， Stackless） |
| 開發模式 | 專有和開源 | 開源 |
| 效率 | 大約比C++慢1到2倍 | 大約比C++慢2到100倍 |
| GUI, Web 等庫 | 沒有標準 | GUI, Web 標準庫 |
|
方法 方法分派 |
動態, (meth obj arg) 語法 runtime-type, multi-methods |
動態, obj.meth(arg) 語法 runtime-type, single class-based |
| 數據類型 | Lisp 數據類型 | Python 數據類型 |
|
Integer Bignum Float Complex String Symbol Hashtable/Dictionary Function Class Instance Stream Boolean Empty Sequence Missing Value Lisp List (linked) Python List (adjustable array) Others |
42 100000000000000000 12.34 #C(1, 2) "hello" hello (make-hash-table) (lambda (x) (+ x x)) (defclass stack ...) (make 'stack) (open "file") t, nil (), #() linked list, array nil (1 2.0 "three") (make-arrary 3 :adjustable t :initial-contents '(1 2 3)) 很多 (in core language) |
42 100000000000000000 12.34 1 + 2J "hello" or 'hello' ## 不可變的 'hello' {} lambda x: x + x class Stack: ... Stack() open("file") True, False (), [] tuple, array None (1, (2.0, ("three", None))) [1, 2.0, "three"] 很多 (in libraries) |
| 控制結構 | Lisp 控制結構 | Python 控制結構 |
| 語句和表達式 | 一切都是表達式 | 區分語句和表達式 |
| 假值(False) | nil是唯一的假值 | False, None, 0, '', [ ], {}都是假值 |
| 函數調用 | (func x y z) | func(x,y,z) |
| 條件測試 | (if x y z) |
if x: y else: z |
| 條件表達式 | (if x y z) | y if x else z |
| While循環 | (loop while (test) do (f)) | while test(): f() |
| 其他循環 |
(dotimes (i n) (f i)) (loop for x in s do (f x)) (loop for (name addr salary) in db do ...) |
for i in range(n): f(i) for x in s: f(x) ## s為任意序列 for (name, addr, salary) in db: ... |
| 賦值 |
(setq x y) (psetq x 1 y 2) (rotatef x y) (setf (slot x) y) (values 1 2 3) 在棧上 (multiple-value-setq (x y) (values 1 2)) |
x = y x, y = 1, 2 x, y = y, x x.slot = y (1, 2, 3) 在堆中 x, y = 1, 2 |
| 異常 |
(assert (/= denom 0)) (unwind-protect (attempt) (recovery)) (catch 'ball ... (throw 'ball)) |
assert denom != 0, "denom != 0" try: attempt() finally: recovery() try: ...; raise 'ball' except 'ball': ... |
| 其他控制結構 | case, etypecase, cond, with-open-file, etc. |
擴展的with語句 沒有其他控制結構 |
| 詞法結構 | Lisp 詞法結構 | Python 詞法結構 |
| 注釋 | ;; 分號直到行尾 | ## 井號直到行尾 |
| 界定符（Delimiters） |
用括號來界定表達式 (defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1))))) |
用縮進來界定語句 def fact (n): if n <= 1: return 1 else: return n * fact(n — 1) |
| 高階函數 | Lisp 高階函數 | Python 高階函數 |
|
應用函數 執行一個表達式 執行一個語句 加載文件 |
(apply fn args) (eval '(+ 2 2)) => 4 (eval '(dolist (x list) (f x))) (load "file.lisp") or (require 'file) |
apply(fn, args) or fn(*args) eval("2+2") => 4 exec("for x in list: f(x)") execfile("file.py") or import file |
| 序列函數 |
(mapcar length '("one" (2 3))) => (3 2) (reduce #'+ numbers) (every #'oddp '(1 3 5)) => T (some #'oddp '(1 2 3)) => 1 (remove-if-not #'evenp numbers) (reduce #'min numbers) |
map(len, ["one", [2, 3]]) => [3, 2] or [len(x) for x in ["one", [2, 3]]] reduce(operator.add, numbers) all(x%2 for x in [1,3,5]) => True any(x%2 for x in [1,2,3]) => True filter(lambda x: x%2 == 0, numbers) or [x for x in numbers if x%2 == 0] min(numbers) |
| 其他高階函數 |
count-if 等 :test, :key 等關鍵字參數 |
沒有其他內置的高階函數 map/reduce/filter函數沒有關鍵字參數 |
|
Close over read-only var Close over writable var |
(lambda (x) (f x y)) (lambda (x) (incf y x)) |
lambda x: f(x, y) Can't be done; use objects |
| 參數列表 | Lisp 參數列表 | Python 參數列表 |
|
可選參數 變長參數 未確定的關鍵字參數 調用約定 |
(defun f (&optional (arg val) ...) (defun f (&rest arg) ...) (defun f (&allow-other-keys &rest arg) ...) 只有明確聲明時，才可以用關鍵詞方式調用: (defun f (&key x y) ...) (f :y 1 :x 2) |
def f (arg=val): ... def f (*arg): ... def f (**arg): ... 用關鍵字方式調用任何函數: def f (x,y): ... f(y=1, x=2) |
| 效率 | Lisp 效率問題 | Python 效率問題 |
|
編譯 函數引用解析 聲明 |
編譯到本機代碼 大多數“函數/方法”的查找很快 為了效率可以進行聲明 |
編譯到字節碼 大多數“函數/方法”的查找比較慢 沒有聲明 |
| 特征 | Lisp 特征和函數 | Python 特征和函數 |
| 引用（Quotation） |
引用整個列表結構: 'hello '(this is a test) '(hello world (+ 2 2)) |
引用單個的字符串或者.split(): 'hello' 'this is a test'.split() ['hello', 'world', [2, "+", 2]] |
| 自省（Introspectible）文檔字符串 |
(defun f (x) "compute f value" ...) > (documentation 'f 'function) "compute f value" |
def f(x): "compute f value" ... >>> f.__doc__ "compute f value" |
| 列表訪問 |
通過函數: (first list) (setf (elt list n) val) (first (last list)) (subseq list start end) (subseq list start) |
通過語法: list[0] list[n] = val list[-1] list[start:end] list[start:] |
| 哈希表訪問 |
通過函數: (setq h (make-hash-table)) (setf (gethash "one" h) 1.0) (gethash "one" h) (let ((h (make-hash-table))) (setf (gethash "one" h) 1) (setf (gethash "two" h) 2) h) |
通過語法: h = {} h["one"] = 1.0 h["one"] or h.get("one") h = {"one": 1, "two": 2} |
| 列表上的操作 |
(cons x y) (car x) (cdr x) (equal x y) (eq x y) nil (length seq) (vector 1 2 3) |
[x] + y but O(n); also y.append(x) x[0] x[1:] but O(n) x == y x is y () or [ ] len(seq) (1, 2, 3) |
| 數組上的操作 |
(make-array 10 :initial-element 42) (aref x i) (incf (aref x i)) (setf (aref x i) 0) (length x) #(10 20 30) 如果大小不變的話 |
10 * [42] x[i] x[i] += 1 x[i] = 0 len(x) [10, 20, 30] |
對大多數人來說，一個重要的方面就是Python和Lisp相對于其他語言而言的執行速度如何。我很難得到和你的應用相關的基準測試數據，但是下面這個表可能對你有用：
The Great Computer Language Shootout5種語言在基準測試集上的相對速度.
| 測試 | Lisp | Java | Python | Perl | C++ |
|
|
|---|---|---|---|---|---|---|---|
| 哈希訪問 | 1.06 | 3.23 | 4.01 | 1.85 | 1.00 |
|
|
| 異常處理 | 0.01 | 0.90 | 1.54 | 1.73 | 1.00 |
|
圖例說明 |
| 對文件中的數字進行求和 | 7.54 | 2.63 | 8.34 | 2.49 | 1.00 |
|
> 100 x C++ |
| 反轉行 | 1.61 | 1.22 | 1.38 | 1.25 | 1.00 |
|
50-100 x C++ |
| 矩陣相乘 | 3.30 | 8.90 | 278.00 | 226.00 | 1.00 |
|
10-50 x C++ |
| 堆排序 | 1.67 | 7.00 | 84.42 | 75.67 | 1.00 |
|
5-10 x C++ |
| 數組訪問 | 1.75 | 6.83 | 141.08 | 127.25 | 1.00 |
|
2-5 x C++ |
| 列表處理 | 0.93 | 20.47 | 20.33 | 11.27 | 1.00 |
|
1-2 x C++ |
| 對象實例化 | 1.32 | 2.39 | 49.11 | 89.21 | 1.00 |
|
< 1 x C++ |
| 單詞計數 | 0.73 | 4.61 | 2.57 | 1.64 | 1.00 |
|
|
|
|
|
|
|
|
|
|
|
| 中位數 | 1.67 | 4.61 | 20.33 | 11.27 | 1.00 |
|
|
| 25% to 75% | 0.93 to 1.67 | 2.63 to 7.00 | 2.57 to 84.42 | 1.73 to 89.21 | 1.00 to 1.00 |
|
|
| 范圍 | 0.01 to 7.54 | 0.90 to 20.47 | 1.38 to 278 | 1.25 to 226 | 1.00 to 1.00 |
|
|
對速度進行了規格化處理，以使得利用g++編譯器編譯過的c++代碼的速度是1.00，所以2.00意味著比c++慢2倍；0.01意味著比c++快 100倍。對于Lisp而言，使用的是CMUCL編譯器。背景顏色是按照右邊圖例說明進行繪制的。最后的3行給出了中位數值，25%到75%的 quartile值（即去掉兩個最低值和去掉兩個最高值），以及整體范圍。在去掉兩個最低的和兩個最高的之后，比較Lisp和Python，我們發現 Python比Lisp要慢3到85倍，Perl和Python差不多，但是比Java和Lisp都慢。Lisp大約比Java要快2倍
給Lisp程序員的Python要點
在這里我列出了一些概念上的問題，是為像我一樣轉到Python的Lisp程序員準備的：
-
Lists are not Conses。 Python的列表其實比較像Lisp的可變數組，或者Java的向量（Vector）。這意味著列表的存取是O(1)的，但是與cons和cdr等價的 操作卻產生了O(n)的新空間。你真的應該使用map或者for e in x:，而不是基于car/cdr的遞歸。注意Python里有多個空列表，而不是一個。這修正了Lisp一個常見的bug，即用戶調用(nconc old new)，并期待old被修改了，但是當old是nil的時候，它并沒有被修改。在Python里，即使old是[ ]，old.extend(new)也可以正常工作。但是這將意味著你必須用==測試列表是否為[]；而不是用is，同時這也意味著，如果你把一個默認參 數的值設置為[]，你最好不要修改這個值。
-
Python is less functional。 部分原因是Python的列表不是conses，相比于Lisp，Python使用了更多方法去改變列表的結構，并且為了強調它們的改變，它們通常返回 None值。例如像list.sort, list.reverse, 和list.remove這樣的方法都是，但是Python的新版本中引入了函數式的版本，即作為一個函數而不是方法，我們現在有了sorted and reversed（但是沒有removed）。
-
Python classes are more functional.在Lisp（CLOS）中，當你重 定義一個類C時，表示類C的對象也相應地得到修改。已經存在的C的實例和子類也因此重新指向新的類。這有時候會引起一些問題，但是在交互式的調試中，這卻 是很有用的。在Python中，當你重定義一個類時，你會得到一個新的類對象，但是實例和子類還是指向舊類。這就意味著大多數時候你必須重新載入你的子 類，并且重建你的數據結構。如果你忘記了，將會引起混淆。
-
Python is more dynamic, does less error-checking. 在 Python中，對于未定義的函數或者域，或者傳給了函數錯誤的參數個數，或者其他載入階段的其他大多數問題，你都不會得到任何警告信息；你必須等到運行 時，才能得到錯誤信息。商業的Lisp實現將會把這些大多數問題標識為警告；簡單的Lisp實現（如clisp）不會。一個演示Python危險性的地方 是，當你想寫self.field = 0時，卻敲入了 self.feild = 0，后者將會動態的創建一個新的域。與之相對的Lisp等價物為，(setf (feild self) 0)，它將給你一個錯誤。另一方面，訪問你一個未定義的域時，兩個語言都會報告一個錯誤。
-
Don't forget self.這點更應該引起Java程序員的注意：在一個方法中，確保你寫的是self.field，而不是field。這里沒有隱式的作用域（scope）。通常這會引起一個運行時錯誤。這很令人討厭，但是我認為過一段時間后，人們將學會不這么干。
-
不要忘記return.寫 函數def twice(x): x+x是很誘人的，并且這不會發出任何警告或者異常信號，但是你可能真正想要的是def twice(x): return x+x。這點特別令人厭煩，因為在一個lambda表達式中，return語句是被禁止的，但是它的語義卻是執行return。
-
注意單元素元組（tuple）。一 個元組是一個不可變的列表，并且用圓括號圍起來，而不是用方括號。()是空元組，(1, 2)是一個含有兩個元素的元組，但是(1)表示的是1。而一個元素的元組卻要用(1,)表示，我擦！Damian Morton指出，如果你把元組看成是由逗號（,）產生的，打印時帶有圓括號的數據，這樣就好理解了。圓括號只是起了消除歧義的作用，在這個解釋下，1, 2是含有兩個元素的元組，1,是含有一個元素的元組，圓括號有時是需要的，這主要取決于元組出現的位置。例如，雖然2, + 2,是一個合法的表達式，但是更加清晰的方式是(2,) + (2,)或者(2, 2)。
-
注意特定的異常 小心: 當key不存在時，dict[key]會拋出KeyError; lisp哈希表的用戶則期望得到nil。你應該捕獲這個異常或者用key in dict測試。
-
Python是Lisp-1的。 我的意思是Python只有一個命名空間，里面包含了變量和函數，就像scheme一樣，而不是想Common Lisp那樣，有兩個命名空間。例如：
def f(list, len): return list((len, len(list))) ## bad Python (define (f list length) (list length (length list))) ;; bad Scheme (defun f (list length) (list length (length list))) ;; legal Common Lisp
對于域和方法也是一樣：你不能提供一個和域名相同的方法名：
class C: def f(self): return self.f ## bad Python ...
-
Python字符串不同于Lisp的符號（symbol）。Python通過把字符串內化到模塊或類的哈希表中，然后進行符號查找。也就是說，當你寫obj.slot時，Python在運行階段會去obj類的哈希表中查找字符串"slot"。Python也會內化一些用戶代碼中的字符串，例如，當你寫x = "str"時。但是Python并不內化那些看起來不像變量的字符串，例如x = "a str"（感謝Brian Spilsbur指出這點）。
-
Python沒有宏（macro）。 Python可以訪問一個程序的抽象語法樹，但是這不是適合“心臟不好”的人。從積極的方面來看，該模塊容易理解，并且在5分鐘內，我用5行代碼就可以得到：
>>> parse("2 + 2") ['eval_input', ['testlist', ['test', ['and_test', ['not_test', ['comparison', ['expr', ['xor_expr', ['and_expr', ['shift_expr', ['arith_expr', ['term', ['factor', ['power', ['atom', [2, '2']]]]], [14, '+'], ['term', ['factor', ['power', ['atom', [2, '2']]]]]]]]]]]]]]], [4, ''], [0, '']]這令我相當失望，同樣的表達式在Lisp中的解析結果是(+ 2 2)。看來，只有真正的專家才會想去操縱Python的解析樹，相 反，Lisp的解析樹對任何人來說都是簡單可用。我們任然可以在Python中，通過連接字符串，來創建一些類似于宏的東西，但是它不能和其他語言集成， 所以在實踐中不這樣做。在Lisp中，兩個使用宏的主要目的是：新的控制結構和定制針對特定問題的語言。前者沒有在Python中實現。后者可以通過在 Python中，用適合特定問題的數據格式來做到：下面我在Python中定義了一個上下文無關語法，分別通過1）組合字典的內置語法，2）解析字符串的 預處理過程完成的。第一種方式和Lisp的宏一樣優雅。但是對于復雜的任務，例如為邏輯編程語言寫一個編譯器這樣的事，在Lisp中很容易，但是在 Python將很困難。
比較Lisp和Python程序
我從《Paradigms of Artificial Intelligence Programming》一書中取了一個簡單的隨機句子生產器程序，并把它翻譯成Python。結論：簡介性相當；Python因為grammar[phrase]比 (rule-rhs (assoc phrase *grammar*))簡單，而獲得一分，但是Lisp因為'(NP VP)比['NP', 'VP']更簡介而扳平比分。Python程序很可能比較低效，但是這不是我們關注的點。兩個語言看起來都很適合這樣的程序。調整瀏覽器窗口到合適的寬度以便閱讀代碼。
| Lisp程序 simple.lisp | Python程序 simple.py |
|
(defparameter *grammar* '((sentence -> (noun-phrase verb-phrase)) (noun-phrase -> (Article Noun)) (verb-phrase -> (Verb noun-phrase)) (Article -> the a) (Noun -> man ball woman table) (Verb -> hit took saw liked)) "A grammar for a trivial subset of English.") (defun generate (phrase) "Generate a random sentence or phrase" (cond ((listp phrase) (mappend #'generate phrase)) ((rewrites phrase) (generate (random-elt (rewrites phrase)))) (t (list phrase)))) (defun generate-tree (phrase) "Generate a random sentence or phrase, with a complete parse tree." (cond ((listp phrase) (mapcar #'generate-tree phrase)) ((rewrites phrase) (cons phrase (generate-tree (random-elt (rewrites phrase))))) (t (list phrase)))) (defun mappend (fn list) "Append the results of calling fn on each element of list. Like mapcon, but uses append instead of nconc." (apply #'append (mapcar fn list))) (defun rule-rhs (rule) "The right hand side of a rule." (rest (rest rule))) (defun rewrites (category) "Return a list of the possible rewrites for this category." (rule-rhs (assoc category *grammar*))) |
from random import choice grammar = dict( S = [['NP','VP']], NP = [['Art', 'N']], VP = [['V', 'NP']], Art = ['the', 'a'], N = ['man', 'ball', 'woman', 'table'], V = ['hit', 'took', 'saw', 'liked'] ) def generate(phrase): "Generate a random sentence or phrase" if isinstance(phrase, list): return mappend(generate, phrase) elif phrase in grammar: return generate(choice(grammar[phrase])) else: return [phrase] def generate_tree(phrase): """Generate a random sentence or phrase, with a complete parse tree.""" if isinstance(phrase, list): return map(generate_tree, phrase) elif phrase in grammar: return [phrase] + generate_tree(choice(grammar[phrase])) else: return [phrase] def mappend(fn, list): "Append the results of calling fn on each element of list." return reduce(lambda x,y: x+y, map(fn, list)) |
| Running the Lisp Program | Running the Python Program |
|
> (generate 'S) (the man saw the table) |
>>> generate('S') ['the', 'man', 'saw', 'the', 'table'] >>> ' '.join(generate('S')) 'the man saw the table' |
Python中的grammer比Lisp中的丑陋，這讓我很擔心，所以我考慮在Python中寫一個解析器（后來發現已經有一些寫好的，并且可以免費獲得的），以及重載一些內置的操作符。第二種方法在一些應用中是可行的，例如我寫Expr class， 這是用來表現和操縱邏輯表達式的。但是對于這個應用而言，一個簡單、定制的語法規則解析器就夠了：一個語法規則是一個用“|”分開的，可選部分的列表，每 個可選部分都是由空格（" ")分隔的單詞列表。把grammar程序重寫為一個更加符合Python慣用法的程序，而不是Lisp程序的翻譯，下面就是該程序：
| Python Program simple.py (idiomatic version) |
|
"""Generate random sentences from a grammar. The grammar consists of entries that can be written as S = 'NP VP | S and S', which gets translated to {'S': [['NP', 'VP'], ['S', 'and', 'S']]}, and means that one of the top-level lists will be chosen at random, and then each element of the second-level list will be rewritten; if it is not in the grammar it rewrites as itself. The functions rewrite and rewrite_tree take as input a list of symbols. The functions generate and generate_tree are convenient interfaces to rewrite and rewrite_tree that accept a string (which defaults to 'S') as input.""" import random def make_grammar(**grammar): "Create a dictionary mapping symbols to alternatives." for (cat, rhs) in grammar.items(): grammar[cat] = [alt.split() for alt in rhs.split('|')] r eturn grammar grammar = make_grammar( S = 'NP VP', NP = 'Art N', VP = 'V NP', Art = 'the | a', N = 'man | ball | woman | table', V = 'hit | took | saw | liked' ) def rewrite(symbols): "Replace each non-terminal symbol in the list with a random entry in grammar (recursively)." return [terminal for symbol in symbols for terminal in (rewrite(random.choice(grammar[symbol])) if symbol in grammar else [symbol])] def rewrite_tree(symbols): "Replace the list of symbols into a random tree, chosen from grammar." return [{symbol: rewrite_tree(random.choice(grammar[symbol]))} if symbol in grammar else symbol for symbol in symbols] def generate(symbols='S'): """Replace symbol(s) in the space-delimited input string by a random entry in grammar (recursively until terminals); join back into a string.""" return ' '.join(rewrite(symbols.split())) def generate_tree(symbols='S'): "Replace symbol(s) in the space-delimited input string by a random entry in grammar (recursively until terminals); return a tree.""" return rewrite_tree(symbols.split()) |
原文地址：http://jineslong.appspot.com/python-lisp/