在另一个问题中,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 演算。
最佳答案
我认为原始数据定义不可能实现正确的按名称调用。 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 表达式和应用程序代替上述机制。
关于haskell - lambda 演算的按值调用和按名称调用解释器之间的区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28790172/