Evaluating parsed expression in Haskell

Question

This is my first question on SO :)

My Haskell knowledge is pretty limited, so i need a bit of help to get me started. I have this BNF grammar:

num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
int ::= num | num int
var ::= A | B | C | ... | Z
expr ::= var | int | - expr
        | +(expr , expr) | *(expr , expr)
        | let var be expr in expr

I have already written a parser, with some help from another post here on SO.

My datatype is:

data Expr =  Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr  Expr Expr

What I need is to evaluate the expression that the parser outputs (Expr, String). I really dont know where to begin on this task. Can anyone help me?

Im not sure on what more information thats needed, I will post if necessary.

Answer 1

First off, in your datatype, the first piece of data for the Let constructor should just be the variable identifier (Char in your case) and not Expr.

Try a recursive function. You evaluate your Expr to Int, so basically the function you want to have a signature

evaluate :: Expr -> Int

Then just start matching on the constructors of Expr and evaluate subexpressions recursively:

evaluate (Tall n) = n
evaluate (Sum e1 e2) = evaluate e1 + evaluate e2

When it comes to Let bindings and variables, you'll need to extend the signature to additionally pass an environment that maps variables to their values. This can be as simple as a list of pairs of (Char, Int). Let will add the variable and its value to the environment that's passed to the in expression. So you'd end up with something like:

evaluate :: Expr -> Int
evaluate e = evaluate' e EmptyEnv
  where evaluate' :: Expr -> Env -> Int
        evaluate' (Tall n) _ = n
        ...

Of course you have to provide error handling if a variable is used that has not been bound by a let.

Does that help already?

Answer 2

Environment

For handling environments, You can use

• either lookup from Prelude
• or its namesake lookup from Data.Map library (and the other functions of the library)

If You choose to use Data.Map module, it is worth writing

Data.Map.lookup

instead of just lookup,

or -- another solution -- hiding Prelude's lookup with

import Prelude hiding (lookup)

so that not to receive an error message about the clash of the two lookup functions.

For simplicity's sake, first I write the solution with the simpler lookup function, that of Prelude.

For simpicity's sake again, I do not incorporate error hadling yet.

Environment:

module Env (Env) where

type Env = [Binding]

type Binding = (Char, Integer)

Expression:

module Expr where

data Expr = Var Char
          | Tall Int
          | Sum Expr Expr
          | Mult Expr Expr
          | Neg Expr
          | Let Char Expr Expr

Evaluation:

module Semantics (evaluate) where

import Expr (Expr)
import Env (Env)

evaluate :: Expr -> Integer
evaluate = evaluate' []

evaluate' :: Env -> Expr -> Integer
evaluate' _   (Tall n) = n
evaluate' env (Var x) = case lookup x env of
    Just n -> n
    Nothing -> error ("Variable" ++ [x] ++ "is free!")
evaluate' env (Sum a b) = evaluate' env a + evaluate' env b
evaluate' env (Mult a b) = evaluate' env a * evaluate' env b
evaluate' env (Neg a) = - evaluate' env a
evaluate' env (Let x a b) = evaluate' ((x, a) : env) b

Clash of variables

As for planning Your object language: in later releases, it is worth planning a strategy, how to deal with clashing variable names:

let A be 5 in (A +3)

is clear, but what should be meant for

let A be 5 in (let A be 3 in A)

?

In earlier releases of Your evaluator, You do not have to plan this, because lookup function will decide the situation "automatically" according to the default behavior immanent in its definition. But if You do not like its default behavior, You probably will augment Your evaluator with a conscious strategy for dealing with variable name clashes.

Error handling

If You evaluate an expression in an environment, and the expression references a variable that is not contained in the environment, then the interpreter must report an error somehow.

You can do it several ways, the simplest ones:

Bottom

With the error function, You can force the program to halt with a user-defined error message. This solution has disadvantages, but it is easy to write.

Maybe

You can alter Your evaluate' function. It will not have signature

evaluate' :: Env -> Expr -> Integer

but, rather

evaluate' :: Env -> Expr -> Maybe Integer

In this case, You have to alter the definition of evaluate' severely. You cannot write any more:

evaluate' env (Sum a b) = evaluate' env a + evaluate' env b

but a much more complicated definition is needed

evaluate' env (Sum a b) = case (evaluate' env a, evaluate' env b) of
        (Just a0, Just b0) -> Just (a0 + b0)
        _                  -> Nothing

We pack the Maybe-ed integers out, sum them, then pack them back into a Maybe-ed integer. It is like doing summation "inside the pack". We could save much work if we could tell Haskell that it can do summation "inside" the Maybe.

We can do that, if we exploit that Maybe is a monad: we can use the functions that have been designed for working with monads. Such auxiliary functions are provided in Control.Monad library. Here, liftM2 is the function that will help us to wrap summation around the Maybe-packed values:

evaluate' env (Sum a b) = liftM2 (+) (evaluate' env a) (evaluate' env b)

Some other auxiliary functions for Maybe-ed values can be found in Data.Maybe library, but here, we need not them.

module Semantics (evaluate) where

import Expr (Expr)
import Env (Env)
import Control.Monad (liftM, liftM2)

evaluate :: Expr -> Maybe Integer
evaluate = evaluate' []

evaluate' :: Env -> Expr -> Maybe Integer
evaluate' _   (Tall n) = Just n
evaluate' env (Var x) = lookup x env
evaluate' env (Sum a b) = liftM2 (+) (evaluate' env a) (evaluate' env b)
evaluate' env (Mult a b) = liftM2 (*) (evaluate' env a) (evaluate' env b)
evaluate' env (Neg a) = liftM negate (evaluate' env a)
evaluate' env (Let x a b) = evaluate' ((x, a) : env) b