Haskell -查找未声明的变量
AST:
data AST = Nr Int | Sum AST AST | Mul AST AST | Min AST | If AST AST AST |
Let String AST AST | Var String deriving (Eq, Show)嗨!我需要帮助在输入中找到未声明的变量。我的问题是，我不能简单地在我的评估器中这样做：
eval :: Env -> AST -> Int
eval env (Nr nr) = nr
eval env (Sum xs xss) = eval env xs + eval env xss
eval env (Mul xs xss) = eval env xs * eval env xss
eval env (Min xs ) = - eval env xs
eval env (If x xs xss) = if (eval env x == 0)
then eval env xs
else eval env xss
eval env (Let s xs xss) = eval ((s, (eval env xs)) : env) xss
eval env (Var x) = case lookup x env of
Just n -> n
Nothing -> error ("Variable " ++ x ++ " is undeclared!")如果有任何未声明的变量，我需要在解析时给出一个包含所有未声明变量的列表的适当错误，或者在计算之前对我的AST进行后处理。我不知道从哪里开始。下面是一个解析表达式的示例：
parse "let X = + 1 2 in * X + 2 - X"
Let "X" (Sum (Nr 1) (Nr 2)) (Mul (Var "X") (Sum (Nr 2) (Min (Var "X"))))回答 1
Stack Overflow用户
发布于 2017-10-05 16:23:17
让我们从类型开始：
如果有任何未声明的变量，我需要在解析时给出一个包含所有未声明变量的列表的适当错误。
如果函数eval给出未声明变量的列表，或者给出一个Int (如果没有未声明的变量)，怎么样？
type Identifier = String
eval :: Env -> AST -> Either [Identifier] Int我们现在需要将原始数字包装在Right中：
eval env (Nr nr) = Right nr在Var情况下，声明的变量也是如此，而未声明的变量被包装在列表和Left中。
eval env (Var x) = case lookup x env of
Just n -> Right n
Nothing -> Left [x]对于Min情况，我们不能再否定递归调用了，因为否定不是为Either [Identifier] Int定义的。
我们可以通过模式匹配来看看我们得到了什么：
eval env (Min xs ) = case eval env xs of
Left err -> Left err
Right x -> Right (-x)但是，这是非常冗长的，并且与使用来自Either e的函子实例的Either e完全相同：
eval env (Min xs ) = fmap negate (eval env xs)类似地，对于Sum，我们可以对两个参数进行模式匹配：
eval env (Sum xs xss) = case (eval env xs, eval env xss) of
(Left err, Left err') -> Left (err ++ err')
(Left err, Right _) -> Left err
(Right _, Left err') -> Left err'
(Right a, Right b) -> Right (a + b)注意，如果两个子项都包含未声明的变量，那么我们将它们连接起来，以获得Sum下的未声明变量列表。
对于其余的构造函数来说，这也是我们需要的技巧。但是，我不想每次都要键入这样的大型case语句。这是一个小加法的大量工作！If和Let将有8箱！
因此，让我们为我们创建一个帮助函数来完成这个任务：
apply :: Either [Identifier] (a -> b) -> Either [Identifier] a -> Either [Identifier] b
apply (Left err) (Left err') = Left (err ++ err')
apply (Left err) (Right _) = Left err
apply (Right _) (Left err') = Left err'
apply (Right f) (Right a) = Right (f a)现在，为Sum、Mul和If定义用例要容易得多：
eval env (Sum xs xss) = fmap (+) (eval env xs) `apply` eval env xss
eval env (Mul xs xss) = fmap (*) (eval env xs) `apply` eval env xss
eval env (If x xs xss) = fmap jnz (eval env x) `apply` eval env xs `apply` eval env xss
where jnz i a a' = if i == 0 then a else a'Let略有不同：
eval env (Let s xs xss) = fmap second v `apply` eval env' xss
where val = eval env xs
env' = (s,val) : env
getRight (Right a) = a
getRight (Left _) = 0
second _ a = a注意，当第一个项包含一个未声明的变量时，我们如何“欺骗”第二个术语的环境中的伪值。由于我们不会使用任何Int值，所以在这种情况下，第二个项可能会产生结果，这是可以的。
一旦您深入到Haskell，您可能会注意到，apply看起来非常像来自Applicative的<*>。我们之所以不这么做，是因为Either e的Applicative实例没有按我们希望的方式工作。它不是聚合错误，而是在碰到第一个错误时退出：
>>> Left ["foo"] `apply` Left ["bar", "baz"]
Left ["foo", "bar", "baz"]
>>> Left ["foo"] <*> Left ["bar", "baz"]
Left ["foo"]但是，有一个应用程序实例正是以这种方式工作的 package，因此，如果您愿意，可以使用它：
>>> Failure ["foo"] <*> Failure ["bar", "baz"]
Failure ["foo", "bar", "baz"]一种可能使Let情况不那么麻烦的方法是将eval的返回类型从Either [Identifier] Int更改为([Identifier], [(Identifier, Int)] -> Int) --让它返回表达式中所有空闲变量的列表，以及在给定这些变量绑定的情况下计算表达式的方法。
如果我们给这个类型起个名字：
data Result a = Result { freeVariables :: [Identifier], eval :: [(Identifier,Int)] -> a }我们可以为它定义Functor和Applicative实例：
instance Functor Result where
fmap f (Result is g) = Result is (f . g)
instance Applicative Result where
pure a = Result [] (const a)
Result is ff <*> js fa = Result (is ++ js) (ff <*> js)并使用这些方法轻松地定义一个函数来解析空闲变量和eval表达式：
parse :: AST -> Result Int
parse (Nr nr) = pure nr
parse (Sum xs xss) = (+) <$> parse xs <*> parse xss
parse (Mul xs xss) = (*) <$> parse xs <*> parse xss
parse (Min xs ) = negate <$> parse xs
parse (If x xs xss) = jnz <$> parse x <*> parse xs <*> parse xss
where jnz a b c = if a == 0 then b else c
parse (Let s xs xss) = Result ks h
where Result is f = parse xs
Result js g = parse xss
ks = is ++ delete s js
h env = g ((s,f env):env)
parse (Var x) = Result [x] $ \env -> case lookup x env of
Just n -> n
Nothing -> error ("Variable " ++ x ++ " is undeclared!")https://stackoverflow.com/questions/46589051
复制相似问题
腾讯云开发者
