设计模块时，如何决定是在类型级别还是在模块级别进行参数化? [英] How to decide whether to parameterize on the type-level or the module-level when designing modules?

问题描述

我正在努力深入理解ML样式的模块:我认为 概念很重要，我喜欢他们鼓励的那种思维.我只是 现在发现参数类型和 参数模块.我正在寻找思考问题的工具 在构建程序时帮助我做出明智的设计决策.

I'm working towards a deep understanding of ML-style modules: I think the concept is important and I love the kind of thinking they encourage. I am just now discovering the tension that can arise between parametric types and parametric modules. I am seeking tools for thinking about the matter that will help me make smart design decisions as I build up my programs.

第一拳，我将尝试概括地描述我的问题.然后，我将提供 我正在研究的学习项目中的具体示例.最后，我会 重新审视一般性问题，以便将其理解为一个重点.

Fist I will try to describe my question in general. Then I will provide a concrete example from a learning project I am working on. Finally, I will revisit the general question in order to draw it to a point.

(很抱歉，我还不足够清楚地提出这个问题.)

(I'm sorry that I don't yet know enough to pose this question more succinctly.)

总的来说，我发现的张力是:功能是最重要的 当我们为他们提供参数化参数时，它具有灵活性，并且可以进行最大程度的重用 类型签名(如果适用).但是，模块是最灵活和开放的 当我们密封内部的函数的参数化时，最大程度地重用 模块，而是以给定类型对整个模块进行参数化.

In general terms, the tension I've discovered is this: functions are most flexible, and open to the widest reuse, when we provide them with parametric type signatures (where appropriate). However, modules are most flexible and open to the widest reuse when we seal the parameterization of functions inside the module, and instead parameterize the entire module on a given type.

可以在比较模块中找到这种差异的现成示例， 使用那些实现了 LIST 签名的方法 ORD_SET .模块List:LIST提供了许多有用的功能， 在任何类型上进行参数化.定义或加载List模块后，我们可以 随时应用其提供的任何功能来构造，操纵或 检查任何类型的列表.例如，如果我们同时使用字符串和 整数，我们可以使用一个相同的模块来构造和操作 两种类型的值:

A ready example of this difference can be found in comparing modules that implement the LIST signature with those that implement ORD_SET. A module List:LIST provides a bunch of useful functions, parameterized on any type. Once we've defined or loaded a List module, we can readily apply any of the functions it provides to construct, manipulate, or examine lists of any type. E.g., if we are working with both strings and integers, we can use one and the same module to construct and manipulate values of both types:

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]:

On the other hand, if we want to deal with ordered sets, matters are different: ordered sets require that an ordering relation hold over all of their elements, and there can be no single concrete function compare : 'a * 'a -> order producing that relation for every type. Consequently, we require a different module satisfying the ORD_SET signature for each type we wish to put into ordered sets. Thus, in order to construct or manipulate ordered sets of strings and integers, we must implement different modules for each type[1]:

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

然后我们必须使用适当模块中的拟合函数 希望对给定类型进行操作:

And we must then use the fitting function from the appropriate module when we wish to operate on a given type:

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

这里有一个非常简单的权衡:LIST模块提供功能 您可以选择任何类型的范围，但它们无法利用任何关系 介于任何特定类型的值之间； ORD_SET模块提供 必须限制在函子中提供的类型的函数 参数，但是通过相同的参数设置，他们可以 纳入有关内部结构和关系的具体信息 他们的目标类型.

There is a pretty straightforward tradeoff here: LIST modules provide functions that range over any type you please, but they cannot take advantage of any relations that hold between the values of any particular type; ORD_SET modules provide functions that are necessarily constrained to the type supplied in the functors parameter, but through that same parameterization, they are capable of incorporating specific information about the internal structure and relations of their target types.

很容易想到我们想要设计替代家庭的情况 列表模块，使用函子将类型和其他值参数化为 提供具有更复杂结构的类似列表的数据类型:例如，指定 排序列表的数据类型，或使用自平衡二进制数表示列表的数据类型 搜索树.

It is easy to imagine cases where we would want to design an alternative family of list modules, using functors to parameterize types and other values to provide list-like data types with a more complicated structure: e.g., to specify a data type for ordered list, or to represent lists using self-balancing binary search trees.

在创建模块时，我认为很容易识别何时 能够提供多态函数，以及何时需要对其进行参数化 在某些类型上.对我来说，似乎更困难的是找出哪种 在进行后续工作时，您应该依赖的模块.

When creating a module, I think it is also fairly easy to recognize when it will be able to provided polymorphic functions and when it will need to be parameterized on some type(s). What seems more difficult, to me, is figuring out which kind of modules you should depend on when working on something further down stream.

总的来说，我的问题是:当我设计一个 各种相关的模块，我如何确定是否围绕模块进行设计 提供使用函子生成的多态函数或模块 参数化类型和值?

In general terms, my question is this: when I am designing a system of variously related modules, how can I figure out whether to design around modules providing polymorphic functions or modules generated using functors parameterized on types and values?

我希望通过以下示例来说明这一难题及其重要性: 取自我正在从事的玩具项目.

I hope to illustrate the dilemma and why it matters with the following example, taken from a toy project I am working on.

我有一个functor PostFix (ST:STACK) : CALCULATOR_SYNTAX.这需要 堆栈数据结构的实现，并生成读取的解析器 将具体的后缀(反向修饰")符号转换为抽象语法( 由下游的计算器模块评估)，反之亦然.现在，我曾经 使用提供多态堆栈类型的标准堆栈接口，以及 要对其进行操作的功能数量:

I have a functor PostFix (ST:STACK) : CALCULATOR_SYNTAX. This takes an implementation of a stack data structure and produces a parser that reads concrete postfix ("reverse polish") notation into an abstract syntax (to be evaluated by a calculator module down stream), and vice-versa. Now, I had been using a standard stack interface that provides a polymorphic stack type and number of functions to operate on it:

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函数使我产生一个 所收集类型的可打印表示形式.所以我需要类似的东西

This works fine, and gives me some flexibility, as I can use a list-based stack or vector-based stack, or whatever. But, say I want to add a simple logging function to the stack module, so that every time an element is pushed to, or popped from, the stack, it prints out the current state of the stack. Now I will need a fun toString : 'a -> string for the type collected by the stack, and this, as I understand, cannot be incorporated into the STACK module. Now I need to seal the type into the module, and parameterize the module over the type collected in the stack and a toString function that will let me produce a printable representation of the collected type. So I need something like

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

，这将不会生成与STACK签名匹配的模块，因为它 不提供多态类型.因此，我必须更改所需的签名 用于PostFix仿函数.如果我还有很多其他模块，则必须更改 所有这些都一样.那可能不方便，但真正的问题是我 不能再在 PostFix仿函数，当我不想想要记录日志时.现在，看来，我必须回去 并将这些模块也重写为密封类型.

and this will not produce a module matching the STACK signature, since it doesn't provide a polymorphic type. Thus, I must change the signature required for the PostFix functor. If I have a lot of other modules, I have to change all of them as well. That could be inconvenient, but the real problem is that I can no longer use my simple list-based, or vector-based STACK modules in the PostFix functor when I don't want logging. Now, it seems, I have to go back and rewrite those modules to have a sealed type as well.

因此，回到，扩展并(愉快地)完成我的问题:

So to return to, expand upon, and (mercifully) finish my question:

1. 是否有某种方法可以指定由以下人员产生的模块的签名? StackFn，以便它们最终成为STACK的特殊情况"?
或者，是否可以为PostFix模块编写签名? 既可以使用StackFn生成的模块，也可以使用 满足STACK?
2. 一般来说，是否有一种思考方式 可以帮助我在将来捕捉/预料到这类事情的模块?

1. Is there some way of specifying the signature of the modules produced by StackFn so that they'll end up as "special cases" of STACK?
2. Alternatively, is there a way of writing a signature for the PostFix module that would allow for both the modules produced by StackFn and those that satisfy STACK?
3. Generally speaking, is there a way of thinking about the relation between modules that would help me catch/anticipate this kind of thing in the future?

(如果您已经读了那么多.非常感谢！)

(If you've read this far. Thank you very much!)

推荐答案

您发现，在SML和OCaml中，参数多态与函子/模块之间存在紧张关系.这主要是由于模块的两种语言"性质以及缺乏即席多态性所致. 1ML 和模块化隐式都为该问题提供了不同的解决方案.第一种是通过统一两种参数，第二种是在需要时允许产生一些特殊的多态性.

As you discovered, there is a tension between parametric polymorphism and functors/module in SML and OCaml. This is mostly due to the "two language" nature of modules and to the lack of ad hoc polymorphism. 1ML and modular implicits both provide different solutions to that problem. The first by unifying back the two kind of parametrism, the later by allowing to sparkle some ad-hoc polymorphism when needed.

回到实际考虑.使用函子，可以很容易地(但是冗长/讨厌)使给定的数据结构单一化.这是一个示例(在OCaml中).这样，您仍然可以编写通用的实现，并在以后(通过提供打印功能)对它们进行专门化.

Back to practical considerations. With functors, it's fairly easy (but verbose/annoying) to monomorphise a given datastructure. Here is an example (in OCaml). With this, you can still write generic implementations and specialize them later on (by providing a printing function).

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

这篇关于设计模块时，如何决定是在类型级别还是在模块级别进行参数化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！