Recursion problem written by a tiny parser in Haskell. Check Variables
I am still working on a small parser for a tiny language defined in an assignment at school. A parser is running, which generates an AST (Abstract Syntax Tree). I want to check certain variables, they must be constrained by a let expression. First, the method defined in the task (suggestion, not needed):
checkVars :: Expr -> Char
data Expr = Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr Expr Expr
deriving(Eq, Show)
A valid sentence is "let X be 5 in * (2, X)". X will usually be Var and 5 will usually be int. And the latter can be any part of the dataExpr type. Main point: X is used somewhere in the last expression. Data type for let:
Let Expr Expr Expr
Link to other questions I asked here, FYI only; First question Second question
As you can see, the datatype for checkVars is Expr, so here's an example of what I'll use for this function:
parseProg "let X be 4 in let Y be *(2 , X) in let Z be +(Y , X) in
+(+(X , Y) , Z)"
Let (Var 'X') (Tall 4) (Let (Var 'Y') (Mult (Tall 2) (Var 'X')) (Let
(Var 'Z') (Sum (Var 'Y') (Var 'X')) (Sum (Sum (Var 'X') (Var 'Y')) (Var
'Z'))))
Just 24
This is a fully included example, the top is the line / program being processed. The second part, starting at line 3 (Let), is the AST input to the checkVars function. And the bottom of "Just 24" is the score. Which I will come back here for more help. Note. The point is to spit out the first unbound variable found as an error and "if everything is fine. Obviously, if you want to do it differently, you can.
source to share
Here's something to think about:
The first field of your Let constructor is Expr
. But can it actually hold on to anything other than Var
s? If not, you should reflect this by creating this field type, say, String
and adapting the parser accordingly. This will simplify your task.
The standard trick for evaluating an expression with let-bindings (which you do) is to write a function
type Env = [(String, Int)]
eval :: Expr -> Env -> Int
Note the additional argument for environment. The environment keeps track of which variables are bound to which values at any time. Its position in the type means that you solve its value every time you call eval
in child expressions. It is important! This also means that you can have locally declared variables: binding a variable does not affect its context, only subexpressions.
Here are special cases:
- In
Var
you want tolookup
name a variable in the environment and return the value bound to it. (Use the standard Prelude functionlookup
.) - In,
Let
you want to add an extra one(varname, value)
to the beginning of the environment list before passing it to the child expression.
I forgot some details, but that should be enough to get you a long way. If you get stuck, ask another question. :-)
Oh, and I see that you want to return a value Maybe
to indicate failure. I suggest you first try and use error
to specify unbound variables. When you use this version eval
, adapt it to return values Maybe
. The reason for this is that working with values Maybe
makes evaluation quite difficult.
source to share