Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[8]

Определяет множество всех значений , которые мы должны иногда называть Top(наибольший тип):

type Top - За. атип любого значения.

Множество всех упорядоченных пар может быть определено следующим экзстенциональным типом.

тип любой пары.

Это тип любой пары p,q ,так как для некоторого типа и для некоторого типа b , p и q имеют тип a*b.Тип любого объекта вместе с операцией возвращяющей integer , которая может быть применена к нему может быть определен следующим экзистенциональным типом.

Пара (3,succ) имеет этот тип , если мы возмем а=Ь11Аналогично пара ([1,2,3],length) имеет этот тип , если мы возмем аЬй].

Так как типы включает не толькопростые типы но еще и универсальные типы и тип Top, ъкзистенцианально квантифицированные типы имеют некоторые свойства , котрые могут спевар показаться не интуитивными.Тип За- а *а это не просто тип пар эквивалентных типов, как некотроые могут ожидать. В действительности даже тип 3,true имеет этот тип.Мы знаме ,что 3 и true имеют тип Тор, следовательно есть тип а=Тор , такой что 3,птде:а*а.Поэтому тип За. а у а это тпи всех пар, также как За. ЗЬ а х Ь.Также любая ффункция имеет тип За. а -»а ,если мы в качестве а возмем Тор.

Однако За. а х (а Int) эт0 отношение между типом объектом и типом функией ,возвращающей integer.Например (3,length) не имеет этого типа (если посчитаем 3 типом Top , тогда нам надо показать ,что length имеет тип Top-> Int, но мы уже знаем что , Length имеет тип Va. List[a] а з который отображает целочисленный список на integer , и мы не моджем предположить ,что произкольный объект типа Top можно отобразить на Integer) Не все экзистенуиональные типы могут быть полезными.Например если у нас есть неизвестный объект типа За. а, то у нас нет способов манипулирования им , так как у нас нет информации о нем . Если мы имеем неиъвестный объект типа За. ava: х0 мы можем предположить ,что это пара и пременить к ней fst и snd, но потом вызапнемся так как мы не имеем информации о а.

Экзистенционально типипзированные объекты могут быть полезны , если они достаточно структурированны.Например х: За. а х{а -> Int] предоставляет достаточную структурированность ,чтобы над ним проводить вычисления.Мы можем выполнить:

и получить integer.

Следовательно есть полезные экзистенциональные типы , которые могут сркывать структуру объекта ,который они предствляют , но показывают достаточную структуру ,чтобы позволять манипулировать этими объектами через оперрации ,предоставлямые этим объектом.

Эти экзистенциональные типы могут быть использованы ,например , разнородных списков:


Мы можем позже изъять элемент этого списка и манипулировать им , хотя мы можем не знать ,какой конкретный элемент мы используем и какого он типа.Конечно ,мы можем сфрмиировать разнородный спииок типа Listpa.a; н0 Это достаточно бесполезно.

5.1 Экзистенциональная ква нитфикация и сокрыие информации.

Реальная польза экзистенциональных типов становится видимой , только тогда когда мв понимаем ,что За. а х {а. Int) простой пример абстракции данных с множеством своих операций. Переменная а сама является абстрактным типом , котрый скрывает представление.Представление было Int и List[Int] в предыдущем примере.Тогда

это множество операторов над абстрактным типом: константа типа а и оператор типа a -> Int. Эти оперраторы не обозначены ,но мы можем ввести обозначенные версии ,используя тип запись вместо декартова произведения:

х: За. {const: a, op: а -> Int} х.ор(х.const}

Так как мы не знаем какого представления а ,то мы не можем ничего предположить о нем и пользователи х не смогут использовать преимущества некоторого конкретного типа а.

Как мы объявляли ранее , мы были немного свободны в применении разных операторов к объектам экзистеционального типа. Это будет теперь запрещено , чтоюы сделать наш формализм более простым для проверки типов.Вместо этого мы будем иметь явные языковые кострукции для создания и манирулироввания объектами экзистенционального типа , так как мы имели абстракции типов all[t] и означивание типов exp[t] Для создания и использования объектов универсальных типов.

Обычный объект (3,succ) может быть в абстрактный объект ,имеющий тип

За. а х (a->lnt) ПрИ ПОМОщИ пакетирования и поэтому некоторая структура его

скрыта.Операция pack снизу инкапсулирует объект (3,succ) , так чтобы пользователь знал

только ,что это объект типа а х (a-nntj существует без знания фактического

объекта.Естествено подумать ,что результирующий объект имеет экзитсенциональный

тип За. a x(a-*lnt).

value р = pack [a=lnt in а * (a->lnt)] (3,succ) : 3a. a x(a->lnt)

Пакетированный объект такой как р называется пакетом.Значение (3,succ) Это содержание пакета.Тип а у <a-*rt) это интерфейс: он определяет структурное пределение содержания и соответствует определению части абстракции данных.Связывание а=Ьп" это представление типов : оно связывает абстрактный тип данных с конкретным представлением Int и соответствует скрытому типу данных ассоциированный с абстракцией данных. Общая форма операции pack

pack [а = пурегер in interface] (couthits) Операция pack это единственный механизм для создания объектов экзистенционального типа. Таким образом если переменная экзистенционального типа была объявлена так :

р : За. а * (а -»Int)

Тогда р может брать только значения созданные операцией pack. Пакет должен быть открыт перед тем как его использовать


open p as x in (snd(x))(fct(x))

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

value р = pack [а = Int in {arg:a, op:a-»lnt}] (3, succj open p as x in x.op(x.arg)

Нам может также понадобиться ссылаться на неизвестный тип скрытый пакетом. Например ,представьте ,что мы хотели означить второй компонент p значением абстракного типа ,приведенного как внешний аргумент.В этом случае на неизвестный тип b должна быть внешняя ссылка и следующая форма может быть использована:

open р as х [1з] in ... fun(y:b) (snd(x))(y)...

Здесь имя типа b соответствует скрытому представлению типа в области следующей за in.Тип выражения следующего за in не должен содержать b,чтобы b не вышло из своей области видимости. Функция open связывает имена с представлениями типов и помогает проверятелю типов в верификации типовых структур.Во многих ситуациях мы захотим сократить р as х in х.а до р.а.Мы должны избегать таких сокращений ,чтобы предотварщать конфликты ,но вообще они приминимы.

И pack и open не имеют влияния времени выполнения на данные.Предоставляя достаточно умный проверяльщик типов , некоторые могут опустить эти конструкции и вернуться к нотации ,использованной с предыдущих секциях.

5.2 Пакеты и абстрактные типы данных.

Чтобы проиллюстрировать применимость нашей нотации к реальным языкам программирования , мы покажем как записи с функциональными компонентами могкт быть исползованы для моделирования пакетов в Ада и как экзистенциональная квантификация может быть использована для моделтрования абстракций данных в Ада[83].Рассмотрим тип Point1 лдя создания геометрических точек от глобально определенного типа Point - пары действительных чисел и для выбора х и у координат точек.

type Point = Real * Real type Pointl =

{makepoint: {Real v Real) -> Point

x coord: Point -* Real

y coord: Point -»Real

}

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

value poind : Pointl =

{makepoint = fun(x:Real,y:Real) (x,y), x coord = fun (p: Point) fst(p), y coord = fun(p:Point) snd{p)

}

В Ада пакет с функциями makepoint , x coord , y coord может быть определен так:



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13]