seq 在 Haskell 中实际上做了什么?

What does seq actually do in Haskell?

来自Real World Haskell我读

It operates as follows: when a seq expression is evaluated, it forces its first argument to be evaluated, then returns its second argument. It doesn't actually do anything with the first argument: seq exists solely as a way to force that value to be evaluated.

我强调 然后 因为对我来说它意味着两件事发生的顺序。

来自Hackage我读

The value of seq a b is bottom if a is bottom, and otherwise equal to b. In other words, it evaluates the first argument a to weak head normal form (WHNF). seq is usually introduced to improve performance by avoiding unneeded laziness.

A note on evaluation order: the expression seq a b does not guarantee that a will be evaluated before b. The only guarantee given by seq is that the both a and b will be evaluated before seq returns a value. In particular, this means that b may be evaluated before a. […]

此外,如果我从那里点击# Source link,该页面不存在,所以我看不到seq的代码。

这似乎与 this answer 下的评论一致:

[…] seq cannot be defined in normal Haskell

另一方面(或者实际上是同一只手),另一条评论是:

The 'real' seq is defined in GHC.Prim as seq :: a -> b -> b; seq = let x = x in x. This is only a dummy definition. Basically seq is specially syntax handled particularly by the compiler.

任何人都可以阐明这个话题吗?特别是在:

Real World Haskell 是错误的,您引用的所有其他内容都是正确的。如果您非常关心评估顺序,请改用 pseq

seq 在两个 thunk 之间引入了人为的 数据依赖性 。通常,仅当模式匹配需要它时,thunk 才被迫求值。如果 thunk a 包含表达式 case b of { … },则强制 a 也会强制 b。所以两者之间存在依赖关系:为了确定a的值,我们必须评估b.

seq 指定任意两个任意 thunk 之间的这种关系。当seq c d被强制时,除了d之外,c被强制。请注意,我没有说 before:根据标准,实现可以自由强制 c before d or dc 之前,甚至是它们的某种混合。只要求c不停机,则seq c d也不停机。如果要保证评价顺序,可以使用pseq.

下图说明了差异。黑色箭头 (▼) 表示真正的数据依赖性,您可以使用 case 表示的那种;白色箭头(▽)表示人为依赖。

  • 强制 seq a b 必须同时强制 ab.

      │
    ┌─▼───────┐
    │ seq a b │
    └─┬─────┬─┘
      │     │  
    ┌─▽─┐ ┌─▼─┐
    │ a │ │ b │
    └───┘ └───┘
    
  • 强制pseq a b必须强制b,必须先强制​​a.

      │
    ┌─▼────────┐
    │ pseq a b │
    └─┬────────┘
      │
    ┌─▼─┐
    │ b │
    └─┬─┘
      │
    ┌─▽─┐
    │ a │
    └───┘
    

就目前而言,它必须作为内在函数实现,因为它的类型 forall a b. a -> b -> b 声称它适用于 any 类型 ab,没有任何限制。它曾经属于一个类型类,但它被删除并变成了原始类型,因为类型类版本被认为具有较差的人体工程学:添加 seq 以尝试修复深度嵌套的函数调用链中的性能问题会需要在链中的每个函数上添加样板 Seq a 约束。 (我更喜欢明确的,但现在很难改变。)

所以 seq 和它的语法糖,如 data 类型中的严格字段或模式中的 BangPatterns,是关于确保通过 附加评估某些内容 它将评价其他将被评价的东西。经典的例子就是foldl'。这里,seq 确保当递归调用被强制时,累加器也被强制:

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f acc [] = acc
foldl' f acc (x : xs)
  = acc' `seq` foldl' f acc' xs
  where
    acc' = f acc x

编译器的要求如果f是严格的,例如(+)对像Int这样的严格数据类型,那么累加器在每一步都减少到 Int,而不是构建一个仅在最后才被评估的 thunk 链。

其他答案已经讨论了seq的含义及其与pseq的关系。但对于 seq 的警告的 含义 究竟是什么,似乎存在一些混淆。

从技术上讲,a `seq` b 确实 保证 a 会在 b 之前被评估。这似乎令人不安:如果是这样的话,它怎么可能达到目的呢?让我们考虑一下乔恩在他们的回答中给出的例子:

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f acc [] = acc
foldl' f acc (x : xs)
  = acc' `seq` foldl' f acc' xs
  where
    acc' = f acc x

当然,我们关心 acc' 在递归调用之前被计算。如果不是,foldl' 的全部目的就失去了!那么为什么不在这里使用 pseq 呢? seq 真的那么有用吗?

幸运的是,情况实际上并没有那么可怕。 seq确实这里的正确选择。 GHC 实际上永远不会选择编译 foldl',这样它会在计算 acc' 之前计算递归调用,所以我们想要的行为会被保留。 seqpseq 之间的区别在于优化器在认为有特别充分的理由时必须做出不同决定的灵活性。

了解 seqpseq 的严格性

要理解这意味着什么,我们必须学会像 GHC 优化器那样思考。实际上,seqpseq 之间唯一的具体区别是它们如何影响严格性分析器:

  1. seq 在其参数 both 中被认为是严格的。也就是说,在像

    这样的函数定义中
    f a b c = (a `seq` b) + c
    

    f 的所有三个参数都将被视为严格。

  2. pseq 就像 seq 一样,但它只在其 第一个 参数中被认为是严格的,而不是它的第二个参数。这意味着在像

    这样的函数定义中
    g a b c = (a `pseq` b) + c
    

    gac 中将被认为是严格的,但 不是 b.

这是什么意思?好吧,让我们首先定义函数“在其参数中严格”的含义。这个想法是,如果一个函数在它的一个参数上是严格的,那么对该函数的调用保证会评估该参数。这有几个含义:

  • 假设我们有一个参数严格的函数 foo :: Int -> Int,并且假设我们有一个对 foo 的调用,如下所示:

    foo (x + y)
    

    一个天真的 Haskell 编译器会为表达式 x + y 构造一个 thunk,并将生成的 thunk 传递给 foo。但是我们知道评估 foo 必然地 强制那个 thunk,所以我们不会从这种懒惰中获得任何好处。最好立即评估 x + y,然后将结果传递给 foo 以节省不必要的 thunk 分配。

  • 因为我们知道没有任何理由将 thunk 传递给 foo,所以我们有机会进行额外的优化。例如,优化器可以选择在内部重写 foo 以采用未装箱的 Int# 而不是 Int,不仅避免 x + y 的 thunk 构造,而且避免装箱结果价值一共。这允许 x + y 的结果直接在堆栈上传递,而不是在堆上传递。

如您所见,严格性分析对于构建高效的 Haskell 编译器至关重要,因为它允许编译器在如何编译函数调用等方面做出更明智的决策。出于这个原因,我们通常希望严格分析找到尽可能多的机会来热切地评估事物,让我们节省无用的堆分配。

考虑到这一点,让我们 return 回到上面的 fg 示例。让我们考虑一下我们 直觉上 期望这些函数具有的严格程度:

  1. 回想一下 f 的正文是 (a `seq` b) + c。即使我们完全忽略 seq 的特殊属性,我们也知道它最终会计算出它的第二个参数。这意味着 f 应该 至少 就像它的主体只是 b + c 一样严格(a 完全未使用)。

    我们知道评估b + c必须从根本上评估bc,所以f必须至少在[=21]中都严格=] 和 c。在 a 中是否严格是一个更有趣的问题。如果 seq 实际上只是 flip const,则不会,因为 a 不会被使用,当然 整点 seq是引入人为的严格,所以实际上fa中也算严格。

    令人高兴的是,我上面提到的 f 的严格性与我们对它应该具有的严格性的直觉完全一致。 f 的所有参数都是严格的,正如我们所期望的那样。

  2. 直觉上,上述针对 f 的所有推理也应该适用于 g。唯一的区别是 seq 替换为 pseq,我们知道 pseqseq 提供了 更强 的评估顺序保证] 确实如此,所以我们期望 g 至少与 f 一样严格……也就是说,在所有参数中也严格。

    然而,值得注意的是,这 不是 GHC 为 g 推断的严格性。 GHC 在 ac 中认为 g 是严格的,但在 b 中不是21=]:b 必须 计算 g 才能产生结果!正如我们将看到的,正是这种差异使 pseq 如此神奇,以及为什么它通常不是一个好主意。

严格的含义

我们现在已经看到 seq 导致了我们期望的严格性,而 pseq 则没有,但这意味着什么并不是很明显。为了说明,请考虑使用 f 的可能调用站点:

f a (b + 1) c

我们知道 f 在所有参数上都是严格的,所以根据我们上面使用的相同推理,GHC 应该立即评估 b + 1 并将其结果传递给 f,避免砰的一声。

乍一看,这似乎一切都很好,但是等等:如果 a 是一个 thunk 怎么办?尽管 fa 中也是严格的,但它只是一个裸变量——也许它是从其他地方作为参数传入的——并且 GHC 没有理由急切地在此处强制使用 a如果 f 将强制它自己。我们强制 b + 1 的唯一原因是避免创建 new thunk,但除了在调用站点强制已创建的 a 之外,我们什么也没保存。这意味着 a 实际上可能作为未计算的 thunk 传递。

这是个问题,因为在 f 的正文中,我们写了 a `seq` b,要求 a 之前被评估 b。但是根据我们上面的推理,GHC 只是先评估了 b!如果我们真的,真的需要确保 ba 之后才被评估,那么这种急切的评估是不允许的。

当然,这正是 pseq 在其第二个参数中被认为是懒惰的原因,尽管实际上并非如此。如果我们将 f 替换为 g,那么 GHC 会乖乖地为 b + 1 分配一个新的 thunk 并将其传递到堆上,确保它不会过早评估。这当然意味着更多的堆分配,没有拆箱,并且(最糟糕的是)没有严格信息在调用链上进一步传播,从而产生潜在的级联悲观。但是,嘿,这就是我们要求的:不惜一切代价避免过早评估 b

希望这能说明为什么 pseq 很诱人,但最终会适得其反,除非你 真的 知道你在做什么。当然,您可以保证您正在寻找的评估......但是要付出什么代价?

外卖

希望上面的解释清楚了seqpseq的优缺点:

  • seq 与严格性分析器配合得很好,暴露出更多潜在的优化,但这些优化可能会破坏我们预期的评估顺序。

  • pseq 不惜一切代价保留所需的评估顺序,但它只是通过完全向严格性分析器撒谎来做到这一点,这样它就不会出现这种情况,从而大大削弱了它的能力帮助优化器做好事。

我们如何知道选择哪些权衡?虽然我们现在可能理解 为什么 seq 有时无法在其第二个参数之前评估其第一个参数,但我们没有更多理由相信这是一件好事发生了。

为了消除恐惧,让我们退后一步,想想这里到底发生了什么。请注意,GHC never 实际上编译 a `seq` b 表达式本身的方式使得 ab 之前无法计算。给定一个像 a `seq` (b + c) 这样的表达式,GHC 永远不会在计算 a 之前偷偷暗中攻击你并计算 b + c。相反,它所做的事情要微妙得多:它可能 间接地 导致 bc 在评估整个 b + c 表达式之前单独评估,因为严格性分析器会注意到 bc.

中的整体表达式仍然是严格的

如何将所有这些组合在一起 令人难以置信 棘手,它可能会让您头晕目眩,所以也许您最终并没有发现上一段那么舒缓。但为了使这一点更具体,让我们 return 到此答案开头的 foldl' 示例。回想一下,它包含这样一个表达式:

acc' `seq` foldl' f acc' xs

为了避免 thunk blowup,我们需要 acc' 在对 foldl' 的递归调用之前进行计算。但鉴于上述推理,它仍然永远是! seq 相对于 pseq 的区别再次仅与严格性分析相关:它允许 GHC 推断该表达式在 fxs 中也是严格的,不只是 acc',在这种情况下实际上根本没有太大变化:

  • 整个 foldl' 函数在 f 中仍然不被认为是严格的,因为在函数的第一种情况下(xs[]), f 未使用,因此对于某些调用模式,foldl'f.

    中是惰性的
  • foldl' 可以xs中被认为是严格的,但这在这里完全没有意思,因为xs是只有 foldl' 参数的一部分,并且严格性信息根本不会影响 foldl' 的严格性。

所以,如果这里实际上没有任何区别,为什么不使用pseq呢?好吧,假设 foldl' 在调用点被内联了有限次数,因为它的第二个参数的形状可能是部分已知的。 seq 公开的严格信息可能会在调用站点公开几个额外的优化,从而导致一系列有利的优化。如果使用 pseq,这些优化将被掩盖,GHC 将产生更糟糕的代码。

因此,这里真正的要点是即使 seq 可能 有时 不会在第二个参数之前评估它的第一个参数,这仅在技术上是正确的,它发生的方式是微妙的,它不太可能破坏你的程序。这应该不足为奇:seq 是 GHC 的作者 期望 程序员在这种情况下使用的工具,因此让他们这样做是相当粗鲁的错事! seq 是这项工作的惯用工具,而不是 pseq,因此请使用 seq

那什么时候用pseq呢?只有当你真的非常关心一个非常具体的评估顺序时,这通常只发生在两个原因之一:你正在使用基于 par 的并行性,或者你正在使用 unsafePerformIO 并且关心副作用的顺序。如果你没有做这两件事,那么就不要使用 pseq如果您只关心像 foldl' 这样的用例,您只是想避免不必要的 thunk 堆积,请使用 seq 这就是它的用途。