算法表达中的抽象机制(一）
简介
要用计算机解决一个稍为复杂的实际问题，大体都要经历如下的步骤。
将实际问题数学化，即把实际问题抽象为一个带有一般性的数学问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的已知条件、所要求的结果、以及在已知条件和所要求的结果之间存在着的隐式或显式的联系。 对于确定的数学问题，设计其求解的方法，即所谓的算法设计。这一步要建立问题的求解模型，即确定问题的数据模型并在此模型上定义一组运算，然后借助于对这组运算的调用和控制，从已知数据出发导向所要求的结果，形成算法并用自然语言来表述。这种语言还不是程序设计语言，不能被计算机所接受。 用计算机上的一种程序设计语言来表达已设计好的算法。换句话说，将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。这一步叫程序设计或程序编制。 在计算机上编辑、调试和测试编制好的程序，直到输出所要求的结果。
在这里，我们只关心第3步，而且把注意力集中在算法程序表达的抽象机制上，目的是引人一个重要的概念--抽象数据类型，同时为大型程序设计提供一种相应的自顶向下逐步求精、模块化的具体方法，即运用抽象数据类型来描述程序的方法。
从机器语言到高级语言的抽象
我们知道，算法被定义为一个运算序列。这个运算序列中的所有运算定义在一类特定的数据模型上，并以解决一类特定问题为目标。这个运算序列应该具备下列四个特征。
有限性，即序列的项数有限，且每一运算项都可在有限的时间内完成; 确定性，即序列的每一项运算都有明确的定义，无二义性; 可以没有输入运算项，但一定要有输出运算项; 可行性，即对于任意给定的合法的输入都能得到相应的正确的输出。
这些特征可以用来判别一个确定的运算序列是否称得上是一个算法。
但是，我们现在的问题不是要判别一个确定的运算序列是否称得上是一个算法，而是要对一个己经称得上是算法的运算序列，回顾我们曾经如何用程序设计语言去表达它。
算法的程序表达，归根到底是算法要素的程序表达，因为一旦算法的每一项要素都用程序清楚地表达，整个算法的程序表达也就不成问题。
作为运算序列的算法，有三个要素。
作为运算序列中各种运算的运算对象和运算结果的数据; 运算序列中的各种运算; 运算序列中的控制转移。
这三种要素依序分别简称为数据、运算和控制。
由于算法层出不穷，变化万千，其中的运算所作用的对象数据和所得到的结果数据名目繁多，不胜枚举。最简单最基本的有布尔值数据、字符数据、整数和实数数据等;稍复杂的有向量、矩阵、记录等数据;更复杂的有集合、树和图，还有声音、图形、图像等数据。
同样由于算法层出不穷，变化万千，其中运算的种类五花八门、多姿多彩。最基本最初等的有赋值运算、算术运算、逻辑运算和关系运算等;稍复杂的有算术表达式和逻辑表达式等;更复杂的有函数值计算、向量运算、矩阵运算、集合运算，以及表、栈、队列、树和图上的运算等:此外，还可能有以上列举的运算的复合和嵌套。
关于控制转移，相对单纯。在串行计算中，它只有顺序、分支、循环、递归和无条件转移等几种。
我们来回顾一下，自从计算机问世以来，算法的上述三要素的程序表达，经历过一个怎样的过程。
最早的程序设计语言是机器语言，即具体的计算机上的一个指令集。当时，要在计算机上运行的所有算法都必须直接用机器语言来表达，计算机才能接受。算法的运算序列包括运算对象和运算结果都必须转换为指令序列。其中的每一条指令都以编码(指令码和地址码)的形式出现。与算法语言表达的算法，相差十万八千里。对于没受过程序设计专门训练的人来说，一份程序恰似一份"天书"，让人看了不知所云，可读性极差。
用机器语言表达算法的运算、数据和控制十分繁杂琐碎，因为机器语言所提供的指令太初等、原始。机器语言只接受算术运算、按位逻辑运算和数的大小比较运算等。对于稍复杂的运算，都必须一一分解，直到到达最初等的运算才能用相应的指令替代之。机器语言能直接表达的数据只有最原始的位、字节、和字三种。算法中即使是最简单的数据如布尔值、字符、整数、和实数，也必须一一地映射到位、字节和字中，还得一一分配它们的存储单元。对于算法中有结构的数据的表达则要麻烦得多。机器语言所提供的控制转移指令也只有无条件转移、条件转移、进入子程序和从子程序返回等最基本的几种。用它们来构造循环、形成分支、调用函数和过程得事先做许多的准备，还得靠许多的技巧。
直接用机器语言表达算法有许多缺点。
大量繁杂琐碎的细节牵制着程序员，使他们不可能有更多的时间和精力去从事创造性的劳动，执行对他们来说更为重要的任务。如确保程序的正确性、高效性。 程序员既要驾驭程序设计的全局又要深入每一个局部直到实现的细节，即使智力超群的程序员也常常会顾此失彼，屡出差错，因而所编出的程序可靠性差，且开发周期长。 由于用机器语言进行程序设计的思维和表达方式与人们的习惯大相径庭，只有经过较长时间职业训练的程序员才能胜任，使得程序设计曲高和寡。 因为它的书面形式全是"密"码，所以可读性差，不便于交流与合作。 因为它严重地依赖于具体的计算机，所以可移植性差，重用性差。
这些弊端造成当时的计算机应用未能迅速得到推广。
克服上述缺点的出路在于程序设计语言的抽象，让它尽可能地接近于算法语言。
为此，人们首先注意到的是可读性和可移植性，因为它们相对地容易通过抽象而得到改善。于是，很快就出现汇编语言。这种语言对机器语言的抽象，首先表现在将机器语言的每一条指令符号化:指令码代之以记忆符号，地址码代之以符号地址，使得其含义显现在符号上而不再隐藏在编码中，可让人望"文"生义。其次表现在这种语言摆脱了具体计算机的限制，可在不同指令集的计算机上运行，只要该计算机配上汇编语言的一个汇编程序。这无疑是机器语言朝算法语言靠拢迈出的一步。但是，它离算法语言还太远，以致程序员还不能从分解算法的数据、运算和控制到汇编才能直接表达的指令等繁杂琐碎的事务中解脱出来。
到了50年代中期，出现程序设计的高级语言如Fortran，Algol60，以及后来的PL/l，Pascal等，算法的程序表达才产生一次大的飞跃。
诚然，算法最终要表达为具体计算机上的机器语言才能在该计算机上运行，得到所需要的结果。但汇编语言的实践启发人们，表达成机器语言不必一步到位，可以分两步走或者可以筑桥过河。即先表达成一种中介语言，然后转成机器语言。汇编语言作为一种中介语言，并没有获得很大成功，原因是它离算法语言还太远。这便指引人们去设计一种尽量接近算法语言的规范语言，即所谓的高级语言，让程序员可以用它方便地表达算法，然后借助于规范的高级语言到规范的机器语言的"翻译"，最终将算法表达为机器语言。而且，由于高级语言和机器语言都具有规范性，这里的"翻译"完全可以机械化地由计算机来完成，就像汇编语言被翻译成机器语言一样，只要计算机配上一个编译程序。
上述两步，前一步由程序员去完成，后一步可以由编译程序去完成。在规定清楚它们各自该做什么之后，这两步是完全独立的。它们各自该如何做互不相干。前一步要做的只是用高级语言正确地表达给定的算法，产生一个高级语言程序;后一步要做的只是将第一步得到的高级语言程序翻译成机器语言程序。至于程序员如何用高级语言表达算法和编译程序如何将高级语言表达的算法翻译成机器语言表达的算法，显然毫不相干。
处理从算法语言最终表达成机器语言这一复杂过程的上述思想方法就是一种抽象。汇编语言和高级语言的出现都是这种抽象的范例。
与汇编语言相比，高级语言的巨大成功在于它在数据、运算和控制三方面的表达中引入许多接近算法语言的概念和工具，大大地提高抽象地表达算法的能力。
在运算方面，高级语言如Pascal，除允许原封不动地运用算法语言的四则运算、逻辑运算、关系运算、算术表达式、逻辑表达式外，还引入强有力的函数与过程的工具，并让用户自定义。这一工具的重要性不仅在于它精简了重复的程序文本段，而且在于它反映出程序的两级抽象。在函数与过程调用级，人们只关心它能做什么，不必关心它如何做。只是到函数与过程的定义时，人们才给出如何做的细节。用过高级语言的读者都知道，一旦函数与过程的名称、参数和功能被规定清楚，那么，在程序中调用它们便与在程序的头部说明它们完全分开。你可以修改甚至更换函数体与过程体，而不影响它们的被调用。如果把函数与过程名看成是运算名，把参数看成是运算的对象或运算的结果，那么，函数与过程的调用和初等运算的引用没有两样。利用函数和过程以及它们的复合或嵌套可以很自然地表达算法语言中任何复杂的运算。
在数据方面，高级语言如Pascal引人了数据类型的概念，即把所有的数据加以分类。每一个数据(包括表达式)或每一个数据变量都属于其中确定的一类。称这一类数据为一个数据类型。 因此，数据类型是数据或数据变量类属的说明，它指示该数据或数据变量可能取的值的全体。对于无结构的数据，高级语言如Pascal，除提供标准的基本数据类型--布尔型、字符型、整型和实型外，还提供用户可自定义的枚举类型、子界类型和指针类型。这些类型(除指针外)，其使用方式都顺应人们在算法语言中使用的习惯。对于有结构的数据，高级语言如Pascal，提供了数组、记录、有限制的集合和文件等四种标准的结构数据类型。其中，数组是科学计算中的向量、矩阵的抽象;记录是商业和管理中的记录的抽象;有限制的集合是数学中足够小的集合的势集的抽象;文件是诸如磁盘等外存储数据的抽象。人们可以利用所提供的基本数据类型(包括标准的和自定义的)，按数组、记录、有限制的集合和文件的构造规则构造有结构的数据。 此外，还允许用户利用标准的结构数据类型，通过复合或嵌套构造更复杂更高层的结构数据。这使得高级语言中的数据类型呈明显的分层，如图1-6所示。
高级语言中数据类型的分层是没有穷尽的，因而用它们可以表达算法语言中任何复杂层次的数据。
在控制方面，高级语言如Pascal，提供了表达算法控制转移的六种方式。
(1)缺省的顺序控制";"。
(2)条件(分支)控制:"if表达式(为真)then S1 else S2;" 。
(3)选择(情况)控制:
"Case 表达式 of
值1: S1
值2: S2
...
值n: Sn
end"
(4)循环控制:
"while 表达式(为真) do S;" 或
"repeat S until 表达式(为真);" 或
"for变量名:=初值 to/downto 终值do S;"
(5)函数和过程的调用，包括递归函数和递归过程的调用。
(6)无条件转移goto。
这六种表达方式不仅覆盖了算法语言中所有控制表达的要求，而且不再像机器语言或汇编语言那样原始、那样繁琐、那样隐晦，而是如上面所看到的，与自然语言的表达相差无几。
程序设计语言从机器语言到高级语言的抽象，带来的主要好处是：
高级语言接近算法语言，易学、易掌握，一般工程技术人员只要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言远离机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好，重用率高； 由于把繁杂琐碎的事务交给了编译程序去做，所以自动化程度高，开发周期短，且程序员得到解脱，可以集中时间和精力去从事对于他们来说更为重要的创造性劳动，以提高程序的质量。
算法表达中的抽象机制(一）
简介
要用计算机解决一个稍为复杂的实际问题，大体都要经历如下的步骤。
将实际问题数学化，即把实际问题抽象为一个带有一般性的数学问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的已知条件、所要求的结果、以及在已知条件和所要求的结果之间存在着的隐式或显式的联系。 对于确定的数学问题，设计其求解的方法，即所谓的算法设计。这一步要建立问题的求解模型，即确定问题的数据模型并在此模型上定义一组运算，然后借助于对这组运算的调用和控制，从已知数据出发导向所要求的结果，形成算法并用自然语言来表述。这种语言还不是程序设计语言，不能被计算机所接受。 用计算机上的一种程序设计语言来表达已设计好的算法。换句话说，将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。这一步叫程序设计或程序编制。 在计算机上编辑、调试和测试编制好的程序，直到输出所要求的结果。
在这里，我们只关心第3步，而且把注意力集中在算法程序表达的抽象机制上，目的是引人一个重要的概念--抽象数据类型，同时为大型程序设计提供一种相应的自顶向下逐步求精、模块化的具体方法，即运用抽象数据类型来描述程序的方法。
从机器语言到高级语言的抽象
我们知道，算法被定义为一个运算序列。这个运算序列中的所有运算定义在一类特定的数据模型上，并以解决一类特定问题为目标。这个运算序列应该具备下列四个特征。
有限性，即序列的项数有限，且每一运算项都可在有限的时间内完成; 确定性，即序列的每一项运算都有明确的定义，无二义性; 可以没有输入运算项，但一定要有输出运算项; 可行性，即对于任意给定的合法的输入都能得到相应的正确的输出。
这些特征可以用来判别一个确定的运算序列是否称得上是一个算法。
但是，我们现在的问题不是要判别一个确定的运算序列是否称得上是一个算法，而是要对一个己经称得上是算法的运算序列，回顾我们曾经如何用程序设计语言去表达它。
算法的程序表达，归根到底是算法要素的程序表达，因为一旦算法的每一项要素都用程序清楚地表达，整个算法的程序表达也就不成问题。
作为运算序列的算法，有三个要素。
作为运算序列中各种运算的运算对象和运算结果的数据; 运算序列中的各种运算; 运算序列中的控制转移。
这三种要素依序分别简称为数据、运算和控制。
由于算法层出不穷，变化万千，其中的运算所作用的对象数据和所得到的结果数据名目繁多，不胜枚举。最简单最基本的有布尔值数据、字符数据、整数和实数数据等;稍复杂的有向量、矩阵、记录等数据;更复杂的有集合、树和图，还有声音、图形、图像等数据。
同样由于算法层出不穷，变化万千，其中运算的种类五花八门、多姿多彩。最基本最初等的有赋值运算、算术运算、逻辑运算和关系运算等;稍复杂的有算术表达式和逻辑表达式等;更复杂的有函数值计算、向量运算、矩阵运算、集合运算，以及表、栈、队列、树和图上的运算等:此外，还可能有以上列举的运算的复合和嵌套。
关于控制转移，相对单纯。在串行计算中，它只有顺序、分支、循环、递归和无条件转移等几种。
我们来回顾一下，自从计算机问世以来，算法的上述三要素的程序表达，经历过一个怎样的过程。
最早的程序设计语言是机器语言，即具体的计算机上的一个指令集。当时，要在计算机上运行的所有算法都必须直接用机器语言来表达，计算机才能接受。算法的运算序列包括运算对象和运算结果都必须转换为指令序列。其中的每一条指令都以编码(指令码和地址码)的形式出现。与算法语言表达的算法，相差十万八千里。对于没受过程序设计专门训练的人来说，一份程序恰似一份"天书"，让人看了不知所云，可读性极差。
用机器语言表达算法的运算、数据和控制十分繁杂琐碎，因为机器语言所提供的指令太初等、原始。机器语言只接受算术运算、按位逻辑运算和数的大小比较运算等。对于稍复杂的运算，都必须一一分解，直到到达最初等的运算才能用相应的指令替代之。机器语言能直接表达的数据只有最原始的位、字节、和字三种。算法中即使是最简单的数据如布尔值、字符、整数、和实数，也必须一一地映射到位、字节和字中，还得一一分配它们的存储单元。对于算法中有结构的数据的表达则要麻烦得多。机器语言所提供的控制转移指令也只有无条件转移、条件转移、进入子程序和从子程序返回等最基本的几种。用它们来构造循环、形成分支、调用函数和过程得事先做许多的准备，还得靠许多的技巧。
直接用机器语言表达算法有许多缺点。
大量繁杂琐碎的细节牵制着程序员，使他们不可能有更多的时间和精力去从事创造性的劳动，执行对他们来说更为重要的任务。如确保程序的正确性、高效性。 程序员既要驾驭程序设计的全局又要深入每一个局部直到实现的细节，即使智力超群的程序员也常常会顾此失彼，屡出差错，因而所编出的程序可靠性差，且开发周期长。 由于用机器语言进行程序设计的思维和表达方式与人们的习惯大相径庭，只有经过较长时间职业训练的程序员才能胜任，使得程序设计曲高和寡。 因为它的书面形式全是"密"码，所以可读性差，不便于交流与合作。 因为它严重地依赖于具体的计算机，所以可移植性差，重用性差。
这些弊端造成当时的计算机应用未能迅速得到推广。
克服上述缺点的出路在于程序设计语言的抽象，让它尽可能地接近于算法语言。
为此，人们首先注意到的是可读性和可移植性，因为它们相对地容易通过抽象而得到改善。于是，很快就出现汇编语言。这种语言对机器语言的抽象，首先表现在将机器语言的每一条指令符号化:指令码代之以记忆符号，地址码代之以符号地址，使得其含义显现在符号上而不再隐藏在编码中，可让人望"文"生义。其次表现在这种语言摆脱了具体计算机的限制，可在不同指令集的计算机上运行，只要该计算机配上汇编语言的一个汇编程序。这无疑是机器语言朝算法语言靠拢迈出的一步。但是，它离算法语言还太远，以致程序员还不能从分解算法的数据、运算和控制到汇编才能直接表达的指令等繁杂琐碎的事务中解脱出来。
到了50年代中期，出现程序设计的高级语言如Fortran，Algol60，以及后来的PL/l，Pascal等，算法的程序表达才产生一次大的飞跃。
诚然，算法最终要表达为具体计算机上的机器语言才能在该计算机上运行，得到所需要的结果。但汇编语言的实践启发人们，表达成机器语言不必一步到位，可以分两步走或者可以筑桥过河。即先表达成一种中介语言，然后转成机器语言。汇编语言作为一种中介语言，并没有获得很大成功，原因是它离算法语言还太远。这便指引人们去设计一种尽量接近算法语言的规范语言，即所谓的高级语言，让程序员可以用它方便地表达算法，然后借助于规范的高级语言到规范的机器语言的"翻译"，最终将算法表达为机器语言。而且，由于高级语言和机器语言都具有规范性，这里的"翻译"完全可以机械化地由计算机来完成，就像汇编语言被翻译成机器语言一样，只要计算机配上一个编译程序。
上述两步，前一步由程序员去完成，后一步可以由编译程序去完成。在规定清楚它们各自该做什么之后，这两步是完全独立的。它们各自该如何做互不相干。前一步要做的只是用高级语言正确地表达给定的算法，产生一个高级语言程序;后一步要做的只是将第一步得到的高级语言程序翻译成机器语言程序。至于程序员如何用高级语言表达算法和编译程序如何将高级语言表达的算法翻译成机器语言表达的算法，显然毫不相干。
处理从算法语言最终表达成机器语言这一复杂过程的上述思想方法就是一种抽象。汇编语言和高级语言的出现都是这种抽象的范例。
与汇编语言相比，高级语言的巨大成功在于它在数据、运算和控制三方面的表达中引入许多接近算法语言的概念和工具，大大地提高抽象地表达算法的能力。
在运算方面，高级语言如Pascal，除允许原封不动地运用算法语言的四则运算、逻辑运算、关系运算、算术表达式、逻辑表达式外，还引入强有力的函数与过程的工具，并让用户自定义。这一工具的重要性不仅在于它精简了重复的程序文本段，而且在于它反映出程序的两级抽象。在函数与过程调用级，人们只关心它能做什么，不必关心它如何做。只是到函数与过程的定义时，人们才给出如何做的细节。用过高级语言的读者都知道，一旦函数与过程的名称、参数和功能被规定清楚，那么，在程序中调用它们便与在程序的头部说明它们完全分开。你可以修改甚至更换函数体与过程体，而不影响它们的被调用。如果把函数与过程名看成是运算名，把参数看成是运算的对象或运算的结果，那么，函数与过程的调用和初等运算的引用没有两样。利用函数和过程以及它们的复合或嵌套可以很自然地表达算法语言中任何复杂的运算。
在数据方面，高级语言如Pascal引人了数据类型的概念，即把所有的数据加以分类。每一个数据(包括表达式)或每一个数据变量都属于其中确定的一类。称这一类数据为一个数据类型。 因此，数据类型是数据或数据变量类属的说明，它指示该数据或数据变量可能取的值的全体。对于无结构的数据，高级语言如Pascal，除提供标准的基本数据类型--布尔型、字符型、整型和实型外，还提供用户可自定义的枚举类型、子界类型和指针类型。这些类型(除指针外)，其使用方式都顺应人们在算法语言中使用的习惯。对于有结构的数据，高级语言如Pascal，提供了数组、记录、有限制的集合和文件等四种标准的结构数据类型。其中，数组是科学计算中的向量、矩阵的抽象;记录是商业和管理中的记录的抽象;有限制的集合是数学中足够小的集合的势集的抽象;文件是诸如磁盘等外存储数据的抽象。人们可以利用所提供的基本数据类型(包括标准的和自定义的)，按数组、记录、有限制的集合和文件的构造规则构造有结构的数据。 此外，还允许用户利用标准的结构数据类型，通过复合或嵌套构造更复杂更高层的结构数据。这使得高级语言中的数据类型呈明显的分层，如图1-6所示。
高级语言中数据类型的分层是没有穷尽的，因而用它们可以表达算法语言中任何复杂层次的数据。
在控制方面，高级语言如Pascal，提供了表达算法控制转移的六种方式。
(1)缺省的顺序控制";"。
(2)条件(分支)控制:"if表达式(为真)then S1 else S2;" 。
(3)选择(情况)控制:
"Case 表达式 of
值1: S1
值2: S2
...
值n: Sn
end"
(4)循环控制:
"while 表达式(为真) do S;" 或
"repeat S until 表达式(为真);" 或
"for变量名:=初值 to/downto 终值do S;"
(5)函数和过程的调用，包括递归函数和递归过程的调用。
(6)无条件转移goto。
这六种表达方式不仅覆盖了算法语言中所有控制表达的要求，而且不再像机器语言或汇编语言那样原始、那样繁琐、那样隐晦，而是如上面所看到的，与自然语言的表达相差无几。
程序设计语言从机器语言到高级语言的抽象，带来的主要好处是：
高级语言接近算法语言，易学、易掌握，一般工程技术人员只要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言远离机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好，重用率高； 由于把繁杂琐碎的事务交给了编译程序去做，所以自动化程度高，开发周期短，且程序员得到解脱，可以集中时间和精力去从事对于他们来说更为重要的创造性劳动，以提高程序的质量。