dsl - 以自定义语言实现“生成器”支持

Question

我在语言设计上有点偏爱，目前正在玩自己的业余语言。 (http://rogeralsing.com/2010/04/14/playing-with-plastic/)

真正让我流血的一件事是“发电机”和“收益”关键字。
我知道C#使用AST转换将枚举器方法转换为状态机。

但是它如何在其他语言中工作？
有什么方法可以在不进行AST转换的语言中获得生成器支持？
例如是否像Python或Ruby这样的语言依靠AST转换来解决此问题？

(问题是如何在幕后用不同的语言实现生成器，而不是如何用其中一种语言编写生成器)

Answer 1

生成器基本上是半协程，具有一些令人讨厌的限制。因此，显然，您可以使用半协程(当然还有完整协程)来实现它们。

如果没有协程，则可以使用任何其他通用控制流构造。有许多控制流结构是“通用的”，因为每个控制流结构(包括所有其他通用控制流结构)(包括协程)都可以(或多或少)琐碎地转换成仅通用的构造。

其中最著名的可能是GOTO。仅使用GOTO，您就可以构建任何其他控制流构造:IF-THEN-ELSE，WHILE，FOR，REPEAT-UNTIL，FOREACH，异常，线程，子例程调用，方法调用，函数调用等，当然还有协程和生成器。

几乎所有的CPU都支持GOTO(尽管在CPU中通常将其称为jmp)。实际上，在许多CPU中，GOTO是唯一的控制流构造，尽管今天通常至少本地支持子例程调用(call)以及某些原始形式的异常处理和/或并发原语(compare-and-swap)。内置的。

另一个众所周知的控制流原语是延续。基本上，延续是GOTO的结构化更好，更易于管理且不那么邪恶的变体，在功能语言中尤其流行。但是，也有一些低级语言将控制流基于连续性，例如Parrot虚拟机将连续性用于控制流，我相信某些研究实验室甚至在某个地方甚至有一些基于连续性的CPU。

C具有某种“cr脚”形式的延续(setjmp和longjmp)，其功能远不如“真实”延续那么强大，并且不易使用，但是它们足够强大，可以实现生成器(实际上，可以用于实现完整的延续)。

在Unix平台上，setcontext可以用作setjmp / longjmp的更强大，更高级的替代方法。

另一个众所周知的控制流程构造是例外，但它可能不会引起人们的注意，因为底层的基础构造其他控制流程构造除外。有一篇论文表明，异常可能比延续更强大，因此使异常在本质上等效于GOTO，因此具有普遍的功能。而且，实际上，有时将异常用作通用的控制流构造:Microsoft Volta项目将.NET字节码编译为JavaScript，并使用JavaScript异常来实现.NET线程和生成器。

这不是通用的，但可能足够强大以实现生成器，只是普通的尾部调用优化。 (不过，我可能是错的。不幸的是，我没有证据。)我认为您可以将生成器转换为一组相互尾部递归的函数。我知道状态机可以使用尾部调用来实现，因此我很确定生成器也可以，因为毕竟C#将生成器实现为状态机。 (我认为这与惰性评估特别有效。)

最后但并非最不重要的一点是，在具有标准化调用堆栈的语言中(例如，像大多数Smalltalks一样)，您可以构建几乎所需的任何类型的控制流构造。 (实际上，标准化的调用堆栈基本上是过程上的低端等效于功能上的高层延续。)

那么，生成器的其他实现是什么样的？

Lua本身没有生成器，但是具有完整的不对称协程。主要的C实现使用setjmp / longjmp来实现它们。

Ruby本身也没有生成器，但是它具有Enumerator，可以用作生成器。 Enumerator不是语言的一部分，它们是一种库功能。 MRI使用延续来实现Enumerator，而延续则通过setjmp / longjmp来实现。 YARV使用Enumerator(这是Ruby拼写“协程”的方式)实现Fiber，而这些使用setjmp / longjmp实现。我相信JRuby当前使用线程来实现Enumerator，但是他们希望在JVM获得更好的控制流构造后立即切换到更好的状态。

Python的生成器实际上或多或少是成熟的协程。 CPython使用setjmp / longjmp实现它们。