algebra - 什么是 “multisorted algebra”，如何使用它来解决 “real problems”？

Question

显然，Alexander Stepanov在interview中声明了以下内容:

“I find OOP [object-oriented programming] technically unsound. It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras - families of interfaces that span multiple types.” [Emphasis added.]

暂时忽略他关于OOP的陈述，什么是“多元代数”，超出他的简洁定义，您能否给出一个实际的使用它们的示例(以您选择的语言)？

Answer 1

我相信他是在谈论泛型编程(he coined the term)，无论是在此有关STL的讨论中，还是在某种意义上说“总体上”:

针对一种描述可能适合的东西的接口(interface)进行编程所有(并希望是几种)类型(因此是多分类的)，...

... 提供了，他们具有的某些属性，通常涉及对该类型的元素进行某些操作的性质(因此称为代数)。

要执行(1)，您需要有一种方法来指定一个将类型作为 参数的程序，即多态，并且要做(2)，您需要一种方法来表明您 以及都希望该类型进行 特定操作(并且，如果可以表示的话，可以使用 属性)。实际上，您是通过程序所处理的数据的结构来对程序进行参数化的。范式在某些地方被称为有界多态性，即数据类型通用编程，它反射(reflect)了语言对如何实现该想法有不同的看法，因此上面用斜体表示。

对于C++，似乎(至少在Stepanov中)这与模板相对应(尽管有关如何做到最好的are still evolving的想法)。

对于OO语言(通用Java，C#)，通常使用子类型范围(“bounded wildcards” ...)来表示对类型参数的约束。

对于Haskell或Scala，您分别(并且同样)具有类型类或隐式类型。

ML语言家族更喜欢使用模块来完成此任务。

请注意，许多proof assistants(可以将“诚实”属性表示为类型)已经发展出一种类型类别的 flavor :Isabelle，Coq，Matita就是此类示例

请注意，Stepanov只是共同编写了 an entire book，从而对库进行了详尽的开发，该库体现了 和(我认为)是什么意思。因此，如果您想使用C++编写示例，那么绝对是您应该去的地方。还请注意，这比 coding against an interface, rather than an object现在常见的建议要发展得多。

通过“实际例子”，我不知道您是说“如何”或“为什么”使用它。为了快速给出“为什么”的答案，通用性很好，因为有点像常规的多态性，它允许您重用代码。但是，更重要的是:

必须与 一起使用的

多态代码，每种类型通常都无法做任何有趣的事情，而具有受限制的接口(interface)可以使您编写更丰富的程序

通过指定该接口(interface)如何适合您的某些数据，您可以通过一种类型安全的方式选择仅适合您需求的那些元素。例如，您可能知道缩减运算符(Python和Hadoop的reduce，一堆功能语言的fold)仅在您应用缩减功能的顺序无关紧要(+，x，min， and有效，但设置差异无效)。如果您有“配备了关联运算的类型”的概念，那么您将可以对其进行并行化简。

由通用性引起的任何开销都在编译时发生。例如，模板是传说中的快速

如果您已经看过一些通用Java，请看一下 Comparable通用接口(interface)。它只定义了一个运算，但是它所达成的契约虽然很基本，但却具有代数风格。我引用:

For the mathematically inclined, the relation that defines the natural ordering on a given class C is:

  {(x, y) such that x.compareTo((Object)y) <= 0}.

The quotient for this total order is:

  {(x, y) such that x.compareTo((Object)y) == 0}.

It follows immediately from the contract for compareTo that the quotient is an equivalence relation on C, > and that the natural ordering is a total order on C.

现在，我可以编写一个选择最小值 的方法，并将其用于适合此接口(interface)的任何类型:

 public static <T extends Comparable<T>> T min (T x, T y) {
   if (x.compare(y) < 0) x; else y;
 }

自然，由于编程构造实现该概念的方式千差万别，因此您在可用性和表达性方面所获得的 yield 也将有所不同。也许您不应该仅通过C++或Java之类的OO语言来判断数据泛型编程，但是我已经写了太多文章，从模块归属或类型类的自动实例生成开始。