你如何在一个简单的编程语言中实现一个解释器(在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和ErrorTmonad变换器在上面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].)

在这个基础之上,我有各种辅助函数来执行操作,例如在当前上下文中操作堆栈(由monad 的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的get,put和modify功能,但他们只是在一个领域上操作RPLContext的记录.

所有语言的内置命令都只是RPLmonad中的动作,它们构建在像pushValue.之类的工具之上.

为了用我的语言解析代码,我正在使用Parsec.这很不错.

在与我的RPL翻译无关的单独轨道上,您可能会发现" 在48小时内为自己编写一个方案 "很有帮助.

Answer 2

我首先在EDSL中编码整个程序.EDSL本身就是一个monad并且类似于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.