Структурированное программирование - Structured programming

Парадигмы программирования

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

Он возник в конце 1950-х годов с появлением АЛГОЛ 58 и АЛГОЛ 60 языки программирования,[1] причем последний включает поддержку блочных структур. Факторы, способствующие его популярности и широкому признанию, сначала в академических кругах, а затем среди практиков, включают открытие того, что сейчас известно как теорема о структурированной программе в 1966 г.,[2] и издание влиятельного "Перейти к заявлению, которое считается вредным "открытое письмо голландского ученого-информатика в 1968 г. Эдсгер В. Дейкстра, который ввел термин «структурное программирование».[3]

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

Элементы

Структуры управления

После теорема о структурированной программе, все программы рассматриваются как состоящие из управляющие структуры:

  • "Последовательность"; упорядоченные операторы или подпрограммы, выполняемые последовательно.
  • «Подборка»; один или несколько операторов выполняется в зависимости от состояния программы. Обычно это выражается с помощью ключевые слова Такие как если..тем..елс..endif.
  • «Итерация»; оператор или блок выполняется до тех пор, пока программа не достигнет определенного состояния или пока операции не будут применены к каждому элементу коллекции. Обычно это выражается такими ключевыми словами, как пока, повторение, за или же делать .. пока. Часто рекомендуется, чтобы у каждого цикла была только одна точка входа (а в исходном структурном программировании также только одна точка выхода, и несколько языков это обеспечивают).
  • «Рекурсия»; оператор выполняется путем многократного вызова самого себя до тех пор, пока не будут выполнены условия завершения. Хотя на практике они похожи на итерационные циклы, рекурсивные циклы могут быть более эффективными с точки зрения вычислений и по-разному реализованы как каскадный стек.
Графическое представление три основных шаблона - последовательность, выбор и повторение - использование Диаграммы NS (синий) и блок-схемы (зеленый).

Подпрограммы

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

Блоки

Блоки используются для того, чтобы группы операторов можно было обрабатывать, как если бы они были одним оператором. Блочно-структурированный у языков есть синтаксис для включения структур некоторым формальным образом, например, оператор if, заключенный в скобки если..фи как в АЛГОЛ 68, или раздел кода в квадратных скобках НАЧАТЬ..END, как в PL / I и Паскаль, пробел отступ, как в Python - или фигурные скобки {...} из C и многие более поздние языки.

Структурированные языки программирования

Структурированное программирование можно выполнять на любом языке программирования, хотя предпочтительнее использовать что-то вроде процедурный язык программирования. Некоторые из языков, изначально использовавшихся для структурного программирования, включают: АЛГОЛ, Паскаль, PL / I и Ада, но с тех пор большинство новых процедурных языков программирования включают функции, способствующие структурированному программированию, а иногда и намеренно не учитывают функции - особенно GOTO - в попытке сделать неструктурированное программирование труднее.Структурированное программирование (иногда известное как модульное программирование[нужна цитата ]) обеспечивает логическую структуру в написанной программе, чтобы сделать ее более эффективной и легкой для понимания и модификации.


История

Теоретическая основа

В теорема о структурированной программе обеспечивает теоретические основы структурного программирования. В нем говорится, что трех способов комбинирования программ - последовательности, выбора и итерации - достаточно, чтобы выразить любую вычислимая функция. Это наблюдение не связано с движением структурного программирования; этих структур достаточно для описания цикл обучения из центральное процессорное устройство, а также работу Машина Тьюринга. Следовательно, процессор всегда выполняет «структурированную программу» в этом смысле, даже если инструкции, которые он считывает из памяти, не являются частью структурированной программы. Однако авторы обычно приписывают результат работе Бема и Якопини 1966 года, возможно потому, что Dijkstra цитировал эту статью сам.[4] Теорема о структурированной программе не касается написания и анализа хорошо структурированной программы. Эти вопросы были рассмотрены в конце 1960-х - начале 1970-х годов, при этом значительный вклад внесли Dijkstra, Роберт В. Флойд, Тони Хоар, Оле-Йохан Даль, и Дэвид Грис.

Дебаты

П. Дж. Плаугер, первых компаний, внедривших структурированного программирования, описал свою реакцию на теорему о структурированной программе:

Американские новообращенные подбрасывали эту интересную новость перед носом неподготовленных программистов на ассемблере, которые продолжали выдвигать извилистые кусочки логики и говорить: «Я уверен, что не могу это структурировать». Ни доказательство Бема и Якопини, ни наши неоднократные успехи в написании структурированного кода не привели их к существованию на один день раньше, чем они были готовы убедить себя.[5]

Дональд Кнут принял принцип, что программы должны быть написаны с учетом доказуемости, но он не согласен (и все еще не согласен[нужна цитата ]) с отменой оператора GOTO. В своей статье 1974 г. «Структурированное программирование с помощью операторов Goto»,[6] он привел примеры, в которых он считал, что прямой переход ведет к более ясному и эффективному коду без ущерба для доказуемости. Кнут предложил более слабое структурное ограничение: должна быть возможность рисовать программы блок-схема со всеми передними ветвями слева, всеми задними ветвями справа и без пересекающих друг друга ветвей. Многие из тех, кто разбирается в компиляторы и теория графов выступали за разрешение только приводимые потоковые графы[когда определяется как? ].[ВОЗ? ]

Теоретики структурного программирования приобрели главного союзника в 1970-х годах после того, как IBM Исследователь Харлан Миллс применил свою интерпретацию теории структурного программирования к разработке системы индексации для Нью-Йорк Таймс файл исследования. Проект имел большой инженерный успех, и менеджеры других компаний ссылались на него в поддержку принятия структурного программирования, хотя Дейкстра критиковал то, как интерпретация Миллса отличалась от опубликованной работы.[нужна цитата ]

Даже в 1987 году еще можно было поднять вопрос о структурном программировании в журнале по информатике. Фрэнк Рубин сделал это в том же году с открытым письмом, озаглавленным «GOTO считается вредным» считается вредным.[7] Последовали многочисленные возражения, в том числе ответ Дейкстры, в котором резко критиковался как Рубин, так и уступки, на которые пошли другие писатели, отвечая ему.

Исход

К концу 20-го века почти все компьютерные ученые были убеждены, что полезно изучать и применять концепции структурного программирования. Языки программирования высокого уровня, в которых изначально отсутствовали структуры программирования, такие как FORTRAN, КОБОЛ, и БАЗОВЫЙ, теперь есть они.

Общие отклонения

В то время как goto в настоящее время в значительной степени заменен структурированными конструкциями выбора (if / then / else) и повторения (while и for), немногие языки являются чисто структурированными. Наиболее распространенное отклонение, встречающееся во многих языках, - это использование заявление о возврате для досрочного выхода из подпрограммы. Это приводит к нескольким точкам выхода вместо одной точки выхода, требуемой структурным программированием. Существуют и другие конструкции для обработки случаев, которые неудобны в чисто структурном программировании.

Ранний выход

Наиболее частым отклонением от структурного программирования является ранний выход из функции или цикла. На уровне функций это возвращаться утверждение. На уровне петель это перемена оператор (завершить цикл) или Продолжить оператор (завершить текущую итерацию, перейти к следующей итерации). В структурированном программировании их можно воспроизвести путем добавления дополнительных ветвей или тестов, но для результатов вложенного кода это может значительно усложнить работу. C является ранним и ярким примером этих конструкций. В некоторых новых языках также есть «помеченные разрывы», которые позволяют выйти не только из самого внутреннего цикла. Исключения также допускают ранний выход, но имеют дополнительные последствия, поэтому они рассматриваются ниже.

Множественные выходы могут возникать по разным причинам, чаще всего из-за того, что у подпрограммы больше нет работы (если она возвращает значение, вычисление завершено), или из-за «исключительных» обстоятельств, которые препятствуют ее продолжению, следовательно, необходимо Обработка исключений.

Наиболее распространенная проблема при раннем выходе заключается в том, что операторы очистки или final не выполняются - например, выделенная память не освобождается или открытые файлы не закрываются, что приводит к утечки памяти или же утечки ресурсов. Это необходимо делать на каждом сайте возврата, который является хрупким и может легко привести к ошибкам. Например, в более поздней разработке разработчик мог упустить из виду оператор return и действие, которое должно быть выполнено в конце подпрограммы (например, след заявление) может выполняться не во всех случаях. Языки без оператора возврата, например стандартные Паскаль и Семя7, нет этой проблемы.

Большинство современных языков обеспечивают поддержку на уровне языка для предотвращения таких утечек;[8] см. подробное обсуждение на Управление ресурсами. Чаще всего это делается с помощью защиты от размотки, которая гарантирует, что определенный код будет гарантированно запускаться, когда выполнение выходит из блока; это структурированная альтернатива блоку очистки и идти к. Это чаще всего известно как попробуй ... наконец, и считался частью Обработка исключений. В случае нескольких возвращаться заявления, вводящие попробуй ... наконец, без исключения может выглядеть странно. Существуют различные методы инкапсуляции управления ресурсами. Альтернативный подход, встречающийся в основном в C ++, - это Приобретение ресурсов - это инициализация, который использует обычное разворачивание стека (освобождение переменных) при выходе из функции для вызова деструкторов локальных переменных для освобождения ресурсов.

Кент Бек, Мартин Фаулер и соавторы утверждали в своих рефакторинг книги, в которых вложенные условные выражения могут быть труднее для понимания, чем определенный тип более плоской структуры, использующей несколько выходов, обусловленных охранные оговорки. В их книге 2009 года категорически утверждается, что «одна точка выхода на самом деле не является полезным правилом. Ясность - ключевой принцип: если метод более ясен с одной точкой выхода, используйте одну точку выхода; в противном случае - нет». Они предлагают решение для преобразования функции, состоящей только из вложенных условных выражений, в последовательность защищенных операторов return (или throw), за которыми следует один неохраняемый блок, который предназначен для содержания кода для общего случая, в то время как защищенные операторы являются предполагается, что нужно иметь дело с менее распространенными (или с ошибками).[9] Херб Саттер и Андрей Александреску в своей книге советов по C ++ 2004 г. также утверждают, что единственная точка выхода является устаревшим требованием.[10]

В своем учебнике 2004 г. Дэвид Ватт пишет, что «часто желательны потоки управления с одним входом и несколькими выходами». Используя концепцию Теннента секвенсор Ватт единообразно описывает конструкции потока управления, встречающиеся в современных языках программирования, и пытается объяснить, почему определенные типы секвенсоров предпочтительнее других в контексте потоков управления с несколькими выходами. Ватт пишет, что неограниченные переходы (секвенсоры перехода) - это плохо, потому что назначение перехода не является самоочевидным для читателя программы, пока читатель не найдет и не изучит фактическую метку или адрес, являющийся целью перехода. В отличие от этого, Ватт утверждает, что концептуальная цель секвенсора возврата ясна из его собственного контекста, без необходимости исследовать его назначение. Ватт пишет, что класс секвенсоров, известный как escape-последовательности, определяемый как «секвенсор, который завершает выполнение команды или процедуры, содержащей текст», включает как разрывы из циклов (включая многоуровневые разрывы), так и операторы возврата. Ватт также отмечает, что, хотя секвенсоры переходов (gotos) были в некоторой степени ограничены в таких языках, как C, где цель должна быть внутри локального блока или охватывающим внешним блоком, одного этого ограничения недостаточно, чтобы сделать намерение gotos в C самим собой. -описание и чтобы они все еще могли производить »код спагетти ". Ватт также исследует, чем секвенсоры исключений отличаются от секвенсоров перехода и перехода; это объясняется в следующем разделе этой статьи.[11]

В отличие от вышеизложенного, Бертран Мейер написал в своем учебнике 2009 года, что инструкции вроде перемена и Продолжить "просто старые идти к в овечьей шкуре »и категорически не рекомендует их использовать.[12]

Обработка исключений

На основе ошибки кодирования из Катастрофа Ariane 501, разработчик программного обеспечения Джим Бонанг утверждает, что любые исключения, создаваемые функцией, нарушают парадигму единственного выхода, и предлагает запретить все межпроцедурные исключения. В синтаксисе C ++ это делается путем объявления всех сигнатур функций как нет кроме (начиная с C ++ 11) или бросать().[13] Бонанг предлагает, чтобы весь C ++, соответствующий единственному выходу, был написан следующим образом:

bool MyCheck1() бросать() {  bool успех = ложный;  пытаться {    // Делаем что-нибудь, что может вызвать исключения.    если (!MyCheck2()) {      бросать SomeInternalException();    }    // Другой код, аналогичный приведенному выше.    успех = истинный;  } ловить (...) {    // Все исключения пойманы и зарегистрированы.  }  возвращаться успех;}

Питер Ричи также отмечает, что в принципе даже один бросать прямо перед возвращаться в функции представляет собой нарушение принципа единственного выхода, но утверждает, что правила Дейкстры были написаны до того, как обработка исключений стала парадигмой в языках программирования, поэтому он предлагает разрешить любое количество точек выброса в дополнение к одной точке возврата . Он отмечает, что решения, которые обертывают исключения ради создания единого выхода, имеют более высокую глубину вложенности и, следовательно, их труднее понять, и даже обвиняет тех, кто предлагает применять такие решения к языкам программирования, которые поддерживают исключения участия в культ карго мышление.[14]

Дэвид Ватт также анализирует обработку исключений в рамках секвенсоров (представленных в этой статье в предыдущем разделе о ранних выходах). Ватт отмечает, что ненормальная ситуация (обычно проявляющаяся арифметическим переполнением или ошибками ввода / вывода, такими как файл не найден) является своего рода ошибки, которая «обнаружена в некоторой программной единице низкого уровня, но [для которой] обработчик более естественно расположен в программной единице высокого уровня». Например, программа может содержать несколько вызовов для чтения файлов, но действие, которое нужно выполнить, когда файл не найден, зависит от значения (цели) файла, о котором идет речь в программе, и, следовательно, процедура обработки этой ненормальной ситуации не может быть находится в системном коде нижнего уровня. Уоттс далее отмечает, что введение тестирования флагов состояния в вызывающей программе, как это повлечет за собой структурированное программирование с одним выходом или даже секвенсоры возврата (с несколькими выходами), приводит к ситуации, когда «код приложения имеет тенденцию загромождаться тестами флагов состояния» и что «программист может по забывчивости или лениво пропустить проверку флага состояния. Фактически, ненормальные ситуации, представленные флагами состояния, по умолчанию игнорируются!» Он отмечает, что в отличие от тестирования флагов состояния, исключения имеют обратное поведение по умолчанию, в результате чего программа завершается, если программист явно не обрабатывает исключение каким-либо образом, возможно, путем добавления кода для его преднамеренного игнорирования. Основываясь на этих аргументах, Ватт заключает, что секвенсоры перехода или управляющие секвенсоры (обсуждаемые в предыдущем разделе) не так подходят, как выделенный секвенсор исключений с семантикой, описанной выше.[15]

В учебнике Лаудена и Ламберта подчеркивается, что обработка исключений отличается от таких структур структурного программирования, как пока циклы, потому что передача управления «устанавливается в другой точке программы, чем та, где происходит фактическая передача. В точке, где передача фактически происходит, может не быть синтаксического указания того, что управление действительно будет передано».[16] Профессор информатики Арвинд Кумар Бансал также отмечает, что в языках, реализующих обработку исключений, даже управляющие структуры, такие как за, которые имеют свойство единого выхода при отсутствии исключений, больше не имеют его при наличии исключений, потому что исключение может преждевременно вызвать ранний выход в любой части структуры управления; например, если в этом() выдает исключение в для (инициализация (); проверка (); инкремент ()), то обычная точка выхода после check () не достигается.[17] Ссылаясь на многочисленные предыдущие исследования других авторов (1999-2004 гг.) И их собственные результаты, Westley Weimer и Джордж Некула писали, что серьезная проблема с исключениями заключается в том, что они «создают скрытые пути потока управления, о которых программистам трудно рассуждать».[18]:8:27

Необходимость ограничить код точками единственного выхода появляется в некоторых современных средах программирования, ориентированных на параллельные вычисления, таких как OpenMP. Различные параллельные конструкции из OpenMP, например параллельно делать, не допускайте преждевременных выходов изнутри наружу параллельной конструкции; это ограничение включает в себя все виды выходов из перемена в исключения C ++, но все они разрешены внутри параллельной конструкции, если цель перехода также находится внутри нее.[19]

Множественная запись

Дальнейшая информация: Coroutine

Реже подпрограммы позволяют несколько Вход. Чаще всего это только повторно-вход в сопрограмма (или же генератор / semicoroutine), где подпрограмма выдает управление (и, возможно, значение), но затем может быть возобновлена ​​с того места, где она остановилась. Есть ряд общее использование такого программирования, особенно для потоки (особенно ввод / вывод), конечные автоматы и параллелизм. С точки зрения выполнения кода выход из сопрограммы ближе к структурированному программированию, чем возврат из подпрограммы, поскольку подпрограмма фактически не завершилась и продолжится при повторном вызове - это не ранний выход. Однако сопрограммы означают, что несколько подпрограмм имеют состояние выполнения, а не один стек вызовов подпрограмм, и, таким образом, вводят другую форму сложности.

Подпрограммы очень редко позволяют вход в произвольную позицию в подпрограмме, так как в этом случае состояние программы (например, значения переменных) неинициализировано или неоднозначно, и это очень похоже на goto.

Государственные машины

Некоторые программы, в частности парсеры и протоколы связи, иметь ряд состояния которые следуют друг за другом способом, который нелегко свести к базовым структурам, и некоторые программисты реализуют изменения состояния с переходом в новое состояние. Этот тип переключения состояний часто используется в ядре Linux.[нужна цитата ]

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

Смотрите также

Рекомендации

Цитаты

  1. ^ Кларк, Лесли Б. Уилсон, Роберт Дж .; Роберт, Кларк (2000). Сравнительные языки программирования (3-е изд.). Харлоу, Англия: Эддисон-Уэсли. п. 20. ISBN  9780201710120. В архиве из оригинала 26 ноября 2015 г.. Получено 25 ноября 2015.
  2. ^ Бом, Коррадо; Джузеппе Якопини (май 1966 г.). «Блок-схемы, машины Тьюринга и языки только с двумя правилами формирования» (PDF). Коммуникации ACM. 9 (5): 366–371. CiteSeerX  10.1.1.119.9119. Дои:10.1145/355592.365646. S2CID  10236439. В архиве (PDF) из оригинала от 23.09.2015.
  3. ^ Дейкстра 1968, "Необузданное использование оператора go to сразу же приводит к тому, что становится ужасно трудно найти значимый набор координат, в которых можно было бы описать ход процесса ... Оператор go to в его нынешнем виде слишком примитивен, это слишком большое приглашение испортить свою программу ».
  4. ^ Дейкстра, Э. В. (март 1968 г.). «Письма в редакцию: перейти к заявлению, признанному вредным». Коммуникации ACM. 11 (3): 147–148. Дои:10.1145/362929.362947. ISSN  0001-0782. S2CID  17469809.
  5. ^ Плаугер, П. Дж. (12 февраля 1993 г.). Программирование по назначению, Очерки по дизайну программного обеспечения (1-е изд.). Прентис-Холл. п.25. ISBN  978-0-13-721374-0.
  6. ^ Дональд Кнут - Структурированное программирование с операторами перехода В архиве 2013-10-23 на Wayback Machine
  7. ^ Франк Рубин (март 1987 г.). ""GOTO Считается вредным "Считается вредным" (PDF). Коммуникации ACM. 30 (3): 195–196. Дои:10.1145/214748.315722. S2CID  6853038. Архивировано из оригинал (PDF) на 20.03.2009.
  8. ^ Старейшина, Джексон и Либлит, 2008 г..
  9. ^ Джей Филдс; Шейн Харви; Мартин Фаулер; Кент Бек (2009). Рефакторинг: Ruby Edition. Pearson Education. С. 274–279. ISBN  978-0-321-60350-0.
  10. ^ Херб Саттер; Андрей Александреску (2004). Стандарты программирования C ++: 101 правила, рекомендации и передовые методы. Pearson Education. ISBN  978-0-13-265442-5. "Пример 4: Одна запись, один выход (" SESE "). Исторически некоторые стандарты кодирования требовали, чтобы каждая функция имела ровно один выход, что означает один оператор возврата. Такое требование устарело в языках, поддерживающих исключения и деструкторы, где функции обычно имеют множество неявных выходов. ")
  11. ^ Дэвид Энтони Уотт; Уильям Финдли (2004). Концепции проектирования языков программирования. Джон Вили и сыновья. С. 215–221. ISBN  978-0-470-85320-7.
  12. ^ Бертран Мейер (2009). Touch of Class: учимся хорошо программировать с объектами и контрактами. Springer Science & Business Media. п. 189. ISBN  978-3-540-92144-8.
  13. ^ «PragPub, апрель 2012 г. - Прагматическая защита - Прагматическая книжная полка». pragprog.com. В архиве с оригинала 10 июля 2017 г.. Получено 6 мая 2018.
  14. ^ «Единый вход, единственный выход, должно ли это все еще применяться в объектно-ориентированных языках? - Блог Питера Ричи MVP». В архиве из оригинала от 14.11.2012. Получено 2014-07-15.
  15. ^ Дэвид Энтони Уотт; Уильям Финдли (2004). Концепции проектирования языков программирования. Джон Вили и сыновья. С. 221–222. ISBN  978-0-470-85320-7.
  16. ^ Кеннет К. Лауден; Кеннет А. Ламберт (2011). Языки программирования: принципы и практика (3-е изд.). Cengage Learning. п. 423. ISBN  978-1-111-52941-3.
  17. ^ Арвинд Кумар Бансал (2013). Введение в языки программирования. CRC Press. п. 135. ISBN  978-1-4665-6514-2.
  18. ^ Weimer, W & Necula, G.C. (2008). «Исключительные ситуации и надежность программы» (PDF). Транзакции ACM по языкам и системам программирования. 30 (2). В архиве (PDF) из оригинала от 23.09.2015.
  19. ^ Рохит Чандра (2001). Параллельное программирование в OpenMP. Морган Кауфманн. п. 45. ISBN  978-1-55860-671-5.

Источники

внешняя ссылка

  • BPStruct - Инструмент для структурирования параллельных систем (программ, моделей процессов)
  • Дж. Дарлинтон; М. Ганем; H. W. To (1993), "Структурированное параллельное программирование", В моделях программирования для массивно параллельных компьютеров. Издательство IEEE Computer Society Press. 1993 г.: 160–169, CiteSeerX  10.1.1.37.4610