Можно ли всегда устранить goto's?

Question

Несмотря на то, что сделать что-либо с помощью goto легко (что подтверждается, например, в IL), мне было интересно, можно ли также исключить все операторы goto с помощью выражений и выражений более высокого уровня, скажем, используя все, что поддерживается в Java.

Или, если хотите, то, что я ищу, это "переписать правила", которые будут работать всегда, независимо от того, как создается 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).

Это заставило меня задуматься. Если у вас есть f.ex. Реализация метода "удалить" в открытой адресации (см. http://en.wikipedia.org/wiki/Open_addressing - примечание 1), довольно удобно иметь "goto" в исключительном случае, хотя в этом конкретном случае В этом случае вы можете переписать его, введя переменную 'state'. Обратите внимание, что это только один пример, я реализовал генераторы кода для продолжений, которые выдают тонны и тонны goto, когда вы пытаетесь их декомпилировать.

Я также не уверен, что переписывание в этом вопросе всегда устранит утверждение "goto" и разрешено ли оно в каждом случае. Хотя я не ищу формальных "доказательств", некоторые доказательства того, что устранение возможно в этом вопросе, были бы великолепны.

Что касается "широты", я бросаю вызов всем людям, которые думают, что "слишком много ответов" или "много способов переписать goto", чтобы предоставить алгоритм или подход к переписыванию общего случая, пожалуйста, так как единственный ответ, который я нашел пока тот, который я отправил.

Answer 1

В этой статье 1994 года: Укрощение потока управления: структурированный подход к устранению операторов Goto предлагается алгоритм устранения всех операторов Goto в C-программе. Этот метод применим к любой программе, написанной на C# или к любому языку, который использует общие конструкции, такие как if/switch/loop/break/continue (AFAIK, но я не понимаю, почему это не так).

Он начинается с двух самых простых преобразований:

// CASE 1

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

Label:
Stuff3();

// Becomes:

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

// CASE 2

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

// becomes:

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

и основывается на этом для изучения каждого сложного случая и применения итерационных преобразований, которые приводят к этим тривиальным случаям. Затем он завершается алгоритмом уничтожения gotos / label.

Это очень интересное чтение.

ОБНОВЛЕНИЕ: Некоторые другие интересные статьи на эту тему (не так-то просто достать, поэтому я скопирую прямые ссылки здесь для справки):

Формальная основа для удаления операторов Goto

Метод Goto-ликвидации и его реализация для компилятора McCat C

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.

Чтобы избежать перехода, вы должны сделать что-то вроде этого:

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

Answer 3

У меня есть некоторый практический опыт попыток взять неструктурированную программу (на COBOL, не менее) и сделать ее структурированной, удалив каждый экземпляр GOTO. Первоначальный программист был преобразованным программистом на ассемблере, и хотя он, возможно, знал об утверждении PERFORM, он не использовал его. Это было GOTO GOTO GOTO. И это был серьезный код спагетти - несколько сотен строк кода спагетти. Я потратил пару недель свободного времени, пытаясь переписать эту чудовищную конструкцию, и в конце концов мне пришлось сдаться. Это была огромная дымящаяся куча безумия. Это работало, хотя! Его работа заключалась в том, чтобы анализировать пользовательские инструкции, отправленные на мэйнфрейм, в текстовом формате, и он делал это хорошо.

Итак, НЕТ, не всегда возможно полностью устранить GOTO - если вы используете ручные методы. Однако это крайний случай - существующий код, который был написан человеком с явно извращенным умом программирования. В наше время существуют инструменты, которые могут решить ранее неразрешимые структурные проблемы.

С того дня я кодировал в Modula-2, C, Revelation Basic, три разновидности VB и C# и никогда не находил ситуации, которая требовала или даже предлагала GOTO в качестве решения. Однако для оригинального бейсика GOTO был неизбежен.

Answer 4

Поскольку вы сказали, что это теоретический вопрос, вот теоретический ответ.

Ява завершена по Тьюрингу, так что, конечно, да. Вы можете выразить любую программу C# на Java. Вы также можете выразить это в Minecraft Redstone или Minesweeper. По сравнению с этими альтернативами выразить это в Java должно быть легко.

Очевидно, что более практичный ответ, а именно понятный алгоритм для преобразования, был дан Патрисом.

Answer 5

Мне немного не нравится мое решение. Во-первых, он ужасно уродлив, а для двух он в основном превращает goto в переключатель, который делает то же самое, что и goto.

Это то, что вы всегда получите, когда будете искать общий шаблон, который может заменить любое использование goto, то, что делает то же самое, что и goto. Что еще это может быть? Различные варианты использования goto должны быть заменены наилучшей подходящей языковой конструкцией. Вот почему в первую очередь существуют конструкции как операторы switch и циклы for, чтобы упростить и снизить вероятность создания такого программного потока. Компилятор будет по-прежнему генерировать goto (или переходы), но он будет делать это последовательно, где мы облажаемся. Кроме того, нам не нужно читать то, что генерирует компилятор, но мы можем прочитать (и написать) что-то, что легче понять.

Вы обнаружите, что большинство конструкций компилятора существуют для обобщения конкретного использования goto, эти конструкции создаются на основе общих шаблонов использования goto, которые существовали до этого. В статье Патриса Гахайда упоминается, что этот процесс показан в обратном порядке. Если вы находите goto в своем коде, вы либо просматриваете один из этих шаблонов, и в этом случае вы должны заменить его соответствующей языковой конструкцией. Или вы смотрите на по существу неструктурированный код, и в этом случае вы должны структурировать код (или оставить его в покое). Меняя его на что-то неструктурированное, но без goto может только усугубить ситуацию. (Кстати, тот же процесс обобщения все еще продолжается, рассмотрим, как foreach добавляется в компиляторы, чтобы обобщить очень распространенное использование for...)