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

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

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

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

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

Происхождение и варианты [ править ]

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

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

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

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

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

р  : =  1 , а  р  >  0  делать ,  если  р  =  1 ,  то  выполнить  шаг  1  из  в  блок - схемы  р  : =  результирующий  преемник  шага  число  на  шаге  1  из  в  блок - схеме  ( 0 ,  если  нет  правопреемником )  конец ,  если ,  если  р  =  2 ,  то  выполнить  шаг  2  из  блок - схема последовательности р : =    в результате чего  преемник  шаг  номер  на  этапе  2  из  на  блок - схеме  ( 0 ,  если  нет  преемника )  конца ,  если  ... ,  если  р  =  п ,  то  выполнить  шаг  п  от  на  блок - схемы  р  : = в  результате чего  преемник  шаг  номер  на  этапе  п  от  в  блок - схеме  ( 0 ,  если  нет  преемника )  конец,  если конец пока

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

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

Последствия и уточнения [ править ]

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

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

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

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

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

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

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

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

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

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

Приложение к Cobol [ править ]

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

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

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

См. Также [ править ]

  • Структурированное программирование
  • Полнота по Тьюрингу

Ссылки [ править ]

  1. ^ a b c Декстер Козен и Вей-Лунг Дастин Ценг (2008). Теорема Бёма – Якопини неверна, пропозиционально (PDF) . Мпк 2008 . Конспект лекций по информатике. 5133 . С. 177–192. CiteSeerX  10.1.1.218.9241 . DOI : 10.1007 / 978-3-540-70594-9_11 . ISBN 978-3-540-70593-2.
  2. ^ "CSE 111, осень 2004, ТЕОРЕМА БОЭМА-ЯКОПИНИ" . Cse.buffalo.edu. 2004-11-22 . Проверено 24 августа 2013 .
  3. ^ a b c d e f g h Харел, Дэвид (1980). «О народных теоремах» (PDF) . Коммуникации ACM . 23 (7): 379–389. DOI : 10.1145 / 358886.358892 .
  4. ^ Бом, Коррадо; Джузеппе Якопини (май 1966 г.). «Блок-схемы, машины Тьюринга и языки только с двумя правилами формирования». Коммуникации ACM . 9 (5): 366–371. CiteSeerX 10.1.1.119.9119 . DOI : 10.1145 / 355592.365646 . 
  5. ^ Дональд Кнут (1974). «Структурированное программирование с переходом к операторам». Вычислительные обзоры . 6 (4): 261–301. CiteSeerX 10.1.1.103.6084 . DOI : 10.1145 / 356635.356640 . 
  6. ^ Брюс Ян Миллс (2005). Теоретическое введение в программирование . Springer. п. 279. ISBN 978-1-84628-263-8.
  7. ^ a b Аммаргеллат, З. (1992). «Алгоритм нормализации потока управления и его сложность». IEEE Transactions по разработке программного обеспечения . 18 (3): 237–251. DOI : 10.1109 / 32.126773 .
  8. ^ Дейкстра, Эдсгер (1968). «Перейти к заявлению, которое считается вредным» . Коммуникации ACM . 11 (3): 147–148. DOI : 10.1145 / 362929.362947 . Архивировано из оригинала на 2007-07-03.
  9. ^ a b Робертс, Э. [1995] « Выходы из цикла и структурированное программирование: возобновление дискуссии », Бюллетень ACM SIGCSE, (27) 1: 268–272.
  10. ^ EN Yourdon (1979). Классика программной инженерии . Yourdon Press. С.  49–50 . ISBN 978-0-917072-14-7.
  11. ^ Эшкрофт, Эдвард; Зохар Манна (1971). «Перевод программ перехода в программы« пока »». Материалы Конгресса ИФИП . Статья, которую трудно найти в исходных материалах конференции из-за их ограниченного распространения, была переиздана в книге Йордона 1979 года, стр. 51-65.
  12. ^ Дэвид Энтони Уотт; Уильям Финдли (2004). Концепции проектирования языков программирования . Джон Вили и сыновья. п. 228 . ISBN 978-0-470-85320-7.
  13. ^ Кеннет С. Лауден; Кеннет А. Ламберт (2011). Языки программирования: принципы и практика (3-е изд.). Cengage Learning. стр.  422 -423. ISBN 978-1-111-52941-3.
  14. ^ КОСАРАЮ, С. РАО. «Анализ структурированных программ», Учеб. Пятый ежегодный сироп ACM. Теория вычислений (май 1973 г.), 240–252; также Косараджу, С. Рао (1974). «Анализ структурированных программ». Журнал компьютерных и системных наук . 9 : 232–255. DOI : 10.1016 / S0022-0000 (74) 80043-7 .цитируется Дональдом Кнутом (1974). «Структурированное программирование с переходом к операторам». Вычислительные обзоры . 6 (4): 261–301. CiteSeerX 10.1.1.103.6084 . DOI : 10.1145 / 356635.356640 . 
  15. ^ Брендер, Рональд Ф. (2002). «Язык программирования BLISS: история» (PDF) . Программное обеспечение: практика и опыт . 32 (10): 955–981. DOI : 10.1002 / spe.470 .
  16. ↑ Оригинальная статья - Томас Дж. МакКейб (декабрь 1976 г.). «Мера сложности» . IEEE Transactions по разработке программного обеспечения . SE-2 (4): 315–318. DOI : 10.1109 / tse.1976.233837 .Дополнительную информацию см. В Paul C. Jorgensen (2002). Тестирование программного обеспечения: подход мастера, второе издание (2-е изд.). CRC Press. С. 150–153. ISBN 978-0-8493-0809-3.
  17. Перейти ↑ Williams, MH (1983). «Блок-схемы и проблема номенклатуры» . Компьютерный журнал . 26 (3): 270–276. DOI : 10.1093 / comjnl / 26.3.270 .
  18. ^ Ramshaw, Л. (1988). «Устранение перебоев при сохранении структуры программы». Журнал ACM . 35 (4): 893–920. DOI : 10.1145 / 48014.48021 .
  19. ^ Годфри Нолан (2004). Декомпиляция Java . Апресс. п. 142. ISBN. 978-1-4302-0739-9.
  20. ^ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf
  21. ^ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf

Дальнейшее чтение [ править ]

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

  • Де Милло, Ричард А. (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.