编程语言中的控制结构

引论

第1章 早期编程语言

第1.1节 处理器之中的控制流

第1.2节 机器语言, 汇编语言

第1.3节 FORTRAN

第1.4节 ALGOL 60

第1.5节 条件式和循环

第1.6节 从循环和块之中及早退出

第1.7节 深入阅读

第2章 结构化编程

第2.1节 一场运动和一场争议

如今结构化编程指的是使用高层次控制结构 (条件式, 循环, ...) 而非低层次的goto跳转这一毫无争议的编程实践. 然而, 在1965-1975期间, 结构化编程则是充满争论的主题, 其既可以视为一场迈向看待软件的新角度的运动, 也可以视为关于如何编写良好程序的一场争议.

结构化编程运动.

第2.2节 没有goto的编程

第3章 非局部控制

第4章 控制反转

第5章 函数式语言

第5.1节 声明式编程: 抛弃控制?

到目前为止, 我们理所当然地认为源代码必须显式描述程序之中的计算顺序 (sequencing), 并且编程语言必须提供表达这种顺序的控制结构. 然而, 这种假设受到了声明式语言的质疑, 其在源代码之中大体将计算顺序留作隐式, 而依赖于编译器确定计算的正确顺序. 换言之, 声明式语言强调什么 (什么是要被计算的?) 而非如何 (如何将计算分解为基本步骤? 以什么顺序施行这些步骤?).

声明性方法的一个例子是诸如SQL这样的数据库查询语言: 查询描述了要从数据库里拉取什么记录; 如何搜索数据库则留给数据库管理系统确定. 其他的声明性编程范式包括逻辑编程 (Prolog, Datalog), 纯函数式编程 (Haskell, Agda), 以及数据流编程 (Simulink, Lustre). 诸如Verilog和VHDL这样的硬件描述语言本质上也是声明性的.

声明式编程于1970年代引入, 其目的在于简化编程和将编程从von Neumann风格之中解放出来, 如Backus (1978) 所言. 1980年代的焦点转移到了并行计算之上: 人们希望声明式语言比起标准的命令式语言并行执行起来更加容易, 这恰恰是因为前者给予了编译器在调度计算方面更大的灵活性. 自1990年代起, 声明式编程因其安全性和与形式验证的亲缘关系而受到认可.

声明式编程能否摆脱控制结构? 其能否将程序员从表达程序之中的控制的重担中解放出来呢? 本章试图在纯函数式编程的上下文之中回答这些问题, 通过检视三种表达力依次递增的小语言: XL, 一个电子表格语言; APP, 带有与值不同的函数的一个应用性语言; FUN, 将函数作为值的一个函数式语言.

第5.2节 XL: 表达式和电子表格

带有共享的表达式. 考虑以下算术表达式和等式的语言, 昵称XL:$$\begin{array}{rrcll}\text{表达式:}& e& ⩴& 0\left|1.2\right|3.1415|\dots & \text{常量}\\ & & |& x\left|y\right|z|\dots & \text{变量}\\ & & |& \mathrm{op}(e_1,\dots ,e_n)& \text{运算}\\ \text{程序:}& p& ⩴& \{x_1=e_1;\dots ;x_n=e_n\}& \text{等式的集合}\end{array}$$诸如$x+1$和$y\times z$这样的算术表达式是由常量和变量通过使用诸如$+,-,\times ,/$等运算构筑而成的. 程序是变量和表达式之间的等式的集合.

通过等式被绑定至表达式的变量使用捕获了计算共享的概念. 例如, 以下两个程序$$\begin{array}{rcl}{p}_1& =& \{x=2\times 3;y=x+x\}\\ p_2& =& \{x=2\times 3;y=2\times 3+2\times 3\}\end{array}$$能够计算出相同的结果 (其含义之后将会精确化), 但是$p_1$只会对于$2\times 3$进行一次求值, 之后在对于$x+x$的求值过程中共享结果$6$, 而$p_2$会对于$2\times 3$求值三次.

电子表格.

无环条件. 我们希望XL程序容易求值. 这意味着避免难以求解的等式, 例如$x=x^3-2x^2+2$. 我们还要走的远得多, 排除所有这样的等式$x=e$, 其中$e$依赖于$x$, 不论直接依赖还是通过其他等式间接依赖, 如以下例子所示:$$\begin{array}{c}\{x=x+1\}\\ \{x=y+1;y=x-1\}\end{array}$$换言之, 这些等式不能包含依赖循环. 这种无环条件成立当且仅当程序不只是能写作等式的集合, 而且可以写作等式的有序列表$$x_1=e_1;\dots ;x_n=e_n$$其中可以出现在$e_i$之中的变量只能是满足$j<i$的变量$x_j$.

电路和数据流.

程序求值.

第5.3节 APP: 表达式和用户定义的函数

第5.4节 FUN: 函数作为第一级值

第5.5节 上下文下的归约

第5.6节 深入阅读

第6章 延续和CPS变换

第6.1节 延续的概念

程序点的延续. 考虑程序执行过程中的一个点. 这个程序中该程序点的延续是在执行抵达该点之后还要执行的计算序列, 其是为了完成整个程序的执行过程.

第6.2节 指称语义回顾

指称语义由Christopher Strachey, Dana Scott, Christopher Wadsworth于1960年代后期引入, 其是以数学的精确定义程序的含义之方法. 指称语义以复合性的方式将数学对象与编程语言的每个句法元素 (表达式, 语句, 函数, ...) 联系起来.

例如, 一个牵涉变量的整数算术表达式$e$的含义可以被定义为从存储到整数的映射, 其中存储将整数与变量联系起来:

第6.3节 基于延续的指称语义

第6.4节 标签和跳转的指称语义

第6.5节 CPS变换

第6.6节 CPS变换的语义性质

第6.7节 深入阅读

第7章 延续编程

第8章 控制运算子

控制运算子是由某些函数式语言所提供的语言构造, 其允许表达式捕获延续, 将延续作为第一级值操纵, 以及之后重启延续.

控制运算子使得将高级控制结构 (异常, 回溯, 协作线程, 等等) 编写为库函数成为可能, 其可以在以直接风格写成的程序之中运用. 藉由控制运算子, 我们无需像我们在第7章所做的那样, 通过将程序改写为延续传递风格以使用用户所定义的高级控制结构.

第8.1节 Landin的J运算子

第8.2节 call-with-current-continuation (callcc)

最为知名的控制运算子或许是来自于Scheme语言的call-with-current-continuation, 其经常被缩略为call/cc或者callcc. 其允许一个表达式将其自身的延续以函数的形式捕获. 这个运算子在文献里以各种不同的名字出现:

第8.3节 使用callcc实现控制结构

第8.4节 callcc的语义

第8.5节 定界延续

第8.6节 定界延续运算子的语义

第8.7节 使用定界延续实现控制结构

第8.8节 定界延续的CPS变换

第8.9节 深入阅读

第9章 异常

第10章 用户定义作用的作用处理器

第11章 单子

第12章 代数作用

第13章 类型和作用系统

第14章 控制结构的Hoare逻辑

第15章 控制运算子的分离逻辑