LISP简介

陆建木
2023-12-01

LISP(全名LISt Processor,就是链表处理语言),由约翰·麦卡锡在1960年左右创造的一种基于λ演算的函数式编程语言。

LISP有很多种方言,各个实现中的语言不完全一样,Guy L. Steele编写了Common Lisp the Language试图进行标准化,这个标准被大多数解释器和编译器所接受。在Unix/Linux系统中,还有一种和Emacs一起的Emacs Lisp(而Emacs正是用Lisp编写的)非常流行,并建立了自己的标准。

LISP的祖先是20世纪50年代Carnegie-Mellon大学的Newell、Shaw、Simon开发的IPL语言。

LISP语言的主要现代版本包括Common Lisp和Scheme。

LISP的特点和数据结构  

1.LISP语言具有下列特点:
  (1)主要数据结构是表(符号表达式),而不是作为算术运算对象的数。
  (2)特性表简单,便于进行表处理。
  (3)最主要的控制结构为递归,适于过程描述和问题求解。
  (4)LISP程序内外一致,全部数据均以表形式表示。
  (5)能够产生更复杂的函数和解释程序。
  (6)对大多数事物的约束发生在尽可能晚的时刻。
  (7)数据和过程都可以表示成表使得程序可能构成一个过程并执行这个过程。
  (8)大多数LISP系统可以交互方式运行,便于开发各类程序,包括交互程序。

2.数据结构
  在基本LISP中,仅有一种数据类型,即表结构。大多数LISP程序设计中,数据是以表或者原子为专门形式。
  原子:原子是LISP中最小的符号单位。原子有标识符,诸如I AM A STUDENT,3,XYZ,或者NIL等。它们没有组合部分,各种性质或属性可附加到单个原子上。
  一个原子最重要的属性除其名字外是值,这与变量有值同义。一些原子有标准值:原子NIL的值是NIL,T的值是T。任何数字原子,其相应的整数或浮点数是它的值。这里要注意,原子不是"类型",任何原子,除常数外,可以给予任意值。
  表:一个表递归地定义为括号内零个或n个元素的序列:
(元素1 … 元素n)
其中每一个元素是一个原子或是一个表。零或者空表写成(),或者NIL。NIL既是原子又是表。表的固有递归结构非常灵活,便于表示各种信号。
  例如:
  (4 6 7 9 14 17 20 24 76)一组数
  ((-B)+(SQRT((B*B)-(4*A*C))))代数表达式
  (I(know((that(gasoline can))explode)))语法分析句子
  (YELLOW TABLE)断言
  (AND(ON A B)(ON A C)(NOT(TOUCH B C)))合取子句
  表的数据结构:LISP表的内部表示是由称为CONS单元的基元构成。每个CONS单元是一个地址,它包括一对指针,每个指针指到一个原子,或者指到另一个CONS单元。
  LISP的表结构可以用来使任何数据结构模型化。例如,二维数组可以表示为由许多行组成的一张表,每行又是一张元素表。当然,对于许多目的,这种数组的实现是相当低效的。
  控制结构:LISP是函数式程序语言,LISP的控制结构主要是应用函数指导控制流,其中变元又可以是应用函数。这点与大多数程序设计语言的顺序控制结构不同,在那里分离的句子是一句接一句地执行。在LISP中,语句与表达式没有区别,过程与函数也没有区别。每个函数,不管是否是一个语言原语,或是由用户定义的,都以指向一个表结构的形式返回一个单值。
  
3.变量约束及其辖域
  在LISP中有3种主要的赋予符号含义的方法。这里我们将介绍其中最常用的2种:把变量约束到值上和建立函数。
  变量约束到值上:变量本身并无什么含义,它只是一个符号。通过这个符号可以"达到"这个值。变量本身只不过是具有当前值的原子名称而已。当把此名称输入到LISP去时,LISP通过告诉原子的当前值,作为回答。这个名称与原子当前具有的值之间的联系称为约束,例如可把x约束到5。每当您在程序中引用x时,LISP都理解为5。以后您可以重新把x约束到pen,这就破坏了原来的联系而代之以x和pen之间的联系,在这以后,当引用x时,LISP把它理解为pen。x值还可能是一般复杂数据。可以自由地用任意数据段约束任何一个任意选择的符号。在最简单的情况下,变量就是某个对象的名字,变量的值就是对象本身。因此,我们可以发明一些名词写入到程序中去,并对这些名词赋予含义。我们还可以改变这些含义。
  建立函数:我们希望能够建立函数,以对名词进行运算,产生新的名词。建立函数的方法与用值约束符号的方法相同。不过,这时的值不是事实,而是要做的事情。在完成这些之后,再把符号正确地输入到LISP中去,LISP不象以前那样理解对象,而是把对象理解为需要完成的某件事。当把有关的符号约束到"含义"上时,就规定了这件事。
  辖域:如前所述,当一个值约束一个变量时,约束一直有效,直到使用者改变它为止。当约束来自最高层即来自键盘时,这总是对的。来自函数内部所建立的约束可以是永久性的,但当函数完成时,这些约束往往就消失,变量的名字将成为无约束的。如果在整个程序执行过程中始终保持变量的约束,那么变量被认为是全程变量。如果变量的约束是建立在单个函数的内部,而且当函数约束时,约束就消失,那么这是该函数的局部变量。当然,这二者之间有各种状态:你可能希望在程序的某一点被赋值的变量在执行若干个子程序的过程中保持它的值,然后再失掉这些值。
  值得指出,如果局部变量已能解决问题,就不需要建立全程变量。不然的话,就会浪费计算机内存。

 
 类似资料: