haskell - callCC是如何用严格的函数式语言实现的？

Question

考虑下面的 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 block 可以被认为是

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如何用严格(非惰性)函数式语言来完成？

Answer 1

没有。 callcc的这个实现不依赖于惰性评估。为了证明这一点，我将用严格的函数式语言来实现它，并表明 k n 之后的任何内容。根本没有执行。

我将使用的严格函数式语言是 JavaScript。由于 JavaScript 不是静态类型，因此您无需声明 newtype 。因此，我们首先定义 return和>>= Cont的功能JavaScript 中的 monad。我们将这些函数称为 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!" 。这证明了 bind 的第二个参数从未被处决。请参阅demo为你自己。

为什么会发生这种情况？让我们从 quux(alert) 开始倒退。通过减少贝塔值，它相当于:

(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);

下一步是减少 bind 的 beta 值我们得到:

(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函数不依赖于惰性求值。

callcc 创建的函数在 k 之后终止被调用不是因为惰性求值，而是因为调用 k通过不调用它的第一个参数来打破链，因此立即返回。

这让我回到你的问题:

And we can see from the definition of k which is \a -> cont $ \_ -> h a that in the above we have \x -> runCont ((\_ -> return 25) x) c being passed into the argument that is ignored with underscore. Ultimately the return 25 is effectively "ignored" because the underscore argument is never used so from lazy evaluation its never evaluated.

你错了。如您所见k是 (\a -> cont $ \_ -> h a)和函数 (\x -> runCont ((\_ -> return 25) x) c)被传递到 k 忽略的参数中。在那之前你是对的。但这并不意味着return 25由于惰性求值而未求值。它根本没有被评估，因为函数 (\x -> runCont ((\_ -> return 25) x) c)从未被调用过。我希望事情能够澄清。