haskell - 在 Haskell 中实现按值调用 lambda 演算

Question

在 Haskell 中实现按值调用 lambda 演算时，我是否应该强制对对象语言中函数的参数求值(即按值调用 lambda 演算)来绕过调用 -元语言(即 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

在有评论的那一行，我是否应该使用 fun $! eval opd 代替？

我知道对象和元级别之间的评估顺序依赖可以通过 CPS 转换来避免。但我暂时不想打扰它。我就要确保在 Haskell 中忠实地实现按值调用。我提出这个问题是因为我看到的许多示例实现似乎都没有考虑到这一点。我是说这些实现不会强制执行 eval opd。不知是他们疏忽了，还是我想多了。谢谢。

Answer 1

在这里使用 $! 确实有效，只要在元语言中将 eval e 评估为弱头部范式对应于评估 e 到对象语言中的值。

让我通过向 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)

现在我们可以看看这是否是按值调用。下面的代码应该发散，因为我们将 bottom 传递给一个函数。唉，它没有:

*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) 在调用 fun 之前在 eval 中。