Evaluating Expression in Haskell
This is my first question on SO :)
My Haskell's knowledge is rather limited, so I need a little 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 already wrote a parser with some help from another post here on SO.
My datatype:
data Expr = Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr Expr Expr
I need to evaluate the expression that the parser outputs (Expr, String). I really don't know where to start this task. Can anyone help me?
I'm not sure if you need more information, I'll post if necessary.
source to share
First of all, in your data type, the first piece of data for the constructor Let
should just be a variable identifier ( Char
in your case), not Expr
.
Try a recursive function. You are evaluating your Expr
before Int
, so basically the function you want to have signatures
evaluate :: Expr -> Int
Then, just start matching constructors Expr
and evaluate the subexpressions recursively:
evaluate (Tall n) = n
evaluate (Sum e1 e2) = evaluate e1 + evaluate e2
When it comes to Let
bindings and variables, you need to extend the signature to further pass an environment that maps variables to their values. It can be as simple as a list of pairs (Char, Int)
. Let
will add the variable and its value to the environment passed to the expression in
. So you 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 must provide error handling if you are using a variable that has not been bound to Let
.
Does it help already?
source to share
Environment
For working with environments you can use
- or lookup from Prelude
- or its namesake lookup from the Data.Map library (and other library functions)
If you decide to use the Data.Map module it is worth writing
Data.Map.lookup
instead lookup
,
or - another solution is to hide the Prelude lookup
with
import Prelude hiding (lookup)
to avoid getting an error message due to a collision of two functions lookup
.
For simplicity, I'll first write a solution with a simpler function lookup
than the Prelude.
For simplicity, I have not yet included the bug.
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
Rating:
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
Variable collision
As far as scheduling the language of your object: in later releases it is worth planning a strategy on how to deal with conflicting variable names:
let A be 5 in (A +3)
clear, but what needs to be understood for
let A be 5 in (let A be 3 in A)
?
In earlier versions of your evaluator, you do not need to plan for this, because the function lookup
will solve the situation "automatically" according to the default behavior immanent in its definition. But if you don't like the default behavior, you probably add your evaluator to a deliberate strategy for dealing with variable name conflicts.
Error processing
If you are evaluating an expression in the environment, and the expression refers to a variable that is not contained in the environment, the interpreter must somehow report an error.
You can do this in several ways, the simplest:
From below
With a function, error
you can force the program to stop with a custom error message. This solution has disadvantages, but it is easy to write.
May be
You can change your function evaluate'
. He will not have a signature
evaluate' :: Env -> Expr -> Integer
but rather
evaluate' :: Env -> Expr -> Maybe Integer
In this case, you need to change the definition of "serious". You can no longer write:
evaluate' env (Sum a b) = evaluate' env a + evaluate' env b
but a much more complex definition is required
evaluate' env (Sum a b) = case (evaluate' env a, evaluate' env b) of
(Just a0, Just b0) -> Just (a0 + b0)
_ -> Nothing
We collect the Maybe-ed integers, add them up, and then send them back to the Maybe-ed integer. This is similar to "in-package" summation. We could save a lot of work if we could tell Haskell that it can do summation inside Maybe.
We can do this by using that Maybe is a monad: we can use functions that were designed to work with monads. Such helper functions are provided in the Control.Monad library . Here liftM2 is a function to help us concatenate the sums around Maybe-pack values:
evaluate' env (Sum a b) = liftM2 (+) (evaluate' env a) (evaluate' env b)
Some helper functions for Maybe-ed values can be found in the Data.Maybe library , but we don't need them here.
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
source to share