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

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

12.2. ОБЪЕКТНАЯ МОДУЛЬНОСТЬ

725

BEmpty : Boolean;

NotEl : PElemContainer;

constructor InitQueue ( InputMaxSize : Integer);

procedure PutElQueue ( X : PElemContainer );

function GetElQueue : PElemContainer;

function StateQueue : States;

procedure IncI ( var I : Integer );

destructor DoneQueue;

end;

Модуль

AllQueue_5_5

предлагает описание типа

Tqueue

с использованием

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

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

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

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

ются прямые обращения, например, к

и другим полям, не имеющим

смысла для нового представления. И хотя это дурной стиль, но нельзя га-

рантировать, что все использования

AllQueue_5_5

будут подчиняться никак

не поддержанным соглашениям. Надежность программирования снижается.

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

TURBO

Pascal

дополнительных средств защиты.

Мы обстоятельно обсудили недостаточность средств

TURBOPascal

’я вер-

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

(в этой связи сравните разделы

interface

модулей

AllQueue_5_5

IntQueue

из пункта 8.6.1). Поэтому приведем пример на более развитом языке:

TURBO

Pascal7.0

.В новом варианте для транслятора дается указание,какие из средств

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

public

в объявлении типа),а какие скрывать от пользователя (секции описаний

private

Обратите внимание на эти спецификаторы — их названия были приведены

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

дартном языке

Pascal

Программа 12.2.2

unit AllQueue_7_0;

interface

uses ContainerUnit; {

модуль, предоставляющий средства

}

{

хранения объектов разной природы

}

type States = ( Full, Empty, Normal );

726

ГЛАВА 12. ООП

Pqueue = ^Tqueue;

Tqueue = object ( Container );

private

MaxSize,

IB,

IE : Integer;

BFull,

BEmpty : Boolean;

NotEl : PElemContainer;

public

constructor InitQueue ( InputMaxSize : Integer);

procedure PutElQueue ( X : PElemContainer );

function GetElQueue : PElemContainer;

function StateQueue : States;

private

procedure IncI ( var I : Integer );

public

destructor DoneQueue;

end;

...

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

public

private

.Расположение их отно-

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

TURBO

Pascal

7.0 есть и другие спецификаторы управления доступом, повышающие

надежность программ.

Язык

Object Pascal

системы программирования

Delphi

с точки зрения мо-

дуляризации мало чем отличается от

TURBO Pascal

7.0: появились новые

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

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

ства, задаваемые описателем

property

) и все. Некоторые из новых средств

системно зависимы, что отрицательно сказывается на качестве языка (см. об-

суждение системы

Delphi

на стр. 85).

Object Pascal

’е принято прагматическое соглашение о том, что все объ-

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

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

объекты, размещение которых на стеке не разрешается. Это соглашение, от-

ражающее реальную потребность, поскольку в програмах оперировали в по-

давляющем большинстве случаев с указателями на объекты, избавляет от не-

12.2. ОБЪЕКТНАЯ МОДУЛЬНОСТЬ

727

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

type Pqueue = ^Tqueue;

совмещая два описания в одном:

type Tqueue = class ( Container );

Соответственно, исчезает необходимость изображать переменные этих ти-

пов,используя “^”для извлечения объекта по указателю. Таким образом,наш

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

му, объектный тип).

В последних примерах мы приводили описание только раздела интерфей-

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

программе 8.6.1, с учетом синтаксических модификаций, требуемых описа-

нием класса.

В языке

Java

возникает противоположная языкам линии

Pascal

задача.

Модуль является классом. Класс может быть создан и уничтожен. А если нам

этого не нужно, нужно лишь воспользоваться понятиями из данного класса?

Для этой цели в

Java

предлагается следующее решение. Описать лишь один

конструктор без параметров и объявить его

private

. Тем самым он не сможет

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

щается в модуль.

Вопросы для самопроверки

1. Постройте абстрактно-синтаксическое представление вызова динами-

ческого метода. Внимание! Возможны разные схемы реализации дина-

мического связывания, поэтому сравните Ваше решение с двумя (прак-

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

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

Object

Pascal

, специфицируемыми как

virtual

dynamic

2. Как по-Вашему, полезно ли чем-нибудь наличие в

Object Pascal

двух

спецификаций

virtual

dynamic

? Если полезно, то в каких случаях?

Глава 13

Сентенциальные методы

Сентенциальное программирование возникает тогда, когда данные име-

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

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

ствует инварианту:

Действия глобальны, условия глобальны. (13.1)

В этом случае необходимы мощные средства распознавания глобальных усло-

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

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

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

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

описании перестроек структуры.

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

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

PROLOG

Рефал

при рас-

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

нения перестройки. Это качество

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

условий,

(13.2)

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

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

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

от приоритетов. Хотя проверка приоритетов и выбор действия с наивысшим

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

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

728

13.1. КОНКРЕТИЗАЦИЯ

729

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

го действия.

Следует заметить, что еще одна особенность, общая для трех стилей: сен-

тенциального, от приоритетов и событийно-ориентированного —

Отделение проверки условий от выполнения действий (13.3)

представляется общей характеристикой технологических решений для сти-

лей, соответствующих инварианту (13.1).

В настоящее время глобальная проверка условий осуществляется в систе-

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

Метавыражение отличичается от выражения тем, что в нем встречаются пе-

ременные. При проверке выясняется возможности отождествить некоторые

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

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

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

программы информацию. Такой способ работы согласуется с формулиров-

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

нельзя считать a priori исчерпывающим. В дальнейшем могут появиться дру-

гие формы глобальной проверки данных.

§ 13.1. КОНКРЕТИЗАЦИЯ

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

переменные встречаются лишь в метавыражении и поиск их значений про-

исходит путем подбора без рекурсии. Идея конкретизации была явно сфор-

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

Рефал

Язык

Рефал

был создан В. Ф.Турчиным для программирования символь-

ных преобразований. Исходный толчок он получил от идеи алгорифмов Мар-

кова (см. стр. 849), но она была полностью пересмотрена в ходе работы по

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

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

уделено внимания.

Язык определен через три компоненты: структуру данных,

Рефал

-маши-

ну, обрабатывающую эти данные,и собственно конкретный синтаксис языка.

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

Прежде всего,рассмотрим структуру данных,обрабатываемых

Рефал

ом.

Она состоит из основного поля данных (поля памяти), в котором перед ка-

ждым шагом исполнения выделяется активная часть (поле зрения), и стеков

730

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

глобальных данных (закопанные данные). Данные в поле зрения и закопан-

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

туры поля памяти. Далее, поскольку и программа имеет практически ту же

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

(метаданные), расширяющая поле памяти.

Определение 13.1.1. Выражения языка

Рефал

1. Атомы являются выражениями. В конкретном синтаксисе нынешнего

Рефала

атомы делятся на

(a) Символы (байты);

(b) Составные символы (имена, определенные в программе);

;

(d) Действительные числа.

2. Любая последовательность выражений является выражением.

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

нием.

4. Если E — выражение,A — описанный в программе атом,AE,заключен-

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

циональным выражением). A называется детерминативом этого выра-

жения.

В конкретном синтаксисе

Рефала

функциональные скобки обозначаются

, структурные —

( )

Объектное выражение — выражение, не содержащее функциональных

скобок. Минимальное функциональное выражение — выражение, имеющее

вид

, где E — объектное выражение. Поле памяти

Рефал

-машины в лю-

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

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

скобки. Поле зрения (активная часть) поля памяти — первое из встречаю-

щихся в поле памяти минимальных функциональных выражений.

Конец определения 13.1.1.

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

обрабатывающей содержимое скобок. Поэтому в ходе вычислений не могут

образовываться выражения вида

. В подавляющем большинстве

13.1. КОНКРЕТИЗАЦИЯ

731

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

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

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

честве детерминативов.

Пример 13.1.2. Рассмотрим пример памяти

Рефал

-машины в ходе вычи-

слений.

Поле памяти:

’aaxzACDE’ <Sort <Perm ’G’1.5E5> <Perm 115 ’F’> <Perm 112 -2.0E-5>><Sort

AllRight Sort Perm ’QRTS’>’XZ<(’

Поле зрения выделено в поле памяти жирным шрифтом. Заметим, что в по-

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

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

ся вне программных скобок; в нашем случае

’aaxzACDE’

’XZ<(’

). Далее, у

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

но имеющие парные и не влияющие на структурирование выражения. Далее,

если первый атом

Perm

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

Perm

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

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

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

гого. И, наконец, еще одна тонкость. Если

123

— это один символ,

’123’

—

три символа,

-123.0

— опять один символ, то

-123

— два символа: символ

’-’

после которого стоит число.

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

несколько стеков закопанных выражений, например:

Stack1 ’=’ 15 Stack2 ’=’ <Perm B A>

21 <Perm C2 C1>

-45 <Perm ’X’ 20>

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

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

ций.

Конец примера 13.1.2.

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

сматриваются как общие области памяти, лучше в каждом модуле иметь свой стек. К сожа-

лению, связи между стеками и модулями в явном виде в

Рефал

-программах нет.

732

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

Пусть есть строка

< AB(CD)(E)F>

. Она практически во всех

Рефал

-систе-

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

Этот формат представления стал общераспространенным для

Рефал

-систем,

(

) ( )

C D E

Рис. 13.1. Структура данных

Рефала

начиная с реализации, описанной в [69]. Однако он не является обязатель-

ным.

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

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

Рассмотрим конкретный синтаксис выражений. Идентификатор — любая

последовательность цифр и букв, начинающаяся с большой буквы. Иденти-

фикатор является символьным литералом и представляет составной символ.

Символы, заключенные в одинарные

’ ’

или двойные

" "

кавычки, являют-

ся символьными литералами, представляют сами себя. Дважды повторенная

кавычка представляет себя. Если вне кавычек встречается символ, не являю-

щийся скобкой, частью идентификатора или числа, это трактуется как ошиб-

ка.

Определение 13.1.3. Метавыражение

Рефала

может содержать перемен-

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

конкретном синтаксисе как

тип.атом

. Переменные не могут быть детермина-

тивами. В стандартном

Рефале

имеются переменные трех типов: символь-

При реализации языка

Рефал

В. Ф. Турчин задумался, как избежать слишком частых

обращений к каким-то суррогатам возможностей традиционных языков. Поэтому он решил

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

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

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

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

ранних, см. параграф, относящийся к языку

PROLOG

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

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

Рефал

13.1. КОНКРЕТИЗАЦИЯ

733

ные (

s.First

), термовые (

t.Inner

) и общие (

e.Last

). Метавыражение называется

образцом, если оно не содержит функциональных скобок.

Конец определения 13.1.3.

Значением символьной переменной служит атом,термовой —неделимое объ-

ектное выражение (терм,в терминах

Рефала

),то есть символ или выражение

в скобках, общей — произвольное (может быть, пустое) объектное выраже-

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

ждый идентификатор является атомом.

Рефал развивался как язык символьных преобразований в самом широ-

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

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

метакодирования, взаимно-однозначно и взаимно-обратно преобразующие

произвольное метавыражение в объектное и наоборот. Таким образом, по-

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

грамм и затем выполнять их «на лету». Такая возможность, просто гибель-

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

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

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

ка.

Тем самым мы естественно перешли от модели данных к модели вычи-

слений.

13.1.2. Модель вычислений и Рефал-программа

Основными двумя шагами при

Рефал

-вычислениях являются конкрети-

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

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

лишь частный случай конкретизации.

Конкретизацией образца Me в объектное выражение E называется такая

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

ной подстановки Me совпадет с E.

Заметим, что одно и то же метавыражение может иметь много конкрети-

заций в одно и то же объектное выражение. Например, рассмотрим метавы-

ражение

e.Begin s.Middle e.End

(13.4)

К этой концептуальной конфетке еще бы красивую обертку!

734

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

и объектное выражение

AhAhAh ’OhOhOh’ (Ugu’,’Udgu) ’(((’ Basta’!’

(13.5)

Имеется 11 вариантов конкретизации (13.4) в (13.5) (проверьте!).

Если у метавыражения

есть много вариантов конкретизации в

, то

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

Пусть

Env1

Env2

—два варианта конкретизации

.Рассмотрим все

вхождения переменных в

. Если

Env1

Env2

не совпадают, они приписы-

вают некоторым переменным различные значения. Найдем в

самое первое

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

Env1

Env2

приписывают разные

значения и сравним длину этих значений. Та из конкретизаций, в которой

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

ствует другой и имеет приоритет перед ней.

Например, сопоставим объектное выражение

(A1 A2 A3)(B1 B2)

с образ-

цом

e.1 (e.X s.A e.Y) e.2

. В результате получится следующее множество ва-

риантов сопоставления:

{e.1 = , eX = , sA = A1, eY = A2 A3, e.2 = (B1 B2) }

{e.1 = , eX = A1, sA = A2, eY = A3, e.2 = (B1 B2) }

{e.1 = , eX = A1 A2, sA = A3, eY = , e.2 = (B1 B2) }

{e.1 = (A1 A2 A3), eX = , sA = B1, eY = B2, e.2 = }

{e.1 = (A1 A2 A3), eX = B1, sA = B2, eY = , e.2 = }

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

т. е. самый первый вариант находится на первом месте и т. д. Описанный

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

слева направо.

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

Рефале

, называ-

ется проецированием и согласован с введенным нами отношением порядка.

Опишем его (описание взято из учебника Турчина [90]). Обратите внима-

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

рация ‘проецируется’ на свою частную реализацию, одновременно повыша-

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

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

Алгоритм для сопоставления объектного выражения E с образцом P

РЕФАЛ-5

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

выражений. Пропуски между элементами будут называться узлами. Сопо-

ставление E : P определяется как процесс отображения, или проектирова-