haskell - lambda 演算的按值调用和按名称调用解释器之间的区别

Question

在另一个问题中，Bob 提出了以下 interpreter for the untyped lambda calculus .

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 remarked由于 F f -> f (interpret env e2)，这个解释器是按值调用的. 按名称调用解释器的实现与上面介绍的有什么不同？

普洛特金学习了 call-by-name and call-by-value strategies用于评估 1970 年代的 lambda 演算。

Answer 1

我认为原始数据定义不可能实现正确的按名称调用。 F (Value a -> Value a)有 Value a作为参数，所以我们别无选择，只能传入一些已经解释过的值，它会在 Haskell 缩减行为下按需调用。

我们可以修改数据定义:

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

并且还让解释器返回显式 thunk:

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 #-}

现在，我们不再在环境中存储一个 thunk，而是存储一个 partial application object ，然后在不同的调用站点分别对其进行评估。
force和 delay需要防止 GHC 浮出函数体， thereby recovering sharing.或者，可以使用 {-# OPTIONS -fno-full-laziness #-} 进行编译并使用简单的 lambda 表达式和应用程序代替上述机制。