命令型言語である単純なプログラミング言語のインタプリタ（Haskellで）を実装するにはどうすればいいですか

Question

言語の意味論と私が知るべきすべてを与えられています。データ型の概念ではありません。だから私は変数に何かを格納し、それらを操作することができます。

私はループと条件と関数呼び出しを持っていたでしょう。 私は理論の本ではなく、最初の例を探しています。ハスケルでこのような基本的な言語通訳を実装した人はいますか？私はポインタと参照を探しています。

ありがとうございます！

Answer 1

私は練習プロジェクトとして現在作業中です。

これは動的型言語なので、変数を宣言する必要はありませんが、各値には関連する型があります。 、プログラムの実行のために

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

私はIOの上にStateTとErrorTモナド変圧器使用しています：「文脈」

-- | 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) 

をである私はHaskellでは代数的データ型を使用していることを実装しましたデータスタック（スタックベースの言語）と、現在スコープ内にあるすべての変数を保持する「環境」の組み合わせ。

-- | 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さんget、putをモデルにした、とmodify機能が、彼らはただ一つのフィールド上で動作していますRPLContextのレコードの

すべての言語の組み込みコマンドは、のようなツールの上に構築されたRPLモナドのアクションに過ぎません。

私の言語でコードを解析する場合は、Parsecを使用しています。それはかなり良いです。別のトラックに

---

は、私のRPLインタプリタに関係のない、あなたは「 Write Yourself a Scheme in 48 Hours」役に立つかもしれません。

Answer 2

Mapを使用して、可変変数をエミュレートするために、StateTのモナドでインタープリタを実行することが1つの方法です。簡単な例：

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は、符号化するために、これは非常に簡単です：あなたも、専用のEDSLせずに、このような単純な何かを行うことができ、簡単な言語では

{-# 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 ... 

：

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