您的位置:首页 > 百科大全 |

LISP语言

为非数值符号运算而设计的表处理语言。LISP是英文LIST PROCESSING(表处理)的缩写。 LISP语言是1960年J.麦卡锡在递归函数论基础上首先设计出来的。LISP语言的形式化程度高,表达力强,适合于描述各种知识和编写问题求解的程序,因此一直是用来研究人工智能的一种基本语言。

数据结构

自然语言中词可以认为是能单独用来构成句子的最小单元,由词可以构成词组,由词组可以构成更复杂的词组或句子。LISP语言的“词”称为原子,如15(数值原子)、IFAC(非数值原子)。LISP语言的“词组”就是由一组原子构成的有一定形式的表,如(A-KIND-OF FEDERATION)。表和原子可以组成更复杂的表称为符号表达式(相当于复杂词组)如 (IFAC(A-KIND-OF FEDERATION))。

程序结构

符号表达式不但是LISP语言的数据结构形式而且也是它的程序结构形式,也就是说符号表达式可以代表一个语句,即一段程序。这种数据结构和程序结构在格式上的一致性是LISP语言的显著特点。从语义角度考虑:对符号表达式求值的函数称为EVAL。求值也可用简式表出,记为“符号表达式⇒值”。求值规则如下:

(1)数字、T(真)、NIL(假,空表)的值就是自身。

(2)如果符号表达式是表,且表的第一元素是函数,那么首先求出其他元素的值,然后对函数求值,如(PLUS(TIMES3 5)2)⇒17。

(3)对以保留词形式出现的函数,其值完全取决于保留词的意义。如 (SETQ X (PLUS 15 1))即对X赋予16的值(SETQ是对原子赋值的意思)。

(4)如果符号表达式是一原子,那么其值就是最近赋予的值。

符号表达式的基本操作

如果符号表达式是一个复杂的表,对其操作可归结为取、删、添、并、组合等。为了防止EVAL将所有表的第一元素都看成函数,引入符号“\”,表示对紧随“\”后的表或其他符号表达式不求值。也可用函数QUOTE来实现同样的目的。例如:

(CAR\(ABC))⇒A

CAR表示取表的首元素

(CDR\(ABC))⇒(BC)

CDR表示删去表的首元素

(CONS\A\(BC))⇒(ABC)

CONS表示在表中添入新的首元素

(APPEND\(AB)\(CD))⇒(ABCD)

APPEND表示将两表合并为一

(LIST\A\B\(CD))⇒A(AB(CD))

LIST表示将各元素列入表中作为简例,下面给出用LISP语言写的求表 L中各数之和的程序,例如L=(7,5,3,0),则SUM(和)之值为15。

PROG (SUM)

(SETQ SUMφ)

LOOP (COND ((NULL L)(RETURN SUM)))

(SETQ SUM (PLUS SUM (CAR L)))

(SETQ L (CDR L))

(GO LOOP)

这段程序的含义是:用PROG引入分程序,它的局部变元是SUM,赋予SUM的初值是零(φ),循环:条件是,如果L等于空表,则返回SUM的值,

否则

将SUM原来值与表L首元素值之和赋予SUM,

将表L删去首元素后的值赋予表L

继续循环

用户自定义函数

LISP语言的用户自定义函数常用LAMBDA表达式给出,其一般形式为(LAMBDA(atom 1,atom2,…,atom k)e),LAMBDA 之后是一形式参数表,e是有待求值表达式的LISP形式。函数调用时,对所有形式参数赋予实在参数的值,然后对函数体 e求值。函数定义的 LAMBDA记法是 J.麦卡锡根据 A.丘奇的 λ演算理论引入程序设计语言的。LAMBDA是希腊字母λ的英语拼音。这种记法有助于函数定义精确化,是LISP语言中定义非基本函数的普遍方法。例如用户可自行定义一新函数 EXCHANGE(交换):EXCHANGE=(LAMBDA(Y)(LIST(CADR Y)(CAR Y)))。这样(EXCHANGE\(AB))的值便是(BA),定义中CADR为先作CDR后作CAR两次函数运算的简写形式。因此,LISP程序的运行可归结为函数求值,LISP语言是一种函数型程序设计语言。这是70年代发展起来的新型程序设计语言。LISP语言的函数定义方式允许被定义函数间相互调用,也允许直接或间接地调用自身(称为递归)。下面是一个定义阶乘(!)函数的递归程序例子。FACTORIAL:(LAMBDA (N) (COND (EQUAL N 1)1)

(T (TIMES N

(FACTORIAL

(SUB1 N)))))

由于在函数体中出现被定义函数 FACTORIAL,所以这个定义是递归的。LISP语言兼有递归和迭代(见上例PROG)的功能,具有较强的表达力和较大的灵活性。LISP还可用于逻辑程序设计。用于逻辑程序设计的、扩展的LISP语言称为LOGLISP,它的功能与PROLOG等价。

LISP语言有很多变种,但最基本的是LISP1.5,比较著名的还有MACLISP,INTERLISP等。

参考书目
    Winston, Horn著,黄昌宁、陆玉昌译:《LISP程序设计》,清华大学出版社,北京,1983。(P.H.Winston and B.K.P.Horn, Lisp, Addison-Wesley Publ. Co., Reading, Mass.,1981.)