Since there isn't a specific question I'll just offer some general advice on the problem.
Looks like you're on the right track. Your approach is correct you need to walk your syntax tree and check each subexpression, failing if your types don't match.
typecheckexp :: [TypeEnv] -> Exp -> Bool
typecheckexp types (Add e1 e2) =
case (te1, te2) of
(Just TyInt, Just TyInt) -> True
_ -> False
where
te1 = getTypeOfExp e1
te2 = getTypeOfExp e2
At the toplevel you'll apply your expression level checker across all expressions and then and
all the results together to get whether your program as a whole typechecks.
typecheckexplist :: [TypeEnv] -> [Exp] -> Bool
typecheckexplist env stmts = and (map (typecheckexp env) stmts)
If your types are all declared up front and the TypeEnv is not altered as a result of traveresing the AST then this approach will work. If you are building up definitions as you walk the tree then consider wrapping your typechecker in a State monad.
Obviously if you are assigning and comparing variables/expressions,
Depending on your frontend language you'll need to decide whether to add explicit type declarations ( i.e. int a
) for variables or whether you'll try and deduce them from context of the program, which is a separate task called type inference. If you have explicit declarations from the user then you can simply mechanically check the given types against the uses of the variable and determine if they match. Your types are all simple monotypes so this is easy as you can attach (derving Eq
) to your Type
and get type comparison.
Another case to consider is error reporting, with your given AST there is no position information attached so if you walk the tree and fail midways you'll have no way to tell the user what failed and where. If you're parsing the frontend language from a parser like Parsec you can tag each data type (Expr Pos
) with the information when constructing the syntax tree.
data Expr t = Add t (Expr t) (Expr t) | ...
data Pos = Pos { line :: Integer , col :: Integer }
For ease of use you might look into a generics library like Uniplate which will let you apply functions and traverse your AST without so much boilerplate. A contrived example to extract all nodes of a specific type might be:
{-# LANGUAGE DeriveDataTypeable #-}
module Expr where
import Data.Data
import Data.Typeable
import Data.Generics.Uniplate.Data
data Expr = Val String
| Add Expr Expr
| Sub Expr Expr
| Div Expr Expr
| Mul Expr Expr
| Neg Expr
deriving (Show, Eq, Data, Typeable)
vars :: Expr -> [String]
vars ex = [i | Val i <- universe ex]
test :: [String]
test = vars (Add (Val "a") (Mul (Val "b") (Val "c")))