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

Question

考虑函数的Haskell中的以下示例quux以及continuation 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.因此,我们首先在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!".这证明第二个参数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功能不依赖于惰性评估.

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)永远不会被调用.我希望能把事情搞清楚.