跳至內容

LISP

出自Taiwan Tongues 台語維基
這是此頁批准,以及是最近的修訂。

Lisp(歷史上拼寫為LISP), 是有悠久歷史的計算機程式語言家族,有獨特的完全用圓括號的前綴符號表示法。伊因為一九五八年,是現今仔第二悠久猶原廣泛使用的高階程式語言,只有 FORTRAN 程式語言比伊較早一年。Lisp 編程語族已經演變真濟種方言,現代上出名的通用編程方言是 Scheme、Common Lisp 佮這个新近的 Clojure。

簡介

Lisp 上原初是為計算機程式建立的實用數學表示法,彼陣借鑑過阿隆佐 ・ 邱奇的 lambda 表示法。伊真緊就成做人工智慧研究當中上受歡迎的程式語言。作為較早的高階程式語言之一,Lisp 開創了計算機科學領域的濟濟概念,包括樹結構、自動記憶體管理、動態型別、條件表達式、高階函式、遞迴、自主編譯器、讀取 ﹣ 求值 ﹣ 輸出循環(REPL)。

" LISP " 名稱源自「列表處理器」(英語:LISt Processor)的縮寫。列表是 Lisp 的主要數據結構之一,Lisp 編程代碼嘛仝款由列表組成。所以,Lisp 程式會當共原始碼當做數據結構進行操作,使用其中的宏系統,開發人員會當共家己定義的新語法抑是領域專用的語言,楷入去佇 Lisp 編程當中。

代碼佮數據的相換性做 Lisp 提供了隨可能辨識的語法。所有的 Lisp 程式碼攏寫為 S-表達式抑是以括號表示的列表。函式調用抑是語義的形式嘛仝款寫做列表,首先是函式抑是運算子的名稱,然後接紲是一抑是幾若个參數:比如講,取三个參數的函式 ` f ` 即為 ` ( f arg 一 arg 二 arg 三 ) `。

歷史

佇一九五八年,約翰 ・ 麥卡錫佇麻省理工學院發明矣 Lisp 程式語言。佇一九六O年,伊佇咧《ACM 通訊》發表了論文《符號表達式的遞迴函式佮其機器計算,第一部份》。 佇這篇論文中闡述了只要透過一寡簡單的運算子,以及借鑑自阿隆佐 ・ 邱奇的用佇咧匿名函式的表示法,就會當建立一个會當用佇咧演算法中的具圖靈完備性的語言。Lisp 閣採納佇咧一九五五年至一九五六年間建立的資訊處理語言所提出的列表處理佮遞迴概念。

約翰 ・ 麥卡錫佇咧上蓋初定義的 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 七百空四機器上使用拍空卡寫出的。史帝芬 ・ 羅素咧閱讀完約翰 ・ 麥卡錫的論文了後,認為講其中的 ` eval ` 函式會當用機器的碼來實作,創造一个會當做工課的 Lisp 直譯器。直譯器會當用來執行 Lisp 程式,抑是閣較適當的講「求值 Lisp 表達式」。

佇一九六O年發表的 LISP I 中,研究生 Daniel Edwards 開發糞埽回收程式,予咧通用計算機頂頭運行 Lisp 變甲可行。佇一九六二年,Timothy Hart 佮 Michael Levin 佇麻省理工學院以 Lisp 自身,實在做出第一个完整的 Lisp 編譯器。佇一九六三年,Timothy Hart 提議向 LISP 一爿五增加宏。

佇一九七五年,傑拉德 ・ 薩斯曼和蓋它 ・ 史拿而已二世開發了 Scheme,伊是使用詞法作用域佮尾呼叫最佳化的頭一个 Lisp 方言。佇一九八空年代到一九九空年代期間,蓋它 ・ 史拿而已二世、Scott Fahlman、Richard P . Gabriel、David A . Moon 和 Daniel Weinreb 等人,咧將彼个時陣新近的 Lisp 方言,其多數攏是 Maclisp 的後繼者比如講 ZetaLisp 和 NIL,統一成單一語言頂頭進行了誠大的努力。新語言 Common Lisp,佇某一種程度相讓伊所替代的方言。佇咧一九九四年,ANSI 出版矣 Common Lisp 標準《ANSI X 三石二二六石一千九百九十四資訊科技程式語言 Common Lisp》。 另外閣有1875入去編輯器 Emacs 中的 Emacs Lisp,伊非常流行並建立了家己的標準。

聯絡著人工的智慧

自從創始以來,Lisp 就密切聯絡佇人工的智慧研究社群,特別是佇咧 PDP 鋪十系統之上。佇一九七空年傑拉德 ・ 薩斯曼和特里 ・ 威諾格拉德使用 Lisp 實現程式語言 Micro-Planner,伊予人用佇咧出名的 AI 系統 SHRDLU 之中。

譜系佮方言

佇伊六十外年的歷史內底,Lisp 產生矣佇 S-表達語言的核心主旨上的真濟變體。此外,每一个共定方言閣可能有偌種實現,比如講 Common Lisp 就有十外種以上的實現。佇一種標準化去的方言內底,符合標準的實現支援仝款的核心語言,但是有著無仝的擴充佮函式庫。

佇方言間的差異可能是足顯目的,若像定義一个函式,Common Lisp 使用 Maclisp 佇一九六九年介入的關鍵字 ` defun `,而且 Scheme 使用伊佇一九七五年介入的 ` define `。Richard P . Gabriel 和 Kent Pitman 佇一九九八年的一篇論文中,照用統一的抑是分立的函式佮值號名空間,將 Lisp 家族的語言劃分做 Lisp 一和 Lisp 二(抑寫為 Lisp 板一和 Lisp 鋪二)。

歷史上的重要方言

  • LISP I,是第一个實現。
  • LISP 一垺五,是第一个廣泛發行的版本,由 McCarthy 佮其他的人佇咧 MIT 開發。按呢號名是因為伊包括了對上早的 LISP I 直譯器的改進,但是毋是 LISP 二規劃的彼種重大的重大的構。
  • Stanford LISP 一孵六,斯坦福 AI 實驗室開發的 LISP 一爿五後繼者,廣泛的發行佇執行 TOPS 鋪十作業系統的 PDP 鋪十系統。羅賓 ・ 米爾納的 LCF ML 執行佇咧 Stanford LISP 一孵六下。伊予 Maclisp 和 InterLisp 所淘汰。
  • MACLISP,由 MIT 的 MAC 計畫開發,伊是 LISP 一孵五的直接後代。伊執行佇 PDP 鋪十佮 Multics 系統上。MACLISP 後來予人號做 Maclisp,嘛通常號做 MacLisp。佇咧 MACLISP 中的「MAC」,也無關於著 Apple 的 Macintosh,閣無關於著 McCarthy。
  • Interlisp,由 BBN 科技開發,用佇執行 TENEX 作業系統的 PDP 鋪十系統之上,後來 InterLisp-D 予被 Xerox Lisp 機器接納並號做「西海岸 Lisp」。 猶閣有為是六千五百空二的 Atari 八位元機家族電腦發行的叫做「InterLISP 六十五」的小型版本。佇咧足長的一段時間內,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(一九七五年版), 上代先是佇 Maclisp 上執行的直譯器。
  • Common Lisp(一九八四年版), 是通過合併嘿 Maclisp 的無仝試看覓(ZetaLisp、Spice Lisp、NIL 和 S 影一 Lisp)來建立的方言,嘛有來自 Scheme 方言的影響。這个版本的 Common Lisp 佇廣泛的平台上攏得會到,對抑若予眾人接受做業界標準,一直到 ANSI Common Lisp(ANSI X 三孵二二六鼻一千九百九十四)出版。上廣泛傳播的 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 一爿三千八百十六 : 一千九百九十七,尾仔修訂做 ISO / IEC 一爿三千八百十六 : 兩千空七:《 資訊科技–程式語言,𪜶的環境佮系統軟體介面–程式語言 ISLISP》。
  • IEEE Scheme,IEEE 標準一千一百七十八–一千九百九十(停用日期:二千空一十九九九十一孵七)。
  • ANSI Common Lisp(一九九四年版), 是美國國家標準協會(ANSI)的 Common Lisp 標準,由 X 三 J 十三委員會建立,其實這个章程是:開始於以《Common Lisp 語言》做基礎文件,致使通過公開的達成共識過程,揣著 Common Lisp 實現的程式會當移植性佮相容性這个共通問題的解決方案。就算講形式上是 ANSI 標準,ANSI Common Lisp 的實現、銷售、使用佮影響一直攏是世界範圍的。
  • ACL 二,是 Common LISP 的一个應用式(毋免佇副作用)變體。ACL 二既然是會當建模電腦系統的程式語言,嘛是幫助證明遮的模型性質的工具。
  • GOAL,是一个電動遊戲程式語言,由 Andy Gavin 和 Jak and Daxter 團隊佇狡怪狗開發。伊是使用 Allegro Common Lisp 寫做並予人用規个 Jak and Daxter 系列遊戲的開發。

二空空空年到今

佇咧一九九空年代衰退了後,Lisp 佇咧二空空年了後因一寡關注啊若漸漸復甦。做其他的人認為 Lisp 已經過時陳舊的,受著保羅 ・ 格雷厄姆佮埃里克 ・ 雷蒙等人關於 Lisp 的著作的啟發,足濟新的 Lisp 編程者定定共欲描述做令人大開眼界的經驗,並且聲稱佇本質上比較其他程式語言閣較有生產效率。這種意識的提懸可比講「人工智慧冬季」和 Lisp 佇一九九空年代的中期的短暫增長。

Common Lisp 開源社群建立到今猶閣活跳的支援基礎有:CLiki,伊是收集 Common Lisp 相關資訊的維基;Planet Lisp,伊是收集了各種 Lisp 相關部落格的內容;Common-lisp . net,伊是開源專案的代管站點;Quicklisp,伊是含著真濟函式庫裝載管理器。佇咧 Common-lisp . net 上,推薦過六種開源佮兩種商業 Common Lisp 實現。

Scheme 社群基於廣泛接納的 R 五 RS 語言標準,開發一寡活跳到今的實作如 Chicken、Gambit、Gauche、Larceny 和 STklos 等。Scheme 實在要求建立了真濟準標準函式庫佮 Scheme 擴展功能。隨著 Scheme 實作使用者社群增長,自二空空三年的語言標準化過程佇二空空七年產生矣 R 六 RS 標準,佇咧二空一三年就閣通過矣 R 七 RS-small 最終草案,伊已經有一寡實現支援。使用 Scheme 紹介計算機科學課程的學校敢若有所減少,麻省理工學院的計算機科學入門課程,已經無閣使用 Scheme。

Clojure 是佇二空空七年出現的新近 Lisp 方言,伊編譯啊到 Java 虛擬機器並特別關注並行性。現今佮 Lisp 有關的大多數的新活動,包括開發新的跨平台函式庫佮應用,攏集中佇咧 Scheme、Common Lisp、Emacs Lisp、Racket 和 Clojure 的實作上。

近來閣有幾種新的 Lisp 方言:Arc、Hy、LFE、Axel 和 Fennel。此外,佇二空空七年出現的 Nu,是 OS X 上採用 Lisp 式語法的手稿語言;佇二空一二年出現的 Julia 所採用的語法來解析器,是用 Scheme 方言 Femtolisp 實現的。佇咧二空一九年十月,保羅 ・ 格雷厄姆發布了一个新的 Lisp 方言 Bel。

Lisp 編程語族時間軸

主要方言

Common Lisp 和 Scheme 是 Lisp 發展的兩大主流的代表。遮的語言體現出來矣無仝款的設計選擇。

Common Lisp 是 Maclisp 的後繼者。對伊有重要影響的是 Lisp Machine Lisp、Maclisp、NIL、S 影一 Lisp、Spice Lisp 和 Scheme。伊有用於編程 Lisp 機器的大型 Lisp 方言 Lisp Machine Lisp 的足濟特徵,猶毋過設計上會當高效的實這馬任何個人電腦抑是工作徛上。Common Lisp 是通用程式語言,因為按呢有一个大型的語言標準,包括真濟內建資料類型、函式、宏佮其他的語言的元素,猶閣有一个物件的系統,即 Common Lisp 東西系統。Common Lisp 猶閣對 Scheme 借鑑了特定特徵,比如詞法作用域佮詞法閉包。Common Lisp 實現目標定做無仝的平台,比如講:LLVM、Java 虛擬機器、x 八十六陵六十四、PowerPC、Alpha、ARM、Motorola 六桱八千佮 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 直譯器藏佇咧有足細的大細,予伊特別流行佇1875入式指令碼。例包括 SIOD 和 TinyScheme,二者攏捌以共享名「Script-fu」成功的1875入到矣 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 的一九五八年論文介入兩種類型的語法:符號表達式即 S-表達式抑是 sexps,伊鏡像代碼佮資料的內部表示;佮元表達式即 M-表達式,伊是佮 S-表達式對應的用類似數學符號表達的函式。M-表達式對無得著佮意,差不多所有今仔日的 Lisp 攏使用 S-表達式來操縱代碼佮資料二者。

大量而單一的使用圓括號,是 Lisp 佮其他的程式語言家族上蓋直接明顯的差別。為此學生囡仔一直將 Lisp 戲叫做:「 迷失佇咧戇愚的括號中」(LostInStupidParentheses), 抑是「大量煩惱人的加額括號」(Lots ofIrritatingSuperfluousParentheses)。 猶毋過 S-表達式語法嘛承擔矣 Lisp 多數能力:語法極其正,利於電腦操縱。毋過 Lisp 的語法無間限制傳統的括號表示法,伊有法度擴充做包括會當代表示法。比如講,XMLisp 是 Common Lisp 擴充,伊採用元物件協定,整合矣 S-表達式佮會當延伸標記式的語言(XML)。

有賴於表達式予語言大摸的靈活性。因為 Lisp 函式攏寫做列表,𪜶會當完全就像資料按呢處理。這允准著輕易的書寫會當操縱其他程式的程式,即進行元程式的設計。足濟的 Lisp 方言使用宏系統來利用這个特徵,伊確實語言擴充強欲無限制。

列表

書寫 Lisp 列表,是以空白來分隔其元素,並包圍以圓括號。比如講,` ( 一二 foo ) ` 是其元素為三个原子 ` 一 `、` 二 ` 和 ` foo ` 的一个列表。遮的值是隱含的有類型的:𪜶分別是兩个整數佮號做「符號」的 Lisp 專有資料的類型,毋過無需要顯式的聲明。

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

表示式予人寫做使用字首表示法的列表。佇咧列表中第一个元素是一个函式的名、一个宏的名、一个 lambda 表達式抑是特殊算符合的名(見後)。 列表的餘下部份是實際參數。比如講,函式 ` list ` 共伊的實際參數做一个列表倒轉來,所以表達式:

佇頭前例中的 ` foo ` 進前的 ` quote ` 是特殊算符,伊無求值就倒轉來伊的實際參數。任何無引進的表達式,佇外圍表達式被求值進前,攏交迴的被求值。比如講:

注意第三个實際參數是一个列表;列表是會當岫狀的。

算符

對這个算符的對待攏是類似的。表達式:

其中共表示法下的等價形式為:` 一 + 二 + 三 + 四 `。

Lisp 無佇咧 Algol 衍生語言中實現的彼款的算符概念。佇咧 Lisp 算符合是會當變參數函式(抑是多元函式), 會當接受任何數目的實際參數。C-風格的 ` + + ` 增加算符,有時佇名 ` incf ` 之下實現,予出的語法是:

等價於 ` ( setq x ( + x 一 ) ) `,伊閣倒轉來 ` x ` 的新值。

特殊算符合(有時仔號做特殊形式)提供矣 Lisp 的控制結構。比如講,特殊算符合 ` if ` 接受三个實際參數。若第一个實際參數為非 ` nil `,伊求值為第二實際的參數;抑無伊求值做第三个實際的參數。因此表達式:

當然喔,若佇咧 ` nil ` 的位置替換上非平凡的表達式會閣較有路用的。

Lisp 閣提供邏輯算符 ` and `、` or ` 和 ` not `。` and ` 和 ` or ` 算符進行短路求值,閣分別倒轉來𪜶的頭一个 ` nil ` 抑毋是 ` nil ` 實際參數:

Lambda 表達式佮函式定義

另外一个特殊算符仔 ` lambda `,予人用來結變數到值,紲落來對表達式求進行求值。這个算符猶閣予人用佇咧建立函式:給 ` lambda ` 的實際參數是一个形式參數列,和這个函式要求值的一个抑是多個表達式,伊的回值是其求值的上尾一个表達式的值。表達式:

求值為一个函式,伊接受一个實際的參數,結果伊到 ` arg ` 閣倒轉來比這實際參數大 ` 一 ` 的數。對待 Lambda 表達式於號名函式無區別;𪜶以仝款的方式呼叫做。如下表達式:

遮咱做一改函式應用:阮通過傳遞予值 ` 五 ` 煞來執行這个匿名函式。

號名函式是通過使用 ` defun ` 宏,將一个 lambda 表達式儲存佇咧一个符號內面抑若建立的:

` ( defun f ( a ) b . . . ) ` 佇咧全域環境中定義一个名做 ` f ` 的新函式。伊佇咧概念頂懸類似表達式:

遮的 ` setf ` 是一个宏,用來設定第一个實際的參數 ` fdefinition'f ` 為一个新的函式的物件。` fdefinition ` 是對號名做 ` f ` 的函式的全域函式定義。` #'` 是特殊算符 ` function ` 的簡寫,伊倒轉去指定函式佇咧當前詞法環境下的一个函式的物件。

作用域和閉包

照變數的作用域,可將 Lisp 家族仔分做兩大支系,分別使用動態作用域,抑是使用靜態(嘛叫做詞法)作用域。Scheme、Common Lisp 和 Clojure 預設使用靜態作用域,而且 AutoLISP、PicoLisp 和 newLISP 使用動態作用域。Emacs Lisp 自從 Emacs 版本二十四界做伙使用動態佮詞法作用域二者。

原子

佇咧上早的 LISP 中,有兩種基礎資料類型:原子佮列表。列表是元素的一个有限有序列,遮的逐个元素愛按怎是一个原子愛哪會是一个列表,啊若原子欲啥物是一个數欲啥物是一个符號乎。符號實質上是唯一性號名的專案,踮原始碼中寫做字母數字串,並且予欲按怎用做一个變數名欲按怎符號處理當中的一个資料專案。比如講,列表 ` ( FOO ( BAR 一 ) 二 ) ` 包括三个元素:符號 ` FOO `、列表 ` ( BAR 一 ) ` 和數 ` 二 `。

佇原子佮列表之間的彼个本質區別是原子是不可變的和唯一性的。出現佇原始碼中無仝位置的兩个原子,若是以完全仝款的方式去寫做仝款的物件,猶閣逐家列表攏是一个分立的物件,𪜶會當獨立佇咧其他列表來改變,並會使通過是較算符合區分佇其他列表。

綴後來的 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 求值使用者錄入的表達式。符號佮列表求值為某一个其他(通常閣較簡單的)表達式,比如講:一个符號求值為伊指名的變數的值;` ( + 二三 ) ` 求值為 ` 五 `。猶毋過,多數其他的形式求值為其他的身軀:伊若灌入 ` 五 ` 到 Lisp 中,伊閣倒轉來 ` 五 `。

任何表達式攏會當加上防止被求值的標記,這對符號佮列表是需要的。特殊算符合 ` 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-表達式做輸入,並且共𪜶解破做內部的資料結構。比如講,若是你咧提示符下錄入文字 ` ( + 一二 ) `,` read ` 共轉做有三个元素的一个連結串列:符號 ` + `、數 ` 一 ` 和數 ` 二 `。拄好這个列表嘛是一段有效的 Lisp 代碼,就是講伊是會當予人求值的。這是因為 ` car ` 這个列表指名矣一个函式即加法運算。

注意 ` foo ` 將被讀做一个單一符號。` 一百二三 ` 將被讀做一百二十三。` " 一百二三 " ` 將予人讀做字串 ` " 一百二三 " `。

` eval ` 函式求值資料,回零抑是濟个其他 Lisp 資料做結果。求值毋免數意思解說;一寡仔 Lisp 系統編譯所有的表達式為機器碼。但是將求一寡值來解說是真簡單:要求愛值其他 ` car ` 指名一个函式的一个列表,` eval ` 起先求值佇伊的 ` cdr ` 中的逐家實際參數,紲落來應用這个函式佇遮的實際來參數。佇這个案例中間,這个函式是加法,來應用伊佇實際的參數列 ` ( 一二 ) ` 產生答案 ` 三 `。這是這求值的結果。

符號 ` foo ` 求值做符號 ` foo ` 的值。資料比如講字攕 ` " 一百二三 " ` 求值為相仝的字捾。列表 ` ( quote ( 一二三 ) ) ` 求值為列表 ` ( 一二三 ) `。

` print ` 函式的工課是將輸入表示予使用者。嘿於簡單結果比如講 ` 三 ` 這是平凡的。求值為一段列表結構的一个表達式會要求 ` 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 六十採納矣約翰 ・ 巴科斯提議的 if–then–else 條件語句學起來是開始。

Lisp 深刻影響了艾倫 ・ 凱,伊是佇咧 Xerox PARC 開發 Smalltalk 的研究組的領導者;顛倒反 Lisp 閣受著 Smalltalk 的影響,其後來的方言佇一九七空年代接納了物件導向程式設計特徵,有包括有繼承的類、封裝的實例、訊息傳達等等。Flavors 物件系統介入真濟重繼承佮濫入的概念。Common Lisp 東西系統(CLOS)提供偌重繼承、有多分派的多方法、佮頭等泛化函式,從而產生了一種靈活而強力形式的動態分派。CLOS 充當了真濟後來的包括 Scheme 在內的 Lisp 的物件系統的模樣,伊通過 Gregor Kiczales 等人發展出的元物件協定來實現,這是一種反射式元迴圈設計,其中的物件系統根據家己來定義。因為遮的特徵的融合,Lisp 成做 Smalltalk 了後第二个有元物件系統的語言。多年以後艾倫 ・ 凱宣稱,只有 Smalltalk 和 Lisp 會當看做完全意義上的物件導向程式設計系統。

Lisp 介入了自動糞埽回收的概念,即系統巡視堆來走揣無路用的記持體。現代複雜的糞埽回收演算法比如分代糞埽回收的進步,受著矣伊佇咧 Lisp 中使用的激勵。

艾茲爾 ・ 戴克斯特拉佇伊的一九七二年圖靈獎演講當中講著:

> 誠有一寡非常基本的原理來做基礎,伊 [LISP] 已經展示出卓越的穩定性。除了這以外,LISP 已經有承載相當可觀的佇咧某一種意義上咱上複雜的電腦應用。LISP 予人耍笑對這个耍笑「濫用電腦的上明智方式」。 我認為是咧講這是一種大摸的讚美,因為伊傳達了解放的全部意味:伊輔助大量阮上有天賦的人類同胞去思考佇古早無可能的想法。 > >

真大的程度上因為伊對包括早期微處理器在內的早期電腦硬體的資源需求,Lisp 未能像 Fortran 和 ALGOL 後裔 C 語言彼款佇人工智慧社群以外會當時行。因為伊適合複雜佮動態的應用,Lisp 佇二空一空年代享有一定程度的大眾注意的復興。

七个原始運算

保羅 ・ 格雷厄姆對約翰 ・ 麥卡錫的上初論文中提煉出如下七个原始運算:

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 ( p 一 e 一 ) . . . ( pn en ) ) ` 求值規則如下:著「條件列表達式 ` p `」依次求值,一直到有一个倒轉去 ` t `。若會當揣著按呢的 ` p ` 列表達式,相應的「結果列表達式 ` e `」的值,作為規个 ` cond ` 列表達式的返回值。比如講:

東西系統

已經有各種物件系統佮模型建造佇咧 Lisp 之上、邊仔抑是邊仔,包括講:

  • Common Lisp 東西系統(CLOS), 是 ANSI Common Lisp 內底的一部份。CLOS 衍生自 New Flavors 和 CommonLOOPS。ANSI Common Lisp 是頭一个標準化的物件導向程式設計語言(一千九百九十四 , ANSI X 三 J 十三)。
  • 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 . 一千九百九十二 .

資源

  • Awesome Lisp Languages
  • CLiki : the Common Lisp wiki
  • Lisp FAQ Index
  • Planet Lisp