7

考虑下面的 Haskell 函数示例quux以及延续 monad 和 的定义callCC。

instance Monad (Cont r) where
    return x = cont ($ x)
    s >>= f  = cont $ \c -> runCont s $ \x -> runCont (f x) c

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h

quux :: Cont r Int
quux = callCC $ \k -> do
    let n = 5
    k n
    return 25

据我了解这个例子。do 块可以被认为是

k n >>= \_ -> return 25 == 
cont $ \c -> runCont (k n) $ \x -> runCont ((\_ -> return 25) x) c

我们可以从它的定义中k看出\a -> cont $ \_ -> h a，在上面我们已经\x -> runCont ((\_ -> return 25) x) c被传入了被下划线忽略的参数。最终，它return 25被有效地“忽略”了，因为从未使用下划线参数，因此从惰性评估中它从未被评估过。

据我所知，这种实现从callCC根本上依赖于惰性求值。这callCC将如何在严格（非惰性）函数式语言中完成？

4

1 回答 1

7

不，这种实现callcc不依赖于惰性求值。为了证明这一点，我将用一种严格的函数式语言来实现它，并展示之后的任何内容k n都不会被执行。

我将使用的严格的函数式语言是 JavaScript。由于 JavaScript 不是静态类型的，因此您不需要声明newtype. 因此，我们首先在 JavaScript 中定义 monad的return和>>=函数。Cont我们将分别调用这些函数unit和bind：

function unit(a) {
    return function (k) {
        return k(a);
    };
}

function bind(m, k) {
    return function (c) {
        return m(function (a) {
            return k(a)(c);
        });
    };
}

接下来我们定义callcc如下：

function callcc(f) {
    return function (c) {
        return f(function (a) {
            return function () {
                return c(a);
            };
        })(c);
    };
}

现在我们可以定义quux如下：

var quux = callcc(function (k) {
    var n = 5;

    return bind(k(n), function () {
        alert("Hello World!");
        return unit(25);
    });
});

请注意，我alert在第二个参数中添加了一个bind来测试它是否被执行。现在，如果您调用quux(alert)它，它将显示5但不会显示"Hello World!"。这证明 to 的第二个参数bind从未被执行。亲自查看演示。

为什么会这样？让我们从quux(alert). 通过 beta 减少它相当于：

(function (k) {
    var n = 5;

    return bind(k(n), function () {
        alert("Hello World!");
        return unit(25);
    });
})(function (a) {
    return function () {
        alert(a);
    };
})(alert);

通过 beta 再次减少它，它变成：

bind(function () {
    alert(5);
}, function () {
    alert("Hello World!");
    return unit(25);
})(alert);

接下来通过 beta 减少bind我们得到：

(function (c) {
    return (function () {
        alert(5);
    })(function (a) {
        return (function () {
            alert("Hello World!");
            return unit(25);
        })(a)(c);
    });
})(alert);

现在我们可以看到为什么"Hello World!"从未显示。通过减少 beta，我们正在执行function () { alert(5); }. 这个函数的工作就是调用它的参数，但它从来没有这样做过。因为这个执行停止并且"Hello World!"永远不会显示。综上所述：

该callcc函数不依赖于惰性求值。

由callccterminate after创建的函数k被调用不是因为惰性求值，而是因为调用k通过不调用它的第一个参数来破坏链并因此立即返回。

这让我回到你的问题：

我们可以从它的定义中k看出\a -> cont $ \_ -> h a，在上面我们已经\x -> runCont ((\_ -> return 25) x) c被传入了被下划线忽略的参数。最终，它return 25被有效地“忽略”了，因为从未使用下划线参数，因此从惰性评估中它从未被评估过。

你错了。如您所见k，(\a -> cont $ \_ -> h a)函数(\x -> runCont ((\_ -> return 25) x) c)被传递到被k. 在那之前你是对的。然而，这并不意味着return 25因为惰性评估而没有评估。它根本没有被评估，因为该函数(\x -> runCont ((\_ -> return 25) x) c)从未被调用。我希望能把事情弄清楚。

于 2013-12-21T06:32:05.440 回答