哈斯克爾 - 發現未聲明的變量

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的情況，我們不能只是否定r遞歸調用了，因爲 否定沒有定義爲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將會有八個案例！

因此，讓一個輔助函數來爲我們做這一點：爲Sum，Mul和If

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) 

現在定義的情況下是很容易：

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情況下少哈克將來自Either [Identifier] Int改變eval返回類型([Identifier], [(Identifier, Int)] -> Int) - 有它返回所有的免費VAR名單可以在表達式中使用iables，以及在給定綁定這些變量的情況下評估表達式的方法。

如果我們給該類型的名稱：

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