Теорема о структурированной программе - Structured program theorem

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

Теорема о структурированной программе , также называемая теоремой Бема – Якопини , является результатом теории языков программирования . В нем говорится , что класс графов потока управления (исторически называемых блок - схемой в данном контексте) можно вычислить любую вычислимую функцию , если она сочетает в себе подпрограммы всего три конкретных способах ( управляющие структурами ). Эти

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

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

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

Происхождение и варианты

Эта теорема обычно упоминается в статье Коррадо Бема и Джузеппе Якопини, опубликованной в 1966 году . Дэвид Харел писал в 1980 году, что статья Бема – Якопини пользуется «всеобщей популярностью», особенно среди сторонников структурного программирования. Харел также отметил, что «из-за своего довольно технического стиля [статья Бема-Якопини 1966 года], по-видимому, чаще цитируется, чем читается подробно», и, просмотрев большое количество статей, опубликованных до 1980 года, Харел утверждал, что содержание статьи Доказательство Бема – Якопини обычно искажалось как народная теорема, которая по существу содержит более простой результат, результат, который сам по себе можно проследить до зарождения современной теории вычислений в работах фон Неймана и Клини .

Харел также пишет, что более общее название было предложено HD Mills как «Структурная теорема» в начале 1970-х годов.

Однократный цикл, народная версия теоремы

Эта версия теоремы заменяет весь поток управления исходной программы одним глобальным whileциклом, который имитирует счетчик программы, просматривающий все возможные метки (блоки блок-схемы) в исходной неструктурированной программе. Харел проследил происхождение этой народной теоремы до двух статей, положивших начало вычислениям. Одним из них является описание архитектуры фон Неймана в 1946 году , в котором объясняется, как работает счетчик программ с точки зрения цикла while. Харел отмечает, что единственный цикл, используемый народной версией теоремы структурированного программирования, в основном просто обеспечивает операционную семантику для выполнения блок-схемы на компьютере фон Неймана. Другой, даже более старый источник, в котором Харел проследил народную версию теоремы, - это теорема Стивена Клини о нормальной форме от 1936 года.

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

p := 1
while p > 0 do
    if p = 1 then
        perform step 1 from the flowchart
        p := resulting successor step number of step 1 from the flowchart (0 if no successor)
    end if
    if p = 2 then
        perform step 2 from the flowchart
        p := resulting successor step number of step 2 from the flowchart (0 if no successor)
    end if
    ...
    if p = n then
        perform step n from the flowchart
        p := resulting successor step number of step n from the flowchart (0 if no successor)
    end if
end while

Доказательство Бема и Якопини

Доказательство в статье Бема и Якопини проводится индукцией по структуре блок-схемы. Поскольку в нем использовалось сопоставление с образцом в графах , доказательство Бема и Якопини было непрактичным в качестве алгоритма преобразования программ и, таким образом, открыло дверь для дополнительных исследований в этом направлении.

Последствия и уточнения

Доказательство Бема – Якопини не разрешило вопрос о том, следует ли применять структурированное программирование для разработки программного обеспечения, отчасти потому, что конструкция скорее скрывала программу, чем улучшала ее. Напротив, это означало начало дебатов. В 1968 году последовало известное письмо Эдсгера Дейкстры « Перейти к заявлению, которое считается вредным ».

Некоторые ученые придерживались пуристского подхода к результату Бема-Якопини и утверждали, что даже инструкции типа breakи returnиз середины циклов являются плохой практикой, поскольку они не нужны в доказательстве Бема-Якопини, и поэтому они выступали за то, чтобы все циклы имели единый точка выхода. Этот пуристический подход воплощен в языке программирования Паскаль (разработанном в 1968–1969 гг.), Который до середины 1990-х годов был предпочтительным инструментом для преподавания вводных курсов программирования в академических кругах.

Эдвард Йордон отмечает, что в 1970-х годах существовало даже философское противодействие преобразованию неструктурированных программ в структурированные с помощью автоматизированных средств, основанное на аргументе, что нужно мыслить в стиле структурированного программирования с самого начала. Прагматический контраргумент заключался в том, что такие преобразования приносили пользу большому количеству существующих программ. Среди первых предложений по автоматизированному преобразованию была статья Эдварда Эшкрофта и Зохара Манна 1971 года .

Прямое применение теоремы Бема – Якопини может привести к добавлению дополнительных локальных переменных в структурированную диаграмму, а также может привести к некоторому дублированию кода . Последняя проблема в этом контексте называется проблемой полутора петель . На Паскаль влияют обе эти проблемы, и, согласно эмпирическим исследованиям, процитированным Эриком С. Робертсом , студентам-программистам было трудно сформулировать правильные решения на Паскале для нескольких простых задач, включая написание функции для поиска элемента в массиве. Исследование 1980 года Генри Шапиро, цитируемое Робертсом, показало, что при использовании только управляющих структур, предоставленных Паскалем, правильное решение было дано только 20% испытуемых, в то время как ни один из испытуемых не написал неправильный код для этой проблемы, если ему разрешили написать ответ из середина петли.

В 1973 году С. Рао Косараджу доказал, что можно избежать добавления дополнительных переменных в структурное программирование, если разрешены многоуровневые перерывы произвольной глубины из циклов. Более того, Косараджу доказал, что существует строгая иерархия программ, в настоящее время называемая иерархией Косараджу , в которой для каждого целого числа n существует программа, содержащая многоуровневый разрыв глубины n, которую нельзя переписать как программу с многоуровневыми разрывами глубина меньше n (без введения дополнительных переменных). Косараджу ссылается на конструкцию многоуровневого разрыва языка программирования BLISS . Многоуровневые разрывы в форме ключевого слова были фактически введены в версии BLISS-11 этого языка; у оригинального BLISS были только одноуровневые перерывы. Семейство языков BLISS не предоставляло неограниченного goto. Язык программирования Java позже следовать этому подходу , а также. leave label

Более простой результат из статьи Косараджу состоит в том, что программа сводится к структурированной программе (без добавления переменных) тогда и только тогда, когда она не содержит цикла с двумя отдельными выходами. Сводимость была определена Косараджу, грубо говоря, как вычисление одной и той же функции и использование тех же «примитивных действий» и предикатов, что и исходная программа, но, возможно, с использованием других структур потока управления. (Это более узкое понятие сводимости, чем то, что использовал Бём-Якопини.) Вдохновленный этим результатом, в разделе VI своей широко цитируемой статьи, в которой было введено понятие цикломатической сложности , Томас Дж. Маккейб описал аналог теоремы Куратовского для графы потока управления (CFG) неструктурированных программ, то есть минимальные подграфы, которые делают CFG программы неструктурированным. Эти подграфы имеют очень хорошее описание на естественном языке. Они есть:

  1. выход из цикла (кроме теста цикла цикла)
  2. разветвляясь в петлю
  3. переход к решению (то есть к "ответвлению" if)
  4. отклонение от решения

МакКейб фактически обнаружил, что эти четыре графа не являются независимыми, когда появляются как подграфы, а это означает, что необходимое и достаточное условие для того, чтобы программа была неструктурированной, состоит в том, чтобы ее CFG имел в качестве подграфа один из любого подмножества трех из этих четырех графов. Он также обнаружил, что если неструктурированная программа содержит один из этих четырех подграфов, он должен содержать еще один, отличный от набора из четырех. Этот последний результат помогает объяснить, как поток управления неструктурированной программы запутывается в так называемом « спагетти-коде ». Маккейб также разработал числовую меру, которая для произвольной программы количественно определяет, насколько она далека от идеала структурированной программы; Маккейб назвал свою меру существенной сложностью .

Описание МакКейбом запрещенных графов для структурного программирования можно считать неполным, по крайней мере, если D-структуры Дейкстры считаются строительными блоками.

Вплоть до 1990 г. предлагалось довольно много методов удаления goto из существующих программ с сохранением большей части их структуры. Различные подходы к этой проблеме также предлагали несколько понятий эквивалентности, которые являются более строгими, чем просто эквивалентность Тьюринга, чтобы избежать вывода, подобного народной теореме, обсужденной выше. Строгость выбранного понятия эквивалентности диктует минимальный набор необходимых структур потока управления. В статье JACM 1988 г., написанной Лайлом Рэмшоу, до этого момента исследуется месторождение, а также предлагается собственный метод. Алгоритм Ramshaw был использован, например , в некоторых Java декомпиляции , потому что Java виртуальной машины код имеют команды ветвления с целями , выраженных в виде смещений, но высокий уровень Java язык имеет только многоуровневый breakи continueзаявление. Аммаргеллат (1992) предложил метод преобразования, который восходит к принудительному использованию единого выхода.

Приложение к Коболу

В 1980 - е годы IBM исследователь Харлан Миллс курировал развитие COBOL Структурирование фонда , который применяется алгоритм структурирования для COBOL кода. Преобразование Миллса включало следующие шаги для каждой процедуры.

  1. Определите основные блоки в процедуре.
  2. Назначьте уникальную метку пути входа каждого блока и пометьте пути выхода каждого блока метками путей входа, к которым они подключаются. Используйте 0 для возврата из процедуры и 1 для пути входа в процедуру.
  3. Разбейте процедуру на основные блоки.
  4. Для каждого блока, который является адресатом только одного пути выхода, повторно подключите этот блок к этому пути выхода.
  5. Объявите новую переменную в процедуре (для справки она называется L).
  6. На каждый оставшийся неподключенный путь выхода добавьте оператор, который устанавливает L равным значению метки на этом пути.
  7. Объедините полученные программы в оператор выбора, который выполняет программу с меткой пути входа, обозначенной L
  8. Создайте цикл, который выполняет этот оператор выбора, пока L не равно 0.
  9. Создайте последовательность, которая инициализирует L равным 1 и выполняет цикл.

Обратите внимание, что эту конструкцию можно улучшить, преобразовав некоторые случаи оператора выбора в подпроцедуры.

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

использованная литература

дальнейшее чтение

Материал, еще не рассмотренный выше:

  • Де Милло, Ричард А. (1980). "Пространственно-временные компромиссы в структурированном программировании: улучшенная комбинаторная теорема вложения". Журнал ACM . 27 (1): 123–127. DOI : 10.1145 / 322169.322180 .
  • Девьен, Филипп (1994). Достаточно одного бинарного предложения рог . Конспект лекций по информатике. 775 . С. 19–32. CiteSeerX  10.1.1.14.537 . DOI : 10.1007 / 3-540-57785-8_128 . ISBN 978-3-540-57785-0.