Переходы и выдаваемые значения
В общее употребление структурное программирование вошло после популяризировавшей его работы Э. Дейкстры, в которой, к сожалению, не было даже намека на его ограничения. Ограничения структурного программирования вытекают как из самой его сути, так и из теоремы Бема-Джакопини. Применение структурных переходов, которые ввел в практику и теорию Д. Кнут (откопавший оригинальную работу Бема-Джакопини и четко выделивший ограничения дейкстровского структурного подхода14)), избавляет от многих недостатков, присущих методике Дейкстры. Структурные переходы - переходы лишь вперед и на более высокий уровень стр
уктурной иерархии управления, ни в каком случае не выводящие нас за пределы данного модуля.
/* Примеры структурных goto.*/ . . . do {y = f( x ,y)}; if (y>0) break; x=g(x,y); }while (x>0); . . . {. . . { if (All_Done)goto Success; } . . . Success: Hurra;}
Пример 14.5.1.
Структурные переходы в настоящее время также включаются в общераспространенные языки программирования. Их использование понемногу проникает и в учебные курсы.
Структурные переходы являются паллиативом. Они возникли из-за необходимости выразить мысль о том, что успех либо неудача глобального процесса может выявиться внутри одной из решаемых подзадач, и дальнейшая работа и над текущей задачей, и над всей последовательностью вложенных подзадач становится просто бессмысленной. В этом случае нужны даже не переходы, а операторы завершения. Но они во многих распространенных языках действуют лишь на один уровень иерархии вверх, а даже теоретически этого недостаточно15). Стоит заметить, что между идеей и ее корректной реализацией часто проходят долгие годы. Ныне в общераспространенном языке Java завершители наконец-то более или менее корректно реализованы.
Есть одно ограничение структурных переходов, известное с 80-х гг. ХХ века (cм. [20]), по крайней мере один раз достоверно повредившее создателям отечественной серии машин Эльбрус, в которых на аппаратном уровне поддерживалось структурное и функциональное программирование.
Структурные переходы (в том числе и завершители) некорректны, когда они выводят нас из функции-параметра вызова другой функции. Ирония в том, что абсолютно четкая и полная реализация завершителей еще до осознания необходимости данного средства и тем более задолго до осознания пределов его применимости была проделана именно там, где они в общем случае некорректны (в языке LISP). В нем, как мы видели, процедуры являются полноправными значениями, могут быть параметрами и результатами других процедур. Самый очевидный случай некорректности (правда, вылавливаемый системой обнаружения динамических ошибок Common Lisp), когда мы внутри созданной процедуры завершаем блок, существовавший в момент создания процедуры, но переставший существовать в тот момент, когда ее вызвали. Наверняка многие наталкивались на непонятное поведение программ с завершителями, но в соответствии с общераспространенным "позитивным" мышлением не обращали внимания на данный феномен.
Есть еще одна, на первый взгляд исключительно привлекательная, возможность. В обычных языках программирования часто раздражает то, что значение, выработанное один раз, не удается сразу же использовать в следующем операторе, и, более того, по какой-то очевидной глупости совершенно безвредное и использованное еще в Algol 60 понятие условного выражения, подобного
if x=0 then sin(y) else tan(y)
оказалось выброшено из некоторых распространенных языков (может быть, потому, что в данном случае часть else обязательна). В том же языке LISP, где была (достаточно уникальный случай в программировании) создана четкая и достаточно замкнутая система концепций (ни одной неувязки, которую можно было диагностировать при тогдашнем состоянии теории и практики, найти в нем не удалось), каждый оператор выдает значение, которое может быть использовано объемлющим оператором.
Эту концепцию попытались перенести на язык традиционного типа в языке Алгол 68. На первый взгляд получилось очень красиво. Например, оператор
if x>0 then a1 else a2 fi [if y>0 then j else i fi]:= if z>0 then sin(u) else tan(u) fi
намного компактней и красивей последовательности условных операторов, которую придется написать в Pascal или C++. Но концепция вырабатываемого значения оказалась в концептуальном противоречии и с оператором присваивания, и с совместными вычислениями. Например, согласно семантике Алгола 68, следующая запись
(x:=3, у:=x+y, z:=x+y)
является блоком программы, в котором все три присваивания исполняются совместно. Но очевидно, что в данном случае результат вычислений неоднозначен. Одновременно, поскольку значения не забываются, эта же конструкция является изображением массива из трех элементов либо записи с тремя полями.
Следовательно, если распространить систему выдаваемых значений на все операторы структурного программирования, то появляются формально допустимые и соблазнительные для хакерских трюков неустойчивые выражения. Выражение, изменяющее свой контекст (в частности, присваивание), выдавать значение не должно, чтобы не было соблазна поместить его в окружение, где оно будет вызывать трудно диагностируемую неоднозначность.
 |
|
|
Если нечто в данный момент используется практически монопольно, то из этого не следует, что оно будет занимать столь же исключительное положение и в будущем и что оно окажется лучшим средством для решения Ваших конкретных задач.
2)
Пожалуй, это первое концептуальное противоречие, явно отмеченное и учтенное в теории и практике программирования (и даже во всей современной науке). Но, поскольку не было даже наметок теории неформализуемых понятий, и на работу с ними переносили опыт работы с малыми формализациями, структурное противоречие было воспринято следующим образом.
К несчастью, оператор go to формально совместим с другими конструкциями традиционных (тогда говорили - универсальных) алгоритмических языков. Но реально он плохо взаимодействует с ними. Значит, он плох сам по себе.
3)
На самом деле традиционным вычислительным программам соответствует не классическая, а интуиционистская логика, но структура доказательств и большинство правил вывода в них совпадают.
4)
В этой системе требований без труда распознается так называемая блочная структура языков программирования, появившаяся еще в Algol 60 и ставшая в настоящее время фактическим стандартом.
5)
Кстати, программистам стоит почаще вспоминать, что, с точки зрения пользователя или заказчика, их внутрипрограммные объекты как раз являются такими же призраками, которые не имеют никакого отношения к реальной действительности. Так что при переходе от уровня рассмотрения программы самой по себе к уровню программы как части архитектуры реальной человеко-машинной системы идеальные и реальные объекты порою меняются местами.
6)
Как видим, программа должна составляться после того, как программист хорошенько подумал, а не до того.
7)
Конечно, уже всем в зубах навязли алгоритмы Евклида и факториалы! Но в изложении основ структурного программирования они как раз на месте, поскольку этот стиль создавался для сравнительно небольших (по нынешним масштабам) вычислительных программ.
8)
В принципе, если думать об эффективности в смысле используемой памяти либо времени счета, для любой рекурсивной программы можно подобрать более экономную циклическую реализацию. Но эта реализация будет переполнена подпорками, поэтому потребует гораздо больше усилий от программиста и развалится при первой же попытке модификации.
9)
Впрочем, неявно это следует из того, что парой строк выше мы использовали термин 'множество'.
10)
Для удобства хакеров, что ли?
11)
Прямо переписать в языке Common LISP данную программку в рекурсивную с использованием mapcar не удастся, поскольку реализаторы превратили данный функционал в макрос, для того чтобы в стандартных случаях чуть-чуть выиграть в эффективности (многим так не хочется писать тривиальные вещи!). Переопределив mapcar как функцию, можно реализовать рекурсивное определение указанной выше функции search.
12)
Всегда возникает соблазн сделать свой излюбленный способ действий универсальнее, исправив его замеченные недостатки. Но порою достоинства являются продолжением недостатков, и наоборот. При устранении любого частного недостатка, возникшего из-за неуниверсальности системы, появятся другие, как правило, худшие, хотя, может быть, на первых порах менее заметные.
13)
За исключением мелких.
14)
Так что, применяя теоретический результат, всегда интересуйтесь не только его формулировкой, но и доказательством, желательно в работе авторов.
15)
В связи с этим стоит помянуть добрым словом отечественные разработки в области алгоритмических языков, в частности язык ЯРМО, в котором необходимость многоуровневых средств завершения конструкций была осознана еще в начале 70-х гг.
