LISP
Lisp(過去拼寫為LISP)是具有悠久歷史的計算機編程語言家族,有獨特的完全用圓括號的前綴符號表示法[3]。它起源於1958年[4],是現今第二悠久而仍廣泛使用的高階程式語言,只有FORTRAN編程語言比它更早一年[5]。Lisp編程語族已經演變出許多種方言,現代最著名的通用編程方言是Scheme、Common Lisp和新近的Clojure。
![]() | |
編程範型 | 多范型:函數式,過程式,同像性,反射式,元編程 |
---|---|
設計者 | 約翰·麥卡錫 |
實作者 | 史帝芬·羅素, Timothy P. Hart和Michael I. Levin |
面市時間 | 1958年 |
型態系統 | 動態類型,強類型 |
衍生副語言 | |
Arc, AutoLISP, Clojure, Common Lisp, Emacs Lisp, ISLISP, newLISP, PicoLisp, Racket, Scheme, SKILL, T | |
啟發語言 | |
IPL | |
影響語言 | |
CLU, Dylan, Falcon, Forth, Haskell, Io, JavaScript, Julia[1], Logo, Lua, LPC, MDL, ML, Nu, OPS5, Perl, POP-2/11, Python, REBOL, Ruby, Smalltalk, Wolfram語言[2] |
簡介
編輯Lisp最初是為計算機程序創建的實用數學表示法[6],當時借鑒過阿隆佐·邱奇的lambda表示法[7]。它很快成為人工智能研究中最受歡迎的編程語言[8]。作為早期的高階編程語言之一,Lisp開創了計算機科學領域的許多概念,包括樹結構、自動記憶體管理、動態類型、條件表達式[9]、高階函數[10]、遞迴[11]、自主編譯器[12]、讀取﹣求值﹣輸出循環(REPL)[13]。
Lisp的名稱源自「列表處理器」(英語:list processor)的縮寫[14]。列表是Lisp的主要數據結構之一,Lisp編程代碼也同樣由列表組成。因此,Lisp程序可以把源代碼當作數據結構進行操作,而使用其中的宏系統,開發人員可將自己定義的新語法或領域專用的語言,嵌入在Lisp編程中。
代碼和數據的可互換性為Lisp提供了立即可辨識的語法。所有的Lisp程序代碼都寫為S-表達式或以括號表示的列表。函數調用或語義形式也同樣寫成列表,首先是函數或操作符的名稱,然後接著是一或多個參數:例如,取三個參數的函數f
即為(f arg1 arg2 arg3)
。
歷史
編輯在1958年,約翰·麥卡錫在麻省理工學院發明了Lisp程式語言[4]。在1960年,他在《ACM通訊》發表了論文《符號表達式的遞迴函數及其機器計算,第一部份》[15]。在這篇論文中闡述了只要透過一些簡單的運算子,以及借鑒自阿隆佐·邱奇的用於匿名函數的表示法[7],就可以建立一個可用於演算法中的具圖靈完備性的語言。Lisp還採納了在1955年至1956年間創建的資訊處理語言所提出的列表處理與遞歸概念。
約翰·麥卡錫在最初定義的Lisp之中,先將程序表達為M-表達式(元表達式)[16],再將它轉換成S-表達式(符號表達式),舉例來說M-表達式的car[cons[A;B]]
,等同於S-表達式的(car (cons A B))
。S-表達式可以將複雜結構表示為列表,在Lisp被實現了之後,編程者一般只使用S-表達式,而棄用M-表達式,這使得程式具備了同像性,即程式與資料由同樣的結構儲存。M-表達式曾短暫存續於Horace Enea的MLisp和沃恩·普拉特的CGOL之中[17]。
第一個Lisp實作是在IBM 704機器上使用打孔卡寫出的[18]。史帝芬·羅素在閱讀完約翰·麥卡錫的論文後,認為其中的eval
函數可以用機器碼來實作[19],從而創造了一個能工作的Lisp解釋器[20]。解釋器可以用來運行Lisp程序,或者更恰當的說為:「求值Lisp表達式」[21]。
在1960年發表的LISP I中[22],研究生Daniel Edwards開發了垃圾回收程序,使得在通用計算機上運行Lisp變得可行。在1962年,Timothy Hart與Michael Levin在麻省理工學院以Lisp自身,實做出第一個完整的Lisp編譯器[23]。在1963年,Timothy Hart提議向LISP 1.5增加宏[24]。
在1975年,傑拉德·薩斯曼和蓋伊·史提爾二世開發了Scheme,它是使用詞法作用域和尾調用優化的第一個Lisp方言[25]。在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系統之上[26]。在1970年傑拉德·薩斯曼和特里·威諾格拉德使用Lisp實現了編程語言Micro-Planner[27],它被用在著名的AI系統SHRDLU之中。
譜系和方言
編輯在它六十餘年的歷史中,Lisp產生了在S-表達式語言的核心主旨上的很多變體[28]。此外,每個給定方言又可能有多種實現,例如Common Lisp就有十餘種以上的實現。在一種標準化了的方言之內,符合標準的實現支持相同的核心語言,但是有着不同的擴展和函數庫。
在方言間的差異可能是非常顯眼的,例如定義一個函數[29],Common Lisp使用Maclisp在1969年介入的關鍵字defun
[30],而Scheme使用它在1975年介入的define
[31]。Richard P. Gabriel和Kent Pitman在1998年的一篇論文中,按採用統一的還是分立的函數與值命名空間,將Lisp家族語言劃分為Lisp1和Lisp2(或寫為Lisp-1和Lisp-2)[32]。
歷史上的重要方言
編輯- LISP I[22],是第一個實現。
- LISP 1.5[33],是第一個廣泛發行的版本,由McCarthy和其他人在MIT開發。如此命名是因為它包含了對最初的LISP I解釋器的改進,但不是LISP 2規劃的那種重大重構。
- Stanford LISP 1.6[34],是斯坦福AI實驗室開發的LISP 1.5後繼者,廣泛的發行於運行TOPS-10操作系統的PDP-10系統。羅賓·米爾納的LCF ML運行在Stanford LISP 1.6下[35]。它被Maclisp和InterLisp所淘汰。
- MACLISP[36],由MIT的MAC計劃開發,它是LISP 1.5的直接後代[37]。它運行在PDP-10和Multics系統上。MACLISP後來被稱為Maclisp,也通常叫做MacLisp。在MACLISP中的「MAC」,既無關於Apple的Macintosh,又無關於McCarthy。
- Interlisp[38],由BBN科技開發,用於運行TENEX操作系統的PDP-10系統之上,後來InterLisp-D被Xerox Lisp機器接納並暱稱為「西海岸Lisp」。還有為基於6502的Atari 8位機家族計算機發行的叫做「InterLISP 65」的小型版本。在很長一段時間內,Maclisp和InterLisp相互之間是強有力的競爭者[37]。
- Franz Lisp,起源於加利福尼亞大學伯克利分校的計劃,後來由Franz Inc開發。這個名字是Franz Liszt的幽默變形,它不牽涉到Franz Inc後來銷售的Allegro Common Lisp。
- XLISP,由David Betz開發[39],AutoLISP基於了它。
- Standard Lisp和Portable Standard Lisp,是曾被廣泛使用和移植的猶他大學開發的版本,特別是用它寫成了計算機代數系統REDUCE。
- Lisp Machine Lisp,Symbolics稱其變體版本為ZetaLisp,它用在Lisp機器之上,是Maclisp的直接後代。Lisp Machine Lisp對Common Lisp有巨大影響。
- Le Lisp,是一個法國Lisp方言。最早的界面建造器之一(叫做SOS界面[40])是用Le Lisp寫成的。
- Scheme(1975年版),最初是在Maclisp上運行的解釋器[41]。
- Common Lisp(1984年版)[42],是通過合併對Maclisp的不同嘗試(ZetaLisp、Spice Lisp、NIL和S-1 Lisp)而創建的方言[43],也具有來自Scheme方言的實質影響。這個版本的Common Lisp在廣泛的平台上都能獲得到,從而被眾人接受為業界標準[44],直至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[45],後來修訂為ISO/IEC 13816:2007[46]:《信息技術 – 編程語言,它們的環境和系統軟件接口 – 編程語言 ISLISP》。
- IEEE Scheme,IEEE標準1178–1990(停用日期:2019-11-07)[47]。
- ANSI Common Lisp(1994年版),是美國國家標準協會(ANSI)的Common Lisp標準 ,由X3J13委員會創建,其章程是[48]:開始於以《Common Lisp語言》作為基礎文檔[42],致力於通過公開的達成共識過程,找到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編程者經常將其描述為令人大開眼界的經驗,並聲稱在本質上比較其它編程語言更有生產效率[49]。這種意識的提高可對比於「人工智能冬季」和Lisp在1990年代中期的短暫增長[50]。
Common Lisp開源社群建立了至今仍活躍的支援基礎有:CLiki,它是收集Common Lisp相關資訊的維基;Planet Lisp,它是收集了各種Lisp相關博客的內容;Common-lisp.net,它是開源專案的託管站點;Quicklisp,它是含括了許多函式庫的裝載管理器。在Common-lisp.net上,推薦了6種開源和2種商業Common Lisp實現[51]。
Scheme社群基於廣泛接納的R5RS語言標準[52],開發了一些活躍至今的實作如Chicken、Gambit、Gauche、Larceny和STklos等。Scheme實現要求建立了很多準標準函式庫和Scheme擴展功能。隨着Scheme實作用戶社群增長,始自2003年的語言標準化過程在2007年產生了R6RS標準[53],在2013年又通過了R7RS-small最終草案[54],它已經有了一些實現支持[55]。使用Scheme介紹計算機科學課程的學校似乎有所減少,麻省理工學院的計算機科學入門課程,已經不再使用Scheme[56][57]。
Clojure是在2007年出現的新近Lisp方言,它編譯至Java虛擬機並特別關注並發性。現今與Lisp有關的大多數新活動,包括開發新的跨平台函式庫和應用,都集中在Scheme、Common Lisp、Emacs Lisp、Racket和Clojure的實作上。
近年來又有了幾種新的Lisp方言:Arc、Hy、LFE、Axel[58]和Fennel[59]。此外,在2007年出現的Nu,是OS X上採用Lisp式語法的腳本語言;在2012年出現的Julia語言所採用的語法解析器,是用Scheme方言Femtolisp實現的。在2019年10月,保羅·格雷厄姆發布了一個新的Lisp方言Bel[60]。
Lisp編程語族時間軸
編輯主要方言
編輯Common Lisp和Scheme是Lisp發展的兩大主流的代表。這些語言體現了顯著不同的設計選擇。
Common Lisp是Maclisp的後繼者。對它有重要影響的是Lisp Machine Lisp、Maclisp、NIL、S-1 Lisp、Spice Lisp和Scheme[61]。它擁有用於編程Lisp機器的大型Lisp方言Lisp Machine Lisp的很多特徵,但設計上能高效的實現在任何個人計算機或工作站上。Common Lisp是通用編程語言,因而擁有一個大型語言標準,包括很多內建數據類型、函數、宏和其他語言元素,以及一個對象系統,即Common Lisp對象系統。Common Lisp還從Scheme借鑑了特定特徵,比如詞法作用域和詞法閉包。Common Lisp實現目標定為不同的平台,比如:LLVM[62]、Java虛擬機[63]、x86-64、PowerPC、Alpha、ARM、Motorola 68000和MIPS[64],和不同的操作系統,比如:Windows、macOS、Linux、Solaris、FreeBSD、NetBSD、OpenBSD、Dragonfly BSD和Heroku[65]。
Scheme是一個靜態作用域和適當尾遞歸的Lisp編程語言方言[66]。它的設計有着非常清晰和簡單的語義,和很少的形成表達式的不同方式。它的設計大約比Common Lisp早上一個年代,Scheme是一個相當極簡主義的設計。它擁有非常小的標準特徵集合,但具有在Common Lisp中未規定的特定實現特徵,比如尾遞歸優化和完全續體。在Scheme中能方便的表達廣闊的編程范型,包括指令式、函數式和消息傳遞風格。Scheme通過一系列的標準,即第n次修訂的算法語言Scheme報告,和一系列Scheme實現要求而持續的演化。
Clojure是Lisp的一個新近方言,其目標主要是Java虛擬機、通用語言運行庫(CLR)和編譯成JavaScript,它被設計為一個務實的通用編程語言。Clojure受到了Haskell的相當大的影響,因而非常強烈的強調了不可變性[67]。Clojure提供了對Java框架和庫的訪問,具有可選的類型提示和類型推論,這樣到Java的調用就可以避免反射並確使了快速的原始操作。Clojure設計上不後向兼容於其他Lisp方言[68]。
進一步的,Lisp方言在很多應用中被用作腳本語言,其中最周知的是在Emacs編輯器中的Emacs Lisp,在AutoCAD中的AutoLISP和後來的Visual Lisp,Audacity中的Nyquist,和LilyPond中GNU Guile。有用的Scheme解釋器潛在有很小的大小,使得它特別流行於嵌入式腳本。例子包括SIOD和TinyScheme,二者都曾經以共用名字「Script-fu」成功的嵌入到了GIMP圖像處理軟件中[69]。LIBREP是John Harper最初基於Emacs Lisp語言開發的Lisp解釋器,它已經嵌入到了Sawfish窗口管理器[70]。
標準化的方言
編輯Lisp有官方標準化和業界標準的方言:IEEE Scheme[47]、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戲稱為:「迷失在愚蠢的括號中」(Lost In Stupid Parentheses),或「大量煩人的多餘括號」(Lots of Irritating Superfluous Parentheses)[71]。但是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
的新值。
特殊算符(有時叫做特殊形式[72])提供了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
的實際參數是一個形式參數列表,和這個函數要求值的一個或多個表達式,它的返回值是其求值的最後一個表達式的值[73]。表達式:
* (lambda (arg) (+ arg 1))
#<FUNCTION (LAMBDA (ARG)) {5344B3FB}>
求值為一個函數,它接受一個實際參數,綁定它到arg
並返回比這個實際參數大1
的數。對待Lambda表達式於命名函數沒有區別;它們以相同方式調用。如下表達式:
* ((lambda (arg) (+ arg 1)) 5)
6
這裡我們做了一次函數應用:我們通過傳遞給它值5
而執行了這個匿名函數。
命名函數是通過使用defun
宏[30],將一個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
是一個宏[74],用來設置第一個實際參數fdefinition 'f
為一個新的函數對象。fdefinition
是對命名為f
的函數的全局函數定義。#'
是特殊算符function
的簡寫,它返回指定函數在當前詞法環境下的一個函數對象[10]。
作用域
編輯按照變量的作用域[75],可將Lisp家族劃分為兩大支系,分別使用動態作用域[76],或使用靜態(也叫做詞法)作用域[77]。Scheme、Common Lisp[78]和Clojure缺省使用靜態作用域,而AutoLISP、PicoLisp[79]和newLISP[80]使用動態作用域。Emacs Lisp自從Emacs版本24.1起使用動態和詞法作用域二者[81]。
原子
編輯在最初的LISP中,有兩種基礎數據類型:原子和列表。列表是元素的一個有限有序序列,這裡的每個元素要麼是一個原子要麼是一個列表,而原子要麼是一個數要麼是一個符號。符號實質上是唯一性命名的項目,在源代碼中寫為字母數字串,並被要麼用作一個變量名字要麼符號處理中的一個數據項目。例如,列表(FOO (BAR 1) 2)
包含三個元素:符號FOO
、列表(BAR 1)
和數2
。
在原子和列表之間的本質區別是原子是不可變的和唯一性的。出現在源代碼中不同位置的兩個原子,如果以完全相同方式寫成則表示相同的對象,而每個列表都是一個分立的對象,它們可以獨立於其他列表而改變 ,並可以通過比較算符而區分於其他列表。
隨着後來的Lisp介入了更多的數據類型,和編程風格的演化,原子的概念失去了重要性。很多方言出於遺產兼容性而保留了謂詞atom
,定義它為對不是cons
的任何對象都為真。
cons和列表
編輯(42 69 613)
的方框與指針示意圖Lisp列表被實現為單向鍊表[82]。這個鍊表的每個單元都叫做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)[83],可以用這二種表示法的組合來書寫,比如列表(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列表是鍊表,附加兩個列表有漸進時間複雜度 :
* (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
[74],用來輕易的定義和使用破壞性函數。在Common Lisp中常見的風格是在構建原型的時候寫函數式代碼(沒有破壞性調用),接着將破壞性調用作為優化增加於可以安全的進行它們的地方。
自求值形式和引述
編輯Lisp求值用戶錄入的表達式。符號和列表求值為某個其他(通常更簡單的)表達式,例如:一個符號求值為它指名的變量的值;(+ 2 3)
求值為5
。但是,多數其他形式求值為其自身:如果錄入5
到Lisp中,它返回5
。
任何表達式都可以加上防止被求值的標記,這對於符號和列表是需要的。特殊算符quote
承擔了這個角色,它也簡寫為'
(一個單引號)。例如,通常如果錄入了符號foo
,它返回對應變量的值(沒有這個變量則為一個錯誤)。要引用這個文字符號,錄入要麼(quote foo)
,要麼更常見的'foo
[37]。
Common Lisp和Scheme二者還支持「反引述」(backquote)算符(在Scheme中叫做准引述(quasiquote),這時錄入`
字符(重音符)。它幾乎同於普通引述,除了它允許表達式被求值,並將它們的值插入到引述列表之中,這些表達式標記了,
(逗號)表示去引述(unquote),或,@
(逗號-at)表示拼接算符(unquote-splicing)。如果變量snue
有值(bar baz)
,則`(foo ,snue)
求值為(foo (bar baz))
,而`(foo ,@snue)
求值為(foo bar baz)
。反引述經常用於定義宏展開[84][85]。
自求值形式和引述形式是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
[9],它或被視為後來的if-then-else
結構的先驅。
Scheme方言的編程者經常使用尾遞歸表達循環。Scheme在學術計算機科學中的通行性,導致了一些學生相信尾遞歸是在Lisp中書寫迭代的唯一的或最常用的方式,但是這是不正確的。所有常見的Lisp方言都有指令式風格的迭代構造,從Scheme的do
循環到Common Lisp的複雜的loop
表達式。此外,使之成為客觀而非主觀事物的關鍵要點,是Scheme對尾遞歸的處理提出了特殊要求,Scheme通常鼓勵使用尾遞歸的原因,是語言定義明確的支持了這種實踐。與之相反,ANSI Common Lisp不要求常稱為尾遞歸消除的這種優化[86]。因此,不鼓勵將尾遞歸風格作為使用更傳統的迭代構造(比如do
、dolist
或loop
)的替代品[87]。在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
機制,允許代碼在編譯時間期間出現(在一個宏需要它的時候),而不出現在發行的模塊中[88]。
求值和讀取–求值–打印循環
編輯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中實際參數的次序是未定義的,為編譯器優化留下了餘地[89]。
語言創意
編輯保羅·格雷厄姆辨識出Lisp區別於其他現存的語言如Fortran的九個重要特徵[90]:
- 條件不受限於跳轉。
- 頭等函數。
- 遞歸。
- 將變量統一當作指針,將類型留給值。
- 垃圾回收。
- 程序完全構成自表達式而沒有語句。
- 符號數據類型,區別於字符串數據類型。
- 代碼的表示法構成自符號樹(使用很多圓括號)。
- 完全的語言可以獲得於裝載時間、編譯時間和執行時間。
Lisp是將程序代碼的結構忠實而直接的表示為標準數據結構的第一個語言,這種品質後來被稱為「同像性」。故而Lisp函數可以在Lisp程序中被操縱、更改、甚至創建,而不用低層操縱。 這通常被認為是語言表達能力方面的主要優勢之一,使得語言適合於語法宏和元循環求值。
條件表達式是麥卡錫用Fortran寫一個象棋程序時發明的,他提議將其包含在ALGOL中但未被採納[91]。Lisp中的條件表達式使用了一般性的cond
結構,ALGOL 60採納了約翰·巴科斯提議的if–then–else條件語句並使之流行起來[9]。
Lisp深刻影響了艾倫·凱[92],他是在Xerox PARC開發Smalltalk的研究組的領導者;反過來Lisp又受到Smalltalk的影響,其後來的方言在1970年代接納了面向對象編程特徵,包括有繼承的類、封裝的實例、消息傳遞等。Flavors對象系統介入了多重繼承和混入的概念。Common Lisp對象系統(CLOS)提供了多重繼承、具有多分派的多方法、和頭等泛化函數,從而產生了一種靈活而強力形式的動態分派。CLOS充當了很多後來的包括Scheme在內的Lisp的對象系統的模板,它經常通過Gregor Kiczales等人發展出的元對象協議來實現,這是一種反射式元循環設計[93],其中的對象系統依據自身來定義。由於這些特徵的融合,Lisp成為Smalltalk之後第二個具有元對象系統的語言。多年以後艾倫·凱宣稱,只有Smalltalk和Lisp可以視為完全意義上的面向對象編程系統[94]。
Lisp介入了自動垃圾回收的概念,即系統巡視堆來尋找無用的內存。現代複雜的垃圾回收算法比如分代垃圾回收的進步,受到了它在Lisp中使用的激勵[95]。
艾茲赫爾·戴克斯特拉在他的1972年圖靈獎演講中說道:
具有一些非常基本的原理作為基礎,它[LISP]已經展示出卓越的穩定性。除此之外,LISP已經承載了相當可觀的在某種意義上我們最複雜的計算機應用。LISP被玩笑的描述為「濫用計算機的最明智方式」。我認為這個描述是一種巨大的讚美,因為它傳達了解放的全部意味:它輔助大量我們最有天賦的人類同胞去思考在以前不可能的想法。[96]
很大程度上由於它對於包括早期微處理器在內的早期計算機硬件的資源需求,Lisp未能像Fortran和ALGOL後裔C語言那樣在人工智能社區之外得以流行。由於它適合於複雜和動態的應用,Lisp在2010年代享有了一定程度的大眾關注的復興[97]。
七個原始運算
編輯保羅·格雷厄姆從約翰·麥卡錫的最初論文中提煉出如下7個原始運算[98]:
quote
編輯(quote x)
返回x
,通常簡記為'x
:
* (quote a)
A
* 'a
A
* (quote (a b c))
(A B C)
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[99]或Object Lisp,用於Lisp機器公司和早期版本的Macintosh Common Lisp。
- LOOPS(Lisp面向對象編程系統)和後來的CommonLOOPS。
- Flavors,建造於MIT,它的後代是New Flavors(由Symbolics.com開發)。
- KR(知識表達),它是用來輔助書寫Common Lisp的GUI庫Garnet的基於約束的對象系統。
- 知識工程環境(KEE)使用叫做UNITS的對象系統併集成入了推理機[100]和推理維護系統(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))
參見
編輯參考文獻
編輯- ^ Julia Documentation - Introduction. [2022-11-16]. (原始內容存檔於2021-01-11).
Julia builds upon the lineage of mathematical programming languages, but also borrows much from popular dynamic languages, including Lisp, Perl, Python, Lua, and Ruby. …… some advantages of Julia over comparable systems include: …… Lisp-like macros and other metaprogramming facilities.
- ^ Wolfram Language Q&A. Wolfram Research. [2022-11-16]. (原始內容存檔於2022-09-20).
LISP and APL were two early influences, as was Stephen Wolfram's 1981 SMP symbolic computation language.
- ^ Edwin D. Reilly. Milestones in computer science and information technology. Greenwood Publishing Group. 2003: 156–157 [2021-10-24]. ISBN 978-1-57356-521-9. (原始內容存檔於2020-08-05).
- ^ 4.0 4.1
John McCarthy. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-10-25]. (原始內容 (PDF)存檔於2020-11-07).
There were two motivations for developing a language for the IBM 704. First, IBM was generously establishing a New England Computation Center at M.I.T. …… Second, IBM was undertaking to develop a program for proving theorems in plane geometry (based on an idea of Marvin Minsky’s), ……. ……
In connection with IBM’s plane geometry project, Nathaniel Rochester and Herbert Gelernter (on the advice of McCarthy) decided to implement a list processing language within FORTRAN, ……. This work was undertaken by Herbert Gelernter and Carl Gerberich at IBM and led to FLPL, standing for FORTRAN List Processing Language. ……
I spent the summer of 1958 at the IBM Information Research Department at the invitation of Nathaniel Rochester and chose differentiating algebraic expressions as a sample problem. It led to the following innovations beyond FLPL:
a. Writing recursive function definitions using conditional expressions. ……
b. The maplist function that forms a list of applications of a functional argument to the elements of a list. ……
c. To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). ……
d. The recursive definition of differentiation made no provision for erasure of abandoned list structure. ……
The implementation of LISP began in Fall 1958. ……
LISP is now the second oldest programming language in present widespread use (after FORTRAN and not counting APT, which isn’t used for programming per se). - ^ SICP: Foreword. (原始內容存檔於2001-07-27).
Lisp is a survivor, having been in use for about a quarter of a century. Among the active programming languages only Fortran has had a longer life.
- ^
Guy L. Steele Jr., Gerald J. Sussman. The Art of the Interpreter of the Modularity Complex (Parts Zero, One, and Two). MIT Libraries. May 1978 [2020-08-01]. hdl:1721.1/6094. (原始內容存檔於2021-01-24).
Contrary to popular belief, LISP was not originally derived from Church's λ-calculus [Church] [LISP History]. The earliest LISP did not have a well-defined notion of free variables or procedural objects. Early LISP programs were similar to recursion equations, defining functions on symbolic expressions ("S-expressions"). They differed from the equations of pure recursive function theory Kleene by introducing the conditional expression construction (often called the "McCarthy conditional"), to avoid "pattern-directed invocation". That is, in recursive function theory one would define the factorial function by the following two equations:
factorial(0) = 1
factorial(successor(x)) = successor(x) * factorial(x)
In early LISP, however, one would have written:
factorial[x] = [x=0 → 1; T → x*factoria1[x-1]]
where "[a → b; T → c]
" essentially means "if a then b else c
". The recursive function theory version depends on selecting which of two equations to use by matching the argument to the left-hand sides (such a discipline is actually used in the PROLOG language [Warren]); the early LISP version represents this decision as a conditional expression.
The theory of recursion equations deals with functions over the natural numbers. In LISP, however, one is interested in being able to manipulate algebraic expressions, programs, and other symbolic expressions as data structures. While such expressions can be encoded as numbers (using the technique of "arithmetization" developed by Kurt Gödel), such an encoding is not very convenient. Instead, a new kind of data called "S-expressions" (for "symbolic expressions") is introduced specifically to provide convenient encodings. S-expressions can be defined by a set of formal inductive axioms analogous to the Peano postulates used to define natural numbers. - ^ 7.0 7.1 John McCarthy. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-10-25]. (原始內容存檔 (PDF)於2020-11-07).
To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions. Church used higher order functionals instead of using conditional expressions. Conditional expressions are much more readily implemented on computers. ……
One mathematical consideration that influenced LISP was to express programs as applicative expressions built up from variables and constants using functions. I considered it important to make these expressions obey the usual mathematical laws allowing replacement of expressions by expressions giving the same value. The motive was to allow proofs of properties of programs using ordinary mathematical methods. This is only possible to the extent that side-effects can be avoided. Unfortunately, side-effects are often a great convenience when computational efficiency is important, and 「functions」 with side-effects are present in LISP. However, the so-called pure LISP is free of side-effects, and (Cartwright 1976) and (Cartwright and McCarthy 1978) show how to represent pure LISP programs by sentences and schemata in first order logic and prove their properties. ……
Free variables. In all innocence, James R. Slagle programmed the following LISP function definition and complained when it didn’t work right ……. …… In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained.
I must confess that I regarded this difficulty as just a bug and expressed confidence that Steve Russell would soon fix it. He did fix it but by inventing the so-called FUNARG device that took the lexical environment along with the functional argument. Similar difficulties later showed up in Algol 60, and Russell’s turned out to be one of the more comprehensive solutions to the problem. While it worked well in the interpreter, comprehensiveness and speed seem to be opposed in compiled code, and this led to a succession of compromises. …… the interested reader is referred to (Moses 1970) as a place to start.
David Turner. Some History of Functional Programming Languages (PDF). [2021-10-25]. (原始內容 (PDF)存檔於2020-04-15).The data on which LISP works is the S-language. ……
The M-language defines computations on S-expressions. ……
This is computationally complete. McCarthy (1960, Sect. 6) showed an arbitrary flowchart can be coded as mutually recursive functions.
The M-language of McCarthy (1960) is first order, as there is no provision to pass a function as argument or return a function as result.
However, McCarthy shows that M-language expressions and functions can be easily encoded as S-expressions and then defines in the M-language functions,eval
andapply
, that correctly interpret these S-expressions.
Thus LISP allows meta-programming, that is treating program as data and vice versa, by appropriate uses ofeval
andquote
. The 1960 paper gives the impression, quite strongly, that McCarthy saw this as removing any limitation stemming from the M-Language itself being first order.
It was originally intended that people would write programs in the M-language, in an Algol-like notation. In practice LISP programmers wrote their code directly in the S-language form, and the M-language became a kind of ghost that hovered in the background — theoretically important but nobody used it.
In LISP 1.5 (McCarthy et al. 1962) atoms acquired property lists, which serve several purposes and numbers appeared, as another kind of atom, along with basic arithmetic functions. ……
LISP was not based on the lambda calculus, despite using the word 「LAMBDA」 to denote functions. At the time he invented LISP, McCarthy was aware of (Church 1941) but had not studied it. The theoretical model behind LISP was Kleene’s theory of first order recursive functions. (McCarthy made these statements, or very similar ones, in a contribution from the floor at the 1982 ACM symposium on LISP and functional programming in Pittsburgh. No written version of this exists, as far as know.)
The M-language was first order, as already noted, but you could pass a function as a parameter by quotation, i.e. as the S-expression which encodes it. Unfortunately, this gives the wrong binding rules for free variables (dynamic instead of lexicographic). ……
McCarthy (1978) reports that this problem (wrong binding for free variables) showed up very early in a program of James Slagle. At first McCarthy assumed it was a bug and expected it to be fixed, but it actually springs from something fundamental — that meta-programming is not the same as higher order programming. Various devices were invented to get round this FUNARG problem, as it became known.
Not until SCHEME (Sussman 1975) did versions of LISP with default static binding appear. Today all versions of LISP are lambda calculus based. - ^ The Top Programming Languages in Artificial Intelligence. Artificial Intelligence. APRO. [2021-02-15]. (原始內容存檔於2020-10-30).
- ^ 9.0 9.1 9.2 John McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. (PDF). Communications of the ACM (ACM New York, NY, USA). 1960, 3 (4): 184–195 [2021-09-23]. doi:10.1145/367177.367199. (原始內容存檔 (PDF)於2021-02-19).
A conditional expression has the form
(p1 → e1, …, pn → en)
where thep
's are propositional expressions and thee
's are expressions of any kind. It may be read, 「Ifp1
thene1
otherwise ifp2
thene2
, …, otherwise ifpn
thenen
,」 or 「p1
yieldse1
, …,pn
yieldsen
.」
I sent a proposal for conditional expressions to a CACM forum on what should be included in Algol 60. Because the item was short, the editor demoted it to a letter to the editor, for which CACM subsequently apologized. The notation given here was rejected for Algol 60, because it had been decided that no new mathematical notation should be allowed in Algol 60, and everything new had to be English. The if...then...else that Algol 60 adopted was suggested by John Backus.
John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-10-25]. ISBN 0-262-13011-4. (原始內容存檔 (PDF)於2021-03-02).The conditional expression
[p1 → e1; …; pn → en]
is translated into(COND (p1* e1*) … (pn* en*))
. - ^ 10.0 10.1 John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-10-25]. ISBN 0-262-13011-4. (原始內容存檔 (PDF)於2021-03-02).
Mathematically, it is possible to have functions as arguments of other functions. For example, in arithmetic one could define a function operate
[op;a;b]
, whereop
is a functional argument that specifies which arithmetic operation is to be performed ona
andb
. ……
In LISP, functional arguments are extremely useful. A very important function with a functional argument ismaplist
. Its M-expression definition is
maplist[x;fn]=[null[x]→NIL;
T→cons[fn[x];maplist[cdr[x];fn]]]
……
The functional argument is, of course, a function translated into an S-expression. It is bound to the variablefn
and is then used wheneverfn
is mentioned as a function. The S-expression formaplist
itself is as follows:
(MAPLIST (LAMBDA (X FN) (COND ((NULL X) NIL)
(T (CONS (FN X) (MAPLIST (CDR X) FN))) )))
……
Usingmaplist
, we definechange
by
change[a]=maplist[a;λ[[j];cons[car[j];X]]]
This is not a valid M-expression as defined syntactically in section 1.5 because a function appears where a form is expected. This can be corrected by modifying the rule defining an argument so as to include functional arguments:
<argument> ::= <form> | <function>
We also need a special rule to translate functional arguments into S-expression. Iffn
is a function used as an argument, then it is translated into(FUNCTION fn*)
.
Example
(CHANGE (LAMBDA (A) (MAPLIST A (FUNCTION
(LAMBDA (J) (CONS (CAR J) (QUOTE X))) )))
An examination ofevalquote
shows thatQUOTE
will work instead ofFUNCTION
, provided that there are no free variables present.
Special Operator FUNCTION. Common Lisp HyperSpec. [2022-11-21]. (原始內容存檔於2022-11-30).
Syntax:
function
name ⇒ function
Arguments and Values:
name - a function name or lambda expression.
function - a function object.
Description:
The value offunction
is the functional value of name in the current lexical environment.
……
Notes:
The notation#' name
may be used as an abbreviation for(function name)
.
Function FUNCALL. Common Lisp HyperSpec. [2022-12-14]. (原始內容存檔於2022-12-25).
Syntax:
funcall
function &rest args ⇒ result*
Arguments and Values:
function - a function designator.
args - arguments to the function.
results - the values returned by the function.
Description:
funcall
applies function to args. If function is a symbol, it is coerced to a function as if by finding its functional value in the global environment. - ^ John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-09-23]. ISBN 0-262-13011-4. (原始內容 (PDF)存檔於2021-03-02).
A function can be simply a name. In this case its meaning must be previously understood. A function may be defined by using the lambda notation and establishing a correspondence between the arguments and the variables used in a form. If the function is recursive, it must be given a name by using a label. ……
When a symbol stands for a function, the situation is similar to that in which a symbol stands for an argument. When a function is recursive, it must be given a name. This is done by means of the formLABEL
, which pairs the name with the function definition on the a-list. The name is then bound to the function definition, just as a variable is bound to its value.
In actual practice,LABEL
is seldom used. It is usually more convenient to attach the name to the definition in a uniform manner. This is done by putting on the property list of the name, the symbolEXPR
followed by the function definition. The pseudo-functiondefine
used at the beginning of this section accomplishes this. Whenapply
interprets a function represented by an atomic symbol, it searches the p-list of the atomic symbol before searching the current a-list. Thus adefine
will override aLABEL
.
The fact that most functions are constants defined by the programmer, and not variables that are modified by the program, is not due to any weakness of the system. On the contrary, it indicates a richness of the system which we do not know how to exploit very well. - ^ Paul Graham. Revenge of the Nerds. [2013-03-14]. (原始內容存檔於2019-06-07).
- ^ Chisnall, David. Influential Programming Languages, Part 4: Lisp. 2011-01-12 [2021-10-24]. (原始內容存檔於2021-03-01).
- ^ Jones, Robin; Maynard, Clive; Stewart, Ian. The Art of Lisp Programming. Springer Science & Business Media. December 6, 2012: 2. ISBN 9781447117193.
- ^
John McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. (PDF). Communications of the ACM (ACM New York, NY, USA). 1960, 3 (4): 184–195 [2021-09-23]. doi:10.1145/367177.367199. (原始內容 (PDF)存檔於2021-02-19).
In this article, we first describe a formalism for defining functions recursively. …… Next, we describe S-expressions and S-functions, give some examples, and then describe the universal S-function apply which plays the theoretical role of a universal Turing machine and the practical role of an interpreter. Then we describe the representation of S-expressions in the memory of the IBM 704 by list structures similar to those used by Newell, Shaw and Simon, and the representation of S-functions by program. Then we mention the main features of the LISP programming system for the IBM 704. Next comes another way of describing computations with symbolic expressions, and finally we give a recursive function interpretation of flow charts. ……
We shall need a number of mathematical ideas and notations concerning functions in general. Most of the ideas are well known, but the notion of conditional expression is believed to be new, and the use of conditional expressions permits functions to be defined recursively in a new and convenient way. ……
We shall first define a class of symbolic expressions in terms of ordered pairs and lists. Then we shall define five elementary functions and predicates, and build from them by composition, conditional expressions, and recursive definitions an extensive class of functions of which we shall give a number of examples. We shall then show how these functions themselves can be expressed as symbolic expressions, and we shall define a universal function apply that allows us to compute from the expression for a given function its value for given arguments. Finally, we shall define some functions with functions as arguments and give some useful examples. ……
The LISP programming system is a system for using the IBM 704 computer to compute with symbolic information in the form of S-expressions. …… The basis of the system is a way of writing computer programs to evaluate S-functions. …… In addition to the facilities for describing S-functions, there are facilities for using S-functions in programs written as sequences of statements along the lines of FORTRAN or ALGOL. ……
There are a number of ways of defining functions of symbolic expressions which are quite similar to the system we have adopted. Each of them involves three basic functions, conditional expressions, and recursive function definitions, but the class of expressions corresponding to S-expressions is different, and so are the precise definitions of the functions. We shall describe one of these variants called linear LISP. ……
Since both the usual form of computer program and recursive function definitions are universal computationally, it is interesting to display the relation between them. The translation of recursive symbolic functions into computer programs was the subject of the rest of this report. In this section we show how to go the other way, at least in principle. - ^
Michael J. Fischer. Lambda-Calculus Schemata (PDF). LISP AND SYMBOLIC COMPUTATION: An International Journal, 6, 259–288. 1993 [2021-11-10]. (原始內容 (PDF)存檔於2022-03-02).
Two general approaches were taken in order to have programming languages with fully specified semantics: (i) Better specification methods were developed that were adequate to fully describe existing large programming languages such as PL/1. (ii) New languages were developed with clean mathematical structure that were more amenable to formal description. McCarthy pioneered the latter approach in basing the LISP 1.5 programming language on a simpler functional language, sometimes called 「pure LISP」 or M-expressions, that was defined in a mathematical style, independent of a particular machine or implementation.
Pure LISP allows the definition and evaluation of functions over S-expressions. The lambda notation for functional abstraction is borrowed from Church’s lambda calculus, but otherwise there is little similarity between the two systems. Pure LISP has no higher-order functions, and call-by-value evaluation order is implicitly assumed. Two special constructs, conditional expressions and the label operator, allow recursive functions to be defined. Limited as it is, pure LISP is nevertheless powerful enough to express all partial recursive functions and hence provides an adequate basis for a theory of computation.
The LISP 1.5 programming language extends pure LISP in many ways that make it more useful in practice but at the same time tend to destroy its clean mathematical properties. Its semantics is defined by an interpreter written in a mixture of pure LISP and English. The distinction between programs and data is blurred. Higher-order functions, assignment, and a global symbol table are added. - ^ CGOL: Algol-like language that compiles into Common Lisp. [2022-11-21]. (原始內容存檔於2022-12-30).
- ^ John McCarthy. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-10-25]. (原始內容存檔 (PDF)於2020-11-07).
The programs to be hand-compiled were written in an informal notation called M-expressions intended to resemble FORTRAN as much as possible. Besides FORTRAN-like assignment statements and go tos, the language allowed conditional expressions and the basic functions of LISP. Allowing recursive function definitions required no new notation from the function definitions allowed in FORTRAN I - only the removal of the restriction - as I recall, unstated in the FORTRAN manual - forbidding recursive definitions. The M-notation also used brackets instead of parentheses to enclose the arguments of functions in order to reserve parentheses for list-structure constants. It was intended to compile from some approximation to the M-notation, but the M-notation was never fully defined, because representing LISP functions by LISP lists became the dominant programming language when the interpreter later became available. A machine readable M-notation would have required redefinition, because the pencil-and-paper M-notation used characters unavailable on the IBM 026 key punch.
The READ and PRINT programs induced a de facto standard external notation for symbolic information, e.g. representingx + 3y + z
by(PLUS X (TIMES 3 Y) Z)
and(∀x)(P (x) ∨ Q(x, y)
by(ALL (X) (OR (P X) (Q X Y)))
.
……
Many people participated in the initial development of LISP, and I haven’t been able to remember all their contributions and must settle, at this writing, for a list of names. I can remember Paul Abrahams, Robert Brayton, Daniel Edwards, Patrick Fischer, Phyllis Fox, Saul Goldberg, Timothy Hart, Louis Hodes, Michael Levin, David Luckham, Klim Maling, Marvin Minsky, David Park, Nathaniel Rochester of IBM, and Steve Russell.
Stoyan, Herbert. Early LISP history (1956–1959). LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programming. Association for Computing Machinery: 307. 1984-08-06. doi:10.1145/800055.802047. (原始內容存檔於2005-04-05).It was McCarthy's fortune that he found a financial basis for his work: The MIT Artificial Intelligence Project was founded on the first of September, 1958. McCarthy became an assistant professor in the department of Electrical Engineering (his branch was communication sciences), Minsky was already assistant professor in the department of mathematics. They received support from the Research Laboratory for Electronics in the form of the two programmers, a secretary, a typewriter and six graduate students.
When Maling started his job at the first of September he met S. Russell who seems to have something to do already. Maling remembers: "We were housed in an office in the basement of one of MIT's buildings, near the computer center. Initially there was John, Steve Russell, Carol - a buxom Boston Irish secretary and I. Steve was a brilliant programmer who had worked for John at Dartmouth (I believe). He was what we then called a 'Programming bum' ...". - ^
Stoyan, Herbert. Early LISP history (1956–1959). LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programming. Association for Computing Machinery: 307. 1984-08-06. doi:10.1145/800055.802047. (原始內容存檔於2005-04-05).
As far as we know the first universal function was indeed
apply
-eval
was not present at all or not seen to be important. When McCarthy was working on this function S. Russel saw it and suggested translating it by hand - as he had done so often - and adding it to the program system. McCarthy recalls: "… thisEVAL
was written and published in the paper and Steve Russell said, look, why don't I program thisEVAL
and you remember the interpreter, and I said to him, ho, ho, you're confusing theory with practice, thisEVAL
is intended for reading not for computing. But he went ahead and did it. That is, he compiled theEVAL
in my paper into 704 machine code fixing bugs and then advertised this as a LISP interpreter which it certainly was, so at that point LISP had essentially the form that it has today, the S-expression form ...". - ^
John McCarthy. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-10-25]. (原始內容存檔 (PDF)於2020-11-07).
Another way to show that LISP was neater than Turing machines was to write a universal LISP function and show that it is briefer and more comprehensible than the description of a universal Turing machine. This was the LISP function
eval[e,a]
, which computes the value of a LISP expressione
- the second argumenta
being a list of assignments of values to variables. (a
is needed to make the recursion work). Writingeval
required inventing a notation representing LISP functions as LISP data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express LISP programs in practice. Logical completeness required that the notation used to express functions used as functional arguments be extended to provide for recursive functions, and theLABEL
notation was invented by Nathaniel Rochester for that purpose. ……
S.R. Russell noticed thateval
could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter. ……
Once theeval
interpreter was programmed, it became available to the programmer, and it was especially easy to use because it interprets LISP programs expressed as LISP data. In particular, eval made possible FEXPRS and FSUBRS which are 「functions」 that are not given their actual arguments but are given the expressions that evaluate to the arguments and must calleval
themselves when they want the expressions evaluated. The main application of this facility is to functions that don't always evaluate all of their arguments; they evaluate some of them first, and then decide which others to evaluate. This facility resembles Algol's call-by-name but is more flexible, becauseeval
is explicitly available. A first order logic treatment of 「extensional」FEXPR
s andFSUBR
s now seems possible. - ^ John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-10-25]. ISBN 0-262-13011-4. (原始內容存檔 (PDF)於2021-03-02).「
A form is an expression that can be evaluated. A form that is merely a constant has that constant as its value. If a form is a variable, then the value of the form is the S-expression that is bound to that variable at the time when we evaluate the form. ……
A function can be simply a name. In this case its meaning must be previously understood. A function may be defined by using the lambda notation and establishing a correspondence between the arguments and the variables used in a form. If the function is recursive, it must be given a name by using a label. ……
An interpreter or universal function is one that can compute the value of any given function applied to its arguments when given a description of that function. (Of course, if the function that is being interpreted has infinite recursion, the interpreter will recur infinitely also.)
We are now in a position to define the universal LISP functionevalqyote[fn;args]
. Whenevalquote
is given a function and a list of arguments for that function, it computes the value of the function applied to the arguments.
LISP functions have S-expressions as arguments. In particular, the argument "fn
" of the functionevalquote
must be an S-expression. Since we have been writing functions as M-expressions, it is necessary to translate them into S-expressions. ……evalquote
is defined by using two main functions, calledeval
andapply
.apply
handles a function and its arguments, whileeval
handles forms. Each of these functions also has another argument that is used as an association list for storing the values of bound variables and function names. ……
A variable is a symbol that is used to represent an argument of a function. ……
The formalism for variables in LISP is the Church lambda notation. The part of the interpreter that binds variables is calledapply
. Whenapply
encounters a function beginning withLAMBDA
, the list of variables is paired with the list of arguments and added to the front of the a-list During the evaluation of the function, variables may be encountered. They are evaluated by looking them up on the a-list. If a variable has been bound several times, the last or most recent value is used. The part of the interpreter that does this is calledeval
. The following example will illustrate this discussion. Suppose the interpreter is given the following doublet:
fn: (LAMBDA (X Y) (CONS X Y))
args: (A B)
evalquote
will give these arguments toapply
. (Look at the universal function of Section I.)
apply[(LAMBDA (X Y) (CONS X Y)); (A B);NIL]
apply
will bind the variables and give the function and a-list toeval
.
eval[(CONS X Y); ((X . A) (Y . B))]
eval
will evaluate the variables and give it tocons
.
cons[A;B] = (A . B)
The actual interpreter skips one step required by the universal function, namely,apply[CONS;(A B);((X . A) (Y . B))]
. ……
It is sometimes assumed that a constant stands for itself as opposed to a variable which stands for something else. …… It seems more reasonable to say that one variable is more nearly constant than another if it is bound at a higher level and changes value less frequently.
In LISP, a variable remains bound within the scope of theLAMBDA
that binds it. When a variable always has a certain value regardless of the current a-list, it will be called a constant. This is accomplished by means of the property list (p-list) of the variable symbol. Every atomic symbol has a p-list. When the p-list contains the indicatorAPVAL
, then the symbol is a constant and the next item on the list is the value.eval
searches p-lists before a-lists when evaluating variables, thus making it possible to set constants. ……
An interesting type of constant is one that stands for itself.NIL
is an example of this. It can be evaluated repeatedly and will still beNIL
.T
,F
.NIL
, and other constants cannot be used as variables. ……
The program form has the structure -
(PROG
, list of program variables, sequence of statements and atomic' symbols…)
……
Program variables are treated much like bound variables, but they are not bound byLAMBDA
. The value of each program variable isNIL
until it has been set to something else. To set a program variable, use the formSET
. To set variablePI
to3.14
write(SET (OUOTE PI) 3.14)
.SETQ
is likeSET
except that it quotes its first argument. Thus(SETQ PI 3.14)
.SETQ
is usually more convenient.SET
andSETQ
can change variables that are on the a-list from higher level functions. The value ofSET
orSETQ
is the value of its second argument. ……
Every atomic symbol has a property list. When an atomic symbol is read in for the first time, a property list is created for it.
A property list is characterized by having the special constant777778
(i.e., minus1
) as the first element of the list. The rest of the list contains various properties of the atomic symbol. Each property is preceded by an atomic symbol which is called its indicator. Some of the indicators are:
PNAME
- the BCD print name of the atomic symbol for input-output use.
EXPR
- S-expression defining a function whose name is the atomic symbol on whose property list theEXPR
appears.
SUBR
- Function defined by a machine language subroutine.
APVAL
- Permanent value for the atomic symbol considered as a variable.
The atomic symbolNIL
has two things on its property list - itsPNAME
, and anAPVAL
that gives it a value ofNIL
. Its property list looks like this:.---.---. .-----.---. .---.---. .-----.---. .---.---. |-1 | |->|APVAL| |->| | |->|PNAME| |->| | / | `---'---' `-----'---' `---'---' `-----'---' `---'---' ^ | | | .-V-.---. .-V-.---. | | | / | | | / | | `---'---' `---'---' | | | '-----------------------' .-V-----. | NIL???| `-------'
……
The indicatorEXPR
points to an S-expression defining a function. The functiondefine
putsEXPR
's on property lists. After definingff
, its property list would look like this.---.---. .-----.---. .---.---. .-----.---. .---.---. |-1 | |->|EXPR | |->| | |->|PNAME| |->| | / | `---'---' `-----'---' `---'---' `-----'---' `---'---' .-----------------------' | .-V----.---. .---.---. .---.---. .-V-.---. |LAMBDA| |->| | |->| | / | | | / | `------'---' `---'---' `---'---' `---'---' | | | .---.---. .----.---. .-V-----. | X | / | |COND| |-> - - - | FF????| `---'---' `----'---' `-------'
……
An indicator on a property list that does not have a property following it is called a flag. ……
Numbers are represented by a type of atomic symbol in LISP. This word consists of a word with-1
in the address, certain bits in the tag which specify that it is a number and what type it is, and a pointer to the number itself in the decrement of this word.
Unlike atomic symbols, numbers are not stored uniquely.
For example, the decimal number15
is represented as follows:.----.-.---. .--------------. | -1 |1| |->| 000000000017 | `----'-'---' `--------------'
……
special[x]
SUBR
pseudo-function
The listx
contains the names of variables that are to be declaredSPECIAL
. ……common[x]
SUBR
pseudo-function
The listx
contains the names of variables that are to be declaredCOMMON
. ……PROG
feature is anFSUBR
coded into the system. ……
When aset
or asetq
is encountered, the name of the variable is located on the a-list. The value of the variable (orcdr
of the pair) is actually replaced with the new value. ……
The following points should be noted concerning declared variables.
1. Program variables follow the same rules as λ variables do.
a. If a variable is purely local, it need not be declared.
b. Special variables can be used as free variables in compiled functions. They may be set at a lower level than that at which they are bound.
c. Common program variables maintain complete communication between compiled programs and the interpreter.
2.set
as distinct fromsetq
can only be used to set common variables.」 - ^ 22.0 22.1 John McCarthy; Robert Brayton; Daniel Edwards; Phyllis Fox; Louis Hodes; David Luckham; Klim Maling; David Park; Steve Russell. LISP I Programmers Manual (PDF). Boston, Massachusetts: Artificial Intelligence Group, M.I.T. Computation Center and Research Laboratory. March 1960 [2021-09-23]. (原始內容 (PDF)存檔於2022-04-02).
- ^
Timothy P. Hart, Michael I. Levin. AI Memo 39-The new compiler (PDF). [2022-11-24]. (原始內容存檔 (PDF)於2022-04-19).
The purpose of the LISP Compiler is to replace S-expression definitions of functions with efficient machine language subroutines. A subroutine can be expected to run about 40 times as fast as the interpreter can execute the same function from its S-expression definition. Subroutines typically take 70-80 per cent of the storage required by their corresponding S-expressions.
Timothy P. Hart, Michael I. Levin. LISP 1.5 compiler. [2022-11-24]. (原始內容存檔於2022-08-13). - ^ Hart, Timothy P. AIM-057, MACRO Definitions for LISP, Timothy P. Hart. October 1963. hdl:1721.1/6111.
- ^
Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978 [2021-10-26]. (原始內容存檔於2022-04-06).
SCHEME is a dialect of LISP. It is an expression-oriented, applicative order, interpreter-based language which allows one to manipulate programs as data.
It differs from most current dialects of LISP in that it closes all lambda-expressions in the environment of their definition or declaration, rather than in the execution environment. This has the consequence that variables are normally lexically scoped, as in ALGOL. However, in contrast with ALGOL, SCHEME treats procedures as a first-class data type. They can be the values of variables, the returned values of procedures, and components of data structures.
Another difference from LISP is that SCHEME is implemented in such a way that tail-recursions execute without net growth of the interpreter stack. The effect of this is that a procedure call behaves like a GOTO and thus procedure calls can be used to implement iterations, as in PLASMA. - ^ The 36-bit word size of the PDP-6/PDP-10 was influenced by the usefulness of having two Lisp 18-bit pointers in a single word. Peter J. Hurley. The History of TOPS or Life in the Fast ACs. Newsgroup: alt.folklore.computers. 18 October 1990 [2021-10-24]. Usenet: 84950@tut.cis.ohio-state.edu. (原始內容存檔於2013-05-28).
The PDP-6 project started in early 1963, as a 24-bit machine. It grew to 36 bits for LISP, a design goal.
- ^ Gerald Jay Sussman, Terry Winograd. Micro-planner Reference Manual. AI Memo No, 203, MIT Project MAC. 1970 [2022-12-07]. (原始內容存檔於2022-12-07).
Micro-Planner is an implementation of a subset of Cal Hewitt's language, PLANNER by Gerald Jay Sussman, Terry Winograd, and Eugene Charniak on the AI group computer in LISP.
- ^ Guy L.Steele, Jr., Richard P. Gabriel. The evolution of Lisp. The second ACM SIGPLAN conference on History of programming languages. ACM: 231–270. 1993 [2022-11-19]. (原始內容存檔於2022-11-12).
In this history of the evolution of Lisp, we have seen that Lisp seems to have a more elaborate and complex history than languages with wider usage. It would seem that almost every little research group has its own version of Lisp and there would appear to be as many Lisps as variations on language concepts. It is natural to ask what is so special or different about Lisp that explains it.
There are six basic reasons: ……
Its theoretical foundations. Lisp was founded on the footing of recursive function theory and the theory of computability. The work on Scheme aligned it with Church's lambda calculus and denotational semantics. Its purest form is useful for mathematical reasoning and proof. ……
Its expressiveness. Lisp has proved itself concerned more with expressiveness than anything else. ……
Its malleability. It is easy with Lisp to experiment with new language features, because it is possible to extend Lisp in such a way that the extensions are indistinguishable to users from the base language. Primarily this is accomplished through the use of macros, which have been part of Lisp since 1963 [Hart 1963]. ……
Its interactive and incremental nature. It is easy to explore the solutions to programming problems in Lisp, because it is easy to implement part of a solution, test it, modify it, change design, and debug the changes. ……
Its operating system facilities. Many Lisp implementations provide facilities reminiscent of operating systems: a command processor, an automatic storage management facility, file management, display (windows, graphics, mouse) facilities, multitasking, a compiler, an incremental (re)linker/loader, a symbolic debugger, performance monitoring, and sometimes multiprocessing. ……
Its people. Of course, languages do not diversify themselves; people diversify languages. ……Lisp is the language of artificial intelligence, among other things. …… Another attraction is that Lisp is a language of experts, which for our purposes means that Lisp is not a language designed for inexpert programmers to code robust reliable software. - ^
John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-10-25]. ISBN 0-262-13011-4. (原始內容 (PDF)存檔於2021-03-02).「
To define these functions, we use the pseudo-functiondefine
. …… A pseudo-function is a function that is executed for its effect on the system in core memory, as well as for its value.define
causes these functions to be defined and available within the system. Its value is a list of the functions defined ……. ……define[x]
:EXPR
pseudo-function
The argument ofdefine
,x
, is a list of pairs
((u1 v1) (u2 v2) … (un vn))
where eachu
is a name and eachv
is a λ-expression for a function. For each pair, define puts anEXPR
on the property list foru
pointing tov
. The function ofdefine
puts things on at the front of the property list. The value ofdefine
is the list ofu
's.
define[x] = deflist[x;EXPR]
deflist[x;ind]
:EXPR
pseudo-function
The functiondeflist
is a more general defining function. Its first argument is a list of pairs as fordefine
. Its second argument is the indicator that is to be used. Afterdeflist
has been executed with(ui vi)
among its first argument, the property list ofui
will begin:| .----.---. .---.---. .---.---. uᵢ `->| -1 | |->|IND| |->| | |--> - - - `----'---' `---'---' `---'---' | V vᵢ
If
deflist
ordefine
is used twice on the same object with the same indicator, the old value will be replaced by the new one.」 - ^ 30.0 30.1
Kent M. Pitman. The Revised Maclisp Manual. 1983, 2007 [2021-10-26]. (原始內容存檔於2022-03-28).
DEFUN
Special Form(DEFUN namespec . definitionspec)
DEFUN
offers a way of associating a functional definition with a symbol. ……DEFUN
can be used to define both normal functions and special forms (fexprs and macros). ……
;; Normal expr or lexpr function definitions
(DEFUN name bvl . body)
……
Ifname
is a symbol andbvl
is a list of symbols which is free of&
keywords (to be described below), the definition is an expr or lexpr definition. In Maclisp, this would be essentially equivalent to writing
(DEFPROP name (LAMBDA bvl . body) EXPR)
.
…… Note also that the keywordEXPR
is used for both expr and lexpr definitions. The only distinction between expr and lexpr definitions is whether thebvl
is a symbol or a list, but they are specified in the same way and looked up from the same property. ……
A fexpr is a function for which the formal parameters are not evaluated. The form of a fexpr definition is:
(DEFUN name FEXPR (sym) . body)
.
The lambda expression which describes a fexpr should expect to receive exactly one argument which will be the list of (unevaluated) arguments given in the call to the fexpr, so usually there is only one bound variable (sym
) in the bound variable list. ……DEFUN
can also be used to instantiate aMACRO
definition. …… The syntax for a macro definition is
(DEFUN name MACRO (sym) . body)
,
wheresym
will become bound to the whole macro form to be expanded (including the name). Note that this argument convention is different than fexprs, which only receive thecdr
of the call form. ……DEFUN
was introduced into Maclisp in March, 1969. Although now it is recognized as the standard function defining form because it shields the user from the implementational details of how the function is defined ……. ……DEFPROP
Function(DEFPROP sym val indicator)
Givessym
a property called indicator with valueval
. The arguments are not evaluated.DEFPROP
should not be used imbedded in other expressions. It is intended to occur at toplevel to assign properties that are set up once and never changed. In other places, usePUTPROP
with three quoted arguments. - ^
Gerald J. Sussman, Guy L. Steele Jr.. Scheme: An Interpreter for Extended Lambda Calculus. 維基文庫. 1975 (英文).
DEFINE
- This is analogous to the MacLISPDEFUN
primitive (but note that theLAMBDA
must appear explicitly!). It is used for defining a function in the "global environment" permanently, as opposed toLABELS
(see below), which is used for temporary definitions in a local environment.DEFINE
takes a name and a lambda expression; it closes the lambda expression in the global environment and stores the closure in the LISP value cell of the name (which is a LISP atom).
Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978 [2021-10-26]. (原始內容存檔於2022-04-06).Atoms which are not atomic symbols (identifiers) evaluate to themselves. Typical examples of such atoms are numbers, arrays, and strings (character arrays). Symbols are treated as identifiers or variables. They may be lexically bound by lambda-expressions. There is a global environment containing values initially have as their values primitive operations such as, for example,
CAR
,CONS
, andPLUS
. SCHEME differs from most LISP systems in that the atomCAR
is not itself an operation (in the sense of being an invocable object, e.g. a valid first argument toAPPLY
), but only has one as a value when considered as an identifier. - ^ Richard P. Gabriel; Kent M. Pitman. Technical Issues of Separation in Function Cells and Value Cells. Lisp and Symbolic Computation. June 1988, 1 (1): 81–101 [2021-11-01]. S2CID 26716515. doi:10.1007/bf01806178. (原始內容存檔於2006-11-13).
In 1981 the emerging Common Lisp community turned to Scheme for some of its motivation and inspiration [Steele 1984]. Adopting lexical scoping proved one of the most important decisions the Common Lisp group ever made.
One aspect of Scheme that was not adopted, however, was a single namespace for functions and values, along with uniform evaluation rules for expressions in function and argument positions within the language. ……
In this paper, we shall refer to two abstract dialects of Lisp called Lisp1 and Lisp2.
Lisp1 has a single namespace that serves a dual role as the function namespace and value namespace; that is, its function namespace and value namespace are not distinct. In Lisp1, the functional position of a form and the argument positions of forms are evaluated according to the same rules. Scheme [Rees 1986] and the language being designed by the EuLisp group [Padget 1986] are Lisp1 dialects.
Lisp2 has distinct function and value namespaces. In Lisp2, the rules for evaluation in the functional position of a form are distinct from those for evaluation in the argument positions of the form. Common Lisp is a Lisp2 dialect. ……
Most Lisp dialects adopted a two-namespace approach to the naming problem. To some extent this is because most dialects followed Lisp 1.5 [McCarthy 1965] or dialects derived from Lisp 1.5.
Lisp 1.5 broke symbols into values and functions; values were stored on an association list, and function on the property lists of symbols. Compiled and interpreted code worked in different ways. In the interpreter, the association list was where all bindings were kept. When an identifier was encountered (an 'atomic symbol' in Lisp 1.5 terminology), it was taken as a variable to be evaluated for its value. First theAPVAL
part of the symbol was interrogated — anAPVAL
was "A Permanent, system-defined VALue" stored in a specific place in the symbol. Second, the association list was searched. Finally, if no binding was found, an error was signaled.
When a combination was encountered, the function position was evaluated differently from other positions. First, the symbol was interrogated to see whether there was a function definition associated with it; then the association list was searched.
Here we can see two namespaces at work, though nonsymbol variables were treated somewhat uniformly (Lisp 1.5 did not have lexical variables in interpreted code): when there were no function definitions associated with a symbol, there was one namespace, which was explicitly represented by the association list.
Compiled code worked a slightly different way, and from its internals we can see where the two namespaces came about in descendants of Lisp 1.5.
The Lisp 1.5 compiler supported 'common' and 'special' variables. A common variable enabled compiled and interpreted code to communicate with each other. A common variable was bound on an explicit association list; to evaluate such a variable, a call toEVAL
was emitted to determine the value. A special variable was the compiler's modeling of free variables and closely matched what is now called 'shallow binding.' Ordinary variables compiled into what we have termed lexical variables.
Thus, we see all of the components of the two-namespace world in Lisp 1.5, along with some of the components of the one-namespace world.
It seems that the designers of Lisp 1.5 thought of function names as being different from variable names — the Lisp 1.5 interpreter looked at the property list of the named atomic symbol first, and so it can be argued that a function was considered a property of a symbol. The designers used the terminology that a symbol "stands for" a function while a variable "refers" to a value.
Lisp for the PDP-6 at MIT adopted the style of the Lisp 1.5 special variables for dynamic binding in both compiled and interpreted code, thereby eliminated common variables. Compilers were still written that were to try to interpret special variables as lexical variables in as many places as possible. The value of a symbol was stored in the value cell of the symbol, and the function remained on the property list as it did in Lisp 1.5.
MacLisp [Pitman 1983] is a direct descendant of the PDP-6 Lisp and is a Lisp2 dialect. MacLisp uses a sophisticated form of link table, which is made possible by the separation of namespaces. In particular, function-defining functions have controlled access into the places where functions are stored so that the link tables can be correctly maintained. ……
Common Lisp was the result of a compromise between a number of dialects of Lisp, most of them descendants of MacLisp, all of them Lisp2s. ……
A free variable in Common Lisp is currently taken to be a dynamic rather than a lexical reference because there is no global lexical environment in Common Lisp. In this code
(DEFUN PLUS (X Y) (+ X Y))
(DEFUN SOMEWHAT-MORE-THAN (X) (PLUS X *SOMEWHAT*))
The reference to*SOMEWHAT*
is special (dynamic). On the surface, in Lisp1 the reference toPLUS
is free also, and thus it is special (dynamic).
When a variable is declared special, a free reference to it is to the most recent dynamically bound value for it; all bindings of it become special (dynamic) bindings. When a variable is declared constant, free references to it are to its permanent constant value, and compilers are free to fold that constant into the code they emit.
We introduce the concept of global variables; when a variable is global, free references to it are to the value cell of the symbol named by the variable, and all bindings of it are still lexical.
To avoid a compiler warning for free use of a variable like*SOMEWHAT*
, the variable is declaredSPECIAL
. In order to have compilers for Lisp1 not to warn about the free use ofPLUS
, it would be unfortunate to have to declare itSPECIAL
.
As noted, in Common Lisp the default for free variable references isSPECIAL
; that is, a free variable reference is taken to be a special variable reference. If the default in Lisp1 were that free variable references were global (lexical), then it would make sense for a compiler not to warn about such free variable references. - ^
John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-10-25]. ISBN 0-262-13011-4. (原始內容 (PDF)存檔於2021-03-02).
The over-all design of the LISP Programming System is the work of John McCarthy and is based on his paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine" which was published in Communications of the ACM, April 1960.
This manual was written by Michael I. Levin.
The interpreter was programmed by Stephen B. Russell and Daniel J . Edwards.
The print and read programs were written by John McCarthy, Klim Maling, Daniel J. Edwards, and Paul W, Abrahams.
The garbage collector and arithmetic features Were written by Daniel J. Edwards.
The compiler and assembler were written by Timothy P. Hart and Michael I. Levin.
An earlier compiler was written by Robert Brayton.
The "LISP 1 Programmer's Manual," March 1, 1960, was written by Phyllis A. Fox. Additional programs and suggestions were contributed by the following members of the Artificial Intelligence Group of the Research Laboratory of Electronics: Marvin L. Minsky, Bertram Raphael, Louis Hodes, David M. R. Park, David C. Luckham, Daniel G. Bobrow, James R. Slagle, and Nathaniel Rochester. - ^ Lynn H. Quam. Stanford LISP 1.6 Manual (PDF). 1969 [2021-12-29]. (原始內容 (PDF)存檔於2022-03-03).
The STANFORD A.I. LISP 1.6 System was originally an adaptation of one developed by the Artificial Intelligence Project a t M.I.T. Since 1966, that system has been largely rewritten by John Allen and the author.
Guy L.Steele, Jr., Richard P. Gabriel. The evolution of Lisp. The second ACM SIGPLAN conference on History of programming languages. ACM: 231–270. 1993 [2022-11-19]. (原始內容存檔於2022-11-12).At Stanford in the 1960s, an early version of MacLisp was adapted for their PDP-6; this Lisp was called Lisp 1.6 [Quam 1972]. The early adaptation was rewritten by John Allen and Lynn Quam; later compiler improvements were made by Whit Diffie. Lisp 1.6 disappeared during the mid-1970s, one of the last remnants of the Lisp 1.5 era.
- ^ The original Edinburgh LCF. 1977 [2021-10-10]. (原始內容存檔於2021-10-10).
- ^ Maclisp Reference Manual. March 3, 1979 [2021-10-29]. (原始內容存檔於2022-03-28).
Guy L.Steele, Jr., Richard P. Gabriel. The evolution of Lisp. The second ACM SIGPLAN conference on History of programming languages. ACM: 231–270. 1993 [2022-11-19]. (原始內容存檔於2022-11-12).By 1964 a version of Lisp 1.5 was running in the Electrical Engineering Department at MIT on an IBM 7094 computer, running the Compatible Time Sharing System (CTSS). This Lisp and Basic PDP-1 Lisp were the main influences on the PDP-6 Lisp [PDP-6 Lisp 1967] implemented by DEC and some members of MIT's Tech Model Railroad Club in the spring of 1964. This Lisp was the first program written on the PDP-6. Also, this Lisp was the ancestor of MacLisp, the Lisp written to run under the Incompatible Timesharing System (ITS) [Eastlake 1968, 1972] at MIT on the PDP-6 and later on the PDP-10. ……
In 1965, virtually all of the Lisps in existence were identical or differed only in trivial ways. After 1965 - or more precisely, after MacLisp and BBN-Lisp diverged from each other - there came a plethora of Lisp dialects. ……
MacLisp was the primary Lisp dialect at the MIT AI Lab from the late 1960s until the early 1980s. Other important Lisp work at the Lab during this period included Lisp-Machine Lisp (later named Zetalisp) and Scheme. MacLisp is usually identified with the PDP-10 computer, but MacLisp also ran on another machine, the Honeywell 6180, under the Multics operating system [Organick 1972]. - ^ 37.0 37.1 37.2 37.3 John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-10-25]. ISBN 0-262-13011-4. (原始內容 (PDF)存檔於2021-03-02).
The Artificial Intelligence Project at Stanford University has produced a version of LISP 1.5 to be distributed by SHARE. In the middle of February 1965 the system is complete and is available from Stanford. The system should be available from SHARE by the end of March 1965. ……
Evalquote
is available to the programmer as a LISP function - thus, one may now write "(EVALQUOTE APPEND ((A)(B C D)))
", rather than "(EVAL (QUOTE (APPEND (A)(B C D))) NIL)
", should one desire to do so.
Guy L.Steele, Jr., Richard P. Gabriel. The evolution of Lisp. The second ACM SIGPLAN conference on History of programming languages. ACM: 231–270. 1993 [2022-11-19]. (原始內容存檔於2022-11-12).A key difference between MacLisp and Interlisp was the approach to syntax. MacLisp favored the pure list style, using
EVAL
as the top level. Interlisp, along with Lisp 1.5, usedEVALQUOTE
.
To concatenate the lists(BOAT AIRPLANE SKATEBOARD)
and(CAR TRUCK)
in MacLisp, one would type this expression toEVAL
:
(APPEND (QUOTE (BOAT AIRPLANE SKATEBOARD)) (QUOTE (CAR TRUCK)))
or, using the syntactic abbreviation'x
for(quote x)
,
(APPEND '(BOAT AIRPLANE SKATEBOARD) '(CAR TRUCK))
The result would of course be(BOAT AIRPLANE SKATEBOARD CAR TRUCK)
.
In Lisp 1.5, one would type an expression (actually two expressions) like this toEVALQUOTE
:
APPEND((BOAT AIRPLANE SKATEBOARD) (CAR TRUCK))
The first expression denotes a function, and the second is a list of arguments. The "quote" in the nameEVALQUOTE
signifies the "implicit quoting of the arguments" to the function applied. MacLisp forked off and usedEVAL
exclusively as a top level interface. BBN-Lisp (and thus Interlisp) accommodated both: if the first input line contained a complete form and at least one character of a second form, then BBN-Lisp finished reading the second form and used theEVALQUOTE
interface for that interaction; otherwise it read exactly one form and used theEVAL
interface for that interaction.
The phrase "quoting arguments" actually is misleading and imprecise. It refers to the actions of a hypothetical preprocessor that transforms the input from a form like
APPEND((BOAT AIRPLANE SKATEBOARD) (CAR TRUCK))
to one like
(APPEND (QUOTE (BOAT AIRPLANE SKATEBOARD)) (QUOTE (CAR TRUCK)))
before evaluation is performed. A similar confusion carried over into the description of the so-calledFEXPR
or"special form." In some texts on Lisp one will find descriptions of special forms that speak of a special form "quoting its arguments," when in fact a special form has a special rule for determining its meaning and that rule involves not evaluating some forms [Pitman 1980].
McCarthy [McCarthy 1981] noted that the original Lisp interpreter was regarded as a universal Turing machine: It could perform any computation given a set of instructions (a function) and the initial input on its tape (arguments). Thus it was intended that
APPEND((BOAT AIRPLANE SKATEBOARD) (CAR TRUCK))
be regarded not as a syntactically mutated version of
(APPEND (QUOTE (BOAT AIRPLANE SKATEBOARD)) (QUOTE (CAR TRUCK)))
but as a function and (separately) a literal list of arguments. In hindsight we see that theEVALQUOTE
top level might better have been called theAPPLY
top level, making it pleasantly symmetrical to theEVAL
top level; the BBN-Lisp documentation brought out this symmetry explicitly. Indeed,EVALQUOTE
would have been identical to the functionAPPLY
in Lisp 1.5 if not for these two differences: (a) in Lisp 1.5,APPLY
took a third argument, an environment (regarded nowadays as something of a mistake that resulted in dynamic binding rather than the lexical scoping needed for a faithful reflection of the lambda calculus); and (b) "EVALQUOTE
is capable of handling special forms as a sort of exception" [McCarthy 1962]. Nowadays such an exception is referred to as a kluge [Raymond 1991]. (Note, however, that MacLisp'sAPPLY
function supported this same kluge.) - ^ Teitelman, Warren. InterLisp Reference Manual (PDF). 1974 [2021-10-29]. (原始內容 (PDF)存檔於2022-03-03).
Guy L.Steele, Jr., Richard P. Gabriel. The evolution of Lisp. The second ACM SIGPLAN conference on History of programming languages. ACM: 231–270. 1993 [2022-11-19]. (原始內容存檔於2022-11-12).In 1963, L. Peter Deutsch (at that time a high school student) implemented a Lisp similar to Lisp 1.5 on the PDP-1 at Bolt Beranek and Newman (BBN) [Deutsch 1964]. This Lisp was called Basic PDP-1 Lisp. ……
At BBN, a successor to Basic PDP-1 Lisp was implemented on the PDP-1 and an upward-compatible version, patterned after Lisp 1.5 on the MIT CTSS system, was implemented on the Scientific Data Systems 940 (SDS 940) by Daniel Bobrow and D. L. Murphy. A further upward-compatible version was written for the PDP-10 by Alice Hartley and Murphy, and this Lisp was called BBN-Lisp [Teitelman 1971]. In 1973, not long after the time that SDS was acquired by Xerox and renamed Xerox Data Systems, the maintenance of BBN-Lisp was shared by BBN and Xerox Palo Alto Research Center and the name of the Lisp was changed to Interlisp [Teitelman 1974]. ……
Interlisp (and BBN-Lisp before it) introduced many radical ideas into Lisp programming style and methodology. The most visible of these ideas are embodied in programming tools, such as the spelling corrector, the file package, DWIM, CLISP, the structure editor, and MASTERSCOPE.
The origin of these ideas can be found in Warren Teitelman's Ph.D. dissertation on man-computer symbiosis [Teitelman 1966]. In particular, it contains the roots of structure editing (as opposed to "text" or "tape" editing [Rudloe 1962]), breakpointing, advice, and CLISP. ……
CLISP (Conversational LISP) was a mixed ALGOL-like and English-like syntax embedded within normal Interlisp syntax. Here is a valid definition ofFACTORIAL
written in lnterlisp CLISP syntax:
DEFINEQ((FACTORIAL
(LAMBDA (N) (IF N=0 THEN 1 ELSE N*(FACTORIAL N-I)))))
- ^ Package: lang/lisp/impl/xlisp/. cs.cmu.edu. [2021-10-26]. (原始內容存檔於2022-03-31).
- ^ Outils de generation d’interfaces : etat de l’art et classification by H. El Mrabet (PDF). [2021-10-24]. (原始內容 (PDF)存檔於2017-10-01).
- ^ Gerald J. Sussman, Guy L. Steele Jr. SCHEME: An Interpreter for Extended Lambda Calculus. 1975 [2021-10-27]. (原始內容存檔於2022-04-17).
Inspired by ACTORS [Greif and Hewitt][Smith and Hewitt], we have implemented an interpreter for a LISP-like language, SCHEME, based on the lambda calculus [Church], but extended for side effects, multiprocessing, and process synchronization. The purpose of this implementation is tutorial. We wish to:
⑴ alleviate the confusion caused by Micro-PLANNER, CONNIVER, etc. by clarifying the embedding of non-recursive control structures in a recursive host language like LISP.
⑵ explain how to use these control structures, independent of such issues as pattern matching and data base manipulation.
⑶ have a simple concrete experimental domain for certain issues of programming semantics and style. - ^ 42.0 42.1 Guy L. Steele, Jr., Scott Fahlman, Richard P. Gabriel, David A. Moon, Daniel Weinreb. Common Lisp the Language 1st edition. 1984. ISBN 0-932376-41-X.
- ^ Steele, Guy L., Jr. Purpose. Common Lisp the Language 2nd edition. 1990 [2021-10-24]. ISBN 0-13-152414-3. (原始內容存檔於2021-03-08).
- ^ Kantrowitz, Mark; Margolin, Barry. History: Where did Lisp come from?. FAQ: Lisp Frequently Asked Questions 2/7. 20 February 1996 [2021-10-24]. (原始內容存檔於2021-03-08).
- ^ ISO/IEC 13816:1997. Iso.org. 2007-10-01 [2013-11-15]. (原始內容存檔於2016-07-30).
- ^ ISO/IEC 13816:2007. Iso.org. 2013-10-30 [2013-11-15]. (原始內容存檔於2016-07-30).
- ^ 47.0 47.1 IEEE Scheme. IEEE 1178-1990 - IEEE Standard for the Scheme Programming Language. [27 August 2019]. (原始內容存檔於2021-03-04).
- ^ X3J13 Charter. [2021-10-24]. (原始內容存檔於2021-03-05).
- ^ The Road To Lisp Survey. [2006-10-13]. (原始內容存檔於2006-10-04).
- ^ Trends for the Future. Faqs.org. [2013-11-15]. (原始內容存檔於2013-06-03).
- ^ Common Lisp Implementations. [2022-11-13]. (原始內容存檔於2022-11-13).
- ^ The Revised5 Report on the Algorithmic Language Scheme. schemers.org. 1998 [2021-10-24]. (原始內容存檔於2007-01-05).
- ^ The Revised6 Report on the Algorithmic Language Scheme. 2007 [2021-11-04]. (原始內容存檔於2013-06-25).
- ^ R7RS-small language, final draft (PDF). [2022-09-06]. (原始內容存檔 (PDF)於2022-11-13).
- ^ Implementations support all or part of R7RS-small. [2022-11-13]. (原始內容存檔於2022-11-13).
- ^ Why MIT now uses python instead of scheme for its undergraduate CS program. cemerick.com. March 24, 2009 [November 10, 2013]. (原始內容存檔於September 17, 2010).
- ^ Broder, Evan. The End of an Era. mitadmissions.org. January 8, 2008 [November 10, 2013]. (原始內容存檔於2018-08-21).
- ^ Axel - Haskell + Lisp. [2022-11-22]. (原始內容存檔於2022-11-22).
- ^ Fennel is a programming language that brings together the speed, simplicity, and reach of Lua with the flexibility of a lisp syntax and macro system.. [2023-01-20]. (原始內容存檔於2021-07-27).
- ^ a specification for Bel (頁面存檔備份,存於網際網路檔案館), "a new dialect of Lisp."
- ^ Chapter 1.1.2, History, ANSI CL Standard
- ^ [1] (頁面存檔備份,存於網際網路檔案館) Clasp is a Common Lisp implementation that interoperates with C++ and uses LLVM for just-in-time compilation (JIT) to native code.
- ^ [2] (頁面存檔備份,存於網際網路檔案館) "Armed Bear Common Lisp (ABCL) is a full implementation of the Common Lisp language featuring both an interpreter and a compiler, running in the JVM"
- ^ [3] 網際網路檔案館的存檔,存檔日期2018-06-22. Common Lisp Implementations: A Survey
- ^ [4] (頁面存檔備份,存於網際網路檔案館) Comparison of actively developed Common Lisp implementations
- ^ Gerald J. Sussman, Guy L. Steele Jr. The First Report on Scheme Revisited. 1998 [2021-10-28]. (原始內容存檔於2022-04-06).
Sussman had just been studying Algol. He suggested starting with a lexically scoped dialect of Lisp, because that seemed necessary to model the way names could refer to acquaintances in PLASMA. Lexical scoping would allow actors and functions to be created by almost identical mechanisms. Evaluating a form beginning with the word
lambda
would capture the current variable-lookup environment and create a closure; evaluating a form beginning with the wordalpha
would also capture the current environment but create an actor. Message passing could be expressed syntactically in the same way as function invocation. The difference between an actor and a function would be detected in the part of the interpreter traditionally known asapply
. A function would return a value, but an actor would never return; instead, it would typically invoke a continuation, another actor that it knew about. Our interpreter also provided the necessary primitives for implementing the internal behavior of primitive actors, such as an addition operator that could accept two numbers and a continuation actor. ……
…… This led us to three important ideas:
• First, we realized that all the patterns of control structure that Hewitt had described in terms of actors could equally well be described by the λ-calculus. ……
• Second, we realized that the λ-calculus — a small, simple formalism — could serve as the core of a powerful and expressive programming language. (Lisp had adopted the λ-notation for functions but had failed to support the appropriate behavior for free variables. The original theoretical core of Lisp was recursion equations, not the λ-calculus.) ……
• Third, we realized that in our quest for the 「ultimate AI language」 we had come full circle. As the MIT school had struggled to find more and more powerful ways to express and manipulate control structure to support heuristic search, we had progressed from Lisp to CONVERT to Planner to Conniver to PLASMA to a simple variation of Lisp! - ^ An In-Depth Look at Clojure Collections (頁面存檔備份,存於網際網路檔案館), Retrieved 2012-06-24
- ^ Clojure rational. [27 August 2019]. (原始內容存檔於2016-01-04).
Clojure is a Lisp not constrained by backwards compatibility
- ^ Script-fu In GIMP 2.4 (頁面存檔備份,存於網際網路檔案館), Retrieved 2009-10-29
- ^ librep (頁面存檔備份,存於網際網路檔案館) at Sawfish Wikia, retrieved 2009-10-29
- ^ The Jargon File - Lisp. [2006-10-13]. (原始內容存檔於2021-04-18).
- ^ John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-10-25]. ISBN 0-262-13011-4. (原始內容 (PDF)存檔於2021-03-02).
Special Forms - Normally,
eval
evaluates the arguments of a function before applying the function itself. Thus ifeval
is given(CONS X Y)
, it will evaluateX
andY
, and thencons
them. But ifeval
is given(QUOTE X)
,X
should not be evaluated.QUOTE
is a special form that prevents its argument from being evaluated.
A special form differs from a function in two ways. Its arguments are not evaluated before the special form sees them.COND
, for example, has a very special way of evaluating its arguments by usingevcon
. The second way which special forms differ from functions is that they may have an indefinite number of arguments. Special forms have indicators on their property lists calledFEXPR
andFSUBR
for LISP-defined forms and machine language coded forms, respectively. - ^ Common Lisp the Language, 2nd Edition — 5. Program Structure — 5.2.2. Lambda-Expressions. [2024-01-14]. (原始內容存檔於2024-05-28).
- ^ 74.0 74.1 Guy L.Steele, Jr., Richard P. Gabriel. The evolution of Lisp. The second ACM SIGPLAN conference on History of programming languages. ACM: 231–270. 1993 [2022-11-19]. (原始內容存檔於2022-11-12).
The use of
SETF
throughout Common Lisp - a later dialect of Lisp and the most popular - can be traced through Symbolics Zetalisp and MacLisp to the influence of MIT Lisp-Machine Lisp and then back through Greenblatt's proposal to Peter Deutsch and thence to Alan Kay.
The uniform treatment of access - reading and writing of state - has made Common Lisp more uniform that it might otherwise be. It is no longer necessary to remember both a reader function (such asCAR
) and also a separate writer or update function (such asRPLACA
), nor to remember the order of arguments. (ForRPLACA
, which comes first, the dotted pair or the new value for its car?) If the general form of a read operation is(f…)
, then the form of the write is(setf (f…) newvalue)
, and that is all the programmer needs to know about reading and writing data. - ^ Guy L. Steele. Common Lisp the Language, 2nd Edition. 1990 [2022-12-16]. ISBN 1-55558-041-6. (原始內容存檔於2023-01-17).「
In describing various features of the Common Lisp language, the notions of scope and extent are frequently useful. These notions arise when some object or construct must be referred to from some distant part of a program. Scope refers to the spatial or textual region of the program within which references may occur. Extent refers to the interval of time during which references may occur. ……
There are a few kinds of scope and extent that are particularly useful in describing Common Lisp:
- Lexical scope. Here references to the established entity can occur only within certain program portions that are lexically (that is, textually) contained within the establishing construct. Typically the construct will have a part designated the body, and the scope of all entities established will be (or include) the body.
Example: the names of parameters to a function normally are lexically scoped. - Indefinite scope. References may occur anywhere, in any program.
- Dynamic extent. References may occur at any time in the interval between establishment of the entity and the explicit disestablishment of the entity. As a rule, the entity is disestablished when execution of the establishing construct completes or is otherwise terminated. Therefore entities with dynamic extent obey a stack-like discipline, paralleling the nested executions of their establishing constructs.
Example: thewith-open-file
construct opens a connection to a file and creates a stream object to represent the connection. The stream object has indefinite extent, but the connection to the open file has dynamic extent: when control exits thewith-open-file
construct, either normally or abnormally, the stream is automatically closed.
Example: the binding of a 「special」 variable has dynamic extent. - Indefinite extent. The entity continues to exist as long as the possibility of reference remains. (An implementation is free to destroy the entity if it can prove that reference to it is no longer possible. Garbage collection strategies implicitly employ such proofs.)
Example: most Common Lisp data objects have indefinite extent.
Example: the bindings of lexically scoped parameters of a function have indefinite extent. (By contrast, in Algol the bindings of lexically scoped parameters of a procedure have dynamic extent.) The function definition(defun compose (f g)
#'(lambda (x)
(funcall f (funcall g x))))
when given two arguments, immediately returns a function as its value. The parameter bindings forf
andg
do not disappear because the returned function, when called, could still refer to those bindings. Therefore(funcall (compose #'sqrt #'abs) -9.0)
produces the value3.0
. (An analogous procedure would not necessarily work correctly in typical Algol implementations or, for that matter, in most Lisp dialects.)
The term 「dynamic scope」 is a misnomer. Nevertheless it is both traditional and useful. 」 - Lexical scope. Here references to the established entity can occur only within certain program portions that are lexically (that is, textually) contained within the establishing construct. Typically the construct will have a part designated the body, and the scope of all entities established will be (or include) the body.
- ^
John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-10-25]. ISBN 0-262-13011-4. (原始內容 (PDF)存檔於2021-03-02).
The variables in a lambda expression are dummy or bound variables because systematically changing them does not alter the meaning of the expression. Thus
λ[[u;v];v2+u]
means the same thing asλ[[x;y];y2+x]
.
We shall sometimes use expressions in which a variable is not bound by a lambda. For example, in the function of two variablesλ[[x;y];xn+yn]
the variablen
is not bound. This is called a free variable. It may be regarded as a parameter. Unlessn
has been given a value before trying to compute with this function, the value of the function must be undefined. ……
When the compiler is called upon to compile a function, it looks for anEXPR
orFEXPR
on the property list of the function name. The compiler then translates this S-expression into an S-expression that represents a subroutine in the LISP Assembly Language (LAP). LAP then proceeds to assemble this program into binary program space. Thus anEXPR
, or anFEXPR
, has been changed to aSUBR
or anFSUBR
, respectively. ……
Free variables in compiled functions must be declared before the function is compiled. ……
A variable is bound in a particular function when it occurs in a list of bound variables following the wordLAMBDA
orPROG
. Any variable that is not bound is free. ……
When a variable is used free, it must have been bound by a higher level function. If a program is being run interpretively, and a free variable is used without having bee bound on a higher level, error diagnostic *A 8* will occur.
If the program is being run complied, the diagnostic may not occur, and the variable may have value NIL.
There are three types of variables in compiled functions: ordinary variables,SPECIAL
variables, andCOMMON
variables.SPECIAL
andCOMMON
variables must be declared before compiling. Any variable that is not declared will be considered an ordinary variable.
When functions are translated into subroutines, the concept of a variable is translated into a location where an argument is stored. If the variable is an ordinary one, then a storage location for it is set up on the push-down list. Other functions cannot find this private cell, making it impossible to use it as a free variable.SPECIAL
variables have the indicatorSPECIAL
on their property lists Following the indicator there is a pointer to a fixed cell. When this variable is bound, the old value is saved on the push-down list, and the current value is stored in theSPECLAL
cell. When it is no longer bound, the old value must be restored. When a function uses this variable free, then the quantity in theSPECIAL
cell is picked up.SPECIAL
variables are declared by using the pseudo-functionspecial[a]
, wherea
is a list of variable names. ……SPECIAL
variables are inexpensive and will allow free communication among compiled functions. They do not increase run time significantly.SPECIAL
variables cannot be communicated between the interpreter and compiled functions.COMMON
variables have the flagCOMMON
on their property lists; however, this is only used to inform the compiler that they areCOMMON
, and is not needed at run time.COMMON
variables are bound on an a-list by the compiled functions. When they are to be evaluated,eval
is given this a-list. This happens at run time.
The use ofCOMMON
variables will slow down any compiled function using them. However, they do provide complete communication between interpreted and compiled functions.COMMON
variables are declared bycommon[a]
, wherea
is a list of variable names. ……
LISP is designed in such a way that all functions for which the possibility of recursion can exist are in fact recursive. This requires that all temporary stored results related to the computation that is in progress be set aside when a piece of coding is to be used recursively, and that they be later restored. This is done automatically and need not be programmed explicitly.
All saving of temporary results in LISP is performed on a linear block of storage called the push-down list. Each set of stored data that is moved onto the push-down list is in a block labeled with its size and the name of the subroutine from which it came. Since it is in the nature of recursion that the first block to be saved is always the last block to be restored, it is possible to keep the push-down list compact.
Joel Moses. The Function of FUNCTION in LISP, or Why the FUNARG Problem Should Be Called the Environment Problem (pdf). June 1970 [2009-10-27]. AI Memo 199. (原始內容存檔於2010-05-23).There are several ways in which to maintain the values of free variables (and, thus the computational environment) in order to handle cases like the one above. All of the techniques used involve some increase in time. One approach makes it easy to access the value of a free variable is local. This approach is favored in recent implementations of LISP. We shall call it the "shallow access" approach.
Another approach is to make it relatively easy to enter and leave a block in which a free variable is bound, but relatively expensive to access a free variable. This approach is used in the classical "alist" implementation of LISP. Several Algol systems have opted for a similar approach. We shall call this the "deep access" approach. Both of these approaches allow one to modify the value of the variable as well as access it. The access time is approximately the same as modification time in both approaches.
Let us consider the "shallow access" approach first. By "shallow access" we mean that the value of a free variable can be obtained in a single fetch from memory. Since the current value may be stored in a difficult-to-determine location up in the stack, a special cell for its current value is used. In many recent LISP implementations this special values cell is stored as a property of the atom structure, and is unique to the free variable. In order to maintain the proper value in the special cell, extra work must be done every time a function or a block is entered in which the variable is an argument or is local. On entering such a function or block one usually saves the old value which is in the special cell on the stack alone with sufficient information to allow one to know from where the stack value came. On leaving such a function or block one must remember to store the value saved in the stack in the special cell.
The "deep access" approach forces one to search upward in the stack for the most recent value of the free variable. Such a search may be quite deep and slow if the free variable was bond vary far up in the stack. However, this approach has the advantage of avoiding the need for an extra special value cell. In addition, we shall see later that this approach sometimes allows one to use free variables with greater ease and flexibility than the "shallow access" approach. ……
Certain LISP systems use "deep access" in interpreted functions and "shallow access" in compiled functions. if free variables in compiled functions are declared to beCOMMON
, their values will be stored on the "alist". In this manner one can solve the environment problem. The cost is a very slow interpreter and "deep access" to free variables. - ^
Gerald J. Sussman, Guy L. Steele Jr.. Scheme: An Interpreter for Extended Lambda Calculus. 維基文庫. 1975 (英文).
There are several important consequences of closing every lambda expression in the environment from which it is passed (i.e., in its "lexical" or "static" environment).
First, the axioms of lambda calculus are automatically preserved. Thus, referential transparency is enforced. This in turn implies that there are no "fluid" variable bindings (as there are in standard stack implementations of LISP such as MacLISP).
Second, the upward funarg problem [Moses] requires that the environment structure be potentially tree-like.
Finally, the environment at any point in a computation can never be deeper than the lexical depth of the expression being evaluated at that time; i.e., the environment contains bindings only for variables bound in lambdas lexically surrounding the expression being evaluated. This is true even if recursive functions are involved. ……Furthermore, it is not even necessary to scan the environment for the variable, since its value must be in a known position relative to the top of the environment structure; this position can be computed by a compiler at compile time on the basis of lexical scope. - ^ Guy L. Steele. Common Lisp the Language, 2nd Edition. 1990 [2022-12-16]. ISBN 1-55558-041-6. (原始內容存檔於2022-08-15).
Symbols are used as names of variables in Common Lisp programs. When a symbol is evaluated as a form, the value of the variable it names is produced. For example, after doing (
setq items 3
), which assigns the value3
to the variable nameditems
, thenitems
⇒3
. Variables can be assigned to, as bysetq
, or bound, as bylet
. Any program construct that binds a variable effectively saves the old value of the variable and causes it to have a new value, and on exit from the construct the old value is reinstated.
There are actually two kinds of variables in Common Lisp, called lexical (or static) variables and special (or dynamic) variables. At any given time either or both kinds of variable with the same name may have a current value. Which of the two kinds of variable is referred to when a symbol is evaluated depends on the context of the evaluation. The general rule is that if the symbol occurs textually within a program construct that creates a binding for a variable of the same name, then the reference is to the variable specified by the binding; if no such program construct textually contains the reference, then it is taken to refer to the special variable of that name.
The distinction between the two kinds of variable is one of scope and extent. A lexically bound variable can be referred to only by forms occurring at any place textually within the program construct that binds the variable. A dynamically bound (special) variable can be referred to at any time from the time the binding is made until the time evaluation of the construct that binds the variable terminates. Therefore lexical binding of variables imposes a spatial limitation on occurrences of references (but no temporal limitation, for the binding continues to exist as long as the possibility of reference remains). Conversely, dynamic binding of variables imposes a temporal limitation on occurrences of references (but no spatial limitation). For more information on scope and extent, see chapter 3.
The value a special variable has when there are currently no bindings of that variable is called the global value of the (special) variable. A global value can be given to a variable only by assignment, because a value given by binding is by definition not global.
It is possible for a special variable to have no value at all, in which case it is said to be unbound. By default, every global variable is unbound unless and until explicitly assigned a value, except for those global variables defined in this book or by the implementation already to have values when the Lisp system is first started. It is also possible to establish a binding of a special variable and then cause that binding to be valueless by using the functionmakunbound
. In this situation the variable is also said to be 「unbound,」 although this is a misnomer; precisely speaking, it is bound but valueless. It is an error to refer to a variable that is unbound.
Macro DEFPARAMETER, DEFVAR. Common Lisp HyperSpec. [2022-12-14]. (原始內容存檔於2022-12-25).It is customary to name dynamic variables with an asterisk at the beginning and end of the name. e.g.,
*foo*
is a good name for a dynamic variable, but not for a lexical variable;foo
is a good name for a lexical variable, but not for a dynamic variable. This naming convention is observed for all defined names in Common Lisp; however, neither conforming programs nor conforming implementations are obliged to adhere to this convention. - ^
Alexander Burger. PicoLisp Frequently Asked Questions. [2021-10-29]. (原始內容存檔於2017-08-06).
Why do you use dynamic variable binding? Dynamic binding is very powerful, because there is only one single, dynamically changing environment active all the time. This makes it possible (e.g. for program snippets, interspersed with application data and/or passed over the network) to access the whole application context, freely, yet in a dynamically controlled manner. And (shallow) dynamic binding is the fastest method for a Lisp interpreter.
Lexical binding is more limited by definition, because each environment is deliberately restricted to the visible (textual) static scope within its establishing form. Therefore, most Lisps with lexical binding introduce "special variables" to support dynamic binding as well, and constructs like labels to extend the scope of variables beyond a single function.
In PicoLisp, function definitions are normal symbol values. They can be dynamically rebound like other variables. ……
Are there no problems caused by dynamic binding? You mean the funarg problem, or problems that arise when a variable might be bound to itself? For that reason we have a convention in PicoLisp to use transient symbols (instead of internal symbols) or private internal symbols ……
But with dynamic binding I cannot implement closures! This is not true. Closures are a matter of scope, not of binding.
For a closure it is necessary to build and maintain a separate environment. In a system with lexical bindings, this has to be done at each function call, and for compiled code it is the most efficient strategy anyway, because it is done once by the compiler, and can then be accessed as stack frames at runtime.
For an interpreter, however, this is quite an overhead. So it should not be done automatically at each and every function invocation, but only if needed. - ^
Lutz Mueller. Comparison to Common Lisp and Scheme. [2021-10-29]. (原始內容存檔於2022-04-06).
Dynamic scoping inside isolated namespaces - newLISP is sometimes criticized for using dynamic scoping and fexprs. …… In newLISP, all variables are dynamically scoped by default. However, by defining a function in its own context, static/lexical scoping can be achieved. In newLISP, several functions and data can share a namespace. By enclosing functions in their own namespace, a lexical closure- like mechanism is achieved. Common Lisp and Scheme are lexically scoped by default and use lambda expressions as the closure mechanism. Common Lisp also offers special variables for dynamic scoping.
The problems of free variables in dynamic scoping can be avoided. In the rare cases when free variables must be used, you can partition code into namespace modules for easier control over free variables. You can then exploit the advantages of dynamic scoping. With dynamic scoping inside lexically-closed namespaces, newLISP combines the best of both scoping worlds.
newLISP has no funarg problem because it follows a simple rule: variables always show the binding of their current environment. When expressions with local variables are entered, newLISP saves the current variable state on a stack and restores it on exit of that expression. In newLISP, not only are function parameters and variables declared with let expressions local, loop variables in all looping expressions are local too. - ^
Dynamic Binding Vs Lexical Binding. EmacsWiki. [2021-10-28]. (原始內容存檔於2022-05-09).
dynamic - All variable names and their values live in one global table. lexical - Each binding scope (function, let syntax, …) creates a new table of variable names and values, organised in a hierarchy called 「the environment」. ……
EmacsLisp as of 24.1 has both dynamic binding and lexical binding. Lexical binding must be enabled explicitly for a file or buffer. Individual variables can be'defvar'
ed to make them 「special」, like in CommonLisp. - ^ Sebesta, Robert W. "2.4 Functional Programming: LISP";"6.9 List Types";"15.4 The First Functional Programming Language: LISP". Concepts of Programming Languages 10th. Boston, MA, USA: Addison-Wesley. 2012: 47–52;281–284;677–680 [2021-10-23]. ISBN 978-0-13-139531-2. (原始內容 (print)存檔於2021-03-08) (英語).
- ^ Conses as Lists. Common Lisp HyperSpec. [2022-11-22]. (原始內容存檔於2022-11-22).
A list is a chain of conses in which the car of each cons is an element of the list, and the cdr of each cons is either the next link in the chain or a terminating atom.
A proper list is a list terminated by the empty list. The empty list is a proper list, but is not a cons.
An improper list is a list that is not a proper list; that is, it is a circular list or a dotted list.
A dotted list is a list that has a terminating atom that is not the empty list. A non-nil atom by itself is not considered to be a list of any kind---not even a dotted list.
A circular list is a chain of conses that has no termination because some cons in the chain is the cdr of a later cons. - ^ CSE 341: Scheme: Quote, Quasiquote, and Metaprogramming. Cs.washington.edu. 1999-02-22 [2013-11-15]. (原始內容存檔於2013-08-23).
- ^ Alan Bawden. Quasiquotation in Lisp. 1999 [2021-10-29]. (原始內容存檔於2021-10-29).
- ^ 3.2.2.3 Semantic Constraints (頁面存檔備份,存於網際網路檔案館) in Common Lisp HyperSpec (頁面存檔備份,存於網際網路檔案館)
- ^ 4.3. Control Abstraction (Recursion vs. Iteration) in Tutorial on Good Lisp Programming Style (頁面存檔備份,存於網際網路檔案館) by Kent Pitman and Peter Norvig, August, 1993.
- ^ Time of Evaluation - Common Lisp Extensions (頁面存檔備份,存於網際網路檔案館). Gnu.org. Retrieved on 2013-07-17.
- ^ Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978.
Magic forms are recognized by then presence of a "magic (reserved) word" in the
car
position of the form. All non-atomic forms which are not magic forms are considered to be combinations. The system has a small initial set of magic words; there is also a mechanism for creating new ones {Note FUNCALL is a Pain}.
A combination is considered to be a list of subforms. These subforms are all evaluated. The first value mub be a procedure; it is applied to the other values to get the value of the combination. There are four important points here:
(1) the procedure Position is always evaluated just like any other position. (This is why the primitive operators are the values of global identifiers.)
(2) the procedure is never "re-evaluated"; if the first subform fails to evaluate to a applicable procedure, it is an error. Thus, unlike most LISP systems, SCHEME always evaluates the first subform of a combination exactly once.
(3) the arguments are all completely evaluated before the procedure is applied; that is, SCHEME, like most LISP systems, is an applicative-order language. Many SCHEME programs exploit this fact.
(4) the argument forms (and procedure form) may in principle be evaluated in any order. This is unlike the usual LISP left-to-right order. (All SCHEME interpreters implemented so far have in fact performed left-to-right evaluation, but we do not wish programs to depend on this fact. Indeed, there are some reasons why a clever interpreter might want to evaluate them right-to-left, e.g. to get things on a stack in the correct order.) - ^ Paul Graham. What Made Lisp Different. May 2002 [2022-11-16]. (原始內容存檔於2023-01-17).
- ^ John McCarthy. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-10-25]. (原始內容存檔 (PDF)於2020-11-07).
I invented conditional expressions in connection with a set of chess legal move routines I wrote in FORTRAN for the IBM 704 at M.I.T. during 1957-58. ……
A paper defining conditional expressions and proposing their use in Algol was sent to the Communications of the ACM but was arbitrarily demoted to a letter to the editor, because it was very short. - ^ Alan Kay. The Early History of Smalltalk. 1993 [2022-11-20]. doi:10.1145/155360.155364. (原始內容存檔於2011-04-29).
The biggest hit for me while at SAIL in late '69 was to really understand LISP. Of course, every student knew about
car
,cdr
, andcons
, but Utah was impoverished in that no one there used LISP and hence, no one had penetrated the mysteries ofeval
andapply
. I could hardly believe how beautiful and wonderful the idea of LISP was [McCarthy 1960]. I say it this way because LISP had not only been around enough to get some honest barnacles, but worse, there wee deep flaws in its logical foundations. By this, I mean that the pure language was supposed to be based on functions, but its most important components — such as lambda expressions quotes, and conds – were not functions at all, and instead were called special forms. Landin and others had been able to get quotes and conds in terms of lambda by tricks that were variously clever and useful, but the flaw remained in the jewel. In the practical language things were better. There were not justEXPR
s (which evaluated their arguments), butFEXPR
s (which did not). My next questions was, why on earth call it a functional language? Why not just base everything onFEXPR
s and force evaluation on the receiving side when needed? I could never get a good answer, but the question was very helpful when it came time to invent Smalltalk, because this started a line of thought that said 「take the hardest and most profound thing you need to do, make it great, an then build every easier thing out of it」. That was the promise of LISP and the lure of lambda – needed was a better 「hardest and most profound」 thing. Objects should be it. ……
This Smalltalk language (today labeled -71) was very influenced by FLEX, PLANNER, LOGO, META II, and my own derivatives from them. ……
As I mentioned previously, it was annoying that the surface beauty of LISP was marred by some of its key parts having to be introduced as 「special forms」 rather than as its supposed universal building block of functions. ……
An elegant approach was suggested in a CMU thesis of Dave Fisher [Fisher 70] on the syntheses of control structures. ALGOL60 required a separate link for dynamic subroutine linking and for access to static global state. Fisher showed how a generalization of these links could be used to simulate a wide variety of control environments. One of the ways to solve the 「funarg problem」 of LISP is to associate the proper global state link with expressions and functions that are to be evaluated later so that the free variables referenced are the ones that were actually implied by the static form of the language. The notion of 「lazy evaluation」 is anticipated here as well. - ^ 3-lisp: an infinite tower of meta-circular interpreters. [2023-01-26]. (原始內容存檔於2023-01-26).
- ^ Alan Kay, Stefan Ram. Dr. Alan Kay on the Meaning of “Object-Oriented Programming”. 2003-07-23 [2022-11-16]. (原始內容存檔於2021-06-27).
My original experiments with this architecture were done using a model I adapted from van Wijngaarten's and Wirth's "Generalization of Algol" and Wirth's Euler. Both of these were rather LISP-like but with a more conventional readable syntax. I didn't understand the monster LISP idea of tangible metalanguage then, but got kind of close with ideas about extensible languages draw from various sources, including Irons' IMP.
The second phase of this was to finally understand LISP and then using this understanding to make much nicer and smaller and more powerful and more late bound understructures. Dave Fisher's thesis was done in "McCarthy" style and his ideas about extensible control structures were very helpful. ……
OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP. There are possibly other systems in which this is possible, but I'm not aware of them. - ^ Lieberman, Henry; Hewitt, Carl, A Real-Time Garbage Collector Based on the Lifetimes of Objects, Communications of the ACM, June 1983, 26 (6): 419–429 [2022-11-16], CiteSeerX 10.1.1.4.8633 , S2CID 14161480, doi:10.1145/358141.358147, hdl:1721.1/6335, (原始內容存檔於2011-05-25)
- ^ Edsger W. Dijkstra, The Humble Programmer (EWD 340), 1972 (ACM Turing Award lecture).
- ^ A Look at Clojure and the Lisp Resurgence. [2022-11-16]. (原始內容存檔於2021-03-08).
- ^ Paul Graham. The Roots of Lisp (PDF). 2002 [2021-10-28]. (原始內容 (PDF)存檔於2021-10-28).
- ^ Daniel G. Bobrow, Kenneth Kahn, Gregor Kiczales, Larry Masinter, Mark Stefik, Frank Zdybel. CommonLoops: Merging Lisp and Object-Oriented Programming. 1986 [2021-10-29]. (原始內容存檔於2022-04-06).
- ^ "A History and Description of CLOS", by Jim Veitch. Pages 107–158 of Handbook of Programming Languages, Volume IV: Functional and Logic Programming Languages, ed. Peter H. Salus. 1998 (1st edition), Macmillan Technical Publishing; ISBN 1-57870-011-6
延伸閱讀
編輯- 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.
外部連結
編輯- 歷史
- 圖書和教程
- 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 (頁面存檔備份,存於網際網路檔案館)