什么是"多重排列代数",我如何用它来解决"真正的问题"？

Question

显然,亚历山大·斯捷潘诺夫在接受采访时表示如下:

"我发现OOP [面向对象编程]技术上不合理.它试图根据在单一类型上变化的接口来分解世界.要处理真正的问题,您需要多重代数 - 跨多种类型的接口系列." [强调补充.]

暂时忽略他关于OOP的陈述,除了他简洁的定义之外,什么是"多重代数",你能否给出一个如何使用它们的实际例子(用你选择的语言)？

Answer 1

我相信他正在谈论泛型编程(他创造了这个术语),无论是在关于STL的谈论的背景下,还是"在意大利",意思是:

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

要做(1),你需要有一种方法来指定一个类型作为参数的程序,即多态,并且要做(2),你需要一种方式来表明你也希望该类型携带特定的操作(并且,如果您可以表达它们,属性).实际上,您通过其操作的数据结构对程序进行参数化.范式在某些地方被称为有界多态,数据类型 - 泛型编程,......这反映出语言对如何实现该想法有不同的概念 - 因此上面的斜体"类型".

• 对于C++来说,似乎至少对Stepanov而言 - 这对应于模板(尽管关于如何做到这一点的想法仍在不断发展).
• 对于OO语言(Generic Java,C#),类型参数的约束通常使用子类型边界('有界通配符'...)表示.
• 对于哈斯克尔或斯卡拉,你有(分别,同样)类型,属性或implicits.
• ML系列语言更喜欢使用模块来完成这项工作.
• 请注意,许多证明助手(可以表达'诚实上帝' 属性作为类型)已经形成了类型的类型:Isabelle,Coq,Matita就是这样的例子

请注意,斯捷潘诺夫只是共同编写了一本完整的书籍,对图书馆进行了详尽的开发,这个图书馆完全体现了(我认为)他的意思.因此,如果你想要C++中的例子,这绝对是你应该看的地方.还要注意,这比现在常见的编码对接口而不是对象的建议更加进化.

通过"实际例子",我不知道你是说"如何"或"为什么"使用它.为了快速回答'为什么',通用性很好,因为有点像普通的多态,它可以让你重用代码.但是,更重要的是:

1. 必须与每种类型一起工作的多态代码通常无法做任何有趣的事情,而拥有一个受限制的界面可以让你编写更丰富的程序

2. 通过指定该界面如何适合您的某些数据,您可以选择一种类型安全的方法来选择那些符合您需求的元素.例如,你可能知道,减少操作员(reducePython的与Hadoop的,的fold一堆函数式语言的)是并行只有在你申请你还原功能的顺序并不重要(+,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;
 }

当然,由于程序化构造实现的概念变化很大,所以在可用性和表达性方面你会得到的也会有所不同.也许您不应仅仅通过CO或Java等OO语言来判断数据通用编程 - 但我已经编写了太多的内容来开始使用模块归属或类型类的自动实例生成.

Answer 2

我来不及了,但也许对你有帮助.用户huitseeker从软件设计的角度写了一个很好的答案.我想从数学的角度回答你的问题.在深入软件世界之前,Alex Stepanov是一位数学家,他研究过抽象和通用代数.他经常试图将严谨的数学基础带入软件和算法设计领域.在他的书中,从数学到通用编程和编程要素,他提倡这种设计实践.他关于混合代数结构和软件设计概念的想法是在概念中实现的generic programming.现在让我们来谈谈他的话:

要处理真正的问题,您需要多重代数 - 跨多种类型的接口系列

在我看来,他想在这里提到两个主要概念:抽象数据类型(ADT)和代数结构的概念.第一个概念:ADT.ADT - 是数据类型的数学模型,其中数据类型仅由其语义定义.Stepanov 对OOP意义上的想法ADT进行了对比object.对象包含数据和状态,而ADT 则不包括.ADT -是一个behavioural abstraction,一个operation cluster其描述与数据的交互.行为抽象完全通过抽象数据类型的代数规范来描述.您可以在原始的Liskov和Zilles论文中阅读更多内容,我也建议您使用William R. Cook 撰写的面向对象编程与抽象数据类型的论文.

(Discalimer:你可以跳过这一段,因为它更"数学而不是那么重要")起初我想澄清一些术语.当我谈到algebraic structure它时,它与代数相同.这个词algebra通常也用于代数结构.更确切地说,当我们谈论代数结构(代数)时,我们通常意味着代数理论上的代数.存在各种代数的概念,因为在某个类别的对象上存在几个代数结构的概念.根据定义,algebraic theory(代数)由这些操作必须满足的操作和规则的规范组成:这是我们将使用的代数结构的工作定义,我认为,这个定义,Stepanov在引用中隐含地提到.

Stepanov想提到的第二个概念是ADT 最有趣的特性:它们可以直接正式建模为many-sorted algebraic structures.让我们更正式地谈谈它.代数结构 - carrier set在其上定义了一个或多个有限运算.这些操作通常不是在一组上定义,而是在多组上定义.例如,让我们定义和代数来模拟字符串连接.这个代数将不是在一组字符串上定义,而是在两组中定义:字符串集S和自然数集N,因为我们可以定义一个操作,它可以将字符串与自身连接一些有限次数.因此,此操作将采用两个操作数,这些操作数属于不同的底层(载体)集:S和N.设置在代数中定义这些不同的操作数(它们的类型)称为一组sorts.Sort是类型的代数模拟.具有多种排序的代数称为多分类代数.在通用代数中,a signature列出了表征代数结构的操作.多排序的代数结构可以具有任意数量的域.这些类型是签名的一部分,它们扮演着不同域名的角色.许多排序的签名还规定了定义多排序代数结构的功能和关系的排序.对于一个有序的各种代数,签名是一个集合,其元素称为操作,每个元素都被赋予一个称为arity的基数(0,1,2,...).多重排序代数的签名可以定义为? = (S,OP,A),其中S- 排序名称(类型)OP集合,- 操作名称集合A- 和以前一样 - 除了现在arity是列表(序列或更一般地是免费的monoid)之外输入排序而不仅仅是自然数(列表的长度)和一个输出排序.现在我们可以创建一个抽象数据类型的代数规范ADT作为三元组:

ADT = (N, ?, E)

,其中N- 抽象数据类型的名称,? = (S,OP,A)- 多分类代数结构的签名,E = {e1, e2, …,en}- 是签名中的等式的有限集合.你现在可以看到我们对ADT有严格的数学描述.在数学中,许多分类的代数结构通常被用作方便的工具,即使只需要一点点努力就可以避免它们.许多排序的代数结构很少以严格的方式定义,因为明确地执行泛化是直截了当的.这就是为什么多分类代数的理论可以成功地应用于软件设计的原因.

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