title: Creating an Interpreter in Haskell
body: <p>So, I need to write a function <code>evalS :: Statement -&gt; Store -&gt; Store</code> that takes as input a statement and a store and returns a possibly modified store.</p>
  
  <p>The following case has been given to me:</p>
  
  <pre><code>evalS w@(While e s1) s = case (evalE e s) of
                            (BoolVal True,s')  -&gt; let s'' = evalS s1 s' in evalS w s''
                            (BoolVal False,s') -&gt; s'
                            _                  -&gt; error "Condition must be a BoolVal 
  </code></pre>
  
  <p><strong>And I need to write:</strong></p>
  
  <pre><code>evalS Skip s             = ...
  evalS (Expr e) s         = ...
  evalS (Sequence s1 s2) s = ...
  evalS (If e s1 s2) s     = ...
  </code></pre>
  
  <p>In the If case, if e evaluates to a non-boolean value, I need to throw an error using the error function.</p>
  
  <p><strong>Sample input/output:</strong></p>
  
  <pre><code>&gt; run stmtParser "x=1+1" evalS
  fromList [("x",2)]
  &gt; run stmtParser "x = 2; x = x + 3" evalS
  fromList [("x",5)]
  &gt; run stmtParser "if true then x = 1 else x = 2 end" evalS
  fromList [("x",1)]
  &gt; run stmtParser "x=2; y=x + 3; if y &lt; 4 then z = true else z = false end" evalS
  fromList [("x",2),("y",5),("z",false)]
  &gt; run stmtParser "x = 1; while x &lt; 3 do x = x + 1 end" evalS
  fromList [("x",3)]
  &gt; run stmtParser "x = 1 ; y = 1; while x &lt; 5 do x = x + 1 ; y = y * x end" evalS
  fromList [("x",5),("y",120)] 
  </code></pre>
  
  <p><strong>Code for stmtParser:</strong></p>
  
  <pre><code>-- Sequence of statements
  stmtParser :: Parser Statement
  stmtParser = stmtParser1 `chainl1` (P.semi lexer &gt;&gt; return Sequence)
  
  -- Single statements
  stmtParser1 :: Parser Statement
  stmtParser1 = (Expr &lt;$&gt; exprParser)
            &lt;|&gt; do
                P.reserved lexer "if"
                cond &lt;- exprParser
                P.reserved lexer "then"
                the &lt;- stmtParser
                P.reserved lexer "else"
                els &lt;- stmtParser
                P.reserved lexer "end"
                return (If cond the els)
            &lt;|&gt; do
                P.reserved lexer "while"
                cond &lt;- exprParser
                P.reserved lexer "do"
                body &lt;- stmtParser
                P.reserved lexer "end"
                return (While cond body)
  </code></pre>
  
  <p><strong>WHAT I'VE TRIED:</strong></p>
  
  <p>I am not sure if I need to use evalE in this problem or not. I have written it in a previous problem. The signature for evalE is <code>evalE :: Expression -&gt; Store -&gt; (Value, Store)</code> and asked me to write:</p>
  
  <pre><code>evalE (Var x) s = ...
  evalE (Val v) s = ...
  evalE (Assignment x e) s = ...
  </code></pre>
  
  <p>I have done the above, already.</p>
  
  <p><strong>ATTEMPT:</strong></p>
  
  <pre><code>evalS Skip s             = show s -- I am assuming that since Skip returns an empty String, I just need to return an empty String.
  evalS (Sequence s1 s2) s = evalS s1 &gt;&gt; evalS s2 -- sequence1 then sequence2. I am not quite sure what to do with the s.
  evalS (Expr e) s         = ... Not sure what to do, here.
  evalS (If e s1 s2) s     = do
     x &lt;- evalE e
     case x of
        BoolVal True -&gt; evalS s1
        BoolVal False -&gt; evalS s2
  </code></pre>
  
  <p>I am having trouble writing the above statements.</p>
  
  <p><strong>For reference, here is the entire skeleton that was given to me to work with:</strong></p>
  
  <pre><code>-- Necessary imports
  import Control.Applicative ((&lt;$&gt;),liftA,liftA2)
  import Data.Map
  import Text.Parsec
  import Text.Parsec.Expr
  import Text.Parsec.Language (emptyDef)
  import Text.Parsec.String (Parser)
  import qualified Text.Parsec.Token as P
  
  
  --------- AST Nodes ---------
  
  -- Variables are identified by their name as string
  type Variable = String
  
  -- Values are either integers or booleans
  data Value = IntVal Int       -- Integer value
             | BoolVal Bool     -- Boolean value
  
  -- Expressions are variables, literal values, unary and binary operations
  data Expression = Var Variable                    -- e.g. x
                  | Val Value                       -- e.g. 2
                  | BinOp Op Expression Expression  -- e.g. x + 3
                  | Assignment Variable Expression  -- e.g. x = 3
  
  -- Statements are expressions, conditionals, while loops and sequences
  data Statement = Expr Expression                   -- e.g. x = 23
                 | If Expression Statement Statement -- if e then s1 else s2 end
                 | While Expression Statement        -- while e do s end
                 | Sequence Statement Statement      -- s1; s2
                 | Skip                              -- no-op
  
  -- All binary operations
  data Op = Plus         --  +  :: Int -&gt; Int -&gt; Int
          | Minus        --  -  :: Int -&gt; Int -&gt; Int
          | Times        --  *  :: Int -&gt; Int -&gt; Int
          | GreaterThan  --  &gt;  :: Int -&gt; Int -&gt; Bool
          | Equals       --  == :: Int -&gt; Int -&gt; Bool
          | LessThan     --  &lt;  :: Int -&gt; Int -&gt; Bool
  
  -- The `Store` is an associative map from `Variable` to `Value` representing the memory
  type Store = Map Variable Value
  
  --------- Parser ---------
  
  -- The Lexer
  
  lexer = P.makeTokenParser (emptyDef {
    P.identStart = letter,
    P.identLetter = alphaNum,
    P.reservedOpNames = ["+", "-", "*", "!", "&gt;", "=", "==", "&lt;"],
    P.reservedNames = ["true", "false", "if", "in", "then", "else", "while", "end", "to", "do", "for"]
  })
  
  -- The Parser
  
  -- Number literals
  numberParser :: Parser Value
  numberParser = (IntVal . fromIntegral) &lt;$&gt; P.natural lexer
  
  -- Boolean literals
  boolParser :: Parser Value
  boolParser =  (P.reserved lexer "true" &gt;&gt; return (BoolVal True))
            &lt;|&gt; (P.reserved lexer "false" &gt;&gt; return (BoolVal False))
  
  -- Literals and Variables
  valueParser :: Parser Expression
  valueParser =  Val &lt;$&gt; (numberParser &lt;|&gt; boolParser)
             &lt;|&gt; Var &lt;$&gt; P.identifier lexer
  
  -- -- Expressions
  exprParser :: Parser Expression
  exprParser = liftA2 Assignment
                      (try (P.identifier lexer &gt;&gt;= (\v -&gt;
                            P.reservedOp lexer "=" &gt;&gt; return v)))
                      exprParser
            &lt;|&gt; buildExpressionParser table valueParser
      where table = [[Infix (op "*" (BinOp Times)) AssocLeft]
                    ,[Infix (op "+" (BinOp Plus)) AssocLeft]
                    ,[Infix (op "-" (BinOp Minus)) AssocLeft]
                    ,[Infix (op "&gt;" (BinOp GreaterThan)) AssocLeft]
                    ,[Infix (op "==" (BinOp Equals)) AssocLeft]
                    ,[Infix (op "&lt;" (BinOp LessThan)) AssocLeft]]
            op name node = (P.reservedOp lexer name) &gt;&gt; return node
  
  -- Sequence of statements
  stmtParser :: Parser Statement
  stmtParser = stmtParser1 `chainl1` (P.semi lexer &gt;&gt; return Sequence)
  
  -- Single statements
  stmtParser1 :: Parser Statement
  stmtParser1 = (Expr &lt;$&gt; exprParser)
            &lt;|&gt; do
                P.reserved lexer "if"
                cond &lt;- exprParser
                P.reserved lexer "then"
                the &lt;- stmtParser
                P.reserved lexer "else"
                els &lt;- stmtParser
                P.reserved lexer "end"
                return (If cond the els)
            &lt;|&gt; do
                P.reserved lexer "while"
                cond &lt;- exprParser
                P.reserved lexer "do"
                body &lt;- stmtParser
                P.reserved lexer "end"
                return (While cond body)
  
  -------- Helper functions --------
  
  -- Lift primitive operations on IntVal and BoolVal values
  liftIII :: (Int -&gt; Int -&gt; Int) -&gt; Value -&gt; Value -&gt; Value
  liftIII f (IntVal x) (IntVal y) = IntVal $ f x y
  liftIIB :: (Int -&gt; Int -&gt; Bool) -&gt; Value -&gt; Value -&gt; Value
  liftIIB f (IntVal x) (IntVal y) = BoolVal $ f x y
  
  -- Apply the correct primitive operator for the given Op value
  applyOp :: Op -&gt; Value -&gt; Value -&gt; Value
  applyOp Plus        = liftIII (+)
  applyOp Minus       = liftIII (-)
  applyOp Times       = liftIII (*)
  applyOp GreaterThan = liftIIB (&gt;)
  applyOp Equals      = liftIIB (==)
  applyOp LessThan    = liftIIB (&lt;)
  
  -- Parse and print (pp) the given WHILE programs
  pp :: String -&gt; IO ()
  pp input = case (parse stmtParser "" input) of
      Left err -&gt; print err
      Right x  -&gt; print x
  
  -- Parse and run the given WHILE programs
  run :: (Show v) =&gt; (Parser n) -&gt; String -&gt; (n -&gt; Store -&gt; v) -&gt; IO ()
  run parser input eval = case (parse parser "" input) of
      Left err -&gt; print err
      Right x  -&gt; print (eval x empty)
  </code></pre>