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"))))
最佳答案
让我们从类型开始:
If there are any undeclared variables I need to give an appropriate error containing a list of ALL undeclared variables either while parsing.
一个函数怎么样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)
但这非常冗长,并且与使用 fmap
完全相同来自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
将有八个案例!
因此,让我们创建一个辅助函数来为我们执行此操作:
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"]
但是,有 Validation
type from the either
package它有一个完全按照这种方式工作的应用实例,所以如果您愿意,您可以使用它:
>>> Failure ["foo"] <*> Failure ["bar", "baz"]
Failure ["foo", "bar", "baz"]
<小时/>
一种可能使 Let
成为可能的方法比较简单的情况是更改 eval
的返回类型来自Either [Identifier] Int
至([Identifier], [(Identifier, Int)] -> Int)
- 让它返回表达式中所有自由变量的列表,以及在给定这些变量的绑定(bind)的情况下计算表达式的方法。
如果我们给该类型一个名称:
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!")
关于Haskell - 查找未声明的变量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46589051/