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

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

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

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

Элементы

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

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

• "Последовательность"; упорядоченные операторы или подпрограммы, выполняемые последовательно.
• «Отбор»; один или несколько операторов выполняются в зависимости от состояния программы. Обычно это выражается такими ключевыми словами , как if..then..else..endif. Условный оператор должен иметь хотя бы одно истинное условие, и каждое условие должно иметь максимум одну точку выхода.
• «Итерация»; оператор или блок выполняется до тех пор, пока программа не достигнет определенного состояния или пока операции не будут применены к каждому элементу коллекции. Обычно это выражается такими ключевыми словами, как while, repeat, for или do..until. Часто рекомендуется, чтобы каждый цикл имел только одну точку входа (а в исходном структурном программировании также только одну точку выхода, и это предусмотрено некоторыми языками).

Графическое представление трех основных шаблонов — последовательности, выбора и повторения — с использованием диаграмм NS (синий) и блок-схем (зеленый).

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

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

Блоки

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

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

Структурное программирование можно выполнять на любом языке программирования, хотя предпочтительнее использовать что-то вроде процедурного языка программирования . Некоторые из языков, первоначально использовавшихся для структурного программирования, включают: ALGOL , Pascal , PL/I , Ada и RPL, но большинство новых языков процедурного программирования с тех пор включали функции, способствующие структурному программированию, а иногда и намеренно оставляли функции – особенно GOTO – в попытка усложнить неструктурированное программирование .

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

История

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

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

Дебаты

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

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

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

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

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

Результат

К концу 20 века почти все ученые-компьютерщики были убеждены, что изучать и применять концепции структурного программирования полезно. Языки программирования высокого уровня, в которых изначально отсутствовали структуры программирования, такие как FORTRAN , COBOL и BASIC , теперь имеют их.

Распространенные отклонения

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

Ранний выход

Дополнительная информация: Вернитесь раньше.

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

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

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

Большинство современных языков обеспечивают поддержку на уровне языка для предотвращения таких утечек; см. подробное обсуждение в разделе «Управление ресурсами» . Чаще всего это делается с помощью защиты от завершения, которая гарантирует, что определенный код будет гарантированно запущен при выходе из блока; это структурированная альтернатива блоку очистки и goto. Чаще всего это называют try...finally,и считается частью обработки исключений . В случае нескольких return заявления, вводящие try...finally,без исключений может выглядеть странно. Существуют различные методы инкапсуляции управления ресурсами. Альтернативный подход, встречающийся в основном в C++, — это Resource Acquisition Is Initialization , который использует обычное развертывание стека (освобождение переменных) при выходе из функции для вызова деструкторов локальных переменных для освобождения ресурсов.

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

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

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

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

Дополнительная информация: Обработка исключений (программирование).

Основываясь на ошибке кодирования, возникшей в результате катастрофы Ariane 501 , разработчик программного обеспечения Джим Бонанг утверждает, что любые исключения, вызванные функцией, нарушают парадигму единого выхода, и предлагает запретить все межпроцедурные исключения. Бонанг предлагает, чтобы все C++, соответствующие одному выходу, были написаны следующим образом:

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

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

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

В учебнике Лаудена и Ламберта подчеркивается, что обработка исключений отличается от таких конструкций структурного программирования, как while зацикливается, потому что передача управления «настраивается в другой точке программы, чем та, где происходит фактическая передача. В той точке, где передача действительно происходит, может не быть синтаксического указания на то, что управление действительно будет передано». Профессор информатики Арвинд Кумар Бансал также отмечает, что в языках, реализующих обработку исключений, даже такие структуры управления, как for, которые обладают свойством единственного выхода при отсутствии исключений, больше не имеют его при наличии исключений, поскольку исключение может преждевременно вызвать досрочный выход в любой части структуры управления; например, если init() выдает исключение в for (init(); check(); increm()), то обычная точка выхода после check() не достигается. Ссылаясь на многочисленные предыдущие исследования других (1999–2004 гг.) и свои собственные результаты, Уэстли Веймер и Джордж Некула написали, что серьезная проблема с исключениями заключается в том, что они «создают скрытые пути потока управления, о которых программистам трудно рассуждать».

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

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

Дополнительная информация: Сопрограмма

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

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

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

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

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

См. также

• DRAKON
• Минимальная оценка
• Диаграмма Насси – Шнейдермана
• Структурная диаграмма
• Структурированный параллелизм
• Оператор переключения

Ссылки

Источники

• Эдсгер Дейкстра , «Заметки о структурном программировании» , стр. 6.
• Бём, Коррадо ; Якопини, Джузеппе (май 1966 г.). «Блок-схемы, машины Тьюринга и языки только с двумя правилами формирования» (PDF) . Коммуникации АКМ . 9 (5): 366–371. CiteSeerX   10.1.1.119.9119 . дои : 10.1145/355592.365646 . S2CID   10236439 . Архивировано (PDF) из оригинала 23 сентября 2015 г.
• Дейкстра, Эдсгер В. (март 1968 г.). «Письма в редакцию: Перейти к заявлению, признанному вредным» (PDF) . Коммуникации АКМ . 11 (3): 147–148. дои : 10.1145/362929.362947 . ISSN   0001-0782 . S2CID   17469809 .
• Майкл А. Джексон , Принципы разработки программ , Academic Press, Лондон, 1975.
• О.-Ж. Даль , Э. В. Дейкстра , CAR Hoare Structured Programming , Academic Press, Лондон, 1972. ISBN   0-12-200550-3 .
  • этот том включает расширенную версию «Заметок по структурированному программированию» , приведенных выше, включая расширенный пример использования структурированного подхода для разработки алгоритма поиска с возвратом для решения проблемы 8 ферзей .
  • версия в формате pdf находится в серии классических книг ACM.
  • Обратите внимание, что третья глава этой книги, написанная Далем, описывает подход, который легко узнать как объектно-ориентированное программирование. Это можно рассматривать как еще один способ «полезного структурирования» программы, чтобы показать ее правильность.
• Ватт, Дэвид Энтони; Финдли, Уильям (2004). Концепции проектирования языков программирования . Джон Уайли и сыновья. ISBN  978-0-470-85320-7 .

Внешние ссылки

• BPStruct — инструмент для структурирования параллельных систем (программ, моделей процессов).
• Дж. Дарлинтон; М. Ганем; HW To (1993), «Структурированное параллельное программирование», В моделях программирования для компьютеров с массовым параллелизмом. Издательство Компьютерного общества IEEE. 1993 : 160–169, CiteSeerX   10.1.1.37.4610.