Untying Knuth knots: как реструктурировать код спагетти?

Ответ 1

Я набросал алгоритм для OP ранее fooobar.com/questions/557406/...

Найдена лучшая статья, в которой обсуждается, как сгенерировать структурированный код, сохраняя при этом собственно исходный граф потока управления:

W.D Maurer, "Обобщенные структурированные программы и деревья циклов" , Science of Computer Programming, 2007

Я следовал этой процедуре (на бумаге, надеюсь, я сделал это правильно, посмотрел ОК в 2:40). Его основной трюк состоит в том, чтобы найти сильно связанные области (циклы в коде); они станут петлями; Затем он разрушает этот цикл, удаляя край; это в конечном итоге становится обратной связью цикла (восстанавливается, когда он завершен). Процесс повторяется до тех пор, пока не будет найдено больше циклов; то, что осталось, по существу представляет собой структурированную программу с идентифицированными циклами. Трудно делать это правильно; вам действительно нужна автоматическая процедура. Ваш бит кода, хотя и небольшой, по-прежнему довольно неприятен: -}

Я обманул в одном месте. Маурер настаивает на том, что вперед gotos в порядке, даже в середине цикла. Если вы купите это, вы сможете точно сохранить CFG. Если нет, вы должны обрабатывать случай, когда цикл имеет две или более точек входа; ваш алгоритм имеет такой цикл. Я решил проблему, закодировав цикл и закодировав эквивалент фрагмента loop-end-end-fragment, который действует как первая итерация перехода в середину, за которой следует сам цикл.

Мои обозначения немного забавны: у большинства языков нет "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) [email protected];
         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) [email protected];
         6:
         decrease(k);
         if (k==0) return;
         set(p,u_k);
      } // while(true)@5
  } // while(true)@3
  4:
  increase(k);
} // while(true)@2

В отличие от большинства других ответов, которые я видел до сих пор, это выполняется с той же скоростью, что и оригинал (никаких дополнительных флажков или флагов).

@hatchet ответ интересен; а) он одинаково быстро, б) он решил обработать два петли ввода тем же методом, но он выбрал "другую запись" как верх петли. Он сделал что-то подобное с "enter_level (k)" на метке 2.

Интересно, что все это структурирование, похоже, не помогает читабельности этого кода один бит. Заставляет задуматься о цели "структурированных программ". Возможно, хорошо продуманные спагетти не так уж плохи: -}

Ответ 2

Без слишком больших усилий (и не много риска) вы можете быстро сократить количество gotos и меток.

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;

Я был бы склонен остановиться здесь. Но если вы продолжите, это станет вопросом идентификации циклов и замены 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: внутренний цикл. Я избавился от goto 5, скопировав код 5: вместо goto и заменив goto 3 на перерыв. Это облегчает создание чистых петель. Goo 6 фиксируется с использованием другого. Продолжение goto 3 продолжается.

После этого (если у вас есть энергия слева), вы можете попытаться изменить петли с (true) с продолжением в действительные условия.

Рекомендуется сначала разработать ваши тесты, а затем сделать одно или два изменения и проверить. Сделайте другое изменение, затем повторите тест. Если вы этого не сделаете, легко сделать структурную ошибку на ранней стадии, а затем аннулировать последующие шаги и заставить вас начать все заново.

Ответ 3

В С++ алгоритм может быть записан как:

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

• если метка вернется к себе, тогда поместите блок во время (true). Удалить снизу lbl5 (lbl5 теперь автономно и может быть заменен там, где он используется)

• если блок самодостаточен, а затем замените его везде, где он используется. Удалить lbl5

• Если одна метка следует за другой, тогда поместите следующую метку в конец блока, чтобы ее можно было заменить в соответствии с правилом 2. Удалите lbl2 (который может goto lbl3)

• теперь мы остаемся с последней меткой goto по всему коду. Замените goto lbl3 на skiptail=true, поместите оставшийся блок в блок while (true) и установите остальные инструкции, чтобы проверить, есть ли skiptail=false. Удалите lbl3 и замените на skiptail = false.

Ответ 4

Я никогда не использовал goto, но это казалось забавным вызовом, поэтому я попытался самостоятельно реорганизовать.

Прежде всего, просмотрите код и посмотрите, сколько операторов goto для каждой метки; это будет важно иметь в виду, чтобы избежать ошибок. В вашем примере ничего не приводит к 1, поэтому мы можем игнорировать его.

Иногда мне было удобно добавлять goto, когда они подразумевались потоком управления. Это помогло отслеживать порядок, когда я переместил код между вещами.

Лучший способ реорганизации goto работает вверх изнутри или снизу вверх.

• Последняя команда 7:return;, которую можно просто перемещать туда, где вызывается goto 7. Это легко.

• Затем я пытаюсь увидеть, какие метки заканчиваются на goto (безоговорочно) и поступают сразу после другого goto. В этом случае это будет 4; он может быть перемещен перед 2, внутри, если контролируется дозорным (при подготовке к петле). (goto мой первый пункт, чтобы увидеть, что 2 можно удалить сейчас.)

• Следующее, что я сделал, было помещено 5 и 6 в цикл. Если бы я был неправ, я мог бы просто отступить в любом случае.

• В этот момент я вижу, что 6 будет выполняться после 3 или 5. Я также вижу, что 5 может выполнить 3, поэтому я решил переместить 3 после 5. Я добавляю переменную, чтобы я мог пропустить 5 в первый раз. Я установил его в true в конце 6.

• Чтобы обеспечить 5, можно перейти непосредственно к 6, когда это необходимо, я могу обернуть 3 в инструкции if с противоположным условием выполнения 5. Когда мне нужно перейти от 5 до 3, я могу изменить условие, пока я внутри 5, так что 3 выполняется сразу после этого.

• В этот момент у меня есть только один goto, который идет от 3 до 4. Если я изменил это на break, я могу выйти из одного цикла, и я дойду до конца. Чтобы добраться до 4, я просто завершаю все (кроме 1) в цикле.

Вы можете использовать этот трюк, чтобы вырваться из вложенных циклов, не используя 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;
    }
}

Ответ 5

Вы можете использовать множество переменных, чтобы имитировать поток gotos для работы с 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's, я лично предпочитал не использовать их.