為什麼很少有用lisp描述演算法？

01-05

「Fortran 被發明出來以替代彙編語言。 Lisp 被發明出來表述算
法。「——&<&&>,p5
但是在現實中，人們往往傾向於用高級語言，偽碼，狀態機，甚至彙編語言，而少有用lisp來描述演算法，這是為什麼？

C里有的那些低層次的構造，賦值、循環、數組、位運算之類的，Lisp里一樣不缺，拿來描述演算法並無不妥。

其實唯一的原因就是學Lisp的少，市場小。演算法教材拿C/C++/Java做描述語言的多，但最近連Python/JavaScript演算法書都有了，而我覺得這兩門語言反而不適合演算法入門，因為語言提供的容器類型已經是關聯數組之類的數據結構。。

這事跟函數式編程也沒有半毛線關係。Lisp不是函數式語言，而是多範式語言，就像C++一樣，只是寫個演算法程序的話，什麼閉包啊宏啊之類的特性無視掉都行。。。

我覺得很重要的一點是，大多數人很難理解lisp的函數式思路。

而且在圖靈機和lambda演算的這兩種不同基礎上，許多演算法的形式會發生很大的改變。如果現在流行的機器是lisp機，那麼描述演算法用的最多的估計還是lisp類的

Procedural programming language可以把演算法的每一步都拆分表示出來。

Lisp把很多步驟囊括在lambda calculus或者recursion里了，不容易分解成每一步，而且不易於計算機科學領域的初學者領會演算法的全過程與精要。所以就略去了。題主可以這麼問：「為什麼在教學/技術博客/日誌中，人們更傾向於用Procedural programming language來描述演算法，而在實際操作中更傾向於使用lisp？」

這麼說吧比如描述一個binary tree.

struct node { int key_value; struct node *left; struct node *right; };

insert(int key, struct node **leaf) { if( *leaf == 0 ) { *leaf = (struct node*) malloc( sizeof( struct node ) ); (*leaf)-&>key_value = key; /* initialize the children to null */ (*leaf)-&>left = 0; (*leaf)-&>right = 0; } else if(key &< (*leaf)-&>key_value) { insert( key, (*leaf)-&>left ); } else if(key &> (*leaf)-&>key_value) { insert( key, (*leaf)-&>right ); } }

lisp:

(defun insert (Tr Int) (if (isEmptyTree Tr) (create_tree (create_empty_tree) Int (create_empty_tree)) (if (eq (node_value Tr) Int) Tr (if (&< (node_value Tr) Int) (create_tree (left_subtree Tr) (node_value Tr) (insert (right_subtree Tr) Int) ) (create_tree (insert (left_subtree Tr) Int) (node_value Tr) (right_subtree Tr) ) ) ) ) )

初學者在學習和理解演算法的時候用C比較容易

但是有些時候用lisp理解一些解釋器卻比C簡潔流暢多了。

比如下面這一行可以返出大量自定義函數的值。

(function (interp (car (substitutes-all (get-vars (cdr function)) (get-body function) arg)) P))

而C要完成這一行能做的相當麻煩。

但是解釋器並不是初學者能夠接觸到的諸如二叉樹一類的普適演算法，並且某些要巧妙運用閉包特性的地方需要程序員對lambda運算元的理解，所以lisp並不適合向初學者解釋演算法。

使用的人數少是一個重要原因，此外，現在廣泛使用的也並非lisp machine，c類的語言更符合現在的計算機模型，能達到更高的計算效率，比如數組，如果不在語言裡面內置，無法達到O(1)的隨機訪問效率，很多純函數式語言寫演算法降低複雜度還要依賴於惰性求值。

用c寫演算法的一大好處在於可以充分榨乾機器特性帶來的優勢，比如一些匪夷所思的位運算(題主見過樹狀數組的lowbit沒？)

lisp當然也有它自己的奇技淫巧，光是「宏」這一根本特性就有很多人在研究，只是基於函數式的演算法由於lisp的生不逢時很難進入非專業人士的涉獵範圍。

最後，高度抽象肯定要有一點代價的，比如可讀性。

加一個可能的因素: 寫書寫演算法的人對於 Lisp 不那麼熟悉, 他的目標用戶也是.

當然這個本身就是從 Lisp 使用的人群太少引起的

要是我考慮看我博客的人大部分寫 Lisp, 那我也會用 Lisp 寫博客里的代碼的..

用戶少，而且方言多，這麼一分用戶就更少了

LISP programmers know the value of everything and the cost of nothing.
- Alan Perlis

quoting指得是動態型別, closure, macro等特性讓高效Lisp code不易撰寫profiling, 我一直很想引用所以就在此處用上了。

不過使用Lisp進行演算法分析與Lisp那些神奇功能沒什麼關係，反倒是s-exp可讀性較差（IMHO）及慣用遞迴的寫法都讓cost analysis徒增無謂的複雜度。Lisp(not all)本身是multiparadigm, 做為演算法分析的工具並無不妥

lisp的代碼這年頭我都很少看到了，何況是演算法。

1.用LISP寫程序對編程能力要求很高，用LISP來寫演算法可能會把學習演算法變成學習編程。不信的話你試試用LISP寫個快排

2.LISP程序演算法複雜度不容易分析

1 On Lisp中很多謬誤，不可信以為真

2 有用scheme描述很難的數學，物理演算法的，比如Gerald Sussman 的 Structure and

Interpretation of Classical Mechanics 和 Functional Differential Geometry.

用Lisp描述演算法太便宜學生了，鏈表和樹直接過

你能一句話把你的問題不帶標點的表述出來且別人還看的下去

有些演算法，如果用函數式的思路來實現，所有變數都不能修改，那麼計算複雜性會上升。

因為lisp原生不支持隨機存取，只有順序存取。

比如求一個矩陣的跡，c語言是for(int i=0;i&lisp也可以寫，但是就沒有這麼直接了當，小學生都能懂。

補充：主要是由於lisp的歷史起源和刻板印象。這不是lisp的錯。。。