# Глава 2. Система модулей

В этой главе содержится введение в систему модулей Objective Caml.

## 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
        and '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`.

## 2.2 Сигнатуры

Сигнатуры - это интерфейсы структур. Они указывают, какие элементы структуры с какими типами доступны извне. Поэтому сигнатуры могут использоваться для скрытия некоторых компонентов структуры (например, локальных функций) или для ограничения типов экспортируемых компонентов. Сигнатура ниже включает три оператора очереди по приоритету `empty`, `insert` и `extract`, но скрывает вспомогательную функцию `remove_top`. Кроме того, тип `queue` становится абстрактным (конкретный тип не указан):

    # 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;;

    module type PRIOQUEUE =
      sig
        type priority = int
        and '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`: функция `remove_top` недоступна, а конкретный тип очередей по приоритету скрыт.

    #module AbstractPrioQueue = (PrioQueue : PRIOQUEUE);;

    module AbstractPrioQueue : PRIOQUEUE

    #AbstractPrioQueue.remove_top;;

    Unbound value AbstractPrioQueue.remove_top

    #AbstractPrioQueue.insert AbstractPrioQueue.empty 1 "hello";;

    - : string AbstractPrioQueue.queue = <abstr>

Подобные ограничения можно наложить и при определении структуры:

            module PrioQueue = (struct ... end : PRIOQUEUE);;

Альтернативный синтаксис:

            module PrioQueue : PRIOQUEUE = struct ... end;;

## 2.3 Функторы

Функторы - это "функции" для структур. Они используются для параметризации структур: структура A, параметризованная структурой B является функтором F с формальным аргументом B (соответвующим сигнатуре B), возвращающим непосредственно структуру А. Функтор F может быть применен к различным реализациям B типа B1...Bn, вернув в результате структуры А1...Аn, соответственно.

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

                #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 уже есть в s *)
                | Less    -> x :: s    (* x меньше любого элемента 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 находится в s *)
                 | Less    -> false    (* x меньше любого элемента s *)
                 | Greater -> member x tl
         end;;

    module Set :
      functor (Elt : ORDERED_TYPE) ->
        sig
          type element = Elt.t
          and 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
        and 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      (* конкретный тип *)
           type set                  (* абстрактный тип *)
           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
          and 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
        and 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 = <abstr>

Может показаться, что ограничение типа получится элегантнее, если именовать сигнатуру структуры, возвращаемой функтором, а затем использовать эту сигнатуру в ограничении:

    #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
        and 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
        and set = WrongSet(OrderedString).set
        val empty : set
        val add : element -> set -> set
        val member : element -> set -> bool
      end

    #WrongStringSet.add "gee" WrongStringSet.empty;;

    This expression has type string but is here used with type
      WrongStringSet.element = WrongSet(OrderedString).element

Дело в том, что в модуле `SET` тип `element` определен как абстрактный, поэтому равенство типов между `element` в результате функтора и `t` не соблюдается. Следовательно, `WrongStringSet.element` и `string` имеют разные типы, а потому операции `WrongStringSet` не применимы к строкам. Поэтому тип `element` в сигнатуре `SET` должен быть объявлен как `Elt.t`, что, увы, невозможно, поскольку `SET` объявлен в контексте, где `Elt` не существует. Подобные проблемы в Objective Caml обходятся с помощью конструкции `with type`, позволяющей добавить в сигнатуру дополнительные условия равенства типов.

    #module AbstractSet =
       (Set : functor(Elt: ORDERED_TYPE) -> (SET with type element = Elt.t));;

    module AbstractSet :
      functor (Elt : ORDERED_TYPE) ->
        sig
          type element = Elt.t
          and set
          val empty : set
          val add : element -> set -> set
          val member : element -> set -> bool
        end

Как и в случае простых структур, для определения функторов и ограничения их результатов существует альтернативный синтаксис:

    module AbstractSet(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 s1) (String.lowercase 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
        and set = AbstractSet(NoCaseString).set
        val empty : set
        val add : element -> set -> set
        val member : element -> set -> bool
      end

    #NoCaseStringSet.add "FOO" AbstractStringSet.empty;;

    This expression has type
      AbstractStringSet.set = AbstractSet(OrderedString).set
    but is here used with type
      NoCaseStringSet.set = AbstractSet(NoCaseString).set

Типы `AbstractStringSet.set` и `NoCaseStringSet.set` не совместимы, и их значения не равны. Это правильное поведение: несмотря на то, что оба содержат элементы одного типа (строки), в них используются разные функции сортировки, соотвественно, операции должны поддерживать разные инварианты. Использование операций `AbstractStringSet` для значений типа `NoCaseStringSet.set` приведет к неправильным результатам и созданию списков, нарушающих инварианты `NoCaseStringSet`.

## 2.5 Модули и раздельная компиляция

До сих пор о модулях рассказывалось в контексте интерактивной системы. Однако особенно полезны они в больших программах, предназначенных для пакетной компиляции. В подобных случаях практически необходимо разделять исходный текст на несколько файлов (единиц компиляции), и компилировать их раздельно, чтобы после внесения изменений свести повторную компиляцию к минимуму.

В Objective Caml единицы компиляции - особый случай структур и сигнатур, причем отношения между этими единицами легко описываются в терминах системы модулей. Единица компиляции `a` включает в себя два файла:

- Реализация `a.ml`, включающая определения, как в блоке `struct...end`.

- Интерфейс `a.mli`, содержащий спецификации, как в блоке `sig...end`.

Оба файла описывают структуру `А` (то же имя, что и `a`, но с первой заглавной буквой), как если бы было введено следующее определение:

    module A: sig (* содержимое файла a.mli *) end
          = struct (* содержимое файла a.ml *) end;;

Файлы, составляющие единицу, компилируются отдельно, командой `ocamlc -c` (ключ `-c` означает "компиляция без компоновки"), что дает файлы с расширениями `.cmi` для интерфейса и `.cmo` для объектного кода. По окончании единиц объектные файлы компонуются командой `ocamlc`. Следующие команды компилируют и компонуют программу из единиц `aux` и `main`.

    $ ocamlc -c aux.mli                     # создает aux.cmi
    $ ocamlc -c aux.ml                      # создает aux.cmo
    $ ocamlc -c main.mli                    # создает main.cmi
    $ ocamlc -c main.ml                     # создает 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` могут использовать определения и объявления из `aux.ml` c помощью нотации `Aux.ident`, если соответствующие определения экспортируются в файле `aux.mli`.

Объектные файлы передаются компилятору в порядке следования определений модуля. В примере выше `Aux` идет первым, поэтому `Main` может ссылаться на него, но `Aux` не может ссылаться на `Main`.

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