Haskell - 解析された式の変数の状態（変数がバインドされているかどうか）

Question

こんにちは、文字列を受け取り、intまたはboolのいずれかの値を計算する関数を得ました。文字列は、「* let X = 3 in + X 1 2」であり、「(let X = 3 in (X + 1)) * 2」を表す。もし私がブールを求めるなら、それは私に8か偽を与えるでしょう。十分に簡単です。しかし、私はまた、パーサのバインドされた変数の状態をチェックしたい。私。この "* let X = 3 in + X 1 X"のような文字列を入力として使用すると、 "(let X = 3 in (X + 1)) * X"となり、最後のXはアンバインドされます。これは、変数Aがバインドされていないか何かであるというエラーを私に与えます。 誰かが私にこのことをどうやってできるか考えてもらえれば、とても感謝しています！解析された文字列の

Expample：

((let X = 3 in (X + 1)) * 2)

は私を与える：

(Mul (Let (Vari X) (Lit (Single 3)) (Sum (Vari X) (Lit (Single 1)))) (Vari X))

をだから私の質問は、解析された文字列に結合していない変数を持っている場合、私は確認することができますどのようにbasicllyです。

data Number = Single Int | Many Int Number deriving (Eq, Show) 

data Expr = Vari Chara | Lit Number | Sub Expr | Sum Expr Expr | Mul Expr Expr | Let Expr Expr Expr | If Expr Expr Expr deriving (Eq, Show) 

Answer 1

バインドされた変数のセットを保持して、解析された式を再帰します。あなたがVarに出くわすたびに、Letに出くわすたびにそれを記録し、それがあなたのセットに入っていることを確認し、何か他のものに遭遇するたびに、そのサブ表現をチェックしてください。

checkVars' :: Set String -> Expr -> Bool 
checkVars' bound (Var v) = S.member v set 
checkVars' bound (Let var val expr) = checkVars' bound val && checkVars' (insert var bound) expr 
checkVars' bound (Mul expr1 expr2) = checkVars' bound expr1 && checkVars' bound expr2 
-- Similar for other ctors... 

checkVars :: Expr -> Bool 
checkVars = checkVars' S.empty 

はまた、ボトムアップから自由変数の集合を構築し、あなたがLetに縛らそれらを見るたびに、変数を削除し、逆方向に動作することができます。 （これは、より自然な感じ。）私はバインディングと構文で（the extraordinarily useful bound libraryによって提供されるこのようなものなど）の変数のためのローカル無名表現を使用することをお勧めします

freeVars :: Expr -> Set String 
freeVars (Var v) = S.singleton v 
freeVars (Let var val expr) = S.union (freeVars val) $ S.delete var $ freeVars expr 
freeVars (Add expr1 expr2) = S.union expr1 expr2 
-- etc. 

checkVars :: Expr -> Bool 
checkVars = S.null . freeVars 

-- With recursion-schemes 
data ExprF a = Add a a 
      | Mul a a 
      | Let String a a 
      | Var String 
      | Lit Int 
      deriving (Eq, Show, Read, Functor, Foldable, Traversable) 

type Expr = Fix ExprF 

freeVars :: Expr -> Set String 
freeVars = cata go -- -XLambdaCase, anyone? 
    where go :: ExprF (Set String) -> Set String 
     go (Var var) = S.singleton var 
     go (Let var val expr) = S.union val $ S.delete var expr 
     go e = foldl S.union S.empty e -- Handle everything else 

Answer 2

。局所的に名前のない表現では、バインドされた変数はde Bruijnインデックスを使用して表され、バインドされていない変数は名前を使用して表されます。これは、アルファ等価性やキャプチャを避ける代用などの場合には、 "これは変数にバインドされていますか？"非常に簡単になります。

通常、ローカルで名前のない表現は、サーフェス構文ツリー上のスコープチェック操作の出力です。私たちは、代わりにBoolの確認期間を生成するために@HNTW's answerからコードを調整することができます

data Scoped a = SVar a 
       | SLet (Scoped a) (Scope() Scoped a) -- The expression being let-bound, and the subexpression with the new variable in scope 
       | SLit Number 
       | SSub (Scoped a) 
       | SSum (Scoped a) (Scoped a) 
       | SMul (Scoped a) (Scoped a) 
       | SIf (Scoped a) (Scoped a) (Scoped a) 
       deriving (Functor, Foldable, Traversable) 

instance Applicative Scoped where 
    pure = SVar 
    (<*>) = ap 

instance Monad Scoped where 
    return = SVar 
    SVar a >>= g = g a 
    SLet expr scope >>= g = SLet (expr >>= g) (scope >>>= g) 
    SLit x >>= g = SLit x 
    SSub x >>= g = SSub (x >>= g) 
    SSum x y >>= g = SSum (x >>= g) (y >>= g) 
    SMul x y >>= g = SMul (x >>= g) (y >>= g) 
    SIf cond t f >>= g = SIf (cond >>= g) (t >>= g) (f >>= g) 

scoped :: Expr -> Scoped Char 
scoped (Var x) = SVar x 
scoped (Let name expr sub) = SLet (scope expr) (abstract1 name $ scoped sub) 
scoped (Lit x) = SLit x 
scoped (Sub s) = SSub (scoped s) 
scoped (Sum x y) = SSum (scoped x) (scoped y) 
scoped (Mul x y) = SMul (scoped x) (scoped y) 
scoped (If cond t f) = SIf (scoped cond) (scoped t) (scoped f) 

bound名前aの「コンテナ」として表現を表示します。 Monadインスタンスは置換を実行します（(>>=) :: Scoped a -> (a -> Scoped b) -> Scoped bはaという名前の関数マッピング名をScoped bに移植して移植します）。boundライブラリでは、この置換操作を使用して、サブ式の変数をバインドして新しいサブ表現を生成するabstract1などのツールを実装しますローカルで名前のない形式で。

（別のExprタイプを削除してパーサーの出力として直接Scoped Charを生成することは不合理ではありません。）

ScopedのFoldableおよびTraversableインスタンスでは、式内のすべてのバインドされていない変数を見つけることができます。

unboundVariables :: Scoped a -> [a] 
unboundVariables = toList 

boundのisClosedコンビネータは、あなたが望んでいただけで何が行われます。式は任意の自由変数を持っている場合、それはFalseを返します。

スコープの下で歩いて、あなたが特定の変数が結合した、または自由されている場合、あなたはどちらかできVarのBとFコンストラクタ上のパターンマッチ、またはthe supplied Prismsを使用する知っている必要があり、場合：

isBound :: Var b f -> Bool 
isBound = is _B 

boundの詳細については、this blog postまたはthese slidesを参照してください。