callCC如何以严格的功能语言实现？

Question

考虑函数quux的Haskell中的以下示例以及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中定义Cont monad的return和>>=函数。我们将分别调用这些函数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); 
    }); 
}); 

注意，我在bind的第二个参数内添加一个alert来测试它是否被执行。现在，如果您拨打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!"从未显示。通过beta测试，我们正在执行function() { alert(5); }。这个函数的作用是调用它的参数，但它从来没有这样做。由于这种执行停止，并且从不显示"Hello World!"。总之：

该callcc功能不依赖于懒惰的评价。 k被称为不是因为懒惰的评价，但因为没有调用它的第一个参数，因此立即返回调用k断链后

通过callcc创建函数结束。

这让我回到你的问题：

而且我们可以从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)。我希望把事情弄清楚。