#+title: implementing Lisp scope and closure
- tags :: [[file:20200604222651-lisp.org][Lisp]] [[file:20210314131218-dial.org][Dial]] [[file:20210403130721-dial_implementation.org][Dial implementation]] [[file:20200705154112-rust.org][Rust]]

In implementing a Lisp, there is the problem of scope and closure.

* Memory efficiency
Since we are making a programming language, we'd want our language's interpreter
to be as efficient as possible[fn:1]. Therefore we should try to reduce cloning
data as much as possible. This could be achieved with the use of =RefCell= in
Rust.
* Scopes
How do we deal with scoping in general? Consider the following:

#+begin_src lisp :eval never
(def x (fn (a) + a 10)
#+end_src

How do we implement this without =a= conflicting with something at a higher
level?

** Possible solutions
*** Recursive =env=
MAL and Risp define an env as such, essentially:
#+begin_src rust :eval never
struct Env {
    bindings: HashMap<String, Val>
    outer: Option<Env>,
}
#+end_src

There are a couple of concerns I have with this. Once you start introducing
lifetimes, this becomes quite complicated.
*** Flat table
[[file:literature/20210307152720-lisp_in_small_pieces.org][Lisp in Small Pieces]] implies that one way to store variables would be to store
them all in the same place as one collection. This would perhaps make lookup
more complicated.

#+begin_src rust :eval never
struct Env {
    bindings: HashMap<String, Binding>
}

struct Binding {
    val: Val,
    scope: usize, // (ref:scope)
}
#+end_src

Here [[(scope)]] would be a reference to something that provides information about
how it could be accessed. This might make memory management simpler but would
make lookup complicated, as each scope would need to know:

- its own ID
- its parent ID
- if its a valid reference
- what values shadow it

These problems can be sidestepped with [[Recursive =env=]].
* Tail-call problem
If our interpreter is rewritten to essentially be one big =while= loop, scope
and garbage collection becomes a problem.

At the end of each iteration of the loop, we need to clear any values that
should go out of scope. For example, if our =eval= function evaluates the
following:

#+begin_src lisp :eval never
((lambda (a b) + a b) 1 2)
#+end_src

We would need =a= and =b= to not live beyond the =lambda= and have the =lambda=
not persist after its evaluation.
* Footnotes
[fn:1] Ideally Dial will compile to machine code as well, where this will
hopefully be less of an issue.