Geek asks and answers

How do you go about implementing an interpreter (in Haskell) for a simple programming language, which is an imperative style language

They gave me the semantics of the language and everything I need to know. It supported only a few operations and there would be no concept of data types. Therefore, I can store something in a variable and work with them.

I would have cycles, conditions and function calls, and that’s it. I am looking for a start, an example is not a theory book. Has anyone ever implemented such a basic language translator in Haskell? I am looking for pointers and links.

Thank!

+3
source share
4 answers

I am working on it right now as a practical project.

, , . , 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 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 data stack.
  contextEnv :: Env  -- ^ The context 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, , pushValue.

Parsec. .

, RPL, "" 48 ".

+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 = ...

, . . StateT .

+6

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. ( , ).

+3

Here is some resource https://github.com/budabudimir/imp_interpreter , this is an interpreter for a simple imperative language described here http://fsl.cs.illinois.edu/images/0/0d/CS522-Spring-2011- PL-book-imp.pdf

+1
source

More articles:


All Articles