Haskell Happy implement assign to variable

Question

I'm trying to implement some language with x = 4 and pritn x, constructions using haskell happy So far I've defined grammar like this

 terms 
    : term                   { [$1] }
    | term terms             { $1 : $2 }

 term 
    : var '=' int             { Assign $1 $3 }
    | print var               { Print $2 }

When I run it over something like

x = 4
print x
y = 5
print y

I get

[Assign "x" 4, Print "x", Assign "y" 5, Print "y"]

Now I want to do actual implementation, but I don't know how to implement "assign"

Though I'm not good at haskell, from happy docs I saw "let" implementation and got the idea of some environment p passed and evaluated in

Exp   : let var '=' Exp in Exp  { \p -> $6 (($2,$4 p):p) }
  | Exp1                    { $1 }

Exp1  : Exp1 '+' Term           { \p -> $1 p + $3 p }
  | Exp1 '-' Term           { \p -> $1 p - $3 p }
  | Term                    { $1 }

Term  : Term '*' Factor         { \p -> $1 p * $3 p }
  | Term '/' Factor         { \p -> $1 p `div` $3 p }
  | Factor                  { $1 }

Factor            
  : int                     { \p -> $1 }
  | var                     { \p -> case lookup $1 p of
                                    Nothing -> error "no var"
                    Just i  -> i }
  | '(' Exp ')'             { $2 }

I guess "assign" implementation has to do something with this env, but I couldn't find any example. How can I implement assign and print or where can I find information or example of it?

Answer 1

You're quite close with the parser. But what you want to build is an interpreter for your little expression language separate from the parsing logic. The parser will just generate the AST for the program and then we'll evaluate it separately.

The code is actually quite small, but it's split across several modules so I put it here in this gist: https://gist.github.com/sdiehl/c2dd1880e0ec6b65a120

I presume your AST looks something like this:

data Expr
  = Var String
  | Num Int
  | Print Expr
  | Assign String Int
  deriving (Eq,Show)

The parser looks right except I think you'll need to add a var production so expressions like print x and print 1 can both be well-formed in the syntax.

%token
    int   { TokenNum $$ }
    var   { TokenSym $$ }
    print { TokenPrint }
    '='   { TokenEq }

%%

terms 
    : term                   { [$1] }
    | term terms             { $1 : $2 }

term 
   : var                     { Var $1 }
   | var '=' int             { Assign $1 $3 }
   | print term              { Print $2 }

For the interpreter we'll use a StateT + IO monad to hold the assigned variables and invoke Haskell's print function for each Print function in our program. The state monad will hold an association list of variables to values. Assign will simply add a new reference to the list, and a Var reference will use the lookup function over the state.

data Value
  = VInt Int
  | VUnit

instance Show Value where
  show (VInt x) = show x

type Eval = StateT Env IO
type Env = [(String, Value)]

eval1 :: Expr -> Eval Value
eval1 expr = case expr of
  Num a -> return (VInt a)
  Var a -> do
    env <- get
    case lookup a env of
      Just val -> return val
      Nothing -> error "Not in scope"
  Print a -> do
    a' <- eval1 a
    liftIO $ print a'
    return VUnit
  Assign ref val -> do
    modify $ \s -> (ref, VInt val) : s
    return VUnit

eval :: [Expr] -> IO ()
eval xs = evalStateT (mapM_ eval1 xs) []

And that's about it.