解开Knuth的结:如何重组意大利面条代码？

Question

这个问题的灵感来自如何将流程图转换为实现？它询问了从算法上消除goto代码语句的方法.本科学论文描述了一般问题的答案.

我已经根据Knuth的算法X 的高级草图实现了一些代码.计算机编程的艺术描述了带有限制前缀的词典排列的生成(参见本草案的第16页).

这是上述算法的相应流程图.

这可能是一个非常聪明且非常有效的算法,但代码的结构似乎很难遵循.我最终使用了良好的旧式goto实现:

//Algorithm X;
1:
initialize();
2:
enter_level(k);
3:
set(a[k],q);
if(test() == ok) {
  if (k == n) {
    visit();
    goto 6;
  }
  goto 4;
}
goto 5;
4:
increase(k);
goto 2;
5:
increasev2(a[k]);
if (q != 0) {
  goto 3;
}
6:
decrease(k);
if (k==0) {
  goto 7;
}
set(p,u_k);
goto 5;
7:
return;

现在的问题是:如何可以将此代码进行重构,以消除所有的goto电话？

一个(虚假的)答案是建议"查阅引用的科学论文,并逐行跟踪" - 事实上,这肯定是一种可能性.但是这个问题是关于经验丰富的程序员一看到意大利面条代码就会立即看到的内容.

我对如何重构,一步一步,而不仅仅是代码感兴趣.

---

注意:

1. 基于其高级规范和goto跳转实际实现算法X是很简单的.实现黑盒功能initialize()等只需要一些额外的指令,但这些指令与代码的结构无关.在函数调用期间发生的事情并不重要,因为现在的重点是程序的流程.
2. 通常的辩论" GOTO仍然被认为是有害的吗？ "在这个问题上绝对无关紧要,在答案和评论中根本不应该解决.

---

相关:如何使用或完成意大利面条代码？

Answer 1

我之前在/sf/answers/2566296701/上勾画了 OP 的算法

找到了一篇更好的论文，讨论了如何生成结构化代码，同时准确保留原始控制流图：

WD Maurer，“广义结构化程序和循环树”，计算机编程科学，2007 年

我遵循了这个程序（在纸上，希望我做对了，凌晨 2:40 看起来还不错）。他的基本技巧是找到强连接区域（代码中的循环）；这些将成为循环；然后他通过删除一条边来打破这个循环；这最终成为循环反向链接（完成后恢复）。重复该过程，直到找不到更多的循环；剩下的本质上是一个带有已识别循环的结构化程序。正确地做到这一点是很棘手的；你确实需要一个自动化的程序。你的代码虽然很小，但仍然非常令人讨厌:-}

我在一处作弊了。Maurer 坚持认为前向 goto 是可以的，即使是在循环中间。如果你买了它，那么你就可以准确地保留 CFG。如果没有，您必须处理循环有两个或多个入口点的情况；你的算法有这样一个循环。我通过对循环进行编码，并编码一个等效的循环尾端片段来解决这个问题，该片段的作用类似于跳转到中间的第一次迭代，后面是循环本身。

我的符号有点有趣：大多数语言没有“block{...}”结构。[我编写的代码（参见简介）就是这样做的]。将其视为“执行一次迭代”循环：-}我假设块/循环具有循环退出并且循环继续。如果你没有这些，你可以用足够数量的 block{ ... } 和 exit_block@N 来模拟它们。

接受后编辑：从白天来看，我做得不对，我遗漏了 while 循环@3。我已经修补了这个；现在不再需要块构造了，因为我可以退出 whileloop@3 来实现相同的效果。实际上，代码读起来更好一些。

我留下了您的数字标签，即使不需要它们，以便于参考。

//Algorithm X;
1:
initialize();
2:
while (true) {
   enter_level(k);
   3: 
   while (true) {
      set(a[k],q);
      if (test() == ok) {
         if (k != n) exit_while@3;
         visit();
         decrease(k); // replicate logic at 6 to avoid jumping into middle of 5 loop
         if (k==0) return;
         set(p,u_k);
      }
      5:
      while (true) {
         increasev2(a[k]);
         if (q != 0) continue_while@3;
         6:
         decrease(k);
         if (k==0) return;
         set(p,u_k);
      } // while(true)@5
  } // while(true)@3
  4:
  increase(k);
} // while(true)@2

与我迄今为止看到的大多数其他答案不同，它的运行速度与原始答案相同（没有额外的标志或标志检查）。

@hatchet 的回答很有趣；a）同样快，b）他选择通过相同的技术处理两个入口循环，但他选择“另一个入口”作为循环顶部。他对标签 2 处的“enter_level(k)”操作做了类似的事情。

有趣的是，所有这些结构似乎对代码的可读性没有一点帮助。让人对“结构化程序”的全部意义产生疑问。也许精心设计的意大利面并没有那么糟糕:-}