结构化程序理论在Cobol上的应用

1980年代IBM研究员哈伦·米尔斯管理COBOL构建设备（COBOL Structuring Facility）的开发时，将程序的结构化算法应用到COBOL语言中。米尔斯的转换方式包括以下的步骤。

1. 找出程序中的基础方块。

2. 将每一个方块的起始点指定不重复的编号，将每个方块的结束点用所连接方块起始点的编号来标示，程序结束点编号指定为0，程序起始点编号指定为1。

3. 将程序分区为基础方块。

4. 若某方块的起始点只对应一个方块的结束点，将二个方块合并。

5. 定义程序中的一个新的变量，假设为L。

6. 针对其他没有合并的结束点，增加一行指令，将L设置为该结束点的编号。

7. 将所有基础方块合并成一个选择执行指令，依L的数值运行对应的程序。

8. 创建一个循环，若L不为0，继续运行循环。

9. 创建程序，一开始将L设为1，并开始循环。

注：将一些选择分支转变为子程序可以改进所得结果。2100433B

因为伯姆及贾可皮尼建构的方式过于复杂，因此此证明没有回答结构化编程是否适用于软件开发的问题，而是引发了后续相关的讨论及争议。在两年之后的1968年，艾兹赫尔·戴克斯特拉就提出著名的“GOTO有害论”。

有些学者试图使伯姆及贾可皮尼的研究结果更加纯粹，因为其论文中没有用到从循环中间跳出循环的break及return指令，因此学者认为这是不好的实现方式，学者们鼓励每一个循环都只能有唯一的结束点，这种设计观点集成到1968至1969年开发的Pascal中。从1969年到1990年代中期，学校常用Pascal来讲授编程语言入门课程。

爱德华·尤登注意到1970年代时在有关是否用自动化方式改写非结构化程序一事，有二元对立的观点，反对者认为需要以结构化程序的方式去思考，而非一味改写，而赞成者的论点是这类的修改实际上可以改善大部分已有的程序。最早提出自动化改写程序概念的有1971年Edward Ashcroft及Zohar Manna的论文。

直接应用伯姆及贾可皮尼定理可能要引入额外的局部变量，也可能产生代码重复的问题，后者也称为loop and a half problem。Pascal受到这些问题的影响，依照埃里克·S·罗伯茨的实验研究，学习程序设计的学生难以用Pascal设计正确代码来解决简单的问题，其中甚至包括从数组中找寻一个元素的问题。一篇1980年由Henry Shapiro进行，而后被被罗伯茨引用的研究指出，若只用Pascal提出的流程控制指令，只有20%的人的解答是正确的，但若允许在循环中直接加入return的话，所有人都写出了正确的答案。

S. Rao Kosaraju在1973年证明只要允许可以从任意深度循环中多层次跳出，就可以将程序转换成结构化编程，而不用引入额外的变量。而且Kosaraju证明了存在一个严格的程序层次结构（现在称为Kosaraju层次结构），针对任一整数n，存在一个程序，其中包括深度n的多层次跳出，而且在不引入额外变量的条件下，无法用深度小于n的跳出来实现。Kosaraju称这种多层次跳出结构源于BLISS语言。BLISS语言中的多层次跳出形式为leave label，实际上在BLISS-11版本中才引入到BLISS中，原始的BLISS只有单一层次的跳出。BLISS语言家族不提供无限制的跳转指令，Java语言后来也引入类似BLISS语言中的多层次跳出指令。

Kosaraju的论文中有另一个较简单的结论：若程序可以在不用额外变量（及多层次的跳出）下化约为结构化程序，其充份必要条件是程序中没有一个循环有二个或二个以上的结束点。简单来说，此处Kosaraju定义的化约是指用相同的“基本动作”及判断，计算相同的函数，但是可能用不同的控制流程（此处的化约比伯姆及贾可皮尼定理中提及的范围要窄）。受到这个结论的启发，Thomas J. McCabe在他引入循环复杂度的论文中的第四部分，描述了对应非结构化程序控制流图（CFG）的Kuratowski定理。使控制流图变得无法结构化的最小子图是：

• 从循环测试以外的地方跳出循环

• 直接跳跃到循环中

• 直接跳跃到一个判断分支之中

• 直接跳出一个判断分支

McCabe发现上述这些子图不是彼此独立的，程序无法结构化的充份必要条件是控制流图中有子图有上述四种条件中的三种（或三种以上）。McCabe也发现若非结构化的程序中包括其中四个条件中的一个，它一定还会包含另一个。这也是非结构化的程序流程会纠结到类似意大利面的原因。McCabe也提供一个量化方式，说明一个程序和理想结构化程序之间的距离，并称其为本质复杂度。

到1990年为止，学者们提出许多消除既有程序中跳转指令，但又维持大部分控制架构的方式，也提出许多标示程序等价的方式，这些方式比简单的图灵等价要严格，以免造成类似上述大众定理般的转换结果。这些等价标示的严格程度指定了所需控制流结构的最小集合。1998年Lyle Ramshaw在ACM期刊的论文进行了相关的调查，也提出了自己的方法 。Ramshaw的算法也用在Java反编译器中，因为Java虚拟机有分支指令，以位移来表示分支跳转的目标，但高级的Java语言只有多层次的break及continue指令。Ammarguellat在1992年提出一种转换方式，回到强制单一结束点的作法。

一般认为此理论最早是在1966年科拉多·伯姆及朱塞佩·贾可皮尼（Giuseppe Jacopini）的论文中提出 。大卫·哈雷尔在1980年曾提到这篇论文广受认可，尤其在结构化程序理论的支持者中。哈雷尔也提到“由于其论文比较技术的风格，因此较常被引用，较少人真正详读过内容。”，在看了1980年以前的大量论文后，哈雷尔认为结构化程序理论被错误诠释为一个结果较简单的大众定理（folk theorem），而此结果可以追溯到冯·诺依曼及斯蒂芬·科尔·克莱尼现代计算理论的论文。

哈雷尔也提到较通用的“结构化程序理论”名称是在1970年代初由哈伦·米尔斯提出。

结构化程序理论单一while循环的大众定理版本

此版本的定理将原来定理中的程控流程改为一个while循环，模拟在原来非结构化的程序中，程序计数器走过所有可能标记（流程图方块）的情形。哈雷尔将此版大众定理的源头追溯到两篇论文，一篇是1946年描述冯·诺伊曼结构，用单一while循环说明程序计数器的运作原理，哈雷尔也注意到大众定理中用到的单一循环基本上可以提供冯·诺伊曼式电脑运行流程的操作语义。。另一篇更早期的论文则是斯蒂芬·科尔·克莱尼1936年的正规形式定理（Kleene's T predicate）论文。

高德纳批评这种转换后的结果类似以下的伪代码，重点是在此转换中完全破坏了原程序的结构。Bruce Ian Mills也有类似的看法：“块状结构的精神是其风格，不是使用的语言。利用模拟冯·诺伊曼结构的方式，可以将任何一个面条式代码转换为块状结构的语言，但它面条式代码的本质没有改变。”

p:=1;
whilep>0dobegin
ifp=1thenbegin
进行流程图的步骤1;
p:=流程图的步骤1之后的步骤编号（若没有后续步骤，数值为0）;
end;
ifp=2thenbegin
进行流程图的步骤2;
p:=流程图的步骤2之后的步骤编号（若没有后续步骤，数值为0）;
end;
...
ifp=nthenbegin
进行流程图的步骤n;
p:=进行流程图的步骤n之后的步骤编号（若没有后续步骤，数值为0）;
end;
end.

结构化程序理论伯姆及贾可皮尼的证明

伯姆及贾可皮尼的证明是以流桯图的结构归纳法为基础，由于用到图模式匹配，其证明在实务上不能当作是程序转换算法，因此开创了此一领域的研究。

三个调整控制流程的方式为

1. 运行一个子程序，然后运行下一个（顺序）

2. 依照布尔变量的结果，决定运行二段子程序中的一段（选择）

3. 重复运行某子程序，直到特定布尔变量为真为止（循环）

匹配上述条件的结构图需要额外的比特变量（在原始证明中放在额外的整数变量中），以纪录原来程序运行到的位置，此种建构法是以伯姆的编程语言P′′为基础。

结构化课程理论内容简介

《结构化课程理论》是一部致力于课程与教学理论建设的专著，以吉登斯的结构化理论为方法论，以“课程结构与课程行动之间关系”为问题域，以构建结构化课程理论为目的。《结构化课程理论》共分三编：第一编，导论，主要对结构化课程研究的问题、方法和基本结论做一简要介绍。第二编，结构化课程原理。第三编，结构化课程原理的应用，具体分析了“师定课程向经验课程的转化过程”和“教师专业发展的实践模式”。

结构化课程理论作者简介

杨道宇，男，汉族，1978年生，河南商丘人，现为渤海大学讲师，硕士生导师，教育学博士，主要研究方向为课程哲学。2004—2010年在哈尔滨师范大学课程与教学论专业攻读硕士、博士。2010年进入北京师范大学教育学博士后流动站工作。近三年来，在《比较教育研究》、《中国教育学刊》、《教育与经济》、《教育研究与实验》等国家核心期刊上发表论文20余篇，出版专著2部，主持省部级课题3项。

结构化程序设计采用自顶向下、逐步求精的设计方法，各个模块通过“顺序、选择、循环”的控制结构进行连接，并且只有一个入口、一个出口。

结构化程序设计的原则可表示为：程序=(算法) (数据结构)。

算法是一个独立的整体，数据结构(包含数据类型与数据)也是一个独立的整体。两者分开设计，以算法(函数或过程)为主。

随着计算机技术的发展，软件工程师越来越注重于系统整体关系的表述，于是出现了数据模型技术(把数据结构与算法看做一个独立功能模块)，这便是面向对象程序设计的雏形。

结构化程序设计顺序结构

顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的。

结构化程序设计选择结构

选择结构表示程序的处理步骤出现了分支，它需要根据某一特定的条件选择其中的一个分支执行。选择结构有单选择、双选择和多选择三种形式。

结构化程序设计循环结构

循环结构表示程序反复执行某个或某些操作，直到某条件为假（或为真）时才可终止循环。在循环结构中最主要的是：什么情况下执行循环？哪些操作需要循环执行？循环结构的基本形式有两种：当型循环和直到型循环。

当型循环：表示先判断条件，当满足给定的条件时执行循环体，并且在循环终端处流程自动返回到循环入口；如果条件不满足，则退出循环体直接到达流程出口处。因为是"当条件满足时执行循环"，即先判断后执行，所以称为当型循环。

直到型循环：表示从结构入口处直接执行循环体，在循环终端处判断条件，如果条件不满足，返回入口处继续执行循环体，直到条件为真时再退出循环到达流程出口处，是先执行后判断。因为是"直到条件为真时为止"，所以称为直到型循环。