Написание переводчика для императивного языка на Haskell

Question

Я пытаюсь создать интерпретатор для C -подобного языка в Haskell. До сих пор я писал и комбинировал небольшие парсеры monadi c, следующие за этой статьей, поэтому до сих пор я могу генерировать AST-представление программы. Я определил абстрактный синтаксис следующим образом:

data LangType = TypeReal | TypeInt | TypeBool | TypeString deriving (Show)
type Id = String

data AddOp = Plus | Minus | Or deriving (Show)
data RelOp = LT | GT | LTE | GTE | NEq | Eq deriving (Show)
data MultOp = Mult | Div | And deriving (Show)
data UnOp = UnMinus | UnNot deriving (Show)
data BinOp = Rel RelOp | Mul MultOp | Add AddOp deriving (Show)

data AST = Program [Statement] deriving (Show)
data Block = StatsBlock [Statement] deriving (Show)
data Statement = VariableDecl Id LangType Expression
               | Assignment Id Expression
               | PrintStatement Expression
               | IfStatement Expression Block Block
               | WhileStatement Expression Block
               | ReturnStatement Expression
               | FunctionDecl Id LangType FormalParams Block 
               | BlockStatement Block 
               deriving (Show)
data Expression = RealLiteral Double
                | IntLiteral Int
                | BoolLiteral Bool
                | StringLiteral String
                | Unary UnOp Expression
                | Binary BinOp Expression Expression
                | FuncCall Id [Expression]
                | Var Id
                deriving (Show)
data FormalParams = IdentifierType [(Id, LangType)] deriving (Show)

Мне еще предстоит проверить тип AST и построить интерпретатор для оценки выражений и выполнения операторов. У меня следующие вопросы:

1. Имеет ли смысл абстрактный синтаксис / его можно улучшить? В частности, я столкнулся с постоянной проблемой. В EBNF этого языка, который я пытаюсь интерпретировать, WhileStatement состоит из Expression (с которым у меня нет проблем) и Block, который в EBNF оказывается Statement точно так же, как WhileStatement, и поэтому я не могу сослаться на Block из моего WhileStatement. Я работал над этим, определяя отдельный тип данных Block (как показано в приведенном выше коде), но не уверен, что это лучший способ. Я нахожу определение типов данных довольно запутанным.
2. Так как мне приходится проверять тип моего AST и оценивать / выполнять, я реализую их отдельно или я могу определить некоторую функцию, которая выполняет их оба одновременно?

Любые общие советы о том, как я должен go о проверке типов и интерпретации языка, также будут с благодарностью. Поскольку в языке есть объявления переменных и функций, я думаю о реализации какой-то таблицы символов, хотя, опять же, я борюсь с определением типа для этого. До сих пор я пробовал

    import qualified Data.Map as M

    data Value = RealLit Double | IntLit Int | BoolLit Bool | StringLit String | Func [FormalParams] String 
                 deriving (Show)
    type TermEnv = M.Map String Value

, но я не уверен, стоит ли мне использовать мой LangType ранее.

Answer 1

Обращаясь к вашему вопросу в комментариях о том, как приступить к проверке и оценке типов.

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

Начните с определения монады с нужными вам функциями. Для проверки типов вам понадобится

• A типовая среда , то есть компонент Reader(Map Id LangType), чтобы отслеживать типы локальные переменные.
• ошибка способность, например ExceptString.

Таким образом, вы можете определить монаду как

type TypeEnv = Map.Map Id LangType
type TC = ReaderT TypeEnv (Except String)

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

typeCheck :: AST -> TC ()

(Мы возвращаем (), потому что нет ничего интересного в процессе проверки типов, кроме знания того, прошла ли программа.)

Это будет в значительной степени структурно индуктивно, например:

typeCheck (Program stmt) = -- typecheckStmt each statement*

typeCheckStmt :: Statement -> TC ()
typeCheckStmt (VariableDecl v type defn) = ...
typeCheckStmt (Assignment v exp) = do
    Just t <- asks (Map.lookup v)
    t' <- typeCheckExp exp
    when (t /= t') $ throwError "Types do not match"
...

-- Return the type of a composite expression to use elsewhere
typeCheckExp :: Expression -> TC LangType
...

Потребуется немного изящества чтобы убедиться, что объявления переменных в списке операторов могут быть видны более поздними операторами в том же списке. Я оставлю это как загадку. (Подсказка: см. Функцию local, чтобы обеспечить обновленную среду в области действия.)

---

Оценка - аналогичная история. Вы правы, что вам нужен тип значений времени выполнения. Без некоторой сообразительности, к которой вы, вероятно, не готовы (и которая может быть сомнительной, даже если бы вы были), на самом деле нет способа использовать LangType в Value, поэтому вы на правильном пути.

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

type Eval = StateT (Map Id Value) IO

и действую, как и прежде. Опять же, при обработке переменных областей и теней потребуется некоторая утонченность, и вам может потребоваться изменить тип среды или немного поработать с типом Value, чтобы учесть эти тонкости, но важно продумать эти проблемы. Начните с простого, не пытайтесь осуществлять проверку типов и оценку сразу для всего языка.