记忆、解释器和闭包
所以我正在尝试，并在方案中创建了一种编程语言。我也为它构建了一个解释器，这是下面的大部分代码。
我想重写解释器，以便它用较小的环境构建闭包，即。在构建闭包时，它使用类似于当前环境的环境，但仅保存闭包函数部分中的自由变量。我正在学习记忆，但这很令人困惑。
编辑：我现在正在使用与此相当的球拍，所以如果那里更容易，你应该给我建议。
(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)))
So I'm experimenting, and have a programming language created in scheme. I've built an interpreter for it as well, which is most of the code below.
I'd like to rewrite the interpreter so that it builds closures with smaller environments, ie. when building a closure, it uses an environment that is like the current environment but only holds variables that are free variables in the function part of the closure. I'm learning memoization, but this is confusing.
EDIT: I'm now using a racket equivalent of this, so if it's easier there, you should give me suggestions.
(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)))
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
第一个问题：您的语言中的绑定是否有突变？目前看来您还没有，但也许您正计划添加它。如果你这样做了，那么复制绑定就会带来新的蠕虫病毒。需要额外的间接。
回答你的问题：是的，你当然可以这样做，并且大多数语言实现都可以这样做。这与“空间安全”的属性有关，即闭包避免保留对本来可以收集的大值的引用。
实现这一点非常简单：您可能希望通过对程序进行一次静态传递来用其自由变量来注释每个表达式。在 Racket 中，我可能会构建一个哈希表，将表达式与其自由变量列表相关联。
无论如何，我可以想象大约有七种方式，通过这样做，你可能会意外地使你的语言变得更慢:)。
First question: do you have mutation of bindings in your language? It looks like you don't, currently, but perhaps you're planning to add it. If you do, then copying bindings opens up a new can of worms; additional indirection is required.
Answer to your question: yes, you can certainly do this, and most language implementations do. This is related to the property of being "safe-for-space", whereby closures avoid retaining references to large values that could otherwise be collected.
Implementing this is pretty straightforward: you probably want to annotate every expression with its free variables, by making a single static pass over the program. In Racket, I would probably build a hash table that associates expressions with a list of their free variables.
For what it's worth, I can imagine about seven ways in which you could accidentally make your language quite a bit slower by doing this :).
看起来你想要创建类似平面闭合的东西，或者 Dybvig 所说的“显示闭合”。也就是说，您必须在 lambda 中递归地查找自由变量，然后创建仅包含这些自由变量的闭包表示。
例如，
将创建一个类似于
[code, a]的闭包。请参阅 Dybvig 的方案的三种实施模型，第 88 页。
It looks like you want to create something like flat closures, or what Dybvig called "display closures". That is, you have to recursively find free variables in your lambda, and then create a representation of the closure containing just those free variables.
For example,
would create a closure that looks like
[code, a].Take a look at Dybvig's Three Implementation Models for Scheme, page 88.
如果您不介意阅读一些 Haskell，在 48 小时内为自己编写一个方案演示了如何创建闭包：当遇到
(lambda ...)表达式时，它的闭包被简单地设置为当前环境（从名称到值的绑定列表）。当计算 lambda 时，它的主体是在该闭包加上参数绑定的上下文中计算的，当然不是当前环境。听起来你想要做的是剔除成为闭包的环境，也许是为了效率。为此，您可以在函数中搜索名称，并仅保留那些未出现在参数列表中的名称。然而，这可能有点过分，因为 lambda 使用的每个名称（除了它的参数）都需要出现在闭包中。因此，我建议简单地参考您已经拥有的环境，其中大部分无论如何都会共享。
If you don’t mind reading some Haskell, Write Yourself a Scheme in 48 Hours demonstrates how closures are created: when a
(lambda ...)expression is encountered, its closure is simply set to the current environment (a list of bindings from names to values). When a lambda is evaluated, its body is evaluated in the context of that closure plus the argument bindings—not, of course, the current environment.It sounds like what you want to do is cull the environment that becomes the closure, perhaps for the sake of efficiency. To do this, you could search the function for names, and keep only those that don’t appear in the argument list. However, this may be excessive, as every name the lambda uses—except for its arguments—will need to appear in the closure. As such, I suggest simply referring to the environment that you already have, most of which will be shared anyway.