1.2 程序设计语言族谱
(EXAMPLE 1.3 Classification of programming languages)现有的许多程序设计语言可以根据它们的计算模型进行分类。图1.1显示了一组常见的分类，这种分类区分了声明式语言和命令式语言，声明式语言的重点是计算机要做什么，命令式语言的重点是关于计算机应该如何做到这一点。
Figure 1.1 Classification of programming languages. Note that the categories are fuzzy, and open to debate. In particular, it is possible for a functional language to be object-oriented, and many authors do not consider functional programming to be declarative.
声明式语言在某种意义上是“更高层次的”；它们更符合程序员的思维方式，而不太符合实现者的思维方式，然而命令式语言占主导地位主要是出于性能原因。声明式语言的设计中存在着一种对立观点，一种是希望摆脱“不相关”的实现细节，另一种是需要与细节保持足够的接近，至少可以控制算法的大纲，毕竟高效算法的设计是计算机科学的重要内容。我们还不清楚编译器能够在多大程度上和在什么问题领域中能够为高抽象级别的问题发现好的算法。在编译器找不到好算法的领域中，需要程序员能够显式地指定一个算法。
在声明式和命令式语言家族中，有几个重要的子家族：
函数式语言采用基于函数递归定义的计算模型，这种思想来自lambda演算，这是Alonzo Church在20世纪30年代开发的一种正则计算模型。从本质上讲，程序被视为从输入到输出的函数，这个函数通过更简单的函数定义。这类语言包括Lisp、ML和Haskell。
数据流语言将计算建模为基本功能节点之间的信息流（token）。它们提供了一个内置的并行模型：节点由输入token触发，并且可以并发操作。Id和Val是数据流语言，Sisal由Val发展而来，但它通常被认为为一种函数式语言。
逻辑式或基于约束的语言来源于谓词逻辑。他们将计算建模为通过一系列的逻辑规则对目标进行搜索，以此试图找到满足特定关系的值。Prolog是最著名的逻辑语言。这类语言有时也包括SQL数据库语言、XSLT脚本语言以及可编程电子表格，例如Excel及其前身。
Von Neumann语言可能是使用最广泛的语言。它们包括Fortran、Ada、C以及所有以修改变量为基本计算手段的语言7。函数式语言基于具有值的表达式，而von Neumann语言则基于使用语句（特别是赋值语句）来修改内存中的值，以此对后续的计算产生影响。
面向对象语言可追溯到Simula 67。这些语言大多数都与von Neumann语言密切相关，但在内存和计算方面都有一个更加结构化和分布式的模型。面向对象语言将计算描述为半独立对象之间的交互，每个对象都有自己的内部状态和管理该状态的子例程，而不是将计算描述为处理器在内存上的操作。Smalltalk是最纯粹的面向对象语言，而C++和Java可能是使用最广泛的。也存在面向对象的函数式语言（其中最著名的是CLOS[Kee89]和OCaml），但它们往往具有很强的命令式风格。
脚本语言强调协调或将周围的环境“粘合在一起”。一些脚本语言最初是为特定目的开发的：csh和bash用于作业控制（shell）程序的输入语言；PHP和JavaScript主要用于生成动态web内容；Lua被广泛用于控制电脑游戏。其它语言，包括Perl、Python和Ruby，更倾向于通用性，很多时候强调快速原型设计，所以更倾向于易于表达而非执行速度。
有人可能会认为并发（并行）语言会形成一个单独的家族（本书有一章专门讨论此类语言），但并发和顺序执行之间的区别与上述分类无关。目前，大多数并发程序都是使用特殊的库或编译器以及Fortran或C等顺序执行的语言编写的。一些广泛使用的语言，包括Java、C#和Ada，都具有明确的并发功能。研究者正在调查这里提到的每个家族中的并发性。
以本章开头介绍的最大公约数（GCD）问题作为不同语言家族间对比的一个简单示例。对于这个问题，von Neumann、函数式或逻辑式语言不仅会影响代码的外观，也会影响程序员的思维方式。(EXAMPLE 1.4 GCD function in C)Von Neumann版本的算法如下：
To compute the gcd of a and b, check to see if a and b are equal. If so, print one of them and stop. Otherwise, replace the larger one by their difference and repeat.
算法的C语言表示如图1.2的上部分所示。
(EXAMPLE 1.5 GCD function in OCaml)在函数式语言中，强调的是输出与输入之间的数学关系：
The gcd of a and b is defined to be (1) a when a and b are equal, (2) the gcd of b and a - b when a > b, and (3) the gcd of a and b - a when b > a. To compute the gcd of a given pair of numbers, expand and simplify this definition until it terminates.
算法的OCaml版本显示如图1.2的中间部分所示。关键字let引入定义；rec表示允许递归（自引用）；函数的参数位于名称（在本例中为gcd）和等号之间。
(EXAMPLE 1.6 GCD rules in Prolog)在逻辑语言中，程序员通过定义一组公理和证明规则来让系统找到所需的值：
The proposition gcd(a, b, g) is true if (1) a, b, and g are all equal; (2) a is greater than b and there exists a number c such that c is a - b and gcd(c, b, g) is true; or (3) a is less than b and there exists a number c such that c is b - a and gcd(c, a, g) is true. To compute the gcd of a given pair of numbers, search for a number g (and various numbers c) for which these rules allow one to prove that gcd(a, b, g) is true.
算法的Prolog版本如图1.2的底部所示，需要将:-理解为if、将,理解为and。
应该强调的是，语言家族之间的区别并不明确。例如，von Neumann和面向对象语言之间的划分通常非常模糊，许多脚本语言也是面向对象的。大多数函数式语言和逻辑式语言都包含一些命令式功能，最近的一些命令式语言也添加了函数式功能。上述描述旨在描述语言家族的一般风格，而不提供正式定义。
本书更多关注命令式语言，包括von Neumann语言和面向对象语言。然而，许多问题跨越了语言家族界限，感兴趣的读者将在本书的大多数章节中发现许多适用于替代计算模型的问题。第11章到第14章包含关于函数式、逻辑式、并发和脚本语言的其他材料。
int gcd(int a, int b) { // C
while (a != b) {
if (a > b) a = a - b;
else b = b - a;
}
return a;
}
let rec gcd a b = (* OCaml *)
if a = b then a
else if a > b then gcd b (a - b)
else gcd a (b - a)
gcd(A,B,G) :- A = B, G = A. % Prolog
gcd(A,B,G) :- A > B, C is A-B, gcd(C,B,G).
gcd(A,B,G) :- B > A, C is B-A, gcd(C,A,G).
图1.2 The GCD algorithm in C (top), OCaml (middle), and Prolog (bottom). All three versions assume (without checking) that their inputs are positive integers.
7. John von Neumann（1903-1957）是数学家和计算机科学家，他提出和开发了存储程序的概念，这也是大多数计算机的基础。在存储程序计算机中，程序和数据都表示为内存中的位，处理器反复的执行取指、译码和更新操作。 ↩