Глава 12. Расширения языка

5 Функции, зависящие от модулей, и модули первого класса

• 5.1 Введение
• 5.2 Справочник

(Модули первого класса появились в OCaml 3.12; синтаксис шаблонов и вывод типов пакетов — в 4.00; структурное сравнение типов пакетов — в 4.02; начиная с 4.05 требуется меньше скобок.
Функции, зависящие от модулей, появились в 5.5.)

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

5.1 Введение

Функции, зависящие от модулей: функции с параметром-модулем

Можно написать функцию sort0, которая сортирует элементы, добавляя их в упорядоченное множество, а затем считывая их в порядке сортировки:

let sort0 (type a) cmp li =
  let module M = struct type t = a let compare = cmp end in
  let module MSet = Stdlib.Set.Make(M) in
  MSet.elements (List.fold_right MSet.add li MSet.empty)

let example = sort0 Int.compare [3; 1; 2]

val sort0 : ('a -> 'a -> int) -> 'a list -> 'a list = 
val example : int list = [1; 2; 3]

С помощью функций, зависящих от модулей, функцию sort также можно выразить как функцию с параметром-модулем упорядоченного множества. Это позволяет вызывающему коду выбирать реализацию упорядоченного множества, которая может быть специализирована для конкретного типа; например, множества целых чисел можно представлять битовыми наборами или компактными представлениями плотных интервалов.

let sort (module MSet : Set.S) li =
  MSet.elements (List.fold_right MSet.add li MSet.empty)

val sort : (module MSet : Set.S) -> MSet.elt list -> MSet.elt list = 

В объявлении sort используется синтаксис шаблона (module M : S), позволяющий передавать функциям в качестве параметров модули вместо обычных значений. Мы называем sort функцией, зависящей от модуля, поскольку в её типе (module MSet : Set.S) -> MSet.elt list -> MSet.elt list параметр-модуль встречается в правой части (типе возвращаемого значения) стрелки (module MSet : Set.S) -> ... через вхождения типа MSet.elt.

Чтобы применить функцию sort, мы используем конструкцию (module M) для передачи аргумента или (module M : S), чтобы явно указать предполагаемую сигнатуру.

module ISetIncr = Set.Make(Int)
module ISetDecr =
  Set.Make(struct
    type t = int
    let compare i1 i2 = Int.compare i2 i1
  end)

# let example = sort (module ISetIncr) [3; 1; 2];;

val example : ISetIncr.elt list = [1; 2; 3]

# let example = sort (module ISetDecr) [3; 1; 2];;

val example : ISetDecr.elt list = [3; 2; 1]

Это лёгкая альтернатива функторам. Действительно, функцию sort можно также выразить с помощью функтора Sort:

module Sort (MSet : Set.S) = struct
  let f li =
    MSet.elements (List.fold_right MSet.add li MSet.empty)
end

module Sort :
  (MSet : Set.S) -> sig val f : MSet.elt list -> MSet.elt list end

# let module S = Sort(ISetDecr) in S.f [3; 1; 2];;

- : ISetDecr.elt list = [3; 2; 1]

Пример использования: абстрагирование алгебраических структур

Функции, зависящие от модулей, позволяют удобно писать код, параметрический по семействам типов, например по любой монаде.

module type Monad = sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end

let mapM (module M : Monad) (f : 'a -> 'b M.t) (li : 'a list) : 'b list M.t =
  let ( let* ) = M.bind in
  let rec loop = function
  | [] -> M.return []
  | x::xs ->
    let* y = f x in
    let* ys = loop xs in
    M.return (y :: ys)
  in loop li

(* Example use-case: a map on the Result monad *)
let map_result (type e)
: ('a -> ('b, e) result) -> 'a list -> ('b list, e) result
= let module R = struct
    type 'a t = ('a, e) result
    let return = Result.ok
    let bind = Result.bind
  end in mapM (module R)

Модули первого класса

В применении функции sort (module ISetIncr) из нашего примера выше аргумент-модуль является статическим: он известен во время компиляции.

Модули первого класса позволяют создавать динамические значения, представляющие модули, выбор которых зависит от вычислений во время выполнения. Если M — модуль с сигнатурой S, то (module M : S) — это выражение типа (module S); говорят, что оно «упаковывает» модуль M в значение.

Типичный пример использования модулей первого класса — выбор во время выполнения одной из нескольких реализаций сигнатуры. Каждая реализация представляет собой структуру, которую можно упаковать в модуль первого класса, а затем сохранить в структуре данных, например в хеш-таблице:

type picture = …
module type DEVICE = sig
  val draw : picture -> unit
  …
end
let devices : (string, (module DEVICE)) Hashtbl.t = Hashtbl.create 17

module SVG = struct … end
let _ = Hashtbl.add devices "SVG" (module SVG : DEVICE)

module PDF = struct … end
let _ = Hashtbl.add devices "PDF" (module PDF : DEVICE)

Затем модульное выражение (val e : S) может распаковать значение упакованного модуля (e : (module S)) обратно в модуль. В нашем примере одну из реализаций можно выбрать на основании аргументов командной строки:

let parse_cmdline () = …
module Device =
  (val (let device_name = parse_cmdline () in
        try Hashtbl.find devices device_name
        with Not_found ->
          Printf.eprintf "Unknown device %s\n" device_name;
          exit 2)
   : DEVICE)

Кроме того, выбор можно выполнить внутри функции:

let draw_using_device device_name picture =
  let module Device =
    (val (Hashtbl.find devices device_name) : DEVICE)
  in
  Device.draw picture

(* or, equivalently *)
let draw_using_device device_name picture =
  let (module Device : DEVICE) = Hashtbl.find devices device_name in
  Device.draw picture

Ограничение: выбор модуля во время выполнения

Для функций, зависящих от модулей, fun (module A : S) -> ..., существует ограничение: если тип тела функции (то есть ...) зависит от аргумента-модуля A, то такой функции разрешено передавать только статические аргументы-модули вида (module M : S), а не произвольные выражения типа (module S). Если тип тела не содержит упоминаний A или проверяющий типы может устранить эти упоминания A, подставив равенства типов (например, когда A.t равен int), такого ограничения нет.

Функция sort из пункта 12.5.1 — это такая функция, зависящая от модуля: её тип — (module MSet : Set.S) -> MSet.elt list -> MSet.elt list, где модуль MSet используется справа от стрелки (module MSet : Set.S) -> .... Следующий пример отклоняется:

let sort_order = `Decr

let wrong =
  sort
    (match sort_order with
     | `Incr -> (module ISetIncr)
     | `Decr -> (module ISetDecr))
    [2; 4]

Error: This expression has type
         (module MSet : Set.S) -> MSet.elt list -> MSet.elt list
       but an expression was expected of type (module Set.S) -> 'a
       The module MSet would escape its scope
This function is module-dependent. The dependency is preserved
when the function is passed a static module argument (module M : S)
or (module M). Its argument here is not static, so the type-checker
tried instead to change the function type to be non-dependent.

В некоторых случаях, в том числе в этом примере, код можно переписать так, чтобы снова использовать статический аргумент-модуль:

let okay =
  let m : (module Set.S with type elt = int) =
    match sort_order with
    | `Incr -> (module ISetIncr)
    | `Decr -> (module ISetDecr)
  in
  let module MSet = (val m) in
  sort (module MSet) [2; 4]

val okay : int list = [4; 2]

Обратите внимание: MSet.elt не может встречаться в типе okay, так как модуль MSet определён только локально. В этом примере тип возвращаемого значения sort действительно содержит MSet.elt, но этот тип равен int, поэтому его можно упростить.

Наконец, зависимость можно устранить и из определения sort, заменив сигнатуру аргумента Set.S сигнатурой Set.S with type elt = a, в которой используется локально абстрактный тип (type a) (см. 12.4). До появления в языке функций, зависящих от модулей, это был единственный доступный подход, но он менее гибок, поскольку требует изменить определение функции, а не только место её вызова.

let sort_nondep (type a) (module MSet : Set.S with type elt = a) (li : a list) =
  MSet.elements (List.fold_right MSet.add li MSet.empty)

let also_okay =
  sort_nondep
    (match sort_order with
     | `Incr -> (module ISetIncr)
     | `Decr -> (module ISetDecr))
    [2; 4]

val sort_nondep :
  (module MSet : Set.S with type elt = 'a) -> 'a list -> MSet.elt list =
  
val also_okay : ISetIncr.elt list = [4; 2]

Обратите внимание: зависимости таким способом, с помощью (type a), можно устранять только для непараметризованных типов, таких как elt, но не для параметризованных типов, таких как 'a t; соответствующей абстракции (type 'a t) не существует. Это невозможно применить к рассмотренному выше примеру с mapM, который зависит от модуля, содержащего параметризованный тип 'a M.t, а значит, не может получать динамически выбираемые аргументы-модули.

Ограничение: применение функций с несколькими аргументами

Следующий пример, в котором sort — рассмотренная ранее функция, зависящая от модуля, завершается ошибкой:

let sort (module MSet : Set.S) li =
  MSet.elements (List.fold_right MSet.add li MSet.empty)

let wrong = Fun.id sort (module ISetIncr) [2; 3]

Error: The value sort has type
         (module MSet : Set.S) -> MSet.elt list -> MSet.elt list
       but an expression was expected of type (module Set.S) -> 'a -> 'b
       The module MSet would escape its scope

Проблема связана с тонкостями проверки типов при применении функций с несколькими аргументами. Это выражение проверяется как Fun.id, которой передаются три параметра; для разрешения применения модуля используется только тип Fun.id (а не его аргументы), поэтому на этом этапе тип функции, зависящей от модуля, неизвестен.

Исправить пример можно, сначала применив Fun.id sort, а затем передав аргумент-модуль отдельным применением. Тогда для проверки применения модуля будет использован тип Fun.id sort, зависящий от модуля. Для этого достаточно добавить скобки:

let fixed = (Fun.id sort) (module ISetIncr) [2; 3]

val fixed : ISetIncr.elt list = [2; 3]

(Явное указание типа Fun.id как типа функции, зависящей от модуля, также сработает.)

Совместимость

До OCaml 5.5 функции, зависящие от модулей, не поддерживались. Можно было использовать модули первого класса, но функции, принимающие модуль первого класса, не могли зависеть от него, поэтому часто применялось обходное решение с (type a).

5.2 Справочник

Выражение ( module module-expr : package-type ) преобразует модуль (структуру или функтор), обозначенный модульным выражением module-expr, в значение основного языка, упаковывающее этот модуль. Тип этого значения основного языка — ( module package-type ). Аннотацию package-type можно опустить, если её можно вывести из контекста.

И наоборот, модульное выражение ( val expr : package-type ) вычисляет выражение основного языка expr и получает значение, тип которого должен быть module package-type, после чего извлекает модуль, заключённый в этом значении. Здесь также можно опустить package-type, если тип expr известен. Если модульное выражение уже заключено в скобки, как аргументы функторов, дополнительные скобки не нужны: Map.Make(val key).

Шаблон ( module module-name : package-type ) сопоставляется с пакетом типа package-type и связывает его с module-name. Его нельзя использовать в определениях let верхнего уровня. Функция, параметр которой имеет в точности такой шаблон, может зависеть от модуля. Здесь также можно опустить package-type, если его можно вывести из охватывающего шаблона.

Синтаксический класс package-type, используемый в выражении типа ( module package-type ), в выражении типа ( module module-name : package-type ) -> typexpr и в формах с аннотациями обозначает подмножество типов модулей. Это подмножество состоит из именованных типов модулей с необязательными ограничениями ограниченного вида: можно указывать только непараметризованные типы.

При проверке типов (начиная с OCaml 4.02) типы пакетов сравниваются с помощью структурного сравнения типов модулей.

При проверке типов мы также считаем ( module module-name : package-type ) -> typexpr и ( module package-type ) -> typexpr идентичными, если module-name можно удалить из typexpr.

В общем случае модульное выражение ( val expr : package-type ) нельзя использовать в теле функтора, так как в сочетании с аппликативными функторами это могло бы привести к несогласованности. Начиная с OCaml 4.02 это ограничение смягчено двумя способами: если package-type не содержит номинальных объявлений типов (то есть типов с собственной идентичностью), такое выражение можно использовать где угодно; даже если оно содержит такие типы, его можно использовать в теле генеративного функтора, описанного в разделе 12.15. Кроме того, его можно использовать где угодно в контексте локального связывания модуля let module module-name = ( val expr₁ : package-type ) in expr₂.