haskell - 在Haskell中创建翻译

因此，我需要编写一个函数evalS :: Statement -> Store -> Store，该函数将一条语句和一个存储作为输入，并返回一个可能经过修改的存储。

以下是我的情况：

evalS w@(While e s1) s = case (evalE e s) of
                          (BoolVal True,s')  -> let s'' = evalS s1 s' in evalS w s''
                          (BoolVal False,s') -> s'
                          _                  -> error "Condition must be a BoolVal

我需要写：

evalS Skip s             = ...
evalS (Expr e) s         = ...
evalS (Sequence s1 s2) s = ...
evalS (If e s1 s2) s     = ...

在If的情况下，如果e计算为非布尔值，则需要使用error函数引发错误。

样本输入/输出：

> run stmtParser "x=1+1" evalS
fromList [("x",2)]
> run stmtParser "x = 2; x = x + 3" evalS
fromList [("x",5)]
> run stmtParser "if true then x = 1 else x = 2 end" evalS
fromList [("x",1)]
> run stmtParser "x=2; y=x + 3; if y < 4 then z = true else z = false end" evalS
fromList [("x",2),("y",5),("z",false)]
> run stmtParser "x = 1; while x < 3 do x = x + 1 end" evalS
fromList [("x",3)]
> run stmtParser "x = 1 ; y = 1; while x < 5 do x = x + 1 ; y = y * x end" evalS
fromList [("x",5),("y",120)]

stmtParser的代码：

-- Sequence of statements
stmtParser :: Parser Statement
stmtParser = stmtParser1 `chainl1` (P.semi lexer >> return Sequence)

-- Single statements
stmtParser1 :: Parser Statement
stmtParser1 = (Expr <$> exprParser)
          <|> do
              P.reserved lexer "if"
              cond <- exprParser
              P.reserved lexer "then"
              the <- stmtParser
              P.reserved lexer "else"
              els <- stmtParser
              P.reserved lexer "end"
              return (If cond the els)
          <|> do
              P.reserved lexer "while"
              cond <- exprParser
              P.reserved lexer "do"
              body <- stmtParser
              P.reserved lexer "end"
              return (While cond body)

我尝试过的内容：

我不确定是否需要在此问题中使用evalE。我已经在先前的问题中写过它。 evalE的签名是evalE :: Expression -> Store -> (Value, Store)，并要求我写：

evalE (Var x) s = ...
evalE (Val v) s = ...
evalE (Assignment x e) s = ...

我已经完成了以上操作。

尝试：

evalS Skip s             = show s -- I am assuming that since Skip returns an empty String, I just need to return an empty String.
evalS (Sequence s1 s2) s = evalS s1 >> evalS s2 -- sequence1 then sequence2. I am not quite sure what to do with the s.
evalS (Expr e) s         = ... Not sure what to do, here.
evalS (If e s1 s2) s     = do
   x <- evalE e
   case x of
      BoolVal True -> evalS s1
      BoolVal False -> evalS s2

我在写上述声明时遇到麻烦。

作为参考，这是给我使用的整个骨架：

-- Necessary imports
import Control.Applicative ((<$>),liftA,liftA2)
import Data.Map
import Text.Parsec
import Text.Parsec.Expr
import Text.Parsec.Language (emptyDef)
import Text.Parsec.String (Parser)
import qualified Text.Parsec.Token as P


--------- AST Nodes ---------

-- Variables are identified by their name as string
type Variable = String

-- Values are either integers or booleans
data Value = IntVal Int       -- Integer value
           | BoolVal Bool     -- Boolean value

-- Expressions are variables, literal values, unary and binary operations
data Expression = Var Variable                    -- e.g. x
                | Val Value                       -- e.g. 2
                | BinOp Op Expression Expression  -- e.g. x + 3
                | Assignment Variable Expression  -- e.g. x = 3

-- Statements are expressions, conditionals, while loops and sequences
data Statement = Expr Expression                   -- e.g. x = 23
               | If Expression Statement Statement -- if e then s1 else s2 end
               | While Expression Statement        -- while e do s end
               | Sequence Statement Statement      -- s1; s2
               | Skip                              -- no-op

-- All binary operations
data Op = Plus         --  +  :: Int -> Int -> Int
        | Minus        --  -  :: Int -> Int -> Int
        | Times        --  *  :: Int -> Int -> Int
        | GreaterThan  --  >  :: Int -> Int -> Bool
        | Equals       --  == :: Int -> Int -> Bool
        | LessThan     --  <  :: Int -> Int -> Bool

-- The `Store` is an associative map from `Variable` to `Value` representing the memory
type Store = Map Variable Value

--------- Parser ---------

-- The Lexer

lexer = P.makeTokenParser (emptyDef {
  P.identStart = letter,
  P.identLetter = alphaNum,
  P.reservedOpNames = ["+", "-", "*", "!", ">", "=", "==", "<"],
  P.reservedNames = ["true", "false", "if", "in", "then", "else", "while", "end", "to", "do", "for"]
})

-- The Parser

-- Number literals
numberParser :: Parser Value
numberParser = (IntVal . fromIntegral) <$> P.natural lexer

-- Boolean literals
boolParser :: Parser Value
boolParser =  (P.reserved lexer "true" >> return (BoolVal True))
          <|> (P.reserved lexer "false" >> return (BoolVal False))

-- Literals and Variables
valueParser :: Parser Expression
valueParser =  Val <$> (numberParser <|> boolParser)
           <|> Var <$> P.identifier lexer

-- -- Expressions
exprParser :: Parser Expression
exprParser = liftA2 Assignment
                    (try (P.identifier lexer >>= (\v ->
                          P.reservedOp lexer "=" >> return v)))
                    exprParser
          <|> buildExpressionParser table valueParser
    where table = [[Infix (op "*" (BinOp Times)) AssocLeft]
                  ,[Infix (op "+" (BinOp Plus)) AssocLeft]
                  ,[Infix (op "-" (BinOp Minus)) AssocLeft]
                  ,[Infix (op ">" (BinOp GreaterThan)) AssocLeft]
                  ,[Infix (op "==" (BinOp Equals)) AssocLeft]
                  ,[Infix (op "<" (BinOp LessThan)) AssocLeft]]
          op name node = (P.reservedOp lexer name) >> return node

-- Sequence of statements
stmtParser :: Parser Statement
stmtParser = stmtParser1 `chainl1` (P.semi lexer >> return Sequence)

-- Single statements
stmtParser1 :: Parser Statement
stmtParser1 = (Expr <$> exprParser)
          <|> do
              P.reserved lexer "if"
              cond <- exprParser
              P.reserved lexer "then"
              the <- stmtParser
              P.reserved lexer "else"
              els <- stmtParser
              P.reserved lexer "end"
              return (If cond the els)
          <|> do
              P.reserved lexer "while"
              cond <- exprParser
              P.reserved lexer "do"
              body <- stmtParser
              P.reserved lexer "end"
              return (While cond body)

-------- Helper functions --------

-- Lift primitive operations on IntVal and BoolVal values
liftIII :: (Int -> Int -> Int) -> Value -> Value -> Value
liftIII f (IntVal x) (IntVal y) = IntVal $ f x y
liftIIB :: (Int -> Int -> Bool) -> Value -> Value -> Value
liftIIB f (IntVal x) (IntVal y) = BoolVal $ f x y

-- Apply the correct primitive operator for the given Op value
applyOp :: Op -> Value -> Value -> Value
applyOp Plus        = liftIII (+)
applyOp Minus       = liftIII (-)
applyOp Times       = liftIII (*)
applyOp GreaterThan = liftIIB (>)
applyOp Equals      = liftIIB (==)
applyOp LessThan    = liftIIB (<)

-- Parse and print (pp) the given WHILE programs
pp :: String -> IO ()
pp input = case (parse stmtParser "" input) of
    Left err -> print err
    Right x  -> print x

-- Parse and run the given WHILE programs
run :: (Show v) => (Parser n) -> String -> (n -> Store -> v) -> IO ()
run parser input eval = case (parse parser "" input) of
    Left err -> print err
    Right x  -> print (eval x empty)

最佳答案

回答您的问题有点困难，因为您实际上没有问过一个问题。为了让您获得一些线索，让我挑选一些您所说的话。

我不确定是否需要在此问题中使用evalE。我已经在先前的问题中写过它。 evalE的签名是evalE :: Expression -> Store -> (Value, Store)
evalS (Expr e) s = ... Not sure what to do, here.

执行包含表达式的语句意味着什么？如果它与评估表达式有关，那么可以使用表达式评估器这一事实可能有助于“在这里做什么”。
接下来，比较为“ while”提供的代码（顺便说一下，其中包含与表达式相关的明智示例）...

evalS w@(While e s1) s = case (evalE e s) of`
  (BoolVal True,s')  -> let s'' = evalS s1 s' in evalS w s''
  (BoolVal False,s') -> s'
  _                  -> error "Condition must be a BoolVal"

...并将其与您的代码“ if”进行比较

evalS (If e s1 s2) s     = do
   x <- evalE e
   case x of
      BoolVal True -> evalS s1
      BoolVal False -> evalS s2

您的代码采用了一种截然不同的样式-“ monadic”样式。你从哪里得到的？如果评估者的类型类似于

evalE :: Expression -> State Store Value
evalS :: Statement  -> State Store ()

单子风格是在评估过程中将变异存储线程化的一种非常好的方法，而无需过多地谈论它。例如，您的x <- evalE e意思是“让x是评估e的结果（安静地接收初始存储并传递结果存储）”。这是一种很好的工作方式，我希望您会在适当的时候进行探索。
但是，这些不是您得到的类型，因此，单子风格是不合适的。你有

evalE :: Expression -> Store -> (Value, Store)
evalS :: Statement  -> Store ->         Store

示例代码显式地线程化存储。再看一遍

evalS w@(While e s1) s = case (evalE e s) of`
  (BoolVal True,s')  -> let s'' = evalS s1 s' in evalS w s''
  (BoolVal False,s') -> s'
  _                  -> error "Condition must be a BoolVal"

看到？ evalS显式接收其初始存储s，并在evalE e s中显式使用它。在两个s'分支中，生成的新存储都称为case。如果循环结束，则将s'作为最终存储返回。否则，将s'用作一次循环主体s1的存储，并将由此产生的存储s''用于下一次循环w。
您的代码在评估的每个阶段都需要类似地明确地命名和使用商店。让我们来看看。

evalS Skip s             = show s -- I am assuming that since Skip returns an empty String, I just need to return an empty String.

您假设错误。 evalS函数不返回String，为空或以其他方式返回：它返回Store。现在，哪个Store？您最初的商店是s：“跳过”之后的商店与s有何关系？

evalS (Sequence s1 s2) s = evalS s1 >> evalS s2 -- sequence1 then sequence2. I am not quite sure what to do with the s.

同样，这是一种单调的方法，不适合这个问题。您需要通过依次评估语句s和s1的过程来对存储（尤其是s2）进行线程化。 “ while”案例有一个很好的例子，说明了如何做这样的事情。

evalS (Expr e) s         = ... Not sure what to do, here.

同样，“ while”示例向您展示了一种通过评估表达式来提取值和更新存储的方法。值得深思，不是吗？

evalS (If e s1 s2) s     = ...

现在，“ if”通过评估条件开始，非常像“ while”，不是吗？
因此，我的建议是：

现在删除单子风格代码，但稍后在合适时再返回；
阅读“ while”的示例实现，并了解它如何处理表达式和语句序列，并显式传递存储；
部署类似的技术来实现其他构造。

提出问题的人足够友好地为您提供代码，该代码给出了您所需的一切示例。请理解并以暗示的方式来回报这种好意！