[Haskell-cafe] Modelling a mutable variable store

[Derek Elkins]

On Sun, 2007-12-02 at 03:11 +0000, Kannan Goundan wrote:
> 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.

Use ST.  First-class state isn't too great unless you specifically want
that.