In the starting post of this series I describe a test case (a function evaluator) and a method to tackle its implementation by writing a complex monad in plain Haskell, built as a pile of transformers. All this from the ground up, without importing any library (except basic stuff like
Data.Map and alike) and following the lines described in a presentation by Henrik Nilsson.
All code is available in GitHub, fully covered by tests.
The first implementation, not even monadic, crashes at the tiniest problem. Therefore, the first onion layer is gonna be an error-handling monad transformer but, before starting, we need to have a round core to cover.
Every onion starts from a round soft core
Before covering the onion with the various transformer layers, we must put a monad at the heart of the construction.
Because of the quirky nature of Haskell mtl uses
IO, we’ll use
Identity instead, as we like to keep things simple.
The first step must be therefore to define
I, the Identity monad, plus the unwrapper and the runner (which in this case are the same thing):
newtype I a = I a deriving (Show, Read, Eq) -- unwrap the monad unI :: I a -> a unI (I a) = a -- run the monad runI :: I a -> a runI = unI instance Monad I where return = I ia >>= faib = faib (unI ia)
The running code contains also the definition of the Functor and Applicative instances, so to keep GHC happy without having to invoke any mysterious compiler spell.
The monadic evaluation function
eval1 will just box/unbox stuff while walking through the same algo seen previously, and will crash just as often as before:
eval1 :: Env -> Exp -> I Value eval1 env (Lit i) = return $ IntVal i eval1 env (Var name) = return $ fromJust $ Map.lookup name env eval1 env (Plus e1 e2) = do (IntVal i1) <- eval1 env e1 (IntVal i2) <- eval1 env e2 return $ IntVal $ i1 + i2 eval1 env (Lambda argname body) = return $ FunVal argname body env eval1 env (App lambda expr) = let (FunVal argname body env') = unI $ eval1 env lambda val = unI $ eval1 env expr in eval1 (Map.insert argname val env') body
After that, we’ll use the unbox function one final time to extract the
runEval1 :: I Value -> Value runEval1 = unI
All this is to be seen in action by running TestNilsson_01.hs in GHC.
The first onion layer handles errors coming out from the Identity core
Next we place an error-handling monad transformer around
I. Usually it is
ErrorT, based on
Either String, but Nilsson chooses an
ET (shorter name to avoid any possible clash with mtl) which is actually the transformer
MaybeT. In case of error we’ll avoid crashes, but there will be no specific error message.
newtype ET m a = ET (m (Maybe a)) deriving instance Show (m (Maybe a)) => Show (ET m a) deriving instance Eq (m (Maybe a)) => Eq (ET m a)
In our testcase, we’ll have an
ET I Value = ET (I (Maybe Value)). The boxed result will either be a
Just Value or a
The definition of the error monad instance produced by the
ET transformer is the following:
instance (Monad m) => Monad (ET m) where return a = ET (return (Just a)) etma >>= faetmb = ET $ do maybea <- unET etma case maybea of Just a -> unET (faetmb a) Nothing -> return Nothing
As usual, the running code contains the functor and applicative instances as well, along with the unwrapper and the runner.
eval2 evaluating function with error handling is ready:
eval2 :: Env -> Exp -> ET I Value -- ET I (Maybe Value) eval2 env (Lit i) = return $ IntVal i eval2 env (Var name) = case (Map.lookup name env) of Just v -> return v Nothing -> eFail eval2 env (Plus e1 e2) = do v1 <- eval2 env e1 v2 <- eval2 env e2 case (v1, v2) of (IntVal i1, IntVal i2) -> return $ IntVal $ i1 + i2 _ -> eFail eval2 env (Lambda argname body) = return $ FunVal argname body env eval2 env (App lambda expr) = do v1 <- eval2 env lambda v2 <- eval2 env expr case v1 of FunVal argname body env' -> eval2 (Map.insert argname v2 env') body _ -> eFail
The traits of a generic error handler…
The definition of
eFail is not part of
ET m (for a monad you only need
bind); it is part of that typeclass which in Haskell is called a
MonadError. Nilsson calls it
MonadErrors do for a living is:
- fail gently
- provide a
catchinstruction in case a
We all want
ET m to be member of typeclass
E, of course…
-- kind of MonadError class (Monad m) => E m where eFail :: m a -- save the day returning a monad anyhow eHandle :: m a -> m a -> m a --tryclause->catchclause->pick_one instance (Monad m) => E (ET m) where eFail = ET (return Nothing) eHandle tryetma catchetma = ET $ do maybetry <- unET tryetma case maybetry of Just _ -> return maybetry Nothing -> unET catchetma
For the first time we have tests that can handle failures as well.
…and those of a monad transformer
There’s nothing done so far that makes
ET pluggable as member of a pile of monad transformers. Using once more the onion analogy (which is kinda becoming boring) there will be more layers coming. Computations at those levels will certainly not implement error handling and will want instead to call
ET each time something goes awry.
ET has to play ball.
What makes any monad transformer capable of working alongside other transformers is the shared belonging to the
MonadTrans typeclass, which Nilsson calls
MonadTransformer. This means implementing a
lift takes whatever monad from the underlying layer and makes it runnable up here. In the case of
ET it’s just a matter of unboxing/boxing:
instance (Monad m) => MonadTransformer ET m where lift :: m a -> ET m a -- ET m a = ET m (Maybe a) lift ma = ET $ do a <- ma return (Just a)
and, if you prefer it with no sugar…
lift ma = ET $ ma >>= \a -> return (Just a)
The monadic expression evaluator won’t crash anymore and its error-recovering magic will be callable from every layer of the onion by implementing
lift at each level.
In the next installment of this series we will add the capability to handle state; this will allow to record many interesting things happening during the evaluation of a complex expression.