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

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

11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ

705

begin Writeln;

Writeln (’OK’);

R := R + ’|’;

end

else

begin Writeln (’^’);

Writeln (’ERR’)

end;

Writeln (R);

Readln;

end.

Программы

PARSER

POLIS

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

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

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

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

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

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

и генерации ПОЛИЗ (изменятся лишь лексические вычисления). Это хоро-

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

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

PARSER

, т. е. модульное

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

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

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

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

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

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

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

трансляторов.

Реализация систем программирования для алгоритмических языков —

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

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

ние обработки, появляются возможности для рекурсивного спуска. Совсем

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

ется лишь монотонность разбиения данных

{Σ

, Σ

, . . . , Σ

, . . . }

по некоторому фундированному отношению , которое отслеживается при

706

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

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

матических форм это свойство гарантируется конечностью перерабатывае-

мой строки и, как следствие, вариантов ее разбора.

Особый вопрос, связанный с реализацией рекурсивного спуска — обес-

печение вычислений без возвратов.Для трансляционного применения это ка-

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

тривать неоднократно, безвозвратность требовать не обязательно. Однако и

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

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

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

но порою ценой усложнения определений и ухудшения их понятности.

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

1. Что будет с программой

FloodFill4

в следующем ‘граничном’ случае,

если в области есть пиксели, лежащие на границе экрана? Исправьте

этот недочет и другие, замеченные Вами.

2. Составьте программу для закрашивания гранично определенных 8-связ-

ных областей.

3. Разработать программу построения множеств (а не последовательно-

стей!) неповторяющихся индексов.

4. Разработать конкретное представление лабиринта, включающее визуа-

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

и слежения за их ходом.

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

содержательное отображение, стоит затратить усилия на построение

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

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

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

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

нено с помощью локальной модификации этой процедуры.

5. Разработайте алгоритм генерации достаточно красивых и интересных

лабиринтов. Некоторые возможные идеи. Размещать а одновременно

пары вертикальных и горизонтальных стенок. Случайным образом вы-

брать комнату, а затем вертикальное или горизонтальное направление.

Использовать технику фрактальной графики.

11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ

707

Сравните Ваш алгоритм с алгоритмом товарища, прежде всего, по эсте-

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

6. Реализовать алгоритм поиска пути в лабиринте с пометками уже прой-

денных комнат и с использованием массива

Way

7. Какие последовательности помечает программа 8.7.4?

8. Программа 8.7.4 составлена с учетом удобного для чтения с экрана вы-

вода информации. Объясните, в каком месте программы эта ‘пользуха’

реализована и каким образом?

9. Написать нерекурсивную программу, делающую то же, что 8.7.4. Срав-

нить решения, дать ответ на вопрос, как повысить эффективность ре-

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

кой. Какие пути повышения эффективности можно предложить допол-

нительно?

10. Программа 8.7.4 содержит неиспользованную процедуру

Inpt

. Зачем

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

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

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

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

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

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

Глава 12

Объектно-ориентированный

подход

В объектно-ориентированном программировании собственно объектный

стиль занимает не более 40%. В остальных случаях это — формальное пред-

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

другим стилям. В настоящее время ООП может рассматриваться как общая

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

граммированием от состояний.

Графовые модели ООП, таблицы переходов и синтаксических таблицы

внешне похожи, что порой создает путаницу. Так что объектно-ориентиро-

ванный стиль естественно разбивать на три направления: рекурсия в форме

ООП, состояния в форме ООП, собственно объекты и роли. В данной главе

мы рассмотрим ООП, ориентируясь на главные области применения.

§ 12.1. ОБЪЕКТЫ

В данном параграфе рассматривается объектная ориентированность в язы-

ках традиционного типа. В операционном плане процедуры объектно-ориен-

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

программирование. Однако здесь процедура уже не может рассматривать-

ся как основная единица декомпозиции программы. Основой декомпозиции

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

этими данными.Эта единица называется объектом. Таким образом,в первом

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

программами, работающими над другими полями. Подпрограммы, включен-

708

12.1. ОБЪЕКТЫ

709

ные в состав объекта, называются его методами.

Как всегда бывает в достаточно сложных и взаимосогласованных систе-

мах

, изменения (в данном случае расширения) в базовом понятии влекут

необходимость адекватной надстройки на следующих уровнях.

12.1.1. Объекты как структуры данных и права доступа

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

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

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

к внутренним данным объекта. Но такое запрещение не может быть абсо-

лютным. Скажем, реализация методов самого объекта должна иметь воз-

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

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

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

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

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

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

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

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

экранированы от внешнего мира. В связи с этим возникает необходимость

специфицировать права доступа к компонентам объекта.

Общепринятый во всех развитых практических объектно-ориентирован-

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

дующий.

public

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

тоды.

private

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

заций методов описываемого объекта.

protected

Специфицирует защищенные данные и методы, доступные дан-

ному объекту и его наследникам.

C++/C#

эти спецификации могут применяться также к полям записей и

объединений.

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

с некоторой натяжкой может быть применена к ним.

710

ГЛАВА 12. ООП

В конкретных системах ООП (

C++

Java

Object Pascal

) имеются и

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

каций различается порой до смешного.

Внимание!

C++

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

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

и в

Java

, и в

Object Pascal

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

нию считаются закрытыми!

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

ничения доступа (см., напр., § 8.6.2), которые естественно возникли при раз-

витии модульности. Поэтому модульность и объектная ориентированность

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

языке

Java

, где открытый класс (

public class

) практически отождествляется

с содержащим его

JAVA

-файлом.

Рассмортим пример описания класса:

Программа 12.1.1

{ Object Pascal }

TBits = class(TObject)

private

FSize: Integer;

FBits: Pointer;

procedure Error;

procedure SetSize(Value: Integer);

procedure SetBit(Index: Integer; Value: Boolean);

function GetBit(Index: Integer): Boolean;

public

constructor Create; override;

destructor Destroy; override;

function OpenBit: Integer;

property Bits[Index: Integer]: Boolean read GetBit write SetBit; default;

property Size: Integer read FSize write SetSize;

end;

В одном из стандартных пакетов

Visual C++

версии 6 имеется комментарий: «Данный тип

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

public.

12.1. ОБЪЕКТЫ

711

...

implementation

...

constructor Tbits.Create;

begin

inherited Create;

Fsize:=0;

Fbits:=nil;

end

...

Уже на этом примере видно несколько особенностей объектных типов.

С точностью до спецификаторов

private

public

(а также других описа-

телей и соглашений, регламентирующих доступ к составляющим объектов)

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

ным дополнением: описание объектов обязательно включает объявление их

методов, определяющих возможное поведение объектов. Более того, в язы-

ках

C# /C++

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

объединены под синтаксическим понятием объекта, и почти все специфика-

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

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

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

зуются специфицированные имена (смотри пример выше)с указанием имени

класса, метод которого описывается. Например:

procedure TBits.Error;

begin

raise EBitsError.CreateRes(SBitsIndexError);

end;

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

поля объектов могут специфицироваться как

property

, при этом операции

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

ды данного объекта (обычно закрытые). Таким образом, использование в вы-

ражении имени

TheBits.Bits[i]

, где

TheBits

— конкретный объект типа

Tbits

является неявным вызовом функции

TheBits.Getbit(i)

. Соответственно, при-

сваивание

712

ГЛАВА 12. ООП

TheBits.Bits[i]:=true;

интерпретируется как вызов

TheBits.Setbit(i,true);

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

структоры.В расширениях

Pascal

конструкторы описываются как

constructor

а деструкторы как

destructor

. Даже вызов конструктора несколько отличает-

ся по синтаксису от вызова обычного методов. В частности, в

Object Pascal

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

объекта (поскольку в момент создания самого объекта еще нет), например,

Tbits.Create;

Это решение достаточно логично, но в других объектно-ориентированных

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

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

a. выделение нужной для объекта памяти (вычисление ее размеров осуще-

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

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

которой принято решение о создании объекта, и

c. вызов конструктора, который завершает создание объекта.

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

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

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

нем самом и унаследованные им от ‘родителей’: создается ли объект весь

сразу или по частям (сначала ‘родительские’ части, а затем — собственные.

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

Java

и в

C++

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

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

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

класса-наследника

. Как всегда, данная неоднозначность — следствие теоре-

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

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

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

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

12.1. ОБЪЕКТЫ

713

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

вопросов.

C++

Java

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

С++

Java

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

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

несколько.

Деструкторы в

С++

носят имя класса с отрицанием (например,

Tbits

). В

языке

Java

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

на систему сборки мусора.

Система объектно-ориентированного программирования по умолчанию

предлагает простейшие конструкторы и деструкторы. В частности, а параме-

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

в описании. В

Object Pascal

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

имя

Create

, а деструктор —

Destroy

, и параметров они не имеют.

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

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

объект может являться не чистым объектом данного класса, а его наследни-

ком, а наследник может заменить некоторые методы (как у нас сделано для

конструктора

Create

). При описании нового метода на старый метод можно

сослаться как на

inherited

, (

super

в языке

Java

) и явно выписать лишь новые

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

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

полнения, которые рассматриваются в следующем пункте. Именно эта воз-

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

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

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

ширение является непринципиальным).

В языках

С++

Java

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

static

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

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

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

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

Object

Pascal

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

языка

Pascal

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

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

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

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

цию

implementation

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

initialization

714

ГЛАВА 12. ООП

модуля.

12.1.2. Наследование и полиморфизм

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

подобный

{Object Pascal}

CRoleOfActor = class(CRole)

Тело описания класса

end;

/* C++ */

class CRoleOfActor:: public CRole

{ Тело описания класса };

/* Java */

class CRoleOfActor extends CRole

{ Тело описания класса };

(12.1)

Это означает,что новый класс

CRoleOfActor

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

деленного класса

CActor

, а он его предками. Отношение наследования тран-

зитивно, так что

CRoleOfActor

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

ков

CActor

. Наследник включает все данные и все методы предков. Наслед-

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

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

ные объекты классов-предков, как правило, не приходится. Далее, скобки в

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

делением отношения порядка на множестве классов. Математический смысл

Turbo Pascal

Object Pascal

не имеет предков лишь один, предопределенный в системе,

класс

TObject

. Если предки класса не указаны, то он считается прямым наследнком

TObject

так что описания

Hermit = сlass

Hermit = сlass(TObject)

эквивалентны.