[Haskell-cafe] Modelling a mutable variable store

Kannan Goundan cakoose at yahoo.com
Sat Dec 1 22:11:46 EST 2007

I'm implementing an interpreter for the lambda calculus augmented with 
mutable variables.  I'm having problems doing the mutable state stuff in 
Haskell.  Here's what I have so far:

  type Expr    = ... terms in the language ...
  type Value   = ... values in the language ...
  type Ident   = String
  type VarId   = String

  type Env = Map Ident Target
  data Target = TValue Value | TVar VarId
    -- idents might refer to values or vars in the store.

  type Store = Map VarId (Maybe Value)
    -- Using "Maybe" because vars start out uninitialized.

  eval :: (Env, Store, Expr) -> (Store, Value)
    -- The Store is threaded through the evaluator.

One problem is that the link between an identifier and it's entry in the 
store is via VarIds, which are just strings.  For example, if I see the 
identifier "x", I first look it up in the Env, and if it is a "TVar", I 
then look it up in the store.  I'd like to get something stronger (in 
Java, I would use a pointer).  

Another problem is that entries in my Store never get garbage collected.  
Again, if I were using pointers in Java, this wouldn't be an issue.

There's also the issue of finding a more elegant way of threading the 
Store through my evaluator, but I'm not concerned too much about that at 
this point.  I can probably define a state-carrying monad like Parsec.  
My real concerns are the first two issues.


- Kannan

More information about the Haskell-Cafe mailing list