4

別の質問で、Bobは型指定されていないラムダ計算の次のインタープリターを提示しました。

data Expr = Var String | Lam String Expr | App Expr Expr

data Value a = V a | F (Value a -> Value a)

interpret :: [(String, Value a)] -> Expr -> Value a
interpret env (Var x) = case lookup x env of
  Nothing -> error "undefined variable"
  Just v -> v
interpret env (Lam x e) = F (\v -> interpret ((x, v):env) e)
interpret env (App e1 e2) = case interpret env e1 of
  V _ -> error "not a function"
  F f -> f (interpret env e2)

Ivan Zakharyaschev は、このインタプリタは値による呼び出しであると述べましたF f -> f (interpret env e2)。call-by-name インタープリターの実装は、上記のものとどのように異なるでしょうか?

Plotkinは、1970 年代にラムダ計算を評価するための名前による呼び出しと値による呼び出しの戦略を研究しました。

4

2 に答える 2

5

元のデータ定義では適切な名前による呼び出しは不可能だと思います。F (Value a -> Value a)はValue a引数として持っているため、すでに解釈された値を渡すしかありません。Haskell の削減動作では、必要に応じて呼び出します。

データ定義を変更できます。

data Value a = V a | F ((() -> Value a) -> Value a)

また、インタプリタが明示的なサンクを返すようにします。

interpret :: [(String, () -> Value a)] -> Expr -> () -> Value a
interpret env (Var x) = delay (case lookup x env of
  Nothing -> error "undefined variable"
  Just v -> force v)
interpret env (Lam x e) = delay (F (\v -> force (interpret ((x, v):env) e)))
interpret env (App e1 e2) = delay (case force (interpret env e1) of
  V _ -> error "not a function"
  F f -> f (interpret env e2))

force :: (() -> a) -> a
force f = f ()
{-# NOINLINE force #-}

delay :: a -> () -> a
delay a () = a
{-# NOINLINE delay #-}

ここで、サンクを環境に格納する代わりに、部分的なアプリケーション オブジェクトを格納し、異なる呼び出しサイトで個別に評価します。

forcedelayGHC が関数本体を浮かび上がらせないようにするために必要であり、それによって共有を回復します。{-# OPTIONS -fno-full-laziness #-}あるいは、上記の機構の代わりに単純なラムダとアプリケーションを使用してコンパイルして使用することもできます。

于 2015-03-01T08:07:32.337 に答える
3

CBV/CBN は、ラムダ計算の評価戦略に関連する概念です。つまり、ラムダ項簡約における redex の選択に関連します。用語表現を削減する運用スタイルのインタープリターでは、CBV/CBN について適切に話すことができます。

投稿されたような表示スタイルのインタープリターでは、CBV/CBN ではなく、熱心なセマンティクスと怠惰なセマンティクスについて話します。もちろんeagerはCBV、lazyはCBNに対応。

Haskell は遅延なので、コードは

interpret env (App e1 e2) = case interpret env e1 of
  V _ -> error "not a function"
  F f -> f (interpret env e2)

レイジー セマンティクス (CBN) を実装します。(luqui が述べているように、運用上、GHC は必要に応じた方法でこれを削減します)。

熱心な (CBV) セマンティクスを取得するには、呼び出しの前に引数を強制できます。

interpret env (App e1 e2) = case interpret env e1 of
  V _ -> error "not a function"
  F f -> case interpret env e2 of
         V v -> f v
         F g -> f g

これにより、未評価のサンクが既に環境内にない限り、関数に供給されないことが保証されます。vただし、環境は、上記の値を環境に挿入するラムダを評価する場合にのみ設定gされます。したがって、サンクはそこに挿入されません。

于 2015-03-01T08:44:18.540 に答える