函数式语言基本知识

本文抄录自一本有关函数式语言的书，书名与作者暂不可考。文中介绍了一些函数式语言的基本知识，对于不了解函数式语言的读者有一定参考价值。

一些作者已经强调了面向对象程序设计和面向数值程序设计的区别。MacLenna(1982)指出，值（例如数字17）是应用式的和只读的，他们总是抽象的。对象（例如实例）在一定范围内存在，可以被创造、撤销、共享和更新。数值是引用透明的，引用它的一切事情将使用同样的数值。Smalltalk也因此受到一些批评，在Smalltalk中任何事物都是对象。无法实现一种正确的区分将导致几个危险。不清楚共享的数据结构是否可能被错误地更新，或者存在着一个以潜在的代价昂贵的复制开销。在给出了应用式程序设计或面向数值的程序设计的一切优点以后，为什么我们应该完全需要对象呢？

首先，如果我们所采用的数据结构对应于真实世界的话，那么计算机系统里现实世界模拟将会被大大简化。文件是对象，他们不能被代数描述。在普通程序设计语言中，变量是对象，他们的标识和区分是通过他们的位置，而无需考虑它们的当前值是什么。一个值属于一个类型，而一个对象属于一个类，本质的区别是：具有相同描述的两个对象可能并不相同，而相同的描述不可能是两个不同的值。例如，只可能有一个值等于17的整数，但蒙娜丽莎画像可以有两个完全一样的副本。反之则是不正确的，这可以通过下面的情况进行说明。考虑具有不同描述的两个对象（早晨的星星和晚上的星星），他们代表的是同一物理对象（金星）。许多语言都混淆了这个问题，例如，Pascal中的文件可能无法被赋予表达式或在表达式中使用，尽管他们的声明是通过和其他类型同样的方式。模拟系统的程序员必须处理“状态”和状态的变化，他们必须处理时间或（至少在人工智能里的）可能世界。应用式程序设计不是为此目的而设计的，而是为了处理不受时间影响的数学抽象。

那么，我们所需要做的就是清楚地区分值和对象以及支持这种区分并允许使用恰当模型（值或对象）的一种语言。

函数是程序设计是一种风格，包括建立在形式逻辑和数学基础上的语言，例如Lisp或ML。普通程序通过向变量赋值而发生作用，这些变量代表了内存中的存储位置。任何以前存储的值将会被重写并永久消失，除非事先采取了有关步骤。应用式程序语言（比如Lisp）不采用这种破坏的赋值过程。相对于命令式编程，应用式程序设计不允许赋值或侧放作用。在实际中，这意味着要节省存储空间，处理器必须周期性地执行一些无用存储单元收集以清除那些不再需要的值。另一个普遍的特征是“延迟计算”，通过这种方式，数值在函数用到之前是不被计算的。这种类型的语言建立在函数应用和组合的基础之上，他们依赖于以以“lambda演算”而闻名的逻辑系统，对lambda演算,我们将在下面进行说明。当应用式程序设计维持“参照透明性”的时候，这就是说每个表达式或变量在给定作用于范围内具有相同的值，所有变量都是局部的。那么在这种情况下，应用式程序设计也就变成了函数是程序设计。这暗示我们可以用一个相等值来替换一个表达式，而不会改变整个表达式的值。这个属性在定理证明和数据库查询中是很有用的，因为其中重写和替换是很基本的。虽然这种作用与规则很容易让人想起面向对象的语言，但函数式程序设计不允许对象具有状态。一种过程语言命令计算机如何执行一个特定的任务。一种非过程语言仅仅告诉计算机该做些什么，而不是怎么做。思考下列一个数据库查询，该查询询问每个部门各有多少个雇员以及总薪水和平均薪水是多少。

SELECT DNAME, JOB, SUM(SAL), COUNT(*), AVG(SAL)
FORM EMPLOYEE,DEPARTMENT
WHERE EMPLOYEE.DEPTNO=DEPARTMENT.DEPTNO
GROUP BY DNAME,JOB

实际上，这个查询产生正确输出，但结果是不必与我们相关的。上面所用的语言是SQL语言，注意他并没有告诉计算机如何回答这个问题。这涉及到获取雇员表单，按部门和工作进行排序，然后计算人数以及平均薪水和总薪水。最后，在输出结果中，部门编号必须被部门名称所代替。这本是一个相当复杂的过程，其中涉及到读纪录和保存每一阶段的中间结果。但这种建立在关系代数基础之上的非过程SQL是所有这些都是不必要的。在SQL
的执行过程中，存在着引入了一种过程性元素的内置函数。纯粹形性是一个非常珍贵的帮助。

术语“说明性”比“非过程”更通用一些，因为它包括了纯说明性语言。这个术语更多的是与数据表示方法有关，而于特定的程序设计风格并无太大关系。说明性语言的对立语言通常称为命令式语言，但这种用法在更时髦但不太悦耳的“非过程”的攻击下边的落伍。Prolog语言也是一种说明性的非过程风格（尽管一种修剪(！)操作的出现使他同样能够以一种不灵活的过程风格被使用）。现在，让我们转向使得这种语言成为可能的逻辑。

Prolog和SQL都是基于一阶谓词演算（这是数学逻辑的一种形式），SQL是建立在更小自己的基础之上，因此可表达性较差。这些语言金当他们的可表达性像Prolog一样时才通常被称为逻辑程序设计语言。函数式程序设计语言建立在另一种逻辑系统的基础（lambda演算）之上，通常认为它是逻辑程序设计语言，尽管它们深深根植于逻辑。

函数式程序语言有一些明显的好处，这些好处包括：

◆它们的形式化基础。

◆通过增加额外的可重用功能，他们很容易被扩展。

◆统一的程序设计隐喻，从而，每件事都是一个函数。

◆较高级的结构体（函数的函数）容易表达。

◆支持多态性类型（像ML一样）或完全风格的类型自由（像Lisp一样）。