loading...

Using the Writer monad to refactor my interpreter

dwayne profile image Dwayne Crooks ・3 min read

I recently started back working through EoPL and yesterday I solved exercise 3.15.

Extend the language by adding a new operation print that takes one argument, prints it, and returns the integer 1. Why is this operation not expressible in our specification framework?

Since I'm using Haskell to complete these exercises this one presented a unique challenge because print is not a pure function.

To solve it I decided to change the type of my interpreter from

valueOfProgram :: Program -> Value

to

valueOfProgram :: Program -> (Value, String)

but this had significant consequences on the readability of my code.

run :: String -> (Value, String)
run = valueOfProgram . parse

valueOfProgram :: Program -> (Value, String)
valueOfProgram (Program expr) =
  valueOfExpr expr initEnv
  where
    initEnv =
      Env.extend "i" (NumberVal 1)
        (Env.extend "v" (NumberVal 5)
          (Env.extend "x" (NumberVal 10)
            Env.empty))

valueOfExpr :: Expr -> Environment -> (Value, String)
valueOfExpr expr env =
  case expr of
    Const n ->
      (NumberVal n, "")

    Var v ->
      (Env.apply env v, "")

    Diff a b ->
      let
        (aVal, s) = valueOfExpr a env
        (bVal, t) = valueOfExpr b env
      in
        (NumberVal (toNumber aVal - toNumber bVal), s ++ t)

    Zero e ->
      let
        (val, s) = valueOfExpr e env
      in
        (BoolVal (toNumber val == 0), s)

    If test consequent alternative ->
      let
        (testVal, s) = valueOfExpr test env
      in
        if (toBool testVal) then
          let
            (result, t) = valueOfExpr consequent env
          in
            (result, s ++ t)
        else
          let
            (result, t) = valueOfExpr alternative env
          in
            (result, s ++ t)

    Let var e body ->
      let
        (val, s) = valueOfExpr e env
        (result, t) = valueOfExpr body (Env.extend var val env)
      in
        (result, s ++ t)

    Print e ->
      let
        (val, s) = valueOfExpr e env
      in
        (NumberVal 1, s ++ show val ++ "\n")

See the full change here.

You see all the drudgery involved to ensure that the output string gets handled correctly.

I was able to use the Writer monad to hide all that drudgery and improve the readability of my code.

Look at it now.

run :: String -> (Value, String)
run = runWriter . valueOfProgram . parse

valueOfProgram :: Program -> Writer String Value
valueOfProgram (Program expr) =
  valueOfExpr expr initEnv
  where
    initEnv =
      Env.extend "i" (NumberVal 1)
        (Env.extend "v" (NumberVal 5)
          (Env.extend "x" (NumberVal 10)
            Env.empty))

valueOfExpr :: Expr -> Environment -> Writer String Value
valueOfExpr expr env =
  case expr of
    Const n ->
      return $ NumberVal n

    Var v ->
      return $ Env.apply env v

    Diff a b -> do
      aVal <- valueOfExpr a env
      bVal <- valueOfExpr b env
      return $ NumberVal (toNumber aVal - toNumber bVal)

    Zero e -> do
      val <- valueOfExpr e env
      return $ BoolVal (toNumber val == 0)

    If test consequent alternative -> do
      testVal <- valueOfExpr test env

      if (toBool testVal) then
        valueOfExpr consequent env
      else
        valueOfExpr alternative env

    Let var e body -> do
      val <- valueOfExpr e env
      valueOfExpr body (Env.extend var val env)

    Print e -> do
      val <- valueOfExpr e env

      tell $ show val ++ "\n"

      return $ NumberVal 1

See the full change here.

Takeaways

  1. Write the most obvious Haskell code that solves the problem. Don't worry about what's the best way to do it in Haskell at this point.

  2. Write tests to ensure the code works as expected.

  3. Refactor the code. At this point you have well tested working code but you think you can do better. Now is the best time to learn what techniques or ideas can help you improve the code. Read widely and expand your knowledge of Haskell.

P.S. This was not a post about how to use the Writer monad. It was a post about how the Writer monad helped me to write clearer Haskell code. To learn about the Writer monad I'd recommend the book "Haskell Programming from First Principles".

Posted on Mar 27 by:

dwayne profile

Dwayne Crooks

@dwayne

A full stack web developer who has an interest in programming language theory, interpreters, compilers and type theory. I enjoy programming with Elm and Haskell in my free time.

Discussion

markdown guide