Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

8.8. ПРОЦЕДУРЫ В РАЗНЫХ МОДЕЛЯХ ВЫЧИСЛЕНИЙ

475

end;

if Nstr >= MaxNstr then begin Nstr := 0; Readln end

until not Next;

Writeln;

end.

§ 8.8. ПРОЦЕДУРЫ В РАЗНЫХ МОДЕЛЯХ ВЫЧИСЛЕНИЙ

При обсуждении подпрограмм, представленном в настоящей главе, бы-

ли подробно рассмотрены все аспекты работы с ними как с операционными

единицами программы и единицами декомпозиции. В целом это рассмотре-

ние ограничивалось лишь стилем структурного программирования, в рамках

которого, собственно говоря, понятие процедуры и приобрело современное

содержание.Если же взглянуть на это понятие шире, попытаться распростра-

нить его на другие стили, то окажется, что некоторые из рассмотренных вы-

ше положений нуждаются в корректировке. Причина тому очевидна: стили,

относящиеся к другим моделям вычислений, вкладывают свое содержание

как в операционные, так и в декомпозиционные аспекты автономно рассма-

триваемых подпрограмм.

Даже самое близкое к структурному стилю программирование от состоя-

ний приводит к несколько отличному от устоявшегося понятию процедуры.

Этому случаю оказывается противопоказана рекурсия. В самом деле, с точ-

ки зрения модели вычислений программирование от состояний есть конеч-

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

контекста и др., тогда как для структурного понимания процедуры они необ-

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

программирования

Fortran IV

Basic

, которые в б

ольшей степени, чем все

их наследники, соответствуют данному стилю. Предписываемые в них меха-

низмы реализации подпрограмм явно указывают на то, что о рекурсивности

здесь речи нет.

Basic

стиль программирования от состояний поддержива-

ется наиболее последовательно: нет не только рекурсии, но и само понятие

Отсутствие рекурсивности в ранних языках часто объясняют неразвитостью методов

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

подобными мотивами. Однако есть контрпример: язык

LISP

, рекурсивные механизмы кото-

рого органичны для функционального стиля. Это один из самых старых языков програм-

мирования, применявшийся в тех же самых жестких условиях. В этом контексте следует

отметить

Algol 60

, разработчики которого пусть не во всем, пусть лишь на уровне идей, но

уже понимали, что потребуется не только программирование от состояний, но и значительно

476

ГЛАВА 8. ПОДПРОГРАММЫ

процедуры подменено командами

GOSUB

RETURN

, которые выполняют-

ся, соответственно, как переход по метке с запоминанием адреса возврата и

как переход по этому запомненному адресу. С точностью до использования

специальных регистров это именно то, что делается в обычном ассемблер-

ном коде.

Различное отношение двух родственных стилей к рекурсии можно счи-

тать следствием различий в трактовке структуры информационного простран-

ства программы (см. § 3.3). Процедурность в программировании от состоя-

ний исходит из того, что информационное пространство является общим для

всех подзадач, из решений которых складывается решение основной зада-

чи. Отсюда следует, что в данном случае утверждение о том, что процедура

выполняется в каком-то контексте, в первом приближении становится триви-

альным — все программные единицы вычисляются в одном и том же контек-

сте.

Как было показано, в структурном программировании ситуация иная.

Понятие контекста выполнения процедуры как частный случай вложенно-

сти контекстов является основой и реализационного механизма, и методики

декомпозиции программы.

Другая трактовка процедур требутеся и в ООП (см. соответствующую

главу). Тут основным является понятие предоставляемого интерфейса, и воз-

никает принципиально новое понятие делегирования действий.

Если для столь родственных моделей вычислений обнаруживаются раз-

личия процедур, то что говорить о других, нетрадиционных языках и сти-

лях, на которых мы здесь и остановимся. Но предварительно надо отметить,

что традиционное понятие процедуры сформировалось под значительным

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

до сих пор при исследовании вопросов вычислимости. По этой причине не-

удивительно, что процедуры функционального стиля (т. е. функции) похожи

на то, что применяется в языках структурного программирования. Можно

утверждать, что разработчики структурных и других ранних языков поста-

рались спроецировать функциональные возможности на фон Неймановскую

модель вычислений. При этом они посчитали не имеющим смысла, как про-

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

свойств функций, как частичная параметризация, как оперирование с типа-

ми высоких порядков, как понятие предела и т. д. Практически за рамка-

ми рассмотрения осталась концепция значения, без которой оперирование

более развитые стили.

Более подробное рассмотрение данного вопроса см. в § 10.1.

8.8. ПРОЦЕДУРЫ В РАЗНЫХ МОДЕЛЯХ ВЫЧИСЛЕНИЙ

477

с функциями (суперпозиция, комбинирование и др.) просто бессодержатель-

но. Вместо них языки предлагают суррогаты, со всех сторон “обвешанные”

прагматическими соглашениями. Это было бы не так страшно, если бы не

стихийная стандартизация концептуально недоработанных средств,в резуль-

тате чего плохие традиции сохраняются и множатся во вполне современных

системах.

Рассмотренные варианты процедур не выходят за рамки нетрадицион-

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

числительного процесса, императивность и пассивность памяти. И хотя они

заметно различаются, но не кардинально. Новые качества процедурности не-

избежно появляются в системах, которые пытаются внедрить идею изъяви-

тельного наклонения в языки программирования. Рассмотрим их в той же

последовательности, что и ранее (см. § 3.1).

1. Системы продукций. Процедуры в таких системах должны приме-

няться для следующих целей:

• Они объединяют логически связанные правила вывода, применя-

емые для задания серий сопоставления обрабатываемых данных

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

вычислений. Логическая связанность здесь трактуется и в опера-

ционном плане:пока выполняются правила, объединенные проце-

дурой, другие правила не используются. В результате появляются

система усложняющихся образцов и более емкие преобразования

данных по сравнению с тем,что задано в качестве базовых средств

языка;

• Вспомогательные действия, которые неестественно (в частности,

неэффективно) представлять в рамках систем продукций, оформ-

ляются как внешние процедуры, связанные с системой продукций

лишь форматами входа и выхода. Эти форматы требуются, соот-

ветственно, для переключения на внешний процесс и включения

сопоставления после выполнения процедуры.

Примером продуктивной реализации идеи может служить язык

Рефал

(см. § 13.1), в котором аналогом процедуры являются правила с совпа-

дающим детерминативом. Такие процедуры применяются как для объ-

единенного описания однотипных сопоставлений, так и для выполне-

ния внешних, в частности, арифметических действий.

478

ГЛАВА 8. ПОДПРОГРАММЫ

2. Системы функций. Как уже упоминалось, форма задания традицион-

ных процедур во многом унаследована от функциональной схемы, ко-

торая оказалась существенно сужена при проецировании на фон Ней-

мановскую модель. Указанные выше возможности (частичная параме-

тризация, оперирование с типами высоких порядков, понятие предель-

ного перехода и т. д.), реализуемые в противовес (а чаще в дополнение)

к императивным средствам, характеризуют операционный аспект про-

цедурности в системах функционального программирования. Особен-

ностью процедур функциональных систем является возможность гиб-

кой реализации параметризации, в частности, параметризации по не-

обходимости, размножения параметров и др.

Эти же возможности способствуют развитию средств декомпозиции

функциональных систем, позволяя конструировать зависимости меж-

ду данными с весьма сложной структурой. Как правило, подобное кон-

струирование оформляется в виде библиотечных средств, которые ока-

зываются в состоянии достаточно естественно описывать весьма аб-

страктные взаимоотношения между данными. Иллюстрацией тому мо-

жет служить библиотечная надстройка над языком

LispCLOS

(Common

Lisp Object System), которая по существу представляет собой функци-

ональный объектно-ориентированный язык с иными и в некоторых от-

ношениях более широкими возможностями, нежели то,что предлагают

развитые операционные объектные языки.

3. Коммутационные системы. Процедура как элемент декомпозиции в

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

обладающий замкнутостью относительно выполняемого в этом под-

графе действия, т. е. как подсистема с входами и выходами, к которым

ведут и из которых исходят дуги, связывающие ее с другими вершина-

Справедливости ради следует отметить, что успех

CLOS

объясняется не только функци-

ональностью

LISP

а, но и двумя другими свойствами этого языка:

• идентичность структуры перерабатываемых данных и структуры программы,

• возможность определения так называемых списков свойств атомарных единиц струк-

туры данных или программы.

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

таться характерным для этого стиля (оно соответствует трактовке данных как нульместных

функций), второе — более универсально и согласуется с объектной установкой на совмест-

ное определение данных и операций.

8.8. ПРОЦЕДУРЫ В РАЗНЫХ МОДЕЛЯХ ВЫЧИСЛЕНИЙ

479

ми.Такой подграф может быть стянут в структурную вершину.Для точ-

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

происходит транзитная передача данных по дугам графа через струк-

турные процедурные вершины. Здесь возможны такие режимы:

•

Блокировка вычислений

до тех пор, пока не будут поставлены все

значения на входы (такая стратегия принята в однородных вычи-

слительных системах);

•

Прозрачность транзита

,когда данные передаются вложенным вер-

шинам без задержек ожидания поставки значений на другие вхо-

ды (это соответствует передаче параметров по необходимости);

•

Смешанный транзит

, когда для одних процедурных вершин при-

нимается одна стратегия, а для других — другая.

Поскольку ациклические коммутационные системы есть одна из форм

задания функциональных систем, для них сохраняются все указанные

выше возможности. Однако если допускаются циклы, то появляются

дополнительные возможности, которые не всегда сводятся к рекурсив-

ным вызовам.

Коль скоро в коммутационной системе активизация вычислений вер-

шины происходит при появлении данных на входных местах, цикли-

ческие графы заставляют говорить об экземплярах, т. е. об активаци-

ях процедур, причем таких, которые могут выполняться параллельно.

Здесь очень важны регламенты на процессы передачи данных по гра-

фу,которые гарантируют,что данные разных активаций не перепутыва-

ются. Эта задача осложняется еще одной проблемой коммутационных

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

зависаний, т. е. бесконечного ожидания поступления данных на вход-

ных местах.

4. Ассоциативные системы как вариантная форма коммутационных си-

стем при задании вычислений переносят акцент на активность данных,

которые ‘знают’, в каких действиях они должны участвовать (это зна-

ние заключено в коде ключа, сопровождающего значение). Соответ-

ственно, основной единицей декомпозиции ассоциативной программы

становятся множества данных,ключи которых (или фрагменты ключей)

можно рассматривать в качестве указателей на процедуры (имен про-

480

ГЛАВА 8. ПОДПРОГРАММЫ

цедур),подобные методам объектно-ориентированного стиля програм-

мирования.

Процедуры-действия в ассоциативных системах выделяются перера-

батываемыми в каждой активации данными. Это выделение задается в

ключах данных. Тем самым обеспечивается разграничение экземпля-

ров (активаций) процедур по данным. В отличие от последовательного

случая, ассоциативные процедуры требуют трех этапов обращения, ко-

торые выполняются асинхронно и в любом порядке:

•

Подготовка вызова

: действия, собирающие параметры в виде спе-

циальной передаточной структуры, которая для входных пара-

метров заполняется по мере их вычисления в окружении, а для

выходных параметров — по мере их подготовки процедурой. В

этой структуре должно быть место и для номера активации;

•

Вызов процедуры

:выделение ей номера активации (системное дей-

ствие) и передача его структуре, сформированной на первом эта-

пе. Это действие будет задержано, когда структура еще не готова;

•

Обращение к процедуре

(аналог перехода к телу процедуры): на-

стройка локальных вычислений для работы.Эти действия в какой-

то момент потребуют извлечения номера активации, после чего

формируется экземпляр процедуры. Тем самым, фактическое вы-

полнение процедуры задерживается до тех пор, пока не будет вы-

полнен предыдущий этап.

Прекращение выполнения процедуры (аналог возврата)может быть ав-

томатическим, если это действие предписано для выполнения, когда

готовы выходные параметры, либо принудительным, как срабатывание

специально проверяемого условия. В обоих случаях необходимо осво-

бождение номера активации, ликвидация локальных данных и переда-

точной структуры.

Из описания процедурного механизма видно, что в нем особое вни-

мание уделяется асинхронному параллельному вычислению всего, что

может быть вычислено по мере готовности операндов, а не путем при-

нудительной либо неявной передачи управления. Таким образом, упра-

вление в ассоциативных системах подчиняется потокам данных (dataﬂow-

вычисления).

8.8. ПРОЦЕДУРЫ В РАЗНЫХ МОДЕЛЯХ ВЫЧИСЛЕНИЙ

481

5. Аксиоматические системы.Аналогом процедуры в такой системе слу-

жит лемма, которая трактуется как факт, уже не нуждающийся в дока-

зательстве в контексте вызова. Контекст вызова, или, точнее, контекст

использования процедуры-утверждения — это набор фактов, для кото-

рых конкретизируется лемма. В качестве аналогов параметров проце-

дуры используются другие факты и предположения, которые конкре-

тизируются (подставляются) при вызове. Выполнению тела процеду-

ры соответствует получение непосредственных следствий из леммы и

подставленных в нее конкретных данных и утверждений.

Из обсуждения нетрадиционных процедур видно, что в их механизмах

проявляется необходимость параллельного и совместного исполнения, пред-

писываемого либо поощряемого соответствующими моделями вычислений.

Задания для самопроверки

1. Устранить неэффективность рекурсивного алгоритма для числе Фибо-

наччи 8.7.2 путем преобразования программы, направленного на запо-

минание вычисляемых значений.

2. Устранить неэффективность рекурсивного алгоритма для числе Фибо-

наччи 8.7.2 путем перехода к итеративной программе.

3. Устранить неэффективность рекурсивного алгоритма для числе Фибо-

наччи 8.7.2 путем использования теоретических результатов, дающих

другое определение чисел Фибоначчи.

4. Сравнить четыре решения задачи про числа Фибоначчи.

Глава 9

Структуры данных

В данной главе анализируется, как организуются структуры перерабаты-

ваемых программой данных.

Первой причиной появления структур данных является то, что система-

тизация и структурирование для сложной информации всегда идут рука об

руку. Поскольку управление и данные взаимосвязаны, иерархически струк-

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

Другая причина связана с тем,что реальные объекты представляются агре-

гатами взаимосвязанных характеристик.Например,хранить координаты точ-

ки пространства как три отдельные переменные — провоцировать ошибки в

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

агрегирования (соединения) данных. А для вычислителя нужно обеспечить,

чтобы в конце концов и аргументы, и результат вычислений сводились на

уровень атомарных объектов. Поэтому агрегаты необходимо уметь разъеди-

нять на составные части.

Третья причина в том, что при составлении программ требуется задавать

регулярные действия для подобно описываемых и подобно интерпретируе-

мых объектов, и хранить промежуточные результаты вычислений, при этом

далеко не всегда можно обойтись атомарными единицами данных.

В последующих параграфах обсуждаются вопросы задания, использова-

ния и хранения структурированных данных, а также средства, предлагаемые

для этого языками программирования.

§ 9.1. ОБЩИЕ КОНЦЕПЦИИ СТРУКТУРИРОВАНИЯ ДАННЫХ

9.1.1. Структура программы и структуры данных

482

9.1. СТРУКТУРИРОВАНИЕ ДАННЫХ

483

Система данных, перерабатываемых программой, базируется на простых

и неделимых понятиях — первичных элементах системы. Выбор базы пер-

вичных элементов зависит от точки зрения на программу, в частности, от

того, что считается существенным и чем можно временно пренебречь. Аб-

стракция рассмотрения в значительной степени определяет и взгляд на дан-

ные. В то же время, различные уровни абстрактности данных требуют раз-

личных языковых средств, иногда своего языка описания обработки. Это ка-

сается и средств оперирования, и структур данных. Реальная моделируемая

программой жизнь содержит не целые, вещественные и иные числа или мас-

сивы, а вполне конкретные объекты, представляемые в программе числами,

структурами, массивами и т. п. Выбор представления сущностей предопре-

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

программного проекта.

Поэтому, если задача с самого начала ставится корректно, правильно го-

ворить о выборе языка программирования, соответствующего решаемой за-

даче. Но часто выбор языка навязан внешними обстоятельствами. В любом

случае программист должен осознавать:

• на какие средства описания он вправе рассчитывать и чего не может

требовать в данной ситуации;

• какие абстракции являются идеально подходящими для решаемой за-

дачи, и как это идеальное моделируется в реальном языке.

Ответ на эти вопросы существенно зависит от квалификации самого про-

граммиста. Первая часть этого положения — вопрос специального образова-

ния программиста, вторая — общей теоретической подготовки.

Обычный язык программирования предлагает широкий ассортимент воз-

можностей организации данных. Следовательно, перед программистом сто-

ит задача выбора не только абстрактного, но и конкретного представления

данных. Видимость, что здесь больше свободы, чем при составлении алго-

ритмов, обманчива. Налицо взаимосвязи и взаимовлияние. Фиксация струк-

тур данных определяет, будет ли хорошо работать тот или иной алгоритм. С

другой стороны, идеально подходящие для алгоритма объекты — не только

образы конкретных объектов, но и прообразы программной структуры дан-

ных, которая не может быть выбрана произвольно. Традиционные критерии

эффективности по времени вычислений и занимаемой памяти ныне являют-

ся отнюдь не самыми важными. На выбор и алгоритмов, и структур данных

существенно влияют ответы на следующие вопросы:

484

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

• насколько понятен сделанный выбор,

• каков уровень адекватности получающегося решения,

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

и его модификации при изменений условий задачи,

• каковы границы возможного для таких модификаций?

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

и соответствующих ей алгоритмов.

Единственный универсальный рецепт, который здесь можно дать, это по-

вышение уровня абстрактности рассмотрения задачи с последующей транс-

формацией выбранного в конкретные структуры. Поэтому важно системати-

ческое изучение возможностей наиболее употребляемых структур данных.

Предварительно стоит обратить внимание на одну особенность вопроса:

общность подходов к структурированию данных и действий, которая обусло-

влена двумя обстоятельствами:

• целостностью процесса разработки программ, для которого структури-

рование данных и действий есть две неразрывные составляющие;

• взаимосвязанностью представлений данных и процессов их обработки.

В первом приближении параллелизм данных и действий в программирова-

нии можно охарактеризовать следующим образом:

• Как данные, так и алгоритмы — структурные конструкции, составляе-

мые программистом для тех или иных целей.

Это положение универсально, т. е. не зависит от используемого язы-

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

очередь со структурным программированием.

• Атомам алгоритмов соответствуют атомарные данные,для которых опре-

делены непосредственные действия вычислителя. Из атомов строятся

структуры.

Для алгоритмов это — последовательно, совместно или параллельно

выполняемые операторы, разветвления, циклы и др., а также процеду-

ры.

Для структур данных это — массивы, записи и др., а также классы объ-

ектов.