3

根据 Böhm-Jacopini 定理,可以仅使用三个语句来编写算法:

  • 顺序
  • 选择
  • 迭代

很多老师都认为定理是一种信仰行为,他们教导不要使用(goto、jump、break、multiple return 等),因为这些指令是邪恶的。

但是当我要求解释时,没有人能够提供定理的证明。

我个人不认为这个定理是错误的,但我认为它在现实世界中的适用性并不总是更好的选择。

所以我做了一个小小的搜索,这些是我的疑问:

  1. 该定理已在流程图结构上进行归纳证明,但它真的适用于计算机程序吗?
    根据维基百科,“Böhm 和 Jacopini 的作为程序转换算法并不真正实用,因此为在这个方向上的进一步研究打开了大门”。

  2. 定理的一个结果证明每个“goto”都可以通过归纳转化为选择或迭代,但效率呢?我找不到任何证据表明可以重写每个算法以保持相同的性能。

  3. 递归,递归算法真的可以只使用序列、选择和迭代来编写吗?我知道一些递归算法可以优化为循环(想想尾递归),但真的可以适用于所有人吗?

  4. 干净的代码,我知道滥用跳转会产生可怕的代码,但我认为在某些情况下正确使用循环中的中断可以提高代码的可读性。

样本:

n = 0;
while (n < 1000 || (cond1 && cond2) || (cond3 && cond4) || (cond5 && cond6)) 
{  
   n++;  
   //The rest of code  
}   

可以改写为:

for (n = 0; n < 1000; n++)
{
   if (cond1 && cond2) break;
   elseif (cond2 && cond3) break;
   elseif (cond4 && cond5) break;
   elseif (cond6 && cond7) break;
   //The rest of code
}

就我个人而言,我认为这个定理并不是为了编写更好的代码而创建的,干净的代码必须遵循这个定理的想法已经因为一个奇怪的主观原因传播到了世界上。

  1. 我发现了这篇有趣的文章:https : //www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf 我认为这证明了不能强迫真正的程序遵循 Jaopini 定理。
    你有同样的结论吗?

总结这个问题,我需要知道一个只使用(序列、选择和迭代)的程序是否真的比任何其他使用不同语句的程序更好,以及是否有证明或者是否都是主观的。

4

4 回答 4

3

该定理已在流程图结构上进行归纳证明,但它真的适用于计算机程序吗?根据维基百科,“Böhm 和 Jacopini 的作为程序转换算法并不真正实用,因此为在这个方向上的进一步研究打开了大门”。

他们给出的操作和结构很容易被证明能够复制图灵机的功能。因此,它是一个图灵等效的计算系统。根据 Church-Turing 的论点,这被认为是我们可以做的尽可能多的计算:goto不会添加任何不可能的东西。

定理的一个结果证明每个“goto”都可以通过归纳转化为选择或迭代,但效率呢?我找不到任何证据表明可以重写每个算法以保持相同的性能。

对于许多不使用计算的算法,性能很可能会更差goto。您当然可以证明这是针对特定问题的情况。这是否会改变渐近复杂性是另一个问题,但据我所知,Bohm 和 Jacopini 与此无关。

递归,递归算法真的可以只使用序列、选择和迭代来编写吗?我知道一些递归算法可以优化为循环(想想尾递归),但真的可以适用于所有人吗?

由于 Bohm 和 Jacopini 的系统是图灵等价的,那么你是对的,递归没有增加新的力量。它肯定会增加可读性。

于 2016-11-01T16:29:35.823 回答
3

根据 Böhm-Jacopini 定理,可以仅使用三个语句来编写算法:

  • 顺序
  • 选择
  • 迭代

While语言具有以下结构:

  1. 任务,V := E
  2. 空程序,skip
  3. 顺序, S1;S2
  4. 选择, if B then S1 [elsif Si] else Sn fi, 和
  5. 迭代。 while B do S od

你省略了赋值 and skip,它是一个中性元素,就像算术中的 0 一样。还有其他结构我省略了。这些与过程抽象有关,它命名语句序列,即函数和过程。但我现在不想扩展太多。

我发现了这篇有趣的文章:https ://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf我认为这证明了不能强迫真正的程序遵循 Jacopini 定理。你有同样的结论吗?

Kozen是一位非常好的作者,他严谨而清晰。

Kozen 在证明 Böhm-Jacopini 定理时表明了命题演算的局限性。原始文章使用谓词演算。他使用 1960 年代不可用的技术给出了该定理的正确证明。问题的出现是因为转换使用了变量,而这在命题演算中是无法处理的。存在其他转换,它使用带中断的循环而不是While语言。所有这些讨论GOTO现在都很好理解了。这篇文章很有趣,因为它是一个关于如何在一个众所周知的老问题中使用新技术的例子。

您可以使用 Böhm-Jacopini 定理,因为它产生了一个等效的程序。

我个人不认为这个定理是错误的,但我认为它在现实世界中的适用性并不总是更好的选择。

该结果支持结构化编程。但是你不应该使用它,因为你不应该使用数据流图来设计程序。你甚至不应该使用While伪代码来设计程序。

最佳实践是使用更足以表示您要解决的问题的抽象规范语言。证明您的解决方案,然后编写可以转换为您的编程语言代码的文档。这就是文学编程背后的理念。准确地解释你对问题领域的了解,陈述你如何用抽象规范语言表示你的问题,并将其系统地转换为编程语言。所有的解释都应该用自然语言和数学公式,并且代码片段应该是可分离的以产生程序代码。为此,您可以使用 CWeb 和 LaTeX 之类的程序。

新的声明性语言非常接近规范语言,但最好坚持上述建议。尽管这些语言推断类型,但有时数据结构中的细节会分散设计过程的注意力。稍后应详细说明类型,以便以静态类型的编程语言实现程序。这是一种更好的编程习惯。

于 2019-04-05T17:10:28.473 回答
2

在此处输入图像描述

任何看起来像 Type 1 /2 /3 的程序都可以转换为

在此处输入图像描述

于 2019-01-23T23:03:25.247 回答
0

我个人认为这个定理并不是为了编写更好的代码而创建的,

好吧,从来没有。定理没有被创造出来(定理不仅仅是被创造出来的)。该定理被发现是一种计算模型,可以证明 GOTO 语句不是编码算法的绝对必要条件。

我们需要了解该定理首次提出的背景。当时,程序员相当野蛮地使用 GOTO,而且没有结构,他们坚信 GOTO 语句是必不可少的。

该定理证明情况并非如此。现在,该定理并不意味着由它构建的程序必然是优越的(因为在某些情况下,偏离提议的结构是更好/更优雅/有效的方法。)

那个定理在当时起到了钉在棺材上的作用,即 GOTO 语句是创建复杂程序的必要条件(它们不是。)

该定理的最大好处是它提供了一种新的(在一般情况下,更好的)方法来制定、分析和编码算法。

出于一个奇怪的主观原因,干净的代码必须遵循这个定理的想法已经传播到世界各地。

在一般情况下,这是正确的,并且没有主观原因。该定理是结构化编程的基础,总的来说,这比它的前任替代方案要好得多。

我再说一遍,关于这个定理的全部内容是对于一般情况

  1. 您不需要依赖 GOTO 进行时序逻辑
  2. 时序逻辑可以用这种方法统一描述
  3. 可以对由此产生的时序逻辑编码进行形式化分析(尝试使用 GOTO 汤。)

客观地说,这就是应该如何看待这个定理的。

于 2021-01-01T01:03:52.697 回答