LISP

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

Lisp

編程範型	多范型：函數式，過程式，同像性，反射式，元編程
設計者	約翰·麥卡錫
實作者	史帝芬·羅素, Timothy P. Hart和Michael I. Levin
面市時間	1958年​（1958）
型態系統	動態類型，強類型
衍生副語言
Arc, AutoLISP, Clojure, Common Lisp, Emacs Lisp, ISLISP, newLISP, PicoLisp, Racket, Scheme, SKILL, T
啟發語言
IPL
影響語言
CLU, Dylan, Falcon, Forth, Haskell, Io, JavaScript, Julia, Logo, Lua, LPC, MDL, ML, Nu, OPS5, Perl, POP-2/11, Python, REBOL, Ruby, Smalltalk, Wolfram語言

簡介

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

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

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

歷史

John McCarthy

Steve Russell

在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和沃恩·普拉特的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家族語言劃分為Lisp₁和Lisp₂（或寫為Lisp-1和Lisp-2）。

歷史上的重要方言

Lisp機器，現存於MIT博物館

• 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社群基於廣泛接納的R⁵RS語言標準，開發了一些活躍至今的實作如Chicken、Gambit、Gauche、Larceny和STklos等。Scheme實現要求建立了很多準標準函式庫和Scheme擴展功能。隨着Scheme實作用戶社群增長，始自2003年的語言標準化過程在2007年產生了R⁶RS標準，在2013年又通過了R⁷RS-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編程語族時間軸

Lisp時間軸

1955	1960	1965	1970	1975	1980	1985	1990	1995	2000	2005	2010	2015	2020
LISP I	LISP 1.5
		Maclisp
		BBN Lisp	Interlisp
				Scheme			IEEE 1178	R5RS		R6RS	R7RS-small
				Lisp Machine Lisp
					Franz Lisp
					Common Lisp		ANSI Common Lisp
						Emacs Lisp
						AutoLISP			Visual LISP
						PicoLisp
							newLISP
							PLT Scheme				Racket
								ISLISP
										Clojure
										Arc
										LFE
											Hy

主要方言

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、R⁵RS Scheme和R⁷RS-small Scheme。

語法和語義

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

符號表達式

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

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

大量而單一的使用圓括號，是Lisp與其他編程語言家族最直接明顯的差別。為此學生們一直將Lisp戲稱為：「迷失在愚蠢的括號中」（Lost In Stupid Parentheses），或「大量煩人的多餘括號」（Lots of Irritating Superfluous Parentheses）。但是S-表達式語法也承擔了Lisp多數能力：語法極其正規，利於計算機操縱。然而Lisp的語法不局限於傳統的括號表示法，它可以擴展為包括可替代表示法。例如，XMLisp是Common Lisp擴展，它採用元對象協議，集成了S-表達式和可擴展標記語言（XML）。

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

列表

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

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

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

* (list 1 2 (quote foo))
(1 2 FOO)

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

* (list 1 2 (list 3 4))
(1 2 (3 4))

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

算符

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

* (+ 1 2 3 4)
10

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

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

* (setq x 0)            
0

* (incf x)  
1

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

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

* (if nil
    (list 1 2 "foo")
    (list 3 4 "bar"))
(3 4 "bar")

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

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

* (or (and "zero" nil "never") "James" 'task 'time)
"James"

Lambda表達式和函數定義

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

* (lambda (arg) (+ arg 1))
#<FUNCTION (LAMBDA (ARG)) {5344B3FB}>

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

* ((lambda (arg) (+ arg 1)) 5)
6

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

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

* (defun foo (a b c d) (+ a b c d))
FOO

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

* (setf (fdefinition 'f) #'(lambda (a) (block f b...)))
#<FUNCTION (LAMBDA (A)) {5344BA1B}>

這裡的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和列表

主條目：列表構造函數

列表(42 69 613)的方框與指針示意圖

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過程創建，它接受任何數目的實際參數，並返回這些實際參數的列表：

* (list 1 2 'a 3)
(1 2 A 3)

* (list 1 '(2 3) 4)
(1 (2 3) 4)

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

* (cons 1 '(2 3))
(1 2 3)
 
* (cons '(1 2) '(3 4))
((1 2) 3 4)

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

* (append '(1 2) '(3 4))
(1 2 3 4)
 
* (append '(1 2 3) '() '(a) '(5 6))
(1 2 3 A 5 6)

共享結構

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

* (setf foo (list 'a 'b 'c))
(A B C)

* (setf bar (cons 'x (cdr foo)))
(X B C)

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

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

* (setf (third foo) 'goose)
GOOSE

* bar
(X B 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中文字的等價者。在程序代碼中可以修改（可變）文字的值。例如，如果一個函數返回一個引述形式，而調用這個函數的代碼修改這個形式，這可以改變這個函數在後續調用時的行為：

* (defun should-be-constant ()
    '(one two three))
SHOULD-BE-CONSTANT

* (let ((stuff (should-be-constant)))
    (setf (third stuff) 'bizarre))
BIZARRE

* (should-be-constant)
(ONE TWO BIZARRE)

像這樣修改一個引述形式通常被認為是不良風格，並且被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 #'+ '(1 2 3 4 5) '(10 20 30 40 50))
(11 22 33 44 55)

這個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 a)
A

* 'a
A

* (quote (a b c))
(A B C)

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

atom

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

* (atom 'a)
T

* (atom '(a b c))
NIL

* (atom '())
T

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

* (atom (atom 'a))
T

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

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

* (atom '(atom 'a))
NIL

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

eq

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

* (eq 'a 'a)
T

* (eq 'a 'b)
NIL

* (eq '() '())
T

* (eq '(a b c) '(a b c))
NIL

值得注意的是在Common Lisp中，原子對象在內存中只會有一份拷貝，所以(eq 'a 'a)返回t。

car

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

* (car '(a b))
A

cdr

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

* (cdr '(a b c))
(B C)

cons

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

* (cons 'a 'b)
(A . B)

* (cons 'a (cons 'b 'c))
(A B . C)

* (cons 'a  (cons 'b ()))
(A B)

* (cons 'a (cons 'b (cons 'c ())))
(A B C)

cond

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

* (cond ((eq 'a 'b) 'first)  ((atom 'a)  'second))
SECOND

對象系統

已經有各種對象系統和模型建造在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的三種主要方言，在基本輸出和函數定義上的用法：

Scheme	Common Lisp	Clojure
;; 显示过程在屏幕中打印字符串 ;; 并返回未规定值 (display "Hello, world!") ;; 定义过程hello-world (define (hello-world) (display "Hello, world!")) ;; 调用过程hello-world (hello-world)	;; 格式化函数在第一个参数是t时, ;; 在屏幕中打印字符串，并返回NIL (format t "hello, world!") ;; 定义函数hello-world (defun hello-world () (format t "hello, world!")) ;; 调用函数hello-world (hello-world)	;; 打印函数在屏幕中打印字符串 ;; 并返回nil (print "hello, world!") ;; 定义函数hello-world (defn hello-world [] (print "hello, world!")) ;; 调用函数hello-world (hello-world)

階乘

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

(defun factorial (n)
  (if (zerop n) 1
    (* n (factorial (1- n)))))

下面的版本在底層Lisp系統進行尾遞歸優化時比前面版本取用更少的堆棧空間：

(defun factorial (n &optional (acc 1))
  (if (zerop n) acc
    (factorial (1- n) (* acc n))))

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

(defun factorial (n)
  (loop for i from 1 to n
    for fac = 1 then (* fac i)
    finally (return fac)))

反轉列表

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

(defun -reverse (list)
  (let ((return-value))
    (dolist (e list) (push e return-value))
    return-value))

參見

• 自修改代碼

延伸閱讀

• McCarthy, John. History of Lisp. Stanford University. 1979-02-12 [2008-10-17]. 
• Steele, Jr., Guy L.; Richard P. Gabriel. The evolution of Lisp. The second ACM SIGPLAN conference on History of programming languages. New York, NY: ACM: 231–270. 1993 [2008-10-17]. ISBN 0-89791-570-4. 
• Richard Stallman. My Lisp Experiences and the Development of GNU Emacs. transcript of Richard Stallman's speech, 28 October 2002, at the International Lisp Conference. 
• Edmund Berkeley; Daniel G. Bobrow. The Programming Language LISP: Its Operation and Applications (PDF). Cambridge, Massachusetts: MIT Press. March 1964. 
• Weissman, Clark. LISP 1.5 Primer (PDF). Belmont, California: Dickenson Publishing Company Inc. 1967. 

外部連結

歷史

• 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 （頁面存檔備份，存於網際網路檔案館）