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

Главная цель модулей - сгруппировать связанные определения (например, определения типа данных и операций, допустимых для него) и обеспечить разумную схему именования. Подобная группа называется структурой и задается блоком 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.

Сигнатуры - это интерфейсы для структур. Они указывают, какие элементы структуры с какими типами доступны извне. Поэтому сигнатуры могут использоваться для скрытия некоторых компонентов структуры (например, локальных функций) или для ограничения типов экспортируемых компонентов. Сигнатура ниже включает три оператора очереди по приоритету 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;;
			

Функторы - это "функции" для структур. Они используются для параметризации структур: структура A, параметризованная структурой B является функтором F с формальным аргументом B (соответвующим сигнатуре B), возвращающим непосредственно структуру А. Функтор F может быть применен к различным реализациям B типа B₁...B_n, вернув в результате структуры А₁...А_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

Как и в примере с 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.

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

В 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.

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

• Структура
• Сигнатуры
• Функторы
• Функторы и абстрагирование от типа
• Модули и раздельная компиляция