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.