While working on the code generator for my compiler construction class, I ran across a rather somewhat sticky issue. I am using a state monad to store code as it is generated. This allows me to very quickly build up sequences generated from an AST. However, for conditional instructions, I needed a jump location, which depends on the length of code generated *after* the conditional. There are several ways I could do this, but the solution I invented allows me to generate the code and then 'rewind', knowing the length of the code, and generating the jump instruction.
I'm only going to demonstrate instances that I used in my code generator here, as I have not taken the time to write any others. I also haven't spent a lot of time verifying correctness or elegance, so I'd love to hear about any mistakes in the comments.
class Monad m => MonadAttempt m where
attempt :: a -> m a -> m a
The MonadAttempt class defines 'attempt', which takes a default value and monadic action, and returns the result of the monadic action without its side effects, or the monadic action returning the default value if the input action fails.
instance MonadAttempt Identity where
attempt _ m = m
The instance for the Identity monad is trivial. There are no side effects, so we can simply produce the action.
instance (Monad m, MonadAttempt m) => MonadAttempt (StateT s m) where
attempt a m = do s <- get
(x, _) <- lift $ attempt (a, s) $ runStateT m s
return x
I suppose a more elegant solution would be a do block to extract just the return value from runStateT, but this worked for what I needed. runStateT is used to isolate the side effects, the transformed monad is recursively attempted with a new default value, and the the result is then lifted. But since lift is pure in the transformer (not necessarily the transformed) monad, the state is not updated, and we can extract just the value. (Note that we explicitly get the state and then use it to run the monad.)
instance (Error e, Monad m, MonadAttempt m) => MonadAttempt (ErrorT e m) where
attempt a m = do e <- lift $ attempt (Right a) $ runErrorT m
case e of
Left _ -> return a
Right x -> return x
For ErrorT, we attempt the computation, return its result if we can, and if not, return the default value. Again, a do block for extracting the value is probably in order.
I will try to rewrite the StateT and ErrorT instances tomorrow such that they pass the same value to the recursive attempt calls (down the monad transformer stack). If I'm successful I'll post it here.
Update: I've posted corrected instances.
