Объектно-ориентированное программирование. Объектно-ориентированное программирование в действии. Объектноориентированное программирование
 Скачать 5.29 Mb.
|
|
Глава 21: Реализация объектно-ориентированных языков Целью данной книги не является снабдить читателя подробными инструкциями по реализации языков программирования. Тем не менее общее понимание проблем, возникающих при воплощении объектно-ориентированных языков, а также различные способы борьбы с ними во многих случаях помогут читателю лучше понять объектно- ориентированные технологии. В частности, станет понятно, в чем именно объектно- ориентированные системы отличаются от более традиционных средств. В этой главе содержится обзор некоторых наиболее важных техник реализации, а также ссылки на необходимую литературу для читателей, которые захотят продвинуться дальше. PDF created with pdfFactory Pro trial version www.pdffactory.com 21.1. Компиляторы и интерпретаторы В широком смысле имеются два основных подхода к воплощению языков программирования: компиляторы и интерпретаторы. Компилятор переводит программу пользователя в машинный код компьютера, на котором будет выполняться программа. Вызов компилятора осуществляется как процесс, не зависящий от выполнения программы. Интерпретатор же обязательно присутствует во время исполнения программы и является собственно той системой, которая выполняет программу 1 В общем случае программа, оттранслированная компилятором, будет выполняться быстрее, чем программа, выполняемая под управлением интерпретатора. Но полное время, затраченное на проектирование, ввод текста и запуск на выполнение для компилирующей системы может быть больше, чем для интерпретатора. Более того, когда во время выполнения программы возникает ошибка, компилятор практически всегда может предложить для локализации места вероятной ошибки всего лишь сгенерированный ассемблерный текст. Интерпретатор же обычно покажет ошибку в исходном тексте программы, введенном пользователем. Тем самым имеются достоинства и недостатки у обоих подходов. Хотя одни языки обычно компилируются, а другие, как правило, интерпретируются, в собственно языке программирования нет внутренних причин, которые вынуждают программиста, реализующего язык, выбирать один путь, а не другой. C++ обычно компилируется, но имеются и интерпретаторы C++. С другой стороны, язык Smalltalk почти всегда интерпретируется, однако созданы и экспериментальные Smalltalk- компиляторы. 21.2. Компиляторы Типичной отличительной чертой компиляторов является то, что некоторая информация теряется при переводе исходного текста программы в машинный код. Это наиболее заметно при преобразовании символических имен в адреса ячеек памяти. Так, к локальным переменным внутри процедуры скомпилированный код адресуется не по их именам, а через фиксированный сдвиг относительно начала блока памяти, создаваемого при входе в процедуру1. Аналогично поля данных в записи описываются путем указания их сдвига относительно начала блока, а не через имена. Предположим, что процедура содержит переменную x и запись d, которая в свою очередь имеет поле данных y. Допустим, что x запоминается в ячейке локального блока выделенной памяти с индексом 20, а d начинается с ячейки 28. Пусть поле данных y начинается с восьмого байта записи d. При этих предположениях оператор присваивания x:= d.y может быть оттранслирован в одну ассемблерную команду, которая перемещает содержимое слова, расположенного в тридцать шестом байте от начала блока, в двадцатую ячейку от начала блока: 1 Как и в случае большинства классифицирующих разбиений, между чистыми конечными точками посередине имеется большая серая область. Существуют компиляторы, которые компилируют в интерактивном режиме, иногда даже во время выполнения программы (и по крайней мере на стадии пошаговой отладки). Такие компиляторы обладают некоторыми достоинствами интерпретаторов, в то же время обеспечивая во время выполнения программы преимущества, свойственные компилирующим технологиям. Аналогично некоторые интерпретаторы могут переводить программу в промежуточное представление или псевдокод. PDF created with pdfFactory Pro trial version www.pdffactory.com move AR+36, AR+20 Обратите внимание: операторы ассемблера используют не символические имена переменных, а только их смещения относительно начала блока. Как мы заметили в предыдущих главах, объект напоминает запись или структуру в традиционных языках программирования. Подобно записям, полям данных (переменным экземпляра) приписываются фиксированные смещения относительно начала объекта. Подклассы могут только расширять эту область памяти, но не сокращать ее, так что объем памяти, выделенной для класса-потомка, строго больше, чем у класса-предка. Смещения данных для подклассов должны соответствовать расположению аналогичных полей в надклассах (рис. 21.1). Рис. 21.1. Соответствие между полями данных в родительском и дочернем классах Рассмотрим классы GraphicalObject и Ball для модели бильярда, описанной в главе 6. Класс GraphicalObject содержит поля link и region, а класс Ball добавляет к ним поля direction и energy, одновременно сохраняя для полей класса-предшественника в точности те же смещения. То, что смещения полей для родительского класса сохраняются в дочернем, очень важно: это позволяет методам, определенным для родительского класса, обрабатывать данные экземпляра с использованием постоянных смещений, так что эти функции будут работать правильно независимо от того, к какому классу (родителю или потомку) относится аргумент. Например, метод moveTo класса GraphicalObject будет вести себя как полагается независимо от класса объекта-получателя, поскольку этот метод пользуется только областью region объекта. 21.2.1. Проблема «срезки» То обстоятельство, что дочерний класс может только расширять область данных, определенную родительским классом, решает проблему, описанную в предыдущем разделе. Это позволяет компилятору так генерировать код для процедуры родительского класса, что она будет работать и для объектов, принадлежащих к дочернему классу. Но это же свойство создает другую проблему. Как мы видели в предыдущих главах, полиморфная переменная — это переменная, которая объявлена как принадлежащая к одному типу данных, тогда как на самом деле она содержит значение, относящееся к другому типу. В объектно-ориентированных языках переменная типа родительского класса, как правило, может содержать значения типа потомков. Когда компилятор устанавливает размер локального блока выделяемой памяти, он, вообще говоря, знает только декларированный тип переменной, а не тип, который она будет иметь во время исполнения программы. Таким образом, возникает вопрос: сколько PDF created with pdfFactory Pro trial version www.pdffactory.com памяти должно быть выделено под локальный блок? Как мы выяснили в главе 12, большинство языков программирования выбирают одно из двух решений этой проблемы: • блок выделяемой памяти содержит указатели, а не сами значения; • блок выделяемой памяти содержит только поля данных родительского класса. При операции присваивания те поля данных потомка, которые выходят за пределы родительского класса, отбрасываются (срезаются). У каждой из двух альтернатив имеются свои преимущества, так что мы не будем комментировать, какая из них лучше. Однако для вас как для программиста важно понимать, какая именно техника используется в системе, в которой вы работаете. 21.2.2. Соответствие между методами и сообщениями Наиболее новаторское свойство объектно-ориентированного программирования с точки зрения реализации состоит в том, что интерпретация сообщения может зависеть от типа (класса) получателя. То есть различные классы объектов могут выполнять различные процедуры в качестве реакции на одно и то же сообщение. Для нашей графической модели класс Wall реагирует на сообщение draw иным образом, чем класс Ball. По этой причине каждый объект обязан содержать какой-то способ определения, какая процедура должна вызываться для сообщения, воспринимаемого объектом. Более того, мы хотим, чтобы механизм, который используется для связывания метода и процедуры, работал как можно быстрее. Для компилирующих языков программирования техника, наиболее часто используемая с целью обеспечить скорость, называется таблица виртуальных методов. 21.2.3. Таблицы виртуальных методов Одно из возможных решений проблемы соответствия между методами и сообщениями состоит в том, чтобы разместить поля для методов в точности тем же способом, как выделяется память для полей данных. Значениями полей методов являются указатели на соответствующие функции, как это показано на рис. 21.2. Для того чтобы вызвать нужный метод, достаточно взять значение по правильному смещению внутри объекта, разыменовать его, чтобы получить процедуру, и затем вызвать ее. Однако такой подход, хотя он и приемлем по скорости выполнения, является затратным с точки зрения другого важного ресурса — а именно памяти. Каждый объект должен отводить память (один указатель) для каждого метода. Более того, создание объекта включает в себя инициализацию всех полей методов, что представляет собой ненужные затраты. Возможен компромисс между скоростью и памятью, который основан на том, что все экземпляры одного класса должны совместно использовать одни и те же методы. При таком подходе для каждого класса создается единственная таблица, называемая таблицей виртуальных методов, и все экземпляры класса содержат один указатель на нее (рис. 21.3). Инициализация нового экземпляра подразумевает установку этого указателя на таблицу виртуальных методов. PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 21.2. Методы, реализованные как поля Рис. 21.3. Два бильярдных шара с общей таблицей виртуальных методов Значения полей в таблице виртуальных методов — это указатели на процедуры. Если мы предположим, что эти процедуры известны компилятору и не изменяются во время выполнения программы, то таблица может быть создана статически во время компиляции. Чтобы выполнить метод, нам нужно знать только его смещение в таблице виртуальных методов. Как и область данных, таблица виртуальных методов класса-предшественника входит во все таблицы классов-потомков, а смещения методов в таблице родителя будут теми же самыми в таблицах потомков. Класс, который наследует методы надкласса, просто копирует общую часть из его таблицы виртуальных методов в свою. Когда в подклассе переопределяется метод, необходимо только изменить запись для этого метода. На рис. 21.4 показана таблица виртуальных методов для классов Wall и Ball, каждый из которых является потомком класса GraphicalObject. Заметьте, что у них общие указатели на методы, унаследованные от родительского класса, и что порядок методов совпадает с тем, который задан в родительском классе. PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 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 при внутреннем PDF created with pdfFactory Pro trial version www.pdffactory.com представлении. Обычно пользователю никогда не требуется знать это имя, если только нет необходимости анализировать ассемблерный код, созданный компилятором. В языках программирования, подобных 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). Как и в системе с таблицами виртуальных методов, при использовании таблиц диспетчеризации каждый объект содержит внутри себя неявный (то есть необъявленный) PDF created with pdfFactory Pro trial version www.pdffactory.com указатель на таблицу диспетчеризации, связанную с его классом. Этот неявный указатель называется указателем связи 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 определяемым по селектору метода. Каждая запись в кэш-таблице представляет собой тройку, состоящую из указателя на класс (для этой цели служит собственно таблица диспетчеризации), значения селектора и указателя на метод. Когда функцию пересылки сообщений просят найти метод, который соответствует паре «класс–селектор», она прежде всего осуществляет поиск в кэш-таблице (рис. 21.6). Если запись в кэше по месту расположения хэш-кода соответствует требуемым селектору и классу, то соответствующий метод может быть выполнен немедленно. Если нет — проводится процесс поиска, описанный выше. В результате поиска непосредственно перед выполнением найденного метода происходит обновление кэш-таблицы. При этом запись, содержавшаяся по месту соответствующего хэш-кода (рассчитываемому по селектору 2 Хэширование (hashing) — метод приближенного индексирования для сокращения поиска нужных данных. При хэшировании каждому данному ставится в соответствие хэш-код (hash-code), который используется для упорядочивания данных в хэш-таблице и служит селектором при их поиске. Характерная черта хэш-кода состоит в том, что он, вообще говоря, не является уникальным (то есть различные данные могут порождать при вычислениях одинаковый хэш-код). Однако он быстро вычисляется и позволяет значительно сократить область поиска данных. Примером хэширования служит словарь с закладками по месту смены первой буквы слов. Здесь первая буква слова выступает в качестве его хэш-кода. — Примеч. перев. PDF created with pdfFactory Pro trial version www.pdffactory.com |