Определите другую сигнатуру SUBST и структуру Subst, которая реализует, операцию подстановки для этих выражений (т. е. определите тип Subst как список пар "идентификатор/выражение", и функцию подстановки, которая по выражению и подстановке (значению типа subst) строит выражение, получающееся из исходного путем замены описанных в подстановке идентификаторов на соответствующие выражения).

3.3 Абстракция

Ранее мы отметили, что процесс сопоставления структуры с сигнатурой "обрезает" структуру так, что в ней остаются только компоненты, присутствующие в сигнатуре. Приписывание сигнатуры структуре создает некоторую "проекцию" этой структуры, и, таким образом, сопоставление с сигнатурой обеспечивает некоторый ограниченный способ "сокрытия информации", ограничивая доступ к структуре только теми компонентами, которые имеются в сигнатуре. Одна из причин формирования таких ограничений состоит в том, что при построении сложных программных систем полезно иметь возможность точного описания интерфейса каждого программного модуля. То же самое может быть указано как одна из причин использования абстрактных типов данных в ядре языка: это позволяет сделать всех пользователей данного абстрактного типа данных независимыми от деталей его реализации. Сопоставление с сигнатурой может обеспечить некоторые из возможностей, предоставляемых абстрактными типами данных, поскольку с помощью него возможно "убрать" конструкторы рекурсивных типов, и, таким образом, спрятать внутреннее представление. Но это является одним из частных случаев более общего способа сокрытия информации в ML, называемого абстракцией.

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

-signature SIG =

sig type t

val x : t -> t end;

-structure S : SIG =

type t = int

val x = fn x => x end;

>structure S =

type t = int

val x = fn : t -> t end

-S.x(3);

>3 : int

-S.x(3) : S.t;

>3 : int : S.t

Обратите внимание на то, что S.t есть int, хотя сигнатура SIG ни о чем таком не говорит.

Цель абстракции состоит в том, чтобы скрыть всю информацию о структуре, которая не упоминается явно в сигнатуре.

-abstraction S : SIG =

type t = int

val x = fn x => x

>abstraction S : SIG

-S.x(3);

>3 : int

-S.x(3) : S.t;

Type error in: S.x(3) : S.t Looking for a: int I have found a: S.t

Эффект объявления абстракции состоит в ограничении всей доступной об S информации только той информацией, которая указана в SIG.

Имеется тесная связь между абстракцией и абстрактными типами данных. Рассмотрим следующий абстрактный тип:

-abstype a set = set of a list with

val empty set = set( []) fun union(set(ll),set(12)) = set(11012) end;

>type a set

val empty set = - : a set

val union = fn : a set * a set -> a set

-empty set;

>- : a set

Это объявление определяет тип a set с операциями empty set и union. Конструктор set спрятан для того, чтобы можно было ручаться, что тип

является абстрактным (т.е. что ни одна программа, использующая этот тип, не окажется зависимой от его представления).

В общем случае объявление abstype определяет тип и набор операций над данными этого типа, скрывая при этом тип реализации. Абстракция предлагает другой путь решения этой же задачи, что можно увидеть из следующего примера:

-signature SET =

type a set

val emty set: a set

val union : a set * a set -> a set end;

-abstraction Set: SET =

datatype a set = set of a list val empty set = set( []) fun union(set(ll),set(12)) = set(ll@12) end;

>abstraction Set : SET

-Set.set;

Undefined variable Set.set

-S.empty set;

>- : a S.set

Упражнение 3.3.1 Определите абстракцию для комплексных чисел, используя следующую сигнатуру:

signature COMPLEX = sig

type complex exception divide: unit

val rectangular: {real: real, imag : real} -> complex val plus : complex * complex -> complex val minus : complex * complex -> complex val times : complex * complex -> complex val divide : complex * complex -> complex val eq : complex * complex -> bool val real part : complex -> real val imag part: complex -> real end

Подсказка: используйте следующие формулы для реализации операций над комплексными числами:

(a + ib) + (c + id) = (a + c) + i(b + d)