什么是开放递归?它是专门针对OOP的吗?(我是在丹尼尔·斯皮瓦克的这条推文中遇到这个词的。)
bfrts1fy1#
只需复制http://www.comlab.ox.ac.uk/people/ralf.hinze/talks/Open.pdf:“开放递归大多数对象和类的语言提供的另一个方便的功能是,一个方法体能够通过一个名为self的特殊变量或在某些语言中称为This的特殊变量调用同一对象的另一个方法。self的特殊行为是它是后期绑定的,允许一个类中定义的方法调用稍后在第一个类的某个子类中定义的另一个方法。”
mwg9r5ms2#
This从可表现性和复杂性两个方面分析了在ML中加入面向对象的可能性。它有以下关于物体的摘录,这似乎使这个词相对清晰-
3.3。对象
最简单的对象形式只是共享带有对象状态的公共闭包环境的函数的记录(我们可以称之为这些简单对象)。记录的函数成员可以被定义为相互递归,也可以不被定义为相互递归。然而,如果想要支持带有覆盖的继承,对象的结构就会变得更加复杂。要启用开放递归,方法函数的调用图不能是硬连接的,而需要通过对象自引用间接实现。对象自引用可以通过构造来实现,使每个对象成为递归的、自引用的值(定点模型),或者动态地,通过在每次方法调用时将对象作为额外的参数传递(自应用或自传递模型)。5在任何一种情况下,我们都将调用这些自引用对象。
izj3ouym3#
起初,“开放递归”这个名称有点误导,因为它与通常使用的递归(调用自身的函数)无关;在这种程度上,不存在闭合递归。这基本上意味着,一个事物指的是它自己。我只能猜测,但我确实认为“开放”一词来自于“开放供扩展”一词。从这个意义上说,一个对象是开放的,但仍然是指它自己。或许,一个小例子就能让我们对这一概念有所了解。假设您编写了一个如下所示的Python类:
class SuperClass: def method1(self): self.method2() def method2(self): print(self.__class__.__name__)
如果你把这个放在
s = SuperClass() s.method1()
它将打印“超类”。现在,我们从超类创建一个子类并覆盖方法2:
class SubClass(SuperClass): def method2(self): print(self.__class__.__name__)
并运行它:
sub = SubClass() sub.method1()
现在将打印“SubClass”。尽管如此,我们仍然只像以前一样调用方法1()。在方法1()中,会调用方法2(),但两者都绑定到相同的引用(在Python中是self,在Java中是This)。在子类化过程中,更改了超类方法2(),这意味着子类的对象引用了该方法的不同版本。这就是开放递归。在大多数情况下,您可以重写方法并直接调用重写的方法。这里的方案是使用间接而不是自我引用。附言:我认为这不是发明出来的,而是被发现然后解释的。
p5cysglq4#
开放递归允许从内部调用Object的其他方法,通过This或self等特殊变量。
dm7nw8vv5#
简而言之,开放递归实际上与OOP无关,而是更通用的东西。与OOP的关系来自于这样一个事实,即许多典型的“OOP”pls都具有这样的属性,但它本质上与OOP的任何区别特性无关。因此,即使在相同的面向对象的语言中,也有不同的含义。我将在稍后对其进行说明。
正如前面提到的here,这个术语很可能是在著名的TAPL by BCP中创造出来的,它通过具体的OOP语言来说明其含义。TAPL没有正式定义“开放递归”。相反,它指出“self(或this)的特殊行为是它是后期绑定的,允许一个类中定义的方法调用稍后在第一个类的某个子类中定义的另一个方法”。然而,“开放”和“递归”都不是基于面向对象的语言。(实际上,它也与静态类型无关。)因此,该来源中的解释(或非正式定义,如果有的话)在性质上被过度指定了。
self
this
在TAPL中的提及清楚地表明“递归”是关于“方法调用”的。然而,在真实的语言中并不是那么简单,它们通常没有关于递归调用本身的原始语义规则。真正的语言(包括那些被认为是面向对象语言的语言)通常为方法调用的表示法指定这种调用的语义。作为一种句法手段,这种调用依赖于对其子表达式的求值而受到某种表达式的求值。这些评估意味着在一些独立规则下的方法名称的解析。具体地说,这样的规则是关于名称解析的,即确定子表达式中名称(通常是符号、标识符或一些“限定的”名称表达式)的表示。名称解析通常遵守“作用域”规则。“后期绑定”属性强调如何找到命名方法的目标实现。这是对特定调用表达式求值的一条捷径,但还不够通用,因为方法以外的实体也可以有这种“特殊”行为,甚至使这种行为一点也不特殊。一个值得注意的含糊不清来自于这种不充分的治疗。也就是说,“约束性”是什么意思。传统上,绑定可以建模为一对(限定作用域的)名称及其绑定值,即变量绑定。在对“后期绑定”实体的特殊处理中,允许的实体集较小:方法而不是所有命名实体。除了在元级别(在语言规范中)极大地削弱了语言规则的抽象力之外,它并没有停止绑定的传统意义的必要性(因为还有其他非方法实体),因此令人困惑。使用“后期绑定”至少是一个命名不好的例子。与“绑定”相比,更恰当的名称应该是“调度”。更糟糕的是,在TAPL中的使用直接混淆了这两个意思在处理“重复”。“递归”行为就是查找由某个名称表示的实体,而不仅仅是特定于方法调用(即使是在那些面向对象语言中)。这一章的标题(案例研究:命令性对象)也表明了一些不一致之处。显然,所谓的方法调用的后期绑定与命令性状态无关,因为分派的解析不需要可变的调用元数据。(在一些流行的实现意义上,虚拟方法表不需要修改。)
这里使用的“开放”看起来像是模仿开放(Lambda)术语。开放术语有一些名称尚未绑定,因此这种术语的缩减必须进行一些名称解析(以计算表达式的值),否则术语不会规范化(永远不会在求值时终止)。对于原始演算来说,没有“晚期”或“早期”的区别,因为它们是纯的,并且它们具有Church-Rosser属性,所以“晚期”或不是“晚期”不会改变结果(如果它是标准化的)。这在可能具有不同调度路径的语言中是不同的。即使调度本身隐含的隐式求值是纯粹的,它也对其他具有副作用的求值的顺序很敏感,这些副作用可能依赖于具体的调用目标(例如,一个重写器可能会改变一些全局状态,而另一个重写器不能)。当然,在一种严格的纯语言中,即使对于任何根本不同的调用目标,也不可能有明显的差异,一种语言排除了所有这些调用目标是无用的。然后还有另一个问题:为什么它是特定于OOP的(就像在TAPL中一样)?鉴于开放是限定的“绑定”而不是“方法调用的调度”,当然还有其他方法来获得开放。
一个值得注意的例子是在传统的Lisp方言中计算过程体。正文中可以有未绑定的符号,它们仅在过程被调用(而不是定义)时才被解析。由于LISP在PL历史上具有重要意义,而且与lambda演算关系密切,因此将“开放”专门归因于OOP语言(而不是LIPP)与PL传统相比更为奇怪。(这也是上面提到的“让它们一点都不特殊”的情况:函数体中的每个名称在默认情况下都是“打开的”。)同样有争议的是,self/this参数的OOP风格等同于该过程中来自(隐式)环境的某些闭包转换的结果。在语言语义上将这些特征视为原始性是值得怀疑的。(可能还值得注意的是,对其他表达式中符号解析的函数调用的特殊处理是由Lisp-2 dialects开创的,而不是任何典型的OOP语言。)
如上所述,“开放递归”的不同含义可以在同一“面向对象”语言中共存。C是这里的第一个示例,因为有足够的理由使它们共存。在C中,名称解析都是静态的,规范地是“名称查找”。名称查找的规则因作用域不同而不同。它们中的大多数都与C中的标识符查找规则一致(除了在C中允许隐式声明,但在C中不允许):您必须首先声明名称,然后才能在源代码中(词法上)稍后查找该名称,否则程序格式错误(并且需要在语言的实现中发出错误)。这种名称依赖关系的严格要求是相当“封闭”的,因为以后没有机会从错误中恢复,所以不能直接让名称在不同的声明中相互引用。为了解决这个限制,可以有一些额外的声明,它们的唯一职责是打破循环依赖。这样的声明被称为“前进”声明。使用正向声明仍然不需要“开放”递归,因为每次格式良好的使用都必须静态地看到该名称的前一个声明,因此每次名称查找不需要额外的“后期”绑定。然而,C类有特殊的名称查找规则:类作用域中的一些实体可以在声明之前的上下文中引用。这使得在不同声明之间相互递归使用名称成为可能,而无需任何额外的“转发”声明来打破循环。这正是TAPL意义上的“开放递归”,只是它与方法调用无关。此外,根据TAPL中的描述,C确实具有“开放递归”:this指针和virtual函数。确定虚拟函数的目标(重写器)的规则独立于名称查找规则。派生类中定义的非静态成员通常只是“隐藏”基类中同名的实体。调度规则仅在虚拟函数调用、名称查找之后生效(由于C函数调用的评估是严格的或适用的,因此顺序是有保证的)。通过using声明引入基类名称也很容易,而不必担心实体的类型。这样的设计可以被视为关注点分离的一个示例。名称查找规则允许在语言实现中进行一些通用的静态分析,而无需对函数调用进行特殊处理。Java有一些更复杂的规则来混合名称查找和其他规则,包括如何识别重写者。Java子类中的名称隐藏是特定于实体类型的。对于不同的类型,区分重写和重载/隐藏要复杂得多。在子类的定义中也不能有C的using声明的技术。无论如何,这种复杂性并不会使Java比C更多或更少地“面向对象”。
virtual
using
折叠方法调用的名称解析和调度的绑定不仅导致了歧义、复杂和混乱,而且在元级上也带来了更多的困难。在这里,元意味着名称绑定不仅可以公开源语言语义中可用的属性,而且还可以受元语言的约束:语言的形式语义或其实现(例如,实现解释器或编译器的代码)。
例如,就像在传统的LISP中一样,可以将绑定时间与求值时间区分开来,因为与求值时间属性(如任意对象的具体值)相比,绑定时间中显示的程序属性(直接上下文中的值绑定)更接近元属性。优化编译器可以根据绑定时间分析立即部署代码生成,要么在编译时静态地(当正文要多次求值时),要么在运行时(当编译代价太高时)。对于语言来说,没有这样的选择,盲目地假设所有的解析都是闭合递归的,比开放递归的要快(甚至一开始就让它们在语法上不同)。从这个意义上说,特定于OOP的开放式递归不仅“不”像TAPL中宣传的那样方便,而且是一个过早的优化:过早地放弃metacompilation,不是在语言实现中,而是在语言设计中。
5条答案
按热度按时间bfrts1fy1#
只需复制http://www.comlab.ox.ac.uk/people/ralf.hinze/talks/Open.pdf:“开放递归大多数对象和类的语言提供的另一个方便的功能是,一个方法体能够通过一个名为self的特殊变量或在某些语言中称为This的特殊变量调用同一对象的另一个方法。self的特殊行为是它是后期绑定的,允许一个类中定义的方法调用稍后在第一个类的某个子类中定义的另一个方法。”
mwg9r5ms2#
This从可表现性和复杂性两个方面分析了在ML中加入面向对象的可能性。它有以下关于物体的摘录,这似乎使这个词相对清晰-
3.3。对象
最简单的对象形式只是共享带有对象状态的公共闭包环境的函数的记录(我们可以称之为这些简单对象)。记录的函数成员可以被定义为相互递归,也可以不被定义为相互递归。然而,如果想要支持带有覆盖的继承,对象的结构就会变得更加复杂。要启用开放递归,方法函数的调用图不能是硬连接的,而需要通过对象自引用间接实现。对象自引用可以通过构造来实现,使每个对象成为递归的、自引用的值(定点模型),或者动态地,通过在每次方法调用时将对象作为额外的参数传递(自应用或自传递模型)。5在任何一种情况下,我们都将调用这些自引用对象。
izj3ouym3#
起初,“开放递归”这个名称有点误导,因为它与通常使用的递归(调用自身的函数)无关;在这种程度上,不存在闭合递归。这基本上意味着,一个事物指的是它自己。我只能猜测,但我确实认为“开放”一词来自于“开放供扩展”一词。从这个意义上说,一个对象是开放的,但仍然是指它自己。
或许,一个小例子就能让我们对这一概念有所了解。
假设您编写了一个如下所示的Python类:
如果你把这个放在
它将打印“超类”。
现在,我们从超类创建一个子类并覆盖方法2:
并运行它:
现在将打印“SubClass”。
尽管如此,我们仍然只像以前一样调用方法1()。在方法1()中,会调用方法2(),但两者都绑定到相同的引用(在Python中是self,在Java中是This)。在子类化过程中,更改了超类方法2(),这意味着子类的对象引用了该方法的不同版本。
这就是开放递归。
在大多数情况下,您可以重写方法并直接调用重写的方法。这里的方案是使用间接而不是自我引用。
附言:我认为这不是发明出来的,而是被发现然后解释的。
p5cysglq4#
开放递归允许从内部调用Object的其他方法,通过This或self等特殊变量。
dm7nw8vv5#
简而言之,开放递归实际上与OOP无关,而是更通用的东西。
与OOP的关系来自于这样一个事实,即许多典型的“OOP”pls都具有这样的属性,但它本质上与OOP的任何区别特性无关。
因此,即使在相同的面向对象的语言中,也有不同的含义。我将在稍后对其进行说明。
词源
正如前面提到的here,这个术语很可能是在著名的TAPL by BCP中创造出来的,它通过具体的OOP语言来说明其含义。
TAPL没有正式定义“开放递归”。相反,它指出“
self
(或this
)的特殊行为是它是后期绑定的,允许一个类中定义的方法调用稍后在第一个类的某个子类中定义的另一个方法”。然而,“开放”和“递归”都不是基于面向对象的语言。(实际上,它也与静态类型无关。)因此,该来源中的解释(或非正式定义,如果有的话)在性质上被过度指定了。
歧义
在TAPL中的提及清楚地表明“递归”是关于“方法调用”的。然而,在真实的语言中并不是那么简单,它们通常没有关于递归调用本身的原始语义规则。真正的语言(包括那些被认为是面向对象语言的语言)通常为方法调用的表示法指定这种调用的语义。作为一种句法手段,这种调用依赖于对其子表达式的求值而受到某种表达式的求值。这些评估意味着在一些独立规则下的方法名称的解析。具体地说,这样的规则是关于名称解析的,即确定子表达式中名称(通常是符号、标识符或一些“限定的”名称表达式)的表示。名称解析通常遵守“作用域”规则。
“后期绑定”属性强调如何找到命名方法的目标实现。这是对特定调用表达式求值的一条捷径,但还不够通用,因为方法以外的实体也可以有这种“特殊”行为,甚至使这种行为一点也不特殊。
一个值得注意的含糊不清来自于这种不充分的治疗。也就是说,“约束性”是什么意思。传统上,绑定可以建模为一对(限定作用域的)名称及其绑定值,即变量绑定。在对“后期绑定”实体的特殊处理中,允许的实体集较小:方法而不是所有命名实体。除了在元级别(在语言规范中)极大地削弱了语言规则的抽象力之外,它并没有停止绑定的传统意义的必要性(因为还有其他非方法实体),因此令人困惑。使用“后期绑定”至少是一个命名不好的例子。与“绑定”相比,更恰当的名称应该是“调度”。
更糟糕的是,在TAPL中的使用直接混淆了这两个意思在处理“重复”。“递归”行为就是查找由某个名称表示的实体,而不仅仅是特定于方法调用(即使是在那些面向对象语言中)。
这一章的标题(案例研究:命令性对象)也表明了一些不一致之处。显然,所谓的方法调用的后期绑定与命令性状态无关,因为分派的解析不需要可变的调用元数据。(在一些流行的实现意义上,虚拟方法表不需要修改。)
开放性
这里使用的“开放”看起来像是模仿开放(Lambda)术语。开放术语有一些名称尚未绑定,因此这种术语的缩减必须进行一些名称解析(以计算表达式的值),否则术语不会规范化(永远不会在求值时终止)。对于原始演算来说,没有“晚期”或“早期”的区别,因为它们是纯的,并且它们具有Church-Rosser属性,所以“晚期”或不是“晚期”不会改变结果(如果它是标准化的)。
这在可能具有不同调度路径的语言中是不同的。即使调度本身隐含的隐式求值是纯粹的,它也对其他具有副作用的求值的顺序很敏感,这些副作用可能依赖于具体的调用目标(例如,一个重写器可能会改变一些全局状态,而另一个重写器不能)。当然,在一种严格的纯语言中,即使对于任何根本不同的调用目标,也不可能有明显的差异,一种语言排除了所有这些调用目标是无用的。
然后还有另一个问题:为什么它是特定于OOP的(就像在TAPL中一样)?鉴于开放是限定的“绑定”而不是“方法调用的调度”,当然还有其他方法来获得开放。
一个值得注意的例子是在传统的Lisp方言中计算过程体。正文中可以有未绑定的符号,它们仅在过程被调用(而不是定义)时才被解析。由于LISP在PL历史上具有重要意义,而且与lambda演算关系密切,因此将“开放”专门归因于OOP语言(而不是LIPP)与PL传统相比更为奇怪。(这也是上面提到的“让它们一点都不特殊”的情况:函数体中的每个名称在默认情况下都是“打开的”。)
同样有争议的是,
self
/this
参数的OOP风格等同于该过程中来自(隐式)环境的某些闭包转换的结果。在语言语义上将这些特征视为原始性是值得怀疑的。(可能还值得注意的是,对其他表达式中符号解析的函数调用的特殊处理是由Lisp-2 dialects开创的,而不是任何典型的OOP语言。)
更多案例
如上所述,“开放递归”的不同含义可以在同一“面向对象”语言中共存。
C是这里的第一个示例,因为有足够的理由使它们共存。
在C中,名称解析都是静态的,规范地是“名称查找”。名称查找的规则因作用域不同而不同。它们中的大多数都与C中的标识符查找规则一致(除了在C中允许隐式声明,但在C中不允许):您必须首先声明名称,然后才能在源代码中(词法上)稍后查找该名称,否则程序格式错误(并且需要在语言的实现中发出错误)。这种名称依赖关系的严格要求是相当“封闭”的,因为以后没有机会从错误中恢复,所以不能直接让名称在不同的声明中相互引用。
为了解决这个限制,可以有一些额外的声明,它们的唯一职责是打破循环依赖。这样的声明被称为“前进”声明。使用正向声明仍然不需要“开放”递归,因为每次格式良好的使用都必须静态地看到该名称的前一个声明,因此每次名称查找不需要额外的“后期”绑定。
然而,C类有特殊的名称查找规则:类作用域中的一些实体可以在声明之前的上下文中引用。这使得在不同声明之间相互递归使用名称成为可能,而无需任何额外的“转发”声明来打破循环。这正是TAPL意义上的“开放递归”,只是它与方法调用无关。
此外,根据TAPL中的描述,C确实具有“开放递归”:
this
指针和virtual
函数。确定虚拟函数的目标(重写器)的规则独立于名称查找规则。派生类中定义的非静态成员通常只是“隐藏”基类中同名的实体。调度规则仅在虚拟函数调用、名称查找之后生效(由于C函数调用的评估是严格的或适用的,因此顺序是有保证的)。通过using
声明引入基类名称也很容易,而不必担心实体的类型。这样的设计可以被视为关注点分离的一个示例。名称查找规则允许在语言实现中进行一些通用的静态分析,而无需对函数调用进行特殊处理。
Java有一些更复杂的规则来混合名称查找和其他规则,包括如何识别重写者。Java子类中的名称隐藏是特定于实体类型的。对于不同的类型,区分重写和重载/隐藏要复杂得多。在子类的定义中也不能有C的
using
声明的技术。无论如何,这种复杂性并不会使Java比C更多或更少地“面向对象”。其他后果
折叠方法调用的名称解析和调度的绑定不仅导致了歧义、复杂和混乱,而且在元级上也带来了更多的困难。在这里,元意味着名称绑定不仅可以公开源语言语义中可用的属性,而且还可以受元语言的约束:语言的形式语义或其实现(例如,实现解释器或编译器的代码)。
例如,就像在传统的LISP中一样,可以将绑定时间与求值时间区分开来,因为与求值时间属性(如任意对象的具体值)相比,绑定时间中显示的程序属性(直接上下文中的值绑定)更接近元属性。优化编译器可以根据绑定时间分析立即部署代码生成,要么在编译时静态地(当正文要多次求值时),要么在运行时(当编译代价太高时)。对于语言来说,没有这样的选择,盲目地假设所有的解析都是闭合递归的,比开放递归的要快(甚至一开始就让它们在语法上不同)。从这个意义上说,特定于OOP的开放式递归不仅“不”像TAPL中宣传的那样方便,而且是一个过早的优化:过早地放弃metacompilation,不是在语言实现中,而是在语言设计中。