2

在 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

在与评论一致的情况下，我是否应该改为eval opd使用强制评估fun $! eval opd？

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

4

1 回答 1

6

$!只要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)

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

*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)在eval调用fun.

于 2013-01-22T12:46:06.407 回答