Блок-схемы
На последнем рисунке поток управления показан в виде так называемой блок-схемы программы или просто блок-схемы. Форма элементов блок-схемы стандартизована: ромбы для условий с двумя выходящими ветвями для True и False; прямоугольник для обрабатывающих блоков, здесь для Body. Можно проверить свое понимание блок-схем, изобразив схему для условного оператора.
В свое время блок-схемы были весьма популярны для выражения структуры управления программы. И сегодня их можно встретить в описании процессов, не связанных с программированием. В программировании они потеряли репутацию (некоторые авторы называют их теперь не "flowchart", а "flaw chart" — порочными схемами). Причины этого понятны. Если язык программирования предоставляет вам безусловный оператор перехода goto и условный оператор ветвления, такой как test condition goto label, то блок-схемы представляют способ отображения потока управления в период выполнения более понятный, чем программный текст, использующий goto. Теперь же такое представление устарело по двум причинам.
Наши программы делают все более сложные вещи. Большие блок-схемы с вложенностью внутри циклов и условных операторов быстро становятся запутанными.
Механизмы этой лекции — составной оператор, цикл, условный — обеспечивают высокий уровень выражения структур управления. Аккуратно отформатированный программный текст с отступами, отражающимиуровень вложенности, дает лучшее представление о порядке выполнения операторов.
Переход от блок-схем к тщательно отобранным структурам управления противоречит клише "рисунок лучше тысячи слов". В ПО нам необходимы многие тысячи, фактически — миллионы слов, но критически важно, чтобы это были "правильные" слова. Из-за проблем с точностью картинки теряют свою привлекательность.
Корректность программ может зависеть от маленьких деталей, таких как использование условия i <= n вместо i < n; лучшие рисунки в мире полностью бесполезны, когда приходится иметь дело с правильным отображением таких аспектов.
7.8. Исключение goto и структурное программирование
Блок-схемы — не единственное, что вышло из употребления в программной инженерии с превращением ее в более солидную дисциплину: операторы goto также потеряли свою былую славу.
Goto вредны?
Причины потери доверия к goto практически те же, что и для блок-схем. Механизмы, которые мы уже изучили, предлагают лучшее управление. Приведу два аргумента.
Конструкции цикла и условного оператора лучше читаются, чем goto — особенно для сложных структур с большой степенью вложенности. Особых доказательств не требуется — достаточно визуально сравнить оригинальные структуры и их goto-аналоги.
Однако это еще не вся история. Остановившись на трех перечисленных механизмах, мы ограничиваем себя в сравнении с программистом, который может использовать произвольно оператор goto или, что эквивалентно, произвольные блок-схемы со стрелками, выходящими из любого блока и входящими в любой блок. Прозвищем таких переплетающихся структур является "блюдо спагетти". Образец такого "блюда" для довольно простого варианта с небольшим числом блоков показан на рисунке. Очевидно, что "наши" структуры управления понятнее и лучше читаются, чем блюдо спагетти. Но, с другой стороны, это ведь только методологический аргумент. Возможно ли, что, ограничив себя тремя структурами и исключив goto, мы потеряли нечто важное? Другими словами, существуют ли алгоритмы, не выразимые без полной мощи goto?
Рис. 7.16. Блюдо спагетти
На этот вопрос ответ получен — нет! Теорема, доказанная в 1966 году двумя итальянскими учеными Коррадо Бёмом и Джузеппе Джакопини, говорит, что каждая блок-схема в теории вычислений имеет эквивалентное представление, использующее только последовательности и циклы (нет необходимости даже в условных операторах).
Corrado Bohm, Giuseppe Jacopini: Flow diagrams, Turing machines and languages with only two formation rules. Comm. of the ACM, vol. 9, no. 5, pages 366-371, May 1966.
Общие правила преобразования произвольных блок-схем в программы без goto, приведенные в этой статье, могут быть сложными. Для случаев, встречающихся на практике, часто возможно исключить эти схемы неформальным, но простым и понятным способом. Поскольку это более специальная тема (и она использует присваивание, формально еще не пройденное), ее обсуждение и специальные примеры приведены в приложении. В одном из упражнений, которое предстоит выполнить после чтения приложения, предлагается построить программу без goto для еще одного примера.