Coding Poet, Coding Science

本章单独作为一章，而且并不是用作附录。因为人工智能与程序语言是一体的。每一种语言实际上都可以看成是智能的一部分。而我们的目的是设计出更智能的语言或者程序。为此当然需要了解可计算性理论以及计算复杂性理论。

发现一个优点，就是如果在学习人工智能的时候学习几门语言，要比自己在没有任何指导的情况下看语言入门的书要容易得多。如果直接学习Prolog,我想我会找不到里面的重点。但是在知识表示中顺便介绍了Prolog,我就觉得用它来写程序很自然。

本书第十三章先是一般地介绍了语言的分类，然后介绍了LISP, Scheme, Prolog, POP-11, 以及略微谈及了脚本语言。也许结合七周七语言，让自己对于语言的理解的高度再上一层吧。至少我觉得本章第一节讲语言分类的时候，像是在高屋建翎。由于人工智能本身就说自己写的程序很可能只能在特定情况下被使用，所以人工智能的算法库也不多。这反映了人工智能问题的复杂性，需要使用不同的语言来解决。于是在人工智能领域，我们也更倾向于使用设计得更好的语言，如是不能描述我们的问题，与其使用不合适的语言编程，还不如写一种合乎于我们要求的语言。

这里所介绍的AI语言，现在看来其实是一些通用的AI语言，也就是使用普遍的编程语言来心量实现AI一样的任务。这种方法对于理解一般编程语言是怎样实现智能的也有一定的好处。但是个人并不认为因此这些语言就是智能的了。所以我们在这里我可以看成是以AI应用为背景的对于编程语言的一个综合介绍吧。

Prolog程序设计

前面我们已经讲过了Prolog在知识表示与推理中的基本运用。现在我们考虑的是作为一门编程语言的Prolog.

一个事实是，Prolog解释程序很容易用Prolog语言本身实现(有点像GCC编译器自己编译出来自己，而LISP语言可以轻易地写出LISP编译器一样)。Prolog语言很适合于开发基于知识的系统，以及计算机代数系统。它的问题求解的能力依然是解决知识领域问题的一种重要语言。

越来越发现，编程的时候我们只有一个工具而不去借鉴别人的东西。这是不符合学习的一般规律的。应该减少盲目的摸索，把编程看成是知识传承与改进的领域。这样才会把自己的能力提得很高，而且掌握那些不会过时的部分。Prolog语言用于CAS的实例现在我们根本没有看到，而我现在对此有兴趣，那么该怎么办呢? 当然应先参考别人怎样尝试解决问题的，利用了语言的哪些机制，而不是觉得自己现在就可以做出来成果。

前面我们讲Prolog用于知识表示的时候，并没有讲到它的数据表示。实际上，以大写字母开头的单词代表变元外，还有数值类型与原子类型(相当于常量)，一个以单引号括起来的字符串也代表一个原子。而需要注意的是，现在Prolog的数值是整数类型。

除了基本元素还有列表与元组，可以嵌套，而且列表上有合一规则。

除了这些结构外，Prolog也提供了一组常用的外理数据的谓词。比如append()，length()，member()，列表操纵等。在Prolog语言中，

length([a,b,c], Length)

用于把Length的值赋成列表\([a,b,c]\)的长度，而

length([a,b,c],3)

用于判断列表的长度是否为3.也就是说，在Prolog中，函数值的接收与对值的判断是同样的一个形式。

事实与规则在Prolog知识库中出现。而在推理的过程中实现求值。这些功能在前面我们已经用过了。

最后，在推理的过程中，可以使用trace.跟踪计算的过程。

在Prolog中，把一个表达式赋给一个变量，可以使用

X is 3+3 **2.

这样的形式。注意使用的是is运算符。

Prolog中，可以使用小数，这个时候，小数视为常项。

人工智能语言概述

首先，人工智能算法可以由众多语言实现，但是有些语言更适合于特定的问题。对于神经网络或者遗传算法之类的数字人工智能问题，用C这样的语言是很高效的。对于依赖逻辑谓词的关系问题，Prolog较为理想。从历史上看，LISP是人工智能的基本语言。

程序设计语言的本质都是使程序员利用一台计算机解决问题，但是如何解决问题则可以千变万化。每种编程语言提供相同的功能，但是以不同的方式实现。(我们一般只考虑图灵完备的语言。)

主要的语言类型，或者说它们的特性，有函数式，命令式，面向对象，逻辑，并发这五个衡量的方面。之所以是这五个方面，因为它们大致决定了一门编程语言的基本面貌。用这几个标准可以更直观有效地对语言进行分类。在基本分类的基础上，我们再考虑求值方式，类型系统，性能与效率等因素。

人工智能早期，系统开发的重点是LISP这样的符号语言，以及Prolog这样的逻辑语言。但是实际上许多语言都能用于人工智能的开发。但是有几种范式对于语言的选择比较有影响。

那些LISP过时论的持见者，如果不能看到它现在的应用规模，它用于解决怎样的问题，那么它就没有资格起到决定作用。如果它没有掌握到语言发展的规律，我们就说那个人的话没有话语权。

函数式程序设计

第一种范式是函数式程序设计。这类语言深植于\(\lambda\)-演算的理论框架，具有诸如高阶函数，一等函数，递归，副作用少，连续，以及闭包等诸多特征。

与命令式语言相比，函数式程序设计依赖的是数据上函数的实施，而不是依赖于改变存储器和状态的命令的顺序执行。

高阶函数是函数式程序设计的基本特性，它意味着可以将一个函数作为输入，也可以返回一个函数作为输出。这个概念在数学上较为常见，比如求导函数。比如在Python中，可以使用map把一个函数作为参数作用于列表中的每个元素，甚至C语言也支持传递函数的入口指针。

但是C与Python其中的区别是，在函数式程序设计中，函数是作为一等对象或者一等函数。在一等函数里，我们可以把函数简单地当成数据。一等函数是有值的，就像其它任何数据结构一样。一等函数的一个重要表现是动态函数，也就是在运行期建立。C语言并不支持动态函数。

现代语言都力求支持多编程范式，因此对它们的分类也就越来越困难了。

下面是Ruby中一等函数的例子:

def mul_by(factor)
return Proc.new(|n| n*factor)
end
mul_by_2 = mul_by(2)
mul_by_2.call(8)

其中mul_by()函数接受factor参数，返回相应的乘积函数，然后用mul_by_2作为一个函数对象，使用它的call方法计算函数值。

函数式语言中，通常支持函数调用自身。它是函数式语言中典型的实现循环的方法。比如在LISP中的使用递归计算阶乘:

(defun fact (n) 
(if (= n 1) 1 (* n factor(n-1))))

LISP的特殊性不只是它采用函数式设计，而也是因为它的运算表达式都是前缀形式的表达式。以前以为理解LISP代码与写LISP代码都很难，但是现在觉得括号也没有引起想象中的太大的混淆。

闭包是函数式程序设计中与一等函数相关的一个很有用的特性。被传递到不同的词汇上下文使用的动态函数(有时是匿名的)被称为闭包。在计算机科学中，闭包（Closure）是词法闭包（Lexical Closure）的简称，是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在，即使已经离开了创造它的环境也不例外。所以，有另一种说法认为闭包是由函数和与其相关的引用环境组合而成的实体。

闭包的特殊性在于它引入了已有函数中的变量，当我们返回一个内部的函数的时候，虽然外函数结束，但是我们不能释放掉此函数里面的参数(因为它被闭包函数使用)，所以需要编程语言进行额外的处理才能支持闭包。

命式式程序设计

命令式程序设计把计算过程看成是改变程序状态的语句的顺序执行。最早的命令式语言是1954年开发的FORTRAN语言。FORTRAN语言位于一棵庞大的语言树的根部，BASIC,Pascal,Modula,C,Ada以及Python与Ruby这样的语言都可以看成是从它而来的。

汇编语言与机器语言也可以看成是命令式语言。而机器语言指令不仅改变存储器的状态，也改变机器的状态。

命令式语言通过循环提供迭代的能力。有时候它们也提供递归，但是它们的递归显然没有函数式语言高效。

面向对象程序设计

面向对象的语言的基本特征是类，对象，继承，封装与多态。类是定义了行为和属性的抽象实体，对象是类的实例化。继承是一个类继承其它类的特征的能力。这样，我们就能够创建定义默认行为的基类，然后建立修正这些行为的子类。封装指的是类可以陷藏它内部操作的细节。多态指的是基类的行为方法被父类的行为方法取代。

逻辑程序设计

逻辑程序设计于1958年由John McCarthy首次提出(!)。它基于规则的模式导向进行，以达到某个目标。虽然逻辑程序设计基于数理逻辑，但是它在数理逻辑能力上有很多的限制，特别地，逻辑程序设计可以实现熟知的Horn子句。Prolog,G"odel,Oz,Mercury都是支持逻辑程序设计的语言。

人工智能语言选择参考

在人工智能整个领域，单种语言通常不能提供必须的特性。在专家系统中，POP-11,Prolog与LISP这样的语言较常见，动态应用程序上LISP,Scheme,Dylan较常见，而计算机视觉几乎总是C/CXX.自然语言系统可以选用Prolog或者Oz,而演化系统常用C与DSL.

LISP语言

LISP是与FORTRAN,COBOL一样古老的早期语言之一。同时它也是最独特的语言之一。其数据与LISP程序都是以表的形式表示。程序与数据以相同的方式表示。

John McCarthy(现供职于Stanford)于1958年在MIT提出了LISP语言的基本思想。1960年公开发表了设计LISP语言的文章，不久之后语言被实现。McCarthy的符号系统使用一种方括号内的M表达式，但是这种符号系统在早期实现时即被S表达式取代。虽然LISP本身被认为是一种过时的语言，但是它仍然拥有许多重要的思想理念，因而值得学习研究。

在LISP中，一切事物都是表。表可以是空表，包含空表的表，包含单个原子的表，包含多个原子的表，包含表的表，以及作为结构的表(混合表)。

LISP表达式采取表的方式表示，是采用前缀表示法。每一个LISP表达式都会返回一个值，而且事实上，一个LISP函数可以返回任意个值。

LISP中还有提供判断的谓词，比如atom用于返回它的参数是否是一个原子，返回true或者false.

LISP的赋值也有多种方法，常见的是采用setq方法。用于将一个值赋给一个符号，或者将一系列的值赋值给一系列的符号。比如:

(setq score-1 95 score-2 100)
(setq thedate '("April" 13 1968))

其中在表开头前使用单引号，表示不要对此表进行求值后再赋值。LISP语言的另一种赋值方法是let.

LISP的表处理是其核心的机制。前面已经说过用setq建立一个表(是建立一个表的同时对变量赋值)。

函数cons用于通过两个参数构千定个表，也就是把第一个参数作为第二个参数(表)的第一个元素。比如(cons 1 ())返回(1)，而(cons 1 cons(2 ()))返回(1,2)。

对构造表的一种更简便的方法是list.它表里面所有的参数合并成一个表。如(list 1 2 3)将返回(1,2,3)，而(list 1 '(2,3))将返回(1 (2 3))。

需要注意的一个原则是，如果没有加上单引号，那么LISP就会对表进行求值，也就是把表视为一个函数。所以(2 3)在LISP中被求值，函数名为2,而3作为参数，甚至("Apple" 18)这样的形式，如果不加单引号的话，也会把"Apple"当成一个函数来求值。

LISP提供了一些基本的表处理函数，如car用于得到表的第一个元素，cdr用于得到表的除了第一个元素外的表。使用append可以把两个表连接起来。

注意LISP可以对任何表求值，只要在解析的时候没有加上单引号。

将一个程序作为数据的方法是setq,比如(setq expr ‘(\* 5 5))，表示把expr赋成表'(\* 5 5)(未求值)。然后调用(eval expr)来计算expr的值(25)。

使用print方法输出(此时函数返回被输出的值)，使用if作为条件判断。cond则相当于其它语言里面的case语句。

(setq name "Elise.")
(setq greet
(cond
    ((equal name "Marc")   "Hi,Marc.")
    ((equal name "Megan")  "Hi,Megan.")
    ((equal name "Elise")  "Hi,Elise.")
    ((equal name "Jill")   "Hi,Jill.")
    (t "Hi you.")))
(print greet)

这里，当name等于各个不同值的时候，把greet设置成不同的值。然后使用greet显示出来。最后的t代表true 的意思，相当于case的默认部分。

LISP每个求值都有返回，返回的都是一个表。

在LISP中，使用defun宏建立函数。格式是:

(defun func-name (parameter*)
"Optional string to describe function"
(body-form))

在LISP中，各个不同的词法成分完全通过空白字符以及括号分隔，名称都是可以任意取的。

这里只略微讲它的基本特性。作为编程语言的一面，可以参考LISP的有关书籍。

一个编译器很简单的语言一般都是好的语言，可以供程序员自由地开发。

Scheme语言

Scheme是20世纪70年代在MIT创建的，是LISP语言的一种新的变体并支持诸如命令式与面向对象等多种程序设计范式而设计的，不仅仅是一种函数式语言。

Scheme是Gerald Jay Sussman和Guy Steele, Jr.的一系列论文的综合成果。这些论文着重研究程序语言的设计思想，特别是一种既高效又不受任意规则约束的简单语言的设计。这些论文演化出的语方包括这门语言的体系结构，若干操作原语和以库的形式实现的其它成分。

看来我也对设计语言很着迷。但是不应该纯粹只是一种兴趣，还要使这种语言具有优良的性能。需要了解程序设计语言的本质，才能设计出来不致使自己都厌烦的语言。

程序的本质是什么? 上面说的，体系结构，操作原语与函数库，我觉得是一个语言的核心。我曾意识到，许多语言到最后都变成像汇编那样的长串的操作，比如像TeX那样只由一些内置宏组成，像m4那样的内置宏。但是就是不知道叫什么名子。现在知道，一个程序的功能，或者说代码的语义，所代表的操作，很大程度上决定于原语。

Scheme语言确实很简单，因为全部语言描述大约50页，另有100页的关于库的讨论。同样地，Scheme也有多种实现。

Scheme与LISP一样，都是易于学习，难于掌握的。但是像这样的语言，如果我们最点接触，那么慢慢地有了经验，就会比后来再集中学习好得多。

Scheme作为LISP的一种方方，数据与程序的表示都是相同的。在数据表示上，除了支持原有的表类型外，还支持整数，实数，字符串，符号以及其它一些类型，相当于说扩展了能够识别的类型。Scheme的数学表达式与LISP是相同的。Scheme会将数学符号识别成表示数学运算符的原语，并且使用所谓的前缀表示法。

极端地，在m4语言当中，任何记号都被当成字符处理，这种类型系统就很单调。而Scheme内置了针对实数加法的运算符，我们就称它的类型系统中有实数。也就是说，一门语言的类型系统指的是它内置了那些不同的操作，这些操作又作用在哪些词法单位上。

在Scheme中的谓词有null表示判断表是地为空表，如果用于判断，这些谓词后面都紧跟一个?号。返回的值为\#t或者\#f。如果期望检查内存中的两个对象是否相同，可以使用等价运算符eq?。

在Scheme当中，全局变量使用define赋值，如(define pi 3.1415926)，而局部变量使用(let (var-list) (exr))的形式来表示。比如(let ((pi 3.14159256) (r 5)) (\* pi (\* r r)))表示在计算表达式(\* pi (\* r r))的时候，用3.1415926代表pi,用5代表r.

在Scheme当中，构造表同样可以采取cons与list过程。表示对未被求值的表进行合并，结果是一个不被求值的表，比如(list \a’(b c))返回值是’(a (b c))`。

Scheme基本的表的操作过程与LISP语言相同，也是car与cdr过程。与LISP相同，Scheme也提供了合并算子，比如cadr代表先car,再cdr,cdar代表先cdr再car.除此之外，也可以使用list-ref提取它的第N个元素，比如(list-ref '(a b c d) 2)代表提取它的第三个对象'c(因为编号从零开始)。

而length()返回表的长度。

Scheme支持if与cond这样的表达式。除了以递归实现循环与迭代外，Scheme还提供了类似于do那样的循环与迭代。除此之外，还提供了map函数，用于将一个函数作用于列表中的每一个对象，如:(mapa (lambda (x) (\* x x)) '(0 1 2 3))。Scheme提供两种类型的函数，原语和过程，原语可以理解为内置过程。在语法上，使用(define (proc arg1 arg2) (body-list))来定义函数，与LISP原版稍微不同。

可以使用write或者display函数进行输入与输出。

POP-11语言

POP-11是一种著名的多范式语言，具有函数式语言的许多特性。POP-11因为具有垃圾收集器而被划为函数式语言，但是它像许多命令式语言一样具有块结构语法。POP-11还是面向堆栈的，在语言设计方面具有第四代语言相对独特的功能。

基于堆栈的另一个语言只能想到PostScript了。

POP-11是爱丁堡大学在人工智能研究中进行POP系列语言开发的产物，于20世纪70年代中期在PDP~11/40计算机UNIX操作系统上实现。POP-11在语言设计方面已达到最先进的水平，它不但有函数式功能，还具有面向对象性能与一个图形库。POP-11是一个专为教学而设计的语言，虽然它功能很强大，但是却没有广泛用于软件产品的开发。

POP-11的有益之处是，它在单种语言中支持命令式程序设计，逻辑程序设计以及函数式程序设计，这通常被视为是艰巨的任务，而POP-11却能很好地完成。

在互联网上，这样的语言的资料还真不好完成。至少中文的维基百科上面就缺少这些资料。只能从英文网页寻找。而且关于POP-11的资料实在是太少了。几乎只能上英文官网上面查找。安装过程也比较奇怪。而且现在还不能编译出来带图形界面的版本。最后，能用就行了，安装完成后，输入poplog pop11就可以进入交互式环境了。POP-11的后缀名也是.p,不过为了避免重复，还是使用p11作为后缀吧。不幸的是，listings宏包还没有POP-11的语法高亮。不过现在POPLOG是一个SOURCEFOGRE上的项目，名为OpenPoplog,希望它可以让POP-11发展壮大吧。

POP-11的一个比较全面的描述是支持多种范式的程序设计，对每种范式都有相应的概念。但是在这里显然只能讨论有助于说明语言的基本特性的那些机制。

数据表示(类型系统): POP-11包括多种数据对象，从数值(整数与小数)，到字，串，表以及向量。其中的表可以是复合的，可以包含其它的对象或者表。向量数据类型包括一组标准操作的类，用户可以进一步创建自己的向量类。字是用双引号括起来的，不知道它与串有什么区别。串是用单引号括起来的，它与其它语言中的字符串有更大的相似性。

当然了，在POP-11中，用方括号表示表，用大括号表示向量。

谓词: 对于给定的一个对象，POP-11提供了dataword()函数用于识别其数据类型。如果在一行语句后面添加上=>;，作用是告知解释器输出表达式的结果。如dataword(5) =>;。(这里光说不能讲明白，找一个POPLOG程序试一下就知道了。)

下面是POPLOG的一个交互式输入示例:

15:48 kael~$ poplog pop11
Poplog Version 15.6.4
setting poplib
poplib set to /usr/local/poplog/current-poplog/Poplib

Sussex Poplog (Version 15.64 Mon Oct 24 00:15:10 BST 2011)
Copyright (c) 1982-2009 University of Sussex. All rights reserved.

Setpop
: dataword("zoe")=>
** word 
: dataword(5)=>
** integer 
:

抄终端代码实在是太难看了，要多难看有多难看。

表达式:由于POP-11是一种多范式的语言，我们可以使用多种方式定义表达式并求出其值，像5+7=>;，*(3,4) 这样的形式都是允许的。前缀表示与后缀表示都是可以的。通过两种方式，POP-11同时支持命令式编程与函数式编程。

变量:在POP-11中使用关键字 vars 声明变量，可以用它一次建立多个变量，如matlab中那样。变量之间用逗号分开，语句结束用分号分开。(用分号结尾的句子可以抑制向终端输出，Sage也有这样的功能)。变量的类型是动态确定的，它可以被赋予任意的值，比如 [a b c] -> x (使用 -> 作为赋值运算符(因为 = 代表的是相等测试(逻辑或算术相等)))。

同样地，POP-11提供了表处理功能。对于一个表，可以使用 <> 连接两个表，合并成新的表，并赋给新的变量。(使用pr(var)的方法在终端输出一个变量的值)。除此之外，还可以使用 [x ^^list1 y ^^list2 z] 这样的表达式，来重新组成一个表，其中运算符 ^^ 表示将表的元素提出来，各并到新表中。

POP-11的表处理，还有hd()，tl()，length()函数，分别相当于Scheme的car,cdr与length.

条件语句

~ POP-11的条件语句采用命令式块结构模型。形如if-then-endif这样的形式，因而不再使用括号块。类似的命令式结构，还有until-do, do-until, repeat, while-do与for等等。不过尽管POP-11支持许多迭代方法，但是事实上，有些仅仅是语法糖(那些语言的附加成份，但是不不扩展该语言的表达能力的语句)。

POP-11支持maplist()作为其它语言中的map过程。用于将函数应用到一个表。而在POP-11中，过程的定义与块结构语言一样，使用define-endfine的结构，不过POP-11的函数定义是很广的，可以向过程传递多个结果，也可以返回多个结果(就和Python的语法一样)。

模式匹配:POP-11提供一组完美的模式匹匹功能，用于逻辑程序设计或者自然程序设计过程。POP-11的匹配是通过matches关键字实现的。比如:

[ [tim 41] [jill 35] [megan 15] ] => mylist;
vars age;
mylist matches [ == [jill ?age] == ] =>

其中matches匹配的是列表中的每一个元素。如果有等于jill的项，那么返回真值，并且将age变量的值赋给符合要求的匹配(使用?代表我们的意愿)。

其中的==用于表示模式在列表中出现的位置不限。这种模式匹配对于开发自然语言系统来说特别有用，如著名的Eliza程序。比如:

[I hate you] -> inp_sentence;
if inp_sentence matches [I ?verb you == ] then
[why do you ^verb me] =>
endif;

它表示在遇到指定的模式的时候，把中间的verb提取出来，然后返回输出。

也告诉我们，匹配的时候用问号，而引用变量的匹配的时候用^号。

POP-11内置的输出语句是printf,它的参数的类型是一个串(不是字)。

对POP-11的学习就先到这里吧。实际上，如果要达到可以自由试验的地步，应该知道怎样使用程序的交互式控制台，怎样从命令行运行一个源文件，怎样编译出来结果，以及怎样编译成库。这样才算是比较完美。

非标准分析简介

.NET平台上的一些程序语言

asp.net使用说明

密码学原理与开源工具(日期未定)

加密及密码体制原理介绍

从磁盘启动的过程与SYSLINUX

磁盘启动原理

人工智能语言介绍