Авачева Т. Г., Пруцков А. В. Современный взгляд на концепцию структурного программирования: статья

Аннотация

Структурное программирование – это концепция, появившаяся в конце 1960-х годов и повлиявшая на дальнейшее развитие императивного программирования. Однако многие идеи этой концепции с тех пор были искажены. В статье анализируются работы Э. Дейкстры, Х. Миллса и Э. Йодана по структурному программированию. Приводятся состояние программирования середины 1970-х годов и примеры. Выявлены идеи, появившиеся во времена структурного программирования (уровни абстракции, скрытие деталей, сцепление и связность) и получившие развитие в последующих концепциях, например, объектно-ориентированном программировании. Показано, что доказательство правильности программ не было доведено до практического применения и осталось теоретическим положением структурного программирования. Проведено сравнение стиля программирования середины 1970-х годов и современного стиля программирования, выделены советы, свойственные обоим стилям. Сделан вывод, что структурное программирование повлияло на современные концепции и методы программирования.

Библиографическая ссылка

Авачева Т. Г., Пруцков А. В. Современный взгляд на концепцию структурного программирования // Cloud of Science. — 2019. — Т. 6. — № 4. — С. 646–665.

Отправить сообщение автору

Контактная информация

Текст статьи

Введение

При исследовании эволюции концепций императивного программирования были проанализированы публикации конца 1960-х – 1970-х годов, посвященные структурному программированию. Анализ публикаций позволил сформировать современный взгляд на эту концепцию, который будет изложен далее.

Что повлияло на появление структурного программирования

Программное обеспечение постоянно «догоняет» аппаратное обеспечение на всем протяжении их существования. Как только аппаратное обеспечение предоставляет новые возможности, они тот час используются для написания более функциональных программ. Такая ситуация сложилась к середине 1960-х. Однако воспользоваться новыми возможностями компьютерных систем программистам препятствовали устаревшие методы программирования, не позволявшие разрабатывать программы более высокого уровня сложности. Поэтому возникла необходимость в разработке новых методов программирования более сложных программных систем.

Цель и структура статьи

Целью статьи является формирование современного, неискаженного временем взгляда на структурное программирование и определение значения этой концепции для современного программирования.

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

Бо́льшая часть работ по структурному программированию была опубликована на английском языке. У работ, переведенных на русский язык, в библиографическое описание добавлено исходное издание. Это позволит проследить хронологию исходных публикаций, так как их переводы издавались спустя несколько лет. Кроме того, библиографический список может служить кратким справочником переводов работ по структурному программированию.

Статьи такого плана субъективны. Чтобы повысить объективность изложения приводятся цитаты, позволяющие беспристрастно взглянуть на программирование 1970-х годов. Цитаты взяты из переводных изданий.

Структурная теорема Бёма-Якопини

В 1966 году итальянские ученые К. Бём и Дж. Якопини опубликовали статью [1] (на итальянском языке статья была опубликована в 1965 году), в которой была доказана теорема, называемая также структурной. Теорема утверждала, что любую блок-схему можно преобразовать в блок-схему, состоящую из блоков трех видов: следование, выбор и повторение. Как следует из названия статьи, структурная теорема расширяла теорию машины Тьюринга и к алгоритмическим языкам отношения не имела. Статья не привлекала внимание до тех пор, пока структурное программирование не стало доминирующей концепцией программирования [2] (таблица 1).

Число цитирований статьи Бёма и Якопини по данным Академии Google (https://scholar.google.com) на момент написания статьи
ПериодЧисло цитирований
1966-196915
1970-197216
1973-197588
1976-197994
1980-1989185
1990-1999212
2000-2009215
2010-2018311
Всего1136

В 1968 году статья Бёма и Якопини была упомянута Э. Дейкстрой, основоположником структурного программирования, в его знаменитой работе [3]. Дейкстра осторожно использовал структурную теорему как подтверждение своих доводов против использования оператора goto.

В результате статья Бёма и Якопини стала восприниматься как фундаментальная основа структурного программирования. Например, в статье [4] исследовались блок-схемы, использованные Бёмом и Якопини, как один из классов структурных программ. Д. Кнут писал, что недавний интерес к структурному программированию привел к цитированию результата, полученного Бёмом и Якопини как значительного прорыва и краеугольного камня современного программирования; однако, по мнению Купера, а позже Бруно и Штайглица, структурная теорема с практической точки зрения бессмысленна [5].

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

Авторы структурной теоремы в русскоязычных переводах книг [2, 6] именуются как Бом и Джакопини. Для точной транслитерации имен собственных необходимо использовать специальные справочники. Согласно справочнику [7], фамилии авторов структурной теоремы записываются как Бём и Якопини. В таком виде они и используются в настоящей статье.

Работы Э. Дейкстры

Как было указано выше, Э. Дейкстра был основоположником структурного программирования. Его заслуга состоит не только в разработке этой концепции, но и в ее деятельном продвижении. В 1965 году на конгрессе IFIP Дейкстра высказал мнение, что оператор goto может быть исключен из языков программирования [8]. Однако его мнение не вызвало сильную реакцию. Тогда Дейкстра в 1968 году посвятил оператору goto отдельное письмо редактору одного из научных журналов Н. Вирту [3]. Годом позже Дейкстра опубликовал работу, названную «Структурное программирование» [9], что и дало название новой концепции программирования.

В работах Дейкстры сформулированы основные принципы структурного программирования (главным образом в [10]).

I. Использование в программах управляющих структур трех видов: следование (сочленение в терминологии работы [10]), выбор и повторение. Все эти структуры имеют один вход и один выход. При отладке программы может возникнуть следующая проблема. «Дана работающая программа и предполагается, что до завершения счета она остановлена в одной из дискретных точек продвижения вычислений. Каким способом мы можем идентифицировать точку прерывания, если, например, хотим повторить вычисления именно до этой самой точки? Кроме того, если останов был вызван какой-то динамической ошибкой, то как мы можем идентифицировать соответствующую точку продвижения вычислений, не прибегая к полному копированию памяти?» [10]. Ограничение использования управляющих структур позволяет в любой такт вычислительного процесса отождествлять его этап и соответствующий фрагмент текста программы. «Если мы считаем своей обязанностью контролировать вычисления (интеллектуально!), обращаясь к тексту управляющей вычислениями программы, то нам следует смиренно довольствоваться наиболее систематизированными способами организации следования, гарантирующими самое непосредственное отражение "продвижения вычислений" в "продвижении по тексту"» [10].

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

III. Доказательство правильности программы. «Тестирование выявляет только наличие, но никак не отсутствие ошибок». Это знаменитое высказывание Дейкстры из работы [9] в переводе, приведенном в [2]. Программа – это последовательность вычислений. Вычисления можно записать математическими формулами. Следовательно, можно доказать теорему о правильности программы. В [9] ставится ключевой вопрос: «Для какой структуры программы мы можем доказать ее правильность без чрезмерных усилий, даже если программа имеет большой объем?» Доказательство правильности программы – это ключевой принцип структурного программирования. Принципы, приведенные выше, являются производными от него.

Принципы структурного программирования в том или ином виде были известны до работ Дейкстры, а «математические основы (структурного программирования – Т.Г., А.В.) были известны в алгебре рекурсивных функций уже давно, хотя и не использовались на практике» [11]. Однако именно Дейкстра на основе этих принципов предложил абсолютно новую концепцию программирования.

    Как многие новые революционные идеи, структурное программирование сталкивалось с критикой почти все 1970-е годы. В [12] приводятся достоинства и перечисляются следующие недостатки структурного программирования:
  • относительно неэффективное использование памяти и увеличение времени выполнения (также в [13]);
  • явный недостаток гибкости из-за ограничений в передаче управления в программе;
  • сосредоточение на человеческом факторе, а не на логике, что не позволяет программистам писать максимально эффективные, логически рациональные программы;
  • недостаток управляющих структур для реализации этой концепции в языках программирования (также в [2, 14]).
    Статья Д. Кнута [5] включает два главных раздела, посвященных исключению и включению оператора goto в программу. Включение оператора goto целесообразно в случаях, среди которых:
  • исключение рекурсии;
  • для преобразования программ в более эффективные с оператором goto;
  • исключение логических переменных.

В этой статье Кнут заключает следующее. Во-первых, существует несколько ситуаций в программировании, в которых оператор goto безвреден, даже желателен, если мы программируем на АЛГОЛе или ПЛ/1. Но, во-вторых, были разработаны новые типы синтаксиса, которые обеспечивают замену для этих безобидных операторов goto и не способствуют созданию «логического спагетти» программистом.

Э. Йодан отмечает, что большинству программистов, особенно в США, структурное программирование остается неизвестным [2, стр. 166] и лишь в некоторых организациях пошли на запрет оператора goto в прикладных программах [2, стр. 35].

К сожалению, идеи Дейкстры о структурном программировании были искажены. П. Хендерсон и Р. Сноудон [15] провели эксперимент по написанию программы по принципам структурного программирования. Авторы эксперимента надеялись, что соблюдение этих принципов позволит избежать ошибок. Однако при тестировании программы была выявлена ошибка. Проанализировав статью Хендерсона и Сноудона, Г. Ледгард [16] заключил, что метод, использованный в эксперименте, строго говоря не совсем «структурное программирование», по крайней мере, как задумывал Дейкстра [10].

В то же время были разработаны методы преобразования программ с оператором goto в структурированные программы. Наиболее простым и универсальным был метод Ашкрофта-Манна [17].

А. П. Ершов считал, что перевод названия книги [10] (и названия концепции) не вполне точен. «Более правильно говорить "Структурированное программирование". Это ближе к английскому оригиналу "Structured programming" и более точно отражает смысл: внесение структуры как в процесс программирования, так и в форму программы» [11].

    Некоторые заметки об Э. Дейкстре:
  1. Свои статьи Дейкстра нумеровал EWD0, EWD1, EWD2 и т. д. Статья [8] имеет номер 117, глава Дейкстры из [10] – номер 249, статья [9] – 268, [27] – 196.
  2. Факт о Дейкстре: «Известно, что он мало заинтересован в приеме на старшие курсы университета, где он преподает, студентов со знанием Фортрана по той причине, что вместе с этими знаниями могли привиться дурные привычки программирования» [2, стр. 167].
  3. Еще одна цитата из Дейкстры [10]: «Изящество, ясность и тому подобное в значительной степени определяются количественными аспектами. (Этим владел Моцарт: многие его произведения, от которых замирает дыхание, обманчиво просты; кажется, будто они созданы практически из ничего!)».

Работы Х. Миллса

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

В 1969 году компания IBM выиграла конкурс на разработку информационного банка газеты «Нью-Йорк Таймс». Информационный банк был хранилищем статей и предоставлял доступ к ним сотрудникам газеты [18]. Статьи могли быть найдены по дате выпуска, рубрике, ключевым словам и другим критериям. Руководство разработкой было поручено Х. Миллсу [19]. Миллс выбрал главным программистом Ф. Бейкера, а также его помощника и библиотекаря. Библиотекарь обслуживал библиотеку текстов модулей и документации, а также проверял, чтобы изменения в программную систему вносились строго в соответствии с установленными правилами. При разработке использовалось структурное программирование и его принципы. Группа Миллса, выросшая до 11 человек [14], реализовала информационный банк – большую (по тем временам) систему, текст программы которой был длиной 83 тыс. операторов на языке высокого уровня, за 22 месяца, затратив около 300 000 долларов США [19]. Индекс выявленных ошибок составил 0,1 на 1 000 строк программы [14]. Перечисленные показатели превосходили обычные средние показатели программных проектов. При разработке применялся подход «Бригада главного программиста» (в переводе в [2, стр. 106-112]). Главный программист выполнял основную часть работы, а его бригада ему ассистировала. В [18] этот подход сравнивается с работой хирургической бригады.

Следующей движущей силой к принятию структурного программирования как доминирующей концепции программирования стал самый большой потребитель программного обеспечения – правительство США [13]. Осознание значимости новой концепции программирования привело к изданию указаний по поощрению использования структурного программирования в приобретаемом программном обеспечении. Более крупным проектом была разработка программной системы орбитальной станции «Скайлэб» в 1971-1974 годах [14]. Программная система состояла из двух частей: системы симуляции полета для обучения астронавтов и системы управления полетом. В разработке системы принимали участие более 400 программистов. Использование принципов структурного программирования в разработке системы симуляции позволило повысить производительность труда в 3 раза и снизить сложность интеграции.

    По результатам применения на практике структурного программирования Миллс опубликовал несколько книг, отчетов и статей (например, [6, 20]). В [21] он сформулировал математические основания этой концепции:
  1. структурная теорема Бёма-Якопини;
  2. нисходящее проектирование (названное выводом «сверху-вниз»);
  3. теорема о правильности, которая показывает, как проблема правильности программ может быть сведена к функциональным теоретическим вопросам, к которым применим математический аппарат;
  4. теорема расширения, которая определяет границы расширения функциональной спецификации в структуре на следующем уровне при нисходящем проектировании.

В этой же работе приводятся доказательства теоремы о правильности и теоремы расширения.

Мнения о вкладе Миллса в развитие структурного программирования противоречивы. В [12] отмечается, что он был одним из увлеченных приверженцев структурного программирования вместе с другими подходами к проектированию программ. В [22] Миллс называется одним из авторов структурного программирования. Дейкстра считал, что Миллс сделал оригинальную идею структурного программирования незначительной, сведя ее к упразднению оператора goto [23].

Работы Э. Йодана

    Книга Э. Йодана [2] примечательна по нескольким причинам:
  1. охватывает не только программирование, но и весь процесс разработки программных систем;
  2. описывает, не только каким должно быть программирование, но и каким оно было до появления концепции структурного программирования; именно поэтому практически каждый раздел статьи содержит ссылки на эту книгу;
  3. поднимает проблему структурного проектирования программ, а не только структурного программирования (см. также [24]); потребность в структурном проектировании возникла с увеличением уровня сложности программных систем;
  4. убедительно убеждает в преимуществах структурного программирования.

Приведем несколько интересных фактов о программировании 1970-х годов из [2]:

I. «В 1971 году мне представился случай обсудить вопросы мнемоники и содержательности меток с программистом, разрабатывающим важные имитационные программы для Центра пилотируемых космических кораблей НАСА. По его мнению, переменным, подпрограммам и другим меткам не следует давать «значащие» имена, поскольку впоследствии они могут быть ошибочно поняты или истолкованы программистами, обеспечивающими сопровождение. По этой причине он намеренно выбирал такие имена, как QPK17, GLOP42 и ZYX123, ни одно из которых не имело никакой связи с именуемыми переменными и подпрограммами. Он считал, что в этом случае программист будет вынужден тщательно изучить программу, чтобы узнать истинный смыл этих меток» (стр. 49).

II. В разделе «7.8. Другие методы тестирования» приводится метод избыточного программирования:

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

Этот принцип избыточного программирования может показаться довольно странным и дорогостоящим, однако его можно сравнить с принципом двукратного или многократного резервирования процессоров как способа обеспечения живучести системы при аппаратных отказах» (стр. 318-319).

III. Одним из вариантов нисходящего тестирования является структурированный разбор. Разбор включает следующие этапы (стр. 97-98):

«1. Как один из членов бригады программистов, занятых на одном и том же проекте, программист должен предусматривать структурированный разбор его программы, назначив заранее официальное заседание. За день или за два до заседания программистам группы передаются копии проекта и (или) текста программы, и (или) тестовых данных, с которыми они должны ознакомиться к началу заседания».

«2. Присутствие на структурированных разборах руководителя проекта, как правило, не допускается».

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

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

«5. В структурированных разборах всячески избегают проектирования программы заново».

«6. Вся бригада несет ответственность за ошибки и упущения, которые могут обнаружиться в программе после того, как она передана пользователю».

IV. «Один из программистов проекта для ВВС США, описанного выше, сделал интересное замечание по поводу правила о 500 Кобол-операторах в модуле: "Черт с ними, я соглашусь со всеми глупыми ограничениями вроде этого, большинство из них можно довольно просто обойти. Я пишу программу, не обращая никакого внимания на это правило 500 операторов, а затем, если окончательная программа получается длиной в 3 000 операторов, я просто делаю: чик! чик! чик! – получаю шесть модулей! Вот и все!"» (стр. 118).

Йодан продолжал работу по популяризации структурного проектирования программ не только в роли автора книг и статей, но и в роли руководителя собственного издательства, выпускавшего книги по этой тематике.

Подпрограммы в структурном программировании

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

1. «Впервые я познакомился с понятием замкнутой подпрограммы в связи с системой EDSAC, где понятие подпрограммы служило основой библиотеки стандартных программ. В те времена конструирование машинной аппаратуры было рискованным делом, и многие стандартные программы служили для расплаты и без того малой памятью и временем счета за несовершенство электронных схем; если в машинном коде не предусматривалась операция деления, то обзаводились подпрограммами деления. Однако, как ни странно, я не припоминаю, чтобы какие-то подпрограммы получили признание как средство "перестройки" имеющейся машины в более удобную. Мне не помнится также, чтобы в те времена пользователи проектировали и строили подпрограммы, отражая в них анализ своих задач. Преимущественно дело сводилось к стандартным программам, по отношению к которым пользователь выступал только в роли потребителя. <…> Десятью годами позже, когда появился АЛГОЛ-60, декорации переменились, и мы перестали говорить о замкнутых подпрограммах: отныне мы называли их "процедурами". Они по-прежнему воспринимались программистами как очень удобное средство сокращения текста программы; однако программисты все чаще и чаще начинали использовать их в целях структурной организации с таким расчетом, чтобы приспособление программы к ожидаемым изменениям постановки задачи могло свестись к замене одного или нескольких тел процедур или же к изменению некоторых фактических параметров в каком-то обращении к процедуре» [10, стр. 57-58].

2. «Заметим, что подпрограммы не являются абсолютно необходимым условием возможности реализации структурного программирования» [2, стр. 180].

3. «Оформление логически самостоятельных частей алгоритма в виде подчиненных алгоритмов:

а) облегчает программирование сложных алгоритмов, давая автору сосредоточиться на главной задаче и не отвлекаться одновременно обдумыванием всех деталей процесса;

б) делает запись сложного алгоритма более наглядной и обозримой;

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

Ясно, что в алгоритмическом языке тоже необходимо иметь средства для описания подчиненных алгоритмов. <…> Подчиненные алгоритмы в АЛГОЛе носят название процедур» [25, стр. 138].

Что из структурного программирования перешло в другие концепции

Новые идеи, появившиеся вместе со структурным программированием

Структурное программирование так или иначе повлияло на развитие новых идей в программировании. Авторы этих идей внесли значительный вклад в развитие программирования наряду с Дейкстрой. В последующих разделах перечисляются идеи, которые используются в программировании до сих пор. Р. Флойд [26] объединил нисходящее проектирование программ, уровни абстракции и скрытие деталей в парадигму (концепцию в нашей терминологии) структурного программирования.

Уровни абстракции

Разделение программной системы на уровни иерархии было предложено Дейкстрой [27]. На каждом уровне были реализованы независимые друг от друга абстрактные элементы. Уровни системы упростили модификацию и расширение программы.

    Уровни абстракции получили развитие в работах Б. Лисков. Каждый уровень реализует несколько функций и подчиняется двум правилам [28]:
  1. Каждый уровень имеет ресурсы (данные, устройства ввода-вывода), доступ к которым другим уровням запрещен.
  2. Нижние уровни «не знают» о существовании высших уровней. Высшие уровни могут обращаться к нижним уровням для выполнения функций и для доступа к их ресурсам.

Уровни, образующиеся при нисходящем проектировании, не являются уровнями абстракции, так как не имеют ресурсов. Структурное программирование – недостаточная основа для проектирования программных систем. Система должна разделяться на уровни абстракции. По мнению Б. Лисков, причиной появления ошибки в программе в упоминаемой выше работе Хендерсона и Сноудона [15] является невыделенный уровень абстракции.

Деление программы на уровни абстракции продолжает быть современным стилем программирования.

Скрытие деталей

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

Д. Парнас предложил делить программу на модули не делением ее блок-схемы, а на основе проектировочных решений [29]. Эти решения должны быть скрыты внутри модуля от других модулей. Интерфейс модуля или его определение выбирается так, чтобы как можно меньше открывать проектировочные решения. Этот принцип назван Парнасом «скрытие деталей» (information hiding). Скрытие деталей позволяет снизить сцепление модулей.

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

Принцип скрытия деталей широко применяется в объектно-ориентированном программировании. Спецификаторы языков программирования позволяют ограничить доступ к элементам класса из объектов других классов. Скрытие деталей является обязательным требованием при написании современных программ.

Сцепление и связность

    Л. Константайн с середины 1960-х годов занимался поиском критерия деления программы на модули. Он предложил две меры взаимодействия модулей программы (сошлемся на его более позднюю работу [30]):
  1. Сцепление (coupling) – степень зависимости одного модуля от другого. Чем меньше первый модуль «знает» о втором модуле, тем меньше изменений придется вносить в первый модуль при модификации второго. Под «знать» понимается вызов подпрограмм другого модуля с заданным числом и порядком параметров.
  2. Связность (cohesion) – степень функциональной родственности элементов одного модуля. Чем более специализированы подпрограммы модуля, тем меньше времени требуется для понимания их текста и их изменения.

Обе меры взаимосвязаны. Чем больше связность модулей, тем меньше сцепление между ними. Среди этих мер важнее связность [30].

Сцепление и связность до сих пор используются в объектно-ориентированном программировании [31].

Стиль программирования времен структурного программирования

Некоторые советы по стилю программирования середины 1970-х годов пригодились бы современным программистам (таблица 2). Советы по стилю программирования середины 1970-х годов взяты из главы 5 (советы 1-19), а также из некоторых других глав (с указанием страниц) книги Э. Йодана [2] с необходимыми пояснениями. Часть советов были найдена в книге Р. Мартина [32] по современному стилю программирования (с указанием страниц).

    Сравнение советов по стилю программирования середины 1970-х годов и конца 2000-х годов
    СоветыЭ. Йодан, 1975Р. Мартин, 2009
  1. Пользуйтесь методами структурного программирования
    		2. ++ (стр. 48-49)
  2. Без крайней необходимости избегайте многоцелевого применения (программа инициирует и решает несколько задач)
    		3. +–
  3. Не допускайте произвольного употребления системы команд или языка программирования (не используйте команды, отсутствующие в официальной документации)
    		4. +–
  4. Не пишите программы, которые модифицируются в процессе исполнения
    		5. +–
  5. Избегайте неоправданно сложных математических выражений (разбивайте математические выражения на части)
    		6. +–
  6. Компонуйте вложенные условные операторные фразы (сдвигайте вложенные операторы вправо)
    		7. ++ (стр. 88-89)
  7. В одной строке листинга программы не следует располагать более одной операторной фразы
    		8. ++ (стр. 89)
  8. Пользуйтесь «полем идентификации» на перфокарте
    		9. +–
  9. Пользуйтесь переносом строки листинга, сохраняющим читабельность программы
    		10. +–
  10. Предваряйте и сопровождайте символы арифметических операций одним или более пробелами
    		11. ++ (стр. 86)
  11. Старайтесь располагать начало записи каждого оператора в том же столбце листинга
    		12. ++ (стр. 88-89)
  12. Добавляйте к имени подпрограммы метку в возрастающей последовательности, упрощающей ее поиск в листинге
    		13. +–
  13. Снабжайте листинг программы подробными комментариями
    		14. ++ (стр. 55-58)
  14. Избегайте сложных команд в языке ассемблера
    		15. +–
  15. По возможности избегайте отрицаний в логических выражениях
    		16. ++ (стр. 302)
  16. Избегайте сложных логических выражений
    		17. +–
  17. Не используйте для обозначения одной и той же константы или переменной нескольких имен (псевдонимов)
    		18. +–
  18. Не передавайте управление внутрь цикла или из него в произвольных точках
    		19. +–
  19. Избегайте произвольного изменения значения счетчика циклов
    		20. +–
  20. Выбирайте мнемоничные имена переменных (имена переменных должны соответствовать назначению переменных в программе) (стр. 35-36)
    		21. ++ (стр. 17-30)
  21. Разбивайте ваши программы на малые независимые подпрограммы (стр. 124)
    		22. ++ (стр. 35-37)
  22. Используйте вместо числовых литералов константы (или оператор DEFINE) (стр. 142-146)
    		23. ++ (стр. 300-301)
  23. Отделяйте действия по вводу-выводу от вычислительных операций (стр. 150)
    		24. +–
  24. Контролируйте на достоверность любые входные данные пользователя (стр. 261)
    		25. +–

Эти книги разделяют почти 35 лет. Однако многие советы середины 1970-х годов остались актуальными для современного стиля программирования. Педагогическая практика авторов этой статьи показывает, что советы Йодана требуются и современным студентам при написании ими учебных программ.

Йодан и Мартин при описании стиля программирования ссылаются на одну и ту же книгу Б. Кернигана и Ф. Плаугера [33] (Йодан на ее первое издание, а Мартин – на второе).

Что из структурного программирования не использовалось широко в последующих концепциях

Дейкстра в структурном программировании пытался создать математическую основу программирования не случайно: «Как только программирование вышло за пределы допустимой сложности, произошел поворот к дисциплине, главной целью которой в течении веков было применение эффективного структурирования с целью преодоления казавшейся не поддающейся управлению сложности. Эта дисциплина, всем нам более или менее знакомая, называется математикой. Если мы согласимся с правильностью суждения о том, что математические методы являются наиболее эффективным средством преодоления сложности, у нас не остается другого выбора, как только перестроить область программирования таким образом, чтобы стало возможным применять эти методы, ибо иных средств не существует» [34] (в переводе из [20]). Математическая основа позволила бы свести многие действия, выполняемые при написании программ, к математическим операциям, а это, в свою очередь, привело бы к автоматизации процесса написания программ.

Исследователи изучали вопрос доказательства правильности программы как до, так и после работ Дейкстры (например, [35-39]). Однако полученные результаты оказались неудовлетворительными с практической точки зрения.

«Доказательство правильности программы может оказаться очень дорогостоящей и утомительной работой, требующей больших затрат времени, но если учесть, что плата за это обладание программой, которая всегда будет работать правильно, то оказывается, что такую работу безусловно стоит выполнить. Понадобится выполнить и гораздо более трудоемкую работу в этом направлении, чтобы учесть такие обстоятельства, как конечная точность машин, сложность программ, и разрабатывать форму задания предикатных указаний для программы. Встает много проблем, но здесь я надеялся показать, что по крайней мере какая-то работа делается в этом направлении и она кажется довольно обещающей. Я хочу призвать других людей к понимаю этой работы и развитию» [40].

«Несколько исследователей изучали проблему автоматического доказательства правильности произвольной программы; некоторые из полученных ими результатов можно найти в работах (далее следуют ссылки на [37-39] – Т.Г., А.В.). Эти результаты, однако, не обещают каких-либо практических приложений в ближайшем будущем. В одном из случаев, выполненных Хоором, доказательство правильности программы, содержащей 12 операторов, включает восемнадцать лемм (далее следует ссылка на [39] – Т.Г., А.В.). Более того, все еще сохраняется такое чувство, что число операторов "доказательства" может возрастать с увеличением длины проверяемой программы быстрее, чем по линейному закону. Одной из причины разработки Дейкстрой структурного программирования было то, что автоматическое доказательство программ, отвечающих некоторому структурному образцу, может быть значительно упрощено. Представляется, что так оно и есть на самом деле, однако до сих пор мы не имеем ни одного практического метода получения строгого доказательства правильности программ, записанных в какой-либо форме» [2, стр. 173].

Некоторым развитием доказательства правильности программ была методология «проектирование по соглашению» (design by contract), предложенная Б. Майером [22]. Пусть подпрограмма А вызывает подпрограмму Б (подпрограммы могут быть и методами классов). Подпрограмма Б заключает с подпрограммой А следующее соглашение: «Если подпрограмма А вызовет подпрограмму Б и при этом предусловие P будет истинно, то подпрограмма Б гарантирует, что в конце ее выполнения постусловие R также будет истинно».

Авторам статьи не приходилось сталкиваться с практическим применением доказательства правильности программы или проектирования по соглашению.

Далее ни в одной концепции императивного программирования не предпринимались заметные усилия по математической формализации программирования. Например, в книгах, посвященных шаблонам проектирования, (а именно [41-42]) численно не обосновываются преимущества использования этих шаблонов.

Мнения о нисходящем проектировании

    Разработчик языка С++ Б. Страуструп, рассматривая подходы к разработке программ «сверху-вниз» и «снизу-вверх», считал: «Интересно, что наиболее надежные системы созданы с помощью сочетания обоих подходов, хотя они очевидным образом противоречат друг другу. Причина проста: для крупных реальных систем ни один из этих подходов не гарантирует требуемой правильности, адаптируемости и удобства сопровождения.
  • Мы не можем создать и проверить основные компоненты, заранее устранив все источники ошибок.
  • Мы не можем полностью компенсировать недостатки основных компонентов (библиотек, подсистем, иерархий классов и т. д.), объединив их в законченную систему» [43, стр. 809].

Нисходящее проектирование начинается с написания программы на самом верхнем уровне. Б. Майер замечает, что выделение верхнего уровня в программных системах не всегда очевидно [22, стр. 108–109]. Например, операционная система выполняет несколько функций: выделяет время центрального процессора, распределяет оперативную память, управляет устройствами ввода-вывода, выполняет команды пользователя. Выделение в качестве верхнего уровня ожидания запроса пользователя, его обработку и вывод результата вряд ли станет основой хорошо структурированной операционной системы. Майер заключает, что реально работающие программные системы не имеют верхнего уровня.

Что же такое структурное программирование

Все вышесказанное позволяет сформулировать современное определение структурного программирования.

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

Авторы статьи надеются, что уважаемый читатель осознал, что структурное программирование – это не программирование без оператора goto.

Заключение

    На основе разделов статьи можно сделать следующие выводы:
  1. К середине 1960-х годов возникла потребность в методах разработки более сложных программных систем.
  2. Э. Дейкстра сформулировал принципы структурного программирования с целью автоматизации доказательства правильности программ. Одним из положений, использованного Дейкстрой для обоснования этой концепции, была структурная теорема Бёма-Якопини. Структурное программирование позволило разрабатывать легко изменяемые и расширяемые программы нового уровня сложности.
  3. Принципы структурного программирования и новые подходы к организации труда программистов позволили Х. Миллсу реализовать программный проект с немыслимыми по тем временам показателями.
  4. Возможность реализации более сложных программных систем привел к необходимости создания структурного проектирования программ. Влияние на его развитие оказали работы Э. Йодана.
  5. Структурное программирование послужило источником волны перспективных идей, реализованных в новых концепциях и языках программирования. Уровни абстракции, скрытие деталей, связность и сцепление используются как в языках программирования, так и в стиле программирования.
  6. К сожалению, основной принцип структурного программирования – доказательство правильности программ не получил развития и не был доведен до практического применения.
    Структурное программирование не ушло в небытие. Значение структурного программирования для современного программирования состоит в следующем:
  • несмотря на то, что программирование существовало до структурного программирования, эта концепция стала первой концепцией императивного программирования;
  • структурное программирование живет в последующих концепциях императивного программирования как их фундаментальное основание;
  • структурное программирование до сих преподается в школах и вузах в качестве основы программирования [44].

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

Материалы статьи будут использованы при издании новых томов учебника по информатике и программированию [45].

Библиографический список

  1. Böhm, C., Jacopini, G. Flow diagrams, Turing Machines and Languages With Only Two Formation Rules. In Communications of ACM. 1966. Vol. 9. No. 5. P. 366-371.
  2. Йодан Э. Структурное проектирование и конструирование программ. Перев. с англ. – М.: Мир, 1979. – 416 с. – Перевод изд.: Yourdon, E. Techniques of Program Structure and Design. Prentice-Hall, 1975.
  3. Dijkstra, E.W. Go to Statement Considered Harmful. In Communications of the ACM. 1968. Vol. 11. No. 3. P. 147-148.
  4. Rao Kosaraju, S. Analysis of Structured Programs. In Journal of Computer and System Sciences. 1974. No. 9. P. 232-255.
  5. Knuth, D. Structured Programming with go to Statements. In ACM Computing Surveys. 1974. Vol. 6. No. 4. P. 261-301.
  6. Миллс Х. Программирование больших систем по принципу сверху вниз. В книге Средства разработки больших систем. Под ред. Р. Растина. – М.: Статистика, 1977. – С. 41-56. – Перевод изд.: Mills, H.D. Top-Down Programming in Large Systems. In R. Rustin (ed.) Debugging Techniques in Large Systems, Prentice-Hall, 1971. P. 41-55.
  7. Ермолович Д.И. Имена собственные на стыке языков и культур. – М.: «Р.Валент», 2001. – 200 с.
  8. Dijkstra, E.W. Programming Considered as a Human Activity. In Proc. of IFIP Congress 65, 1965.
  9. Dijkstra, E.W. Structured Programming. In J.N. Buxton, B. Randell (eds.), Software Engineering Techniques, NATO Scientific Affairs Division, Brussels, Belgium, 1969. P. 84-88.
  10. Дал У., Дейкстра Э., Хоор К. Структурное программирование. Перев. с англ. С.Д. Зеленецкого, В.В. Мартынюка, Л.В. Ухова; под ред. Э.З. Любимского и В.В. Мартынюка. – М.: Мир, 1975. – 248 с. – (Сер. «Математическое обеспечение ЭВМ»). – Перевод изд.: Dahl, O.-J., Dijkstra, E.W., Hoare, C.A.R. Structured Programming. Academic Press, 1972.
  11. Ершов А. П. Введение в теоретическое программирование (беседы о методе). – М.: Гл ред. физ.-мат. литературы изд-ва «Наука», 1977. – 288 с.
  12. Hunt, K.P. An Introduction to Structured Programming. In Behavior Research Methods & Instrumentation. 1979. Vol. 11. No. 2. P. 229-233.
  13. Jensen, R.W. Structured Programming. In IEEE Computer. 1981. Vol. 14. No. 3. P. 31-48.
  14. Mills, H.D. Structured Programming – Retrospect and Prospect. In IEEE Software. 1986. Vol. 3. No. 6. P. 58-66.
  15. Henderson, P., Snowdon, R. An Experiment in Structured Programming. In BIT. 1972. No. 12. P. 38-53.
  16. Ledgard, H.F. The Case for Structured Programming. In BIT. 1973. No. 13. P. 45-57.
  17. Ashcroft, Е., Manna, Z. The Translation of «goto» Programs into «while» Programs. In Proc. of IFIP Congress 71, 1, 1971. P. 250-255.
  18. Baker, F.T. System Quality through Structured Programming. In Fall Joint Computer Conference, 1972. P. 339-343.
  19. Фокс Дж. Программное обеспечение и его разработка. Пер. с англ. – М.: Мир, 1985. — 368 с. – Перевод изд.: Fox, J.M. Software and its Development. Prentice Hall, 1982.
  20. Лингер Р., Миллс Х., Уитт Б. Теория и практика структурного программирования: пер. с англ. – М.: Мир, 1982. – 406 с. – Перевод изд.: Linger, R.C., Mills, H.D., Witt, B.I. Structured Programming: Theory and Practice. Addison-Wesley, 1979.
  21. Mills, H.D. Mathematical Foundations for Structured Programming. Report FSC 72-6012, IBM Federal Systems Division, 1972, 62 pp.
  22. Meyer, B. Object-Oriented Software Construction, 2nd ed. Prentice Hall, 1997.
  23. Dijkstra, E.W. What Led to «Notes to Structured Programming» (EWD1308). In M. Broy, E. Denert (eds.) Software Pioneers. Springer, 2002.
  24. Yourdon, E. Structured Programming and Structured Design as Art Forms. In Proc. of AFIPS'75, 1975, p. 277.
  25. Демидович Н.Б., Монахов В.М. Программирование и ЭВМ. – М.: Просвещение, 1977. – 240 с.
  26. Floyd, R.W. The Paradigms of Programming. In Communications of the ACM. 1979. Vol. 22. No. 8. P. 455-460.
  27. Dijkstra, E.W. The Structure of the "THE"-Multiprogramming System. In Communications of the ACM. 1968. Vol. 11. No. 5. P. 341-346.
  28. Liskov, B.H. A Design Methodology for Reliable Software Systems. In Proc. of Fall Joint Computer Conference, 1972. P. 191-199.
  29. Parnas, D.L. On Criteria to Be Used in Decomposing Systems into Modules. In Communications of the ACM. 1972. Vol. 15. No. 12. P. 1053-1058.
  30. Yourdon, E., Constantine, L.L. Structured Design: Fundamentals of a Discipline of Computer Program and System Design. Prentice-Hall, 1979.
  31. Ройс У. Управление проектами по созданию программного обеспечения. Унифицированный подход. – М.: Изд-во «Лори», 2002. – 425 с. – Перевод изд.: Royce, W. Software Project Management. A Unified Framework. Addison-Wesley, 1998.
  32. Martin, R. Clean Code. A Handbook of Agile Software Craftsmanship. Prentice Hall, 2009.
  33. Kernighan, B.W., Plaugher, P.J. The Elements of Programming Style. McGraw-Hill, 1974.
  34. Dijkstra, E.W. On a Methodology of Design, MC-25 Informatica Symposium, MC Tract 37, Mathematisch Centrum, 1971.
  35. McCarthy, J. Towards a Mathematical Science of Computation. In C.M. Popplewell (ed.) Information Processing 1962: Proc. of IFIP Congress 62, 1962. P. 21–28.
  36. London, R.L. Proving Programs Correct: Some Techniques and Examples. In BIT. 1970. Vol. 10. No. 2. P. 168-182.
  37. King, J.C. A Program Verifier. Ph. D. Thesis, Carnegie Mellon University, 1970.
  38. Manna, Z., Ness, S., Vaillemin, J. Inductive Methods for Properties about Programs. In SIGPLAN/SIGACT Conf. on Prooving Assertions about Programs, 1972.
  39. Hoare, C.A.R. Proof of a Program: FIND. In Communications of the ACM. 1971. Vol. 14. No. 1. P. 39-45.
  40. Кинг Дж. Проверяющий компилятор. В книге Средства разработки больших систем. Под ред. Р. Растина. – М.: Статистика, 1977. – С. 23-40. – Перевод изд.: King, J.C. A Verifying Compiler. In R. Rustin (ed.) Debugging Techniques in Large Systems, Prentice-Hall, 1971.
  41. Стелтинг С., Маасен О. Применение шаблонов Java. Библиотека профессионала. Пер. с англ. – М.: Издательский дом «Вильямс», 2002. – 576 с. – Перевод изд.: Stelting, S., Maasen, O. Apllied Java Patterns. Prentice Hall, 2001.
  42. Martin, R. Agile Software Development: Principles, Patterns, and Practices. Prentice Hall, 2003.
  43. Страуструп Б. Программирование: принципы и практика использования C++. Пер. с англ. – М.: ООО «И.Д. Вильямс», 2011. – 1248 с. – Перевод изд.: Strоustrup, B. Programming Principles and Practice Using C++. Addison-Wesley, 2009.
  44. Dmitrieva, T.A., Prutzkow, A.V., Pylkin, A.N. Two-Level Study of Object-Oriented Programming by University Students. In Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2019. Vol. 15. No. 1. pp. 200-206.
  45. Информатика и программирование. Алгоритмизация и программирование: учебник для студ. учреждений высш. проф. образования / Н.И. Парфилова, А.В. Пруцков, А.Н. Пылькин, Б.Г. Трусов; под ред. Б.Г. Трусова. – М.: Издательский центр «Академия», 2012. – 336 c. – (Сер. Бакалавриат).