备忘录技术、解释器和闭包

Question

我正在进行实验，并使用Scheme语言创建了一种编程语言。我还为其构建了一个解释器，下面的大部分代码都是解释器的代码。

我希望重新编写解释器，以便使用更小的环境构建闭包。即，在构建闭包时，它使用的环境类似于当前环境，但仅包含函数部分中的自由变量。我正在学习记忆化，但这很困惑。

编辑：我现在正在使用Racket的等效版本，如果在那里更容易，请给我建议。

(define-struct var (string)) ;; a variable, e.g., (make-var "foo")
(define-struct int (num)) ;; a constant number, e.g., (make-int 17)
(define-struct add (e1 e2)) ;; add two expressions
(define-struct fun (name formal body)) ;; a recursive 1-argument function
(define-struct closure (fun env)) ;; closures (made at run-time)

(define (envlookup env str)
    (cond [(null? env) (error "unbound variable during evaluation" str)]
        [(equal? (caar env) str) (cdar env)]
        [#t (envlookup (cdr env) str)]))

(define (eval-prog p)
    (letrec
        ([f (lambda (env p)
            (cond [(var? p) (envlookup env (var-string p))]
                    [(int? p) p]
                    [(add? p) (let ([v1 (f env (add-e1 p))]
                                    [v2 (f env (add-e2 p))])
                                        (if (and (int? v1) (int? v2))
                                            (make-int (+ (int-num v1) (int-num v2)))
                                            (error "TTPL addition applied to non-number")))]
                    [(fun? p) (make-closure p env)]
                    [(closure? p) p]
                    [#t (error "bad TTPL expression")]))])
    (f () p)))

- user998876

Answer 1

第一个问题：你的语言中是否有绑定的变异？目前看起来好像没有，但也许你正在计划添加。如果有的话，复制绑定会带来新的问题；需要额外的间接性。

回答你的问题：是的，你当然可以这样做，大多数语言实现都可以。这与“安全-for-space”的属性有关，其中闭包避免保留对可能被收集的大值的引用。

实现这个很简单：你可能想要通过在程序上进行单个静态传递来注释每个表达式的自由变量。在Racket中，我可能会建立一个哈希表，将表达式与它们的自由变量列表相关联。

值得一提的是，我可以想象出大约七种方法，通过这样做，你可能会意外地使你的语言变得更慢 :）。

- John Clements

Answer 2

看起来您想创建类似于平面闭包或Dybvig所称的“显示闭包”的东西。也就是说，您必须递归地查找lambda中的自由变量，然后创建一个仅包含这些自由变量的闭包表示。

例如，

((lambda (x) (lambda (f) (f x))) a)

将会创建一个类似于 [code, a] 的闭包。

请看 Dybvig 的 Scheme的三种实现模型，第88页。

- erjiang

Answer 3

如果您不介意阅读一些Haskell，48小时内编写自己的Scheme演示了闭包是如何创建的：当遇到(lambda ...)表达式时，它的闭包就被设置为当前环境（名称到值的绑定列表）。当一个lambda被评估时，它的主体在该闭包加上参数绑定的上下文中进行评估，而不是当前环境。

听起来你想要做的是整理成闭包的环境，也许是为了提高效率。为此，您可以搜索函数以查找名称，并仅保留那些未出现在参数列表中的名称。然而，这可能过于夸张，因为除了其参数之外，lambda使用的每个名称都需要出现在闭包中。因此，我建议简单地引用您已经拥有的环境，其中大部分将会共享。

- Jon Purdy