Lexical Scoping是如何实现的？

Question

几年前,我开始为一个领域特定语言编写一个解释器,其中包括程序员定义的函数.

起初,我使用一组简单的符号表实现了变量范围.但现在我想转向适当的词法范围(可选择闭包).任何人都可以解释词法范围背后的数据结构和算法吗？

Answer 1

要在解释器中获得正确的词法作用域和闭包,您需要做的就是遵循以下规则:

• 在您的解释器中,变量总是在调用者传入的环境表中查找或保存为变量,而不是某些全局env-stack.您的评估操作的签名就像eval(expression, env) => value.
• 当解释的代码调用函数时,环境不会传递给该函数.函数应用程序操作的签名就像apply(function, arguments) => value.
• 当调用解释函数时,其身体被评估的环境是进行函数定义的环境,并且与调用者没有任何关系.因此,如果您有一个本地函数,那么它是一个闭包,即包含字段的数据结构{function definition, env-at-definition-time}.

要扩展Python-ish语法中的最后一点:

x = 1
return lambda y: x + y

应该像执行一样执行

x = 1
return make_closure(<AST for "lambda y: x + y">, {"x": x})

其中第二个dict参数可能只是current-env,而不是当时构造的数据结构.(另一方面,保留整个env而不仅仅是关闭的变量可能意味着程序具有令人惊讶的内存泄漏,因为闭包持有不需要的东西.这在任何"实用"语言实现中都是值得修复的,但不是当你只是试验语言语义时.)

Answer 2

有许多不同的方法来实现词法范围.以下是我的一些最爱:

• 如果您不需要超高速的性能,使用纯功能的数据结构来实现你的符号表,并包含一个指向代码的指针符号表一对代表一个嵌套函数.

• 如果您需要本机代码速度,我最喜欢的技术在Simon Marlow和Simon Peyton Jones的制作快速咖喱中有所描述.

• 如果您需要本机代码速度,但curried函数并不重要,请考虑封闭传递样式.

Answer 3

没有单一的正确方法可以做到这一点。重要的是清楚地说明你想要提供的语义，然后数据结构和算法就会随之而来。