4

我正在尝试在 Haskell 中编写一个程序来计算具有整数变量、一维（整数）数组和函数的命令式语言程序的指称语义。我开始使用的功能是以下类型：

    progsem :: Prog -> State -> State

其中状态如下：

    type State (Name -> Int, Name -> Int -> Int)

第一部分是整数变量的值，而第二部分是特定索引处的数组变量的值。

该计划将具有以下品质：

  • progsem 将在程序执行后返回结果状态

  • 函数有两个参数列表，一个用于整数变量，一个用于数组变量。

  • 函数按值调用结果

下面是命令式语言的抽象语法：

     -- names (variables) are just strings.
     type Name = String

     -- a program is a series (list) of function definitions, followed by a
     -- series of statements.
     type Prog = ([FunDefn],[Stmt])

     -- a statement is either...
     data Stmt =
         Assign Name Exp              -- ...assignment (<name> := <exp>;)
       | If BExp [Stmt] [Stmt]        -- ...if-then-else (if <bexp> { <stmt>* } else { <stmt>* })
       | While BExp [Stmt]            -- ...or a while-loop (while <bexp> { <stmt>*> })
       | Let Name Exp [Stmt]          -- ...let bindings (let <name>=<exp> in { <stmt> *}) 
       | LetArray Name Exp Exp [Stmt] -- ...let-array binding (letarray <name> [ <exp> ] := <exp> in { <stmt>* })
       | Case Exp [(Int,[Stmt])]      -- ...case statements
       | For Name Exp Exp [Stmt]      -- ...for statements 
       | Return Exp                   -- ...return statement
       | ArrayAssign Name Exp Exp     -- ...or array assignment (<name> [ <exp> ] := <exp>;)
       deriving Show

     -- an integer expression is either...
     data Exp =
         Add Exp Exp              -- ...addition (<exp> + <exp>)
       | Sub Exp Exp              -- ...subtract (<exp> - <exp>)
       | Mul Exp Exp              -- ...multiplication (<exp> * <exp>)
       | Neg Exp                  -- ...negation (-<exp>)
       | Var Name                 -- ...a variable (<name>)
       | LitInt Int               -- ...or an integer literal (e.g. 3, 0, 42, 1999)
       | FunCall Name [Exp] [Name] -- ...or a function call (<name> (<exp>,...,<exp> [; <name>,...,<name>]))
       | VarArray Name Exp        -- ...or an array lookup (<name> [ <exp> ])
       deriving Show

     -- a boolean expression is either...
     data BExp =
         IsEq Exp Exp            -- ...test for equality (<exp> == <exp>)
       | IsNEq Exp Exp           -- ...test for inequality (<exp> != <exp>)
       | IsGT Exp Exp            -- ...test for greater-than (<exp> > <exp>)
       | IsLT Exp Exp            -- ...test for less-than (<exp> < <exp>)
       | IsGTE Exp Exp           -- ...test for greater-or-equal (<exp> >= <exp>)
       | IsLTE Exp Exp           -- ...test for less-or-equal (<exp> <= <exp>)
       | And BExp BExp           -- ...boolean and (<bexp> && <bexp>)
       | Or BExp BExp            -- ...boolean or (<bexp> || <bexp>)
       | Not BExp                -- ...boolean negation (!<bexp>)
       | LitBool Bool            -- ... or a boolean literal (true or false)
       deriving Show

     type FunDefn = (Name,[Name],[Name],[Stmt])

现在，我没有具体的问题，但我想知道是否有人可以为我指出如何编写语义的正确方向。

在过去，我为没有数组和函数的命令式编程语言做过类似的事情。它看起来像这样：

   expsem :: Exp -> State -> Int
   expsem (Add e1 e2) s = (expsem e1 s) + (expsem e2 s)
   expsem (Sub e1 e2) s = (expsem e1 s) - (expsem e2 s)
   expsem (Mul e1 e2) s = (expsem e1 s) * (expsem e2 s)
   expsem (Neg e) s   = -(expsem e s)
   expsem (Var x) s   = s x
   expsem (LitInt m) _ = m 


   boolsem :: BExp -> State -> Bool
   boolsem (IsEq  e1 e2) s = expsem e1 s == expsem e2 s       
   boolsem (IsNEq e1 e2) s= not(expsem e1 s == expsem e2 s)
   boolsem (IsGT  e1 e2) s= expsem e1 s >  expsem e2 s
   boolsem (IsGTE e1 e2) s= expsem e1 s >=  expsem e2 s
   boolsem (IsLT e1 e2)  s= expsem e1 s < expsem e2 s
   boolsem (IsLTE e1 e2) s= expsem e1 s <= expsem e2 s
   boolsem (And   b1 b2) s= boolsem b1 s &&  boolsem b2 s
   boolsem (Or    b1 b2) s= boolsem b1 s || boolsem b2 s
   boolsem (Not b)       s= not (boolsem b s)          
   boolsem (LitBool x)   _= x          




   stmtsem :: Stmt -> State -> State
   stmtsem (Assign x e) s = (\z -> if (z==x) then expsem e s else s z)   
   stmtsem (If b pt pf) s = if (boolsem b s) then (progsem pt s) else (progsem pf s) 
   stmtsem (While b p)  s = if (boolsem b s) then stmtsem (While b p) (progsem p s) else s
   stmtsem (Let x e p) s = s1 where
                  initvalx = s x
                  letvalx = expsem e s
                  snew = progsem p (tweak s x letvalx)
                  s1 z = if (z == x) then initvalx else snew z 

   tweak :: State->Name->Int->State
   tweak s vr n = \y -> if vr == y then n else s y 

   progsem :: Prog -> State -> State
   progsem smlist s0 = (foldl (\s -> \sm -> (stmtsem sm s)) (s0) ) smlist

   s :: State
   s "x" = 10

州属于那种类型

  type State=  Name -> Int

就像我说的那样，我不需要深入的答案，但任何帮助/提示/指针将不胜感激。

4

1 回答 1

5

我将与您给定的代码稍有不同，并指出您可能如何开始编写一个单子解释器，该解释器对一种玩具命令式语言的评估语义进行编码，就像您指定的那样。你需要一个像你一样的前端 AST：

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

data Expr = Var Var
          | App Expr Expr
          | Fun Var Expr
          | Lit Ground
          | If Expr Expr Expr
          -- Fill in the rest
          deriving (Show, Eq, Ord)

data Ground = LInt Integer
            | LBool Bool
            deriving (Show, Eq, Ord)

我们将通过函数评估eval具体Value类型。

data Value = VInt Integer
           | VBool Bool
           | VUnit
           | VAddress Int
           | VClosure String Expr TermEnv

type TermEnv = Map.Map String Value
type Memory = [Value]
type Interpreter t = State Memory t

eval :: TermEnv -> Expr -> State Memory Value
eval _ (Lit (LInt k)) = return $ VInt k
eval _ (Lit (LBool k)) = return $ VBool k
eval env (Fun x body) = return (VClosure x body env)
eval env (App fun arg) = do
  VClosure x body clo <- eval env fun
  res <- eval env fun
  args <- eval env arg
  let nenv = Map.insert x args clo
  eval nenv body
eval env (Var x) = case (Map.lookup x env) of
  Just v -> return v
  Nothing -> error "prevent this statically!"
eval env (If cond tr fl) = do
  VBool br <- eval env cond
  if br == True
  then eval env tr
  else eval env fl

-- Finish with the rest of your syntax.

程序将在程序执行后返回结果状态

要运行解释器，我们需要为其提供两个值：变量的绑定环境和堆上的值。这将返回结果值和内存状态的元组，如果构建类似 REPL 的循环，您可以将其反馈给函数本身。

runInterpreter :: TermEnv -> Memory -> Expr -> (Value, [Value])
runInterpreter env mem x = runState (eval env x) mem

initMem = []
initTermEnv = Map.empty

由于您正在编写命令式语言，因此您可能想要添加状态和引用，因此您可以创建新的 AST 节点来工作分配和变异Refs。留给您做的是添加将 an 分配Array为 s 序列的逻辑，Ref并在对其进行索引和分配时使用指针算法。

data Expr = -- Same as above
          | Ref Expr
          | Access Expr
          | Assign Expr Expr

eval :: TermEnv -> Expr -> State Memory Value
...
eval env (Ref e) = do
  ev <- eval env e
  alloc ev
eval env (Access a) = do
  VAddress i <- eval env a
  readAddr i
eval env (Assign a e) = do
  VAddress i <- eval env a
  ev <- eval env e
  updateAddr ev i

有了这个，我们将需要一些帮助函数来处理堆上的值，它们只是 State monad 函数的薄包装。

access :: Int -> Memory -> Value
access i mem = mem !! i

update :: Int -> Value -> Memory -> Memory
update addr val mem = a ++ [val] ++ b
  where
    (a, _:b) = splitAt addr mem

alloc :: Value -> Interpreter Value
alloc val = do
  mem <- get
  put $ mem ++ [val]
  return $ VAddress (length mem)

readAddr :: Int -> Interpreter Value
readAddr i = do
  mem <- get
  return $ access i mem

updateAddr ::  Value -> Int -> Interpreter Value
updateAddr val i = do
  mem <- get
  put $ update i val mem
  return VUnit

希望这有助于您入门。

于 2013-12-04T19:53:25.087 回答