ми в сигнатуре были только идентификаторы других сигнатур и идентификаторы встроенных функций (такие, как + или : :)3.

Упражнение 3.2.4 Пусть даны структуры:

structure А = struct datatype a D = d of a end structure В = struct

type t = int A.D fun f(A.d(x)) = A.d(x+1) end

С какими из следующих сигнатур будет сопоставима структура В ?

1.sig type t val f: int A.D -> int A.D end

2.sig type t val f: t -> int A.D end

3.sig type t val f: t -> t end

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

-signature SIG =

type a List

val Append : a List * a List -> a List end;

-structure S : SIG =

datatype a List = Nil I Cons of a * a List fun Append (x.Nil) = x

I Append (x,Cons(h,t)) = Cons(h,Append(x,t))

> structure S = struct

type a List

val Append = fn : a List * a List -> a List end

2 Свободным называется идентификатор, который не объявлен в сигнатуре. (Прим. перев.)

3Подчеркнем, что правило замкнутости сигнатуры является не формальным требованием языка, а рекомендацией, следование которой облегчает построение сложных программ. (Прим. перев.)

В качестве упражнения убедитесь, что структура S действительно сопоставима с сигнатурой SIG (следуйте тем же путем, каким мы шли в приводимых ранее примерах).

В приведенном выше примере сигнатура SIG, приписанная структуре S, не содержит упоминаний о конструкторах значений типа List. Имеется два способа включить эти конструкторы в сигнатуру. Один из них состоит в том, что конструкторы трактуются как обычные значения, как показывает следующий пример:

-signature SIG =

type a List val Nil: a List

val Cons ; a * a List -> a List val Append : a List * a List -> a List end;

-structure S : SIG =

datatype a List = Nil I Cons of a * a List fun Append(x.Nil) = x

I Append(x,Cons(h,t)) = Cons(h,Append(x,t))

>structure S =

type a List val Nil: a List

val Cons : a * a List -> a List val Append = fn : a List * a List -> a List end

Обратите внимание на то, что a List больше не является рекурсивным типом, и что Nil и Cons являются обычными переменными, а не конструкторами значений.

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

-signature SIG =

datatype a List = Nil I Cons of a * a List val Append : a List * a List -> a List end;

-structure T : SIG = S;

>structure T =

type a List

con Nil : a List

con Cons : a * a List -> a List val Append = fn : a List * a List -> a List end

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

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

Упражнение 3.2.5 Реализуйте стек, используя структуры и сигнатуры.

На практике структуры обычно строятся на основе других структур в соответствии с принципами, определяемыми решаемой задачей. Если структура S построена на основе другой структуры Т, то говорят, что S зависит от Т. Мак-Квин рассматривал две классификации зависимости. Во-первых, зависимость S от Т может быть существенной или несущественной. Существенная зависимость имеет место тогда, когда S не может быть использована без Т - связь между структурами настолько тесная, что раздельное их использование является бессмысленным. Любые другие формы зависимости являются несущественными. Во-вторых, зависимость S от Т может быть явной или неявной. Зависимость S от Т будет явной, если сигнатура S может быть записана только со ссылками на сигнатуру Т; в противном случае зависимость является неявной. Заметьте, что явная зависимость всегда является существенной.

Простейший случай несущественной зависимости возникает, если S импортирует некоторые значения из Т, как в следующем примере:

-structure Т =

val х = 7 end;

> structure T = struct

val x = 7 : int end

-structure S =