造价通

反馈
取消

热门搜词

造价通

取消 发送 反馈意见

结构化程序理论起源及变体

2022/07/16228 作者:佚名
导读:一般认为此理论最早是在1966年科拉多·伯姆及朱塞佩·贾可皮尼(Giuseppe Jacopini)的论文中提出 。大卫·哈雷尔在1980年曾提到这篇论文广受认可,尤其在结构化程序理论的支持者中。哈雷尔也提到“由于其论文比较技术的风格,因此较常被引用,较少人真正详读过内容。”,在看了1980年以前的大量论文后,哈雷尔认为结构化程序理论被错误诠释为一个结果较简单的大众定理(folk theorem)

一般认为此理论最早是在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.

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

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

*文章为作者独立观点,不代表造价通立场,除来源是“造价通”外。
关注微信公众号造价通(zjtcn_Largedata),获取建设行业第一手资讯

热门推荐

相关阅读