Реализация языкового переводчика в Хаскеле

Я хочу внедрить обязательный переводчик языка в Haskell (для образовательных целей). Но это'Мне сложно создать правильную архитектуру для моего интерпретатора: как хранить переменные? Как я могу реализовать вызовы вложенных функций? Как мне реализовать переменную область видимости? Как я могу добавить возможности отладки на моем языке? Должен ли я использовать монады / монадные трансформаторы / другие методы? и т.п.

Кто-нибудь знает хорошие статьи / статьи / учебники / источники по этому вопросу?

 luqui06 июн. 2013 г., 21:23
Обязательно используйте монаду для структурирования возможностей вашего языка. Тот'в основном то, что онио.
 djf06 июн. 2013 г., 21:23

Ответы на вопрос(2)

 duggi18 нояб. 2018 г., 19:23
Как построить монадический переводчик за один день -drive.google.com/file/d/1NaPY7qIrj8rPdq1yTerSq6uJZAYjIKpT/...
 Mateusz Piotrowski10 апр. 2018 г., 01:05
Некоторые ссылки мертвы
 duggi18 нояб. 2018 г., 19:24
Монадные Трансформеры Шаг за шагом -drive.google.com/file/d/1QHBMvrK_nQ1UU05NBdA_U1q5-jsNGC68/...
Решение Вопроса

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

Следующее может служить в качестве руководства.

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

прелиминарии

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

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

Заявления

Язык высказываний довольно минимален. У нас есть три формы операторов: присваивание переменных, циклы while и последовательности.

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

Мы можем использовать монадные преобразователи для создания составной монады для наших двух эффектов, комбинируя монаду основного состояния и монаду основной ошибки. Здесь, однако, мы просто строим составную монаду за один раз.

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

Изменить 2018: Аппликативное предложение монады

Поскольку Аппликативное предложение монады (AMP), каждая монада также должна быть экземпляром Functor и Applicative. Для этого мы можем добавить

import Control.Applicative -- Otherwise you can't do the Applicative instance.

импортировать и сделать Interp экземпляром Functor и Applicative, как это

instance Functor Interp where
  fmap = liftM -- imported from Control.Monad

instance Applicative Interp where
  pure  = return
  (<*>) = ap -- imported from Control.Monad

Изменить конец 2018 года

Для чтения и записи в магазин мы вводим эффективные функции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'"
 Satvik07 июн. 2013 г., 00:30
Просто улучшение по сравнению с определением вашей собственной монады специально для этого случая, вы всегда можете использовать монаду State для хранения состояния.

Ваш ответ на вопрос