什么是开放递归？

Question

什么是开放递归？它是否只与面向对象编程有关？

（我在Daniel Spiewak的这条推文中看到了这个术语。）

- missingfaktor

---

从他最近的一条推特中来到这里：“我对面向对象的定义是消息传递与开放递归相结合。” - letronje

@letronje，你可能想看一下我刚刚链接的论文。 - missingfaktor

考虑到这是我在谷歌搜索“开放递归”时的第一个结果，它应该得到更全面的回答。在此之前，还有一些其他值得阅读的讨论，例如：https://dev59.com/gWMm5IYBdhLWcg3wMssp，https://news.ycombinator.com/item?id=20495597。 - FrankHB

Answer 1

只是复制了 http://www.comlab.ox.ac.uk/people/ralf.hinze/talks/Open.pdf： "开放递归 另一个由大多数具有对象和类的语言提供的方便功能是能够通过一个称为self或在某些语言中称为this的特殊变量来调用同一对象的另一个方法。 self的特殊行为是它是后期绑定的，允许在第一个子类中定义另一个方法的方法调用另一个方法。"

- IttayD

---

“开放递归”似乎只是Haskell中状态单子的花哨名称，或者在Python中使用常规对象方法（第一个参数为self）进行递归...？这个术语是否带来了什么新的意义？ - ninjagecko

是的，Python（或Ruby或C ++或Smalltalk或Java或C＃等）中的常规对象方法可以展示开放递归。你可能认为这不是什么大问题，但如果你曾经正式学习过面向对象编程的语义，你会发现它实际上很棘手。 - James Iry

这个答案对我来说有点误导性。开放递归是指一个方法体能够调用同一对象的另一个方法（相互递归定义，因此是递归），并允许在一个类中定义的方法调用在其第一个子类中后定义的另一个方法（通过打开基类的闭包并让派生类进入，以便基类可以看到它，例如在C++中将其设置为虚拟）。请参阅http://journal.stuffwithstuff.com/2013/08/26/what-is-open-recursion/，了解有关此主题的文章。 - clickMe

Answer 2

该论文分析了将面向对象（OO）添加到ML中的可能性，涉及表达能力和复杂性。它在对象方面有以下摘录，似乎使这个术语相对清晰 -

3.3. 对象

最简单的对象形式仅是具有共享闭包环境的函数记录，该环境携带对象状态（我们可以称之为简单对象）。记录的函数成员可以定义为相互递归或不递归。然而，如果要支持继承和覆盖，则对象的结构变得更加复杂。为了实现开放递归，方法函数的调用图不能被硬编码，而需要通过对象自引用间接实现。对象自引用可以通过构造实现，使每个对象成为递归的、自我引用的值（固定点模型），或通过在每个方法调用上将对象作为额外参数传递来动态实现（自应用或自传递模型）。在任一情况下，我们将这些自引用对象称为self-referential objects。

- missingfaktor

---

开放递归更多地是由于后期绑定和继承带来的副作用，这就是为什么丹尼尔·斯皮沃克可以创造“面向对象是消息传递与开放递归的婚姻”这一说法，因为继承和子类型多态是面向对象编程的支柱之一。 - lcn

Answer 3

“开放递归”这个名称起初有点误导人，因为它与通常使用的递归（函数调用自身）没有任何关系；在这种程度上，也不存在闭合递归。基本上意味着一个东西正在引用它自己。我只能猜测，但我认为术语“开放”是指“可扩展”。从这个意义上说，一个对象是开放的，但仍然引用着自己。

也许一个小例子可以阐明这个概念。

想象你写了一个像这样的Python类：

class SuperClass:
   def method1(self):
       self.method2()
   def method2(self):
       print(self.__class__.__name__)

如果您通过运行此操作

s = SuperClass()
s.method1()

它将打印 "SuperClass"。

现在我们从SuperClass创建一个子类并覆盖method2：

class SubClass(SuperClass):
def method2(self):
    print(self.__class__.__name__)

并运行它：

sub = SubClass()
sub.method1()

现在将打印“SubClass”。 但是，我们仍然像以前一样只调用method1()。在method1()内部，调用了method2()，但两者都绑定到同一个引用上（Python中的self，Java中的this）。在子类化SuperClass时，method2()被更改，这意味着SubClass的对象引用了此方法的不同版本。 这就是开放递归。 在大多数情况下，您会覆盖方法并直接调用覆盖的方法。 这里的方案是使用对自我引用的间接引用。 附言：我认为这不是发明而是发现，然后解释。

- Stefan Sonnenberg-Carstens

---

这是“递归”一词在正常意义下的直接应用。另一方面，普遍误解递归是关于递归调用的。调用的递归是更一般递归的一个实例。而这里的递归恰好是关于元语言中的调用（例如在形式语义或解释器中），它实现了对象语言的名称查找规则。顺便说一下，“开放”是“闭合”的相反，它与“闭包”的同源词，即“闭合项”（在重写系统如λ演算中）。 - FrankHB

Answer 4

简而言之，开放递归与面向对象编程实际上无关，而更为一般化。与面向对象编程的关系在于许多典型的“面向对象”程序语言具有这样的特性，但它本质上并没有与任何区别于面向对象编程的独特特征联系起来。因此，在同一“面向对象”语言中可能存在不同的含义。我将在后面进行阐述。

词源学方面，正如这里所提到的，这个术语很可能是由著名的BCP的TAPL所创造的，通过具体的面向对象语言来说明其含义。

TAPL没有正式定义“开放递归”。相反，它指出了“self”（或“this”）的“特殊行为是它是“晚期绑定”的，允许在一个类中定义的方法调用另一个稍后在某个子类中定义的方法”的事实。

尽管如此，“open”和“递归”都不是面向对象语言的基础。事实上，这与静态类型也无关。因此，在那个资源中的解释（或者如果有的话，非正式定义）具有过度规定性质。

歧义

TAPL中的提及清楚地表明，“递归”是关于“方法调用”的。然而，在真实语言中这并不是那么简单的，通常没有原始的语义规则来处理递归自身的调用。真实语言（包括被认为是面向对象语言的语言）通常会针对方法调用符号的符号表示指定此类调用的语义。作为语法设备，这些调用受到某种表达式的计算的影响，该表达式依赖于其子表达式的计算。这些计算意味着方法名称的解析，根据一些独立规则。具体而言，这些规则涉及名称解析，即确定子表达式中名称（通常是符号、标识符或某些“限定”名称表达式）的指称。名称解析通常遵守作用域规则。

另一方面，“后期绑定”属性强调如何找到命名方法的目标实现。这是特定调用表达式评估的快捷方式，但它并不够通用，因为除了方法之外的实体也可以具有这种“特殊”行为，甚至可以使这种行为变得不那么特殊。

这种不充分的处理带来了一个值得注意的歧义。也就是，“绑定”是什么意思。传统上，绑定可以被建模为一个（作用域）名称和其绑定值的对，即一个变量绑定。在“后期绑定”中的特殊处理中，允许的实体集更小：方法而不是所有命名实体。除了在元级别的语言规范中严重削弱语言规则的抽象能力之外，它并没有消除传统绑定含义的必要性（因为还有其他非方法实体），因此容易引起混淆。“后期绑定”的使用至少是一个糟糕命名的例子。比起“绑定”，更合适的名称应该是“分派”。

更糟糕的是，在TAPL中使用时，直接混淆了两个意义当处理“递归”。 “递归”行为涉及查找某个名称所表示的实体，而不仅限于方法调用（即使在那些面向对象的语言中也是如此）。

本章标题（案例研究：命令式对象）也暗示了一些不一致之处。显然，所谓的方法调用的后期绑定与命令式状态无关，因为分派的解析不需要可变元数据的调用。（在某些流行的实现方式中，虚拟方法表不需要可修改性。）

开放性

这里使用“开放”看起来像是模仿“开放”（lambda）术语。一个开放的术语有一些尚未绑定的名称，因此这样一个术语的缩减必须进行一些名称解析（以计算表达式的值），否则该术语不会被规范化（在评估中永远不会终止）。对于原始的演算法来说，“晚”或“早”的区别没有区别，因为它们是纯粹的，并且具有Church-Rosser属性，因此无论是否“晚”，都不会改变结果（如果它是规范化的）。

这在具有不同派发路径的语言中是不同的。即使派发本身所隐含的隐式评估是纯粹的，它也对其他具有副作用的评估之间的顺序敏感，这些评估可能依赖于具体的调用目标（例如，一个覆盖者可能会改变一些全局状态，而另一个则不能）。当然，在严格纯净的语言中，即使针对任何根本不同的调用目标，也不会有任何可观察到的差异，因此排除所有这些调用目标的语言是没有用的。

然后还有另一个问题：为什么它是面向对象特定的（如TAPL所述）？考虑到开放性是限定“绑定”而不是“方法调用分派”，肯定有其他手段可以获得开放性。

一个值得注意的例子是传统Lisp方言中过程体的评估。在过程体中可能存在未绑定的符号，它们只能在调用过程时（而不是定义时）解析。由于Lisp在PL历史上非常重要，并且它们与λ演算密切相关，将“开放”专门归因于面向对象语言（而不是Lisp）从PL传统上更为奇怪。（这也是上面提到的“使它们一点也不特别”的情况：函数体中的每个名称默认都是“开放”的。）

有人认为，面向对象编程中的self/this参数风格等价于从（隐式）过程的环境进行某些闭包转换的结果。将这些特性视为语言语义中的原始特性是值得质疑的。

（值得注意的是，在其他表达式中的符号解析调用的特殊处理是由Lisp-2方言开创的，而不是任何典型的面向对象编程语言。）

更多案例

如上所述，“开放递归”的不同含义可以在同一个“面向对象”语言中共存。

C++是第一个实例，因为有充分的理由使它们共存。

在C++中，名称解析都是静态的，规范化为“名称查找”。名称查找的规则因不同作用域而异。其中大部分规则与C语言中的标识符查找规则一致（除了C语言中允许隐式声明而C++中不允许），即必须先声明名称，然后才能在源代码中（词法上）稍后查找该名称，否则程序就是非法的（并且在语言实现中必须发出错误）。这种依赖关系的严格要求相当“封闭”，因为没有后来的机会从错误中恢复，所以你不能直接在不同声明之间互相引用名称。

为了绕过这个限制，可以有一些额外的声明，其唯一职责是打破循环依赖关系。这些声明称为“前向”声明。使用前向声明仍然不需要“开放”递归，因为每个良好形成的用法必须静态地看到该名称的先前声明，因此每个名称查找不需要额外的“后期”绑定。

但是，C++类具有特殊的名称查找规则：类作用域中的某些实体可以在其声明之前的上下文中引用。这使得在不需要任何额外的“前向”声明来打破循环的情况下，可以跨不同声明相互递归使用名称。这正是TAPL意义上的“开放递归”，只是它与方法调用无关。

此外，根据TAPL中的描述，C++确实具有“开放递归”：即this指针和virtual函数。确定虚函数目标（覆盖者）的规则与名称查找规则无关。派生类中定义的非静态成员通常只是将与基类中相同名称的实体“隐藏”。调度规则仅在虚函数调用之后的名称查找之后启动（顺序得到保证，因为C++函数调用的评估是严格的或应用的）。还可以通过using声明轻松引入基类名称，而不必担心实体类型。

这种设计可以看作是关注点分离的一个实例。名称查找规则允许在语言实现中进行一些通用的静态分析，而不需要对函数调用进行特殊处理。

另一方面，Java有一些更复杂的规则来混合名称查找和其他规则，包括如何识别覆盖者。在Java子类中的名称遮蔽是特定于实体类型的。对于不同种类的覆盖、重载、遮蔽和模糊，区分覆盖变得更加复杂。在子类的定义中也不能使用C++中的using声明技术。无论如何，这种复杂性并不会使Java比C++更或更少“面向对象”。

其他后果

将名称解析和方法调用的派发绑定合并导致了不仅是歧义、复杂性和混乱，而且还有元级别上的更多困难。这里的元指的是名称绑定可以暴露的属性不仅可用于源语言语义，而且还受到元语言的影响：要么是语言的形式语义，要么是其实现（例如实现解释器或编译器的代码）。

例如，就像传统Lisp中一样，可以区分绑定时间和评估时间，因为在绑定时间（在立即上下文中的值绑定）中揭示的程序属性与评估时间属性（如任意对象的具体值）相比更接近元属性。优化编译器可以根据绑定时间分析立即部署代码生成，要么静态地在编译时（当主体需要评估多次时），要么在运行时推迟（当编译过于昂贵时）。对于那些盲目假设所有封闭递归都比开放递归更快速（甚至在第一次语法上就使它们不同）的语言，没有这样的选项。在这种意义上，面向对象编程特定的开放递归不仅不像TAPL中所宣传的那样方便，而且是一种过早的优化：在语言设计中过早地放弃了元编译，而不是在语言实现中。

- FrankHB

Answer 5

开放递归允许通过特殊变量 this 或 self 从内部调用对象的另一个方法。

- user1660210