是否有可能永远消除goto语句？

Question

虽然使用goto语句制作所有内容很容易（例如IL），但我想知道是否也可以使用高级表达式和语句-比如Java中支持的一切-消除所有goto语句。

或者说，我正在寻找“重写规则”，它们始终有效，而不管goto语句的创建方式如何。

这主要是一个理论问题，纯粹出于兴趣，而不是好/坏的做法。

我想到的明显解决方案是使用类似于此的东西：

while (true)
{
    switch (state) {
       case [label]: // here's where all your goto's will be
          state = [label];
          continue;
       default:
          // here's the rest of the program.
    }
}

虽然这可能有效，并符合我的“正式”问题，但我一点也不喜欢我的解决方案。首先，它非常丑陋，其次，它基本上将goto包装到一个开关中，与goto完全相同。

那么，有更好的解决方案吗？

---

更新1

由于很多人认为这个问题“过于宽泛”，我将更详细地阐述一下... 我提到Java的原因是因为Java没有“goto”语句。作为我的一个业余项目，我正在尝试将C#代码转换成Java，这证明是相当具有挑战性的（部分原因是Java的这种限制）。

这让我想起了一些事情。如果你有Open addressing中“remove”方法的实现（参见：http://en.wikipedia.org/wiki/Open_addressing - 注意1），在异常情况下使用“goto”是非常方便的，尽管在这种特殊情况下，你可以通过引入“状态”变量来重写它。请注意，这只是一个例子，当你试图反编译它们时，我已经为continuations实现了代码生成器，这会产生大量的goto。

我也不确定以这种方式进行重写是否总是会消除“goto”语句，以及在每种情况下是否允许。虽然我不寻求正式的“证明”，但一些证据表明，在这种情况下消除是可能的，这将是非常好的。

关于“广泛性”，我向所有认为有“太多答案”或“重写goto的方式很多”的人发起挑战，请提供一种算法或方法来重写一般情况，因为迄今为止我找到的唯一答案就是我发布的那个。

- atlaste

---

goto是一个可以在特定情况下提高性能的技巧（从实用角度来看：标记器、IL执行引擎和内核）。但它在任何情况下都不是不可替代的。 - Niels Keurentjes

许多编程语言确实通过使用跳转语句来实现这些结构，但这并不是一个概念上的要求；还有其他实现这些结构的方法，只是它们在主流编程语言中不太常用。 - Servy

C#仅仅是代码的规范，任何人都可以编写一种实现方式。微软对C#语言的实现细节并不代表这个属性就是C#语言本身的特点。 - Servy

@Servy 你抓住我了 :) - Sriram Sakthivel

@StefandeBruijn goto 本身并不是邪恶的。它被认为是“最好避免”的，是因为它的操作缺乏透明度和控制流。每个 while 循环也可以用 for 循环来编写，但它们都没有生成真正意义上的代码混乱的内在能力，这就是它们作为方便存在的原因。goto 的灵活性也意味着形式化将非常困难，如果不是不可能的话，因为它本质上是汇编级别结构的封装。我怀疑你在那方面会完全成功 :) - Niels Keurentjes

Answer 1

这篇1994年的论文：Taming Control Flow: A Structured Approach to Eliminating Goto Statements 提出了一种算法来消除C程序中的所有goto语句。该方法适用于任何用C#编写的程序或使用类似if/switch/loop/break/continue的常见结构的语言（据我所知，但我不明白为什么不行）。

它从两个最简单的转换开始：

• 情况1

Stuff1();
if (cond) goto Label;
Stuff2();

Label:
Stuff3();

变成：

Stuff1();
if (!cond)
{
  Stuff2();
}
Stuff3();

• 第二种情况

Stuff1();
Label:
Stuff2();
Stuff3();
if (cond) goto Label;

变成：

Stuff1();
do
{
  Stuff2();
  Stuff3();
} while (cond);

并在此基础上研究每个复杂案例，并应用迭代转换来实现那些琐碎的案例。最后，它采用了终极goto/label根除算法。

这是一篇非常有趣的阅读。

更新：该主题的其他一些有趣论文（不易获得，因此我在此直接复制链接以供参考）：

消除Goto语句的形式基础

一种Goto消除方法及其在McCat C编译器中的实现

- Patrice Gahide

---

谢谢，这正是我在寻找的方向！我会阅读这篇论文，看看它是否回答了我的问题。 - atlaste

Patrice，这篇论文写得很好，肯定是我正在寻找的解决方案迈出的非常好的一步；无论如何，它都很优雅并回答了我的问题。不过我还需要测试一下；我不完全确定它会生成什么样的代码（例如逻辑运算符），并且想知道是否需要更多的AST优化，例如内联（复制）代码片段，将代码片段包装在辅助函数中等。无论如何，它绝对值得实现。你知道是否还有其他相关内容吗？ - atlaste

@PeterSchneider 这很简单：它不会对那里的任何内容产生影响，因为它只适用于“goto”语句。 :-) - atlaste

@Stefan 不，我不知道有任何实现（当然除了作者的实现）。如果你开始了什么，请告诉我。 - Patrice Gahide

@PatriceGahide 我打算在短时间内建立它，可能在接下来的几天内，还有一些我想到的流程分析事项；我非常有兴趣看看输出结果是什么。 - atlaste

Answer 2

避免使用goto语句的情况，但我认为最好使用它的情况：

当我需要退出内部循环和外部循环时：

for(int i = 0; i < list.Count; i++)
{
    // some code that initializes inner
    for(int j = 0; j < inner.Count; j++)
    {
       // Some code.
       if (condition) goto Finished;
    }
}
Finished:
// Some more code.

为了避免使用goto，你应该像这样做：

for(int i = 0; i < list.Count; i++)
{
    // some code that initializes inner
    bool conditon = false;
    for(int j = 0; j < inner.Count; j++)
    {
       // Some code that might change condition
       if (condition) break;
    }
    if (condition) break;
}
// Some more code.

我认为使用goto语句会使代码更加简洁易懂。

如果内部循环位于不同的方法中，则第二种情况是可行的。

void OuterLoop(list)
{
    for(int i = 0; i < list.Count; i++)
    {
        // some code that initializes inner
        if (InnerLoop(inner)) break;
    }
}
bool InnerLoop(inner)
{
    for(int j = 0; j < inner.Count; j++)
    {
       // Some code that might change condition
       if (condition) return true;
    }
    return false;
}

- Casperah

---

我喜欢你的帖子，但是 InnerLoop() 的当前版本总是返回 false，这有点违背了它的目的。你可能想要始终返回 condition（并在 InnerLoop() 中声明和初始化为 false）。 - Peter - Reinstate Monica

Answer 3

我有一些实践经验，尝试将一个非结构化程序（使用COBOL编写）转化为结构化程序，通过删除每个GOTO语句。原始程序员是一个改革后的汇编程序员，虽然他可能知道PERFORM语句，但他没有使用它。这是一个严重的意大利面代码 - 几百行的意大利面代码。我花了几周的业余时间试图重写这个巨大的构造，最终不得不放弃。这是一个巨大的疯狂堆积。不过它工作了！它的工作是解析以文本格式发送到主机的用户指令，并且它做得很好。

因此，如果您使用手动方法，则不总是可能完全消除GOTO。然而，这是一个边缘案例 - 现有代码是由具有明显扭曲编程思维的人编写的。在现代，有可用的工具可以解决以前棘手的结构问题。

自那天起，我编写了Modula-2、C、Revelation Basic、三种VB和C#，从未遇到需要或建议使用GOTO作为解决方案的情况。然而，对于原始的BASIC来说，GOTO是不可避免的。

- Cyberherbalist

---

感谢您的建设性反馈。对我来说也是一样的；我在1987年编写了COMX BASIC，它根本没有任何函数、调用等 - 唯一的选择就是过度使用意大利面条式的GOTO。 :-) 之后我很少使用它们（开放地址法是为数不多的例外）。尽管如此，这表明我的脑海中某个地方有一个“goto消除算法” - 我在这里试图将其形式化。 - atlaste

所以您认为@Patrice帖子中提出的转换策略对您的旧程序不起作用吗？（我认为会起作用。）也许手动操作很困难，但使用编程工具应该是可以的。 - Peter - Reinstate Monica

@PeterSchneider，我没有理由怀疑它们会工作。虽然评论区似乎是你和Stefan之间的对话，但我还是发表了这个回答，所以我确定你没有针对我说这句话！ - Cyberherbalist

不，我是在和你说话，评论你的“因此，不，不可能完全消除GOTO。”我现在从你的评论中明白了，手动从你的旧程序中消除goto会是“不可能的”（付出合理的努力）。正如你在帖子中所写的那样，你已经尝试过了。但是，如果有类似Patrice提到的论文中描述的机器支持，就应该是可能的。也许你可以让我引用的“NO”声明变得不那么绝对，以避免误解。 - Peter - Reinstate Monica

@PeterSchneider 你说得很有道理，所以我相应地修改了我的回答。感谢你的建议！ - Cyberherbalist

Answer 4

既然你说这是一个理论问题，那么这就是一个理论答案。

Java是图灵完备的，所以当然可以。你可以用Java表达任何C#程序。你也可以在Minecraft红石电路或扫雷游戏中表达它。与这些替代方案相比，用Java表达应该很容易。

显然更实际的答案是，即一个可理解的算法来进行转换，已经由Patrice给出。

- Peter - Reinstate Monica

---

严格来说，Java是图灵完备的事实并不意味着您可以用Java表达任何C#程序。大象是一种动物，狮子也是一种动物，但大象不能用他的鬃毛挥手。用耳朵挥手在实践中类似，但并不是同一回事。 - astef

@astef 我其实更倾向于计算机工程师而非科学家，但是："鉴于任何计算机算法，都可以构造一个能够模拟该算法逻辑的图灵机。"（来源：https://en.wikipedia.org/wiki/Turing_machine），且"如果一种编程语言可以用来模拟任何图灵机，那么它就被称为图灵完备或计算通用的。"（来源：https://en.wikipedia.org/wiki/Turing_completeness#Unintentional_Turing_completeness）换句话说，**任何算法都可以用任何图灵完备语言表达。** - Peter - Reinstate Monica

@astef，如果你想要一个比喻，那么它更像是“如果两个集合A和B都有一个双射投影到自然数中，那么它们具有相同的“元素数量”，或者更准确地说，具有相同的基数，即$\aleph_0$。（哦，MathJax在这里不起作用，是吗...）这不是一个常见的子集，而是一个共同的等价关系。 - Peter - Reinstate Monica

任何算法 - 是的。您应该能够将任何纯函数移植到任何图灵完备的语言中，并且它将给您相同的结果。除了副作用（执行时间和地点，使用的资源，外部调用等）。问题是一些程序（如果不是大多数）具有副作用，甚至有时依赖于它们。因此，不，您不能在Java中表达任何C#程序。 - astef

Answer 5

我一点也不喜欢我的解决方案。首先，它非常丑陋，其次，它基本上将goto封装到一个开关语句中，其效果与goto完全相同。 当寻找可替换任何goto使用的通用模式时，你总是会得到这样的结果。还能有什么呢？应该使用最匹配的语言结构来替换不同的goto用法。这就是为什么switch语句和for循环等结构存在的原因，使创建程序流程更加容易和少出错。编译器仍然会生成goto（或跳转），但它会在我们犯错误时保持一致。此外，我们不必阅读编译器生成的内容，而是可以阅读（和编写）更容易理解的内容。

你会发现大多数编译器构造都是为了概括 goto 的特定用法，这些构造是基于在它之前存在的 goto 使用的常见模式创建的。Patrice Gahide所提到的论文有点像反过来展示了这个过程。如果你在代码中找到了 goto，那么要么你正在查看其中一个模式，此时应该用相应的语言结构替换它，要么你在查看本质上是非结构化的代码，在这种情况下，你实际上应该对代码进行结构化处理（或者不管它）。将其更改为无 goto 的非结构化内容只会使事情变得更糟。 （顺便说一句，同样的概括过程仍在继续进行，考虑如何向编译器添加 foreach 以概括 for 的一种非常常见的用法...）

- AVee