CODEWITHSUNDEEP
haskellinterpretermonadsmonad-transformers
k_wisniewski
k_wisniewski

Reputation: 2519

Interpreter of a small imperative language

Hi I'm writing an interpreter of C-like, statically typed language in Haskell. I want to perform typechecking before an execution of code, but I have some problems with it. First of all, below there are some type definitions from my abstract syntax:

newtype Ident = Ident String deriving (Eq,Ord,Show)
data Exp = {-- some other value constructors --} | EFuncWithParams Ident [Exp]
data Type = TInt | TDouble | {-- some other value constructors --} | TFunction [Exp]
type TCM a = ErrorT String (Reader Env) a

TCM is for reporting errors and passing the enviroment, eg:

typeof (EVar v) = do
env <- ask
case M.lookup v env of
    Nothing -> throwError $ "undefined variable" ++ v ++ "\n"
    Just t - > return t

Now I want to check type of expressions so I have following function that performs checks:

typeof Exp :: Exp -> TCM Type

It is defined for all cases but one:

typeof (EFuncWithParams f l)

I'm stuck here. What I think I should do is to check the type of f (I mean first of all check if it really IS a function) and see whether types of arguments that are recorded in definition of f match types of arguments that are actually passed. Unfortunately I'm a haskell newbie and have no idea on how to express it the right way. Any suggestions will be highly appreciated :)

EDIT: OK, It may not be implied by what I wrote here previously but EFuncWithParams Ident [Exp] is a function call actually (Yes, I know it is somewhat misleading) and I want to be able to call a function like f(2 + 3, a, b[0]) and this is why I used TFunction [Exp]. Function declaration and definition is a statement and is defined:

data Function_def =
   Func Type_specifier Declarator Compound_stm
   deriving (Eq,Ord,Show)

where Declarator is:

data Declarator =  FuncDec Ident Parameter_declarations

Parameter declarations is a list of Type_specifiers and Idents

What I think I should do is to save function type in a map while checking its declaration, and then fetch it here. I mean I also have:

typeof_stm :: Stm -> TCM Type -- Function_def is a statement

The problem is that I have a separate function for type-checking statements and I am in doubt whether the map that is used by one function (eg. typeof_stm) is passed automatically to another one (eg. typeof). I see no way of this to happen but maybe I'm wrong.

Upvotes: 3

Views: 643

Answers (3)

n. m. could be an AI
n. m. could be an AI

Reputation: 119847

I think your function type is wrong. You have it as TFunction [Exp], it should be TFunction [Type] Type (a list of argument types and a return type).

Typechecking code for a function call would look something like

case ... of ...
  EFuncWithParams ident args -> do
     t <- typeof (EVar ident)
     ts <- mapM typeof args
     case t of
         TFunction ps r -> if ts == ps
                               then return r
                               else throwError $ "parameter types do not match"
         _ -> throwError $ "called id " ++ ident ++ " which is not a function"

This pseudo-code probably goes in and out of the monad improperly, please bear with me, I don't have all of your code so I cannot really typecheck what I have done. But the overall scheme is like this. You probably will want to give more detailed error report if parameter types do not match (which ones don't match, or perhaps there's a wrong number of parameters).

Upvotes: 3

Dan Burton
Dan Burton

Reputation: 53665

EFuncWithParams Ident [Exp]

It is typical for languages like yours to require a type annotation on the input, and possibly also a type annotation on the output. So if you add this info to that constructor

EFuncWithparams { inType, outType :: Type
                , funcInput :: Ident
                , funcBody :: [Expr] }

Now to typecheck it, you simply:

  1. Add the binding of funcInput to inType to your type environment
  2. Ascertain the type of funcBody with the new type environment
  3. Make sure it matches with outType.

You should also check function applications to make sure that the input matches the function's inType, and that the results are used correctly according to its outType.

Upvotes: 0

Jack
Jack

Reputation: 133557

I'm not practical with Haskell, I just did it in OCaml and in C++ but what you are going to do is to call the type checker function recursively on each parameter and check if they do correspond.

What I mean is that you'll have to type check something that is like 

FunCall ident, exp list

Now you'll have in the environment an entry for the function with the types of parameters associated so what you need to ensure in order is that:

  • function named ident does exist in the environment
  • the number of parameters is equal to the definition (this can be done implicitly by the param checking function, see below)
  • for every parameter you call typeof (exp1) and you check that the returned TCM Type is the same of the corresponding parameter

This is how it should work. In OCaml (which is somewhat similar to Haskell) I would do something like:

match exp with
    | FunCall ident, (param list) ->
      (* get fundecl from ident *)
      (* call check_params list_of_parameters, list_of_type_of_parameters *)
      (* if check params return true then type check value of the function is the return value *)


let check_params list decl_list =
  match list, decl_list with
    | [], [] -> true
    | p :: rp, d :: rd -> typeof(p) = d && check_params rp rd
    | _ -> false

Upvotes: 1

Related Questions