Как вы собираетесь внедрить интерпретатор (в Haskell) для простого языка программирования, который является языком императивного стиля.

Question

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

У меня были бы циклы, условия и функциональные вызовы, и все. Я ищу старт, пример не книгу теории. Кто-нибудь когда-либо реализовал такой базовый переводчик языка в Haskell? Я ищу указатели и ссылки.

Спасибо!

Answer 1

Я сейчас работаю над одним из проектов практики.

Это динамически типизированный язык, поэтому переменные не обязательно должны быть объявлены, но каждое значение имеет связанный тип. Я Реализована с использованием алгебраического типа данных в Haskell:

data Value = BoolValue Bool --^A Boolean value. 
      | NumberValue Double --^A numeric value. 
      | StringValue String --^A string value. 
      -- (several others omitted for simplicity) 

Для выполнения программ, я использую монады трансформаторов StateT и ErrorT на вершине IO:

-- | A monad representing a step in an RPL program. 
-- 
-- This type is an instance of 'MonadState', so each action is a function that 
-- takes an 'RPLContext' as input and produces a (potentially different) 
-- 'RPLContext' as its result. It is also an instance of 'MonadError', so an 
-- action may fail (with 'throwRPLError'). And it is built on the 'IO' monad, 
-- so 'RPL' computations can interact with the outside world. 
type RPL = StateT RPLContext (ErrorT RPLError IO) 

-- | Executes an 'RPL' computation. 
-- The monadic result value (of type @a@) is discarded, leaving only the final 
-- 'RPLContext'. 
runRPL :: RPL a --^The computation to run 
     -> RPLContext --^The computation's initial context 
     -> IO (Either RPLError RPLContext) 
     --^An 'IO' action that performs the operation, producing either 
     -- a modified context if it succeeds, or an error if it fails. 
runRPL a = runErrorT . (execStateT a) 

«контекст» является комбинация стека данных (это язык на основе стека) и «среда», которая содержит все переменные, которые в настоящее время находятся в области:

-- | The monadic state held by an 'RPL' computation. 
data RPLContext = RPLContext { 
    contextStack :: Stack, --^The context's data stack. 
    contextEnv :: Env --^The context's environment. 
} 

(Обратите внимание, что Stack это просто псевдоним для [Value].)

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

-- | Pushes a value onto the stack. 
pushValue :: Value -> RPL() 
pushValue x = modifyStack (x:) 

-- | Transforms the current stack by a function. 
modifyStack :: (Stack -> Stack) -> RPL() 
modifyStack f = do 
    stack <- getStack 
    putStack $ f stack 

-- | Returns the entire current stack. 
getStack :: RPL Stack 
getStack = fmap contextStack get 

-- | Replaces the entire current stack with a new one. 
putStack :: Stack -> RPL() 
putStack stack = do 
    context <- get 
    put $ context { contextStack = stack } 

getStack, putStack и modifyStack моделируются после MonadState «s get, put и modify функций, но они работают только на одном поле от записи RPLContext.

Все встроенные команды языка - это всего лишь действия в монаде RPL, которые строятся поверх таких инструментов, как pushValue.

Для анализа кода на моем языке я использую Parsec. Это довольно хорошо.

---

На отдельной дорожке, не связанный с моим переводчиком RPL, вы можете найти «Write Yourself a Scheme in 48 Hours» полезный.

Answer 2

Один из способов заключается в том, чтобы ваш интерпретатор работал в монаде StateT, используя Map для эмуляции изменяемых переменных. Простой пример:

import Control.Monad.State 
import Data.Map (Map) 
import qualified Data.Map as Map 

type VarName = String 
data Value = VInt Int 
      | VString String 
type InterpreterState = Map VarName Value 

type InterpretM = StateT InterpreterState IO 

putVar :: VarName -> Value -> InterpretM() 
putVar varname value = modify (Map.insert varname value) 

getVar :: VarName -> InterpretM Value 
getVar varname = do 
    m <- gets (Map.lookup varname) 
    case m of 
     Just x -> return x 
     Nothing -> error $ "Variable " ++ varname ++ " is undefined" 

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

Answer 3

Я бы сначала закодировал всю программу в EDSL. Этот EDSL сам был бы монадой и напоминал бы IO. GADT делает это очень легко закодировать:

{-# LANGUAGE GADTs, KindSignatures #-} 

module Interp where 

import SomeStuff 


data Expr :: * -> * where 
    -- Commands 
    Print :: String -> Expr() 
    GetLine :: Expr String 

    -- Variables (created on demand) 
    GetVar :: Name -> Expr Value 
    SetVar :: Name -> Value -> Expr() 

    -- Loop constructs 
    While :: Expr Bool -> Expr a -> Expr() 
    For :: Expr a -> Expr Bool -> Expr b -> Expr c -> Expr() 

    -- Expr is a monad 
    Return :: a -> Expr a 
    Bind :: Expr a -> (a -> Expr b) -> Expr b 

instance Monad Expr where 
    return = Return 
    (>>=) = Bind 

runExpr :: Expr a -> StateT Variables IO a 
runExpr (Print str) = liftIO (putStrLn str) 
runExpr GetLine  = liftIO getLine 
runExpr (While p x) = 
    fix $ \again -> do 
     b <- runExpr p 
     when b (runExpr x >> again) 
runExpr ... 

Для простых языков вы можете даже сделать что-то же просто, как это без специальной EDSL:

parseProgram :: Parser (StateT Variables IO()) 
parseProgram = ... 

Это часто забывают, что Haskell занимает понятие функционального программирования к его завершению. Пусть анализатор возвращает саму программу. Тогда вам просто нужно запуститьStateT с подходящим начальным состоянием.

Answer 4

Вот некоторые ресурс https://github.com/budabudimir/imp_interpreter, это интерпретатор для простого императивного языка, описанный здесь http://fsl.cs.illinois.edu/images/0/0d/CS522-Spring-2011-PL-book-imp.pdf