converted to PDF by BoJIoc
Рис. 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 допускает необязательные описания переменных объекта. Объясните, как компилятор может использовать подобные описания для ускорения обработки сообщений, включающих такие значения. Рассмотрите, что
происходит при операции присваивания и как пересылка сообщений может быть сделана более эффективной.
converted to PDF by BoJIoc
3.Объясните, почему методы, которые в языке C++ не описаны как виртуальные, могут вызываться более эффективно, чем виртуальные методы. Как бы вы произвели замеры времени, чтобы определить, является ли разница существенной?
4.Исследуйте технику кэширования, описанную в разделе 21.2. Объясните, почему класс, запоминаемый в кэш-таблице, — это класс, с которого начинается поиск, а не тот класс, внутри которого найден метод. Объясните, как бы изменился алгоритм просмотра кэш-таблицы, если бы использовалось второе значение. Как вы думаете, новый алгоритм будет работать быстрее или медленнее? Обоснуйте свой ответ.
5.Опишите вкратце структуру интерпретатора языка Smalltalk, основанного на байт- кодах, представленных в тексте.
Приложение А
Исходный код программ для задачи «Восемь ферзей»
В этом приложении приведены готовые программы для задачи о восьми ферзях, описанной в главе 5.
А.1. «Задача о восьми ферзях» на языке Apple Object Pascal
(*
Задача «Восемь ферзей», язык Object Pascal
Автор: Тимоти Бадд, университет штата Орегон, 1996 *)
Program EightQueen; type
Queen = object
(* поля данных *)
row : integer; column : integer; neighbor : Queen;
(* инициализация *)
procedure initialize (col : integer; ngh : Queen); (* операции *)
function canAttack (testRow, testColumn : integer) : boolean; function findSolution : boolean;
function advance : boolean; procedure print;
end; var
neighbor, lastQueen : Queen; i : integer;
procedure Queen.initialize (col : integer; ngh : Queen); begin
(* инициализация нашего столбца и соседних значений *) column := col;
neighbor :=ngh;
(* начать со строки 1 *)
converted to PDF by BoJIoc
row := 1; end;
function Queen.canAttack
(testRow, testColumn : integer) : boolean; var
can : boolean; columnDifference : integer;
begin
(* проверить, одинаковые ли строки *) can := (row = testRow);
(* теперь проверить диагонали *) if not can then begin
columnDifference := testColumn — column; if ((row + columnDifference = testrow) or
(row — columnDifference = testRow)) then can := true;
end;
(* наконец проверить соседей *)
if ((not can) and (neighbor <> nil)) then
can := neighbor.canAttack(testRow, testColumn); canAttack := can;
end;
function Queen.findSolution : boolean; var
done : boolean; begin
done := false; findSolution := true;
(* найти подходящую позицию *) if neighbor <> nil then
while (not done and neighbor.canAttack(row, column)) do if not self.advance then begin
findSolution := false; done := true;
end;
end;
function Queen.advance : boolean; begin
advance := false;
(* попробовать следующий ряд *) if row < 8 then begin
row := row + 1;
advance := self.findSolution; end
else begin
(* дальше нельзя *)
(* передвинуть соседа, чтобы получить следующее решение *) if neighbor <> nil then
if not neighbor.advance then advance := false
else begin
(* начать снова с горизонтали 1 *) row := 1;
advance := self.findSolution; end;
end;
end;
converted to PDF by BoJIoc
procedure Queen.print; begin
if neighbor <> nil then neighbor.print;
writeln('row ', row, ' column ', column); end;
begin
neighbor := nil;
for i := 1 to 8 do begin
(* создать и инициализировать нового ферзя *) new (lastqueen);
lastQueen.initialize (i, neighbor); if not lastQueen.findSolution then
writeln(‘no solution’);
(* самый новый ферзь является следующим соседом *) neighbor := lastQueen;
end;
lastQueen.print;
for i := 1 to 8 do begin neighbor := lastQueen.neighbor; dispose (lastQueen);
lastQueen := neighbor; end;
end.
A.2. «Задача о восьми ферзях» на языке С++
// Задача «Восемь ферзей», язык С++ // Автор: Тимоти Бадд, университет штата Орегон, 1996
//
#include #define bool int #define true 1 #define false 0 class queen
{
public:
// конструктор
queen (int, queen *);
// найти и напечатать решения bool findSolution();
bool advance(); void print();
private:
//поля данных int row;
const int column; queen * neighbor;
//внутренний метод
bool canAttack (int, int);
};
queen::queen(int col, queen * ngh) : column(col), neighbor(ngh)
{
row = 1;
}
bool queen::canAttack (int testRow, int testColumn)