lambda演算的call-by-value和call-by-name解释器之间的区别

Question

在另一个问题中,Bob 为无类型lambda演算提供了以下解释器.

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).如何通过名称解释器的实现与上面提到的解释器的实现不同？

Plotkin 在20世纪70年代研究了用于评估lambda演算的名称呼叫和按值调用策略.

Answer 1

我不认为原始数据定义可以使用正确的call-by-name.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,而是存储部分应用程序对象,然后在不同的调用站点单独评估它.

force并且delay需要防止GHC浮出功能体,从而恢复共享.或者,可以编译{-# OPTIONS -fno-full-laziness #-}并使用简单的lambda和应用程序代替上述机制.