歷史背景
20世紀50年代中期,在大多數計算機處理的都是數值數據等,包括語言學、心理學和數學領域上一些人們開始對人工智慧產生了興趣。覺得必須實現共同需要的一個方法,使計算機能夠處理鍊表中的符號數據,允許語言的處理、信息存入和檢索、定理證明的過程機器化。IBM是首先對人工智慧開發有興趣的商業機構之一。
1958年夏天,來自麻省理工學院的人工智慧研究先驅約翰·麥卡錫(John McCarthy)參與IBM資訊研究部的工作,研究符號運算及套用需求。可是,IBM旗下的Fortran表處理語言卻未能支援符號運算的遞歸、條件表達式、動態存儲分配及隱式回收等功能。John McCarthy於1958年秋季回到麻省理工學院後,和Marvin Minsky組成了人工智慧項目。開展一個表處理軟體系統來實現McCarthy提出建議採納者程式的工作,爾後推動了表處理語言LISP的產生。
發展歷程
1960年4月,McCarthy以《遞迴函式的符號表達式以及由機器運算的方式,第一部》為題,於ACM通訊上發表LISP設定。McCarthy的學生Steve Russell根據該論文,以IBM 704於麻省理工學院的計算機運算文中心成功執行了第一版的LISP。
1962年,McCarthy及人工智慧小組按LISP 1的編譯基礎上改良出LISP 1.5版本。
1969年9月,史丹福大學人工智慧實驗室的Lynn Quam與Whitfield Diffie推出的Stanford LISP 1.6廣泛地套用於使用TOPS-10系統的PDP-10計算機系中。Stanford LISP 1.6版本自麻省理工智慧型項目更新LISP 1.5成MACLISP及BBN科技公司推出的InterLisp成功後,漸被棄置。
自1960代末年至1980年初年,各種更新LISP版本湧現,有源自加大伯克來分校的Franz Lisp、在AutoCAD運行的AutoLISP前身XLISP、猶他大學開展的Standard Lisp及Portable Standard Lisp、專屬於Lisp機器上運行的ZetaLisp、源自法國國家信息與自動化研究所的LeLisp、以及MIT人工智慧實驗室的Gerald Sussman與Guy Steele所開發的Scheme等。
1984年,改良自MacLisp、集各版本大成、跨平台、且被目為事實標準的Common Lisp誕生。至1994年,美國國家標準學會(ANSI)對Common Lisp語言進行了標準化。
自穩定運行的Common Lisp出現起,再有各機構按各自所需而開展後續Lisp,包括1990年來自歐洲用戶的EuLisp及自由開源的IsLisp,ACL2等。
數據結構
在LISP語言中,數據和函式都是採用符號表達式定義的,這種符號表達式稱為S一表達式,它是原予和表的總稱。原子分為符號原予和數原子。符號原子是指有限個大寫字母和數字組成的字元串,其中第一個符號必須是字母。原子NIL和T分別表示邏輯假(或空表)和邏輯真。數原子是指一串數字,通過符號表示其正負。
特點
(1)函式性
函式型語言的基本特點是用函式定義和函式調用構成程式。程式設計師用函式定義和函式調用組成的表達式來描述求解問題的算法,表達式的值就是問題的解。用FORTRAN、PAS—CAL和C等傳統程式設計語言編寫的程式是按一定順序執行的命令序列,執行結果就是問題的解。用這些語言編程時,程式設計師要規定求解的順序,即要描述控制流。用LISP語言編程只需要確定函式之間的調用,把函式執行的細節交給LISP系統來解決。因此,LISP語言是更加面向用戶的語言。
傳統的程式設計語言是適應馮·諾依曼型計算機系統結構而發展起來的,LISP在諾依曼型計算機上運行的效率要低一些。計算機系統結構的發展,使得函式型語言有著廣闊的前途。為了適應當前微型機發展水平和程式設計師使用傳統語言編程的習慣,LISP語言增加了許多非函式型的語言成分,例如,prog、go等函式,所以,LISP已不是純函式型語言,它既具有函式語言的功能,又具有傳統語言的功能。
(2)遞歸性
遞歸函式是指在函式的定義中調用了這個函式本身。所有的可計算函式已被證明都可以用遞歸函式的形式來定義。
由於LISP的主要數據結構是表,而且表是用遞歸方法定義的,即表中的一個元素也可以定義為一個表,因此,程式設計師用LISP提供的自定義函式來定義用戶自己的函式時,可以用遞歸函式的形式來定義自己的函式。自定義的遞歸函式能夠很方便地對遞歸定義的表進行操作。遞歸定義的方法使程式簡明、優美,程式設計師應充分利用遞歸程式設計方法。
(3)數據與程式的一致性
LISP的一段程式是用戶的一個自定義函式,這個函式可被其他函式調用,或者說,一段程式可被其他程式調用。函式執行後的輸出數據稱為這個函式的返回值。一個函式被其他函式調用,就是調用了這個函式的返回值。在LISP中,函式與這個函式的返回值是一致的。這一特點使得LISP的編程就是定義一個宏函式,也使得LISP語言的擴充比較容易。可以根據套用領域的需要,使用LISP提供的基本函式擴充若干面向專門套用領域的宏函式。
(4)自動進行存儲分配
用LISP語言編程時,程式設計師完全可以不考慮存儲分配問題。程式中定義的函式、數據和表等都能在程式運行時,由LISP自動提供。對不再需要的數據,LISP自動釋放其占用的存儲區。
(5)語法簡單
LISP的語法極其簡單,對變數和數據不需要事先定義和說明類型。LISP語言的基本語法就是函式定義和函式調用。因此,LISP語言的程式便於修改、調試和糾錯,可以邊實驗邊設計,通過不斷修改和增加用戶自定義函式來構成複雜的系統。
LISP語言不僅在專家系統和CAD領域有廣泛的套用,在符號代數、定理證明、機器人規劃等領域也有廣泛的套用。影響LISP語言使用的主要原因有:一是LISP是非可視化語言;二是LISP在通用計算機上的運行效率較低;三是LISP的數值計算能力較差;四是人們對函式型語言的編程風格不習慣。
常見版本
LISP語言版本很多,常用的有:
(1)MACLISP語言:1971年由MIT人工智慧實驗室研製,它比較注重效率、地址空間的保護和構造工具的靈活性。
(2)INTERLISP語言:1978年由DEC和XEROX公司開發,它強調即使在速度和存貯空間方面有所損失,也要儘可能地提供最好的程式環境。
(3)ZETALISP語言;在LISP機上實現。它和MACLISP關係密切,有很好的兼容性。並且對MACLISP進行了很多改進,提供了新的性能。
(4)QLISP語言:它嵌在INTERLISP中,能靈活處理大型資料庫,具有返回追蹤與模式調用功能。
(5)CommonLISP語言:它是在MACLISP的基礎上發展起來的,並參考了INTERLISP和ZETALISP,因而功能較強且擁有其它版本的一些優點,目前已被廣泛使用。
(6)GCLISP語言:它作為CommonLISP在PC機上實現的第一個縮本,自然具有ConlmonLISP的通用性特點,其程式電容易移植到其它版本的LISP環境之中。GCLISP和CommonLISP核心部分兼容,與ZETALISP的某些概念吻合,此外還擁有若干先進的數據類型,它著眼於讓機器有較強的處理能力和記憶功能,因而效率較高,用戶易於掌握,使用比較廣泛。