Я хочу внедрить в Haskell обязательный переводчик языка (для образовательных целей). Но мне трудно создать правильную архитектуру для моего интерпретатора: как хранить переменные? Как я могу реализовать вложенные вызовы функций? Как я должен применять переменную область охвата? Как добавить возможности отладки на моем языке? Должен ли я использовать monads/monad transformers/другие методы? и др.
Кто-нибудь знает хорошие статьи/статьи/учебники/источники по этой теме?
Если вы новичок в написании таких процессоров, я бы рекомендовал отложить использование монад на некоторое время и в первую очередь сосредоточиться на получении barebone-реализации без каких-либо звонков или свистов.
В качестве мини-учебника может выступать следующее.
Я предполагаю, что вы уже решили проблему разбора исходного текста программ, для которых вы хотите написать интерпретатор, и что у вас есть несколько типов для захвата абстрактного синтаксиса вашего языка. Язык, который я здесь использую, очень прост и состоит только из целочисленных выражений и некоторых основных операторов.
Давайте сначала импортируем некоторые модули, которые мы будем использовать всего лишь немного.
import Data.Function
import Data.List
Суть императивного языка состоит в том, что он имеет некоторую форму изменяемых переменных. Здесь переменные, просто представленные строками:
type Var = String
Далее мы определяем выражения. Выражения построены из целочисленных констант, переменных ссылок и арифметических операций.
infixl 6 :+:, :-:
infixl 7 :*:, :/:
data Exp
= C Int -- constant
| V Var -- variable
| Exp :+: Exp -- addition
| Exp :-: Exp -- subtraction
| Exp :*: Exp -- multiplication
| Exp :/: Exp -- division
Например, выражение, которое добавляет константу 2 к переменной x, представлено V "x" :+: C 2.
Язык инструкции довольно минимален. У нас есть три формы операторов: назначения переменных, а также циклы и последовательности.
infix 1 :=
data Stmt
= Var := Exp -- assignment
| While Exp Stmt -- loop
| Seq [Stmt] -- sequence
Например, последовательность операторов для "замены" значений переменных x и y может быть представлена Seq ["tmp" := V "x", "x" := V "y", "y" := V "tmp"].
Программа - это просто инструкция.
type Prog = Stmt
Теперь перейдем к фактическому интерпретатору. При запуске программы нам нужно отслеживать значения, назначенные различным переменным в программах. Эти значения являются целыми числами, и в качестве представления нашей "памяти" мы просто используем списки пар, состоящих из переменной и значения.
type Val = Int
type Store = [(Var, Val)]
Выражения оцениваются путем сопоставления констант с их значением, поиска значений переменных в хранилище и сопоставления арифметических операций с их коллегами Haskell.
eval :: Exp -> Store -> Val
eval (C n) r = n
eval (V x) r = case lookup x r of
Nothing -> error ("unbound variable `" ++ x ++ "'")
Just v -> v
eval (e1 :+: e2) r = eval e1 r + eval e2 r
eval (e1 :-: e2) r = eval e1 r - eval e2 r
eval (e1 :*: e2) r = eval e1 r * eval e2 r
eval (e1 :/: e2) r = eval e1 r `div` eval e2 r
Обратите внимание, что если хранилище содержит несколько привязок для переменной, lookup выбирает привязки, которые появляются сначала в хранилище.
Хотя оценка выражения не может изменить содержимое хранилища, выполнение инструкции может фактически привести к обновлению хранилища. Следовательно, функция для выполнения оператора принимает хранилище в качестве аргумента и создает возможно обновленное хранилище.
exec :: Stmt -> Store -> Store
exec (x := e) r = (x, eval e r) : r
exec (While e s) r | eval e r /= 0 = exec (Seq [s, While e s]) r
| otherwise = r
exec (Seq []) r = r
exec (Seq (s : ss)) r = exec (Seq ss) (exec s r)
Обратите внимание, что в случае назначений мы просто нажимаем новое связывание обновленной переменной в хранилище, эффективно затеняя любые предыдущие привязки для этой переменной.
Запуск программы сводится к выполнению своего оператора верхнего уровня в контексте исходного хранилища.
run :: Prog -> Store -> Store
run p r = nubBy ((==) `on` fst) (exec p r)
После выполнения инструкции мы очищаем любые теневые привязки, чтобы мы могли легко считывать содержимое окончательного хранилища.
В качестве примера рассмотрим следующую программу, которая вычисляет число Фибоначчи числа, хранящегося в переменной n, и сохраняет его результат в переменной x.
fib :: Prog
fib = Seq
[ "x" := C 0
, "y" := C 1
, While (V "n") $ Seq
[ "z" := V "x" :+: V "y"
, "x" := V "y"
, "y" := V "z"
, "n" := V "n" :-: C 1
]
]
Например, в интерактивной среде мы можем теперь использовать наш интерпретатор для вычисления 25-го числа Фибоначчи:
> lookup "x" $ run fib [("n", 25)]
Just 75025
Конечно, здесь мы имеем дело с очень простым и крошечным императивным языком. Поскольку ваш язык становится более сложным, так будет и реализация вашего переводчика. Подумайте, например, о том, какие дополнения вам нужны, когда вы добавляете процедуры, и нужно различать локальное (стековое) хранилище и глобальное хранилище на основе кучи. Возвращаясь к этой части вашего вопроса, вы можете действительно подумать о введении монад, чтобы немного упростить реализацию вашего интерпретатора.
В приведенном выше примере интерпретатора есть два "эффекта", которые являются кандидатами для захвата монадической структурой:
Первый эффект обычно захватывается государственной монадой, второй - ошибкой монады. Давайте кратко рассмотрим, как это сделать для нашего переводчика.
Мы готовим, импортируя только один модуль из стандартных библиотек.
import Control.Monad
Мы можем использовать монадные трансформаторы для построения составной монады для наших двух эффектов, комбинируя основную монаду и основную ошибку monad. Здесь, однако, мы просто строим композитную монаду за один раз.
newtype Interp a = Interp { runInterp :: Store -> Either String (a, Store) }
instance Monad Interp where
return x = Interp $ \r -> Right (x, r)
i >>= k = Interp $ \r -> case runInterp i r of
Left msg -> Left msg
Right (x, r') -> runInterp (k x) r'
fail msg = Interp $ \_ -> Left msg
Для чтения и записи в хранилище мы вводим эффективные функции rd и wr:
rd :: Var -> Interp Val
rd x = Interp $ \r -> case lookup x r of
Nothing -> Left ("unbound variable `" ++ x ++ "'")
Just v -> Right (v, r)
wr :: Var -> Val -> Interp ()
wr x v = Interp $ \r -> Right ((), (x, v) : r)
Обратите внимание, что rd создает сообщение об ошибке Left, если сбой поиска переменной.
Монадическая версия оценщика выражения теперь читает
eval :: Exp -> Interp Val
eval (C n) = do return n
eval (V x) = do rd x
eval (e1 :+: e2) = do v1 <- eval e1
v2 <- eval e2
return (v1 + v2)
eval (e1 :-: e2) = do v1 <- eval e1
v2 <- eval e2
return (v1 - v2)
eval (e1 :*: e2) = do v1 <- eval e1
v2 <- eval e2
return (v1 * v2)
eval (e1 :/: e2) = do v1 <- eval e1
v2 <- eval e2
if v2 == 0
then fail "division by zero"
else return (v1 `div` v2)
В случае :/: деление на ноль приводит к появлению сообщения об ошибке через Monad -метод fail, который для Interp сводится к обертке сообщения в Left - значение.
Для выполнения операторов имеем
exec :: Stmt -> Interp ()
exec (x := e) = do v <- eval e
wr x v
exec (While e s) = do v <- eval e
when (v /= 0) (exec (Seq [s, While e s]))
exec (Seq []) = do return ()
exec (Seq (s : ss)) = do exec s
exec (Seq ss)
Тип exec передает, что эти инструкции не приводят к значениям, но выполняются только для их эффектов в хранилище или ошибок времени выполнения, которые они могут запускать.
Наконец, в функции run мы выполняем монадическое вычисление и обрабатываем его эффекты.
run :: Prog -> Store -> Either String Store
run p r = case runInterp (exec p) r of
Left msg -> Left msg
Right (_, r') -> Right (nubBy ((==) `on` fst) r')
В интерактивной среде мы можем теперь пересмотреть интерпретацию нашей примерной программы:
> lookup "x" `fmap` run fib [("n", 25)]
Right (Just 75025)
> lookup "x" `fmap` run fib []
Left "unbound variable `n'"
Несколько хороших документов, которые я наконец нашел: