与代数数据类型相比，更喜欢CPS的要求是什么

Question

我对代数数据类型几乎没有经验，因为我使用的语言没有本机支持。通常可以使用延续传递样式来获得远程类似的体验，但对CPS编码类型的处理不太舒服。

考虑到这一点，为什么像Parsec这样的库会使用CPS？

newtype ParsecT s u m a
= ParsecT {unParser :: forall b .
State s u
-> (a -> State s u -> ParseError -> m b) -- consumed ok
-> (ParseError -> m b)                   -- consumed err
-> (a -> State s u -> ParseError -> m b) -- empty ok
-> (ParseError -> m b)                   -- empty err
-> m b
}

一条线索是try解析器，它通过在两种情况下传递空错误延续来排除消耗错误

try :: ParsecT s u m a -> ParsecT s u m a
try p =
ParsecT $ s cok _ eok eerr ->
unParser p s cok eerr eok eerr
--                   ^^^^     ^^^^

这是可能的，因为cerr和eerr都有相同的类型，只是位置不同，这让我想起了结构类型。虽然我认为你不能用ADT做到这一点，但可能有一种方法可以用它们实现同样的行为。除此之外，单一的组合子并不能证明依赖CPS的深远决定是合理的。那么，为什么要做出这个决定呢？

Answer 1

此更改于2009年3月2日由Antoine Latter在commit a98a3ccb中进行。提交评论只是：

commit a98a3ccbca9835fe749b8cd2d475a0494a84a460
Author: Antoine Latter <[e-mail]>
Date:   Mon Mar 2 00:20:00 2009 +0000
move core data type over to CPS

它取代了ParsecT:的原始ADT

data ParsecT s u m a
= ParsecT { runParsecT :: State s u -> m (Consumed (m (Reply s u a))) }

对于您问题中的新版本，添加一个runParsecT适配器以将所有内容转换回

runParsecT :: Monad m => ParsecT s u m a -> State s u -> m (Consumed (m (Reply s u a)))
runParsecT p s = unParser p s cok cerr eok eerr
where cok a s' err = return . Consumed . return $ Ok a s' err
cerr err = return . Consumed . return $ Error err
eok a s' err = return . Empty . return $ Ok a s' err
eerr err = return . Empty . return $ Error err

我看到他在2009年2月发了一篇博客文章，写了一篇关于最终理解CPS风格的文章，并写了一个CPS版本的MaybeT。他没有谈到任何性能优势，只是指出CPS样式的优势在于，MaybeT的Monad和MonadPlus实例可以在不调用底层monad上的>>=或return或对Maybe值进行显式事例分析的情况下编写。

在2009年12月下旬的一篇博客文章中，他写到了自己的"；痴迷于功能化monad变压器"；，给出了ErrorT的一个例子，并明确指出：

我还没有衡量这是否更快，但我觉得整个过程很有趣。

然而，他在同一篇博客文章中继续讨论了如何向Parsec 3添加功能，使其成为一个monad转换器，而不是一个普通的旧monad，并根据输入类型对其进行参数化，从而导致性能变差(在一些基准测试中大约慢1.8倍)。他发现转换为CPS风格使Parsec 3和Parsec 2一样快，至少在没有使用这些新抽象(transformer)的时候是这样。

推测时间，我认为Antoine认为CPS是"；"酷"；并且具有吸引他的风格优势，所以在开发Parsec 3时，他将其放在了首位。当Parsec 3中的新抽象导致性能问题时，他偶然发现将其转换为CPS似乎可以解决这些问题，尽管他没有详细研究原因(只是博客文章中的一些猜测)。然而，我有点不清楚他是否真的在发现性能优势之前先转换为CPS，或者尝试CPS时期望它可能有助于性能。这篇博客文章读起来像是为了解决性能问题而故意进行的转换，但这可能只是为了在博客文章中进行更简单的阐述。

Answer 2

一个大问题是ParsecT是一个monad转换器，使用ADTs定义的monad转换器比使用CPS的monad变压器更能阻止优化。

表达式CCD_ 14给出了一个最小的说明性示例。

1. 将ExceptT e m a定义为m (Either e a)时，该表达式不会很好地简化，因为它涉及到抽象的底层单体m的(>>=)。

2. 在ExceptT e m a定义为forall r. (Either e a -> m r) -> m r的情况下，pure x >>= k基本上β减少为k x，而没有对m进行任何假设。

您需要专门化m来优化m (Either e a)类型的项，而基于连续性的变体在没有专门化的情况下可以走很长的路。

然而，CPS在Haskell中也不是理想的表示，因为continuation是在堆上分配的函数。功能很便宜，但不是零成本。

归根结底，monad transformers中m的抽象性确实阻碍了优化，必须进行专门化，即打破模块化。因此，一种更有前景的方法是使用一些特殊的原语monad(IO)，并得到运行时系统的专门支持，作为效果系统的基础。

---

另见Alexis King的《少的谈话效果》和相关的图书馆eff。