Интерпретатор небольшого императивного языка

Привет, я пишу интерпретатор C-подобного, статически типизированного языка в Haskell. Я хочу выполнить проверку типов перед выполнением кода, но у меня с этим проблемы. Прежде всего, ниже приведены некоторые определения типов из моего абстрактного синтаксиса:

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 предназначен для сообщения об ошибках и прохождения среды, например:

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

Теперь я хочу проверить тип выражений, поэтому у меня есть следующая функция, которая выполняет проверки:

typeof Exp :: Exp -> TCM Type

Он определен для всех случаев, кроме одного:

typeof (EFuncWithParams f l)

Я застрял здесь. Я думаю, что мне следует проверить тип f (я имею в виду, прежде всего, проверить, действительно ли это функция) и посмотреть, соответствуют ли типы аргументов, которые записаны в определении f, типам аргументов, которые фактически передаются. К сожалению, я новичок в хаскеле и понятия не имею, как правильно это выразить. Любые предложения будут высоко оценены :)

РЕДАКТИРОВАТЬ: ОК, это может не подразумеваться из того, что я писал здесь ранее, но EFuncWithParams Ident [Exp] на самом деле является вызовом функции (да, я знаю, что это несколько вводит в заблуждение), и я хочу иметь возможность вызывать такую ​​функцию, как f(2 + 3, a, b[0]), поэтому я использовал TFunction [Exp]. Объявление и определение функции является оператором и определяется:

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

где декларатор:

data Declarator =  FuncDec Ident Parameter_declarations

Объявления параметров — это список Type_specifiers и Idents.

Я думаю, что мне следует сохранить тип функции на карте при проверке ее объявления, а затем получить его здесь. Я имею в виду, что у меня также есть:

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

Проблема в том, что у меня есть отдельная функция для операторов проверки типов, и я сомневаюсь, передается ли карта, используемая одной функцией (например, typeof_stm), автоматически другой (например, typeof). Я не вижу возможности, чтобы это произошло, но, возможно, я ошибаюсь.


haskell monads interpreter monad-transformers
person k_wisniewski    schedule 19.04.2012    source источник
comment
Как вы представляете как типы аргументов функции, так и тип результата функции?   -  person Chris Kuklewicz    schedule 19.04.2012

Ответы (3)


arrow_upward
3
arrow_downward

Я думаю, что ваш тип функции неверен. У вас это TFunction [Exp], должно быть TFunction [Type] Type (список типов аргументов и тип возвращаемого значения).

Код проверки типов для вызова функции будет выглядеть примерно так:

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"

Этот псевдокод, вероятно, неправильно входит и выходит из монады, пожалуйста, потерпите меня, у меня нет всего вашего кода, поэтому я не могу проверить, что я сделал. Но общая схема такая. Вы, вероятно, захотите предоставить более подробный отчет об ошибке, если типы параметров не совпадают (какие из них не совпадают, или, возможно, неправильное количество параметров).

person n. 1.8e9-where's-my-share m.    schedule 19.04.2012

arrow_upward
1
arrow_downward

Я не умею работать с Haskell, я просто делал это в OCaml и C++, но вы собираетесь рекурсивно вызывать функцию проверки типов для каждого параметра и проверять, соответствуют ли они.

Я имею в виду, что вам нужно будет напечатать что-то вроде проверки

FunCall ident, exp list

Теперь у вас будет в среде запись для функции с типами связанных параметров, поэтому вам нужно убедиться, что:

  • функция с именем ident существует в среде
  • количество параметров равно определению (это можно сделать неявно с помощью функции проверки параметров, см. ниже)
  • для каждого параметра, который вы вызываете typeof (exp1), и вы проверяете, что возвращаемый TCM Type совпадает с соответствующим параметром

Вот как это должно работать. В OCaml (который чем-то похож на Haskell) я бы сделал что-то вроде:

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
person Jack    schedule 19.04.2012

arrow_upward
0
arrow_downward 

EFuncWithParams Ident [Exp]

Для таких языков, как ваш, типично требовать аннотацию типа на входе и, возможно, также аннотацию типа на выходе. Итак, если вы добавите эту информацию в этот конструктор

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

Теперь, чтобы проверить это, вы просто:

  1. Добавьте привязку funcInput к inType в среду вашего типа.
  2. Определите тип funcBody в среде нового типа
  3. Убедитесь, что он совпадает с outType.

Вы также должны проверить приложения функций, чтобы убедиться, что входные данные соответствуют inType функции, и что результаты используются правильно в соответствии с ее outType.

person Dan Burton    schedule 19.04.2012