族谱网 头条 人物百科

结构化程序理论

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:362
转发:0
评论:0
起源及变体一般认为此理论最早是在1966年科拉多·伯姆(英语:CorradoBöhm)及朱塞佩·贾可皮尼(GiuseppeJacopini)的论文中提出。大卫&m

起源及变体

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

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

单一while循环的大众定理版本

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

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

p:=1;whilep>0dobeginifp=1thenbegin進行流程圖的步驟1;p:=流程圖的步驟1之後的步驟編號(若沒有後續步驟,數值為0);end;ifp=2thenbegin進行流程圖的步驟2;p:=流程圖的步驟2之後的步驟編號(若沒有後續步驟,數值為0);end;...ifp=nthenbegin進行流程圖的步驟n;p:=流程圖的步驟n之後的步驟編號(若沒有後續步驟,數值為0);end;end.

伯姆及贾可皮尼的证明

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

相关的讨论及研究

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

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

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

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

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

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

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

直接跳跃到循环中

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

直接跳出一个判断分支

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

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

在Cobol上的应用

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

找出程序中的基础方块(英语:basic block)。

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

将程序分区为基础方块。

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

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

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

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

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

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

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

相关条目

结构化程序设计

图灵完全


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱

相关资料

展开
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 结构化编程
底层的结构化程序设计结构化的程序是以一些简单、有层次的程序流程架构所组成,可分为循序(sequence)、选择(selection)及重复(repetition)。循序是指程序正常的运行方式,运行完一个指令后,运行后面的指令。选择是依程序的状态,选择数段程序中的一个来运行,一般会使用if..then..else..endif或switch、case等关系字来识别。重复是指一直运行某一段程序,直到满足特定条件,或是一集合体中的所有元素均已处理过,一般会使用while、repeat、for或do..until等关键字识别。一般会建议每个循环只能有一个进入点(戴克斯特拉的结构化程序设计要求每个循环只能有一个进入点及一个结束点,有些编程语言仍有此规定)。若一个编程语言的语法允许用成对的关键字包围一段程序,形成一个结构,这种编程语言称为有“区块结构”(block-structured),这类的结构包...
· 结构化分析
目的结构化分析在1980年代起开始广为使用。结构化分析包括将系统概念转换为用数据及控制的来表示,也就是转换为数据流程图。数据流程图中的程序以泡泡来表示,因此也称为“泡泡图”。不过完整的数据流程图中可能有许多的“泡泡”,使得很难去追踪数据流动的情形。此时可以先定义外界需要系统回应的事件,每一个事件指定一个泡泡,当系统定义完成后,再将事件的泡泡和回应的程序的泡泡相连接。也可以将程序对应泡泡加以分组,组合成较高级的程序。数据字典用来描述数据和指令的流动,而用程序规格来描述交易或数据转换的相关信息。许多著名的分析方式都和结构化分析(SA)及结构化设计(SD)有关,包括结构图、数据流程图及数据模型图等。许多程序设计方法学也结合了结构化分析及结构化设计,包括结构化系统分析及设计方法(SSADM)及结构化分析及设计技术(英语:StructuredAnalysisandDesignTechnique)(S...
· 程序错误
史上的第一个隐错1947年9月9日,葛丽丝·霍普(GraceHopper)发现了第一个电脑上的bug。当在MarkII计算机上工作时,整个团队都搞不清楚为什么电脑不能正常运作了。经过大家的深度挖掘,发现原来是一只飞蛾意外飞入了一台电脑内部而引起的故障(如图所示)。这个团队把错误解除了,并在日记本中记录下了这一事件。也因此,人们逐渐开始用“Bug”(原意为“虫子”)来称呼计算机中的隐错。现在在华盛顿的美国国家历史博物馆中还可以看到这个遗稿。Bug的管理与一些常见的名词典型错误历史(GNUClasspathproject数据)。由用户提交的错误是“未确认”(unconfirmed)的,一旦该错误由开发人员重现,即为“已确认”(confirmed)错误。此后已确认的错误会“解决”(fixed)。其他类别的错误(无法重现、不予解决等)通常并不多见。处理进度处理方式Severity:Bug造成的严重...
· 程序员
工作范围系统分析与设计(SystemsAnalysisandDesign)代码撰写(Coding)测试与除错(TestingandDebugging)撰写技术文件(WriteSpecification)相关职业系统管理员(SA)系统设计师(SD)数据库管理员(DBA)应用分析师(AA)技术支持(TS)相关戏称攻城狮程序猿码农(一般用来自嘲为像农民高强度一样的编码工作者)工程师打字员
· 程序设计
设计工具开发环境图像展览早期IBM402会计电脑的程序是用改变线路连接的方式来撰写GANT程序设计软件相关条目中文编程程序软件程序设计语言程序设计实践程序设计方法学软件开发软件设计模式

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信