Haskell - Monad Transformers - Limit number of evaluations in an interpreter

Question

I'm learning Monad Transformers and decided to write an interpreter for a simple language(with loop constructs) similar to Brainfuck using Monad Transformers. I would like to terminate the interpreter after certain number of statements.

This simple language is made of single memory cell capable of holding an Int and 5 instructions Input, Output, Increment, Decrement and Loop. A loop terminates when value in the memory is zero. Input is read from a list and similarly output is written to another list. Increment and Decrement does +1 and -1 to memory correspondingly.

I'm using World type to keep track of input, output (streams) and memory, Sum Int to count number of instructions evaluated. Except World to terminate evaluation after certain statements.

module Transformers where

import qualified Data.Map                      as Map
import           Data.Maybe
import           Control.Monad.State.Lazy
import           Control.Monad.Writer.Lazy
import           Control.Monad.Except


data Term = Input
  | Output
  | Increment
  | Decrement
  | Loop [Term]
  deriving (Show)

data World = World {
  inp :: [Int],
  out :: [Int],
  mem :: Int
} deriving Show

op_limit = 5

loop
  :: [Term]
  -> StateT World (WriterT (Sum Int) (Except World)) ()
  -> StateT World (WriterT (Sum Int) (Except World)) ()
loop terms sp = sp >> do
  s <- get
  if mem s == 0 then put s else loop terms (foldM (\_ t -> eval t) () terms)

limit :: StateT World (WriterT (Sum Int) (Except World)) ()
limit = do
  (s, count) <- listen get
  when (count >= op_limit) $ throwError s

tick :: StateT World (WriterT (Sum Int) (Except World)) ()
tick = tell 1

eval :: Term -> StateT World (WriterT (Sum Int) (Except World)) ()
eval Input =
  limit >> tick >> modify (\s -> s { inp = tail (inp s), mem = head (inp s) })
eval Output       = limit >> tick >> modify (\s -> s { out = mem s : out s })
eval Increment    = limit >> tick >> modify (\s -> s { mem = mem s + 1 })
eval Decrement    = limit >> tick >> modify (\s -> s { mem = mem s - 1 })
eval (Loop terms) = loop terms (void get)

type Instructions = [Term]

interp :: Instructions -> World -> Either World (World, Sum Int)
interp insts w =
  let sp = foldM (\_ inst -> eval inst) () insts
  in  runExcept (runWriterT (execStateT sp w))

Example run in ghci:

*Transformers> interp [Loop [Output, Decrement]]  $ World [] [] 5
Right (World {inp = [], out = [1,2,3,4,5], mem = 0},Sum {getSum = 10})

The monad limit based on count and should decide to either Fail with current state or do nothing. But I noticed that count in (s, count) <- listen get is always zero. I don't understand why is this happening. Please help me understand where I went wrong.

Is my ordering of transformers in the stack correct? Are there any rules (informal) to decide the layering?

I only gave a quick look, but it seems that you want to read your "number of statements", which currently is modeled with a writer monad. If so, don't use the writer monad since you need to read. Put your counter in your world state, and remove the writer layer. — chi

danidiaz danidiaz · Accepted Answer · 2018-11-25T21:31:48

Computations inside the Writer monad can't have access to their own accumulator. What's more: the accumulator is never forced while the computation runs, not even to WHNF. This applies to both the strict and lazy variants of Writer—the strict variant is strict in a sense unrelated to the accumulator. This unavoidable laziness in the accumulator can be a source of space leaks if the computation runs for too long.

Your limit function is not branching on the value of the "mainline" WriterT accumulator. The get action (you are using mtl) simply reads the state from the StateT layer, and performs no effects in the other layers: it adds mempty to its WriterT accumulator an throws no error.

Then, the listen extracts the Writer accumulator of the get action (only of the get, not of the whole computation) and adds it to the "mainline" accumulator. But this extracted value (the one returned in the tuple) will always be mempty, that is, Sum 0!

Instead of WriterT, you could put the counter in the StateT state, as @chi has mentioned. You could also use AccumT, which is very similar to WriterT but lets you inspect the accumulator (it also lets you force it to WHNF using bang patterns).

AccumT doesn't seem to have a corresponding mtl typeclass though, so you'll need to sprinkle a few lifts in order to use it.

Haskell - Monad Transformers - Limit number of evaluations in an interpreter

1 Answers