Lisp_(编程语言)

**Lisp**（歷史上拼寫為 **LISP**），是具有悠久歷史的計算機程式語言家族，有獨特的完全用圓括號的前綴符號表示法。它起源於 1958 年，是現今第二悠久而仍廣泛使用的高階程式語言，只有 FORTRAN 程式語言比它更早一年。Lisp 編程語族已經演變出許多種方言，現代最著名的通用編程方言是 Scheme、Common Lisp 和新近的 Clojure。

## 簡介

Lisp 最初是為計算機程式建立的實用數學表示法，當時借鑒過阿隆佐・邱奇的 lambda 表示法。它很快成為人工智慧研究中最受歡迎的程式語言。作為早期的高階程式語言之一，Lisp 開創了計算機科學領域的許多概念，包括樹結構、自動記憶體管理、動態型別、條件表達式、高階函式、遞迴、自主編譯器、讀取﹣求值﹣輸出循環（REPL）。

"LISP" 名稱源自「列表處理器」（英語：LISt Processor）的縮寫。列表是 Lisp 的主要數據結構之一，Lisp 編程代碼也同樣由列表組成。因此，Lisp 程式可以把原始碼當作數據結構進行操作，而使用其中的宏系統，開發人員可將自己定義的新語法或領域專用的語言，嵌入在 Lisp 編程中。

代碼和數據的可互換性為 Lisp 提供了立即可辨識的語法。所有的 Lisp 程式碼都寫為 S - 表達式或以括號表示的列表。函式調用或語義形式也同樣寫成列表，首先是函式或運算子的名稱，然後接著是一或多個參數：例如，取三個參數的函式 `f` 即為 `(f arg1 arg2 arg3)`。

## 歷史

在 1958 年，約翰・麥卡錫在麻省理工學院發明了 Lisp 程式語言。在 1960 年，他在《ACM 通訊》發表了論文《符號表達式的遞迴函式及其機器計算，第一部份》。在這篇論文中闡述了只要透過一些簡單的運算子，以及借鑒自阿隆佐・邱奇的用於匿名函式的表示法，就可以建立一個可用於演算法中的具圖靈完備性的語言。Lisp 還採納了在 1955 年至 1956 年間建立的資訊處理語言所提出的列表處理與遞迴概念。

約翰・麥卡錫在最初定義的 Lisp 之中，先將程式表達為 M - 表達式（元表達式），再將它轉換成 S - 表達式（符號表達式），舉例來說 M - 表達式的 `car[cons[A;B]]`，等同於 S - 表達式的 `(car (cons A B))`。S - 表達式可以將複雜結構表示為列表，在 Lisp 被實現了之後，編程者一般只使用 S - 表達式，而棄用 M - 表達式，這使得程式具備了同像性，即程式與資料由同樣的結構儲存。M - 表達式曾短暫存續於 Horace Enea 的 MLisp 和 Vaughan Pratt 的 CGOL 之中。

第一個 Lisp 實作是在 IBM 704 機器上使用打孔卡寫出的。史帝芬・羅素在閱讀完約翰・麥卡錫的論文後，認為其中的 `eval` 函式可以用機器碼來實作，從而創造了一個能工作的 Lisp 直譯器。直譯器可以用來執行 Lisp 程式，或者更恰當的說「求值 Lisp 表達式」。

在 1960 年發表的 LISP I 中，研究生 Daniel Edwards 開發了垃圾回收程式，使得在通用計算機上運行 Lisp 變得可行。在 1962 年，Timothy Hart 與 Michael Levin 在麻省理工學院以 Lisp 自身，實做出第一個完整的 Lisp 編譯器。在 1963 年，Timothy Hart 提議向 LISP 1.5 增加宏。

在 1975 年，傑拉德・薩斯曼和蓋伊・史提爾二世開發了 Scheme，它是使用詞法作用域和尾呼叫最佳化的第一個 Lisp 方言。在 1980 年代至 1990 年代期間，蓋伊・史提爾二世、Scott Fahlman、Richard P. Gabriel、David A. Moon 和 Daniel Weinreb 等人，在將當時新近的 Lisp 方言，其多數是 Maclisp 的後繼者比如 ZetaLisp 和 NIL，統一成單一語言上進行了巨大的努力。新語言 Common Lisp，在某種程度上相容於它所替代的方言。在 1994 年，ANSI 出版了 Common Lisp 標準《ANSI X3.226-1994 資訊科技程式語言 Common Lisp》。此外還有嵌入到編輯器 Emacs 中的 Emacs Lisp，它非常流行並建立了自己的標準。

### 聯絡於人工智慧

自從創始以來，Lisp 就密切聯絡於人工智慧研究社群，特別是在 PDP-10 系統之上。在 1970 年傑拉德・薩斯曼和特里・威諾格拉德使用 Lisp 實現了程式語言 Micro-Planner，它被用在著名的 AI 系統 SHRDLU 之中。

### 譜系和方言

在它六十餘年的歷史中，Lisp 產生了在 S - 表達式語言的核心主旨上的很多變體。此外，每個給定方言又可能有多種實現，例如 Common Lisp 就有十餘種以上的實現。在一種標準化了的方言之內，符合標準的實現支援相同的核心語言，但是有著不同的擴充和函式庫。

在方言間的差異可能是非常顯眼的，例如定義一個函式，Common Lisp 使用 Maclisp 在 1969 年介入的關鍵字 `defun`，而 Scheme 使用它在 1975 年介入的 `define`。Richard P. Gabriel 和 Kent Pitman 在 1998 年的一篇論文中，按採用統一的還是分立的函式與值命名空間，將 Lisp 家族語言劃分為 Lisp1 和 Lisp2（或寫為 Lisp-1 和 Lisp-2）。

#### 歷史上的重要方言

* LISP I，是第一個實現。
* LISP 1.5，是第一個廣泛發行的版本，由 McCarthy 和其他人在 MIT 開發。如此命名是因為它包含了對最初的 LISP I 直譯器的改進，但不是 LISP 2 規劃的那種重大重構。
* Stanford LISP 1.6，是斯坦福 AI 實驗室開發的 LISP 1.5 後繼者，廣泛的發行於執行 TOPS-10 作業系統的 PDP-10 系統。羅賓・米爾納的 LCF ML 執行在 Stanford LISP 1.6 下。它被 Maclisp 和 InterLisp 所淘汰。
* MACLISP，由 MIT 的 MAC 計劃開發，它是 LISP 1.5 的直接後代。它執行在 PDP-10 和 Multics 系統上。MACLISP 後來被稱為 Maclisp，也通常叫做 MacLisp。在 MACLISP 中的「MAC」，既無關於 Apple 的 Macintosh，又無關於 McCarthy。
* Interlisp，由 BBN 科技開發，用於執行 TENEX 作業系統的 PDP-10 系統之上，後來 InterLisp-D 被 Xerox Lisp 機器接納並暱稱為「西海岸 Lisp」。還有為基於 6502 的 Atari 8 位元機家族電腦發行的叫做「InterLISP 65」的小型版本。在很長一段時間內，Maclisp 和 InterLisp 相互之間是強有力的競爭者。
* Franz Lisp，起源於加利福尼亞大學伯克利分校的計劃，後來由 Franz Inc 開發。這個名字是 Franz Liszt 的幽默變形，它不牽涉到 Franz Inc 後來銷售的 Allegro Common Lisp。
* XLISP，由 David Betz 開發，AutoLISP 基於了它。
* Standard Lisp 和 Portable Standard Lisp，是曾被廣泛使用和移植的猶他大學開發的版本，特別是用它寫成了電腦代數系統 REDUCE。
* Lisp Machine Lisp，Symbolics 稱其變體版本為 ZetaLisp，它用在 Lisp 機器之上，是 Maclisp 的直接後代。Lisp Machine Lisp 對 Common Lisp 有巨大影響。
* Le Lisp，是一個法國 Lisp 方言。最早的介面建造器之一（叫做 SOS 介面）是用 Le Lisp 寫成的。
* Scheme（1975 年版），最初是在 Maclisp 上執行的直譯器。
* Common Lisp（1984 年版），是通過合併對 Maclisp 的不同嘗試（ZetaLisp、Spice Lisp、NIL 和 S-1 Lisp）而建立的方言，也具有來自 Scheme 方言的實質影響。這個版本的 Common Lisp 在廣泛的平台上都能獲得到，從而被眾人接受為業界標準，直至 ANSI Common Lisp（ANSI X3.226-1994）出版。最廣泛傳播的 Common Lisp 子方言，是 Steel Bank Common Lisp（SBCL）、CMU Common Lisp（CMU-CL）、Clozure OpenMCL、GNU CLISP 和 Allegro Common Lisp；所有這些實現都堅持了後來的 ANSI CL 標準。
* Dylan，在它的第一個版本中是 Scheme 和 Common Lisp 物件系統的混合。
* EuLisp，嘗試開發一個新的高效和整潔的 Lisp。
* ISLISP，嘗試開發一個新的高效和整潔的 Lisp。標準化為 ISO/IEC 13816:1997，後來修訂為 ISO/IEC 13816:2007：《資訊科技 – 程式語言，它們的環境和系統軟體介面 – 程式語言 ISLISP》。
* IEEE Scheme，IEEE 標準 1178–1990（停用日期：2019-11-07）。
* ANSI Common Lisp（1994 年版），是美國國家標準協會（ANSI）的 Common Lisp 標準 ，由 X3J13 委員會建立，其章程是：開始於以《Common Lisp 語言》作為基礎文件，致力於通過公開的達成共識過程，找到 Common Lisp 實現的程式可移植性和相容性這個共通問題的解決方案。儘管形式上是 ANSI 標準，ANSI Common Lisp 的實現、銷售、使用和影響一直都是世界範圍的。
* ACL2，是 Common LISP 的一個應用式（免於副作用）變體。ACL2 既是可以建模電腦系統的程式語言，也是幫助證明這些模型性質的工具。
* GOAL，是一個電動遊戲程式語言，由 Andy Gavin 和 Jak and Daxter 團隊在頑皮狗開發。它是使用 Allegro Common Lisp 寫成並被用於整個 Jak and Daxter 系列遊戲的開發。

### 2000 年迄今

在 1990 年代衰退之後，Lisp 在 2000 年之後因一些關注而逐漸復甦。當其他人認為 Lisp 已經過時陳舊，受到保羅・格雷厄姆和埃里克・雷蒙等人關於 Lisp 的著作的啟發，很多新的 Lisp 編程者經常將其描述為令人大開眼界的經驗，並聲稱在本質上比較其它程式語言更有生產效率。這種意識的提高可對比於「人工智慧冬季」和 Lisp 在 1990 年代中期的短暫增長。

Common Lisp 開源社群建立了至今仍活躍的支援基礎有：CLiki，它是收集 Common Lisp 相關資訊的維基；Planet Lisp，它是收集了各種 Lisp 相關部落格的內容；Common-lisp.net，它是開源專案的代管站點；Quicklisp，它是含括了許多函式庫的裝載管理器。在 Common-lisp.net 上，推薦了 6 種開源和 2 種商業 Common Lisp 實現。

Scheme 社群基於廣泛接納的 R5RS 語言標準，開發了一些活躍至今的實作如 Chicken、Gambit、Gauche、Larceny 和 STklos 等。Scheme 實現要求建立了很多準標準函式庫和 Scheme 擴展功能。隨著 Scheme 實作使用者社群增長，始自 2003 年的語言標準化過程在 2007 年產生了 R6RS 標準，在 2013 年又通過了 R7RS-small 最終草案，它已經有了一些實現支援。使用 Scheme 介紹計算機科學課程的學校似乎有所減少，麻省理工學院的計算機科學入門課程，已經不再使用 Scheme。

Clojure 是在 2007 年出現的新近 Lisp 方言，它編譯至 Java 虛擬機器並特別關注並行性。現今與 Lisp 有關的大多數新活動，包括開發新的跨平台函式庫和應用，都集中在 Scheme、Common Lisp、Emacs Lisp、Racket 和 Clojure 的實作上。

近年來又有了幾種新的 Lisp 方言：Arc、Hy、LFE、Axel 和 Fennel。此外，在 2007 年出現的 Nu，是 OS X 上採用 Lisp 式語法的手稿語言；在 2012 年出現的 Julia 所採用的語法解析器，是用 Scheme 方言 Femtolisp 實現的。在 2019 年 10 月，保羅・格雷厄姆發布了一個新的 Lisp 方言 Bel。

### Lisp 編程語族時間軸

## 主要方言

Common Lisp 和 Scheme 是 Lisp 發展的兩大主流的代表。這些語言體現了顯著不同的設計選擇。

Common Lisp 是 Maclisp 的後繼者。對它有重要影響的是 Lisp Machine Lisp、Maclisp、NIL、S-1 Lisp、Spice Lisp 和 Scheme。它擁有用於編程 Lisp 機器的大型 Lisp 方言 Lisp Machine Lisp 的很多特徵，但設計上能高效的實現在任何個人電腦或工作站上。Common Lisp 是通用程式語言，因而擁有一個大型語言標準，包括很多內建資料類型、函式、宏和其他語言元素，以及一個物件系統，即 Common Lisp 物件系統。Common Lisp 還從 Scheme 借鑑了特定特徵，比如詞法作用域和詞法閉包。Common Lisp 實現目標定為不同的平台，比如：LLVM、Java 虛擬機器、x86-64、PowerPC、Alpha、ARM、Motorola 68000 和 MIPS，和不同的作業系統，比如：Windows、macOS、Linux、Solaris、FreeBSD、NetBSD、OpenBSD、Dragonfly BSD 和 Heroku。

Scheme 是一個靜態作用域和適當尾遞迴的 Lisp 程式語言方言。它的設計有著異常清晰和簡單的語意，和很少的形成表達式的不同方式。它的設計大約比 Common Lisp 早上一個年代，Scheme 是一個相當極簡主義的設計。它擁有非常小的標準特徵集合，但具有在 Common Lisp 中未規定的特定實現特徵，比如尾遞迴最佳化和完全續體。在 Scheme 中能方便的表達廣闊的程式設計範式，包括指令式、函數式和訊息傳遞風格。Scheme 通過一系列的標準，即第 n 次修訂的演算法語言 Scheme 報告，和一系列 Scheme 實現要求而持續的演化。

Clojure 是 Lisp 的一個新近方言，其目標主要是 Java 虛擬機器、通用語言執行庫（CLR）和編譯成 JavaScript，它被設計為一個務實的通用程式語言。Clojure 受到了 Haskell 的相當大的影響，因而非常強烈的強調了不可變性。Clojure 提供了對 Java 框架和庫的存取，具有可選的類型提示和類型推論，這樣到 Java 的呼叫就可以避免反射並確使了快速的原始操作。Clojure 設計上不後向相容於其他 Lisp 方言。

進一步的，Lisp 方言在很多應用中被用作手稿語言，其中最周知的是在 Emacs 編輯器中的 Emacs Lisp，在 AutoCAD 中的 AutoLISP 和後來的 Visual Lisp，Audacity 中的 Nyquist，和 LilyPond 中 GNU Guile。有用的 Scheme 直譯器潛在有很小的大小，使得它特別流行於嵌入式指令碼。例子包括 SIOD 和 TinyScheme，二者都曾經以共享名字「Script-fu」成功的嵌入到了 GIMP 圖像處理軟體中。LIBREP 是 John Harper 最初基於 Emacs Lisp 語言開發的 Lisp 直譯器，它已經嵌入到了 Sawfish 視窗管理員。

### 標準化的方言

Lisp 有官方標準化和業界標準的方言：IEEE Scheme、ANSI Common Lisp、ISO ISLISP、R5RS Scheme 和 R7RS-small Scheme。

## 語法和語意

　
: **注意**：本文的例子是用 Common Lisp 書寫，但是其中的多數在 Scheme 中也是有效的，範例採用的 Common Lisp 實現是 SBCL。

### 符號表達式

Lisp 是一個面向表達式程式語言。不同於多數其他語言，在表達式和語句之間不做區分。所有代碼和資料都寫為表達式。當求值一個表達式的時候，它產生一個值（在 Common Lisp 中可能有多個值），它可以接著被嵌入到其他表達式中。每個值都可以是任何資料類型的。

McCarthy 的 1958 年論文介入兩種類型的語法：符號表達式即 S - 表達式或 sexps，它鏡像了代碼和資料的內部表示；和元表達式即 M - 表達式，它是與 S - 表達式對應的用類似數學符號表達的函式。M - 表達式從未得到青睞，幾乎所有今天的 Lisp 都使用 S - 表達式來操縱代碼和資料二者。

大量而單一的使用圓括號，是 Lisp 與其他程式語言家族最直接明顯的差別。為此學生們一直將 Lisp 戲稱為：「迷失在愚蠢的括號中」（**L**ost **I**n **S**tupid **P**arentheses），或「大量煩人的多餘括號」（**L**ots of **I**rritating **S**uperfluous **P**arentheses）。但是 S - 表達式語法也承擔了 Lisp 多數能力：語法極其正規，利於電腦操縱。然而 Lisp 的語法不局限於傳統的括號表示法，它可以擴充為包括可替代表示法。例如，XMLisp 是 Common Lisp 擴充，它採用元物件協定，整合了 S - 表達式和可延伸標記式語言（XML）。

有賴於表達式給予了語言巨大的靈活性。由於 Lisp 函式都寫為列表，它們可以完全就像資料那樣處理。這允許了輕易的書寫能操縱其他程式的程式，即進行元程式設計。很多 Lisp 方言使用宏系統來利用這個特徵，它確使了語言擴充而幾乎沒有限制。

### 列表

書寫 Lisp 列表，是以空白來分隔其元素，並包圍以圓括號。例如，`(1 2 foo)` 是其元素為三個原子 `1`、`2` 和 `foo` 的一個列表。這些值是隱含的有類型的：它們分別是兩個整數和叫做「符號」的 Lisp 專有資料類型，但不需要顯式的聲明。

空串列 `()` 也表示為特殊原子 `nil`。這是 Lisp 中既是原子又是列表的唯一實體。

表示式被寫為使用字首表示法的列表。在列表中第一個元素是一個函式的名字、一個宏的名字、一個 lambda 表達式或特殊算符的名字（見後）。列表的餘下部份是實際參數。例如，函式 `list` 將它的實際參數作為一個列表返回，所以表達式：

在前面例子中的 `foo` 之前的 `quote` 是特殊算符，它不求值就返回它的實際參數。任何未引述的表達式，在外圍表達式被求值之前，都遞迴的被求值。例如：

注意第三個實際參數是一個列表；列表是可以巢狀的。

### 算符

對算術算符的對待都是類似的。表達式：

其在中綴表示法下的等價形式為：`1 + 2 + 3 + 4`。

Lisp 沒有在 Algol 衍生語言中實現的那樣的算符概念。在 Lisp 中算術算符是可變參數函式（或多元函式），能夠接受任何數目的實際參數。C - 風格的 `++` 增加算符，有時在名字 `incf` 之下實現，給出的語法是：

等價於 `(setq x (+ x 1))`，它返回 `x` 的新值。

特殊算符（有時叫做特殊形式）提供了 Lisp 的控制結構。例如，特殊算符 `if` 接受三個實際參數。如果第一個實際參數為非 `nil`，它求值為第二實際參數；否則它求值為第三個實際參數。因此表達式：

當然，如果在 `nil` 的位置替換上非平凡的表達式會更有用處。

Lisp 還提供邏輯算符 `and`、`or` 和 `not`。`and` 和 `or` 算符進行短路求值，並分別返回它們的第一個 `nil` 或非 `nil` 實際參數：

### Lambda 表達式和函式定義

另一個特殊算符 `lambda`，被用來繫結變數到值，接著對表達式求進行求值。這個算符還被用於建立函式：給 `lambda` 的實際參數是一個形式參數列，和這個函式要求值的一個或多個表達式，它的返回值是其求值的最後一個表達式的值。表達式：

求值為一個函式，它接受一個實際參數，繫結它到 `arg` 並返回比這個實際參數大 `1` 的數。對待 Lambda 表達式於命名函式沒有區別；它們以相同方式呼叫。如下表達式：

這裡我們做了一次函式應用：我們通過傳遞給它值 `5` 而執行了這個匿名函式。

命名函式是通過使用 `defun` 宏，將一個 lambda 表達式儲存在一個符號之中而建立的：

`(defun f (a) b...)` 在全域環境中定義一個名為 `f` 的新函式。它在概念上類似於表達式：

這裡的 `setf` 是一個宏，用來設定第一個實際參數 `fdefinition 'f` 為一個新的函式物件。`fdefinition` 是對命名為 `f` 的函式的全域函式定義。`#'` 是特殊算符 `function` 的簡寫，它返回指定函式在當前詞法環境下的一個函式物件。

### 作用域和閉包

按照變數的作用域，可將 Lisp 家族劃分為兩大支系，分別使用動態作用域，或使用靜態（也叫做詞法）作用域。Scheme、Common Lisp 和 Clojure 預設使用靜態作用域，而 AutoLISP、PicoLisp 和 newLISP 使用動態作用域。Emacs Lisp 自從 Emacs 版本 24.1 起使用動態和詞法作用域二者。

### 原子

在最初的 LISP 中，有兩種基礎資料類型：原子和列表。列表是元素的一個有限有序序列，這裡的每個元素要麼是一個原子要麼是一個列表，而原子要麼是一個數要麼是一個符號。符號實質上是唯一性命名的專案，在原始碼中寫為字母數字串，並被要麼用作一個變數名字要麼符號處理中的一個資料專案。例如，列表 `(FOO (BAR 1) 2)` 包含三個元素：符號 `FOO`、列表 `(BAR 1)` 和數 `2`。

在原子和列表之間的本質區別是原子是不可變的和唯一性的。出現在原始碼中不同位置的兩個原子，如果以完全相同方式寫成則表示相同的物件，而每個列表都是一個分立的物件，它們可以獨立於其他列表而改變 ，並可以通過比較算符而區分於其他列表。

隨著後來的 Lisp 介入了更多的資料類型，和編程風格的演化，原子的概念失去了重要性。很多方言出於遺產相容性而保留了謂詞 `atom`，定義它為對不是 `cons` 的任何物件都為真。

### cons 和列表

Lisp 列表被實現為單向連結串列。這個連結串列的每個單元都叫做 `cons`（在 Scheme 中叫做 `pair`），它構成自兩個指標，分別叫做 `car` 和 `cdr`。

在眾多可以用 `cons` 單元構建的資料結構中，最基本一個叫做「適當列表」（proper list）。適當列表要麼是特殊的 `nil`（空串列）符號，要麼是一個 `cons`，它的 `car` 指向一個資料項（它可以是另一個 `cons` 結構比如一個列表），而 `cdr` 指向另一個適當列表。

如果一個給定 `cons` 被接受為一個連結串列的頭部，那麼它的 `car` 指向這個列表的第一個元素，而它的 `cdr` 指向這個列表的餘下部份。為此，在提及作為連結串列（而非樹等）一部份的 `cons` 的時候，`car` 和 `cdr` 函式也分別叫做 `first` 和 `rest`。

因此，Lisp 列表不是原子物件，它們類似 C++ 或 Java 中的容器類別的實例。一個列表就是連結的 `cons` 的一個聚集。參照一個給定列表的變數，簡單的就是到列表中第一個 `cons` 的指標。遍歷一個列表可以通過逐一 `cdr` 這個列表來進行，就是說連續的選取 `cdr` 來存取這個列表的每個 `cons`；或者通過使用任何一個將一個函式對映在一個列表之上的高階函式。

由於 `cons` 和列表在 Lisp 系統中是普遍性的，經常有人誤解它們是 Lisp 的唯一資料結構。事實上，除了最簡單者之外的所有 Lisp 都有其他資料結構，比如向量（陣列）、雜湊表、結構等等。

#### S - 表達式表示列表

圓括號的 S - 表達式表示了連結串列結構。有多種方式將相同的列表表示為一個 S - 表達式。`cons` 可以用「點對表示法」寫為 `(a . b)`，這裡的 `a` 是 `car` 而 `b` 是 `cdr`。更長的適當列表可以用點對表示法寫為 `(a . (b . (c . (d . nil))))`。這通常簡寫為列表表示法的 `(a b c d)`。「不適當列表」（improper list），可以用這二種表示法的組合來書寫，比如列表 `(a b c . d)` 有三個 `cons`，最後的 `cdr` 是 `d`，它就是完全特殊形式下的 `(a . (b . (c . d)))`。

#### 列表處理過程

Lisp 提供很多內建的過程，用來存取和控制列表。列表可以直接用 `list` 過程建立，它接受任何數目的實際參數，並返回這些實際參數的列表：

由於列表是從 cons 對構造而來，可以使用 `cons` 過程來在一個列表的前端增加一個元素。注意由於列表構造方法，`cons` 在處理列表實際參數上是不對稱的：

`append` 過程將兩個（或更多）列表相互附加。由於 Lisp 列表是連結串列，附加兩個列表有漸進時間複雜度 $O(n)$ ：

#### 共享結構

Lisp 列表，作為單向連結串列，可以相互共享結構。就是說，兩個列表可以有相同的尾部，或者最終的 `cons` 序列。例如，在執行下列 Common Lisp 代碼之後：

尾部 `(b c)` 在兩個列表中都是相同的結構。它不是復件；對於兩個列表指向 `b` 和 `c` 的 `cons` 單元都在相同的記憶體位置。

共享結構而非複製可以得到相當客觀的效能提升。但是這種技術可能以未預期的方式，互動於改變作為實際參數傳遞給它的列表的那些函式。改變一個列表，比如替代 `c` 為 `goose`，將會影響另一個列表：

不僅變更 `foo`，還變更了 `bar`，這可能是未預期的結果。這是缺陷的來源，為此改變它們的實際參數的那些函式被文件標示為破壞性的（destructive）。

函式語言程式設計愛好者避免破壞性函式。在青睞函數式風格的 Scheme 方言中，破壞性函式的名字都標記了警告性感嘆號，或者叫做「bang」，比如 `set-car!`（讀作 set car bang），它替換一個 `cons` 的 `car`。在 Common Lisp 方言中，破壞性函式是司空見慣的，與 `set-car!` 等價的是 `rplaca`，它的名字表示「replace car」。這個函式是不常見的，因為 Common Lisp 包括了一個特殊設施 `setf`，用來輕易的定義和使用破壞性函式。在 Common Lisp 中常見的風格是在構建原型的時候寫函數式代碼（沒有破壞性呼叫），接著將破壞性呼叫作為最佳化增加於可以安全的進行它們的地方。

### 自求值形式和引述

Lisp 求值使用者錄入的表達式。符號和列表求值為某個其他（通常更簡單的）表達式，例如：一個符號求值為它指名的變數的值；`(+ 2 3)` 求值為 `5`。但是，多數其他形式求值為其自身：如果錄入 `5` 到 Lisp 中，它返回 `5`。

任何表達式都可以加上防止被求值的標記，這對於符號和列表是需要的。特殊算符 `quote` 承擔了這個角色，它也簡寫為 `'`（一個單引號）。例如，通常如果錄入了符號 `foo`，它返回對應變數的值（沒有這個變數則為一個錯誤）。要參照這個文字符號，錄入要麼 `(quote foo)` ，要麼更常見的 `'foo`。

Common Lisp 和 Scheme 二者還支援「反引述」（backquote）算符（在 Scheme 中叫做准引述（quasiquote），這時錄入 `` ` `` 字元（重音符）。它幾乎同於普通引述，除了它允許表達式被求值，並將它們的值插入到引述列表之中，這些表達式標記了 `,`（逗號）表示去引述（unquote），或 `,@`（逗號 - at）表示拼接算符（unquote-splicing）。如果變數 `snue` 有值 `(bar baz)`，則 `` `(foo ,snue) `` 求值為 `(foo (bar baz))`，而 `` `(foo ,@snue) `` 求值為 `(foo bar baz)`。反引述經常用於定義宏展開。

自求值形式和引述形式是 Lisp 中文字的等價者。在程式碼中可以修改（可變）文字的值。例如，如果一個函式返回一個引述形式，而呼叫這個函式的代碼修改這個形式，這可以改變這個函式在後續呼叫時的行為：

像這樣修改一個引述形式通常被認為是不良風格，並且被 ANSI Common Lisp 定義為是危險的。它會導致在編譯檔案中的未定義的行為，因為檔案編譯器可以合併類似的常數並將它們放置到防寫記憶體中，等等。

Lisp 的引述形式化已經被 Douglas Hofstadter（在《Gödel, Escher, Bach》中）和其他人註解為自參照的哲學想法的例子。

### 控制結構

Lisp 最初有很少的控制結構，但是在語言演化期間卻增加了很多。Lisp 最初的條件算符是 `cond`，它或被視為後來的 `if-then-else` 結構的先驅。

Scheme 方言的編程者經常使用尾遞迴表達迴圈。Scheme 在學術電腦科學中的通行性，導致了一些學生相信尾遞迴是在 Lisp 中書寫迭代的唯一的或最常用的方式，但是這是不正確的。所有常見的 Lisp 方言都有指令式風格的迭代構造，從 Scheme 的 `do` 迴圈到 Common Lisp 的複雜的 `loop` 表達式。此外，使之成為客觀而非主觀事物的關鍵要點，是 Scheme 對尾遞迴的處理提出了特殊要求，Scheme 通常鼓勵使用尾遞迴的原因，是語言定義明確的支援了這種實踐。與之相反，ANSI Common Lisp 不要求常稱為尾遞迴消除的這種最佳化。因此，不鼓勵將尾遞迴風格作為使用更傳統的迭代構造（比如 `do`、`dolist` 或 `loop`）的替代品。在 Common Lisp 中不只是風格偏好的問題，而是潛在的效率問題，這是因為在 Common Lisp 中明顯的尾遞迴可能未被編譯為簡單的 `jump`；並且也是程式正確性問題，這是因為在 Common Lisp 中尾遞迴可能增加棧的使用而有堆疊溢位風險。

一些 Lisp 控制構造是特殊算符，等價於其他語言的語法關鍵字。使用這些算符的表達式與函式呼叫有著相同的表面外觀，但是不同之處在於參數不是必須求值的，或者在迭代表達式的情況下，可以被求值多於一次。

對比於多數其他主要程式語言，Lisp 允許使用語言自身實現控制結構。一些控制結構被實現為 Lisp 宏，想知道它們是如何工作的編程者甚至可以通過宏展開來研究。

Common Lisp 和 Scheme 二者都有非局部控制流程算符。在這些算符中的不同是在這兩種方言之間最深的差異。Scheme 使用 `call/cc` 過程支援可重入的續體，它允許一個程式儲存（並在將來恢復）執行中的特定位置。Common Lisp 不支援可重入的續體，但是支援處理逃脫續體的一些方式。

相同的演算法在 Lisp 中經常可以用要麼指令式要麼函數式風格來表達。如上所述，Scheme 趨於青睞函數式風格，使用尾遞迴和續體來表達控制流程。但是，指令式風格仍是很有可能的。很多 Common Lisp 編程者偏好的風格，可能讓使用結構化程式語言比如 C 的編程者看著更加熟悉，而 Scheme 編程者偏好的風格更加密切類似於純函式語言程式設計語言比如 Haskell。

由於 Lisp 在列表處理上的早期遺產，它擁有與在序列上迭代有關的一組廣泛的高階函式。在其他語言中需要顯式迴圈（比如 C 中的 `for` 迴圈）的很多情況下，在 Lisp 和很多函式語言程式設計語言中，相同的任務可以通過高階函式來完成。

一個好的例子是在 Scheme 中叫做 `map` 而在 Common Lisp 中叫做 `mapcar` 的函式。給定一個函式和一個或多個列表，`mapcar` 按順序將這個函式依次應用到這些列表的元素之上，並將結果收集入一個新的列表：

這個 `mapcar` 函式將 `+` 函式應用於每個對應的元素對之上。

### 程式碼的列表結構

在 Lisp 和其他語言之間的基本區別是，在 Lisp 中一個程式的文字表示，簡單的是人類可讀的描述，它同於底層 Lisp 系統使用的內部資料結構（連結串列、符號、數、字元等)。

Lisp 利用這一點來實現了一個非常強力的宏系統。就像其他宏語言比如 C，一個宏返回可以接著被編譯的代碼。但是不同於 C 的宏，Lisp 的宏是函式因而可以利用 Lisp 的全部能力。

進一步的，因為 Lisp 代碼作為列表有著相同的結構，宏可以使用語言中任何列表處理常式來建造。簡要的說，Lisp 可以在資料結構上做的任何事情，Lisp 宏都可以在代碼上做。相反的，在多數其他語言中，解析器的輸出是純粹的內部於語言實現的而不能被編程者操縱。

這個特徵可以在語言中開發高效語言。例如，Common Lisp 物件系統可以使用宏清晰的實現為一個語言擴充。這意味著如果一個應用需要不同的繼承機制，它可以使用不同的物件系統。這直接的對立於多數其他語言；例如，Java 不能支援多重繼承並且沒有增加它的合理方式。

在簡單的 Lisp 實現中，這個列表結構被直接的解釋來執行這個程式；一個函式是在文字上的一段列表結構，它被直譯器在執行它的時候遍歷。但是，多數後來的 Lisp 系統還包括一個編譯器。編譯器將列表結構轉換成機器碼或位元組碼用於執行。這個代碼可以像用常規語言比如 C 編譯的代碼一樣快速。

宏在編譯步驟之前展開，因而提供一些有價值的選項。如果一個程式需要一個預先計算了的表格，那麼一個宏可以在編譯時間建立這個表格，所以編譯器只需要輸出這個表格，而不需要在執行時間呼叫代碼來建立這個表格。一些 Lisp 實現甚至擁有一種 `eval-when` 機制，允許代碼在編譯時間期間出現（在一個宏需要它的時候），而不出現在發行的模組中。

### 求值和讀取–求值–列印迴圈

Lisp 語言經常被以互動式命令列來使用，它還可以結合入整合式開發環境（IDE）。使用者在命令列錄入表達式，或指示 IDE 將它們傳送給 Lisp 系統。Lisp 讀取錄入的表達式，求值它們，並列印結果。為此，Lisp 命令列被叫做讀取﹣求值﹣輸出迴圈（REPL）。

REPL 的基本操作描述如下。這是一個簡化的描述，省略了很多真實 Lisp 的元素，比如引述和宏。

`read` 函式接受文字的 S - 表達式作為輸入，並將它們解析為內部資料結構。例如，如果你在提示符下錄入文字 `(+ 1 2)`，`read` 將它轉換成有三個元素的一個連結串列：符號 `+`、數 `1` 和數 `2`。恰巧這個列表也是一段有效的 Lisp 代碼，就是說它是可以被求值的。這是因為 `car` 這個列表指名了一個函式即加法運算。

注意 `foo` 將被讀作一個單一符號。`123` 將被讀作數一百二十三。`"123"` 將被讀作字串 `"123"`。

`eval` 函式求值資料，返回零或多個其他 Lisp 資料作為結果。求值不必然意味著解釋；一些 Lisp 系統編譯所有的表達式為機器碼。但將求值描述為解釋是很簡單的：要求值其 `car` 指名一個函式的一個列表，`eval` 首先求值在它的 `cdr` 中的每個實際參數，接著應用這個函式於這些實際參數。在這個案例中，這個函式是加法，而應用它於實際參數列 `(1 2)` 產生答案 `3`。這是這個求值的結果。

符號 `foo` 求值為符號 `foo` 的值。資料比如字串 `"123"` 求值為相同的字串。列表 `(quote (1 2 3))` 求值為列表 `(1 2 3)`。

`print` 函式的工作是將輸入表示給使用者。對於簡單結果比如 `3` 這是平凡的。求值為一段列表結構的一個表達式會要求 `print` 遍歷這個列表並將結果輸出為一個 S - 表達式。

要實現一個 Lisp REPL，必需的只是實現這三個函式和一個無限迴圈函式。實現 `eval` 函式會很複雜是自然的，因為它必須也要實現所有特殊算符比如 `if` 或 `lambda`。它們完成後，一個基本的 REPL 就是一行代碼：`(loop (print (eval (read))))`。

Lisp REPL 典型的也提供輸入編輯、輸入歷史、錯誤處理和到除錯器的介面。

Lisp 通常使用及早求值。在 Common Lisp 中，實際參數以應用式次序（最左最內為先）求值，而在 Scheme 中實際參數的次序是未定義的，為編譯器最佳化留下了餘地。

## 語言創意

保羅・格雷厄姆辨識出 Lisp 區別於其他現存的語言如 Fortran 的九個重要特徵：

* 條件不受限於跳轉。
* 頭等函式。
* 遞迴。
* 將變數統一當作指標，將類型留給值。
* 垃圾回收。
* 程式完全構成自表達式而沒有語句。
* 符號資料類型，區別於字串資料類型。
* 代碼的表示法構成自符號樹（使用很多圓括號）。
* 完全的語言可以獲得於裝載時間、編譯時間和執行時間。

Lisp 是將程式碼的結構忠實而直接的表示為標準資料結構的第一個語言，這種品質後來被稱為「同像性」。故而 Lisp 函式可以在 Lisp 程式中被操縱、更改、甚至建立，而不用低層操縱。 這通常被認為是語言表達能力方面的主要優勢之一，使得語言適合於語法宏和元迴圈求值。

條件表達式是麥卡錫用 Fortran 寫一個象棋程式時發明的，他提議將其包含在 ALGOL 中但未被採納。Lisp 中的條件表達式使用了一般性的 `cond` 結構，ALGOL 60 採納了約翰・巴科斯提議的 if–then–else 條件語句並使之流行起來。

Lisp 深刻影響了艾倫・凱，他是在 Xerox PARC 開發 Smalltalk 的研究組的領導者；反過來 Lisp 又受到 Smalltalk 的影響，其後來的方言在 1970 年代接納了物件導向程式設計特徵，包括有繼承的類、封裝的實例、訊息傳遞等。Flavors 物件系統介入了多重繼承和混入的概念。Common Lisp 物件系統（CLOS）提供了多重繼承、具有多分派的多方法、和頭等泛化函式，從而產生了一種靈活而強力形式的動態分派。CLOS 充當了很多後來的包括 Scheme 在內的 Lisp 的物件系統的模板，它經常通過 Gregor Kiczales 等人發展出的元物件協定來實現，這是一種反射式元迴圈設計，其中的物件系統依據自身來定義。由於這些特徵的融合，Lisp 成為 Smalltalk 之後第二個具有元物件系統的語言。多年以後艾倫・凱宣稱，只有 Smalltalk 和 Lisp 可以視為完全意義上的物件導向程式設計系統。

Lisp 介入了自動垃圾回收的概念，即系統巡視堆來尋找無用的記憶體。現代複雜的垃圾回收演算法比如分代垃圾回收的進步，受到了它在 Lisp 中使用的激勵。

艾茲赫爾・戴克斯特拉在他的 1972 年圖靈獎演講中說道：

> 具有一些非常基本的原理作為基礎，它 [LISP] 已經展示出卓越的穩定性。除此之外，LISP 已經承載了相當可觀的在某種意義上我們最複雜的電腦應用。LISP 被玩笑的描述為「濫用電腦的最明智方式」。我認為這個描述是一種巨大的讚美，因為它傳達了解放的全部意味：它輔助大量我們最有天賦的人類同胞去思考在以前不可能的想法。
> 
> 

很大程度上由於它對於包括早期微處理器在內的早期電腦硬體的資源需求，Lisp 未能像 Fortran 和 ALGOL 後裔 C 語言那樣在人工智慧社群之外得以流行。由於它適合於複雜和動態的應用，Lisp 在 2010 年代享有了一定程度的大眾關注的復興。

## 七個原始運算

保羅・格雷厄姆從約翰・麥卡錫的最初論文中提煉出如下 7 個原始運算：

### quote

`(quote x)` 返回 `x`，通常簡記為 `'x`：

將 `quote` 寫成 `'` 只是一種語法糖。

### atom

`(atom x)` 當 `x` 是一個 `atom` 或者空的 `list` 時返回原子 `t`，否則返回 `NIL`。在 Common Lisp 中通常習慣用原子 `t` 列表示真，而用空串列 `()` 或 `NIL` 列表示假。例如：

`atom` 是需要求出實際參數值的算符，下面展示 `quote` 算符的作用，即通過引述一個列表，避免它被求值（`eval`）。一個未被引述的列表達式作為實際參數，`atom` 會將其視為代碼，例如：

這是因為 `(atom 'a)` 已求值出結果 `t`，把它代入 `(atom (atom 'a))`，成為 `(atom t)`，從而這個列表達式的結果是 `t`。

反之一個被引述的列表，僅僅被視為列表，例如：

參照看上去有些奇怪，因為很難在其它語言中找到類似的概念，但正是這一特徵構成了 Lisp 最為與眾不同的特點：代碼和資料使用相同的結構來列表示，只是用 `quote` 來區分它們。

### eq

`(eq x y)` 當 `x` 和 `y` 指向相同的物件的時候返回 `t`，否則返回 `NIL`，例如：

值得注意的是在 Common Lisp 中，原子物件在記憶體中只會有一份拷貝，所以 `(eq 'a 'a)` 返回 `t`。

### car

`(car x)` 要求 `x` 是一個列表，它返回 `x` 中的第一個元素，例如：

### cdr

`(cdr x)` 同樣要求 `x` 是一個列表，它返回 `x` 中除第一個元素之外的所有元素組成的列表，例如：

### cons

`(cons x y)` 預期 `y` 的值是一個列表，並且返回包含 `x` 的值和隨後 `y` 的值的那些元素的一個列表，例如：

### cond

`(cond (p1 e1) ...(pn en))` 的求值規則如下：對「條件列表達式 `p`」依次求值，直到有一個返回 `t`。如果能找到這樣的 `p` 列表達式，相應的「結果列表達式 `e`」的值，作為整個 `cond` 列表達式的返回值。例如：

## 物件系統

已經有各種物件系統和模型建造在 Lisp 之上、旁邊或其中，包括：

* Common Lisp 物件系統（CLOS），是 ANSI Common Lisp 內在的一部份。CLOS 衍生自 New Flavors 和 CommonLOOPS。ANSI Common Lisp 是第一個標準化的物件導向程式設計語言（1994, ANSI X3J13）。
* ObjectLisp 或 Object Lisp，用於 Lisp 機器公司和早期版本的 Macintosh Common Lisp。
* LOOPS（Lisp 物件導向程式設計系統）和後來的 CommonLOOPS。
* Flavors，建造於 MIT，它的後代是 New Flavors（由 Symbolics.com 開發）。
* KR（知識表達），它是用來輔助書寫 Common Lisp 的 GUI 庫 Garnet 的基於約束的物件系統。
* 知識工程環境（KEE）使用叫做 UNITS 的物件系統併集成入了推理機和推理維護系統（ATMS）。

## 範例

### Hello World!

這個 Hello World! 例子展示 Lisp 的三種主要方言，在基本輸出和函式定義上的用法：

### 階乘

Lisp 語法自然的適合於遞迴。數學問題比如遞迴定義集合的列舉，在這種表示法中表達是很容易的。例如，要求值一個數的階乘：

下面的版本在底層 Lisp 系統進行尾遞迴最佳化時比前面版本取用更少的堆疊空間：

對比上述例子，下面的指令式版本使用了 Common Lisp 的 `loop` 宏：

### 反轉列表

下列函式反轉一個列表。它與 Lisp 內建的 `reverse` 函式做同樣的事情：

## 參見

* 自修改代碼

## 參考文獻

## 延伸閱讀

## 外部連結

**歷史**

* History of LISP at the Computer History Museum （頁面存檔備份，存於網際網路檔案館）

**圖書和教程**

* Casting SPELs in Lisp （頁面存檔備份，存於網際網路檔案館）, a comic-book style introductory tutorial
* On Lisp （頁面存檔備份，存於網際網路檔案館）, a free book by Paul Graham
* Practical Common Lisp （頁面存檔備份，存於網際網路檔案館）, freeware edition by Peter Seibel
* Land of Lisp （頁面存檔備份，存於網際網路檔案館）, Official Website （頁面存檔備份，存於網際網路檔案館） for the book
* mal - Make a Lisp （頁面存檔備份，存於網際網路檔案館）
* Peter Norvig. Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp. 1992.

**資源**

* Awesome Lisp Languages
* CLiki: the Common Lisp wiki （頁面存檔備份，存於網際網路檔案館）
* Lisp FAQ Index （頁面存檔備份，存於網際網路檔案館）
* Planet Lisp （頁面存檔備份，存於網際網路檔案館）