32

显然，亚历山大·斯捷潘诺夫在接受采访时表示：

“我发现 OOP [面向对象编程] 在技术上是不健全的。它试图根据单一类型的不同接口来分解世界。要处理真正的问题，您需要多排序代数 - 跨越多种类型的接口系列。” [强调补充。]

暂时忽略他关于 OOP 的陈述，什么是“多分类代数”，超出了他的简洁定义，您能否举一个实际示例来说明它们是如何使用的（以您选择的语言）？

4

3 回答 3

23

我相信他在谈论泛型编程（他创造了术语），无论是在这个关于 STL 的讨论的上下文中，还是在以下意义上的“一般”：

  1. 针对一种接口进行编程，该接口描述了可以适合所有（希望是几种）类型（因此是多排序的）的东西，......
  2. ...只要它们具有某些属性，通常是关于对该类型元素的某些操作的性质（因此是代数）。

要做到（1），你需要有一种方法来指定一个将类型作为参数的程序，即多态性，而要做到（2），你需要一种方法来说明你也希望该类型携带特定的操作（并且，如果您可以表达它们，properties）。实际上，您正在通过程序操作的数据结构对程序进行参数化。该范式在某些地方被称为有界多态性、数据类型泛型编程……这反映了语言对于如何实现该想法有不同的概念——因此上面用斜体字“排序”。

  • 对于 C++，似乎——至少在 Stepanov 看来——这对应于模板（尽管关于如何最好地做到这一点的想法仍在不断发展）。
  • 对于 OO 语言（通用 Java、C#），类型参数的约束通常使用子类型边界（“有界通配符”...）来表示。
  • 对于 Haskell 或 Scala，您有（分别和类似的）类型 classes或implicits。
  • ML 系列语言更喜欢使用模块来实现这一点。
  • 请注意，许多证明助手（可以将 'honest-to-god'属性表示为类型）已经开发出一种类型类的风格：Isabelle、Coq、Matita 就是这样的例子

请注意，Stepanov 刚刚与人合着了一整本书，详尽地介绍了一个图书馆的发展，而这正是体现了（我认为）他的意思。因此，如果您想要C++中的示例，这绝对是您应该看的地方。还要注意，这比现在常见的针对接口而不是对象编码的建议要进化得多。

通过“实际示例”，我不知道您的意思是“如何”或“为什么”使用它。为了对“为什么”给出一个讽刺的快速回答，通用性很好，因为有点像普通的多态性，它可以让你重用代码。但是，更重要的是：

  1. 必须与每种单一类型一起工作的多态代码通常无法做任何有趣的事情，而使用受约束的接口可以让您编写更丰富的程序

  2. 通过指定该接口如何适合您的某些数据，您可以使用类型安全的方式来选择适合您需要的元素。例如，您可能知道归约运算符（reducePython 和 Hadoopfold中的一堆函数式语言）只有在应用归约函数的顺序无关紧要（+, x, min,and有效，但设置差异时）才可并行化没有）。如果您有“配备关联操作的类型”的概念，您就会知道您将能够在其上调用并行归约。

  3. 泛型产生的任何开销都发生在编译时。例如，模板速度惊人

如果您看过一些泛型 Java，请看一下Comparable泛型接口。它只定义了一种操作，但它所产生的契约虽然很基本，但却非常具有代数的味道。我引用：

对于数学倾向，定义给定类 C 的自然排序的关系是：

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

这个总订单的商是：

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

从 compareTo 的契约可以直接得出，商是 C 上的等价关系，> 并且自然排序是 C 上的全序。

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

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

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

于 2010-12-26T21:53:59.217 回答
11

我来晚了，但也许对你有帮助。用户huitseeker从软件设计的角度写了一个很好的答案。我想从数学的角度回答你的问题。在进入软件世界之前，Alex Stepanov 是一名数学家，研究抽象和通用代数。他经常尝试将严谨的数学基础带入软件和算法设计的世界。在他的《从数学到通用编程》和《编程元素》一书中，他提倡这种设计实践。他关于混合代数结构和软件设计概念的想法在generic programming. 现在让我们谈谈他的报价：

要处理真正的问题，您需要多排序代数 - 跨越多种类型的接口系列

在我看来，他想在这里提到两个主要概念：抽象数据类型的思想（ADT）和代数结构。第一个概念：ADT。ADT- 是一种数据类型的数学模型，其中数据类型仅由其语义定义。Stepanov 将 ofADT的概念object与 OOP 意义上的概念进行了对比。对象包含数据和状态，而 ADTs -不是。ADT - 是一个behavioural abstraction，operation cluster描述与数据的交互。行为抽象完全通过抽象数据类型的代数规范来描述。您可以在原始Liskov 和 Zilles论文中了解更多信息，我也向您推荐一篇论文William R. Cook的面向对象编程与抽象数据类型。

（Discalimer：你可以跳过这一段，因为它更“数学而不那么重要”）首先我想澄清一些术语。当我谈论algebraic structure它时，它与代数相同。这个词algebra也经常用于代数结构。更准确地说，当我们谈论代数结构（代数）时，我们通常指代数而不是代数理论。有一个代数多样性的概念，因为在某个类别的对象上有几个代数结构的概念。根据定义，一个algebraic theory(algebra over it) 由这些操作必须满足的操作和定律的规范组成：这是我们将使用的代数结构的工作定义，我认为，Stepanov 在引用中隐含地提到了这个定义。

Stepanov 想要提到的第二个概念是 ADT最有趣的属性：它们可以直接被正式建模为many-sorted algebraic structures. 让我们更正式地谈论它。代数结构 - 是在carrier set其上定义了一个或多个有限运算的结构。这些操作通常不是在一个集合上定义，而是在多个集合上定义。例如，让我们定义和代数模型字符串连接。这个代数将不是在一组字符串上定义，而是在两组上定义：字符串 setS和自然数 set N，因为我们可以定义一个操作，它可以将字符串与自身连接有限次。因此，此操作将采用两个操作数，它们属于不同的底层（载体）集合：S和N. 在代数中定义这些不同操作数（它们的类型）的集合称为sorts. Sort是该类型的代数类比。具有多种排序的代数称为多排序代数。在通用代数中，asignature列出了表征代数结构的操作。多排序代数结构可以有任意数量的域。排序是签名的一部分，它们扮演不同域名称的角色。多排序签名还规定了定义多排序代数结构的函数和关系的排序。对于单分类代数，签名是一个集合，其元素称为操作，每个元素都分配有一个基数 (0,1,2,…)，称为其元数。多排序代数的签名可以定义为Σ = (S,OP,A), 其中S- 排序名称（类型）OP集， - 操作名称集和A- arity 和以前一样，只是现在一个 arity 是输入排序的列表（序列或更一般的自由幺半群），而不仅仅是一个自然数（长度列表）以及一种输出排序。现在我们可以将抽象数据类型的代数规范创建ADT为三元组：

ADT = (N, Σ, E)

，其中N- 抽象数据类型的名称，Σ = (S,OP,A)- 多排序代数结构E = {e1, e2, …,en}的签名， - 是签名中等式的有限集合。正如您现在所看到的，我们对 ADT 进行了严格的数学描述。在数学中，多排序代数结构经常被用作一种方便的工具，即使它们可以通过一点努力来避免。多排序代数结构很少以严格的方式定义，因为明确地进行泛化很简单。这就是为什么多排序代数理论可以成功地应用于软件设计的原因。

所以，Alex Stepanov 想说他更喜欢 ADT 和泛型编程而不是 OOP，因为这样我们可以创建具有严格数学/代数基础的程序。我非常感谢他的努力。我们都知道代数设计总是正确的、严谨的、美观的、简单的并且给我们更好的抽象。

于 2015-05-15T07:58:06.600 回答
0

并不是说我是任何这些理论的专家，但让我们看一下引用，以便我可以尝试给出我的实际理解以添加到讨论中。

要处理真正的问题，您需要多排序代数 - 跨越多种类型的接口系列。

From my readings, I think families of interfaces that span multiple types sounds a lot like type classes from Haskell, which is similar to concepts from C++. Take a type class like Foldable it actually is a type parametrized interface, ie. a familiy of interfaces that span multiple types. So about your question of how to solve problems with multisorted algebras, generic programming is all about that if you take it to mean type classes or concepts.

于 2018-05-01T08:45:56.247 回答