Глава 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)
Во втором случае, когда тело локального открытие ограничено скобками, фигурными скобками или квадратными скобками, скобки локального открытие могут быть опущены. Например,
# 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/4.14/htmlman/moduleexamples.html
