Lisp 能被用來幹什麼？

01-28

我曾經跟趙余說過，《歌德爾，埃舍爾，巴赫，集異璧之大成》和《計算機程序的構造與解釋》同看，就像同時吃花生米和豆腐乾一樣相得益彰。實際上這其中每一本都讓我高潮連連。我一直找不到更合適的比喻，直到看到《華爾街之狼》里 Leonardo怎樣貫通了性與毒品。

用一個小例子來一窺堂奧。

這個小例子叫WU謎題，它出現在《GEB》的第一章。這個謎題是「你能產生WU么？」

一開始的時候，我們有一個符號串WI，有下面幾個規則：

1，如果一個歸你所有的符號串結尾是I，則可以在後面加上一個U。

2，如果有Wx，那麼Wxx也歸你所有。e.g. WUI=&>WUIUI

3，如果符號串中有III，那麼可以用U代替III。

4，如果符號串中有UU，那麼可以去掉它。

規則就是這些，現在可以試試找出WU了，能夠找出來的第一個人請把應用規則的序列方式告訴我，我請他吃飯並分享這其中的況味。

這是一個簡單的形式系統，在這個形式系統中，WI被稱為」公理「，由它產生出的符號串被稱作」定理「。四條規則被稱作」推理規則「。由」公理「出發依次利用」推理規則「得到某」定理「的過程被稱為"推導」。"推導「這一概念是向」證明「概念看齊的，但比後者要樸素一點。

這種定義明晰的重複性工作最適合用電腦來做。

我的默認語言是scheme。判斷一個語言好壞有很多標準，我傾向於選擇其中最直觀的一個，那就是在描述眾多具有普遍意義的問題時，代碼總長度最短的是最好的。關於這個直覺我在之前的一篇討論什麼是更好的語言（不只是程序語言）時闡述過。

——talk is cheap， show me the code——

定義「公理」

(define init (list (list m i)))

定義「推理規則」

(define (operator lis)

(define (rule_1 x)

(define (end lis)

(if (null? (cdr lis)) (car lis) (end (cdr lis))))

(if (eq? (end x) i) (append x (list u))))

(define (rule_2 x)

(append x (cdr x)))

(define (rule_3 x)

(cond ((&> (length x) 3)

(cond ((and (eq? (cadr x) i) (eq? (caddr x) i) (eq? (cadddr x) i)) (append (list m u) (cddddr x)))

(else ())))

(define (rule_4 x)

(cond ((or (null? x) (null? (cdr x))) x)

((and (eq? (car x) u) (eq? (cadr x) u)) (rule_4 (cddr x)))

(else (cons (car x) (rule_4 (cdr x))))))

(define (erase seq)

(filter (lambda(x) (not (null? x))) seq))

(erase (list (rule_1 lis) (rule_2 lis) (rule_3 lis) (rule_4 lis)))

)

定義「記憶」

(define dictionary init)

(define (in? value lis)

(or (equal? value (car lis)) (and (not (null? (cdr lis))) (in? value (cdr lis)))))

定義「推導」

(define (expand seqs)

(define (erase_repeat lis)

(cond ((null? lis) ())

(else (cons (car lis) (filter (lambda(x) (not (equal? x (car lis)))) (erase_repeat (cdr lis)))))))

(define (pre-expand lis)

(if (null? lis)

()

(append (operator (car lis))

(pre-expand (cdr lis)))))

(define result (filter (lambda(x) (not (in? x dictionary))) (erase_repeat (pre-expand seqs))))

(begin

(set! dictionary (append dictionary result))

result))

檢驗目標」定理「是否能夠被」推導「出來

(define object (list m u))

(define (f a)

(if (in? object a) yeah (f (expand a))))

(f init)

——talk is not cheap，it turns into code——

在接受了「公理」和「推理規則」之後，我們可以選擇盲目地試一試，在不知不覺中理解這套規則，也可以用scheme來翻譯這套規則。兩種方式都很必要。在進行前者時會產生一種微妙的心理活動，即跳出這個形式系統，看看我們到底在做什麼，系統中暗含了哪些抽象的現象，比如，只有三個字母，每個字元串開頭都是M，等等，這種現象在GEB中被稱作metathinking。第二種思考方式，相應地，就是thinking within the system，在scheme優良的抽象風格下，系統顯示出了其內部的結構。接下來重點闡述後者。

我們首先定義了「公理」，並將「公理」作為唯一一條語句寫入了一個「知識庫」，然後嘗試將四條「推理規則」應用於「公理」，合理的應用結果作為」一級定理「，一方面被寫入「知識庫」，另一方面作為"二級定理"的母定理，即繼續進行」推理「的材料使用，直到某一級定理包含了目標定理，整個推理過程結束。挺笨的。如果一個人掉入了所謂的」思維定勢「，他就變得像這段程序一樣笨了。我們來看一下結果：

1 ]=&> (expand init)

;Value 12: ((m i u) (m i i))

1 ]=&> dictionary

;Value 13: ((m i) (m i u) (m i i))

1 ]=&> (expand (expand (expand init)))

;Value 14: ((m i u u u) (m i u u i u u) (m i u u i u) (m i u i u i u i u) (m i u u i) (m i u i i u i) (m i u i i i) (m i i i i i i i i) (m u i))

1 ]=&> dictionary

;Value 15: ((m i) (m i u) (m i i) (m i u u) (m i u i u) (m i u i) (m i i i i) (m i u u u) (m i u u i u u) (m i u u i u) (m i u i u i u i u) (m i u u i) (m i u i i u i) (m i u i i i) (m i i i i i i i i) (m u i))

1 ]=&> (f init)

;Aborting!: out of memory

;GC #97: took: 0.80 (35%) CPU time, 0.80 (36%) real time; free: 2752857

;GC #98: took: 0.70 (88%) CPU time, 0.70 (99%) real time; free: 2752937

多麼遺憾呢。StackOverFlow。其實這不難理解。如果那麼容易就能推導出來，我怎麼會許下請你吃飯的諾言呢。

在字元串複雜到一定程度之後，每一條「推理規則」都是合理的，因為每一條「推理規則」合理應用於某一字元串都只產生一條「定理」（這裡沒有考慮延遲應用），即」n級定理"的數目是「（n-1）級定理」數目的4的（n-1）次方倍。"0級定理「，即「公理」，有1個，則n級定理有4^n個。如果不過濾重複定理的話，在經過n次「推導」後「知識庫」里的「定理」數目大概是1/3（4^(n+1)-1)個。

Bomb！

」推導「需要metathinking。我們在摸索的時候，系統的模式會悄無聲息地浮現在腦海中。你不僅可以看出這個模式，而且通過檢查那些規則，還可以理解這個模式。這展示了人與機器的區別。這個區別在於：機器有可能在做某件事情時不去觀察，而人不可能不去觀察。能夠跳出正在進行的工作並且看一下已經做了些什麼，這是智能固有的特點。

我已經不知道自己抄了多少GEB中的句子了，如果可以，我想把它全文打下來，用scheme去解釋裡面的每一個小故事。

如果你期待Lisp有什麼「神奇」之處，可以做別的語言做不到的事情，你可能會失望的

Lisp沒有任何神奇之處，它的核心就是一個以s-expression格式為輸入的eval而已。Nothing more, nothing less
Lisp的macro功能更加不是什麼「神奇」的東西。任何解釋性語言的eval都接受動態數據，構造過程用戶可以自由發揮；用戶如果不喜歡語言內置的構造方式，自己可以寫一個，只要eval認就行。甚至C、C++、Java、C#這些編譯型的語言，只要能驅動編譯器，用戶一樣可以自己寫一個「macro」出來（或者叫做generate code on-the-fly）
Lisp由於缺乏用來區分語義的語法變化，導致最後的代碼雖然可以很「緊湊」（緊湊也不代表演算法複雜度更優），但是可讀性和提示性不夠高。《Coders at Work》裡面的使用Lisp的先驅也說了因為這個原因後來不寫Lisp了

但是Lisp是很好的思維訓練的載體，以λ演算而不是圖靈機作為計算模型對於初學者是一種思維上的飛躍，有很高的學習價值

學之生，用之死。

強行用lisp來拉高函數的計算速度。

曾經寫過一些基礎的解釋器，對common lisp里大部分內置函數都可以應用，代碼行數僅八十行。

用lisp寫一些自動機，隨機生成器其實比其他語言還要簡單。

我用它來寫app吧。

lisp app項目地址：evilbinary/scheme-lib

我正在學習 autocad LISP 算是 LISP的一個分支把 .

用來解決我在工程製圖上的問題。

1. Racket, SBCL, Clozure, Emacs Lisp ,Slime, and Clojure等等，實現了哪些就可以做哪些

2. 就算用的是其他的語言也可以對比學習metaprogramming, closure， clos ，clim等等優秀的思想和實現

作為一門普遍意義上的general purpose編程語言，Lisp可以做其它語言也能做的事情，只是有的可能有優勢，有的可能不如其它語言。

ACL2是一個用CommonLisp實現的用於做證明的工具，在它的官網上面說到，AMD用ACL2來驗證Athon處理器的浮點數計算的正確性。

學lisp是學習其中的思想，用這個語言作為其他語言的起點。在lisp中有太多強大的變成思想需要自己慢慢探索的，這是其他語言沒它強大的地方

或許可以用它做個MUD.

lisp不能幹什麼？

只有想不到的，沒有做不到的

Allegro Common Lisp Success Stories

Franz Inc: Allegro Common Lisp and Common Lisp Products

AutoCAD的二次開發使用Visual Lisp。