О структурном программировании

Многие в комментариях к посту об операторе goto высказывали одно и то же мнение, которое звучит примерно так: «За n лет написания программ мне ни разу не понадобился goto, и использовать его в будущем я тоже не собираюсь». И они абсолютно правы, уже давно доказана теорема о структурировании, в которой говорится, что любая простая программа функционально эквивалентна структурированной программе составленной с использованием функций и предикатов исходной программы, а также с использованием дополнительного счетчика. Доказательством является алгоритм составления той самой структурированной программы:
  1. пронумеровать все узлы схемы, при этом порядок обхода произвольный;
  2. пронумеровать все дуги схемы следующим образом: выходной дуге схемы припишем номер 0, всем остальным дугам присвоим номер вершины, в которую данная дуга входит;
  3. для каждого функционального узла исходной программы, имеющего номер i и выходную дугу j, составить новую простую последовательную программу Gi с номером входной дуги i
  4. для каждого предикатного узла с номером i составить новую простую программу
  5. построить программу типа while do с do-частью в виде структры, проверяющей значения L.


Итак, если однажды вы напишите что-то вроде этого (программа из поста о goto):

if (p1)
{
	f1;
	goto L3;
}
L1:
if (p2)
{
L2:
	f2;
L3:
	f3;
	goto L1;
}
else if (p3)
{
	f4;
	goto L2;
}
f5;


То лучше перепишите этот код. Ведь не зря один умный человек сказал: «Пишите код так, как будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете». Если учесть что большинство программистов недолюбливают goto, то это более чем актуально.

Воспользуемся теоремой и преобразуем этот код в соответствии с принципами структурного программирования. Сначала составим блок-схему этого алгоритма и пронумеруем блоки и дуги в соответствии с теоремой.

image

Теперь построим цикл while do с заменой предикатных и функциональных блоков.

image

Получилась схема структурированной программы, но в ней слишком много лишнего. Преобразуем её в соответствии со следующим алгоритмом:
Для каждого j>0 пытаемся заменить все присваивания L=j соответствующей подпрограммой Gj(в том числе и для L=1). Если L больше никогда не будет присвоено значение j можно убрать проверку L=j (вместе с соответствующей ей веткой выполнения) из структуры программы.

image

С помощью этой схемы можно легко написать код, соответствующий принципам структурного программирования.

if p1:
    f1
    f3
l = 3
while l > 0:
    if p2:
        f2
        f3
    elif p3:
        f4
        f2
        f3
    else:
        f5
        l = 0;


Или совсем избавиться от флага как это сделал eigrad здесь.

Так же можно было написать рекурсивный код предварительно преобразовав блок-схему программы в так называемую Е-схему.

image

Код:
def F1():
    if p2:
        F2()
    elif p3:
        f4
        F2()
    else:
        f5

def F2():
    f2
    F3()

def F3():
    f3
    F1()

if p1:
    f1
    F3()
else:
    F1()


Если учесть, что при реальном программировании функции именуются в соответствии с выполняемыми ими действиями, этот код так же становится более читаемым, чем код с использованием goto.

При написании топика использовалась методичка НГТУ «Информатика. Теория и практика структурного программирования.» Т.А.Шапошниковой.

P.S. Спасибо funca за его вопросы и исправления.
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 35

    0
    Опечатку в заголовке поправьте. Струкурное — это почти укурное :)
      +1
      Коллега, Вы меня опередили, как раз собирался написать примерно то же самое.
      В ряде случаев бывает удобно заменить каскадные if… elif… else простым switch по всем состояниям и в каждом case просто вычислять следующее состояние. В общем, классика автоматного прграммирования
        +1
        любая простая программа функционально эквивалентна структурированной программе составленной с использованием функций и предикатов исходной программы

        Кроме этого она так же функционально эквивалентна brainfuck'у и механическому тьюрингу.
        +1
        yury@debian-dev-vm:~/kernel/linux-2.6.36-starterkit/mm$ grep goto *.c | wc -l
        894
        yury@debian-dev-vm:~/kernel/linux-2.6.36-starterkit/mm$ cat *.c | wc -l
        75724


        Право, меня удивляют бурления против goto :-)

        ЗЫ. Это только в управлении памятью, всё ядро долго перебирать.
          +19
          Да-да-да… Продолжим бурлить.

          1) MSDN: It is good programming style to use the break, continue, and return statement in preference to goto whenever possible. Since the break statement only exits from one level of the loop, a goto may be necessary for exiting a loop from within a deeply nested loop. — Т.е. goto неплохо подходит для выхода сразу из нескольких циклов:

          #include <stdio.h>
          int main()
          {
            int i, j;

            for ( i = 0; i < 10; i++ )
            {
              printf_s( "Outer loop executing. i = %d\n", i );
              for ( j = 0; j < 2; j++ )
              {
                printf_s( " Inner loop executing. j = %d\n", j );
                if ( i == 3 )
                  goto stop;
              }
            }

            // This message does not print:
            printf_s( "Loop exited. i = %d\n", i );

          stop:
            printf_s( "Jumped to stop. i = %d\n", i );
          }

          * This source code was highlighted with Source Code Highlighter.


          2) Финализация при помощи goto — а он быстро работает, и SEH не всегда помогает:

          if (...)
            goto Cleanup;
          if (...)
            goto Cleanup;
          ...
          Cleanup:
          ...

          * This source code was highlighted with Source Code Highlighter.


          3) Поддержание принципа «один вход — один выход» при помощи goto:

          int f()
          {
            int res;

            // some code ...

            if (...)
            {
              res = rand();
              goto finish;
            }

            // some code ...

          finish:
            return res; 
          }

          * This source code was highlighted with Source Code Highlighter.


          4) Использование goto в машинно генерируемых кодах (всякого рода анализаторы, парсеры).

          5) В C# оператор goto незаменим внутри switch;

          6) И девушек обижать нехорошо:

          goto gerl


          И да, я склонен всё же к мнению такому (Джонсон М. Харт. Системное программирование в среде Windows, третье издание — 2005 г.): «Возможно, это дело вкуса, — то ли индивидуального, то ли корпоративного, — но многие программисты никогда не используют оператор goto и избегают употребления оператора break, кроме случаев его совместного использования с операторами switch и иногда — в циклах, а также совместного использования с операторами continue. Те, кто мыслит трезво, не спешат определять свою позицию в этом отношении. Обработчики завершения и исключений могут решать многие из тех задач, для решения которых вам хотелось бы привлечь оператор goto и операторы, снабжённые метками.»
            +3
            интересно, что будет, когда противники goto узнают о setjmp и longjmp :-) и о ситуациях, когда они — единственный выход :-)

            Например, в конторе, где я работал, занимаются сертификацией ПО управления электроникой самолётов по стандарту DO-178b. Пишут тесты. Приходит код, в коде — вечный цикл и вызов функции. Как провеить, что тело цикла корректно и не повиснуть? Как вариант, переопределить вызываемую функцию с тем, чтобы при втором вызове она делала longjmp (goto не поможет, т.к. другая функция) в место, не являющееся телом цикла, таким образом мы его завершим. Сам тестируемый код изменять, естественно, вообще нельзя. Исключение плюсовое бросать из вызываемой не получится, т.к. не плюсы :-)
              0
              Главное, чтобы все понимали, что речь здесь идёт о си, а не о си++.
              В си goto действительно нужен в этих местах, в си++ — не обязательно. (1) заменяется выносом в функцию, (2) RAII (с goto тупо не получится exception-safe) (3) много выходов, все довольны, т.к. 2, (4) машинно генерируемый код это вообще другой разговор, ровно как и (5) C#. Ну а с (6), конечно, не поспоришь, хотя там язык тоже другой: Р
            • НЛО прилетело и опубликовало эту надпись здесь
              • НЛО прилетело и опубликовало эту надпись здесь
                • НЛО прилетело и опубликовало эту надпись здесь
              • НЛО прилетело и опубликовало эту надпись здесь
                +1
                Хочу заметить в топике нет «бурления против goto». Зато в нем есть факт: многие программисты недолюбливают goto; авторитетное мнение: «Пишите код так, как будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете»; описание того, как можно избежать использования goto.
                  +9
                  goto — инструмент. Лучше учиться, как им правильно пользоваться, чем его избегать.
                    +4
                    дык избегать его — это и есть один главных из способов правильно пользоваться goto
                      +2
                      таким образом, goto приравнивается к тяжёлым наркотикам :-)
                    +2
                    Даже Рихтер, в примере в книжке clr via C#, использовал goto (глава не была с goto никак связана). Хотя, когда я посмотрел на этот код, было ощущение, что увидел привидение.
                    –1
                    Я хоть и не любитель goto, но недавно пришлось отлаживать код примерно такой:

                    if (a) {
                    ...
                    ...
                    return 1;
                    }

                    if (b) {
                    ...
                    ...
                    return 2;
                    }
                    ...
                    повторить 15 раз в том же духе


                    Представляете как это отлаживать, сколько дебага вставить надо перед каждым return?

                    Не проще ли именно с точки зрения поддержки и сопровождения кода писать как минимум

                    if (что-то) {
                    result = 1;
                    goto Exit;
                    }

                    if (что-то еще) {
                    result = 2;
                    goto Exit;
                    }
                    ...
                    повторить много раз
                    ...

                    : Exit
                    write_debug("Result: " + result);
                    return result;


                    Сколько нервов съэкономит этот goto… хотя одно наличие подобного кода уже убивает.
                      +2
                      Если в вашем примере убрать goto, то он будет выдавать тот же результат.
                        +4
                        не факт
                        если («что-то» && «что-то еще») == true, то без goto результат будет 2, а с ним 1, else-ов ведь нет
                          0
                          Точно, Вы правы.
                          0
                          Не всегда, все зависит от реальных условий. Я собственно хотел показать только то, что при множетвенном ветвлении и куче return goto улучшает и читаемость, и отлаживаемость кода.
                          Это очень неплохо описано в замечательной книжке Алена Голуба, в русском переводе она называется «Правила программирования на С и С++» — перечитывал несколько раз, и хоть кое-что устарело, с чем-то не согласен — но вцелом это супер, каждый, кто хочет писать более-менее грамотный, читаемый и отлаживаемый код — должен ее прочитать. На просторах интернет ее можно найти например тут
                          +1
                          if (что-то)
                            result = 1;
                          else if (что-то еще)
                            result = 2;
                          ...
                          повторить много раз
                          ...
                          
                          write_debug("Result: " + result);
                          return result;
                          


                          В данном случае это то же самое, т.к. у вас при выполнении условия сразу происходит переход к отладочному выводу. Ваш код эквивалентен записи приведённого мной кода на ассемблере:

                            ... ; вычисляем <что-то> и кладём в ebx
                            test ebx, ebx
                            jz L1
                            mov eax, 1
                            jmp Exit
                          
                          L1:
                            ... ; вычисляем <что-то ещё> и кладём в ebx
                            test ebx, ebx
                            jz L2
                            mov eax, 2
                            jmp Exit
                          
                          L2:
                            ...
                            ; повторить много раз
                            ...
                          
                          Exit:
                            ... ; вызываем write_debug (result - в eax)
                            ret
                          


                          В общем, вы привели неудачный пример использования goto.
                            0
                            А если Вы делаете return изнутри цикла?
                            Или даже из пары вложенных циклов? Тут break (который по сути тот же goto к концу цикла) уже не поможет — он сработает на один цикл (хотя вроде поминалось, что в java можно и из вложенных выходить — но тогда опять же goto к концу внешнего цикла).
                            Так что goto иногда все-таки удобно.
                            Но не спорю, лучше бы его поменьше, и такие if'ы не писать.
                          –1
                          Мы как-то с друзьями спорили насчёт goto.
                          Решили посмотреть на самые популярные, проверенные временем программы, которыми пользуются миллионы разработчиков: исходники ядра линукс, llvm, gtk, gstreamer, android и т.д.
                          В каждой из этих программ используется goto.

                          По-моему, те кто фанатично боится goto — школьники, начитавшиеся букварей «не используйте goto, из-за этого взрываются компьютеры». goto — инструмент и, пользуясь им умело, можно сделать код читабельнее, легче в поддержке, структуринованнее.

                            0
                            я бы посмотрел, как все дофига умные будут вываливаться с ошибкой из инициализации ядерного драйвера без исключений и goto.
                              0
                              С правильным возвращением успешно затребованных ресурсов. В нужном порядке :-)
                            0
                            Оффтоп, но наболело.
                            Хабрэффект.ру становится все популярнее, все больше авторов выкладывают картинки к постам именно туда.
                            Но! Я этих картинок в упор не вижу :(
                            Иногда это терпимо, а иногда пост просто теряет смысл.
                            Возможно причина в том, что я не в России или СНГ.
                            Если это официальный хостинг хабра, то просьба к администрации разобраться, если нет, то просьба к авторам, используйте другой хостинг, пожалуйста.
                              0
                              У меня еще прикольнее: на работе картинки вижу, дома — нет. Думаю проблема не у хабраэффекта.
                              А официальный хостинг хабра таки хабрасторадж.орг
                                0
                                Вот именно из-за того, что хостинг «сторадж» он благополучно забанен у меня на работе админом как «Personal Storage». Всякие радикалы и иже с ними тоже забанены, так что у меня ситуация обратная — на работе хабр практически без картинок, а из дома я их вижу.
                              0
                              Или совсем избавиться от флага как это сделал eigrad здесь.

                              кажется, что вариант комменте по ссылке не верный — если условие b изначально '0', то хвост алгоритма (E) не выполнится ни разу.
                                0
                                Вы абсолютно правы, пропустил это
                                0
                                Теперь построим цикл while do с заменой предикатных и функциональных блоков.
                                я правильно понимаю, что на этой схеме получилось нечто похожее на машину состояний — switch, в котором каждый case это подпрограмма, представляющая собой либо выбор нового значения L (одного из двух) либо выполнение операции и назначение нового L?:
                                L = 1
                                white L > 0:
                                   switch L:
                                     case 1: if p1 L = 2 else L = 3   ; break
                                     case 2: f1; L = 6                ; break
                                     ...
                                     case 8: f5; L = 0                ; break 
                                
                                  0
                                  да все верно, более того можно заменить лишь те присваивания L=j, которые удобно, просто в этом примере вышло так что осталось 2 значения флага
                                  0
                                  Для каждого j>0 заменить все присваивания L=j соответствующей подпрограммой Gj(в том числе и для L=1). Так как L больше никогда не будет присвоено значение j можно убрать проверку L=j (вместе с соответствующей ей веткой выполнения) из структуры программы.
                                  выглядит как «inline» подпрограмм? эта затея осуществима для всех j>0, в любом случае? или тут схема маягче: «Для каждого j>0 пытаться заменить все присваивания L=j… », и «Если L больше никогда не будет присвоено значение j ...». Просто в данном примере заменились не все присавивания — «L=3» в структуре осталось.
                                    0
                                    вы снова правы:) это осталась рекурсия, её можно заменить сколько угодно раз, результат будет тот же, только код вырастет

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое