Haskell - 查找未声明的变量

Question

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"))))

Answer 1

让我们从类型开始:

如果有任何未声明的变量,我需要在解析时给出包含所有未声明变量列表的适当错误.

一个函数如何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类型either具有一个适用于这种方式的应用实例,因此如果您愿意,可以使用:

>>> Failure ["foo"] <*> Failure ["bar", "baz"]
Failure ["foo", "bar", "baz"]

一种可能使Let案例不那么苛刻的方法是将evalfrom 的返回类型更改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!")