3

我已经获得了语言语义和我应该知道的一切。它只支持很少的操作，并且不会有任何数据类型的概念。所以我可以将任何东西存储在一个变量中并对其进行操作。

我会有循环、条件和函数调用，就是这样。我正在寻找一个开始，一个例子而不是一本理论书。有没有人在 Haskell 中实现过这样一个基本的语言解释器？我正在寻找指针和参考。

谢谢 ！

4

4 回答 4

6

我现在正在做一个练习项目。

它是一种动态类型的语言，因此不必声明变量，但每个值都有一个关联的类型。我在 Haskell 中使用代数数据类型实现了这一点：

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

对于程序的执行，我在上面使用了StateTand 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的一个字段。getputmodifyRPLContext

所有语言的内置命令都只是RPLmonad 中的操作，它建立在pushValue.

为了用我的语言解析代码，我使用Parsec。这很不错。

在与我的 RPL 解释器无关的单独轨道上，您可能会发现“在 48 小时内为自己编写一个方案”很有帮助。

于 2012-04-27T05:26:23.180 回答
6

我会首先在 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 将函数式编程的概念作为其结论。让解析器返回程序本身。然后你只需要用合适的起始状态 runStateT 它。

于 2012-04-27T05:40:47.910 回答
3

一种方法是让您的解释器在StateT monad 中运行，使用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"

然后解释器将在InterpretMmonad 中运行。上面的访问器允许它访问可变变量（不支持像闭包和词法范围这样的优点）。

于 2012-04-27T05:17:37.327 回答
1

这是一些资源https://github.com/budabudimir/imp_interpreter，这是这里描述的简单命令式语言的解释器http://fsl.cs.illinois.edu/images/0/0d/CS522-Spring-2011-PL -book-imp.pdf

于 2015-03-22T11:03:33.000 回答