Глава 2 Система модулей
- 2.1 Структуры
- 2.2 Подписи
- 2.3 Функторы
- 2.4 Функторы и абстракция типов
- 2.5 Модули и отдельная компиляция
В этой главе представлена система модулей OCaml.
2.1 Структуры
Основной мотивацией для модулей является объединение связанных определений (например, определений типа данных и связанных операций над этим типом) и обеспечение согласованной схемы именования этих определений. Это позволяет избежать исчерпания имен или случайной путаницы имен. Такой пакет называется структурой и вводится конструкцией struct…end, которая содержит произвольную последовательность определений. Структуре обычно присваивается имя с помощью связывания module. Например, вот структура, объединяющая тип очередей с приоритетами и их операции:
# module PrioQueue =
struct
type priority = int
type 'a queue = Empty | Node of priority * 'a * 'a queue * 'a queue
let empty = Empty
let rec insert queue prio elt =
match queue with
Empty -> Node(prio, elt, Empty, Empty)
| Node(p, e, left, right) ->
if prio <= p
then Node(prio, elt, insert right p e, left)
else Node(p, e, insert right prio elt, left)
exception Queue_is_empty
let rec remove_top = function
Empty -> raise Queue_is_empty
| Node(prio, elt, left, Empty) -> left
| Node(prio, elt, Empty, right) -> right
| Node(prio, elt, (Node(lprio, lelt, _, _) as left),
(Node(rprio, relt, _, _) as right)) ->
if lprio <= rprio
then Node(lprio, lelt, remove_top left, right)
else Node(rprio, relt, left, remove_top right)
let extract = function
Empty -> raise Queue_is_empty
| Node(prio, elt, _, _) as queue -> (prio, elt, remove_top queue)
end;;
module PrioQueue :
sig
type priority = int
type 'a queue = Empty | Node of priority * 'a * 'a queue * 'a queue
val empty : 'a queue
val insert : 'a queue -> priority -> 'a -> 'a queue
exception Queue_is_empty
val remove_top : 'a queue -> 'a queue
val extract : 'a queue -> priority * 'a * 'a queue
end Вне структуры к её компонентам можно обратиться, используя «точечную нотацию», то есть идентификаторы, квалифицированные именем структуры. Например, PrioQueue.insert — это функция insert, определённая внутри структуры PrioQueue, а PrioQueue.queue — это тип queue, определённый в PrioQueue.
# PrioQueue.insert PrioQueue.empty 1 "hello";; - : string PrioQueue.queue = PrioQueue.Node (1, "hello", PrioQueue.Empty, PrioQueue.Empty)
Другой вариант — открыть модуль, что добавляет все идентификаторы, определённые внутри модуля, в область видимости текущей структуры.
# open PrioQueue;;
# insert empty 1 "hello";; - : string PrioQueue.queue = Node (1, "hello", Empty, Empty)
Открытие модуля обеспечивает более лёгкий доступ к его компонентам, но при этом усложняет идентификацию модуля, в котором был определён идентификатор. В частности, открытые модули могут скрывать идентификаторы, присутствующие в текущей области видимости, что потенциально приводит к путанице при ошибках:
# let empty = [] open PrioQueue;; val empty : 'a list = []
# let x = 1 :: empty ;;
Error: This expression has type 'a PrioQueue.queue
but an expression was expected of type int list Частичным решением этой проблемы является локальное открытие модулей, делающее компоненты модуля доступными только в соответствующем выражении. Это также может упростить чтение кода (поскольку оператор open находится ближе к месту его использования) и его рефакторинг (поскольку фрагмент кода более самостоятелен).
# let open PrioQueue in insert empty 1 "hello";; - : string PrioQueue.queue = Node (1, "hello", Empty, Empty)
и
# PrioQueue.(insert empty 1 "hello");; - : string PrioQueue.queue = Node (1, "hello", Empty, Empty)
Во втором случае, когда тело локального open ограничено скобками, фигурными скобками или квадратными скобками, скобки локального open можно опустить. Например,
# PrioQueue.[empty] = PrioQueue.([empty]);; - : bool = true
# PrioQueue.[|empty|] = PrioQueue.([|empty|]);; - : bool = true
# PrioQueue.{ contents = empty } = PrioQueue.({ contents = empty });;
- : bool = true становится
# PrioQueue.[insert empty 1 "hello"];; - : string PrioQueue.queue list = [Node (1, "hello", Empty, Empty)]
Этот второй вариант также работает с шаблонами:
# let at_most_one_element x = match x with | PrioQueue.( Empty| Node (_,_, Empty,Empty) ) -> true | _ -> false ;; val at_most_one_element : 'a PrioQueue.queue -> bool =
Также можно скопировать компоненты модуля в другой модуль с помощью оператора include. Это особенно полезно для расширения существующих модулей. В качестве иллюстрации можно добавить функции, возвращающие необязательное значение вместо исключения, когда очередь с приоритетами пуста.
# module PrioQueueOpt =
struct
include PrioQueue
let remove_top_opt x =
try Some(remove_top x) with Queue_is_empty -> None
let extract_opt x =
try Some(extract x) with Queue_is_empty -> None
end;;
module PrioQueueOpt :
sig
type priority = int
type 'a queue =
'a PrioQueue.queue =
Empty
| Node of priority * 'a * 'a queue * 'a queue
val empty : 'a queue
val insert : 'a queue -> priority -> 'a -> 'a queue
exception Queue_is_empty
val remove_top : 'a queue -> 'a queue
val extract : 'a queue -> priority * 'a * 'a queue
val remove_top_opt : 'a queue -> 'a queue option
val extract_opt : 'a queue -> (priority * 'a * 'a queue) option
end 2.2 Подписи
Подписи — это интерфейсы для структур. Подпись указывает, какие компоненты структуры доступны извне и с каким типом. Она может использоваться для скрытия некоторых компонентов структуры (например, локальных определений функций) или экспорта некоторых компонентов со ограниченным типом. Например, следующая подпись указывает на три операции с очередью с приоритетами empty, insert и extract, но не на вспомогательную функцию remove_top. Аналогично, она делает тип queue абстрактным (путем не предоставления фактического представления как конкретного типа).
# module type PRIOQUEUE =
sig
type priority = int (* still concrete *)
type 'a queue (* now abstract *)
val empty : 'a queue
val insert : 'a queue -> int -> 'a -> 'a queue
val extract : 'a queue -> int * 'a * 'a queue
exception Queue_is_empty
end;;
module type PRIOQUEUE =
sig
type priority = int
type 'a queue
val empty : 'a queue
val insert : 'a queue -> int -> 'a -> 'a queue
val extract : 'a queue -> int * 'a * 'a queue
exception Queue_is_empty
end Ограничение структуры PrioQueue этой подписью приводит к другому представлению структуры PrioQueue, где функция remove_top недоступна, а фактическое представление очередей с приоритетами скрыто:
# module AbstractPrioQueue = (PrioQueue : PRIOQUEUE);; module AbstractPrioQueue : PRIOQUEUE
# AbstractPrioQueue.remove_top ;; Error: Unbound value AbstractPrioQueue.remove_top
# AbstractPrioQueue.insert AbstractPrioQueue.empty 1 "hello";; - : string AbstractPrioQueue.queue =
Ограничение также может быть выполнено во время определения структуры, как в
module PrioQueue = (struct ... end : PRIOQUEUE);;
Предоставлена альтернативная синтаксическая конструкция для вышеописанного:
module PrioQueue : PRIOQUEUE = struct ... end;;
Как и для модулей, можно включить подпись, чтобы скопировать её компоненты в текущую подпись. Например, можно расширить подпись PRIOQUEUE функцией extract_opt:
# module type PRIOQUEUE_WITH_OPT =
sig
include PRIOQUEUE
val extract_opt : 'a queue -> (int * 'a * 'a queue) option
end;;
module type PRIOQUEUE_WITH_OPT =
sig
type priority = int
type 'a queue
val empty : 'a queue
val insert : 'a queue -> int -> 'a -> 'a queue
val extract : 'a queue -> int * 'a * 'a queue
exception Queue_is_empty
val extract_opt : 'a queue -> (int * 'a * 'a queue) option
end 2.3 Функторы
Функторы — это «функции» от модулей к модулям. Функторы позволяют создавать параметризованные модули и затем предоставлять другие модули в качестве параметра(ов), чтобы получить конкретную реализацию. Например, модуль Set, реализующий множества как отсортированные списки, может быть параметризован, чтобы работать с любым модулем, который предоставляет тип элемента и функцию сравнения compare (такую как OrderedString):
# type comparison = Less | Equal | Greater;; type comparison = Less | Equal | Greater
# module type ORDERED_TYPE =
sig
type t
val compare: t -> t -> comparison
end;;
module type ORDERED_TYPE = sig type t val compare : t -> t -> comparison end # module Set =
functor (Elt: ORDERED_TYPE) ->
struct
type element = Elt.t
type set = element list
let empty = []
let rec add x s =
match s with
[] -> [x]
| hd::tl ->
match Elt.compare x hd with
Equal -> s (* x is already in s *)
| Less -> x :: s (* x is smaller than all elements of s *)
| Greater -> hd :: add x tl
let rec member x s =
match s with
[] -> false
| hd::tl ->
match Elt.compare x hd with
Equal -> true (* x belongs to s *)
| Less -> false (* x is smaller than all elements of s *)
| Greater -> member x tl
end;;
module Set :
functor (Elt : ORDERED_TYPE) ->
sig
type element = Elt.t
type set = element list
val empty : 'a list
val add : Elt.t -> Elt.t list -> Elt.t list
val member : Elt.t -> Elt.t list -> bool
end Применяя функтор Set к структуре, реализующей упорядоченный тип, мы получаем операции над множествами для этого типа:
# module OrderedString =
struct
type t = string
let compare x y = if x = y then Equal else if x < y then Less else Greater
end;;
module OrderedString :
sig type t = string val compare : 'a -> 'a -> comparison end # module StringSet = Set(OrderedString);;
module StringSet :
sig
type element = OrderedString.t
type set = element list
val empty : 'a list
val add : OrderedString.t -> OrderedString.t list -> OrderedString.t list
val member : OrderedString.t -> OrderedString.t list -> bool
end # StringSet.member "bar" (StringSet.add "foo" StringSet.empty);; - : bool = false
2.4 Функторы и абстракция типов
Как и в примере PrioQueue, было бы хорошим стилем скрыть фактическую реализацию типа set, чтобы пользователи структуры не полагались на то, что множества являются списками, и мы могли в дальнейшем перейти к другому, более эффективному представлению множеств без нарушения их кода. Это можно достичь, ограничив Set подходящей подписью функтора:
# module type SETFUNCTOR =
functor (Elt: ORDERED_TYPE) ->
sig
type element = Elt.t (* concrete *)
type set (* abstract *)
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end;;
module type SETFUNCTOR =
functor (Elt : ORDERED_TYPE) ->
sig
type element = Elt.t
type set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end # module AbstractSet = (Set : SETFUNCTOR);; module AbstractSet : SETFUNCTOR
# module AbstractStringSet = AbstractSet(OrderedString);;
module AbstractStringSet :
sig
type element = OrderedString.t
type set = AbstractSet(OrderedString).set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end # AbstractStringSet.add "gee" AbstractStringSet.empty;; - : AbstractStringSet.set =
В попытке написать ограничение типа выше более изящно, можно захотеть назвать подпись структуры, возвращаемой функтором, а затем использовать эту подпись в ограничении:
# module type SET =
sig
type element
type set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end;;
module type SET =
sig
type element
type set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end # module WrongSet = (Set : functor(Elt: ORDERED_TYPE) -> SET);; module WrongSet : functor (Elt : ORDERED_TYPE) -> SET
# module WrongStringSet = WrongSet(OrderedString);;
module WrongStringSet :
sig
type element = WrongSet(OrderedString).element
type set = WrongSet(OrderedString).set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end # WrongStringSet.add "gee" WrongStringSet.empty ;;
Error: This expression has type string but an expression was expected of type
WrongStringSet.element = WrongSet(OrderedString).element Проблема здесь в том, что SET указывает на тип element абстрактно, так что равенство типов между element в результате функтора и t в его аргументе забывается. Следовательно, WrongStringSet.element не является тем же типом, что и string, и операции WrongStringSet не могут применяться к строкам. Как показано выше, важно, чтобы тип element в подписи SET был объявлен равным Elt.t; к сожалению, это невозможно сделать выше, так как SET определён в контексте, где Elt не существует. Для преодоления этой трудности OCaml предоставляет конструкцию with type над подписями, которая позволяет обогатить подпись дополнительными равенствами типов:
# module AbstractSet2 =
(Set : functor(Elt: ORDERED_TYPE) -> (SET with type element = Elt.t));;
module AbstractSet2 :
functor (Elt : ORDERED_TYPE) ->
sig
type element = Elt.t
type set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end Как и в случае с простыми структурами, для определения функторов и ограничения их результатов предоставляется альтернативный синтаксис:
module AbstractSet2(Elt: ORDERED_TYPE) : (SET with type element = Elt.t) = struct ... end;;
Абстрагирование компонента типа в результате функтора — мощная техника, обеспечивающая высокую степень типовой безопасности, как мы сейчас проиллюстрируем. Рассмотрим упорядочение строковых символов, отличное от стандартного упорядочения, реализованного в структуре OrderedString. Например, мы сравниваем строки без различия между заглавными и строчными буквами.
# module NoCaseString =
struct
type t = string
let compare s1 s2 =
OrderedString.compare (String.lowercase_ascii s1) (String.lowercase_ascii s2)
end;;
module NoCaseString :
sig type t = string val compare : string -> string -> comparison end # module NoCaseStringSet = AbstractSet(NoCaseString);;
module NoCaseStringSet :
sig
type element = NoCaseString.t
type set = AbstractSet(NoCaseString).set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end # NoCaseStringSet.add "FOO" AbstractStringSet.empty ;;
Error: This expression has type
AbstractStringSet.set = AbstractSet(OrderedString).set
but an expression was expected of type
NoCaseStringSet.set = AbstractSet(NoCaseString).set Обратите внимание, что два типа AbstractStringSet.set и NoCaseStringSet.set несовместимы, и значения этих двух типов не совпадают. Это правильное поведение: хотя оба типа множеств содержат элементы одного типа (строки), они построены на основе разных порядков этого типа, и операции должны поддерживать разные инварианты (строго возрастающие для стандартного порядка и для порядка без учета регистра). Применение операций из AbstractStringSet к значениям типа NoCaseStringSet.set может привести к неверным результатам или созданию списков, нарушающих инварианты NoCaseStringSet.
2.5 Модули и отдельная компиляция
Все примеры модулей до сих пор были представлены в контексте интерактивной системы. Однако модули наиболее полезны для больших программ, компилируемых пакетно. Для таких программ необходимо разделить исходный код на несколько файлов, называемых единицами компиляции, которые можно компилировать отдельно, тем самым сводя к минимуму перекомпиляцию после изменений.
В OCaml единицы компиляции являются частными случаями структур и сигнатур, и взаимоотношения между единицами легко объясняются в терминах системы модулей. Единица компиляции A состоит из двух файлов:
- файл реализации A.ml, содержащий последовательность определений, аналогичную содержанию конструкции struct…end;
- файл интерфейса A.mli, содержащий последовательность спецификаций, аналогичную содержанию конструкции sig…end.
Эти два файла вместе определяют структуру с именем A, как если бы следующее определение было введено на верхнем уровне:
module A: sig (* contents of file A.mli *) end
= struct (* contents of file A.ml *) end;;
Файлы, определяющие единицы компиляции, можно компилировать отдельно с помощью команды ocamlc -c (опция -c означает «только компилировать, не пытаться связать»); это создает файлы скомпилированного интерфейса (с расширением .cmi) и файлы скомпилированного объектного кода (с расширением .cmo). После компиляции всех единиц их файлы .cmo связываются вместе с помощью команды ocamlc. Например, следующие команды компилируют и связывают программу, состоящую из двух единиц компиляции Aux и Main:
$ ocamlc -c Aux.mli # produces aux.cmi $ ocamlc -c Aux.ml # produces aux.cmo $ ocamlc -c Main.mli # produces main.cmi $ ocamlc -c Main.ml # produces main.cmo $ ocamlc -o theprogram Aux.cmo Main.cmo
Программа ведет себя точно так же, как если бы следующие фразы были введены на верхнем уровне:
module Aux: sig (* contents of Aux.mli *) end
= struct (* contents of Aux.ml *) end;;
module Main: sig (* contents of Main.mli *) end
= struct (* contents of Main.ml *) end;;
В частности, Main может ссылаться на Aux: определения и объявления, содержащиеся в Main.ml и Main.mli, могут ссылаться на определения в Aux.ml с использованием обозначения Aux.ident, при условии, что эти определения экспортированы в Aux.mli.
Порядок, в котором файлы .cmo передаются в ocamlc во время фазы компоновки, определяет порядок появления определений модулей. Таким образом, в примере выше Aux появляется первым, и Main может ссылаться на него, но Aux не может ссылаться на Main.
Обратите внимание, что только структуры верхнего уровня могут быть сопоставлены с файлами, компилируемыми отдельно, но не функторы и не типы модулей. Однако все объекты класса модулей могут появляться как компоненты структуры, поэтому решением является размещение функтора или типа модуля внутри структуры, которая затем может быть сопоставлена с файлом.
© 1995-2022 INRIA.
https://v2.ocaml.org/releases/5.0/htmlman/moduleexamples.html
