title: Memoization, Interpreters, and Closures
body: <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. </p>
  
  <p>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.</p>
  
  <p>EDIT: I'm now using a racket equivalent of this, so if it's easier there, you should give me suggestions.</p>
  
  <pre><code>(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)))
  </code></pre>