4

Haskell でプログラムを作成して、整数変数、1 次元 (整数) 配列、および関数を使用して命令型言語プログラムの表示セマンティクスを計算しようとしています。私が始めている関数は次のタイプです：

    progsem :: Prog -> State -> State

State は次のとおりです。

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

最初の部分は整数変数の値で、2 番目の部分は特定のインデックスにある配列変数の値です。

プログラムには次のような特徴があります。

  • progsem は、プログラムの実行後に結果の状態を返します

  • 関数には、整数変数用と配列変数用の 2 つのパラメーター リストがあります。

  • 関数は値の結果によって呼び出されます

命令型言語の抽象構文は次のとおりです。

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

プログラムは、プログラムの実行後に結果の状態を返します

インタープリターを実行するには、変数のバインド環境とヒープ上の値の 2 つの値を渡す必要があります。これにより、結果の値とメモリ状態のタプルが返され、REPL のようなループを構築する場合に関数自体にフィードバックできます。

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

initMem = []
initTermEnv = Map.empty

命令型言語を作成しているため、状態と参照を追加する可能性が高いため、割り当てと変更を行う新しい AST ノードを作成できますRefs。Arrayあとは、 an を 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 モナド関数の薄いラッパーであるヒープ上の値を処理するためのヘルパー関数が必要になります。

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 に答える