Как решить, следует ли параметризовать на уровне типов или на уровне модулей при разработке модулей?

Question

Я работаю над глубоким пониманием модулей в стиле ML: я думаю, что концепция важна, и мне нравится то, что они поощряют. Я только сейчас обнаруживаю напряжение, которое может возникнуть между параметрическими типами и параметрическими модулями. Я ищу инструменты для размышления по этому вопросу, которые помогут мне принимать умные решения по проектированию при разработке моих программ.

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

(Мне жаль, что я еще не знаю достаточно, чтобы поставить этот вопрос более кратко.)

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

Готовый пример этой разницы можно найти в сравнении модулей, которые реализуют LIST подпись с теми, которые реализуют ORD_SET, Модуль List:LIST предоставляет множество полезных функций, параметризованных для любого типа. Как только мы определили или загрузили List Модуль, мы можем легко применять любые функции, которые он предоставляет, чтобы создавать, манипулировать или проверять списки любого типа. Например, если мы работаем как со строками, так и с целыми числами, мы можем использовать один и тот же модуль для создания и манипулирования значениями обоих типов:

val strList = List.@ (["a","b"], ["c","d"])
val intList = List.@ ([1,2,3,4], [5,6,7,8])

С другой стороны, если мы хотим иметь дело с упорядоченными множествами, дело обстоит иначе: упорядоченные множества требуют, чтобы отношение упорядочения сохранялось над всеми их элементами, и не может быть единой конкретной функции. compare : 'a * 'a -> order производя это отношение для каждого типа. Следовательно, нам нужен другой модуль, удовлетворяющий ORD_SET подпись для каждого типа мы хотим поместить в упорядоченные наборы. Таким образом, чтобы создать или управлять упорядоченными наборами строк и целых чисел, мы должны реализовать различные модули для каждого типа [1]:

structure IntOrdSet = BinarySetFn ( type ord_key = int
                                    val compare = Int.compare )
structure StrOrdSet = BinarySetFn ( type ord_key = string
                                    val compare = String.compare )

И тогда мы должны использовать функцию подбора из соответствующего модуля, когда мы хотим работать с данным типом:

val strSet = StrOrdSet.fromList ["a","b","c"]
val intSet = IntOrdSet.fromList [1,2,3,4,5,6]

Здесь есть довольно простой компромисс: LIST модули предоставляют функции, которые варьируются по вашему желанию, но они не могут использовать какие-либо отношения между значениями какого-либо конкретного типа; ORD_SET Модули предоставляют функции, которые обязательно ограничены типом, указанным в параметре functors, но с помощью той же самой параметризации они способны включать конкретную информацию о внутренней структуре и отношениях их целевых типов.

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

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

В общих чертах, мой вопрос заключается в следующем: когда я проектирую систему различных модулей, как я могу выяснить, следует ли проектировать модули, предоставляющие полиморфные функции или модули, созданные с использованием функторов, параметризованных по типам и значениям?

Я надеюсь проиллюстрировать дилемму и то, почему она имеет значение, на следующем примере, взятом из игрушечного проекта, над которым я работаю.

у меня есть functor PostFix (ST:STACK) : CALCULATOR_SYNTAX, Это берет реализацию структуры данных стека и создает синтаксический анализатор, который считывает конкретную нотацию постфикса ("обратная полировка") в абстрактный синтаксис (который будет оценен модулем калькулятора в нисходящем направлении) и наоборот. Теперь я использовал стандартный интерфейс стека, который обеспечивает полиморфный тип стека и количество функций для работы с ним:

signature STACK =
sig
    type 'a stack
    exception EmptyStack

    val empty : 'a stack
    val isEmpty : 'a stack -> bool

    val push : ('a * 'a stack) -> 'a stack
    val pop  : 'a stack -> 'a stack
    val top  : 'a stack -> 'a
    val popTop : 'a stack -> 'a stack * 'a
end

Это прекрасно работает и дает мне некоторую гибкость, так как я могу использовать стек на основе списка, векторный стек или что-то еще. Но, скажем, я хочу добавить простую функцию регистрации в модуль стека, чтобы каждый раз, когда элемент помещался в стек или извлекался из него, он выводил текущее состояние стека. Теперь мне понадобится fun toString : 'a -> string для типа, собранного стеком, и это, как я понимаю, не может быть включено в STACK модуль. Теперь мне нужно запечатать тип в модуль и параметризировать модуль по типу, собранному в стеке, и toString функция, которая позволит мне создать печатное представление собранного типа. Так что мне нужно что-то вроде

functor StackFn (type t
                 val toString: t -> string ) =
struct
   ...
end

и это не будет производить модуль, соответствующий STACK подпись, так как она не обеспечивает полиморфный тип. Таким образом, я должен изменить подпись, необходимую для PostFix функтор. Если у меня много других модулей, я должен также поменять их все. Это может быть неудобно, но реальная проблема заключается в том, что я больше не могу использовать свой простой, основанный на списке, или векторный STACK модули в PostFix функтор, когда я не хочу войти. Теперь, похоже, мне нужно вернуться и переписать эти модули, чтобы они также были запечатаны.

Итак, чтобы вернуться, расширить и (к счастью) закончить мой вопрос:

1. Есть ли способ указать сигнатуру модулей, созданных StackFn так что они в конечном итоге как "особые случаи" STACK?
2. В качестве альтернативы, есть ли способ написания подписи для PostFix модуль, который позволит как модули, произведенные StackFn и те, которые удовлетворяют STACK?
3. Вообще говоря, есть ли способ размышления об отношениях между модулями, которые помогут мне уловить / предвидеть подобные вещи в будущем?

(Если вы читали это далеко. Большое спасибо!)

Answer 1

Как вы обнаружили, в SML и OCaml существует противоречие между параметрическим полиморфизмом и функторами / модулями. В основном это связано с "двухъязыковой" природой модулей и отсутствием специального полиморфизма. 1ML и модульные имплициты предоставляют разные решения этой проблемы. Первый, объединяя два вида параметризма, позже позволяя при необходимости вызывать некий специальный полиморфизм.

Вернемся к практическим соображениям. С помощью функторов довольно легко (но многословно / досадно) мономорфизировать данную структуру данных. Вот пример (в OCaml). При этом вы все еще можете писать общие реализации и специализировать их позже (предоставляя функцию печати).

module type POLYSTACK = sig
  type 'a stack
  exception EmptyStack

  val empty : 'a stack
  val isEmpty : 'a stack -> bool

  val push : ('a * 'a stack) -> 'a stack
  val pop  : 'a stack -> 'a stack
  val top  : 'a stack -> 'a
  val popTop : 'a stack -> 'a stack * 'a
  val toString : ('a -> string) -> 'a stack -> string
end

module type STACK = sig
  type elt
  type t
  exception EmptyStack

  val empty : t
  val isEmpty : t -> bool

  val push : (elt * t) -> t
  val pop  : t -> t
  val top  : t -> elt
  val popTop : t -> t * elt
  val toString : t -> string
end

module type PRINTABLE = sig
  type t
  val toString : t -> string
end

module Make (E : PRINTABLE) (S : POLYSTACK)
  : STACK with type elt = E.t and type t = E.t S.stack
= struct
  type elt = E.t
  type t = E.t S.stack
  include S
  let toString = S.toString E.toString
end

module AddLogging (S : STACK)
  : STACK with type elt = S.elt and type t = S.t
= struct
  include S
  let push (x, s) =
    let s' = S.push (x, s) in print_string (toString s') ; s'
end