-Объекты имеют соответствующий объектный тип.

-Типы могут наследовать аттрибуты от супертипов.

Эти требования могут быть суммированы следующим образом:

Объектно-ориентированность= абстракции данных + объектные типы + наследование.

Полезность этого определения может быть проиллюстрирована рассмотрением влияния каждого из этих требований на методологию. Абстракции данных сами по себе предоставляют способ организации данных с соответствующими операциями , что сильно отличается от традиционной методологии процедурных языков. Реализация методологии абстракций данных была одной из главных целей Ады и эта методология описывается в литературе по Ада [83]. Однако Ада удовлетворяет только первому из трех условий объектной-ориентированности и интересно рассмотреть влияние типов объектов и наследования на методологию абстракций данных[86].

Требование ,что все объекты имеют тип ,позволяет им быть первостепенными значениями ,поэтому к ним можно обращаться как к структурам данных для вычислений. Требование наследования разрешает определять отношения между типами. Наследование можно рассматривать как механизм структурирования типов, который позволяет свойствам одного или более типов быть использоваными в определениях другого типа.Определение B наследует A может быть представлено как механизм упрощения , который избегает переопределения аттрибутов типа А в определении B. Однако наследование это больше чем упрощение , так как оно влияет на структуру между совокупностью связанных типов ,которая может сильно уменбшить сложность определения системы. Это показано на примере объектной иерархии в Smalltalk в [83].

Иерархия объектов в Smalltalk это описание среды программирования Smalltalk.По идее это близко к функцие apply в Лисп ,которая описывает интерпретатор языка Лисп,но более сложнее.Она описывает совокупность более 75 связанных объектов системы в терминах иерархии наследования. Объектные типы включают в себя численные объекты ,структурированные объекты ,объекты ввода-вывода итд. Объектная иерархия выносит свойства общие для всех численных объектов в супертип Number ,а свойства присущие всем структурированным объектам - в супертип Collection.Далее свойства общие для численных структурированных объектов и объектов ввода -вывода выносятся в супертип Object.Таким образом коллекция более 75 объектов ,которая составляет среду Smalltalk описана относительно простой структурированной иерархией объектных типов. Упрощение предоставляемое иерархией объектов в повторном использовании суперклассов ,чьи аттрибуты совместно используются подклассами присуща коцептуальной расчетливости ,достигаемой за счет навязывания связанной структуры коллекции объектных типов.

Объектная иерархия в Smalltalk также замечательна тем ,что она иилюстрирует силу полиморфизма.Мы можем определить полиморфную функцию как функцию применимую к значениям более чем одного типа и полимрфизм включения как отношение между типами ,которое разрешает применение операций к объектам разных типов связанных включением. Объекты считаются коолекциями таких операций (аттрибутов). Это подчеркивает совместное использование операций операторами разных типов ,как главной черты полиморфизма.

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

супертип Number.Аттрибуты общие для типов-структур заключены в супертип Collection.Аттрибуты общие для всех типов заключены в супертип Object.Таким образом полиморфизм тесно связан с понятием наследования и мы можем сказать ,что выразительная сила системы типов зависит в большей степени от полиморфизма ,который она использует.

Чтобы закончит дискуссию об эволюции типов в языках программирования мы исследуем механизм типов в ML[84].ML это интерактивный функциональный язык программирования ,в котором определения типов пропущенный пользователем , могут быть введены через выводимость типов.Если пользователь вводит "3+4" ,то система ответчает "7:int" , при этом считается значение выражаения и выводятся типы операндов и всего выражения. Если пользователь вводит определение функции "fun f x = x + 1" , то система отвечает "f:int->int", при этом система считает значение функции и выводит её тип "int->int".ML поддерживает выводимость типов не только для традиционных типов ,но также для параметрических(полиморфных) типов ,таких как например функция длины для списков. Если пользователь ввел "fun rec length x = if x = nil then 0 else 1 + length(tail(x));" ,то ML выведет ,что length это функция от списка с элементами произвольного типа ,возвращающая integer(length:a list -> т).Если пользователь затем вводит "length[1;2;3]" ,то система выводит ,что length имеет конкретный тип "int list -> int" и потом применяет конкретную функциюк списку integer.

Когда мы говорим ,что параметрическая функция применима к списку произвольного типы , мы имеем в виду , этот тип может быть конкретихирован некоторым параметром T и поэтому конкретная функция может быть вызвана для конкретных операндов.Есть важное различие между параметрической функцией length для списков произвольного типа и и специальной функцией для списков типа Int. Функцмм такие как length применимы к спискам произвольных типов ,так как они еимеют одинаковое представление параметров , что позволляет конкретизировать тип параметра. Это различие между параметрическими функциями и их конкретными версиями не ясно в языках ,таких как ML, так как параметры типов ,опускаемые пользователем ,автоматически выводятся механизмо выведения типов.

Супертипы в объектно-ориентированных языках ,могут быть представлены как параметрические типы ,чьи параметры опущены пользователем.Чтобы понять схожесть супертипов и параметрических типов полезно ввести нотацию ,где параметры супертипов должны быть явно введены при выделении из супертипа подтипа. Мы увидим ниже ,что Fun имеет явные параметры типов как для параметрических типов так и для супертипов ,для предоставления единой модели как для параметрического полиморфизма ,так и для полиморфизма выделения подтипов.

1.5 Подмножество языка выражения типов.

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

Туое ::= BasicTyoe Constructed Туре

BasicType ::= Int Bool ...

ConstructedType ::= Аггау(Туре) Туре -*Туре

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

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

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

Читатель ,которого интересует обсуждение алгортмов для построения языка выражения типов и проверки типов для таких языков как Паскаль и С отправляются читать главу 6 [85] ,которые рассматривают проверку типов для перегрузки , приведения типов и параметрического полиморфизмаш! добавляет абстрактные типы данных к множеству базовых типов и добавляет подтипы и наслендование к формам полиморфизма ,которые поддерживаются.

1.6 Предварительное рассмотрение Fun.

Fun это язык основанный на Х-исчислении,который раширяет Х-исчисление первого порядка , особенностями второго порядка реализованных для моделирования полиморфизма и объектно-ориентированных языков.

Секция 2 рассматривает нетипизированное и типизированное Х-исчисление и разрабатывает базовые элементы для подъязыка выражения типов в Fun.Fun имеет базовые типы bool, int ,real , string , структурные типы для организации записей ,функций , рекурсивных типов.Это множство типов первого порядка используется как основа для введения параметрических типов ,абстрактных типов данных и наследования типов .

Секция 3 быстро обозревает теоретические модели типов связанных с элементами Fun , особенно модели ,которые представляют тип как множество значений.Представление типов в виде множеств позволяет определить параметрический полиморфизм как пересечение множеств соответствующих типов и полиморфизм наследования в терминах подмножеств соответствующих типов. Абстракци данных могут быть также определены в терминах операций теории множеств над соответствующими типами.

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