多态变异体

Felix多态性变体基于Ocaml中的多态性变体。多态变体类型可以从任意构造函数集合中形成。深度和宽度都符合子类型规则。

打开/关闭原理

编程语言最基本的原则之一就是语言应该支持某种 module 它同时是开放的，可以扩展，但也可以关闭，这样就可以使用而不必担心更改会中断使用。

bertrandmeyer在其开创性的著作“面向对象的软件构造”中明确阐述了这一原则。它是一个关键的动机，一个类的想法，提供一个封闭的，或 encapsulated 资源具有一组封闭的指定方法来操作它，同时可以通过继承进行扩展。

事实证明，这个想法失败了，因为用单一类型标识模块是错误的答案。核心概念始终是非常重要的。

勤奋的程序员

不懂编程的程序员被要求提供一个表示表达式的术语，该表达式可以对表达式执行加法运算。这是一种类型：

typedef addable = (
 | `Val of int
 | `Add of addable * addable
 )
;

下面是评估者：

fun eval (term: addable) =>
  match term with
  | `Val j => j
  | `Add (t1, t2) => eval t1 + eval t2
;

这很好地解决了这个问题。不幸的是，客户要求扩展包含减法。程序员使用 copy and paste polymorphism 键入：

typedef subable = (
 | `Val of int
 | `Add of subable * subable
 | `Sub of subable * subable
 )
;

这是新的评估者：

fun eval2 (term: subable ) =>
  match term with
  | `Val j => j
  | `Add (t1, t2) => eval2 t1 + eval2 t2
  | `Sub (t1, t2) => eval2 t1 - eval2 t2
;

这似乎是合理的，我们仍然使用旧的addable类型，但是在文本编辑器中修改原始代码是一个非常蹩脚的方法：如果原始例程中出现错误，会发生什么？现在你必须记住修正这两个程序。

如果客户现在也想要倍增，你会感到惊讶吗？

懒惰的程序员

聪明的程序员编写的可添加例程与愚蠢的程序员相同。但是聪明的程序员在客户端需要和扩展时并不感到惊讶。聪明的程序员知道客户机在那之后也会想要另一个。

所以聪明的程序员写下：

typedef addable'[T] = (
 | `Val of int
 | `Add of T * T
 )
;

fun eval'[T] (eval: T-> int) (term: addable'[T]) : int =>
  match term with
  | `Val j => j
  | `Add (t1, t2) => eval t1 + eval t2
;

typedef addable = addable'[addable];
fun eval (term:addable) : int => eval' eval term;

现在来看看为什么这是一个非常酷的解决方案：

typedef subable'[T] = (
 | addable'[T]
 | `Sub of T * T
 )
;

fun eval2'[T] (eval2: T-> int) (term: subable'[T]) : int =>
  match term with
  | `Sub (t1, t2) => eval2 t1 - eval2 t2
  | (addable'[T] :>> y) => eval' eval2 y
;

typedef subable = subable'[subable];
fun eval2 (term:subable) : int => eval2' eval2 term;

您在这里看到的是没有代码重复。新的子表'type扩展了旧的addable'类型。新的eval2'例程调用旧的eval'例程。

这是开/闭原理所要求的扩展。另一方面，通过使这些参数化实体引用自身，我们固定它们以获得递归闭包。

开放递归

调用上面显示的方法 open recursion . 在上面最简单的形式中，它需要多态变体类型和高阶函数。

使用这种技术，我们通过在通常需要递归的类型中使用类型变量参数来生成平面的、可线性扩展的数据类型。类似地，在flat函数中，我们使用作为参数传入的函数来计算类型变量类型的值。

平面表单是可扩展的，因此这些类型是开放的。

但是当自我应用时，类型就变成封闭的，可以直接使用。

因此，该技术提供了一种方法，用离散的事例数定义一个类型，并为它提供了一个求值器，将该类型扩展到一个具有多个事例的类型，而不影响原始类型的使用，并且具有批判性，无需重复任何代码。

分型与变异

理解上面的技术为什么起作用是很重要的，但是面向对象的解决方案却不行。

你可能还没有意识到这一点：

fun f(x:addable) => eval2 x;

什么？是的，addable是subable的一个子类型。首先，它是一个 width subtype ，因为addable的案例较少。但这还不够。同样，构造函数的参数也是子类型。因为他们的案子也少。这叫做 depth subtyping . 它递归地应用，并且子类型被称为 covariant .

面向对象不能做到这一点，因为派生类中的方法参数必须 contravariant 而我们希望他们成为 covariant . 您希望这样做：

class Abstract {
  public: virtual Abstract binop (Abstract const &)const=0;
};

class Derived : public virtual Abstract {
  public: Derived binop (Derived const &)const;
};

因为binop方法的参数随求导方向而变化，所以称之为协变。问题是，方法的参数必须是 invariant 意思是与底部相同的类型，或者 contravariant 意思是一个基地的基地！返回类型是协变的，这是允许的，但协变方法参数不可靠且不允许。

您可以这样做：

class Derived : public virtual Abstract {
  public: Derived binop (Abstract const &other)const {
    Derived *d = dynamic_cast<Derived*>(&other);
    if (d) { ... }
    else { .. }
  }
};

但是你怎么知道你在下拉列表中覆盖了所有可能的派生类呢？如果有人添加了另一个，你必须为它编写代码，这就破坏了封装。

简单的事实是OO不能支持具有协变参数的方法，这将OO的实用性限制在方法具有不变参数的简单类型上。OO非常适合字符设备驱动程序，因为write方法在抽象和所有派生类中都接受字符：它是一个不变参数。

混合蛋白

从演示中可以清楚地看到，在链中使用开放递归可以添加任意数量的扩展。这意味着您可以用从叶子到根的子类型关系形成一个完整的扩展树。让我们进行另一个扩展：

typedef mulable'[T] = (
 | addable'[T]
 | `Mul of T * T
 )
;

fun eval3'[T] (eval3: T-> int) (term: subable'[T]) : int =>
  match term with
  | `Sub (t1, t2) => eval3 t1 - eval3 t2
  | (addable'[T] :>> y) => eval' eval3 y
;

typedef mulable = mulable'[mulable];
fun eval3 (term:mulable) : int => eval3' eval3 term;

当然，它与子表的模式相同。问题是，我们能不能把这个和子表结合起来，这样我们就可以做加法、减法和乘法了？

typedef msable'[T] = (
 | subable'[T]
 | mulable'[T]
 )
;

fun eval4'[T] (eval4: T-> int) (term: msable'[T]) : int =>
  match term with
  | (subable'[T] :>> y) => eval2' eval4 y
  | (mulable'[T] :>> a) => eval3' eval4 z
;

typedef msable = msable'[mslable];
fun eval4 (term:msable) : int  => eval4' eval4 term;

这里的问题是子表和mulable都包含Add和Val的大小写。您将得到一个警告，但在这种情况下它是无害的（因为它是同一个大小写）。

下面是一些测试代码：

val x = `Sub (`Add (`Val 42, `Add (`Val 66, `Val 99)), `Val 23);
val y = `Mul (`Add (`Val 42, `Mul (`Val 66, `Val 99)), `Val 23);
val z = `Sub (`Add (`Val 42, `Mul (`Val 66, `Val 99)), `Val 23);

println$ eval2 x; // subable
println$ eval3 y; // mulable

println$ eval4 x; // subable
println$ eval4 y; // mulable
println$ eval4 z; // msable

注意eval4在x和y以及z上都很好！