什么是“开放递归”（Open Recursion）？

本文信息来源：stuffwithstuff

StackOverflow 上有人偶然发现了“开放递归”（open recursion）这个奇怪的术语，并且 发帖询问它的含义 。鉴于网上关于这个概念的大多数回答都相当晦涩难懂，我本想写个回复，结果一不小心写成了一篇博文。

其实我自己也不记得这到底是什么意思了，所以我翻开了手头的 《类型和程序设计语言》（Types and Programming Languages），据我所知，Pierce 就是在这本书里最先引入这个术语的。略读一番后，我大概明白了。对于那些没有这本书或者不想啃编程语言极客术语的人，我会尝试用更通俗易懂的方式来解释它。

首先，介绍一下背景。Pierce 正从一个基于 Lambda 演算和记录（records）、非面向对象的核心出发，解释面向对象语言的语义和类型。他在书中以最简单的原型语言开篇，能够通过不断添加扩展，逐渐构建出我们今天所见的那种语言。他在书中杜撰了“开放递归”（open recursion）这个术语，指代将一种只包含函数（即“lambda”、“闭包”或“匿名委托”）和记录（大致相当于 JS 中的“对象字面量”或其他语言中的“映射”）的简单语言，构建为面向对象语言所需的那些扩展。

由于不太了解 Lambda 演算的人很多，在这个场景中，我将使用 Dart 语言的一个子集作为替代。我们允许函数声明和映射（maps），但不允许真正的类或方法。

现在问题来了，如果你只有包含函数的映射，这与“真正的”对象相比缺失了什么？Pierce 的答案是“开放递归”。我们将把这个术语拆解为两个词，先从后一个词说起：

“递归”（Recursion）#recursion

假设你想创建一个代表计数器的“对象”。它提供三个操作：increment()、get() 和 set()。在我们的 Dart 子集中，你可以像这样创建这样一个对象：

makeCounter() {
  // Declare the instance state for the "object".
  var count = 0;

  // Declare functions for the "methods". They are closures,
  // so they can access `count`.
  increment() {
    count++;
  }

  get() {
    return count;
  }

  set(value) {
    count = value;
  }

  // Make an "object" as a map of functions.
  return {
    'get': get,
    'set': set,
    'increment': increment
  };
}

很好。这完全没问题。但是，假设我们想通过调用 get() 和 set() 来实现 increment()。方法的一个常见特性就是它们可以互相调用。让我们试试看：

makeCounter() {
  // Declare the instance state for the "object".
  var count = 0;

  // Declare functions for the "methods". They are closures,
  // so they can access count.
  increment() {
    set(get() + 1));
  }

  get() {
    return count;
  }

  set(value) {
    count = value;
  }

  // Make an "object" as a map of functions.
  return {
    'get': get,
    'set': set,
    'increment': increment
  };
}

哎呀！这行不通。问题在于 increment() 在这里调用了 get() 和 set()，但这两个函数尚未声明。 与 JavaScript 不同 ，Dart 不会默认将函数声明提升（hoist）到作用域顶部。因此，在定义 increment() 的时候，get() 和 set() 还没有声明。

我们可以把 increment() 移到 get() 和 set() 之后来解决这个问题。但那样的话，这两个方法就无法看见 increment() 了。无论如何，都无法让所有这些函数在彼此的内部作用域中都可见。

问题在于这些函数的定义是按顺序一个接一个出现的。你真正需要的是将它们定义成一个整体，使得它们能够同时彼此可见。

在函数式语言中，用来称呼这个“整体”的名词是“相互递归定义”（mutually recursive definition）。它允许你声明一组变量名，并在每一个变量的定义中引用这些名字。在 Scheme 和 ML 中，这就是 let 和 letrec 之间的区别（名称中的 rec 代表“递归”）。在 C 语言中，你通过前向声明（forward definitions） 来实现这一点。

所以，这里说的“递归”，意思其实是方法定义之间是相互递归的，因此它们可以看见彼此的名称 。 这并不是说它们实际上必须在运行时相互调用并成为递归函数。这仅仅意味着它们的名字都在作用域内，所以它们能够那样做。

“开放”#open

通过使用函数表达式并像这样对变量进行重新赋值，我们可以在我们的 mini-Dart 中模拟相互递归（mutually recursive）的定义：

makeCounter() {
  // Declare the instance state for the "object".
  var count = 0;

  // Declare the variables up front.
  var increment, get, set.

  // Now that the names are all in scope,
  // create the function bodies.
  increment = () {
    set(get() + 1));
  };

  get = () {
    return count;
  };

  set = (value) {
    count = value;
  };

  // Make an "object" as a map of functions.
  return {
    'get': get,
    'set': set,
    'increment': increment
  };
}

请注意方法名与 () 中间现在的 =。这意味着我们正在将匿名函数赋值给已经声明的变量。这为我们提供了递归结构。我们现在拥有对象了吗？还缺什么？

面向对象语言的另一个关键特性是继承（或者在基于原型的语言中称为“委托”）。这意味着在创建新对象时，通过修改现有对象的行为来定义其自身行为。可以联想一下派生类中的方法重写（overriding）。

我们也来试一试。我们将尝试创建一个可以记录自身状态的计数器。为了避免重新实现所有功能，我们将复用现有的计数器代码：

makeLoggingCounter() {
  var counter = makeCounter();

  return {
    'get': () {
      print('get!');
      return counter['get']();
    },
    'set': (value) {
      print('set!');
      counter['set'](value);
    },
    'increment': () {
      print('increment!');
      counter['increment']();
    }
  };
}

我们要确认一下做得怎么样？当我们在那个具备日志功能的计数器上调用 get() 和 set() 时，它的确正确打印出了 “get!” 和 “set!”，并且随后适当地更新了计数器。问题出在我们调用 increment() 的时候。它 确实 打印了 “increment!”。但是，别忘了，increment() 的实现是依靠 get() 和 set() 来完成的。

由于我们想要在日志对象中重写（override）那些方法，所以调用 increment() 应该也会打印出 “get!” 和 “set!”。但它没有。这是因为非日志对象的 increment() 实现是静态绑定到这些方法的基类定义上的。我们在派生的日志计数器中并没有重写它们，我们只是遮蔽（shadowed）了它们。

用 C++ 的术语来说，get() 和 set() 是非虚函数（non-virtual）。我们的迷你 Dart 语言 目前的表达能力还不足以处理虚方法。问题在于，在内部 makeCounter() 时，我们根本看不到日志计数器的实例。为了解决这个问题，我们必须显式地传入该对象：

makeCounter(receiver) {
  // Declare the instance state for the "object".
  var count = 0;

  // Declare the variables up front.
  var increment, get, set;

  // Now that the names are all in scope,
  // create the function bodies.
  increment = () {
    receiver['set'](receiver['get']() + 1));
  };

  get = () {
    return count;
  };

  set = (value) {
    count = value;
  };

  // Add the methods to the receiver.
  receiver['get'] = get;
  receiver['set'] = set;
  receiver['increment'] = increment;
}

请注意，现在 increment() 的定义是如何在那个传入的 receiver() 对象上查找 get() 和 set() 的。为了创建这个记录日志的计数器，我们现在需要这样做：

makeLoggingCounter() {
  // Create a blank object.
  counter = {};

  // Turn it into a counter.
  makeCounter(counter);

  // Keep track of the original methods.
  var superGet = counter['get'];
  var superSet = counter['set'];
  var superIncrement = counter['increment'];

  // Override the methods.
  counter['get'] = () {
    print('get!');
    return superGet();
  };

  counter['set'] = (value) {
    print('set!');
    superSet(value);
  };

  counter['increment'] = () {
    print('increment!');
    superIncrement();
  };

  return counter;
}

哒哒！

为了使这个工作，我们必须将接收器传递给makeCounter()，以便它的方法可以看到“派生”对象。这使得它能够看到并调用被覆盖的方法。这些方法现在有效地变成了“虚拟”的。

在我们这样做之前，makeCounter()中的方法是相互闭合的。换句话说，它们都是闭包，并通过彼此的变量相互调用。通过显式地传递接收器，我们打开了这个闭包，让派生对象能够进入，以便基本方法可以看到它。因此： “开放”。

Recap#recap

So, if you compare a real object-oriented language to a simpler language with just structures and functions, the differences are:

1. 所有这些方法都可以看到并互相调用对方。定义它们的顺序无关紧要，因为它们的定义是“同时的”或*相互递归*的。
2. 基类方法可以访问派生的接收者对象（即其他语言中的 this 或 self），因此它们不仅是对彼此外推封闭的。它们对重写的方法是*开放*的。

即：开放递归。