Пратт Т. Языки программирования. Разработка и реализация
Подождите немного. Документ загружается.
325
го класса. Конструкции
poolDictionaries и category в данном случае не нужны (они
описаны в приложении, раздел П.12), но синтаксис Smalltalk требует, чтобы все
параметры ключевых методов были приведены, даже если это пустые параметры.
Рассмотрим методы printIt и testIt, которые мы добавляем к классу ClassA при
помощи команды methodsFor:
!ClassA methodsFor: 'basic'!
"Äîáàâëÿåì ìåòîäû ê êëàññó ClassA"
printIt
'Ýòî êëàññ A' printNl !
testIt
self printIt !!
Каждый метод задается посредством указания его имени (и, если требуется,
параметров), затем следует его определение. Окончание определения фиксирует"
ся символом !. Символ !! обозначает завершение объявлений methodsFor для ClassA.
Применение этих методов можно проиллюстрировать на следующем примере:
| x | x _ ClassA new. x testIt !
что, естественно, выводит на печать следующее сообщение:
Ýòî êëàññ A
При этом выполняются следующие шаги:
1) метод new передается классу ClassA, который, в свою очередь, передает его
родительскому классу Object;
2) Object создает новый объект и присваивает его переменной x;
3) метод testIt передается созданному объекту x класса ClassA;
4) метод testIt определяется как self printIt, где self относится к объекту x;
5) метод printIt передается объекту x, который и печатает требуемое сообщение.
Рассмотрим теперь, что произойдет, если мы определим аналогичный метод для
ClassB, в котором есть метод printIt, но отсутствует testIt:
!ClassB methodsFor: 'basic'!
printIt
'Ýòî êëàññ B' printNl !!
Если мы напишем:
| x | x ClassB new. x testIt !
мы получаем:
Ýòî êëàññ B
Метод testIt передается экземпляру x класса ClassB. Поскольку в классе ClassB
метод testIt не определен, то этот метод передается родительскому классу ClassA.
self по"прежнему указывает на объект x, но он теперь принадлежит классу ClassB,
поэтому вызывается метод printIt класса ClassB, а не родительский метод testIt
класса ClassA.
7.2.6. Концепции абстракций
После обсуждения роли методов и виртуальных функций, вероятно, полезно вер"
нуться к обсуждению роли абстракций в языках программирования. Инкапсуля"
7.2. Наследование
326 Глава 7. Наследование
ция часто рассматривается как механизм, позволяющий осуществлять контроль
в процессе разработки программы по принципу «разделяй и властвуй». Програм"
мист имеет доступ только к тем объектам данных, которые являются частью спе"
цификации именно того сегмента программы, разработкой которого он занимает"
ся. Спецификация других частей программы (и внутренняя реализация данных,
отвечающих этой спецификации) от него скрыта. Тем не менее абстракцию дан"
ных и связанную с ней концепцию наследования не следует рассматривать только
как информационную стену, преграждающую программисту доступ к содержимо"
му недоступных объектов данных.
Наследование предоставляет механизм обмена информацией между объекта"
ми в связанных классах. Если À ⇒  означает, что — это класс, связанный с клас"
сом À, то каково взаимоотношение между объектами этих классов? Возможны че"
тыре типа взаимоотношений, как показано на рис. 7.3. К этим четырем типам
сводятся различные способы использования наследования в языках программи"
рования.
Рис. 7.3. Концепции абстракций: а — конкретизация; б — декомпозиция;
в — создание; г — индивидуализация
Конкретизация. Это наиболее распространенная форма наследования, кото"
рая позволяет уточнять свойства производного объекта B по сравнению с исход"
ным объектом A (см. рис. 7.3, а). В частности, стек (stack) — это более точная ха"
рактеристика объекта, чем сложный объект данных, а указание на тип содержимого
327
стека (
int stack, целые числа) уточняет, какой именно стек мы рассматриваем. В то
же время все основные свойства стека сохраняются и в случае целочисленного стека,
так как наследуются методы push и pop. Ранее мы описывали класс NewStack как
производный от ElemStack с добавлением функции peek. Можно сказать, что класс
NewStack является конкретизацией класса ElemStack.
Противоположной концепции конкретизации является концепция обобщение
(например, стек (
stack) — это более общее понятие, чем int stack — целочислен"
ный стек, или real stack — вещественный стек). Обобщение представляет супер"
класс для набора производных классов.
Декомпозиция. Это принцип разбиения абстракции на компоненты (см.
рис. 7.3, б). Он является типичным механизмом инкапсуляции в языках типа Ada,
в которых отсутствует наследование методов. Например, стек (внешняя абстрак"
ция) состоит из переменной top (верхний элемент стека) и массива storage[100]
(внутренняя абстракция). Внутренние имена неизвестны за пределами определя"
ющего класса. Противоположная концепция называется агрегацией.
Создание экземпляров. Этот принцип заключается в создании экземпляров
класса. По существу, он сводится к операции копирования (см. рис. 7.3, в). Объяв"
ление экземпляров объекта некоторого класса в программе на C++ является ти"
пичным примером использования принципа создания экземпляров и заключается
в том, что в программе объект x объявляется принадлежащим к типу y:
stack A, B, C;
В данном случае среда выполнения создает три копии объекта типа stack и на"
зывает их A, B и C.
Противоположная концепция называется классификацией. В частности, в на"
шем примере мы могли бы классифицировать A, B и C как экземпляры класса
stack.
Индивидуализация. Этот четвертый принцип абстракции (см. рис. 7.3, г) не"
сколько труднее для понимания, чем три предыдущих. В данном случае сходные
объекты группируются вместе для некоторых общих целей. Противоположная кон"
цепция называется группированием. Например, среди стеков, используемых транс"
лятором, могут присутствовать записи активации и таблицы символов. И в C, и в
Pascal записи активации реализованы как стеки, но эти стеки имеют различные
характеристики и являются примерами конкретизации. Все стеки тем не менее
имеют одни и те же основные характеристики, примерами которых могут быть
методы push и pop. Но, несмотря на сходство используемых структур, роли записей
активации при выполнении программы на языках C и Pascal различны.
7.3. Полиморфизм
Использование параметров в подпрограммах — одна из наиболее ранних харак"
теристик языков программирования. Тем не менее в большинстве языков про"
граммирования параметры имеют одну важную характеристику: у них есть l"зна"
чение. Это значит, что параметр представляет собой объект данных, который
должен быть размещен в записи активации во время выполнения программы.
Всем знакомы конструкции типа P(A, 7) или Q(B, false, 'i'). Но выражения типа
7.3. Полиморфизм
328 Глава 7. Наследование
R(integer, real)
, в которых параметрами являются типы данных, встречаются
крайне редко.
Полиморфизм означает способность одной операции или имени подпрограммы
ссылаться на любое число определений функций, зависящих от типа данных пара"
метров и результатов. Мы уже сталкивались с некоторым ограниченным видом
полиморфизма в главе 5 при обсуждении перегрузки некоторых операций. В вы"
ражениях 1 + 2 и 1.5 + 2.7 имеются в виду две различные операции сложения: в пер"
вом случае это целочисленное сложение, во втором — вещественное. Использова"
ние модификатора generic в языке Ada позволяет с некоторыми ограничениями
перегружать функции, когда компилируется несколько экземпляров функции,
каждому из которых соответствует свой набор типов параметров и результатов.
Операция унификации в языке Prolog также может рассматриваться как вид по"
лиморфизма, так как Prolog пытается унифицировать запрос при помощи набора
правил и фактов, содержащихся в его базе данных.
Полиморфизм, как правило, применяется к функциям, у которых одним из па"
раметров является тип данных. Из обсуждаемых языков наиболее общее примене"
ние полиморфизма обеспечивают ML и Smalltalk. Например, аргумент тождествен"
ной функции
ident может быть любого типа. Если мы определим ее как
fun ident(x) = x;
мы получим от ML ответ:
- fun ident(x) = x;
val ident = fn : 'a -> 'a
означающий, что функция ident получает аргумент типа 'a (то есть произвольного
типа) и возвращает аргумент типа 'a (то есть того же типа) для параметра типа 'a .
Таким образом, передача в функцию ident целочисленных и строковых парамет"
ров, а также целочисленных списков является корректной:
- ident(3);
val it = 3 : int
- ident("abc");
val it = "abc" : string
- ident([1,2,3]);
val it = [1,2,3] : int list
В ML некоторые операции в определении функции допускают полиморфизм,
как, например, операция равенства и операции, создающие списки объектов. Тем
не менее для некоторых операций область возможных типов параметров ограни"
чена. Например, арифметические операции сложения и вычитания могут приме"
няться только к арифметическим типам. Как уже было объяснено ранее, операция
сложения + перегружена, так как она относится к различным числовым типам дан"
ных. По этой причине уже рассмотренные нами выше определения в ML типа
fun area(length,width) = length*width;
являются неоднозначными, хотя area(1, 2) или area(1.3, 2.3) будут уже вполне
однозначными обращениями к функции. В ML используется статическая провер"
ка типов аргументов функций, хотя динамическая проверка типов сделала бы функ"
цию area полиморфной.
Разница между полиморфизмом в ML и общими функциями в Ada заключает"
ся в том, что в Ada компилировалось бы несколько различных функций ident, каж"
329
дая из которых соответствовала бы своему типу аргумента, а в ML достаточно од"
ного экземпляра функции. Вообще говоря, функции в ML, в которых используют"
ся равенство (или неравенство) и создание кортежей (tuples) и списков, могут быть
полиморфными, так как эти операции не обязательно производятся над фактиче"
скими данными.
Аргументы функций ML могут принадлежать любому типу (который опреде"
ляется статически). Следовательно, мы можем написать полиморфные функции,
которые получают параметры и применяют их к объектам данных. Рассмотрим
следующие две функции ML:
length, которая вычисляет длину списка целых чи"
сел, и printit, которая печатает элементы этого списка в заданном порядке:
fun length(nil) = 0
| length(a::y) = 1+length(y);
fun printit(nil) = print("\n")
| prx(a::y: int list) = (print(a);printit(y));
Теперь можно вызвать функцию process с аргументами любого типа (единствен"
ное требование заключается в том, чтобы они были совместимы), например
fun process(f,l) = f l;
где f l эквивалентно f(l). Тогда мы можем получить следующее:
process(printit,[1,2,3]);
123
process(length,[1,2,3]);
3
Реализация. В случае языков со статической проверкой типов, таких как ML
и С++, полиморфизм не прибавляет новых сложностей при реализации. Тем не
менее с языками, в которых допускается динамический полиморфизм (например,
вариант языка LISP под названием Scheme), дело обстоит несколько сложнее, по"
скольку аргументы полиморфной функции должны быть определены во время
выполнения программы.
В качестве примера можно рассмотреть эту ситуацию в языке LISP. Элемент
списка в LISP состоит их трех полей, которые мы называли ранее полем типа, по"
лем car и полем cdr (раздел 6.1.7). Поскольку поля car и cdr имеют фиксирован"
ный размер, а аргументы полиморфной функции могут быть одного из нескольких
различных типов, то для выполнения программы необходимо определить, каков
фактический тип аргумента.
Аргумент полиморфной функции может быть представлен одним из двух сле"
дующих способов.
1. Непосредственный дескриптор встречается тогда, когда значение парамет"
ра, передаваемого в функцию, меньше, чем размер фиксированного поля.
Например, если функции передается в качестве параметра булево значение,
короткое целое число или символ, то используется пространство меньшее,
чем позволяет объект фиксированного размера. В таком случае фактическое
значение параметра помещается в поле car или cdr, а оставшиеся дополни"
тельные биты в поле используются для сообщения функции о фактическом
типе аргумента.
2. Блоковый дескриптор используется во всех других случаях. Поля car и cdr
будут содержать индикатор типа, указывающий на то, что параметр яв"
7.3. Полиморфизм
330 Глава 7. Наследование
ляется блоковым, а остальная часть поля будет содержать адрес памяти
фактического объекта (который может располагаться где угодно, напри"
мер в куче). По этому адресу будет содержаться вся информация о типе
этого объекта, например в случае сложного объекта данных — его полная
структура.
В качестве примера рассмотрим ситуацию, когда размер поля car или cdr равен
5 байт. Первый байт является идентификатором типа данных, а байты со второго
по пятый отведены непосредственно под данные. Полиморфной функции могут
быть переданы следующие параметры.
1. Целое число размером 32 бит. Первый байт равен 0, что соответствует цело"
му типу параметра, байты со второго по пятый содержат 32"битовое целое
число.
2. Символ размером 8 бит. Первый байт в данном случае равен 1 (что соот"
ветствует символьному типу данных), второй байт содержит фактическое
значение аргумента, остальные байты (с третьего по пятый) не использу"
ются.
3. Булево значение размером 1 бит. Первый байт принимает значение 2, а вто"
рой байт равен 0 или 1.
4. Запись сложной структуры. Первый байт равен 3, а байты со второго по
пятый содержат указатель на запись. r"значение, соответствующее этому
адресу, предоставляет более полную информацию о фактическом аргу"
менте.
Вычисление такой полиморфной функции будет более медленным, чем для
функции в языке со статическим определением типов, например C++, потому что
выполняющая программа должна исследовать параметры, прежде чем получить
их фактические значения. Тем не менее во многих приложениях выигрыш от ис"
пользования полиморфных функций перевешивает неэффективность выполнения
программ.
7.4. Рекомендуемая литература
В начале 70"х гг. Давид Парнас (David Parnas) внес значительный вклад в разра"
ботку инкапсулированных типов данных [86]. Развитие объектно"ориентирован"
ного подхода в программировании является предметом рассмотрения в [53]. Кон"
ференция ACM «Разработка языков программирования для создания надежного
программного обеспечения», состоявшаяся в 1977 г., явилась, вероятно, наиболее
глобальным событием подобного рода, где предлагались различные механизмы ин"
капсуляции в языках Alphard, CLU, Gypsy, Mesa, Euclid и др. [122].
Начало развития объектно"ориентированного подхода к программированию
было положено при появлении Smalltalk"72 и его «последователей» [56], хотя при"
знанию этого языка препятствовали проблемы с доступностью его реализаций.
Более полное обсуждение вопросов наследования вы найдете в [110]. Полимор"
физм и типы в языке ML обсуждаются в [115].
331
7.5. Задачи и упражнения
1. Определите полиморфную функцию reverse в ML, которая получала бы в
качестве аргумента список объектов некоторого типа и возвращала бы эти
же объекты, но в обратном порядке.
2. Разработайте набор полиморфных функций (например, push, pop, NewStack,
top) в ML, которые позволяли бы создавать стеки, содержащие элементы
любого типа.
3. Предположим, что для экземпляров класса object определен метод print.
Объясните, как будет выполняться оператор Smalltalk 3 print.
4. Опишите выполнение каждого из следующих выражений Smalltalk:
а)
2 + 3
б) 3 + 2
в) '2' + 3
г) (2 + 3) print
д) (2 < 3) ifTrue:['true' print] ifFalse:['false' print]
5. Почему использование стандартных файлов включения .h в C не обеспечи"
вает адекватных возможностей абстракции данных для программ на C?
6. Зачем нужны чистые виртуальные классы в C++? Мы могли бы воздержаться
от распределения в памяти объектов этого класса и просто использовать
подклассы суперкласса.
7. Взгляните еще раз на рис. 7.1, где представлены две модели реализации аб"
страктных типов данных. Какая модель соответствует Smalltalk, а какая —
C++? Как они реализованы?
8. Почему в Smalltalk необходимо иметь различные методы для классов и эк"
земпляров классов? Возможно ли отказаться от одного из этих механизмов
и по"прежнему эффективно писать программы на Smalltalk?
9. Рассмотрим следующие объекты: прямоугольник, круг, квадрат, треуголь"
ник, многоугольник, прямая, точка, объект, четырехугольник, сфера, трапе"
ция, параллелограмм, шестиугольник, пятиугольник, пирамида, конус. Раз"
работайте для них иерархию классов и определите соответствующие наборы
функций, использующие наследование для вычисления объема, периметра
и площади поверхности этих объектов (где это возможно).
7.5. Задачи и упражнения
Приложение.
Обзоры языков
В этой книге мы акцентировали внимание на синтаксисе и семантике тринадцати
различных нотаций: Ada, C, C++, FORTRAN, HTML, Java, LISP, ML, Pascal, Perl,
Postscript, Prolog и Smalltalk. Язык HTML был достаточно хорошо описан в гла
ве 12. В данном приложении мы представляем примеры программ на остальных
двенадцати языках, которые менее подробно рассматривались в этой книге, а так
же приводим основы синтаксиса и семантики, необходимые для написания про
стых программ на каждом из этих языков.
П.1. Ada
Пример с пояснениями
В листинге П.1 приведен пример программы суммирования элементов массива.
Здесь мы используем инкапсуляцию, обеспечиваемую пакетами языка Ada, чтобы
реализовать сокрытие информации. Для входных данных
4 1 2 3 4 5 1 2 3 4 5 0
программа печатает следующие результаты:
1 2 3 4
SUM = 10
1 2 3 4 5
SUM = 15
Листинг П.1. Пример суммирования элементов массива на языке Ada
1 package ArrayCalc is
2 type Mydata is private;
3 function sum return integer;
4 procedure setval(arg:in integer);
5 private
6 size: constant:= 99;
7 type myarray is array(1..size) of integer;
8 type Mydata is record
9 val: myarray;
10 sz: integer := 0;
11 end record;
12 v: Mydata;
13 end;
14 package body ArrayCalc is
565
15 function sum return integer is
16 temp: integer;
17 -- Òåëî ôóíêöèè sum
18 begin
19 temp := 0;
20 for i in 1..v.sz loop
21 temp := temp + v.val(i);
22 end loop;
23 v.sz := 0;
24 return temp;
25 end sum;
26 procedure setval(arg:in integer) is
27 begin
28 v.sz := v.sz+1;
29 v.val(v.sz) := arg;
30 end setval; end;
31 with Text_IO; use Text_IO;
32 with ArrayCalc; use ArrayCalc;
33 procedure main is
34 k, m: integer;
35 begin –– íà÷àëî ãëàâíîé ïðîãðàììû main
36 get(k);
37 while k>0 loop
38 for j in 1..k loop
39 get(m); put(m, 3);
40 setval(m);
41 end loop;
42 new_line; put("SUM =");
43 put(ArrayCalc.sum,4);
44 new_line; get(k);
45 end loop;
46 end;
Строка 1. Спецификация пакета ArrayCalc, который собирает массив данных
для этой программы. Все детали о пакете ArrayCalc, которые должны быть извест
ны за пределами этого пакета, следует задать в этой спецификации.
Строка 2. Тип данных MyData будет известен за пределами данного пакета. Од
нако этот тип определен как private, а значит, можно объявлять объекты типа MyData
и передавать их функциям, описанным только внутри пакета ArrayCalc.
Строки 3–4. Здесь определяются подпрограммы sum и setval. Указаны только
сигнатуры двух подпрограмм, чтобы разрешить компиляцию вызовов этих под
программ из других пакетов.
Строка 5. Ключевое слово private обозначает, что вся последующая информа
ция в этой спецификации пакета не может использоваться в подпрограммах, опре
деленных за пределами пакета ArrayCalc.
Строка 6. Имя size определяется как константа, равная 99. Область видимости
данной константы ограничивается пакетом ArrayCalc.
Строки 8–12. Описываются локальные данные пакета, а именно Mydata и v.
Строка 14. Здесь начинается реализация пакета ArrayCalc, где задаются детали
реализации каждой подпрограммы, объявленной в спецификации пакета.
Строка 17. Комментарии в языке Ada начинаются с символов –– и продолжа
ются до конца строки.
Строки 18–25. Блок begin является телом функции sum.
П.1. Ada
566 Приложение. Обзоры языков
Строки 20–22. Итерационный процесс управляется оператором loop. Существу
ет несколько его вариантов. В данной подпрограмме используется вариант цикла
for, который повторно выполняет тело цикла, пока переменная цикла i принимает
последовательные значения от 1 до v.sz. Заметим, что переменная i не была объяв
лена, но она неявно объявляется как локальная переменная, действующая внутри
оператора цикла.
Строки 26–30. Здесь определяется подпрограмма setval. Формальный пара
метр arg является только входным и аналогичен параметру в языке Pascal, переда
ваемому по значению.
Строка 31. Ключевое слово with указывает, что в следующем далее компоненте
языка Ada должен использоваться стандартный пакет Text_IO. Все объекты, опре
деленные в Text_IO, в качестве префикса содержат имя пакета. Поскольку Text_IO
является стандартным пакетом вводавывода, среди прочих в нем определены функ
ции Text_IO.get и Text_IO.put.
Команда use специфицирует, чтобы компилятор Ada первым просматривал па
кет Text_IO для определения области видимости объектов. Это позволяет в про
грамме использовать, например, имя put вместо полного имени Text_IO.put.
Строка 32. Пакет ArrayCalc также будет использоваться в следующем далее ком
поненте Ada.
Строка 33. Программа, написанная на языке Ada, состоит из главной процеду
ры, которая может вызывать подпрограммы из различных пакетов. В этом приме
ре главная процедура называется main.
Строка 36. Для чтения данных в пакете Text_IO определена функция get. Это
перегруженная функция, так что аргумент может быть целой переменной (в дан
ном примере k), строковой переменной или парой (файл, объект), позволяющей
считывать данные из файлов. Поскольку для каждого случая набор аргументов
уникален, то компилятор сам знает, какую функцию get следует вызывать.
Строка 39. Функция get считывает данные в целую переменную m. Функция
put, определенная в пакете Text_IO, выводит на печать значение своего аргумента.
Необязательный второй аргумент задает ширину поля вывода для печати значе
ния объекта. Так, значение переменной m печатается в виде трех символов (с пред
шествующими пробелами для чисел, меньших 100).
Строка 40. Вызывается процедура setval пакета ArrayCalc, которой передается
фактический параметр m. Поскольку в строке 32 имеется команда use, то нет не
обходимости в задании полного имени процедуры ArrayCalc.setval.
Строка 42. Функция new_line, определенная в пакете Text_IO, выводит на пе
чать символ конца строки. Функция put печатает SUM =. Обратите внимание на то,
что этот вызов функции отличается от вызова функции put в строке 39, поскольку
данная функция печатает строку, а функция put в строке 39 печатает целое число.
Реализация перегрузки функций определяет, какую функцию следует вызвать.
Строка 43. Здесь употребляется полностью уточненное имя. Изза того, что в стро
ке 32 использовалась команда use, вместо этого имени можно было бы написать про
сто sum. Полностью уточненное имя необходимо использовать, если одно и то же имя
функции используется в нескольких пакетах внутри области видимости текущего
оператора и при разрешении перегрузки они окажутся неразличимы. В данном случае
число, возвращаемое функцией sum, печатается в виде четырех выходных символов.