解开 Knuth 的心结：如何重构意大利面条代码？

Question

这个问题的灵感来自 which asks about ways of algorithmically eliminating the goto statement from code. The to the general problem is described in this 科学论文。

我已经根据 Knuth 的 计算机编程艺术 中算法 X 的高级草图 实现了一些代码，描述了具有受限前缀的字典排列（参见此 draft 的第 16 页）。

这是上面算法对应的flow chart

这可能是一个非常聪明且非常高效的算法，但是结构该代码似乎很难遵循。我最终使用了很好的旧 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;

问题是：如何重构此代码以消除 all 个 goto 调用？

一个（伪造的）答案是对 "look up the cited scientific paper, and follow it line by line" 的建议 - 事实上，这当然是有可能的。但是这个问题是关于有经验的程序员一旦瞥了一眼这个 spaghetti code.

就会立即看到什么

我对如何重构感兴趣，一步一步，不仅仅是代码。

注：

根据高级规范和 goto 跳转，实际实现算法 X 很简单。实现黑盒函数 initialize() 等只需要一些额外的指令，但这些指令与代码的结构无关。函数调用期间发生了什么并不重要，因为现在的重点是程序的流程。
通常 "is GOTO still considered harmful?" 的辩论与这个问题完全无关，不应该 在答案和评论中解决。

相关：how to work with or complete the spaghetti code?

Answer 1

您可以使用很多变量来模拟 goto 的流程，以便与 if's 和 while's

一起使用

initialize();

enterLevel = true;
executeWhile = true;

do 
{

    if (enterLevel)
    {
        enter_level(k);
    }

    enterLevel = false;

    goto4 = false;
    goto5 = false;
    goto6 = false;

    set(a[k],q);
    if(test() == ok) 
    {
        if (k == n) 
        {
            visit();
            goto6 = true;
        }
        else
        {
            goto4 = true;
        }
    }
    else
    {
        goto5 = true;
    }

    if (goto4) 
    {
        increase(k);
        enterLevel = true;
    }
    else
    {
        do
        {
            if(goto5)
            {
                increasev2(a[k]);
                goto6 = goto5 = !(q != 0); // if (q != 0) { goto6 = goto5 = false; } else { goto6 = goto5 = true; }
            }
            if(goto6)
            {
                decrease(k);
                executeWhile = !(k==0); // if (k == 0) { executeWhile = false; } else { executeWhile = true; }
                set(p,u_k);
                goto5 = true;
            }
        } while (goto5 && executeWhile);
    }
} while (executeWhile);

这个版本是否比带 goto's 的版本好我不能说。

首先，我将所有标签完全分开。

然后我发现这里有 2 个循环：

1 - 
    * label 4 -> goto 2
    * label 5 -> goto 3.

两者都转到代码的顶部，但一个执行 enter_level(k) 而另一个不执行。这就是为什么 enterLevel var.

2 - 
    * label 6 -> goto 5. This goes up a little in the code, and then executes again.

在这个循环中，有两种情况会出现：

    * label 5 -> goto 3. The same as before, but now inside a nested loop
    * label 6 -> goto 7. The way out of the outer loop.

其他变量和 if 只是为了维护控制流。

是的，我可以使用一些休息时间（并且代码可以变得更短），但由于问题是关于 goto 的，我个人更倾向于不使用它们。

Answer 2

无需太多努力（而且风险不大），您可以快速减少 goto 和标签的数量。

1) 删除未在任何地方引用的标签（这将是标签 1:)

2) 查找只有通过 goto 才能输入的代码块，这些代码块在少数地方被调用。这些通常可以简单地分解出来。 4：可以通过将代码移动到它被调用的地方来处理，并且安全地完成，因为它唯一的出口是一个 goto。这也允许我们删除它上面的 goto 5，因为该代码将简单地跳转到 5:。 7：可以通过修改if语句来处理。此时我们有

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

我想就此打住。但如果继续，就会变成识别循环并用循环结构替换 goto 的问题。但是，由于代码的结构方式，进行这些更改的风险似乎要大得多。此外，您可能会以 breaks 和 continues 结束，这无论如何都是一种 gotos。我最终得到的是这个（如果没有一些非常严格的测试，我不会保证它的正确性）：

initialize();
enter_level(k);
while (true) {
  set(a[k],q);
  if(test() == ok) {
    if (k == n) {
      visit();
    } else {
      increase(k);
      enter_level(k);
      continue;
    }
  } else {
    increasev2(a[k]);
    if (q != 0) {
      continue; 
    }
  }
  while (true) {
    decrease(k);
    if (k!=0) {
      set(p,u_k);
      increasev2(a[k]);
      if (q != 0) {
        break; 
      }
    } else {
      return;
    }
  }
}

我做了 3：一个循环，和 6：一个内循环。我通过复制 5: 代码代替 goto 并用 break 替换 goto 3 摆脱了 goto 5。这使得制作更干净的循环变得更容易一些。 goto 6 通过使用 else 来修复。 goto 3 继续。

在此之后（如果您还有精力），您可以尝试将循环从 while(true) with continues 更改为 whiles with actual conditions。

最好先开发测试，然后进行一两个更改并测试。进行另一个更改，然后再次测试。如果你不这样做，很容易在早期犯下结构性错误，然后使后续步骤无效并迫使你重新开始。

Answer 3

在c++中算法可以写成：

void initialize() {}
void enter_level(int k) {}
void set(int x,int y) {}
bool test() { return true; }
void visit() {}
void increase(int k) {}
void increasev2(int k) {}
void decrease(int k) {}

void algorithm_x()
{
    int k{0};
    int a[] ={1,2,3,4,5};
    int q{0};
    bool ok{true};
    int n{0};
    int p{0};
    int u_k{0};

        //Algorithm X;
    lbl1:
        initialize();
    lbl2:
        enter_level(k);
    lbl3:
        set(a[k],q);
        if (test() == ok) {
            if (k == n) {
                visit();
                goto lbl6;
            }
            goto lbl4;
        }
        goto lbl5;
    lbl4:
        increase(k);
        goto lbl2;
    lbl5:
        increasev2(a[k]);
        if (q != 0) {
            goto lbl3;
        }
    lbl6:
        decrease(k);
        if (k==0) {
            goto lbl7;
        }
        set(p,u_k);
        goto lbl5;
    lbl7:
        return;

}

int main()
{
    algorithm_x();
    return 0;
}

假设我们不使用 break 语句，那么程序可能是：

void initialize() {}
void enter_level(int k) {}
void set(int x,int y) {}
bool test() { return true; }
void visit() {}
void increase(int k) {}
void increasev2(int k) {}
void decrease(int k) {}

void algorithm_x()
{
    int k{0};
    int a[] ={1,2,3,4,5};
    int q{0};
    bool ok{true};
    int n{0};
    int p{0};
    int u_k{0};

    bool skiptail{false};

    //Algorithm X;
    initialize();
    enter_level(k);
    while (true) {

        skiptail = false;
        set(a[k],q);
        if (test() == ok) {
            if (k == n) {
                visit();
                decrease(k);
                if (k==0) {
                    return;
                }
                set(p,u_k);
                while (true) {
                    increasev2(a[k]);
                    if (q != 0) {
                        //goto lbl3;
                        skiptail = true;
                    }
                    if (!skiptail) decrease(k);
                    if (!skiptail) if (k==0) {
                        return;
                    }
                    if (!skiptail) set(p,u_k);
                }
            }
            if (!skiptail) increase(k);
            if (!skiptail) enter_level(k);
            //goto lbl3;
            skiptail = true;
        }
        if (!skiptail) while (true) {
            increasev2(a[k]);
            if (q != 0) {
                //goto lbl3;
                skiptail = true;
            }
            if (!skiptail) decrease(k);
            if (!skiptail) if (k==0) {
                return;
            }
            if (!skiptail) set(p,u_k);
        }
        if (!skiptail) increase(k);
        if (!skiptail) enter_level(k);
        //goto lbl3;
        skiptail = true;
        if (!skiptail) while (true) {
            increasev2(a[k]);
            if (q != 0) {
                //goto lbl3;
                skiptail = true;
            }
            if (!skiptail) decrease(k);
            if (!skiptail) if (k==0) {
                return;
            }
            if (!skiptail) set(p,u_k);
        }
    }

}

int main()
{
    algorithm_x();
    return 0;
}

更改使用了以下算法：

删除未使用的标签。删除 lbl1
如果标签以 goto 结尾，则在使用该块的任何地方替换该块。删除 lbl4、lbl6、lbl7
如果一个标签 returns 到它自己然后将块放在 while (true) 中。删除底部 lbl5（lbl5 现在是独立的，可以在使用的地方替换）
如果块是自包含的，则在使用它的任何地方替换它。删除 lbl5
如果一个标签跟在另一个标签后面，则在块的末尾放置一个转到下一个标签，以便可以根据规则 2 替换它。删除 lbl2（可以 goto lbl3）
现在我们在整个代码中只剩下最后一个标签 goto。将goto lbl3替换为skiptail=true，将剩余的块放在while (true)块中，并设置剩余的语句来检查是否skiptail=false。删除 lbl3 并替换为 skiptail = false.

Answer 4

我从未使用过 goto，但这似乎是一个有趣的挑战，所以我尝试了自己的重构。

首先，检查代码并查看每个标签有多少语句 goto；牢记这一点以避免错误很重要。在您的示例中，没有任何内容导致 1，因此我们可以忽略它。

有时，我发现在控制流暗示时添加 goto 很有用。当我在事物之间移动代码时，它有助于跟踪顺序。

重构 goto 的最佳方法是从内向上或自下而上。

最后一条指令是7:return;，可以简单地移动到调用goto 7的地方。很简单。
接下来，我尝试查看哪些标签以 goto 结尾（无条件地）并直接出现在不同的 goto 之后。在这种情况下是 4；它可以移动到 2 的前面，在由哨兵控制的 if 内（为循环做准备）。（goto我第一点看到现在可以去掉2了。）
我接下来要做的是将 5 和 6 放入循环中。如果我错了，我可以原路返回。
此时我看到6会在3或者5之后执行，我也看到5可以执行3，所以我决定把3移到5之后，我加了一个变量so我可以第一次跳过 5。我在6的最后设置为true。
为了保证5在需要的时候可以直接跳转到6，我可以把3包在一个if语句里面，条件和5执行的相反。当我确实需要从5到3时，我可以在5里面改变条件，这样3就直接执行了。
此时我只有一个 goto，从 3 到 4。如果我将其更改为 break 我可以退出一个循环并到达在末尾。为了得到 4，我只是将所有内容（除了 1）都包装在一个循环中。

如果您正在使用 this trick 可以在不使用 goto 的情况下跳出嵌套循环，但在这种情况下没有必要这样做。

最后，我得到了这段代码（包含标签只是为了清楚起见）：

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

Answer 5

我之前在

草拟了一个 OP 算法

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

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

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

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

我的符号有点滑稽：大多数语言没有 "block{...}" 结构。 [我在（见生物）中编码的那个]。将此视为 "execute one iteration" 循环 :-} 我假设 blocks/loops 有循环退出并继续循环。如果你没有这些，你可以用足够数量的 block{ ... } 和 exit_block@N.

来模拟它们

接受后编辑：在今天看来，我没有做对，我遗漏了 while 循环@3。我已经修补了；现在不再需要块构造，因为我可以退出 while 循环@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) 他选择用相同的技术处理两个入口循环，但他选择 "other entry" 作为循环顶部。他对标签 2 的 "enter_level(k)" 操作做了类似的事情。

有趣的是，所有这些结构似乎并没有一点点帮助这段代码的可读性。让人想知道 "structured programs" 的全部要点。也许精心设计的意大利面并没有那么糟糕:-}

解开 Knuth 的心结：如何重构意大利面条代码？

Untying Knuth's knots: how to restructure spaghetti code?

c++

algorithm

refactoring

loops

software-design