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

Question

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

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

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

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

Готовый пример этого различия можно найти в сравнении модулей, которые реализуют LIST подписи с теми, которые реализуют ORD_SET. Модуль 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 обеспечивают функции, которые обязательно ограничены типом, указанным в параметре функтора , но через ту же параметризацию они способны , включающие в себя специфическую информацию о внутренней структуре и отношениях их целевых типов от .

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

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

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

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

У меня есть 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. Если у меня есть много других модулей, я должен также изменить . Это может быть неудобно, но реальная проблема заключается в том, что I больше не может использовать мои простые на основе списка или на основе вектора модули STACK в функторе PostFix, когда я не хочу вести журнал. Теперь, кажется, я должен вернуться и переписать эти модули, чтобы иметь закрытый тип.

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

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

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

Answer 1

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

Назад к практическим соображениям. С функторами довольно легко (но многословно/досадно) мономорфозировать заданную структуру данных. Вот пример (в 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