2

Haskellで値による呼び出しラムダ計算を実装する場合、オブジェクト言語の関数（つまり、値による呼び出しラムダ計算）の引数の評価を強制して、必要な呼び出しを回避する必要がありますメタ言語（すなわち、Haskell）の評価順序？

具体的には、高次の抽象構文を使用した次の実装の場合：

data Exp
  = Abs (Exp -> Exp)
  | App Exp Exp

eval :: Exp -> Exp
eval exp = case exp of
  Abs _       -> exp
  App opr opd -> case eval opr of
    Abs fun -> eval (fun $ eval opd)  -- argument evaluation

コメント付きの行で、代わりにeval opdを使用しての評価を強制する必要がありますか？fun $! eval opd

オブジェクトとメタレベルの間の評価順序の依存性は、CPS変換によって回避できることを私は知っています。しかし、私は今のところそれを気にしたくありません。値による呼び出しがHaskellで忠実に実装されていることを確認したいだけです。私が見た多くの実装例はこれを考慮していないように思われるので、私はこの質問を提起しました。つまり、これらの実装は強制されませんeval opd。彼らがそれを無視しているのか、それとも私が考えすぎているのかしら。ありがとう。

4

1 に答える 1

6

メタ言語での弱い頭の通常の形式への評価がオブジェクト言語での値への評価に対応する$!限り、ここでの使用は機能します。eval ee

Exp発散する計算を表すためにデータ型に新しいコンストラクターを追加し、実際に出力できる値を追加することによって、次のことを示します。

data Exp
  = Abs (Exp -> Exp)
  | App Exp Exp
  | Bot
  | Value

printExp :: Exp -> String
printExp Bot = "bottom"
printExp Value = "base value"
printExp (Abs _) = "function"
printExp (App _ _) = "thunk"

error簡単にするために、評価関数の呼び出しに変換してみましょう。

eval :: Exp -> Exp
eval exp = case exp of
  Bot         -> error "Evaluation would not terminate "
  Value       -> Value
  Abs _       -> exp
  App opr opd -> case eval opr of
    Abs fun -> eval (fun $ eval opd)

これで、これが値による呼び出しであるかどうかを確認できます。以下のコードは、関数にボトムを渡すため、分岐するはずです。残念ながら、それはしません：

*Main> let e = App (Abs (\_ -> Value)) Bot
*Main> printExp e
"thunk"
*Main> printExp (eval e)
"base value"

$に変更するのに役立ちます$!か？はい、そうです：

*Main> let e = App (Abs (const Value)) Bot
*Main> printExp (eval e)
"*** Exception: Evaluation would not terminate

しかし、それはどれほど信頼できるのでしょうか？データ型への変更はExp、ペアの導入など、最も外側のコンストラクターを強制することが必要かどうかを確認するために注意深くチェックする必要があります。

deepseq使用する方が少し信頼性が高いかもしれません$!!。しかし、私が本当に提案するのはisValue :: Exp -> Bool、引数がオブジェクト言語の基本値であるかどうかを明示的にチェックする述語を追加し、を呼び出す前にチェックisValue (eval opd)インすることです。evalfun

于 2013-01-22T12:46:06.407 に答える