Структу́рное программи́рование — парадигма программирования, в основе которой лежит представление программы в виде иерархической структуры блоков. Концептуализирована в конце 1960-х — начале 1970-х годов на фундаменте теоремы Бёма — Якопини, математически обосновывающей возможность структурной организации программ, и работы Эдсгера Дейкстры .
В соответствии с парадигмой, любая программа, которая строится без использования оператора goto, состоит из трёх базовых управляющих конструкций: последовательность, ветвление, цикл; кроме того, используются подпрограммы. При этом разработка программы ведётся пошагово, методом «сверху вниз».
Методология структурного программирования появилась как следствие возрастания сложности решаемых на компьютерах задач, и соответственно, усложнения программного обеспечения. В 1970-е годы объёмы и сложность программ достигли такого уровня, что традиционная (неструктурированная) разработка программ перестала удовлетворять потребностям практики. Программы становились слишком сложными, чтобы их можно было нормально сопровождать. Поэтому потребовалась систематизация процесса разработки и структуры программ.
Методология структурной разработки программного обеспечения была признана «самой сильной формализацией 70-х годов».
По мнению Бертрана Мейера, «Революция во взглядах на программирование, начатая Дейкстрой, привела к движению, известному как структурное программирование, которое предложило систематический, рациональный подход к конструированию программ. Структурное программирование стало основой всего, что сделано в методологии программирования, включая и объектное программирование»Мейер Б. Почувствуй класс. Учимся программировать хорошо с объектами и контрактами. — Пер. с англ. — М.: Национальный открытый университет ИНТУИТ: БИНОМ. Лаборатория знаний, 2011. — 775с. — С. 208. — ISBN 978-5-9963-0573-5.
История Первоначально идея структурного программирования появилась на свет в связи с оператором goto и сомнениями в целесообразности его применения. Впервые подобные сомнения высказал Хайнц Земанек (Heinz Zemanek) на совещании по языку Алгол в начале 1959 года в Копенгагене. Однако это выступление не привлекло к себе внимания и не имело последствий. Эдсгер Дейкстра вспоминает: «До некоторой степени я виню себя за то, что в то время не смог оценить значимость этой идеи»См. также материалы из Архива Дейкстры. E. W. Dijkstra Archive. The manuscripts of Edsger W. Dijkstra. — Department of Computer Science The University of Texas at Austin .
Ситуация коренным образом изменилась через десять лет, когда в марте 1968 года Дейкстра опубликовал своё знаменитое письмо «Оператор Go To считается вредным» (Go To Statement Considered Harmful). Это поистине исторический документ, оказавший заметное влияние на дальнейшее развитие программирования.
Судьба самого документа очень интересна. Дело в том, что Дейкстра дал статье совсем другое название: «Доводы против оператора GO TO» (A Case against the GO TO Statement).
Однако в момент публикации произошло нечто непонятное — статья почему-то загадочным образом превратилась в «Письмо к редактору», причем прежнее название столь же загадочно исчезло. Что произошло на самом деле? Дейкстра объяснил таинственное превращение статьи в письмо лишь много лет спустя, в 2001 году, за год до смерти.
Журнал Communications of the ACM опубликовал мой текст под названием «Оператор GOTO считается вредным». В последующие годы его часто цитировали. К сожалению, зачастую это делали люди, которые видели в нём не больше, чем сказано в заголовке. Этот заголовок стал краеугольным камнем моей славы…
Как все это случилось? Я отправил статью под названием «Доводы против оператора GO TO». Чтобы ускорить публикацию, редактор превратил мою статью в «Письмо к редактору». При этом он придумал для статьи новое название, которое изобрел сам. Редактором был Никлаус ВиртРукопись EWD1308 из Архива Дейкстры. What led to «Notes on Structured Programming» — Nuenen, 10 June 2001. — Department of Computer Sciences. The University of Texas at Austin, USA Расшифровка рукописи EWD1308 из Архива Дейкстры. What led to «Notes on Structured Programming» — Nuenen, 10 June 2001. — Department of Computer Sciences. The University of Texas at Austin, USA .
Цель Цель структурного программирования — повысить производительность труда программистов, в том числе при разработке больших и сложных программных комплексов, сократить число ошибок, упростить отладку, модификацию и сопровождение программного обеспечения.
Такая цель была поставлена в связи с ростом сложности программ и неспособностью разработчиков и руководителей крупных программных проектов справиться с проблемами, возникшими в 1960—1970 годы в связи с развитием программных средствЛингер Р., Миллс Х., Уитт Б. Теория и практика структурного программирования. — Пер. с англ. — М.: Мир, 1982. — 406с. — С. 7..
Спагетти-код
Структурное программирование призвано, в частности, устранить беспорядок и ошибки в программах, вызванные трудностями чтения кода, несистематизированным, неудобным для восприятия и анализа исходным текстом программы. Такой текст нередко характеризуют как «спагетти-код».
Спагетти-код — плохо спроектированная, слабо структурированная, запутанная и трудная для понимания программа, содержащая много операторов goto (особенно переходов назад), исключений и других конструкций, ухудшающих структурированностьJohn Vlissides, Kyle Brown, Gerard Meszaros AntiPatterns: The Survival Guide. Spaghetti code .. Один из самых известных антипаттернов программирования.
Спагетти-код назван так потому, что ход выполнения программы похож на миску спагетти, то есть извилистый и запутанный. Иногда называется «кенгуру-код» (kangaroo code) из-за множества инструкций jump.
В настоящее время термин применяется не только к случаям злоупотребления goto, но и к любому «многосвязному» коду, в котором один и тот же небольшой фрагмент исполняется в большом количестве различных ситуаций и выполняет много различных логических функций.
Спагетти-код может быть отлажен и работать правильно и с высокой производительностью, но он крайне сложен в сопровождении и развитии. Доработка спагетти-кода для добавления новой функциональности иногда несет значительный потенциал внесения новых ошибок. По этой причине становится практически неизбежным рефакторинг — главное лекарство от спагетти.
Оператор goto
Начиная с 1970-х годов, оператор безусловного перехода goto оказался в центре систематической и всевозрастающей критики. Неправильное и необдуманное использование оператора goto в исходном тексте программы приводит к получению запутанного, неудобочитаемого «спагетти-кода». По тексту такого кода практически невозможно понять порядок исполнения и взаимозависимость фрагментов.
Впервые эта точка зрения была отражена в статье Эдсгера Дейкстры «Оператор Go To считается вредным». Дейкстра заметил, что качество программного кода обратно пропорционально количеству операторов goto в нём. Статья приобрела широкую известность, в результате чего взгляды на использование оператора goto были существенно пересмотрены. В работе «Заметки по структурному программированию» Дейкстра обосновал тот факт, что для кода без goto намного легче проверить формальную корректность.
Код с goto трудно форматировать, так как он может нарушать иерархичность выполнения (парадигму структурного программирования) и потому отступы, призванные отображать структуру программы, не всегда могут быть выставлены правильно. Кроме того, оператор goto мешает оптимизации компиляторами управляющих структурDonald Knuth. Structured Programming with go to Statements 1974.
Некоторые способы применения goto могут создавать проблемы с логикой исполнения программы:
Если некоторая переменная инициализируется (получает значение) в одном месте и потом используется далее, то переход в точку после инициализации, но до использования, приведёт к тому, что будет выбрано значение, которое находилось в памяти, выделенной под переменную, до момента выделения (и которое, как правило, является произвольным и случайным). Передача управления внутрь тела цикла приводит к пропуску кода инициализации цикла или первоначальной проверки условия. Аналогично, передача управления внутрь процедуры или функции приводит к пропуску её начальной части, в которой производится инициализация (выделение памяти под локальные переменные).
Доводы против оператора goto оказались столь серьёзными, что в структурном программировании его стали рассматривать как крайне нежелательный. Это нашло отражение при проектировании новых языков программирования. Например, goto запрещён в Java и Ruby. В ряде современных языков он всё же оставлен из соображений эффективности в тех редких случаях, когда применение goto оправданно. Так, goto сохранился в Аде — одном из наиболее продуманных с точки зрения архитектуры языков за всю историюCode Complete: A Practical Handbook of Software Construction Redmond: Microsoft Press, 1993. 880 p..
Однако в языках высокого уровня, где этот оператор сохранился, на его использование, как правило, накладываются жёсткие ограничения, препятствующие использованию наиболее опасных методов его применения: например, запрещается передавать управление извне цикла, процедуры или функции внутрь. Стандарт языка C++ запрещает обход инициализации переменной с помощью goto.
Теорема о структурном программировании
Теорему сформулировали и доказали итальянские математики Коррадо Бём и Джузеппе Якопини (Giuseppe Jacopini). Они опубликовали её в 1965 году на итальянском языке и в 1966 году на английском. Наряду с теоремой, в статье Бёма и Якопини описывались методы преобразования неструктурных алгоритмов в структурные на примере созданного Бёмом языка программирования P′′. Язык P′′ — первый полный по Тьюрингу язык программирования без оператора goto.
Теорема Бёма-Якопини написана сложным языком и в непривычных обозначениях. Если использовать современную терминологию и обозначения, она примет вид:
Любая программа, заданная в виде блок-схемы, может быть представлена с помощью трёх управляющих структур:
последовательность — обозначается: f THEN g, ветвление — обозначается: IF p THEN f ELSE g, цикл — обозначается: WHILE p DO f,
где f, g — блок-схемы с одним входом и одним выходом, р — условие, THEN, IF, ELSE, WHILE, DO — ключевые слова.
Пояснение. Формула f THEN g означает следующее: сначала выполняется программа f, затем выполняется программа g.
Как отмечает , данная теорема резко контрастирует с обычной (в 1960—1970 годы) практикой программирования, когда наблюдалось массовое использование операторов перехода goto.
Бём и Якопини не употребляли термин «структурное программирование». Тем не менее, доказанную ими теорему (и её последующие вариации у разных авторов) впоследствии стали называть «теоремой о структурном программировании», «структурной теоремой», «теоремой о структурировании»Бутаков Е. А. Методы создания качественного программного обеспечения ЭВМ. — М.: Энергоатомиздат, 1984. — 232с. — С. 114..
Принципы структурного программирования Становление и развитие структурного программирования связано с именем Эдсгера Дейкстры.
Принцип 1. Следует отказаться от использования оператора безусловного перехода goto.
Принцип 2. Любая программа строится из трёх базовых управляющих конструкций: последовательность, ветвление, цикл.
Последовательность — однократное выполнение операций в том порядке, в котором они записаны в тексте программы. Бертран Мейер поясняет: «Последовательное соединение: используйте выход одного элемента как вход к другому, подобно тому, как электронщики соединяют выход сопротивления со входом конденсатора»Мейер Б. Почувствуй класс. Учимся программировать хорошо с объектами и контрактами. — Пер. с англ. — М.: Национальный открытый университет ИНТУИТ: БИНОМ. Лаборатория знаний, 2011. — 775с. — С. 209. — ISBN 978-5-9963-0573-5. Ветвление — однократное выполнение одной из двух или более операций, в зависимости от выполнения заданного условия.