2

更新:最終的な解決策を説明する回答を追加しました(ヒント: 単一の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 のコメントに基づいて、エラー モナドに MonadFix インスタンスを使用するようにコードを更新しました。前の例は問題なく動作します。ただし、次の例は正しく機能しません。

test4 :: Expr
test4 = LetRec [ ("x", Con 3)
               , ("y", Var "x")
               ]
               (Con 0)

これを評価するとき、エバリュエーターはループし、何も起こりません。ここで少し厳しすぎるものを作ったと思いますが、それが何であるかはわかりません。MonadFix 法の 1 つに違反していますか?

4

3 に答える 3

4

Haskell が適合しない場合、それは通常、問題の核となる問題について明確に考えていないことを示しています。この場合の質問は、言語にどの評価モデルを使用したいかということです。コール・バイ・バリューまたはコール・バイ・ニード?

環境の表現は、環境に保存する前にすべてがすぐに評価されるため、[(Var,Value)]値による呼び出しを使用することを示唆しています。しかし、それではうまくいきません.2番目の例が示しています!ExprValueletrec

さらに、ホスト言語 (Haskell) の評価モデルは、実装したい言語の評価モデルに干渉することに注意してください。実際、それはあなたが現在あなたの例に利用しているものです.その目的にもかかわらず、あなたValueの s は弱い頭の正規形に評価されません.

小さな式言語の評価モデルを明確に把握していない限りletrec、エラー チェック機能についてはあまり進歩しません。

編集:letrec値渡し言語での 仕様例については、 Ocaml Manualを参照してください。最も単純なレベルでは、ラムダ式である右辺、つまり構文的に値であることがわかっているもののみを許可します。

于 2010-08-20T12:01:59.547 に答える
2

何かが足りないのかもしれませんが、次のことはうまくいきませんか?

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
于 2010-08-19T19:04:33.557 に答える
1

私自身の質問に答えます。私が思いついた最終的な解決策を共有したいと思いました。

ハインリッヒが正しく指摘したように、私は評価順序が与える影響について深く考えていませんでした。

厳密な (値による呼び出し) 言語では、既に値である式 (weak head normal form) は、まだ何らかの評価が必要な式とは異なります。この区別をデータ型でエンコードすると、すべてがうまくいきました。

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)

元のデータ型との唯一の違いは、 2 つのコンストラクター (および) を独自のデータ型にExpr取り出したことです。データ型には新しいコンストラクターがあり、これは値が有効な式でもあるという事実を表しています。ConLamValExprVal

独自のデータ型の値を使用すると、他の式とは別に処理できます。たとえば、letrecバインディングには値のみを含めることができ、他の式は含めることができません。

この区別は、関数と定数のみがグローバル スコープで定義できる C などの他の厳格な言語でも行われます。

更新されたエバリュエーター関数の完全なコードを参照してください。

于 2010-12-21T21:43:13.727 に答える