Monad Transformers in an Interpeter

Question

I am encountering a problem with Monad Transformers, but I think it's helpful to include some context of how I got to the state I'm currently in, so I'll start with a rough explanation of my program:

The project is an interpreter for a simple (toy) programming language. I have a monad that is used to represent evaluation. It has a definition that looks like:

type Eval a = ReaderT Environment (ExceptT String (State ProgState a))

This works quite nicely, and I can happy write an evaluation function:

eval :: Expr -> Eval Value
eval (Apply l r) = ...
eval ...

The Value datatype has a slight quirk in that I embed Haskell functions of type Value -> EvalM Value. To do this I added a generic type parameter to the definition, which I then instantiate with EvalM:

data Value' m
  = IntVal Int 
  ...
  | Builtin (Value' m -> m (Value' m))

type Value = Value' EvalM

Things were going well, but then I had to write a function that heavily interleaved code using the Eval monad with IO operations. This looked kinda horrendous:

  case runEval ({-- some computation--}) of 
    Right (val, state') -> do
     result <- -- IO stuff here 
     case runEvaL {-- something involving result --} of 
      ...
    Left err -> ...

The function had like 5 levels of nesting, and was also recursive... definitely ugly :(. I hoped adapting to use a Monad Transformer would be the solution:

type EvalT m = ReaderT Environment (ExceptT String (StateT ProgState m))

This refactor was relatively painless: mostly it involved changing type-signatures rather than actual code, however there was a problem: Builtin. Given a expression that was applying argument x to a value of the form Builtin f, the eval function would simply return f x. However, this has type Eval Value, but the refactored eval needs to have type-signature:

eval :: Monad m => EvalT m Value

As far as Fixing this (i.e. making it typecheck) is concerned, I can think of a couple solutions each of which has a problem:

Implementing some kind of analog to lift where I can take Eval a to EvalT m a.
- Problem: I'm not aware of how to do this (or if it's even possible)
Changing the Value type so that it is indexed by an inner monad, i.e. Value m = Value' (EvalT m).
- Problem: now anything containing a Value m has to be parameterized by m. I feel that it would unnecessarily clutters up the type-signatures of anything containing a Value, which is a problem given the initial motivation to do this change was cleaning up my code.

Of course, there may be a much better solution that I haven't thought of yet. Any feedback/suggestions are appreciated :).

How about changing Builtin to contain a value of an ADT describing all possible built-in functions, rather than an actual function? — Fyodor Soikin
– Fyodor Soikin, Commented Oct 16, 2022 at 13:15
Your EvalT looks identical to your Eval to me...? Also, did you perhaps mean type Value = Value' EvalM (rather than data ...)? — Daniel Wagner
– Daniel Wagner, Commented Oct 16, 2022 at 18:06

Daniel Wagner · Accepted Answer · 2022-10-16 18:15:35Z

1

You might like the mmorph package.

-- since State s = StateT s Identity, it's probably also the case
-- that Eval = EvalT Identity, under some light assumptions about
-- typos in the question
liftBuiltin :: Monad m => Eval a -> EvalT m a
liftBuiltin = hoist (hoist (hoist generalize))

Alternately, you could store a polymorphic function in your value. One way would be to parameterize over the transformer.

data Value' t = ... | Builtin (forall m. Monad m => Value' t -> t m (Value' t)
type Value = Value' EvalT

Another is to use mtl-style constraints.

data Value = ... | Builtin (forall m. (MonadReader Environment m, MonadError String m, MonadState ProgState m) => Value -> m Value)

This last one, though verbose, looks pretty nice to me; I'd probably start there.

answered Oct 16, 2022 at 18:15

Daniel Wagner

156k10 gold badges231 silver badges392 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Monad Transformers in an Interpeter

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related