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

Question

考虑函数quux的Haskell中的以下示例，以及连续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？

Answer 1

不是的。callcc的这种实现不依赖于懒惰的评估。为了证明这一点，我将用一种严格的函数式语言来实现它，并说明在k n之后的任何事情都没有被执行。

我将要使用的严格的函数式语言是JavaScript。由于JavaScript不是静态类型的，所以不需要声明newtype。因此，我们首先在return中定义Cont monad的Cont和JavaScript函数。我们将分别将这些函数称为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);

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

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

接下来，通过bind的β缩减，我们得到：

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

现在我们可以看到为什么"Hello World!"从未被显示过。通过β缩减，我们正在执行function () { alert(5); }。这个函数的工作是调用它的参数，但它从来没有。由于这个原因，执行停止，"Hello World!"永远不会显示。最后：

callcc 函数不依赖于懒惰的计算。

callcc创建的函数在调用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)从未被调用过。我希望这能把事情弄清楚。