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
--                   ^^^^     ^^^^

这是可能的，因为两个 continuation cerr 和 eerr 有相同的类型，仅在位置上略有不同，这让我想起结构类型。虽然我认为你不能在 ADT 中做到这一点，但可能有一种方法可以使用它们来实现相同的行为。除此之外，单个组合子并不能证明依赖于 CPS 的决定具有深远的正当性。那么为什么要做出这个决定呢？

- user5536315

---

我认为这里有性能优势 - 较少的中间结构。就表现力而言，我认为它们是“相等的”。 - Georgi Lyubenov

我认为这是一个早期的设计决策，最初是因为性能原因而做出的，但在现代 GHC中，非 CPS（Continuation Passing Style）解析器比 CPS解析器快得多。不过，对于可恢复的解析器，CPS提供了一种简单的实现方法。 - András Kovács

@AndrásKovács 你有没有一些关于这两者的基准比较的链接？我对阅读更多感兴趣。 - Georgi Lyubenov

@AndrásKovács，我的记忆是非常现代的serialise包使用CPS，但采取其他措施以避免过度依赖优化器（也许避免专业化？）。然而，解析与反序列化并不相同。 - dfeuer

很遗憾，我没有 CPS 和非 CPS 解析器在功能和语义上完全相同的比较。不过我注意到，最快的库都不是 CPS。CPS 也会阻止例如未打包的总和，这在旧时代不存在，但现在却是一个重大提升。 - András Kovács

对于序列化，非 CPS persist 是几个非 CPS 最快的选择之一。对于解析，bytesmith 和未发布的 parsnip 和 flatparse 库是我所知道的最快的。它们都使用未打包的总和和没有 CPS。它们相当边缘，但我对评估感到自信。 - András Kovács

Answer 1

这个更改是由Antoine Latter在2009年3月2日通过提交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风格，并介绍了MaybeT的CPS版本。他没有谈论任何性能优势，只是指出CPS风格的优点是可以编写MaybeT的Monad和MonadPlus实例，而不需要在底层单子上调用>>=或return，也不需要对Maybe值进行显式的案例分析。

在之后的2009年12月博客文章中，他谈到了他对函数化单子变换器的“痴迷”，并给出了ErrorT的例子，并明确指出：

我没有对是否有更快的东西进行基准测试，但我觉得整个过程非常有趣。

然而，他在同一篇博客文章中谈到了如何将Parsec 3添加功能，使其成为一个单子变换器而不是一个普通的单子，并对输入类型进行参数化会导致性能下降（在某些基准测试中慢了约1.8倍）。他发现将其转换为CPS样式可以使Parsec 3的速度与Parsec 2一样快，至少在不使用这些新抽象（变换器）时是这样的。

关于时间的推测，我认为Antoine认为CPS很“酷”，并且有吸引他的风格优势，所以当他在Parsec 3上工作时，它在他的头脑中。当Parsec 3中的新抽象导致性能问题时，他幸运地发现将其转换为CPS似乎可以解决这些问题，尽管他没有对此进行详细研究（在博客文章中只是一些猜测）。但是，我有点不清楚他是否实际上首先转换为CPS，然后才发现性能优势，还是尝试使用CPS以期望它可以提高性能。博客文章读起来像是转换是有意为之解决性能问题的，但这可能只是为了在博客文章中更简单地阐述。

- K. A. Buhr

Answer 2

一个大问题是ParsecT是一个Monad变换器，而使用ADTs定义的Monad变换器比使用CPS的Monad变换器阻塞优化更多。

表达式pure x >>= k :: ExceptT e m a给出了一个最小的说明性例子。

1. 对于ExceptT e m a被定义为m (Either e a)，这个表达式不容易简化，因为它涉及到抽象的底层Monad 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)的术语，而基于续延的变量可以在不专门化的情况下走得很远。

然而，在Haskell中，CPS也不是理想的表示形式，因为连续体是在堆上分配的函数。函数不是零成本的，但也不是昂贵的。

归根结底，在Monad变换器中m的抽象性真正妨碍了优化，为了进行优化，必须专门化即打破模块化。因此，更有前途的方法是使用一些带有专用运行时系统支持的特殊原始Monad(IO)作为效果系统的基础。

另请参阅由Alexis King主持的演讲Effects for Less，以及相关库eff。

- Li-yao Xia