Haskellの相互再帰評価者
https://stackoverflow.com/questions/3524485
-
29-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
アップデート： 私は追加しました 答え それは私の最終的な解決策を説明しています（ヒント：シングル Expr データ型は十分ではありませんでした）。
私は 書き込み 少しの表現言語の評価者ですが、私は LetRec 構成。
これが言語です：
type Var = String
type Binds = [(Var, Expr)]
data Expr
= Var Var
| Lam Var Expr
| App Expr Expr
| Con Int
| Sub Expr Expr
| If Expr Expr Expr
| Let Var Expr Expr
| LetRec Binds Expr
deriving (Show, Eq)
そして、これはこれまでの評価者です：
data Value
= ValInt Int
| ValFun Env Var Expr
deriving (Show, Eq)
type Env = [(Var, Value)]
eval :: Env -> Expr -> Either String Value
eval env (Var x) = maybe (throwError $ x ++ " not found")
return
(lookup x env)
eval env (Lam x e) = return $ ValFun env x e
eval env (App e1 e2) = do
v1 <- eval env e1
v2 <- eval env e2
case v1 of
ValFun env1 x e -> eval ((x, v2):env1) e
_ -> throwError "First arg to App not a function"
eval _ (Con x) = return $ ValInt x
eval env (Sub e1 e2) = do
v1 <- eval env e1
v2 <- eval env e2
case (v1, v2) of
(ValInt x, ValInt y) -> return $ ValInt (x - y)
_ -> throwError "Both args to Sub must be ints"
eval env (If p t f) = do
v1 <- eval env p
case v1 of
ValInt x -> if x /= 0
then eval env t
else eval env f
_ -> throwError "First arg of If must be an int"
eval env (Let x e1 e2) = do
v1 <- eval env e1
eval ((x, v1):env) e2
eval env (LetRec bs e) = do
env' <- evalBinds
eval env' e
where
evalBinds = mfix $ \env' -> do
env'' <- mapM (\(x, e') -> eval env' e' >>= \v -> return (x, v)) bs
return $ nub (env'' ++ env)
これは私が評価したい私のテスト機能です：
test3 :: Expr
test3 = LetRec [ ("even", Lam "x" (If (Var "x")
(Var "odd" `App` (Var "x" `Sub` Con 1))
(Con 1)
))
, ("odd", Lam "x" (If (Var "x")
(Var "even" `App` (Var "x" `Sub` Con 1))
(Con 0)
))
]
(Var "even" `App` Con 5)
編集：
Travisの答えとLukeのコメントに基づいて、私は自分の更新を更新しました コード Error MonadにMonadfixインスタンスを使用します。前の例は今正常に動作します！ただし、Bellowの例は正しく機能しません。
test4 :: Expr
test4 = LetRec [ ("x", Con 3)
, ("y", Var "x")
]
(Con 0)
これを評価するとき、評価者はループし、何も起こりません。ここで少し厳しすぎるものを作ったと思いますが、それが何であるかはわかりません。 Monadfix法の1つに違反していますか？
解決
Haskellがフィット感を投げたとき、それは通常、問題の中核的な問題についてはっきりと考えていないことを示しています。この場合、質問は次のとおりです 評価モデル あなたはあなたの言語に使いたいですか？ by-valueまたはcall-by-by？
環境の表現 [(Var,Value)] すべてが Expr に評価されます Value 環境に保管する直前。だが letrec それにはうまくいきません、そしてあなたの2番目の例が示しています！
さらに、ホスト言語の評価モデル（Haskell）は、実装する言語の評価モデルに干渉することに注意してください。実際、それはあなたが現在あなたの例で利用しているものです：彼らの目的にもかかわらず、あなたの ValueSは、弱い頭の正常形態に評価されません。
あなたの小さな表現言語の評価モデルの明確な画像がない限り、あなたはあまり進歩することはありません letrec または、エラーチェック施設で。
編集：の例の仕様 letrec 価値のある言語で、 OCAMLマニュアル. 。最も単純なレベルでは、ラムダ式である右側の右側のみ、つまり値であることが構文的に知られているものを許可します。
他のヒント
たぶん私は何かが足りないのですが、次の仕事はありませんか？
eval env (LetRec bs ex) = eval env' ex
where
env' = env ++ map (\(v, e) -> (v, eval env' e)) bs
更新されたバージョンについて：次のアプローチはどうですか？それはあなたのテストケースで望ましいとおりに機能し、エラーを捨てません LetRec 表現：
data Value
= ValInt Int
| ValFun EnvWithError Var Expr
deriving (Show, Eq)
type Env = [(Var, Value)]
type EnvWithError = [(Var, Either String Value)]
eval :: Env -> Expr -> Either String Value
eval = eval' . map (second Right)
where
eval' :: EnvWithError -> Expr -> Either String Value
eval' env (Var x) = maybe (throwError $ x ++ " not found")
(join . return)
(lookup x env)
eval' env (Lam x e) = return $ ValFun env x e
eval' env (App e1 e2) = do
v1 <- eval' env e1
v2 <- eval' env e2
case v1 of
ValFun env1 x e -> eval' ((x, Right v2):env1) e
_ -> throwError "First arg to App not a function"
eval' _ (Con x) = return $ ValInt x
eval' env (Sub e1 e2) = do
v1 <- eval' env e1
v2 <- eval' env e2
case (v1, v2) of
(ValInt x, ValInt y) -> return $ ValInt (x - y)
_ -> throwError "Both args to Sub must be ints"
eval' env (If p t f) = do
v1 <- eval' env p
case v1 of
ValInt x -> if x /= 0
then eval' env t
else eval' env f
_ -> throwError "First arg of If must be an int"
eval' env (Let x e1 e2) = do
v1 <- eval' env e1
eval' ((x, Right v1):env) e2
eval' env (LetRec bs ex) = eval' env' ex
where
env' = env ++ map (\(v, e) -> (v, eval' env' e)) bs
私自身の質問に答える。思いついた最後の解決策を共有したかった。
ハインリッヒとして正しく 指摘した, 、私は評価順序が与える影響を本当に考えていませんでした。
厳格な（価値のある）言語では、すでに値（弱いヘッド正常形式）である式は、まだ何らかの評価が必要な式とは異なります。データ型でこの区別をエンコードすると、すべてが所定の位置に落ちました。
type Var = String
type Binds = [(Var, Val)]
data Val
= Con Int
| Lam Var Expr
deriving (Show, Eq)
data Expr
= Val Val
| Var Var
| App Expr Expr
| Sub Expr Expr
| If Expr Expr Expr
| Let Var Expr Expr
| LetRec Binds Expr
deriving (Show, Eq)
私のオリジナルとの唯一の違い Expr データ型は、2つのコンストラクターを引き出したことです（Con と Lam）独自のデータ型に Val. 。 Expr データ型には新しいコンストラクターがあります Val, 、これは、値も有効な式であるという事実を表しています。
独自のデータ型の値を使用すると、たとえば他の式とは別に処理できます。 letrec バインディングには値のみを含めることができ、他の式はありません。
この区別は、Cのような他の厳格な言語でも行われます。Cのような他の厳格な言語では、機能と定数のみがグローバル範囲で定義できます。
を参照してください 完全なコード 更新された評価者関数用。
