Hytlのevalで同名引数の関数を入れ子に呼ぶとバグる件について

evalで以下のような入力をしたらバグってた

code:hytl

f = x => x

g = x => f(x)

g(1) // 停止しない

ちなみにこうしたら動く

code:hytl

f = x => x

g = y => f(y)

g(1)

関数の中で関数を呼ぶときに引数名がかぶっているとバグっていた

これの原因はgetVarするときにあった

そもそものEnvの構造

こういう感じで入力すると

code:hytl

x = 1

y = 2

f = x => x + 1

x = 10

こういう感じでスタックに積み上がっていく

code:env

"x": (Int 10) ↑

"f": (Lambda "x" (Plus (Var "x") (Int 1))) ↑

"y": (Int 2) ↑

"x": (Int 1) ↑

この辺の仕事をenvBindがやっている

code:hytlのイメージ

getVar "y" env // → (Int 2)

このときに同名のものがあれば、スタックの上側のものが返される

つまり、新しく定義した方の変数

code:hytlのイメージ

getVar "x" env // → (Int 10)

うまくいくときの挙動

上述したように、以下のように書けば正常に動く

code:hytl

f = x => x

g = y => f(y)

g(1) // 1

関数が呼ばれたときに、bindVarsがその実引数と仮引数を一致させる新たなenvを作る

code:env

"x": (Var "y") ┐

"y": (Int 1) ┐ |fのlocalEnv

"g": (Lambda "y" (App "f" (Var "y"))) ┐ | |

"f": (Lambda "x" (Var "x")) |env |gのlocalEnv

うまくいかないときの挙動

こういう構造になっている

code:env

"x": (Var "x")

"x": (Int 1)

"g": (Lambda "y" (App "f" (Var "y")))

"f": (Lambda "x" (Var "x"))

lookupは一番上のものを見るので。

そして、上のループが繰り返され、停止しなくなる

とりあえずの回避策

code:hs

getVar :: String -> Env -> IO Exp

getVar var env = do

e <- readIORef env

case lookup var e of

-- 同名だったら、envの後ろを見る

Just (Var v) -> if v == var

then do

ne <- newIORef (tail e)

getVar var ne

else return (Var v)

Just v -> return v

Nothing -> return (Var "error")

なので、もし、そこが一致していた場合は、

以下の様に、一番上の段を取り除いたenvを作り、同じ動作をするように直した

code:env

"x": (Int 1)

"g": (Lambda "y" (App "f" (Var "y")))

"f": (Lambda "x" (Var "x"))

一応動くようになったが、コーナーケースなどは考えられていない。