Объектно-ориентированное программное обеспечение

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

"Тверской государственный технический университет"

Отчет по курсовой работе по дисциплине

"Объектно-ориентированное программное обеспечение"

Выполнила:

Студентка группы

ПОВТ 0806

Шуралева Н.В.

Проверил: Биллиг В.А.

Тверь 2012



Содержание

Введение

1. Проектирование семейства классов

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

3. Паттерн Decorator

4. Паттерн Визитер

5. Паттерн Наблюдатель

6. Двусвязные списки



Введение

Объектно-ориентированное, или объектное, программирование (в дальнейшем ООП) -- парадигма программирования, в которой основными концепциями являются понятия объектов и классов. В случае языков с прототипированием вместо классов используются объекты-прототипы.

ООП возникло в результате развития идеологии процедурного программирования, где данные и подпрограммы (процедуры, функции) их обработки формально не связаны. Для дальнейшего развития объектно-ориентированного программирования часто большое значение имеют понятия события (так называемое событийно-ориентированное программирование) и компонента (компонентное программирование, КОП).

Формирование КОП от ООП произошло, как случилось формирование модульного от процедурного программирования: процедуры сформировались в модули -- независимые части кода до уровня сборки программы, так объекты сформировались в компоненты -- независимые части кода до уровня выполнения программы. Взаимодействие объектов происходит посредством сообщений. Результатом дальнейшего развития ООП, по-видимому, будет агентно-ориентированое программирование, где агенты -- независимые части кода на уровне выполнения. Взаимодействие агентов происходит посредством изменения среды, в которой они находятся.

Языковые конструкции, конструктивно не относящиеся непосредственно к объектам, но сопутствующие им для их безопасной (исключительные ситуации, проверки) и эффективной работы, инкапсулируются от них в аспекты (в аспектно-ориентированном программировании). Субъектно-ориентированное программирование расширяет понятие объект посредством обеспечения более унифицированного и независимого взаимодействия объектов. Может являться переходной стадией между ООП и агентным программирование в части самостоятельного их взаимодействия.

Первым языком программирования, в котором были предложены принципы объектной ориентированности, была Симула. В момент своего появления (в 1967 году), этот язык программирования предложил поистине революционные идеи: объекты, классы, виртуальные методы и др., однако это всё не было воспринято современниками как нечто грандиозное. Тем не менее, большинство концепций были развиты Аланом Кэйем и Дэном Ингаллсом в языке Smalltalk. Именно он стал первым широко распространённым объектно-ориентированным языком программирования.

В настоящее время количество прикладных языков программирования (список языков), реализующих объектно-ориентированную парадигму, является наибольшим по отношению к другим парадигмам. В области системного программирования до сих пор применяется парадигма процедурного программирования, и общепринятым языком программирования является язык C. Хотя при взаимодействии системного и прикладного уровней операционных систем заметное влияние стали оказывать языки объектно-ориентированного программирования. Например, одной из наиболее распространенных библиотек мультиплатформенного программирования является объектно-ориентированная библиотека Qt, написанная на языке C++.



1. Проектирование семейства классов

Проектирование семейства начинается с создания отложенного класса- класса, в котором для ряда методов задана только спецификация - контракт и сигнатура, но не задана реализация методов, которую обеспечат потомки класса в соответствии со своей спецификой. Мы подробно рассмотрим важнейшие для проектирования понятия - "программы с дырами", отложенные методы, переопределение и переобъявление методов наследниками класса. Отложенные классы и компоненты

Взгляните на список компонентов класса VEHICLE ( рис 2.1).

Здесь можно увидеть компонент movenext. В тексте класса он не появляется, так как наследуется от класса MOVING. Но в тексте MOVING вы найдете следующее объявление

Рис. 2.1. Компоненты VEHICLE в EiffelStudio

move_next -- Переместиться в следующую позицию, согласно расписанию.

deferred

end

Это новая форма объявления. Ранее объявление метода имело тело, начинающееся с ключевого слова do c последующими за ним операторами. Объявление компонента как deferred означает, что компонент имеет спецификацию -- сигнатуру и контракт, но не имеет реализации. Реализация отложена (отсюда и имя ключевого слова) и возлагается на классы-потомки. Действительно, в классе TAXI можно увидеть реализацию:

move_next

-- Переместиться в следующую позицию, согласно расписанию.

do

... Последовательность операторов...

end

Реализация учитывает специфику объектов класса TAXI. Класс TRAM обеспечивает свою специфическую реализацию компонента.

Мы говорим, что эти классы делают компонент эффективным. Отныне мы будем иметь два вида компонентов класса: эффективные (спецификация + реализация) и отложенные (только спецификация). От компонентов эти термины переходят на классы и их типы.

Как обычно, различие между классами и типами связано с универсальностью. Вы могли видеть, что класс LIST является отложенным классом (поскольку он описывает общее понятие списка с реализацией, возложенной на эффективных потомков, таких как LINKED_LIST ). Типы LIST[TAXI] и более общий тип LIST[G] для любого G являются отложенными типами.

Причина, по которой movenext является отложенным компонентом класса MOVING, состоит в том, что на этом уровне:

· мы знаем, что компонент применим ко всем движущимся объектам, и хотим быть уверенными, что все фактические объекты будут обладать некоторой его версией;

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

Класс MOVING специфицирует существование компонента, но ответственность за подходящую реализацию лежит на его правильных потомках, таких как TAXI.

Отсутствие реализации по умолчанию в классе MOVING создает проблему: каков будет эффект от вызова m.movenext, если объект, присоединенный к m, имеет тип MOVING или VEHICLE, когда в обоих классах компонент отложен и, следовательно, не имеет реализации? Ответ прост: таких объектов не существует.

Правило создания "Нет отложенному типу"

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

Это защищает нас от создания объектов типа MOVING или VEHICLE (например, при попытке create myvehicle ). Благодаря этому становится невозможным вызывать отложенный метод, такой какmovenext объектом myvehicle.

Так что, если тип отложен, то нет объектов этого типа. Но при этом можно иметь переменные (и другие сущности и выражения) этого типа, например, myvehicle. Эти переменные можно присоединять к эффективным объектам соответствующих типов, таких как TAXI в нашем примере. Фактически вся идея отложенных компонентов, классов и типов имеет смысл только благодаря полиморфизму и динамическому связыванию.

Поскольку создание требует эффективного типа, при желании создать объект необходимо знать, эффективным или отложенным является соответствующий класс. Чтобы выяснить это, недостаточно знакомства с методами класса, поскольку отложенные компоненты могут наследоваться. Вообще изучение текста классов противоречит принципу скрытия информации. "Быть отложенным" -- это ключевое свойство класса, явно им провозглашаемое. Фактически, сразу же после раздела note-класса, поставляющего общую информацию о классе, первое, что говорит класс всему миру, -- является ли он отложенным.

Правило отложенного класса

Объявление отложенного класса должно начинаться с ключевых слов deferred class (вместо просто class для эффективных классов).

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

В данном правиле "отложенный класс" понимается в соответствии с определением как класс, у которого, по крайней мере, один из методов не имеет реализации и, следовательно, является отложенным. При этом метод может быть как наследуемым, так и введенным в классе. Правило гласит, что это знание не должно оставаться информацией для внутреннего употребления, но должно стать частью интерфейса класса, отражаемого в контрактном облике класса. В нашем примере можно проверить, что классы MOVING и VEHICLE начинаются с deferred class.

В языке Eiffel разрешается объявлять класс как deferred class даже в том случае, когда у класса нет отложенных компонентов. Такой класс также рассматривается как отложенный, расширяя наше определение. Это полезно, если вы проектируете класс как предка семейства классов и хотите избежать создания экземпляров этого класса.

Будем более точными: объявление класса deferred защищает от создания прямых экземпляров. Концепции этой лекции требуют пересмотра понятия "экземпляр". До сих пор экземпляр типа (или лежащего в его основе класса) понимался просто как объект периода выполнения, соответствующий статическому описанию, задаваемому классом. Все это правильно, но теперь требуется ввести уточнения и различать прямой и непрямой случаи.

Экземпляр, прямой экземпляр

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

Следствием правила создания "Нет отложенному типу" является то, что у отложенного типа нет прямых экземпляров, как в случае с классами MOVING и VEHICLE. Но оба класса могут иметь экземпляры -- прямые экземпляры эффективных потомков, таких, как TAXI.

Эти определения непосредственно отражают концепцию полиморфизма: объявление x типа T означает, что вы хотите, чтобы во время выполнения x обозначал экземпляр этого типа. С введением полиморфизма мы полагаем, что теперь понимаются не только объекты, непосредственно выводимые из T -- прямые экземпляры, но и, рекурсивно, экземпляры любого согласованного типа (потомков T ).

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

· Библиотека EiffelBase, содержащая реализацию структур данных и алгоритмов. Библиотека вводит глобальную таксономию фундаментальных структур, используемых в информатике. На вершине иерархии можно видеть такие классы, как LINEAR (структуры, обходимые линейно) и FINITE (конечные структуры). Ниже по иерархии находятся классы, задающие специфические структуры, которые являются эффективными потомками классов верхнего уровня.

· Графическая библиотека EiffelVision. Здесь также существует кластер классов, задающих геометрические фигуры, на верхнем этаже которого находится отложенный класс FIGURE, а ниже по иерархии находятся классы, задающие такие фигуры, как круг и квадрат. Таксономия, принятая для геометрических фигур, служит излюбленным примером в учебниках, рассматривающих наследование. Но в данном случае здесь нет ничего академического -- это полезная часть важной прикладной библиотеки классов.

Некоторые языки программирования, в том числе такие известные, как C# и Java, предлагают языковую конструкцию, называемую interface (это понятие рассматривается в приложениях, посвященных этим языкам). Класс, объявленный с таким ключевым словом, называется интерфейсом, и его главная особенность состоит в том, что все его методы отложены (не имеют контрактов) и должны быть реализованы потомками интерфейса¹⁾.

Отложенные классы являются более общей концепцией: как следует из определения, класс отложен, как только он имеет один отложенный метод, но он может иметь смесь отложенных и эффективных методов. Это дает возможность использования механизма отложенных классов для возрастающего проектирования. Проектирование обычно начинается с задания абстракций, которые определяются в виде классов, в которых большинство методов отложено (по духу близкие к интерфейсам, где все методы отложены). Затем по мере уточнения проблем, появляются потомки, реализующие часть отложенных методов. На заключительных этапах проектирования строятся полностью эффективные классы. Это и есть ОО-вариант общего процесса уточнения в процессе проектирования.

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

search (v: G)



Передвинуться к первой позиции (или после текущей), где появляется v.

Если такой позиции нет, то убедиться, что переменная exhausted будет иметь значение true.

do

from until v = item loop forth end

end

Классы EiffelBase представляют списки и другие подобные им структуры как потомков класса LINEAR, где и появляется приведенный код (в более полной версии учитывается различие между равенством ссылок и равенством объектов). Реализация forth, однако, зависит от реализации, выбранной для списков (использующей массив, ссылочные структуры и так далее). Поэтому в классе LINEAR метод forth является отложенным:

forth

-- Переместить курсор к следующей позиции

require

in_range: not after

deferred

ensure

increased: index = old index + 1

end

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

Каждый эффективный потомок LINEAR реализует forth. Для списка, построенного на массиве, где курсор задается индексом, достаточно выполнить присваивание index:= index + 1. Для связного списка ( LINKEDLIST, TWO_WAY_LIST ) детали более сложны. Но методу search нет дела до деталей: все, что ему нужно, -- это вызвать forth, зная спецификацию, заданную контрактом, а не реализацией.

Имя "Программа с дырами" отражает подход к возрастающему конструированию ПО. На каждом уровне абстракции используется вся известная на этом уровне информация: та, что может быть полностью реализована (эффективные компоненты, не включающие вызовов отложенных методов), те методы, которые могут быть только специфицированы, и те, которые допускают реализацию, использующую вызовы отложенных методов, подобные search в LINEAR. Мы можем рассматривать результат как частично сконструированную программу, дыры которой должны быть заполнены в процессе уточнения при конструировании потомков.

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

Переопределение

Когда класс реализует отложенный компонент, он задает первую реализацию метода, который до сих пор у предков имел только спецификацию. Чтобы использовать в дальнейшем преимущества динамического связывания и сделать архитектуру еще более гибкой, разрешается потомку дать свою собственную реализацию, несмотря на то, что родитель уже задал родительскую реализацию компонента. Мы будем говорить, что класс переопределяет ( red-ifine в Eiffel, override в C++, C#) компонент. Переопределение дополняет только что изученный механизм эффективизации:



Рис. 2.2. Формы переопределения

На диаграмме наиболее правый случай показывает, что при наследовании отложенного компонента можно не только сделать его эффективным (следуя ветви, помеченной как Effecting), но также изменить его, оставляя на время отложенным. Это происходит в том случае, когда наследник меняет спецификацию метода -- сигнатуру или контракт, -- что также рассматривается как переопределение. В дополнение к списку вариантов отметим возможность отмены реализации (Undefinition), при которой реализация родителя забывается, метод снова становится отложенным и готов начать новую жизнь.

Переобъявление наследуемого компонента означает изменение чего-либо или всего - сигнатуры, контракта, реализации, а также удаление реализации. Варианты включают задание реализации ( effecting ), переопределение ( redefinition ), отмену реализации ( undefinition ).

Нет необходимости в изучении отмены реализации, поскольку это своеобразная операция (хотя в ней ничего трудного или загадочного -- примеры ее применения можно найти в EiffelBase, проведя поиск по ключевому слову undefine ). Переопределение, с другой стороны, -- широко распространенная операция.

В качестве примера рассмотрим из библиотеки Traffic класс DISPATCHTAXI, который наследует от TAXI и представляет понятие такси, находящегося под управлением диспетчерской службы, в противоположность тем такси, которые курсируют по улицам и ищут пассажиров, полагаясь на собственную удачу. Процедура take по-разному реализована для этих двух типов такси, поскольку в случае диспетчера необходимо уведомлять его о каждой посадке и высадке пассажиров. На диаграмме наследования переопределяемый компонент отмечен как "++" (идея в том, что определение дает один +, а второй добавляется при изменении реализации, делая метод "более эффективным").

Рис. 2.3. Переопределение

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

Для переопределения наследуемого компонента необходимо задать его новое объявление в тексте класса, но также необходимо объявить ясно, громко и недвусмысленно всему миру о таком переопределении. Для этого задается предложение redifine в соответствующей inherit части класса:

class

DISPATCH_TAXI

inherit

TAXI redefine take end

feature

take (from_location,to_location: LOCATION)

-- Перевезти пассажиров из from_location в to_location

do

... Новая реализация...

end

... Другие компоненты и оставшаяся часть класса...

end

Если класс переопределяет несколько компонентов, он перечисляет все: redifinef, g,...end Цель предложения redefine -- это ясность и безопасность. Важное правило надежного ОО-программирования состоит в том, что имя компонента в классе не должно использоваться для именования двух различных методов. Эта ситуация, известная как перегрузка ( overloading ), допускается в некоторых языках программирования, что увеличивает риск непонимания. Предложение redefine поясняет клиенту класса, читающему текст, отношение с компонентом родителя, имеющим совпадающее имя: это не новый компонент с тем же именем, а переопределение компонента.

Если пропустить предложение, возникнет ошибка на этапе компиляции, так как класс полагает, что в нем определены два метода с одним именем (перегрузка), что запрещено правилами Eiffel.

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

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



group_move (taxi_ fleet: LIST [TAXI]-- Смотри далее о классе TARGET

-- Заставляет все такси в taxi_fleet следовать одним маршрутом.

do

from taxi_ fleet.start until taxi_ fleet.after loop

taxi_ fleet.item.take(...) taxi_ fleet.forth

end

end

В этой программе каждый элемент списка будет выполнять версию take либо из класса TAXI, либо DISPATCHTAXI, в зависимости от того, чьим прямым потомком является элемент. Это подобно нашим прежним примерам с полиморфными переменными и структурами данных. Единственная разница в том, что TAXI эффективно и, следовательно, имеет прямые экземпляры, в то время как MOVING и VEHICLE отложены и таковых не имеют.

Если вы переопределяете метод, родительская версия известна как предшественник (precursor) метода. Довольно часто новая реализация основывается на версии предшественника. Вместо простого дублирования кода (разве я не упоминал, что copy-paste -- не лучшая идея?) можно использовать ключевое слово Precursor. Новая реализация take в DISPATCHTAXI выглядит следующим образом:

take (from_location,to_location: LOCATION)

-- Перевезти пассажиров из from_location в to_location

do

Precursorffrom_location, to_location)

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

end



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

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

За пределами скрытия информации

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

my_vehicle.load (...)

вы запрашиваете некоторую абстрактную операцию load, применяемую к целевому объекту, но так как вам не известно (переменная myvehicle, возможно, полиморфна), какой точно тип имеет связанный с ней объект, -- динамическое связывание означает, что вы не знаете, какой именно метод будет вызван.

В этом причина важности контрактов. То, что вы должны знать, заключено в исходном контракте load, включенном в отложенный класс VEHICLE. Контракт описывает семантику load -- загрузку nпассажиров в транспортное средство. Это справедливо для всех вариантов, хотя каждый из них отличается деталями реализации.

Выбор из многих вариантов

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

load (v: VEHICLE; n: INTEGER)

-- Загрузить n пассажиров в v.

do

if "v объект tram" then

"Применить алгоритм посадки в трамвай"

elseif "v объект taxi" then

"Проверить, что число пассажиров не более 4-х"

"Применить алгоритм посадки в такси"

elseif...

end

end

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

· Когда вариантов много, приходится строить длинный, а в результате сложный оператор if (применение конструкции с разбором случаев в таких ситуациях гораздо предпочтительнее).

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

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

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

Появление в ПО структуры решения с многими ветвями, как в вышеприведенной программе, должно настораживать, поскольку может быть результатом плохого проектирования.

Почувствуй методологию

Сражение с синдромом "Много явных вариантов"

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

Этот совет проектировщику не является абсолютным правилом. Не все условные операторы следует заменять динамическим связыванием. Наиболее "подозрительными" кандидатами являются проверки типа объекта, как в примере. Вместо алгоритма, осуществляющего выбор между возможными типами объектов и, следовательно, обязанного знать все возможные типы, лучше выбрать алгоритм, основанный на наследовании и динамическом связывании.

Наследование делает такое решение лучшим. При добавлении класса, как только найдено для него соответствующее место в иерархии наследования, все, что вам потребуется, это переобъявление методов, специфических для этого класса. Все остальное будет наследовано.

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

Беглый взгляд на реализацию

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

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

cab_at_corner.load (...)

должна применяться версия метода load класса TAXI, что выводимо из типа, заданного при объявлении цели cab_at_corner. Для описания генерируемого кода позвольте использовать язык С. Он является языком достаточно низкого уровня и может служить представителем ассемблерных языков, но все же он достаточно высокого уровня, чтобы оставаться понимаемым и не зависимым от конкретной платформы (помимо всего, компилятор EiffelStudio в качестве одного из своих возможных выходов генерирует код на языке С, так что рассматриваемая ситуация реалистична).

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

C_TAXI_load (C_cab..,.);

Листинг 2.1. (html, txt)



Здесь C_TAXI_load является результатом трансляции вызова метода load для версии класса TAXI. Так как С не является ОО-языком и не имеет понятия квалифицированного вызова x./(...), функции в языке С имеют, по крайней мере, один аргумент, соответствующий цели, -- здесь С_ cab представляет исходный cab_at_corner в Eiffel.

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

При динамическом связывании такая ситуация более не происходит. На этапе компиляции доступны различные версии load, и только на этапе выполнения становится ясным, какая из этих версий должна выполняться в текущей точке вызова. Генерируемый код v.load (. ) должен основываться на некоторой подходящей структуре данных, подобной той, что показанo на рисунке.

Рис. 2.4. Разрешение динамически связываемого вызова

Ключевой структурой является таблица методов¹⁾(называемая также таблицей переходов). Входами в этой таблице являются ссылки. В отличие от обычных ссылок они указывают не на данные, а на код -- в данном примере на соответствующую версию метода load.

Такие ссылки (или "указатели") на код не есть нечто такое, что можно непосредственно получить в Eiffel или в большинстве ОО-языков высокого уровня, но на машинном уровне они являются прямым результатом концепции "программы, хранимой в памяти". Так как код, подобно данным, хранится в памяти, то вход в таблице может содержать адрес начала блока кода. В дополнение к этому, множество команд компьютера включает команду в форме: "выполнить код, начинающийся с адреса addr ".

Языкам высокого уровня нет необходимости в таком свойстве, поскольку оно чревато ошибками: что, если по адресу addr хранится не код, а данные, или, еще хуже, код, размещенный зловредным хакером? Для ОО-языков динамическое связывание является безопасной заменой. В Eiffel имеется еще один подобный механизм - агенты. Агент можно рассматривать как некоторую обертку метода, и он может быть передан различным частям ПО, позволяя им вызывать метод. В некоторых не ОО-языках предоставляется возможность передавать метод в качестве фактического аргумента другим методам. В лекции, посвященной агентам, обсуждаются эти механизмы, позволяющие отложить решение по выбору метода до момента его исполнения.

При динамическом связывании выбор метода зависит от типа целевого объекта. На последнем рисунке этот объект, показанный слева, является экземпляром TAXI. Мы не можем вывести это, анализируя текст программы, где известно только, что переменная v относится к более общему типу VEHICLE; но если v полиморфна, то соответствующая ссылка может быть в некотором сеансе выполнения присоединена к экземпляру TAXI. Вся идея динамического связывания и состоит в том, что объявление типа v означает лишь, что при сохранении общности допускаются разные типы в разных сеансах выполнения.

Если рассматривать эти свойства с позиций разработчика компилятора, то приходим к важному заключению -- каждый объект должен содержать идентификацию своего собственного типа. В противном случае не было бы возможности добиться динамического связывания, так как именно тип определяет, какой вариант метода следует выбрать из множества возможных. Реализации ОО-языков действительно включают в представление любого объекта в дополнение к его полям, задающим атрибуты, поле, задающее тип (на рисунке оно помечено как "Тип"). Обычно тип задается целым числом и для него отводится одно слово памяти (4 или 8 байтов), этого достаточно в современных прикладных системах для задания любого возможного типа. Реализация EiffelStu dio добавляет все же еще одно слово к каждому объекту для контроля информации, необходимой, в частности, сборщику мусора. Таковы издержки ОО-механизмов в этой реализации -- два дополнительных слова на каждый объект. В целом это приемлемая плата, но могут возникать проблемы, если создается очень много небольших объектов.

Можно пройти по пути, показанному на рисунке, начав с объекта v слева вверху, следуя стрелкам. Если значение v не равно void, то ссылка приведет нас к объекту. Поле "Тип" этого объекта даст нам соответствующее целое, представляющее тип объекта (здесь TAXI). Мы используем это целое для индексации входа в таблицу методов, построенную для load ; соответствующий вход даст адрес программного кода соответствующего варианта метода.

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

(routine_table[(_v).type]) (v,...);

Листинг 2.2. (html, txt)

Пояснение: символ * означает операцию разыменования, так что * v -- это объект, заданный ссылкой v, тогда (*v).type (что может быть также записано как v-> type ) является соответствующим полем объекта и его значение используется как индекс в массиве routine_table. Так мы получаем адрес нужной C-программы, которой и передаются необходимые ей аргументы. Как и ранее, список аргументов включает помимо исходных аргументов и аргумент, задающий целевой объект, известный здесь как v, играющий роль объекта C_cab.

Из этой базисной схемы можно вывести много различных вариантов реализации, применяя различные оптимизации. Прежде чем понять всю проблему в целом, заметим, что, поскольку мы имеем дело не только с одним методом load, коллекция всех таблиц разных методов представляет двумерную структуру с T строчками и R столбцами, T -- задает типы, а R -- программы методов, как показано на следующем рисунке:

Рис. 2.5. Общая схема реализации динамического связывания

Хорошая реализация динамического связывания должна обеспечивать время поиска нужного варианта за время О(1).

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

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

Следует учитывать и другую сторону эффективности программы -- стоимость требуемой памяти. Во всех трех вариантах потребуются структуры, имеющие в общей сложности T * R входов. Этому требованию иногда трудно удовлетворить. Например, EiffelStudio использует примерно 6000 типов и 50000 методов. Но таблица, показанная выше, избыточна, поскольку практически большинство входов будут пусты, -- каждый метод имеет смысл только для нескольких типов, например, метод load применим только для VEHICLE и его потомков.

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

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

программирование паттерн полиморфизм наследование

Рис. 2.6. Общая схема реализации динамического связывания

Вышеприведенный код все еще будет работать при условии, что вход в таблицу routine_table[i] индексируется по отношению к эффективному началу, а не относительно физической точки начала столбца. Достичь этого нетрудно.

Такая оптимизация не представляет особого интереса, если непустые входы распределены по всему столбцу, задающему таблицу методов. Предположим, что при наличии 600 типов номер 1 отведен типу VEHICLE, 3000 для TRAM и 6000 для TAXI. Даже если load существует только для этих трех типов, нам все же придется иметь столбец с 600 входами, хотя все из них кроме трех будут пустыми. Для улучшения ситуации заметим, что у нас есть свобода для выбора номеров, присваиваемых типам, так что можно воспользоваться преимуществами следующего свойства.

Теорема о соседстве методов

Классы, обладающие методом М, являются потомками класса, где метод М впервые появился.

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

Выполнение топологической сортировки существенно уменьшает размер таблиц методов -- в EiffelStudio примерно на 85%. Эта техника носит принципиальный характер, поскольку без нее издержки памяти были бы критичными.

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

· некоторая программа имеет только одну версию;

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

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

По этой причине в ряде языков (С++, Java, C# и других) статическое связывание предполагается по умолчанию, а динамическое -- резервируется только для виртуальных методов. Такая политика приводит к появлению проблем, поскольку программисту легко ошибиться, предположив, что вызов является статическим, в то время как он полиморфен. Возможно, что когда-то принятоерешение было корректным, но в ходе эволюции добавился новый класс-потомок с новой версией метода, а изменение объявления метода как виртуального так и не было сделано.

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

В EiffelStudio компилятор действительно занимается подобной оптимизацией.

Эти наблюдения дополняют наш краткий экскурс в технику реализации. Надеюсь, это дало лучшее понимание значимости наследования и связанных с ним приемов для выполнения ОО-программ. Конечно, на практике приходится учитывать много деталей. Если вы хотите дойти "до сути вещей", то стоит перейти к анализу кода на языке С, генерируемого компилятором EiffelStudio в "классическом" варианте. На следующем шаге следует изучить сам Eiffel-код.

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

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

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



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

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

Такси и транспортные средства

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

Наследуемые компоненты

Класс TAXI из TRAFFIC обеспечивает -- вы можете это проверить -- такой компонент, как

take (from_location,to_location: LOCATION)

-- Доставить пассажира из from_location в to_location

Другим компонентом класса является office, представляющий диспетчерский офис службы такси.

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

· такси имеет пассажиров (в противном случае комментарий для компонента take не имел бы смысла: кого следует доставить из одной точки в другую?). Класс должен иметь команду для посадки пассажиров и запрос, позволяющий выяснить текущее число пассажиров;

· в любой момент такси имеет текущую позицию.

Где же находятся соответствующие свойства? Ответ можно найти, взглянув в начало объявления класса:

note

…

class

TAXI

inherit

VEHICLE

feature

... Оставшаяся часть класса...

Класс TAXI наследует от VEHICLE ; и в самом деле, если посмотреть на класс VEHICLE, то можно найти команды load, для посадки пассажиров в транспортное средство, так же как и unload -- для высадки, и запрос count, дающий текущее число пассажиров. Теперь, обратившись к началу объявления класса VEHICLE, вы увидите:

note

...

deferred class

VEHICLE

inherit

MOVING

feature

…Оставшаяся часть класса...

Класс VEHICLE наследует от класса MOVING, который описывает движущиеся объекты и имеет запрос position.

Классы VEHICLE и MOVING объявляются не просто как class, а как deferred class. Мы вскоре познакомимся детально с концепцией отложенного класса, указывающего на то, что не все его компоненты полностью заданы; реализация некоторых из них оставлена его потомкам -- классам, наследующим от него.

Глядя, как эти три класса описывают типы объектов периода выполнения -- такси, транспортные средства, движущиеся объекты, -- мы понимаем, о чем говорит нам наследование. Оно устанавливает, что в системе Traffic любое такси может рассматриваться как транспортное средство, которое, в свою очередь, является движущимся объектом. В частности, все свойства класса MOVING применимы к целям типа VEHICLE и TAXI, и все свойства класса VEHICLE применимы к целям типа TAXI.

Термины наследования

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

Определения: наследник, родитель, (правильный) потомок и предок

Если B наследует от A ( В Eiffel A перечислено в предложении inherit класса B), то B наследник A, а A - родитель B. Потомками класса является сам класс и (рекурсивно) потомки его наследников. Сам класс не включается в число правильных потомков. Предок и правильный предок являются обращенными понятиями по отношению к потомкам.

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

В литературе иногда встречается термин "подкласс", означающий иногда наследника, иногда правильного потомка. Аналогично встречается и термин "суперкласс".

На рисунке ниже, иллюстрирующем наш пример, все классы являются потомками класса MOVING. Все классы -- его правильные потомки, за исключением самого класса. Правильными предками класса TAXI являются классы VEHICLE и MOVING.

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

Рис. 1.1. Иерархия наследования

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

От вас не требуется вручную рисовать диаграмму, отображающую отношения между классами. Если классы скомпилированы, то инструментарий Diagram Tool EiffelStudio создаст диаграмму. Достаточно просто щелкнуть вкладку Diagram, и появится требуемая диаграмма:



Рис. 1.2.

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

Компоненты, приходящие от высших авторитетов

Мы можем теперь оценить новинку, вводимую наследованием. Понятие "компоненты класса" больше не означает только компоненты, заданные в классе, но и компоненты, наследуемые от родителя. Так, объявив объекты m: MOVING, v: VEHICLE, t: TAXI, мы можем помимо прочего писать:

v.load (...)

t.take (...)

v.count -- Выражение



Возможны и другие вызовы, такие как:

t.count

t.load

t.position

v.position

Здесь используются компоненты, наследуемые от родителя или, более точно, от правильных предков. Полезно различать "наследуемые" и "непосредственные" компоненты. Определения: компоненты класса, непосредственные, наследуемые, вводимые

Компонент класса - это одно из двух:

· наследуемый компонент, если это компонент одного из родителей класса;

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

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

Отныне следует понимать, что класс А больше, чем то, что видимо в тексте класса. Компоненты класса означают не только компоненты, объявленные в тексте класса, но и те, что приходят от родителей, если таковые существуют.

Плоский облик

Как тогда получить полную картину? Плоским обликом класса называется искусственно сконструированная версия, которая включает все компоненты, непосредственные и наследуемые. Это не то, что вы пишете, создавая класс, но лишь облик, подобный контрактному облику, который, как мы видели, дает нам свободную от реализации версию класса. EiffelStudio создает этот взгляд на класс, этот облик, для чего достаточно выбрать класс и щелкнуть по кнопке "Flat view":



Рис. 1.3.

Результат похож на обычный текст класса (с некоторой новой нотацией, которая позже прояснится). Отметьте появление нового вида комментариев, здесь для компонента LINKED_LIST:

Рис. 1.4. Плоский облик

Выделенных комментариев нет в исходном тексте, но они добавлены EiffelStudio, когда он создает плоский облик. Они указывают, что компонент наследуется, приходя от правильного предка CHAIN, и что его предусловие было определено в другом предке -- LINEAR. Мы вскоре увидим, как контракты преобразуются в связи с наследованием.

Контрактный облик класса выводится (как объяснялось ранее, удаляется закрытая информация) не из исходного текста класса, а из его плоского облика. Для клиента класса обычно все равно, наследованы ли экспортируемые классом компоненты или введены самим классом. Интерфейсный облик класса позволяет ограничиться только непосредственными компонентами.

Полиморфизм

Аккумулирование компонентов не является единственной целью наследования. Мы уже демонстрировали эту возможность, когда писали класс PREVIEW как наследника класса TOURISM. Мы хотим получить преимущества от наследования не просто за счет модульности, а за счет того, что оно задает отношения между типами, -- дельфины являются млекопитающими, кольца являются группами.

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

my_vehicle: VEHICLE

cab_at_corner: TAXI

Структура наследования, рассмотренная выше, делает допустимым присваивание:

my_vehicle := cab_at_corner

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

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



Рис. 1.5. Полиморфное присваивание

Это обычное ссылочное присваивание. Сами объекты -- здесь объекты типов TAXI и VEHICLE -- не меняются. Новинка в том, что после присваивания переменная типа VEHICLE теперь может быть присоединена к объекту типа TAXI -- к объекту одного из своих потомков.

Определения

Нам нужна подходящая для этой ситуации терминология.

Определения: полиморфизм

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

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

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

Напоминаю, что "сущности" включают переменные (атрибуты, локальные переменные), а также формальные аргументы методов и Result.

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

Как отмечалось в определении, полиморфизм существует не только при присваивании, но и при передаче аргумента в момент вызова метода. Пусть некоторый произвольный класс, например,DAILYSCHEDULE, имеет метод:

register_trip (v: VEHICLE)

Тогда вызов этого метода является вполне корректным:

register_trip (cab_at_corner)

Здесь тип фактического аргумента является потомком типа формального аргумента. Наиболее интересно здесь то, что, когда пишется метод, такой как register_trip, то используется не полное, а частичное знание. Автор знает, что во время выполнения значение аргумента будет присоединено к объекту, представляющему некоторый вид транспортного средства -- VEHICLE, но этот объект может быть TAXI, или TRAM, или любым другим транспортным средством, и автор метода не знает, каким именно, и ответ может изменяться от одного выполнения к другому.

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

Полиморфизм - это не трансформация

Несмотря на свое имя -- от греческого словосочетания "множественность форм" -- полиморфизм не является причиной изменения во время выполнения объектом своей "формы" (изменением типа). Полиморфное присоединение применимо только к ссылочным типам с эффектом, показанным на последнем рисунке, -- изменяются ссылки, но сами объекты не меняют тип.

Иногда возникает необходимость трансформации объекта, но это никак не связано с полиморфизмом. Простейшим примером такой ситуации является присваивание целого целевой переменной типа REAL, чье внутреннее представление отличается от представления источника. Подходящим механизмом в таком случае является трансформация, но не полиморфное присоединение. Общий механизм трансформации, применимый как к ссылочным, так и к развернутым типам, механизм, который стоит за возможностью присваивания целых вещественным переменным, поддерживается в Eiffel. Язык позволяет также определять собственную трансформацию между создаваемыми типами данных. Если проектируется класс DATE с атрибутами day, month, year, то в класс можно включить метод, осуществляющий преобразование из DATE в STRING, что позволит преобразовать дату и представить ее в виде строки текста (например, в виде "13.06.2010" или в любом другом формате, выбранном в методе преобразования). Мы не будем более останавливаться на механизмах преобразования. Если необходимо его использовать, то можно проанализировать для начала класс REAL32 в EiffelBase (смотри предложение convert), этого будет достаточно для понимания основных идей трансформации. Что же касается нашего обсуждения, то следует понимать, что трансформация и полиморфизм являются взаимоисключающими механизмами: если применяется один из них, то второй не применяется. Так что, когда вы видите присваивание a:=b или когда речь идет о передаче аргумента при вызове метода, то никогда не возникает неопределенность, из контекста всегда ясно, с каким случаем мы имеем дело.