converted to PDF by BoJIoc

Интересным свойством систем, основанных на принципе делегирования, является их способность динамически изменять делегатов. После того как было сконструировано устройство «черепашка», а затем пользователь перенес делегирование с обычного пера на перо dasedPen, «черепашка» внезапно развивает в себе способность рисовать не только сплошные, но и пунктирные линии. (Естественно, делегирование к объекту, который не понимает всех требуемых сообщений, может привести к краху программы.)

В определенном смысле отношения объект/делегат подобны отношениям экземпляр/класс, за исключением того, что в первом случае нет двух сущностей — делегат просто является другим объектом. Тем не менее существует распространенная практика создания классо-подобных объектов-фабрик, которые не делают ничего, кроме дублирования существующего объекта. Например, удается произвести «фабрику черепашек», которая по запросу выпускает новую «черепашку», независимую от всех других «черепашек».

Основной литературой по делегированию является работа [Lieberman 1986]. Его статья показывает, как с помощью делегирования мы можем смоделировать механизм наследования. Обратное утверждение «с помощью наследования удается смоделировать делегирование» также было продемонстрировано [Stein 1987]. Язык программирования Self, основанный на делегировании, был описан Унгаром [Ungar 1987]. Томлинсон [Tomlinson 1990] приводит интересный анализ затрат времени и памяти при делегировании и при наследовании, приходя к заключению, что наследование в общем случае является более быстрым и, как ни удивительно, требует меньше памяти.

Упражнения

1.Какие аспекты понятия тип данных не описываются категориями Вегнера [Wegner 1986]? Определите новые точки зрения, чтобы отразить эти аспекты.

2.Изучите технические приемы верификации в стандартных языках программирования (хорошее объяснение их приводится в работах [Gries 1981, Dijkstra 1976]). С какими проблемами вы сталкиваетесь, когда пытаетесь

применить эти подходы к

Глава 21

Реализация объектно-ориентированных языков

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

21.1. Компиляторы и интерпретаторы

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

converted to PDF by BoJIoc

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

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

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

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

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

Хотя одни языки обычно компилируются, а другие, как правило, интерпретируются, в собственно языке программирования нет внутренних причин, которые вынуждают программиста, реализующего язык, выбирать один путь, а не другой. C++ обычно компилируется, но имеются и интерпретаторы C++. С другой стороны, язык Smalltalk почти всегда интерпретируется, однако созданы и экспериментальные Smalltalk- компиляторы.

21.2. Компиляторы

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

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

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

x:= d.y

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

move AR+36, AR+20

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

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

converted to PDF by BoJIoc

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

данных для подклассов должны соответствовать расположению аналогичных полей в надклассах (рис. 21.1).

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

Рассмотрим классы GraphicalObject и Ball для модели бильярда, описанной в главе 6. Класс GraphicalObject содержит поля link и region, а класс Ball добавляет к ним поля direction и energy, одновременно сохраняя для полей класса-предшественника в точности те же смещения. То, что смещения полей для родительского класса сохраняются в дочернем, очень важно: это позволяет методам, определенным для родительского класса, обрабатывать данные экземпляра с использованием постоянных смещений, так что эти функции будут работать правильно независимо от того, к какому классу (родителю или потомку) относится аргумент. Например, метод moveTo класса GraphicalObject будет вести себя как полагается независимо от класса объекта-получателя, поскольку этот метод пользуется только областью region объекта.

21.2.1. Проблема «срезки»

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

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

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

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

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

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

converted to PDF by BoJIoc

21.2.2. Соответствие между методами и сообщениями

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

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

21.2.3. Таблицы виртуальных методов

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

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

Рис. 21.2. Методы, реализованные как поля

converted to PDF by BoJIoc

Рис. 21.3. Два бильярдных шара с общей таблицей виртуальных методов

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

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

рис. 21.4 показана таблица виртуальных методов для классов Wall и Ball, каждый из которых является потомком класса GraphicalObject. Заметьте, что у них общие указатели на методы, унаследованные от родительского класса, и что порядок методов совпадает с тем, который задан в родительском классе.

converted to PDF by BoJIoc

Поскольку редакторы связей (linkers) и загрузчики (loaders) превращают ссылки в смещения (разрешают ссылки), исходя из символических имен, необходимо обеспечить некоторый механизм, который позволил бы избежать противоречия в ситуации, когда два метода имеют одно и то же имя. Типичная схема комбинирует имя класса и имя метода. Так, метод draw из класса Ball превращается, например, в Ball::draw при внутреннем представлении. Обычно пользователю никогда не требуется знать это имя, если только нет необходимости анализировать ассемблерный код, созданный компилятором.

В языках программирования, подобных C++, позволяющих еще более перегружать методы за счет снятия неоднозначности путем анализа типов аргументов, требуется более сложное кодирование в стиле Гёделя1 с использованием имени класса, имени метода и типов аргументов. Например, три конструктора класса Complex, описанные в предыдущих главах, получат соответственно внутренние имена Complex::Complex, Complex::Complex_float и Complex::Complex_float_float. Такие внутренние имена называются кусочно-составными (mangled). Они бывают очень длинными. Как мы видели, внутреннее имя не используется для пересылки сообщения; оно применяется только при

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

Множественное наследование несколько усложняет использование таблиц виртуальных методов. Детали, однако, выходят за рамки данной книги. Заинтересовавшиеся читатели могут найти более полное описание в [Ellis 1990].

21.2.5. Таблицы диспетчеризации

Поскольку языки программирования, подобные C++ и Object Pascal, являются языками со статическими типами данных, они могут определить на этапе компиляции по крайней мере тип родительского класса любого «объектного» выражения. Тем самым таблица виртуальных методов должна быть ровно такой, чтобы вместить методы, реализованные для класса. Для языков программирования с динамическими типами данных (вроде Objective-C) таблица виртуальных методов обязана включать все сообщения, понимаемые всеми классами, и она повторяется для каждого класса. К примеру, если приложение содержит 20 классов и в среднем каждый класс использует 10 методов, то нам требуется 20 таблиц, каждая из которых состоит из 200 записей. Требования к размеру таблиц быстро становятся чрезмерными, и тогда возникает потребность в более удачном подходе.

Рис. 21.5. Объект и его таблица диспетчеризации

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

converted to PDF by BoJIoc

Как и в системе с таблицами виртуальных методов, при использовании таблиц диспетчеризации каждый объект содержит внутри себя неявный (то есть необъявленный) указатель на таблицу диспетчеризации, связанную с его классом. Этот неявный указатель называется указателем связи isa (isa link) (не смешивать с условием «быть экземпляром» (is-a relation) для классов). Пересылка сообщения в языке Objective-C вроде следующего

выражения из задачи о восьми ферзях

[neighbor checkrow: row column: column]

преобразуется компилятором языка Objective-C1 в код objc_msgSend(neighbor, "checkrow:column:", row, column)

Функция objc_msgSend, называемая функцией пересылки сообщений, следует по указателю связи isa для первого аргумента с тем, чтобы найти соответствующую таблицу диспетчеризации. Затем функция пересылки сообщений просматривает таблицу диспетчеризации в поисках записи, соответствующей селектору. Если такая запись найдена, вызывается нужный метод. Если подобного метода не обнаружено, поиск продолжается в таблице диспетчеризации надкласса. Если в конце концов достигнут корневой класс Object, а метод так и не найден, выдается сообщение об ошибке этапа выполнения.

Кэширование методов

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

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

2 Хэширование (hashing) — метод приближенного индексирования для сокращения поиска нужных данных. При хэшировании каждому данному ставится в соответствие хэш-код (hash-code), который используется для упорядочивания данных в хэш-таблице и служит селектором при их поиске. Характерная черта хэш-кода состоит в том, что он, вообще говоря, не является уникальным (то есть различные данные могут порождать при вычислениях одинаковый хэш-код). Однако он быстро вычисляется и позволяет значительно сократить область поиска данных. Примером хэширования служит словарь с закладками по месту смены первой буквы слов. Здесь первая буква слова выступает в качестве его хэш-кода. — Примеч. перев.

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

Когда функцию пересылки сообщений просят найти метод, который соответствует паре «класс–селектор», она прежде всего осуществляет поиск в кэш-таблице (рис. 21.6). Если запись в кэше по месту расположения хэш-кода соответствует требуемым селектору и классу, то соответствующий метод может быть выполнен немедленно. Если нет — проводится процесс поиска, описанный выше. В результате поиска непосредственно перед выполнением найденного метода происходит обновление кэш-таблицы. При этом запись, содержавшаяся по месту соответствующего хэш-кода (рассчитываемому по селектору сообщения), перезаписывается новыми данными. Обратите внимание, что

converted to PDF by BoJIoc

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

Рис. 21.6. Функция пересылки сообщения, проверяющая кэш таблицу

При надлежащем выборе функций вычисления хэш-кода и размера кэша можно достичь частоты попадания в кэш около 90–95 процентов, что уменьшает накладные затраты на передачу сообщения до уровня, лишь примерно в два раза большего, чем расходы на стандартный вызов процедуры [Cox 1986]. Этот показатель вполне благоприятно сравнивается с затратами при использовании таблиц виртуальных методов.

21.3. Интерпретаторы

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

Подход, обычно используемый для интерпретаторов, — преобразовывать исходную программу в «ассемблерный язык» высокого уровня, часто называемый байт-кодом, поскольку обычно каждая инструкция закодирована в одном байте. На рис. 21.7 показан байт-код системы Little Smalltalk. Старшие четыре бита используются для кодирования операции, а младшие используются для указания номера операнда. Если требуются номера операндов большие шестнадцати, применяется расширенная форма инструкции, и последующий байт целиком содержит значение операнда. Немногие инструкции (типа «послать сообщение» и некоторые специальные) требуют дополнительных байтов.

converted to PDF by BoJIoc

Рис. 21.7. Байт-код в системе Little Smalltalk

Сердцем интерпретатора является цикл, который охватывает огромный оператор переключения switch (case, select и т. д.). Цикл считывает последовательные байт-коды, а оператор выбора передает управление той цепочке кода, которая выполняет требуемое действие. Мы не будем вдаваться в дискуссии о внутреннем представлении программы (заинтересованные читатели могут обратиться к работе [Budd 1987]) и сконцентрируемся исключительно на обработке передачи сообщений.

case PushInstance: ...

...

case PushArgument: ...

...

}

}

Подобно тому как все объекты в рассмотренных ранее компилируемых системах содержали указатель на таблицу виртуальных методов, все объекты в системе Smalltalk поддерживают указатель на свой класс. Разница состоит в том, что, как мы видели в главе 20, класс сам по себе является объектом. Среди полей, содержащихся в объекте- классе, есть набор всех методов, которые соответствуют сообщениям, распознаваемым экземплярами класса (рис. 21.8). Другое поле указывает на надкласс этого класса.