Timetombs

泛义的工具是文明的基础，而确指的工具却是愚人的器物

共 66h / 117a 篇
，更新于 2024-12-21T13:29:20Z+08:00 by   2255bb5

[程序设计语言] 03 [核心概念] 控制流

版权声明 - CC BY-NC-SA 4.0
2014-08-27 09:30，约16495字，阅读约33分钟
[程序设计语言]
03e0cc0 fix add displayed_on_home 2022-11-20 14:49 源码

0 概述

前面介绍了语言的演进以及一些基础概念后，从本篇开始进入了语言的核心问题中。这一篇讨论的是语言计算模型(大致可以用控制流来表述)，大致如下7种 :

  1. 顺序执行 : 最基本的流程控制，按部就班的一条一条按顺序执行；
  2. 选择 : 根据运行时的某些条件来决定执行那些，如if else等；
  3. 迭代 : 反复(或特定次数)的执行一段代码，如for循环；
  4. 过程抽象 : 把一段代码抽象成一个简单的过程单元，用来完成某项特定的代码逻辑；
  5. 递归 : 一个表达式直接或者间接的调用自身；
  6. 并发 : 两个或更多程序片段同时(或伪同时)的执行或求值；
  7. 有意识地不去描述语句或表达式之间的次序或选择情况，意味着任何一种选择都能得到正确的结果。

以上7个基本类别囊括了大部分语言中出现的控制流程和结构，如果我们能以此思考问题(而非特定语言的特定语法)，那么学习一门新语言就会是一件很轻松的事情，也可以使得我们站在各各语言之外来评判它们的优点或者缺点，更可以让我们独立于具体的语言来思考算法问题。以上这些好处，不正是我们梦寐以求的吗。

在不同中类的语言中，这些个类别的控制流也有不同的地位。比如命令式语言中视顺序执行为核心；函数式语言中则大量使用递归；逻辑式语言则有意的模糊控制流这种东西。

1 表达式求值

在讨论控制流之前先讨论下表达式的问题，先明确两个概念 : 运算符通常是指那些采用特殊语法形式的内部函数(比如+-*/等)，运算对象指的是运算符的参数(如2+3，2和3就是运算对象)，那么运算符和运算对象的组合就是表达式。一般根据运算符出现的位置(相对于运算对象而言)，可以分为3类表示形式 : 前缀、中缀和后缀。比如SICP中用的Lisp方言Scheme就运用前缀语法 :

(+ 1 3 4 6)     //用数学表示就是1+3+4+6
(*(+ 1 7) 8)    //(1+7)*8
//前缀有2点好处 : 1参数可任意多个，2扩充方便

C#程序员比较熟悉中缀，其中Objective-C的函数调用语法也是属于中缀，比如下面 :

@interface TestDateTime : NSObject {
}
-(void) setDateTime:(int)year Month:(int)month Day:(int)Day;
@end

//setDateTime的完整名称是 : setDateTime:Month:Day:。想要调用它在OC中称为给对象发消息。
//虽然第一眼看上去怪怪的，但是有个很大的优点就是非常直观，阅读起来明了许多(比起setDateTime(2014，8，15)).

[mytestDateTime setDateTime:2014 Month:8 Day:15]

后缀一般出现在少数地方，比如C#中的i--属于此类。

既然有运算符，那么众多的运算符放在一个表达式里面也就会带来新的问题，比如先计算谁？比如如1+2+3*4/5*7，那么这就涉及到要为运算符设定一个优先级了，其实关于优先级笔者觉得不必去在意，弄不清楚的时候加一个括号()完事，如果谁要是真的在项目中写出如此代码p =(a++)+(a++)*5/3;那就该拖出去打屁股了，如果遇见此类面试题，就在心里默念。。。草泥马。。。

1.1 赋值 - 引用和值

在第一篇引言中介绍程序语言的分类时提到过由于计算模型的不同导致的语言派系分类，这里需要进一步解释一下。

在纯函数式语言中，程序的基本组成部分是表达式，计算也仅是对表达式求值。任何一个表达式对于整个计算的影响也仅限于这个表达式所处的上下文环境。

而命令式语言的情况与此截然不同，计算通常是通过对内存中变量值的一系列修改操作来完成，赋值就是这种修改的最基本手段。每一次赋值都表示一个值被放入一个对应的变量中。

一般来说，如果语言中的一个结构除了返回一个值供其外围环境所使用，还能以其他方式影响后续计算(并最终影响程序输出)，那么我们就说这种结构有副作用。

在纯函数式语言中是没有副作用的，好比我们学的那些数学方程式，你给你一个特定的参数，这个方程式只是依赖或不依赖其外围引用环境，如果这一刻它的计算结果是2，那么任何时刻都是2，一个有趣的术语叫引用透明，用来描述纯函数式中的表达式的特性的。

与此相反，命令式语言通常会被描述为通过副作用的方式完成计算。虽然有时候赋值操作可能产生一个新值，但是我们关心的不是这个新值，而是这一步赋值操作后这个被赋值操作的变量对后续计算的影响。

大部分语言都会区分表达式和语句，前者产生一个值，或许会有副作用；而后者的执行就是为了产生副作用。

从表面看，赋值是一个非常直接了当的操作。然而这种表象之下、在不同的命令式语言中却存在着一些微妙的差异，虽然微妙，却是影响重大。如下代码 :

d=a;
a=b+c;
  1. 第一个语句中，赋值语句右部引用了a的值，并希望把这个值放入d。
  2. 第二个语句左部引用了a的位置，希望把b+c的结果放进去。

这两种解释(值和位置)都是可行的，因为c语言中变量就是能保存值的命名容器，所以我们会说类似的语言的变量是值模型。由于指示位置的表达式被放在赋值语句的左部，所以这种指示位置的表达式成为左值表达式。表示一个值的表达式称为右值。在变量的值模型下，同一表达式也可能是左值或者右值，比如a=a+1，左部的a是左值，用于表示存放结果的位置；右部的a是右值，用于代表a具体所指的值。

在采用了变量的引用模型的语言中，这种左值和右值的差异就更加明显了。如下代码 :

b=2;
c=b;
a=b+c;

在值模型语言中程序员会说 : 把2放入b，然后复制到c，然后用它们两个的值相加，把结果4放入a。

在引用模型语言中的程序员会说 : 让b引用2，让c也引用2，然后把这两个引用送给+运算，并让a引用算出的结果，也是4。

上述的例子不管是引用模型还是值模型，最终结果是一样的，那是因为数值2是具有不变性的，所以我们无法区分引用模型和值模型的不同。由于C#是同时支持值模型和引用模型的，那么如下代码如果我不告诉你stu这个变量是值类型还是引用类型，恐怕你是无法确定最终结果的吧。

class Program
{
    static void Main(string[] args)
    {
        Student stu = new Student();
        stu.Name = "Timetombs";
        stu.Age = 25;
        Student stu2 = stu;
        stu2.Name = "王尼玛";
        stu2.Age = 20;

        Console.WriteLine(stu.Name + ":" + stu.Age);
        Console.ReadKey();
    }
}
//struct or class Student
{
    public String Name;
    public Int32 Age;
}

在采用引用模型的语言中，一个变量就是一个左值，当变量出现在期望右值的上下文环境中时，就必须对它进行简接运算来取得它所引用的值。大部分语言中这种间接运算都是隐式进行的。比如上面代码中的stu，就是指代到通过引用去托管堆中取它真正的数据。有些却不是，比如ML语言，程序员需要用前置叹号来表明这个间接运算。

1.2 赋值 - 装箱和拆箱

对于既有值模型有有引用模型的语言，一些要求引用类型的地方，值类型就无法进行统一的操作。比如C#0中的ArrayList，只接受引用类型，那么就需要对值类型进行包装一下才可进行使用，这个包装过程就是装箱。如下的C#代码 :

ArrayList array = new ArrayList();
Int32 i = 123;
Object o = i;//装箱
array.Add(i);

Int32 j =(Int32)array[0];//拆箱

与装箱想对应的是拆箱，大家可能会认为这条语句Int32 j =(Int32)array[0]是拆箱，当然这么理解问题也不大。严格意义上的拆箱是后半部分((Int32)array[0]，也就是拆出来就算拆箱，而不包含进一步的赋值操作,我们通常所说的拆箱都隐含着一步赋值操作。

1.3 赋值 - 多路赋值

我们知道赋值操作有右结合性，这使得我们可以写出a=b=c的简练代码，在一些语言中(Ruby，Go，苹果新秀Swift语言)我们可以进一步这样写 :

a,b=1,2;
//这里的逗号“,”并不是常见的顺序运算符的意思，而是用于定义定义包含多个值的表达式，也成为多元组(tuple)。
//上面的语句结果就是a等于1，b等于2。


//在多路赋值中交换两个变量的值太简单了。
a,b=b,a;
//如果没有这种语言特性，那么就需要引入临时变量了。


//还有一个多路赋值带来的强大特性，比如我们发现，大多数常用语言中一个函数可以接受多个参数。
//却只能返回一个值，我们不得不去想办法弄一个包装类型来组合我们需要的多个返回值，可恶的不对称啊。有了多路赋值就省心多了。
a,b,c=funx(d,e,f);
//看，多么优美简洁！！！

1.4 表达式里的顺序问题&数学的等值关系

虽然优先级和结合性规则定义了表达式里二元中缀运算符的应用顺序，但却没有明确说明特定运算符的各各运算对象的求值顺序。举例来说，如下表达式 :

a-f(b)-c*d

根据结合性可知a-f(b)将在第二个减法前执行，根据优先级可知第二个减法的右运算对象是c*d这个整体而不是c。但是如果没有进一步的规则描述，我们无法得知a-f(b)是否在c*d之前运行。诸如此类 : 对于f(a,g(b),c)这个子程序调用，我们也不知这三个参数的求值顺序。

为何这个问题那么重要呢？大家可能认为从左到右挨个算不就是了，但是由于如下两个方面原因，大多数语言并未明确规定这种(从左到右或者从右到左的)求值顺序。

  1. 副作用 : 如果f(b)这个子程序可能会修改c的值，那么a-f(b)-c*d的求值结果将依赖f(b)和c*d哪一个先执行；类似的，如果g(b)修改了a或者c的值，那么f(a,g(b),c)的结果也是依赖于参数的求值顺序。
  2. 代码改进 : 子表达式的求值顺序对于寄存器分配和指令调度都有重要的影响。比如a*b+f(c)，我们可能会希望在执行a*b之前调用f(c)。因为如果先计算乘法，则在调用f(c)之前就要先保存起来乘积，因为f(c)可能会用光所有的寄存器。

一些语言例外的规定的求值顺序(Java和C#都是规定从左至右的求值顺序)。如果没有这种强制的规定，编译器就可适当的安排出一些高效的代码指令，但是也有可能会带来棘手的副作用问题。

数学的等值关系 : 有些语言为了生成高效的代码而允许编译器对一些表达式做出重新整理，前提是它们满足数学中的交换、结合或分配律。如下面的例子 :

a=b+c;
d=c+e+b;

//等效的优化后的代码 
a=b+c;
d=a+e;

不幸的是虽然数学上的算术运算符遵循各种交换、结合和分配律，但是计算机上的数学运算确不能如我们想的那样，因为计算机中的数是有精度问题的。对于32位整数的计算(32位最大整数43亿左右)，如b-c+d，如果b、c、d都是20-30亿之间的整数，那么b-c+d如果正常计算时可以得出正确的值的；但是如果编译器给重新整理成b+d-c,那么b+d就会可能会造成算术上溢。

许多语言都会算术溢出提供了动态语义检查，在一些语言中可以关闭这种动态检查以降低运行时的开销，比如C#中的checked和unchecked关键字就是干这事的。另外即使不是溢出问题，一些涉及浮点数的表达式的不同整理结果也会有不同的结果，虽然他们在数学形式上是等价的，其中问题我想大家或许都遇到过吧。

1.5 短路求值

对于布尔表达式，如果编译器可以对其执行短路求值，那么它生成的代码可以在表达式前一半的结果可以确定整个表达式的值的情况下跳过后一半的计算。

比如(a<b)and(b>c)，如果a>b，那么完全没必要去检查b是否小于c就可以确定这个表达式一定为假。在一些特殊情况下，短路求值可节省大量时间，比如if(func;func())。实际上这种情况下短路求值已经改变了布尔表达式的语义，如果非短路求值，那么在func不存在的情况下去执行func()，程序是会抛出错误的。

我们常见的语法表现形式是&&和||这种布尔运算符身兼多职，既是布尔运算符又会触发短路求值，但是有一些语言针对短路求值是有单独的语法形式的，比如Clu语言中布尔运算符是and和or,短路运算符是cand和cor。这是为何呢，因为有些代码逻辑是不需要这种短路求值的优化的。

2 结构化和非结构化的流程

汇编语言中的控制流通过有条件的或无条件的跳转(分支)指令来完成，早期的高级语言模仿这种方式(如Fortan)，主要依赖goto来描述大部分非过程化控制流，比如下面代码 :

if A < B goto label1;
//其他代码
label1;
//label1是语句标签。

在汇编向高级语言演进的数10年中，关于goto的争论一直是最激烈的话题。最后的结果是随着结构化程序设计语言的热潮，反对goto的这一派取得了胜利，大部分后续高级语言中已经禁止了goto或者仅仅在受限的上下文环境中使用。在结构化的程序中，一个子程序中的流程控制都可以通过顺序、选择、循环(迭代、递归)来描述，结构化语言不依赖标签(上面例子中的label1)，而是词法上嵌套的词法边界作为流程控制的结构单元。

这里笔者说点我对语言发展的一点理解，如有不当之处欢迎指出。

  1. 程序是由代码+数据组成，早期的机器语言、汇编语言、高级语言以及面向对象语言等等各类语言均是如此，语言所要解决的核心问题就是完成计算(通过代码操作数据来完成计算)。在机器和汇编时代，代码和数据都是交织在一起的，我们知道程序越来越大，数据越来越复杂，导致维护越来越困难。那么如何解决这种复杂性问题呢，答案把其中共性的东西拿来重复使用，既复用。既然是复用，那么必须有一个东西来表示这种可复用的整体，这种打包一组代码或数据成一个复用整体的过程称为抽象化，在开篇时我也说抽象是无处不在的，抽象是解决复杂性问题的有效途径。那么是复用代码还是数据呢？还是两者一起复用呢？

  2. 子程序抽象 : 在汇编的进化到高级语言阶段，随之也是进入了结构化程序设计阶段。这个阶段引入了子程序(函数)，子程序主要对代码进行复用，不是有句话是说程序=数据结构+算法吗，其中这个算法也就是子程序，数据结构则是对零散数据的一种组织方式。(如果从这个角度来看，goto这种在非结构化编程时代可以任意跳转的东西拿到结构化时代是必然会导致问题的，因为一部分代码已经被抽象封装成一个隐藏复杂实现细节的函数了，以goto的变态能力是会打破这种封装的；即使goto可以使用，那么它的应用范围必定会受到子程序这种结构的限制，另外子程序内部的的一些流程控制也可以通过一些被弱化了的goto(比如用于循环中的break和continue、用于子程序返回的return)代替，这也就是解释了为何一些现代语言完全禁用或者限制goto的使用场景，因为使用goto的场景已经不存在了，解决问题的思考方式也不是goto时代的思考方式了。)

  3. 数据的抽象 : 结构化程序设计引入子程序对代码进行抽象，但是子程序和它要处理的数据依然是分离的，随后在90年代兴起的面向对象语言则进一步的抽象，把子程序和其要处理的数据打包成一个对象，隐藏掉了复杂的数据处理细节。然而现实世界中不是任何东西都可以抽象成一个对象的，也都不是一个孤立的对象，多个对象交互时对象的封装能力是把双刃剑，因为有时候封装带来很多的使用上的不便，明明一步到位的操作必须要绕上一圈才能解决，所以有些面向对象语言具有这种破坏封装性的能力，比如ruby中的instance_eval(上下文探针)可以任意的替换掉对象内部的私有字段。

  4. 上述的观点是以代码为主线，而非程序的另一个核心数据，其实从子程序抽象到面向对象，这些是实现手段，而非目的，其根本目的是为了操作数据来满足现实世界的需要，如果以数据为主线，那么结构化程序设计时代可以认为是数据的结构化时代，子程序是为了满足操作结构化数据的而产生的；面向对象则是把对特定数据结构数据操作的子程序打包到了**数据结构(对象)**中。面向对象的封装隐含的包含了一部分的数据操作逻辑，然而这也损失一部分灵活性作为代价(特别是强类型语言)。so,随着多核时代的发展、硬件性能的进一步提升，笔者认为支持并发编程(我觉得没有副作用的函数式语言是并发的最好选择，但是现在基于冯诺依曼计算模型的计算机体系也是其最大的绊脚石)、动态类型(注重语言的表现能力，而非偏向于性能类)的语言会得到蓬勃发展，而强类型的C#我觉得或许是最后一个大范围应用的面向对象时代的强类型命令式语言吧。

2.1 goto的结构化替代品

上面扯了那么多，跑远了，哈哈，转入正题。既然非结构化的goto已经不适合结构化的程序设计了，那么一些使用goto的地方也随之出现一些替代品来完成结构化时代的流程控制。

循环中的退出和继续 : 我们常写C#的都知道for循环中可以用break来终止循环，用contiune来终止当前循环从而进入下一次循环，看下面代码 :

//for-break
for(int i = 0; i < 10; i++)
{
    if(i == 5)
    {
        break;
    }
    Console.WriteLine(i);//
}
//for-goto
for(int i = 0; i < 10; i++)
{
    if(i==5)
    {
        goto label1;
    }
    Console.WriteLine(i);//
}
label1:
//如果你看一下编译后的IL代码，会发现两者完全一模一样的，都是用brtrue.s来实现的跳转
//continue也是这样的。如果这样看，break、continue也就是用于循环中的弱化了的goto。

从子程序提前返回 : 这个例子就不去写了，常用的主要替代品是显示的return语句。

多层返回 : return或局部的goto只能在子程序中返回,如果遇到多层嵌套的子程序，想从内层的子程序返回来结束外围子程序的执行，那return和局部的goto就无能为力了。这种情况下，语言实现要保证能恰当的恢复栈上的子程序调用信息，这种修复工作称为回卷，为完成此事，不仅必须释放需要跳出的所有子程序的栈帧，还要执行一些信息管理工作，比如恢复寄存器内容。作为这种情况下的goto的替代品，也可称为非局部goto，Common Lisp提供了return-from语句来明确指定需要退出的词法外围函数或嵌套块，还可以提供一个返回值 :

//定义一个搜索函数
(defun search(key)
  //定义一个内嵌的搜索文件的子函数
 (defun serarchfile(filename)
    //...搜索代码
    //通过指定函数名来退出到外层serach函数
   (return-from search file)
  )
 
  //...搜索准备代码key转换为keyfilename
  //调用searchfile函数
 (searchfile keyfilename)
)

//上面凑合的Common Lisp代码，如果有误还请指正，笔者不熟悉这块

Common Lisp和另外一个语言ruby中还内置一个throw/catch语法来支持这种多层返回，注意这种结构并不是所谓的异常处理，而是一种多层返回的语法结构，直白点说是一种功能强大的变相goto，看下面代码 :

//定义一个方法
def search_file(filename,pattern)
   file=File.Open(filename)
   //遍历文件每一行
   file.each{|line|
        //根据parrern匹配模式查找，如果匹配就返回到定义found标签的位置
        throw :found,line if line=~/#{pattern}/
   }
end

//用catch定义一个found标签
math=catch:found do
   serach_file("f1",key) 
   serach_file("f2",key)    //如果f2文件找到了则就会返回line至math
   serach_file("f3",key)
   "not fount"              //找不到就执行到此处了
end

print match

错误和异常 : 多层返回的概念假定了被调用方知道调用方期的是什么，并且能返回一个适当的值。还存在一种情况，其中深层嵌套的子程序中发生了一些情况，导致无法继续执行下去，而且因为没有足够的环境信息，甚至无法合适的结束自己的工作，这种情况下，唯一能做的就是退回去，一直回退到能够恢复执行的地方，这种要求程序退回去的条件通常称为叫做异常。常见的结构化的异常处理和多层返回有很大的相似性，两者都需要从某一个内层上下文回退到外层的上下文。具体的差异则是多层返回是内层的上下文正常的完成计算然后根据需要返回正确的值，然后转移到外层上下文，并不需要后续处理。而异常中的内层上下文已经是无法进行正常的计算，必须以一种非正常的退出一直回卷，然后触发某个特殊的处理流程直到catch到它。

2.2 继续(Continuations)

如果进一步推广上一小节中造成栈回卷的非局部goto概念，则可以定义一种称为继续(Continuations)的概念。从底层来看，一个继续是由一个代码地址与其关联的一个引用环境组成的，如果跳转到这个地址，就该恢复这个引用环境。从抽象层面看，它描述一个可能由此继续下去的执行上下文。在Scheme和Ruby中，继续是基本的一等公民，我们可以利用这种机制有效的扩充流程控制结构集合。感兴趣的可以去查查Ruby Continuations，这是一个非常强大的编程特性。

Scheme中支持继续由一个通常称为call-with-current-continuation的函数实现，有时简称call/cc。该函数有一个参数f,f也是一个函数；call/cc调用函数f,把一个记录着当前程序计数器和引用环境的继续(暂时称为是c)c传递给f，这种继续c由一个闭包来表示(通过参数传递的子程序的表示的闭包并无不同)。在将来任何时候，f都可以调用c,然后可以用c来重新建立其保存的上下文。一般的应用情况是我们把这个c赋值给一个变量，则可重复的调用它，甚至我们可以在f中返回它，即使f已经执行完毕，仍然可以调用c。call/cc功能非常强大，足以构造出范围广范的控制结构，比如goto、多层返回、异常、迭代器(下一部分会介绍到)、按名调用参数(子程序和控制抽象中介绍)等等。

3 顺序复合(Sequencing)

我觉得这个翻译有点不恰当(顺序复合)，我们直接叫顺序就是了，也就是按照语句先后顺序来执行的意思。

这是最基本的控制流程，也是命令式语言的核心。那么一些语句的列表通常称为是复合语句，通常由begin...end 或者{...}包围起来。如果复合语句的一开始处包含变量声明，则通常称为块。这里再提一下Ruby,上周花时间翻了一遍《Ruby元编程》，发现这个块这个东西在Ruby中居然可以赋值给一个对象(用Proc包装)，可以当参数传递，实在是大大滴灵活。

在Algol 68(一种执令式程序设计语言)一类语言中，语句和表达式之间非常模糊，甚至完全无法区分，语句列表的值通常就是最后一个元素的值。在Common Lisp中，程序员可以选择返回第一个、第二个或者最后一个元素的值。当然，除非那些不提供返回值的子表达式有副作用，否则这种复合语句在纯函数式编程语言中是没有任何作用的。在Lisp中，各种顺序结构只是被用在哪些不符合纯函数式程序设计模型的代码片段中。这块理解起来有点绕，其实只要明白一点，这种语句列表的目的是为了依赖上一条语句的执行结果(副作用)来继续执行下一条语句的，而纯函数式中是没有赋值这个概念的，也不依赖副作用，所以对它来说这种语句列表没多少用处可言。

即使是在命令式语言中，副作用这个东西也是有利有弊的。一些语言(Euclid和Turing)是不允许函数(因为有返回值而可以用在表达式中的子程序)有副作用的，关于这个副作用带来的影响在前面的表达式里的求值顺序中有讨论，这里就不去赘述了。没有副作用的函数可以保证它是幂等的，就像数学中的函数一样，对一组参数在重复调用时总是得到相同的结果，不论多少次或者什么时间都不会影响后续执行结果(想想多线程编程中那些什么个先后顺序、调用时间等问题，这个幂等特性可以说好处大大的)。但是，命令式语言的计算模型(通过赋值影响后续操作)就是靠着副作用过日子来着，就好比在C# new一个Point对象，你不去设置x,y点的值还执行个鸟蛋。

4 选择

现在大部分命令式语言中采用的选择语句，都是从Algol 60引进过的if...then...else的某种演进变形 :

if condition then statement
else if condition then statement
else if condition then statement
...
else statement

不同的语言在语法细节上有差异，但是终究都是一个条件后面跟着一个语句分支(可以是单条语句也可以是语句列表)。为了防止嵌套的if最后堆积起一批结束符，大部分语言都提供一种elseif的关键字 :

if a=b {...}
elseif a=c {...}
elseif a=d {...}
else {...}

4.1 短路条件

虽然if...then...else语句的条件是一个布尔表达式，但是通常没有必要求出这个表达式的值放入寄存器。大部分机器都提供了条件分支指令(如上面提到的IL指令brtrue.s，因为这个表达式求值的目的并不是为了值，而是为了跳转到合适的位置。这种看法使得可以对#5 短路求值的表达式生成高效的代码(称为跳转码)。跳转码不但可以用于选择语句，也可用在逻辑控制的循环中。如下面代码 :

if((A>B)&&(C<D)||(E!=F)){
   //代码1
}
else{
   //代码2
}

在不使用短路求值的Pascal中，生成的代码大致如下(它会计算每个表达式的结果并放入寄存器r1...，然后再决定跳转) :

     r1=A
     r2=B
     r1=r1>r2
     r2=C
     r3=D
     r2=r2>r3
     r1=r1&r2
     r2=E
     r3=F
     r2=r2!=r3
     r1=r1|r2
     if r1=0 goto L2
L1: //代码1
    goto L3
L2: //代码2
L3:

跳转码的情况于此不同，它不会把表达式的值存入寄存器，而是直接跳转(只用到了r1和r2两个寄存器，明显也不会针对整个表达式进行求值，比上面的要高效一些) :

     r1=A
     r2=B
     if r1<=r2 goto L4
     r1=C
     r2=D
     if r1>r2 goto L1
L4: r1=E
     r2=F
     if r1=r2 goto L2
L1: //代码1
    goto L3
L2: //代码2
L3:

总的来说短路条件对于语言实现者来说，可以生成更高效的底层代码。

4.2 case/switch语句

对于if else代码来说，如果嵌套的层数过多、或者是用于判断的条件表达式是基于一些有限的简单值(或编译时常量)，那么出现了一种更为优雅的语法结构case语句，如下面的代码 :

//if else语法形式
i=...  //给i赋值
if i=1 then
  //codeA
elseif i=3 then
  //codeB
elseif i=5 then
  //codeC
elseif i=10 then
  //codeD
else
  //codeE
end

//case语法结构
case i...
   1:     codeA
   3:     codeB
   5:     codeC
   10:    codeD
   else   codeE
end

其中codeA-E为语句列表(表示条件分支语句)。冒号前面的1，3，5，10，这些条件表达式属于case的语句标号。标号列表中的常数必须互不相同，大部分语言中只允许使用简单的整数、枚举、字符等，C#中还允许字符串。我们发现case语句确实是比if elseif要简洁一些，但是这种语法结构的出现并不单单是为了语法简洁的需要，而是基于编译器可以生成更高效的目标代码，这也是一个由实现驱动设计的一个明显例子。关于生成高效代码的细节就不去细说了，大致方案是可以利用跳转表来进行高效的分支跳转(具体的查找分支策略有顺序、散列、折半检索等)，感兴趣的可以翻翻书。

C语言中的case(switch语法是现在我们熟知的case语句语法形式)，每一个标号是一个单一的值(其实上面的case代码例子我动了下手脚，那里是允许标号列表的，标号也可以表示一个数值区间)，而C语言这种结构则是简化了的，另外它也规定了每一个分支后面必须跟一个break语句，不然可能会进入下一个case分支中 :

switch(i){
 case 1:
        //分支代码
        break;
 case 3:
        //分支代码
        break;
 case 5:
        //分支代码
        break;
 case 7:
        //分支代码
        break;
 default:
       //默认分支语句
       break；
}

从历史角度看，case语句是Fortan中计算goto语句和Algol 60的switch结构的后裔。早期的Fortan中可以写出基于整数值的多路分支跳转 :

goto(15,50,100),I
//如果I是1，则跳转到标号15的语句，如果是3则跳转到标号100的语句，如果不在1..3范围内，则这条语句是不会执行的。

Algol 60的switch语句也属于标号数组 :

switch S:=L15,L50,L100;
...

goto S[I]

这里的I和Fortan那个例子是一样的，一个类似于数组下标的东西。

5 迭代

迭代和递归是计算机能够重复执行一些操作的两种机制；命令式语言倾向于使用迭代、函数式语言则更看重递归。大多数语言中的迭代都是以循环的形式出现的，和复合语句中的语句一样，迭代的执行通常也是为了副作用，也就是修改一些变量的值。根据用何种方式控制迭代的次数来看，循环有两个主要变种"枚举控制的循环"和逻辑控制的循环。前者是在给定的某个有限的集合中执行，后者则是不确定要执行多少次(直到它所依赖的表达式结果被改变)。对于这两种结构，大多数的语言都提供了不同的语法结构来表示。

5.1 枚举控制的循环

枚举控制的循环有四个要素(下标变量、初值、边界值、步长)，枚举控制的循环的历史和Fortan一样悠久，但是随着语言的发展，其语法和语义都与Fortran有了很大距离。如Fortran早期版本中循环的语法形式如下 :

   do 11 i=1,10,2
     //...代码
11 continue

do后面的11是一个标号，它必须出现在当前子程序里随后的某个位置，11 continue代表的是循环体的最后一个语句，continue是个没有任何作用的空操作(表示循环结束继续执行后续语句)。标号后面的变量(就是i)就是循环的下标。等号后面第一个值(1)是下标的初始值、第二个(10)是下标的最大值/边界值、第三个(2)是它的步长/增量。与上面等价的更准确的代码如下 :

      i=1
11   //...代码
      i=i+2
      if i<=10 goto 11

早期的这种结构被证实有诸多的问题，比如其中的边界值和步长都要求是正整数的常量或变量，不允许表达式。Fortran77取消了这个限制，允许任意正负的实数或表达式，由于在计算机中实数的精度问题导致的条件判断问题(两个相近的浮点数的比较可能会得到相反的结果)，Fortran99中又取消了实数作为边界值和步长的功能。早期的do循环(上述第一个实例代码)中还存在以下更严重的微妙问题 :

  1. 如果循环体中的语句修改了i的值，那么循环执行的次数就和人们看到的头部声明不一致。如果是无意间的修改，那么这种错误很则难定位；如果是有意修改，则会导致理解上的难度。
  2. 可以用个goto跳出跳入这种循环，比如在i没有争取初始化时就跳入循环的这种错误，编译器却没办法察觉到。
  3. 如果用goto跳出循环，那么i的值将是最近赋给的值；而如果循环正常结束，那么i的值却是由实现决定的。对于上面的例子，我们可能认为在循环正常结束时i的值是11(也就是第一个大于设定的最大值10的整数)，可惜的是如果这个最大值不是10，而是整数的最大值，那么它再+1则导致算术溢出。在大多数实现中，这种情况的溢出会导致成为一个负值，造成一个死循环。
  4. 因为与边界值的比较是在循环的后面，则即使循环的初值比边界值大，循环依然会执行一次。

这些问题不仅与Fortran有关，在任何语言设计枚举控制的循环时都要解决这些问题。如Modula-2中的更友好的循环语法形式 :

FOR i:=first TO last By step DO
  //...代码
END

其中first、last、step都是任意赋值的整数、枚举或者区间表达式。基于上面提出的四个问题，我们有如下疑问 :

  1. 循环里可以修改i、first或者last的值吗？如果可以，这种修改对循环有何影响？
  2. 如果first比last大(或者step为负数是first比last小)，会出现什么情况？
  3. 循环结束后i的值是什么？
  4. 允许从外面跳入循环吗？

下面主要讨论这几点问题。注意阅读上面问题时不要被你现在所用的语言带来的先入为主的思维给迷糊或影响，最开始的语言中这些问题是要由编译器来控制解决的，而非现在的C风格循环(C是把这些问题大都抛给了程序员来控制，比如1中是否可以修改、2中改为由程序员控制条件判断、3中限制i的作用域为循环体内、4为不允许跳入但是允许提前退出等等)。

  1. 修改循环的下标变量或者边界值 : 早期的大部分语言都禁止在枚举控制的循环中修改下边变量。但是笔者发现现在多接触到的各种语言大都放开了这个限制，允许修改了。

  2. 空的限界 : 限界是什么呢，就是初值和边界值的中间取值区域，如果此区间为空，也就是说循环条件不满足，则语言都不回去执行循环。

  3. 循环的方向 : 可能大家都注意到了，上面的讨论的时候都有一个关于步长的假定，那就是步长为正(也就是first小于last)。那么如果是负的step,则就需要从另一个方向来结束循环。所以有些语言就要求程序声明步长的正负、或者干脆就是步长必须是常量(以方便生成代码)。

  4. 在循环外访问下标变量 : 有些语言未明确定义；有些则是保证这个变量是最后一个的赋值，那么算术溢出了呢，对不起，没明确规定；比较靠谱的做法是限制其使用范围为循环的局部变量，出了循环就不再有效。

  5. 跳转 : 语言大都已经进入从循环外goto到循环内部，但是从内部跳出则也都相应的提供了结构化的操作，比如C#中的break。

前面我们说到循环有两个主要的变种枚举控制的循环和逻辑控制的循环，这两重结构在语言中大都也是两套语法形式，有一些语言却是一套语法表现两种情况，了解就是了，不必去深究了。新型的for循环的设计反应了语义和实现两方面的考虑，比如语义方面关于下标和边界值的修改、其作用域以及goto的跳入跳出；实现方面有浮点数的精度问题、循环检测方向以及迭代结束时的溢出问题。C中的for循环把这里面的绝大部分问题都交由了程序员来控制，严格意义上说C的for循环是属于逻辑控制的(当然任何枚举控制的循环都可重写为逻辑控制的循环，实际上编译器背后也是这样做的，主要的差异还是语义上的差别带来的思维方式上的差异)。如下面的C的for语法形式 :

for(int i=first; i<=first; i+=step){
    //...代码
}

等价的逻辑控制循环 :

int i=first;
while(i<=first){
   //...代码
   i+=step;
}

这种形式就如上面所说，溢出检测、循环方向都有程序员控制，同时下标变量限制在循环内，也可以对下标变量修改来影响循环的执行，当然了，这也是程序员的责任。for中的三个表达式都可为空(for(;;)，条件检测默认是true)，那么它也就是一个while循环。这种把控制信息都放在头部的方式在清晰性和代码简洁上都有很好表现。

5.2 迭代器

上面的循环语法大都是在在一个算数值(first,last,step这些值)上进行迭代，出于两点考虑 : 1我们希望能降低枚举元素(可迭代的元素)的代码与使用这些元素的代码的耦合度，2我们也希望能在更复杂的元素上(而不是简单数值，比如集合)上面进行迭代。一些语言(比如Ruby,C#等)提供了一种称为迭代器的机制来完成这两点目标，另外一些语言(比如C++，java)提供了另外一种基于迭代器对象的结构来支持上述两点目标(笔者觉得C#中的迭代器也是依赖迭代器对象来实现的)，虽然这种对象很容易使用，但是写起来确挺麻烦的。

真迭代器 : Clu，Ruby等语言允许任何容器对象提供一个枚举自己元素的迭代器，这种迭代器就像是允许包含yield语句的子程序，每次yield生成一个循环下标。for循环的设计也融合了这种迭代器的调用(C#中提供了单独的foreach)。前面的Modula-2代码 :

FOR i:=first TO last By step DO
  //...代码
END

在Clu中这样写 :

for i in int$from_to_by(first,last,step) do
 //...代码
end

其中from_to_by是一个内部的迭代器，它生成从first到last，以step为增量的一些列整数。在被调用时，这个迭代器算出循环的第一个下标值，然后通过yield语句返回给调用者，yield语句很像return，但是不同的是再每次循环结束后控制权会再次的交给迭代器，重新开始下一次yield，直到迭代器没有元素可yield为止才结束for循环。从效果上看迭代器就像是另外一个控制线程，有它自己的程序计数器，它的执行与为它提供下标值的for循环交替执行，这一类通常称为真迭代器。

迭代器对象 : 大多数命令式语言中，迭代器的实现大都是for循环的一种特殊形式，以及一种在循环中枚举值得机制。这两个概念可以分开来，一些语言提供枚举控制的循环，但却没有yield语句，也没有用于枚举值的独立的类似线程上下文，它们通过一种对象(面向对象语言中的对象)来实现迭代器，这个对象提供判断是否可以继续循环、获取当前枚举到的元素等方法，在调用期间，这个对象负责保存迭代器的迭代状态。笔者认为C#也是这种实现机制(虽说C#有yield语句，但是却只是一个编译器的语法糖而已)，以前写过一篇C#中迭代器的博客，可以点这里查看。

C++实现迭代器的方式不同于上述两者，它应该说是一种利用操作符重载机制来改变了一些操作符的语义实现的。它在特定的上下文环境中重新定义了!=、++、*等运算符，使其可以满足上述的2点目标要求，如下面的C++迭代器的使用 :

tree_node<int> *my_tree=...
//...
for(tree_node<int>::iterator n=my_tree->begin();
                             n!=my_tree->end();
                             ++n){
  //...使用n
}

其中n封装了我那篇介绍迭代器的博客中的迭代器对象MyEnumerator；C++中实现这个迭代器对象会复杂一些，其中涉及到一个运算符重载、变量的值模型以及垃圾收集等问题。

不用迭代器的迭代 : 在那些没有真迭代器或者迭代器对象的语言中，还是可以通过编程方式实现集合枚举和使用元素之间的解耦的，用C语言做例子 :

tree_node *my_tree;   //要枚举元素
tree_iter ti:         //保存迭代器状态
//...
for(ti_create(my_tree,&ti);
              !ti_done(ti);
              ti_next(&ti)){
     tree_node *n=ti_val(ti);
     //...代码 
}
ti_delete(&ti);

与提供迭代器的语言相比，代码简洁性上差了一些、用作迭代器的代码就是一个类型和一组函数(由于C没有提供任何抽象机制把它们包装成一个整体)，所以由于疏忽出错的几率也大不少。

5.3 逻辑控制的循环

与枚举控制的玄幻相比，逻辑控制的循环在语义和细节方面都要简单一些，不用去管那些什么下标、初值、边界值之类的，总之就是条件满足就循环，不满足就退出。要控制的地方也就是条件检测出现的地方。根据检测条件出现的位置，分为3类前置、后置、中置，一般前两种常用一些(C#中前置就是while,后置就是do while，中置可以用for(;;)+break来做)。

前置检测 : 由Algol W引进，后来被Pascal保留 :

while 条件 do 循环体语句列表

在以前没有真正的while循环的语言中，大都使用枚举控制的循环，为了获得while的效果，则会用如下的代码结构(借助标号和goto完成) :

lable_begin:
if 条件不满足 goto lable_end
  //...循环体
goto lable_begin
lable_end:

后置检测 : 这种的循环体不管是否满足循环条件，都至少会执行一次循环体。如C语言的do..while语句 :

do{
   line=read_line();
   //...代码
} while line[0]!='$';

中置检测 : 在许多语言中中置检测都依赖if和goto来完成，但是人们也希望能有更加结构化的语法替代品，比如Modula-2中引进了中间检测(LOOP关键字)，也成为一个半循环，语法形式入下 :

LOOP
    line:=ReadLine();
    IF AllBlanks(line) THEN EXIT END;
    //...代码
END；

其中for+break(或者while(true)+break)也可以提供类似的效果:

for(;;){
   line=read_line();
   if line[0]!='$' break;
   //...代码
}

6 递归

递归和上述讨论的其他控制流都不同，它不依赖特殊的语法形式，只要语言允许函数直接或间接的调用自身，那么就是支持递归的。大部分情况下递归和迭代都可以互相用对方重写的。

6.1 迭代和递归

早期的一些语言不支持递归(比如Fortan77以前的版本)，也有一些函数式语言不允许迭代，然而大部分现代语言都是同时支持两者的。在命令式语言中，迭代在某种意义上显得更自然一些，因为它们的核心就是反复修改一些变量；对于函数式语言，递归更自然一些，因为它们并不修改变量。如果是要计算gcd(更相减损法)，递归更自然一些 :

int gcd(int a,int b){
  if(a==b) return a;
  else if(a>b) return gcd(a-b,b);
  else return gcd(a,b-a);
}

用迭代也未尝不可 :

int gcd(int a,int b){
   while(a!=b){
      if(a>b) a=a-b;
      else  b=b-a;
   }
   return a;
}

尾递归 : 经常有人说迭代比递归效率更高，其实更准确的说法应该是，迭代的朴素实现的(无优化)效率通常比递归的朴素实现的效率要高。如上面gcd的例子，如果递归的实现确实是实实在在的子程序调用，那么这种子程序调用所带来的栈的分配等的开销确实要比迭代要大。然而一个优化的编译器(通常是专门为函数式语言设计的编译器)，常常能对递归函数生成优异的代码，如上面的gcd尾递归(尾递归函数是指在递归调用之后再无其他计算的函数，其返回值就是递归调用的返回值)。对这种函数完全不必要进行动态的栈分配，编译器在做递归调用时可以重复使用当前的栈空间，从效果上看，好的编译器可以把上面递归的gcd函数改造为 :

int gcd(int a,int b){
start:
   if(a==b) return a;
   else if(a>b){
     a=a-b;
     goto start;  
   }
   else{
     b=b-a;
     goto start;
  }
}

即使是那些非尾递归函数，通过简单的转换也可能产生出尾递归代码。

6.2 应用序和正则序求值

在上述的讨论中，我们都假定所有参数在传入子程序之前已经完成了求值，但是实际中这并不是必须的。完全可以采用另外一种方式，把为求值的之际参数传递给子程序，仅在需要某个值得时候再去求它。前一种在调用前求值的方案称为应用序求值；后一种到用时方求值的方式称为正则序求值。正则序求值在宏这个概念中是自然而然的方式，前面讨论的短路求值、以及后面要讨论的按名调用参数也是应用的正则序求值，一些函数式语言中偶尔也会出现这种方式。

C语言中的宏用来执行一些快速而很小的非递归函数。比如为了确定能否整除另一个数，C程序员可能写 :

#define DIVIDES(a,n)(!((n)%(a)))

在使用DIVIDES的任何地方，预处理器都会以文字方式，对宏定义的参数做适当的替换后，把它带入到程序里面去，如DIVIDES(x,y+z)会替换成!((y+z)%(x))。由于宏是基于一些简单的正则匹配替换，上面代码中的n和a的括号都是必不可少的，假如没有括号，那么替换后的结果就是!(y+z%x),按照优先级来说，这根本就不是你要的结果。这里面还不是太大问题，加一个括号就是了，更严重的是会有一些副作用产生 :

#define MAX(a,b)((a)>(b)?(a):(b))

如果我这么调用MAX(i++，j++)，导致i和j都执行两次++，产生了两次副作用，这是我们不愿意看到的结果。总结来说，只有在表达式求值不会产生副作用的情况下正则序才是安全的。

惰性求值 : 从清晰性和高效的角度看，应用序求值通常会比正则序合适一些，一次大部分语言都采用如此的方式。然而也确实有一些特殊情况下正则序更高效一些，而应用序会造成一些错误出现，这种情况的出现时因为一些参数的值实际上并不会被需要，但是还是被求值了，应用序求值有时也成为非惰性求值，比如下面的JS代码就会是一个死循环 :

function while1() {
    while(true) { }
}
function NullFunction() { }
//NullFunction并不需要参数，但是依然执行了while1导致死循环下去。
console.log(NullFunction(1,2,3,while1()));

Scheme通过内部函数delay和force提供可选的正则序求值功能，这两个函数提供的实际上是惰性求值的一种实现，如果没有副作用，惰性求值的语义整好就是等于正则序求值。但是如何保证无副作用，实现代价挺大的，大部分的一些语言都未提供惰性求值，根本原因就是实现的代价过于昂贵。但是在函数式语言中，比如Haskell中是完全没有副作用，这类语言对参数都采用正则序(惰性)求值。

7 总结

本篇首先从表达式开始，介绍了表达式(语句)中的一些基本概念；然后从讨论了从汇编时代到结构化程序设计时代语言中的控制流程的演进以及发展；有了前面两个基础，后面就详细的介绍了程序中的三大基本流程控制结构顺序、选择、循环(递归和迭代)的发展以及语法改进细节，并发现有些语言特性的发展是由实现驱动的，有些则是由使用方面驱动的。有些地方笔者不是吃的很透(比如继续这一小节)，难免会有一些错误或者不严谨的地方，欢迎园友们不吝赐教。

2014-08-27 09:30，约16495字，阅读约33分钟
[程序设计语言]
03e0cc0 fix add displayed_on_home 2022-11-20 14:49 源码
上一篇 : [程序设计语言] 02 [核心概念] 名字、作用域和约束(Bindings)
下一篇 : [程序设计语言] 04 [核心概念] 数据类型