暂无图片
暂无图片
暂无图片
暂无图片
暂无图片

结构化编程 | 编程范式

海人为记 2021-01-04
2158

结构化编程(Structured Programming)是由 Edsger Wybe Dijkstra
在 1968 年提出的一种编程范式。它采用子程序、块结构、循环等结构来编写程序,并限制 goto
的使用。

所谓的结构化编程,是相对于非结构化编程而言的。非结构化编程,这里就列举汇编语言,当哪块代码逻辑需要执行,就使用 goto
语句跳转到所需要的那块代码,这样很难预测代码的执行结构。

Dijkstra
很早以前就得出 编程的复杂度会使得一个小细节的错误也会造成程序出错 的结论并提出 数学推导方法 的解决方案。希望借鉴推导数学理论的方式来推导出程序的正确性。他在研究过程中发现了 goto
语句的某些用法会导致某个模块无法被递归拆分成更小的、可证明的单元,这会导致无法采用分解法来将大型问题进一步拆分成更小的、可证明的部分。而 goto
的效果和更简单的选择结构以及循环结构所得到的的结果是一致的。

在 1966 年,Corrado Böhm
Giuseppe Jacopini
发表的论文《Flow diagrams, turing machines and languages with only two formation rules》证明了只要一种编程语言使用顺序结构、选择结构和循环结构调整控制流程,就可以使用此种编程语言来表示可计算函数。这也成为 结构化程序理论,也称 Böhm-Jacopini 理论。该理论证明了可以构建可推导模块所需要的控制结构集与构建所有程序所需的控制结构集的最小集是等同的。这和 Dijkstra
的想法一致。

Dijkstra
在 1968 年发表的著名文章 《Go To Statement Considered Harmful》, 提出了应该从所有 “高级” 编程语言中废除 goto
语句,因为它使分析和验证程序正确性的任务变得复杂,并提出了 用结构化编程 来替代。并且在这篇文章中概述了对这三种控制结构的证明。

  • 顺序结构中,通过枚举法对序列中的每个输入,追踪其对应的输出值的变化,从而证明程序的正确性。
  • 选择结构中,通过枚举法证明分支结构中每条路径的正确性。如果每条路径都产生适当的数学结果,就可证明选择结构的正确性。
  • 选择结构中,使用数学归纳法证明。先是用枚举法证明循环 1 次的正确性,在证明第 N 次循环是正确的,那么第 N+1 次循环就是正确的。最后还要用枚举法证明循环结构的起始与结束条件的正确性。

此概念理论上可以由结构化程序理论所证明,也可以使用具有控制结构的编程语言来实现结构化编程。

但是,欧几里得结构没有建立起来,程序员也不会为每个小函数书写冗长复杂的证明过程。当然,数学推导证明并不是证明结构化编程正确性的唯一手段,还可以采用科学证明法,它与数学证明方法有根本性的不同,数学理论可被证明,而科学理论和科学定律通常是无法被证明,即科学结论无法证伪,则认为在当下是正确的。

因此,使用科学证明法,先将一段程序递归讲解为一系列可证明的小函数,然后再编写相关的测试来试图证明这些函数是错误的。如果测试无法证伪这些函数,那就认为这些函数是正确的,进而推导整个程序是正确的。

这样一来,一个大型问题可拆分为一系列高级函数的组合,而高级函数各自又可以继续被拆分为一系列低级函数,每个被拆分出来的函数可以用结构化编程范式来书写,如此无限递归。以此为理论基础,在 20 世纪 70 年代晚期到 80 年代中期出现了结构化分析与结构化设计工作。通过这些技巧,程序员可以将大型系统设计拆分成模块和组件,而模块和组件最终拆分为更小的、可证明的函数。

用任何编程语言都可以进行结构化编程,不过一般较常使用过程式的编程语言,而原先缺乏程序结构的高级语言也都已加入结构化编程,随着编程语言的演进,goto
语句的重要性越来越小,最终甚至消失了。如今大部分的现代语言中都已经没有了 goto
语句,编程语言基本上都已经禁止了不受限制的 goto
语句,还支持 goto
关键词的编程语言通常也限制了 go to
的目标不能超出当前函数范围,使得非结构化编程更加困难。

结论

结构化编程范式中最有价值的地方就是赋予了创造可证伪程序单元的能力,这也是现代编程语言一般不支持无限制的 goto
语句的原因。

无论在哪一层面上,从最小的函数到最大组件,软件开发的过程都和科学援救非常类似,它们都是由证伪驱动的。软件开发者需要定义可以方便地进行证伪的模块、组件以及服务。为了达到这个目的,他们需要将类似结构化编程的限制方法应用在更高的层面上。

总归一句话:结构化编程 是对程序控制权的直接转移进行了限制和规范。



你点的每个赞,我都认真当成了喜欢




文章转载自海人为记,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论