Using IORef for environment of interpreter [Write yourself a Scheme in 48 hours]

userMkII 0
Viewed 75

In chapter 7 of the very nice Write yourself a Scheme in 48 hours an environment for handling variables in the interpreted language (Scheme, where variables are mutable) is introduced as

type Env = IORef [(String, IORef LispVal)]

-- where LispVal is a simple type representing a lisp value:
data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | String String
             | Bool Bool

non tl;dr (tl;dr below)

There is a reason given why the State monad isn't a good choice (environments will get passed around and eventually need to exist 'outside' of runState) so IORef is chosen instead. However, I wondered why one wouldn't just represent as an environment with Map String LispVal? In my (limited) understanding about how GHC compiles our programs if we later changed a variable with Map.insert that shouldn't copy the entire map at all. So is the mutability of IORef here really needed? In other words, is it obvious that IORef is the way to go here? Moreover, I had the impression that IORef was best to be avoided if possible and a typical use case was to 'leak' values from something like a callback in a foreign framework.

I struggled to come up with a good experiment on comparing performance between the two alternatives, though. It seems that the GHC optimizes my deterministic repeated calls too well.

tl;dr

  1. Is it that obvious to use IORef in the example above, both in terms of performance and other caveats (mutability, IO in code that would otherwise be pure)?
  2. Is using Map String LispVal a bad choice here if we expect frequent changes using insert or insertWith?
haskell
1 Answers

  1. Map String LispVal is obviously better than [(String, LispVal)]. The only reason to use a list is tradition: Scheme interpreters are famously minimalist, and often implemented in Scheme, where the basic data structure is a pair, from which association lists can be easily built, but maps would require much more work. If you have easy access to a real map in your implementation language, use it, unless you like to pretend it's still the 1970s.

  2. For the types of LispVal you have defined so far, there's no real need for any IORefs. I think the author is using IORef in preparation for handling lambdas and closures. A closure will capture an Env for its environment. If implemented as you imagine, with no IORefs, then something like

    (let ((x 1))
  (let ((f (lambda () x)))
    (set! x 2)
    (f)))

    would have to return 1, while 2 is the desired result. The interpreter needs a way for set! expressions to modify environments that have already been captured.

    I haven't thought super hard about whether you really need two layers of IORef for this, or whether one would be sufficient. Probably the authors of this book have, though.

amalloy0
Related