在设计模块时如何决定是在类型级别还是模块级别进行参数化？

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