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

Question

Привет Я пишу интерпретатор C-like, статически типизированного языка в 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 

ТСМА для сообщений об ошибках и передач окружающей среды, например:

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 сопоставляемых типов аргументов, которые фактически переданы. К сожалению, я новичок в haskell и понятия не имею, как правильно это выразить. Любые предложения будут высоко оценены :)

EDIT: ОК, Возможно, это не означает, что я писал здесь ранее, но 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 и идент

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

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

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

Answer 1

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

Что я имею в виду, что вы должны ввести кое-что проверить, что это как

FunCall ident, exp list 

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

• функция с именем ident существует в среде
• числа параметров равно определению (это может быть сделано неявно проверочными пары фу nction, смотри ниже)
• для каждого параметра вы называете 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 

Answer 2

EFuncWithParams Ident [Exp] 

Это характерно для языков, как ваш требовать аннотацию типа на входе, и, возможно, также типа АННОТАЦИЯ на вывод. Так что, если вы добавите эту информацию к этому конструктору

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

Теперь typecheck, вы просто:

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

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

Answer 3

Я думаю, что ваш тип функции неправильный. У вас это как 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" 

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