解开Knuth的结：如何重组意大利面条码？ [英] Untying Knuth's knots: how to restructure spaghetti code?

问题描述

此问题的灵感来自如何将流程图转换为实施？，其中提出了如何在算法上消除 goto 语句。 对一般问题的回答在这篇科学论文。

我已经实现了一些代码，在高级草图 X来自Knuth的 艺术描述具有受限前缀的词典排列的生成（参见 draft ）。

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

这可能是一个非常聪明和非常高效的算法，但是代码的结构似乎具有挑战性。我最终使用了好的旧 goto -style实现：

  /算法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. 直接实际执行Algorithm X基于其高级规范和 goto 跳转。实现黑盒子函数 initialize（）等只需要几个额外的指令，但那些与代码的结构无关。在函数调用期间发生的情况并不重要，因为现在的重点是程序的流程。


2. 通常的争论是is GOTO仍然被认为有害吗？对于这个问题绝对不相关，应该不会在




---





相关：如何使用或完成意粉代码？

解决方案

我之前在 http：// stackoverflow中为草图绘制了一个算法.com / a / 36661381/120163





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





WD Maurer，Generalized structured programs and loop trees，Science of Computer Programming，2007





我遵循的程序（在纸上，希望我做到了，看起来上午2:40）。他的基本诀窍是找到强连接区域（代码中的循环）;这些将成为循环;然后他通过删除边缘来打破这个周期;这最终变成一个循环反向链接（当他完成时恢复）。重复该过程，直到不再发现循环;剩下的基本上是一个带有确定循环的结构化程序。这是很难做到这一点;你真的需要一个自动化程序。你的位代码，虽然很小，仍然很讨厌： - }





我在一个地方骗了。 Maurer坚持向前gotos是好的，甚至进入循环的中间。如果你买，那么你可以保留CFG。如果没有，你必须处理一个循环有两个或多个入口点的情况;你的算法有这样一个循环。我通过编码循环来解决这个问题，并编码一个循环尾端片段等效，它像跳入中间的第一次迭代，后面是循环本身。





我的符号有点有趣：大多数语言没有block {...}结构。 [我编码的一个（见生物）]。想想这是一个执行一个迭代循环： - }我假设块/循环有循环退出，循环继续。如果你没有这些，你可以模拟他们足够的数量只是块{...}和exit_block @ N。





编辑后接受： ，我没有做对，我离开了while循环@ 3。我已经打补丁了;对块结构的需要现在消失了，因为我可以退出while循环@ 3来实现相同的效果。





我留下了你的数字标签，即使他们不需要，为了更容易参考。

  //算法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）; //在6处复制逻辑以避免跳入5循环中间
 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）操作的操作。





有趣的是，所有这些结构化似乎并没有帮助这个代码的可读性位。令人惊讶的是结构化程序的整体。也许设计良好的意大利面条并不是那么糟糕： - }




This question was inspired by How to transform a flow chart into an implementation? which asks about ways of algorithmically eliminating the goto statement from code. The answer to the general problem is described in this scientific paper.

I have implemented some code following the high-level sketch of Algorithm X from Knuth's The art of computer programming describing the generation of Lexicographic permutations with restricted prefixes (see p. 16 of this draft).

This is the corresponding flow chart of the above algorithm.

This might be a very clever and very efficient algorithm, but the structure of the code seems to be challenging to follow. I ended up using the good old goto-style implementation:

//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;

The question is: how can this code be refactored to eliminate all the goto calls?

One (bogus) answer is a suggestion to "look up the cited scientific paper, and follow it line by line" - indeed, that is certainly a possibility. But this question is about what experienced programmers see instantly once they give a glance at this spaghetti code.

I am interested in the how of refactoring, step by step, more than just the code.

---

Note:

1. It is straightforward to actually implement Algorithm X based on its high-level specification and goto jumps. Implementing the black-box functions initialize() etc. would take only a few extra instructions, but those are irrelevant regarding the structure of the code. It is not important what is happening during the function calls, as the focus is now on the flow of the program.
2. The usual debate of "is GOTO still considered harmful?" is absolutely irrelevant regarding this question, and should not be addressed at all in the answers and in the comments.

---

Related: how to work with or complete the spaghetti code?

解决方案

I sketched an algorithm for OP earlier at http://stackoverflow.com/a/36661381/120163

Found a better paper that discusses how to generate structured code while preserving the original control flow graph exactly:

W.D Maurer, "Generalized structured programs and loop trees", Science of Computer Programming, 2007

I followed that procedure (on paper, hope I did it right, looks OK at 2:40 am). His basic trick is to find strongly connected regions (cycles in the code); these will become loops; He then breaks that cycle by deleting an edge; this eventually becomes a loop backlink (restored when he is complete). The process is repeated until no more cycles can be found; what is left is essentially a structured program with identified loops. It is tricky to do this right; you really need an automated procedure. Your bit of code, although small, is still pretty nasty :-}

I cheated in one place. Maurer insists that forward gotos are OK, even into the middle of loop. If you buy that, then you can preserve the CFG exactly. If not, you have to handle the case where a loop has two or more entry points; your algorithm has such a loop. I solved the problem by coding the loop, and coding a loop-tail-end-fragment equivalent that acts like the first iteration of jump-into-the-middle, which is followed by the loop itself.

My notation is a little funny: most languages don't have "block{...}" constructs. [The one I code in (see bio) does]. Think of this as being an "execute one iteration" loop :-} I assume that blocks/loops have loop exits and loop continues. If you dont have these, you can simulate them with sufficient quantity of just block{ ... } and exit_block@N.

EDIT after accepted: In the light of day, I didn't do it right, I left out the of the while loop@3. I've patched that; the need for the block construct now goes away because I can exit the while loop@3 to achieve the same affect. Actually, the code reads a little better.

I left your numeric labels in, even where they aren't needed, for easier reference.

//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

Unlike most other answers I've seen so far, this runs at the same speed as the original (no extra flags or flag checks).

@hatchet's answer is interesting; a) it is equally fast, b) he chose to handle the two entry loop by the same technique, but he chose the "other entry" as the loop top. He did something similar with the "enter_level(k)" operation at label 2.

It is interesting that all this structuring doesn't seem to help readability of this code one bit. Makes one wonder about the whole point of "structured programs". Maybe well-designed spaghetti isn't so bad :-}

这篇关于解开Knuth的结：如何重组意大利面条码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！