如何在没有垃圾回收机制的情况下实现闭包?

13

我正在设计一种语言。首先,我想决定要生成什么代码。这种语言将具有类似 JavaScript 的词法闭包和基于原型的继承。但是我不喜欢垃圾回收并尽可能避免使用。所以问题是:是否有一种优雅的方法来实现闭包,而不必将堆栈帧分配到堆上并留给垃圾回收器?

我的第一个想法:

  1. 使用引用计数并垃圾收集循环(我不太喜欢这个方法)
  2. 使用意大利面条式堆栈(看起来非常低效)
  3. 限制形成闭包的某些上下文,以便我可以通过返回地址堆栈和本地变量堆栈摆脱它们。

我不会使用高级语言或遵循任何调用约定,因此我可以随意破坏堆栈。

(编辑:我知道引用计数是一种垃圾收集的形式,但我使用 gc 更常见的含义)


3
“不是GC的粉丝”是什么意思?请记住引用计数是一种垃圾收集形式。另外,在“不遵循任何调用约定”的情况下,“词法闭包”是什么意思? - Allen
1
调用约定,如stdcall、fastcall、cdecl、thiscall... - artificialidiot
1
@Allen 引用计数不是垃圾回收。它是一种自动管理的形式。并非所有类型的自动内存管理都是垃圾回收。 - user529758
13个回答

13
如果您能解释一下不使用垃圾回收(GC)的原因,那么这将是一个更好的问题。正如您所知,大多数提供词法闭包的语言将它们分配在堆上,并允许它们保留对创建它们的激活记录中的变量绑定的引用。
我所知道的唯一替代方法是gcc用于嵌套函数的方法:为函数创建跳板并将其分配到堆栈上。但正如gcc手册所说:
如果您尝试在包含函数退出后通过地址调用嵌套函数,那么所有事情都会失控。如果您在包含作用域级别退出后尝试调用它,并且它引用了一些不再处于作用域内的变量,则您可能很幸运,但冒险并不明智。但是,如果嵌套函数不引用任何已超出范围的内容,则应该是安全的。
简而言之,您有三个主要选择:
- 在堆栈上分配闭包,并且不允许在包含函数退出后使用它们。 - 在堆上分配闭包,并使用某种形式的垃圾回收。 - 进行原始研究,可能从ML、Cyclone等开始。

gcc对闭包的实现相当弱,仅仅减少了显式上下文传递,这是我个人的看法。我想看看在没有垃圾回收的情况下我能走多远。 - artificialidiot

9

这个主题或许可以帮到你,尽管有些答案已经在那里被回答过了。

一个帖子提出了一个好观点:

看起来你想要在“没有真正垃圾收集”的情况下为闭包进行垃圾收集。请注意,闭包可用于实现 cons 单元。因此,你的问题似乎是关于“在没有真正垃圾收集”的情况下进行垃圾收集——有相关丰富的文献。将问题限制在闭包上并不能真正改变它。

所以答案是:不行,没有一种优雅的方法可用于闭包而没有真正的 GC。最好的方法只是对你的闭包进行一些限制性的修改。如果你有一个合适的 GC,所有这些都是不必要的。

那么,我的问题反映了这里其他问题的一些内容——为什么你不想实现 GC?一个简单的标记+清除或停止+复制只需要大约 2-300 行(Scheme)代码,并且在编程方面并不那么糟糕。就程序执行速度而言:

  1. 你可以实现一个更复杂的 GC,它具有更好的性能。
  2. 想象一下你的语言中所有程序不会遭受的内存泄漏。
  3. 使用可用的 GC 编程是一种福音。(想想 C#、Java、Python、Perl 等与 C++ 或 C 相比)。

9

我知道我来晚了,但我无意中看到了这个问题。

我认为完全支持闭包确实需要垃圾回收,但在某些特殊情况下,堆栈分配是安全的。确定这些特殊情况需要进行一些逃逸分析。我建议你看看BitC语言论文,比如BitC中的闭包实现。(尽管我怀疑这些论文是否反映了当前的计划。)BitC的设计者们遇到了和你一样的问题。他们决定为编译器实现一个特殊的非收集模式,拒绝所有可能逃逸的闭包。如果打开它,将会严重限制语言的使用。然而,这个功能还没有实现。

我建议你使用垃圾收集器-这是最优雅的方式。你应该考虑到,一个构建良好的垃圾收集器比malloc更快地分配内存。BitC的人真的很重视性能,他们仍然认为即使对于操作系统Coyotos的大多数部分,GC也是可以的。你可以通过简单的方法来减轻缺点:

  • 只创建最少量的垃圾
  • 让程序员控制收集器
  • 通过逃逸分析优化堆栈/堆使用
  • 使用增量或并发收集器
  • 如果可能的话,像Erlang一样划分堆

许多人因为在Java中的经验而害怕垃圾收集器。Java有一个很棒的收集器,但由于生成了大量垃圾,用Java编写的应用程序存在性能问题。此外,庞大的运行时和花哨的JIT编译对于桌面应用程序来说并不是一个好主意,因为会导致更长的启动和响应时间。


完全闭包支持不需要GC,但需要注意的是它涉及到捕获悬空引用的内存不安全性。C++的闭包对象就是这样工作的。(请注意,闭包并不意味着它可以摆脱所谓的funargs问题)。如果可以证明代码中不存在不安全的捕获(例如通过类型系统,甚至完全禁止引用捕获),那么它将是安全的(尽管对代码有限制)。 - FrankHB

4

C++ 0x标准定义了没有垃圾回收的lambda表达式。简单来说,当lambda闭包中包含不再有效的引用时,规范允许出现非确定性行为。例如(伪代码):

(int)=>int create_lambda(int a)
{
    return { (int x) => x + a }
}

create_lambda(5)(4)    // undefined result

在这个例子中,lambda指的是一个分配在堆栈上的变量(a)。然而,该堆栈帧已经被弹出,并且一旦函数返回,它不一定可用。在这种情况下,它可能会起作用并返回9作为结果(假设编译器语义正常),但无法保证。
如果您要避免垃圾收集,那么我假设您也允许显式堆栈分配和(可能)指针。如果是这种情况,那么您可以像C++一样,只需假设使用您的语言的开发人员足够聪明,能够识别具有lambda问题的问题情况并显式地复制到堆上(就像您在函数内部合成返回值时所做的那样)。

1
谢谢你的建议,但我不想让程序员跟踪帧。我考虑到的一个用例是在使用函数作为事件处理程序时,堆栈帧肯定是无法使用的。 - artificialidiot
对,不要让它们跟踪帧,而是强制它们意识到堆栈上的内容和堆上的内容。如果你没有垃圾回收,那么为了使函数工作,你仍需要这个。 - Daniel Spiewak

4

使用引用计数并对循环进行垃圾回收(我不太喜欢这个方法)

设计语言时可以避免出现循环:如果只能创建新对象而不能改变旧对象,并且创建对象不会形成循环,则永远不会出现循环。Erlang基本上是这样工作的,尽管在实践中它确实使用了垃圾回收。


3
如果您有用于精确复制GC的机器,您可以最初在堆栈上分配并将其复制到堆,并在退出时更新指针,如果发现指向此堆栈帧的指针已经逃逸。这样,只有在实际捕获包含此堆栈帧的闭包时才需要付费。无论这是否有所帮助,都取决于您使用闭包的频率以及它们捕获的数量。
您还可以研究C++0x的方法(N1968),尽管如人们所预期的那样,它依赖于程序员指定要复制和引用的内容,如果出错,则会得到无效访问。

哦,我忘记了那个,谢谢提醒!不过我有点不太愿意移动内存区域。 - artificialidiot
你可以最初在栈上分配内存,然后将其复制到堆上并更新指针,如果发现指向该栈帧的指针已经逃逸,则在退出时执行此操作。我记得,在文献中曾建议过这样做并进行了研究,但它会增加显着的复杂性,并且不会提高性能。 - J D

2
您可以假设所有闭包最终都会被调用一次。现在,当闭包被调用时,您可以在闭包返回时进行清理。
您打算如何处理返回对象?它们必须在某个时候清理,这与闭包的问题完全相同。

@DevinJeanpierre 我可以问一个关于这个的问题吗?这听起来非常有趣,特别是考虑到 Rust 中的闭包可以参与异步/迭代处理。 - bright-star
1
@TrevorAlexander 自我留言以来,Rust已经发生了很大的变化,特别是关于闭包的情况,已经重写了两次。我有一段时间没有使用它了。当时存在一种只能被调用一次的闭包类型,以及其他具有不同限制的闭包类型。今天,我会查看https://doc.rust-lang.org/beta/book/closures.html获取更多信息。 - Devin Jeanpierre

2

问题是:有没有一种优雅的方法来实现闭包,而不需要将堆栈帧分配到堆上并交由垃圾回收器处理?

对于一般情况,垃圾回收是唯一的解决方案。


2

或者干脆不要做垃圾收集。在某些情况下,最好忘记内存泄漏,并在完成后让进程清理它。

根据您对GC的顾虑,您可能会担心定期进行GC扫描。在这种情况下,当项目超出范围或指针更改时,您可以执行选择性GC。但我不确定这会有多昂贵。

@Allen

如果包含函数退出时无法使用闭包,那么闭包有什么用处呢?从我的理解来看,这正是闭包的全部意义所在。


你仍然可以将它传递给你调用的东西。实际上与任何其他堆栈分配的数据结构具有相同的值。我会说这大约是闭包的一半重点。 - Allen
@MikeDunlavey:我认为这里的建议是泄漏所有内存,甚至不提供free函数,这当然不是 Pascal、C、C++ 等语言的工作方式! :-) - J D
@JonHarrop:我看不到你在回复什么评论或答案。我已经写了足够长时间的C/C++代码,并以各种方式使用了所有内存分配设施。我同意Kyle的观点,即在某些情况下,显式释放内存对你毫无益处,反而可能会导致错误。(如果你谈论的是我的差分执行引用,它会自动清理自己。这里有一个新的动画here。) - Mike Dunlavey
据我所知,Claudiu说泄漏所有东西听起来“像是构建编程语言的可怕方式”,而你回答说这“只是没有垃圾收集的所有语言的工作方式”。 - J D
@JonHarrop:好的,我有点盲目了 :) 我想说的是:C和C++并不是糟糕的语言;它们没有垃圾回收。如果程序员选择不使用freedelete,那并不会对语言产生负面影响。这是否反映了程序员的水平则是一个主观问题。希望这样能澄清一些事情。 - Mike Dunlavey
显示剩余3条评论

1

迟做总比不做好?

你可能会对这个感兴趣:差分执行

这是一个鲜为人知的控制结构,其主要用途是编程用户界面,包括在使用过程中可以动态更改的界面。它是模型-视图-控制器范例的重要替代品。

我提到它是因为人们可能认为这样的代码会严重依赖闭包和垃圾回收,但该控制结构的副作用是至少在 UI 代码中消除了这两个问题。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接