Memoirs, Translators, and Closing

Question

So, I experiment and create a programming language created in the circuit. I also built an interpreter for it, which is part of the code below.

I would like to rewrite the interpreter so that it creates closures with smaller environments, i.e. when constructing a closure, it uses an environment that is similar to the current environment, but contains only variables that are free variables in the functional part of the closure. I am learning memoization, but it is confusing.

EDIT: I now use the equivalent of a racket, so if it's easier, you should give me suggestions.

(define-struct var (string)) ;; a variable, eg, (make-var "foo") (define-struct int (num)) ;; a constant number, eg, (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))) 

Answer 1

First question: do you have a mutation of bindings in your language? It doesn't seem like you are doing this, but maybe you are planning on adding it. If you do this, copying the bindings will open a new can of worms; additional indirectness is required.

Answer your question: yes, you can do this, and most language implementations. This is due to the fact that it is "safe for space", in which the closure does not allow you to save links to large values ​​that might otherwise be collected.

The implementation of this is quite simple: you probably want to annotate each expression with your free variables by making one static run 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 present about seven ways in which you could make your language a little slower by doing this :).

Answer 2

It sounds like you want to create something like flat closures or what Dybvig called "screen closures." That is, you must recursively find free variables in your lambda, and then create a closure view containing only these free variables.

For instance,

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

will create a closure that looks like [code, a] .

Take a look at Dybvig's Three Implementation Models for a Scheme , page 88.

Answer 3

If you don’t read any Haskell, write yourself a diagram in 48 hours , demonstrate how closures are created: when the expression (lambda ...) encounters its closure, the current environment is simply set (a list of bindings from names to values). When a lambda is computed, its body is evaluated in the context of this closure plus argument bindings - not, of course, the current environment.

It seems that what you want to do is to discard the environment, which will become a closure, perhaps for the sake of efficiency. To do this, you can search for a function for names and save only those that do not appear in the argument list. However, this can be excessive, since every name that a lambda uses, except for its arguments, should appear in closure. Therefore, I suggest simply referring to the environment that you already have, most of which will be shared anyway.