Глава     21

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

Разделы

Содержание

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

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

Разделы

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

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

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

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

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

Разделы

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

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

x:= d.y

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

move AR+36, AR+20

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

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

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

21.2.1. Проблема ╚срезки╩

Компиляторы

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

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

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

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

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

Компиляторы

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

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

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

Компиляторы

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

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


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


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

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

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


Рис.═21.4. Таблицы виртуальных методов для классов Wall и Ball

Раз уж компилятор знает, где найти указатель на метод, то метод может быть вызван как стандартная процедура. Получатель рассматривается как если бы он был первым параметром в списке аргументов, и тем самым он доступен как значение переменной self (this в C++). Предположим, к примеру, что vtab═≈ это внутреннее имя поля, представляющее указатель на таблицу виртуальных методов в объекте x, и что смещение для метода hitBy в таблице═равно═12. Тогда вызов метода 

x.hitBy(y)
будет преобразован в следующее внутреннее представление:
(*(*(x.vtab))[12]) (x,y)

Заметьте, что имя метода не появляется в выходном коде, и надлежащий метод будет выбираться независимо от того, является ли x объектом класса Ball, или класса Wall, или каким-либо другим графическим объектом GraphicalObject. В═терминах выполнения программы заголовок посылаемого сообщения требует две операции с указателями и одну операцию нахождения элемента в массиве.

21.2.4. Кодирование имен

Компиляторы

Поскольку все методы известны во время компиляции и не могут быть изменены во время выполнения, то таблицы виртуальных методов═≈ это просто статические области данных, устанавливаемые компилятором. Они состоят из указателей на соответствующие методы. Поскольку редакторы связей (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).

Как и в системе с таблицами виртуальных методов, при использовании таблиц диспетчеризации каждый объект содержит внутри себя неявный (то есть необъявленный) указатель на таблицу диспетчеризации, связанную с его классом. Этот неявный указатель называется указателем связи 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, а метод так и не найден, выдается сообщение об ошибке этапа выполнения.

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

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

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

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

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

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


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

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

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

Разделы

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

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


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

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

while (timeslice-- >═0)
{
  high = nextByte();    // считать следующий байт-код
  low = high &═0x0F;    // выделить младшие═4 бита
  high >>=═4;     // сдвинуть старшие четыре бита

  if (high ==═0)        // это расширенная форма?
   {                 	// если так,
    high = low;      	// код операции находится в low
	low = nextByte(); 	// присвоить настоящий операнд
   }

  switch (high)
   {
    case PushInstance: ...
      ...
    case PushArgument: ...
      ...
   }
}

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


Рис.═21.8. Внутренняя структура класса

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

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

Литература для дальнейшего чтения

Разделы

Для читателя, заинтересованного в получении дополнительной информации по реализации объектно-ориентированных языков, можно порекомендовать работу Кокса [Cox═1986], содержащую детальный анализ затрат времени/памяти для различных схем реализации. Реализация множественного наследования в C++ вкратце описана в работе [Ellis═1990], которая основывается на более раннем алгоритме языка Simula [Krogdahl═1985]. Детальное описание реализаций языка C++ приводится Липманом [Lippman═1996].

Интерпретатор языка Smalltalk-80 описан в работе [Goldberg═1983]. Сборник [Krasner 1983] содержит несколько статей, которые описывают методы улучшения эффективности системы Smalltalk-80. Упрощенный интерпретатор языка Smalltalk детально представлен в работе [Budd═1987]. Камин [Kamin═1990] приводит хороший общий обзор приемов реализации нетрадиционных языков программирования.

Упражнения

Разделы

  1. Как следует видоизменить метод таблиц диспетчеризации чтобы разрешить множественное наследование?
  2. Компилятор языка Objective-C допускает необязательные описания переменных объекта. Объясните, как компилятор может использовать подобные описания для ускорения обработки сообщений, включающих такие значения. Рассмотрите, что происходит при операции присваивания и как пересылка сообщений может быть сделана более эффективной.
  3. Объясните, почему методы, которые в языке C++ не описаны как виртуальные, могут вызываться более эффективно, чем виртуальные методы. Как бы вы произвели замеры времени, чтобы определить, является ли разница существенной?
  4. Исследуйте технику кэширования, описанную в разделе═21.2. Объясните, почему класс, запоминаемый в кэш-таблице,═≈ это класс, с которого начинается поиск, а не тот класс, внутри которого найден метод. Объясните, как бы изменился алгоритм просмотра кэш-таблицы, если бы использовалось второе значение. Как вы думаете, новый алгоритм будет работать быстрее или медленнее? Обоснуйте свой ответ.
  5. Опишите вкратце структуру интерпретатора языка Smalltalk, основанного на байт-кодах, представленных в тексте.

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