Структурное программирование

Реальный проект³⁾ - это смесь нисходящего и восходящего подходов:

сначала сверху вниз для выяснения  крупных строительных блоков;

затем попытка движения снизу  вверх, чтобы спроецировать понятия, оформившиеся ранее, на абстрактные  структуры, допускающие адекватную реализацию;

далее проверка соответствия, углубление нисходящей декомпозиции и  обобщение понятий, выделенных восходящими  приемами.

Как в нисходящем, так и  в восходящем подходе важно обеспечить согласование потоков управления и  потоков данных. Основным инструментом здесь может быть взгляд на программу со стороны сетей данных. Поскольку цикл появляется как реализация послойного движения по сети, а массив - как представление слоя сети, то видно, что на самом деле основной информационной структурой цикла является слой сети. Например, в цикле, реализующем числа Фибоначчи, - это структура из fib1 и fib2. Структура, представляющая очередной слой сети, называется реальным параметром (в отличие от формального параметра, диктуемого языком программирования и часто являющегося подпоркой) цикла. Реальный параметр мы будем называть просто параметром.

Далее, поскольку цикл возникает при повторении однородных действий, а действия диктуются свойствами реальных объектов программы, в цикле должно быть общее свойство, зависящее от параметра и называемое инвариантом цикла. Например, в цикле сортировки - это соотношение между отсортированными и неотсортированными фрагментами массива.

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

Методика циклического и  рекурсивного структурного программирования с использованием инвариантов и  недетерминированности (но без явного упоминания сетей данных) прекрасно изложена в учебных пособиях Алагича, Арбиба и Гриса [1] , [9] . Настольной книгой программиста должна служить также книга Кормена и др. (учебник MIT) [13] , в которой можно найти множество хороших примеров того, как находить правильные программные решения и со вкусом использовать подпорки.

Сделаем еще один шаг. Поскольку присваивание с точки зрения решаемой задачи лишь средство задать элементы нового слоя сети, есть смысл считать, что во время всей итерации цикла параметр фиксирован, его изменение происходит лишь в промежутке между двумя итерациями. Таким образом, для согласования потоков данных и потоков управления необходимо сосредоточить все присваивания реальным сущностям в одном месте: либо в конце, либо в начале очередной итерации. Более того, в принципе (и даже не совсем теоретическом, но плохо поддерживаемом современными системами программирования) присваивания можно было бы вообще изгнать, сделав переход старого значения реального параметра цикла к новому неявным, так же, как это сделано для формального, скажем, в языке Pascal.

И, наконец, необходимо заметить следующее.

Внимание!

Призраки и инварианты необходимо осознавать до начала написания  текста работающей программы. Если Вы оставите это на потом, то наверняка спутаете подпорки, которые займут у Вас основную часть мысленных ресурсов на завершающем этапе реализации, с сущностями. Более того, восстановить обоснование по тексту уже готовой программы, как ни парадоксально, обычно труднее, чем построить его заранее (то, что восстановить его во всяком случае не легче, было обосновано даже теоретически; смотри последнюю главу книги [20] ).

Переходы и выдаваемые значения. В общее употребление структурное программирование вошло после популяризировавшей его работы Э. Дейкстры, в которой, к сожалению, не было даже намека на его ограничения. Ограничения структурного программирования вытекают как из самой его сути, так и из теоремы Бема-Джакопини. Применение структурных переходов, которые ввел в практику и теорию Д. Кнут (откопавший оригинальную работу Бема-Джакопини и четко выделивший ограничения дейкстровского структурного подхода¹⁾ ), избавляет от многих недостатков, присущих методике Дейкстры. Структурные переходы - переходы лишь вперед и на более высокий уровень структурной иерархии управления, ни в каком случае не выводящие нас за пределы данного модуля.

 

/* Примеры структурных  goto. */

...

do {y = f (x,y) };

if (y>0) break;

x=g (x,y);

}while (x>0);

...

{...

{

if (All_Done) goto Success;

}

...

Success: Hurra; }

 

Пример 2 (html, txt)

Структурные переходы в настоящее время также включаются в общераспространенные языки программирования. Их использование понемногу проникает и в учебные курсы.

Структурные переходы являются паллиативом. Они возникли из-за необходимости выразить мысль о том, что успех либо неудача глобального процесса может выявиться внутри одной из решаемых подзадач, и дальнейшая работа и над текущей задачей, и над всей последовательностью вложенных подзадач становится просто бессмысленной. В этом случае нужны даже не переходы, а операторы завершения. Но они во многих распространенных языках действуют лишь на один уровень иерархии вверх, а даже теоретически этого недостаточно²⁾ . Стоит заметить, что между идеей и ее корректной реализацией часто проходят долгие годы. Ныне в общераспространенном языке 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)

 

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

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