Изначально я хотел назвать статью как нибудь вызывающе, например, "Как наука может превращаться в религию", "В ловушке искажений смыслов структурного программирования" или "О чем вам забыли рассказать про структурное программирование", но в результате все же оставил текущее название и надеюсь, оно не вызывает раздражения у читателей. И хотя другие заголовки являются более кликбейтными, тем не менее они все же в больше степени отражают смысл статьи, чем нейтральные "размышления".
А поводом к этой статье послужил один из комментариев к предыдущей публикации Управление памятью и разделяемыми ресурсами без ошибок, где написали "было доказано математически". А я сразу вспомнил свое небольшое расследование, когда пытался разобраться в одном из "математических доказательств", про которое нам всем рассказывают еще в школе на уроках информатики.
Все наверно помнят, что любой алгоритм можно представить в виде трех видов алгоритмических конструкций, следование, ветвление и повторения? А иногда еще добавляют, что эту теорему выдвинул и доказал Э. Дейкстра в 70-х гг. прошлого века, в том числе, включая широко распиаренный якобы запрет на использование операторов goto.
Структурное программирование
Структурное программирование – это концепция, появившаяся в конце 1960-х годов и повлиявшая на дальнейшее развитие императивного программирования. Основоположником структурного программирования считается Эдсгер Дейкстра. Его заслуга состоит не только в разработке этой концепции, но и в ее продвижении.
Основные принципы структурного программирования Эдсгер Дейкстра сформулировал главным образом в Dahl, O.-J., Dijkstra, E.W., Hoare, C.A.R. Structured Programming.
Однако разрабатывая лексику для своего языка программирования у меня неоднократно возникали некоторые сомнения в достоверности этих фактов. Ведь в данную концепцию (что любой алгоритм можно представить в виде трех видов алгоритмических конструкций), совсем не вписывается обработка исключений и некоторые другие элементы, которые являются практически обязательными для всех современных языков программирования.
В поисках правды
Поэтому я решил разобраться с доказательством Э. Дейкстра и найденные результаты меня очень удивили. Все вышло как про ученого, который изнасиловал журналиста или в более толерантное в анекдоте: "Не Кац, а Рабинович. Не в лотерею, а в карты. Не миллион, а сто рублей. И не выиграл, а проиграл".
Другими словами, все оказалось совсем не так. Отсутствует контекст, который необходим для правильного понимания этой информации, структурную теорему опубликовал и доказал вовсе не Э. Дейкстра и много чего еще, что кардинально меняет представления о некоторых вопросах, связанных со структурным программированием. А так как это фактически обязательная база, которая используется в школе при обучении основам программирования, то я думаю, что необходимо сорвать покровы рассказать про найденные факты.
Начал я с того, что попробовал найти первоисточник публикации в котором Э. Дейкстра выдвинул и доказал теорему о достаточности трех алгоритмических конструкций. И не нашел. Но в процессе поиска наткнулся на подробную статью с анализом интересующей меня информации и ссылками на первоисточники: Авачева Т. Г., Пруцков А. В. Современный взгляд на концепцию структурного программирования
Выводы
В результате получились вот таки итоги моего поиска:
- Структурная теорема о том, что любую блок-схему можно преобразовать в блок-схему, состоящую из блоков трех видов: следование, выбор и повторение доказали в 1966 году итальянские ученые К. Бём и Дж. Якопини (на итальянском языке статья была опубликована в 1965 году) Теорема Бёма — Якопини — Википедия. Данная теорема чисто теоретическая, доказана с учетом некоторых ограничений и была упомянута Э. Дейкстрой, в его работе "Go To Statement Considered Harmful".
- Принципы структурного программирования предложенные Э. Дейкстрой предназначены для улучшения стиля программного кода за счёт использования структур управления и отказа от других инструкций, управляющих ходом алгоритма, т.е. это не доказанная теорема, только предложение отказаться от использования, причем не только от оператора goto, но и от оператора присвоения значения: "Оператор goto позволяет нам посредством перехода назад повторить часть программы, тогда как оператор присвоения может создать необходимое различие в состоянии между последовательными повторениями."
- Э. Дейкстра в своей работе формулировал принципы структурного программирования в попытке автоматизировать доказательства правильности программ (программа – это последовательность вычислений. Вычисления можно записать математическими формулами. Следовательно, можно доказать теорему о правильности программы), но все же финальный вывод «Тестирование выявляет только наличие, но никак не отсутствие ошибок».
- Кроме трех видов алгоритмических конструкций (следования, ветвления и повторения) требуется еще механизм обработки ошибок (исключений), а иногда обработка прерываний и выполнение параллельных действий, без которых полноценная реализация отдельных алгоритмов будет невозможна.
З.Ы.
С наступающим Новым Годом!
Автор: Александр Рябиков
