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

html5 • • 问答

我从真实世界的 Haskell 中读到

它的操作如下：当一个seq表达式被求值时，它会强制求值它的第一个参数，然后返回它的第二个参数。它实际上对第一个参数没有任何作用：seq仅作为强制评估该值的一种方式存在。

我在那里强调了then因为对我来说它意味着两件事发生的顺序。

从Hackage我读到

seq a b如果a是底部，则的值是底部，否则等于b。换句话说，它将第一个参数评估a为弱头部范式（WHNF）。seq 通常用于通过避免不必要的懒惰来提高性能。

关于求值顺序的注意事项：表达式seq a b不保证a会在 之前求值b。by 给出的唯一保证seq是两者a和b将在seq返回值之前进行评估。特别是，这意味着b可以在 之前进行评估a。[…]

此外，如果我# Source从那里点击链接，页面不存在，所以我看不到seq.

这似乎与此答案下的评论一致：

[…]seq不能在普通的 Haskell 中定义

另一方面（或在同一方面，真的），另一条评论写道：

“真实”seq在 GHC.Prim 中定义为seq :: a -> b -> b; seq = let x = x in x。这只是一个虚拟的定义。基本上seq是由编译器特别处理的特殊语法。

任何人都可以对这个话题有所了解吗？尤其是在以下方面：

  • 什么来源是对的？
  • 是seq的实现确实在Haskell不写吗？
    • 如果是这样，它甚至意味着什么？说它是原始的？这告诉我什么seq实际上是什么？
  • 在seq a b被a保证将前评估b，所述壳体至少b利用的a，例如，seq a (a + x)？

回答

其他答案已经讨论了 的含义seq及其关系pseq。但是，对于's 警告的含义究竟是什么，似乎存在一些混淆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

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'，因此我们想要的行为被保留。seq和之间的区别在于pseq优化器在认为它有特别好的理由时必须做出不同决定的灵活性。

理解seq和pseq严格

要理解这意味着什么，我们必须学会像 GHC 优化器一样思考。在实践中，seq和之间的唯一具体区别pseq是它们如何影响严格分析器：

  1. seq在它的两个论点中都被认为是严格的。也就是说，在函数定义中

    f a b c = (a `seq` b) + c

    f 在其所有三个参数中都将被视为严格。

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

    g a b c = (a `pseq` b) + c

    g在aand中将被认为是严格的c，但不是 b。

这是什么意思？好吧，让我们首先定义一个函数“严格控制它的一个参数”意味着什么。这个想法是，如果一个函数的一个参数是严格的，那么对该函数的调用肯定会评估该参数。这有几个含义：

  • 假设我们有一个foo :: Int -> Int参数严格的函数，并假设我们有一个foo看起来像这样的调用：

    foo (x + y)

    一个简单的 Haskell 编译器会为表达式构造一个 thunkx + y并将生成的 thunk 传递给foo。但我们知道，评估foo将必然迫使该thunk的，所以我们不会获得从这个懒惰什么。最好x + y立即评估，然后将结果传递foo给以保存不必要的 thunk 分配。

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

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

考虑到这一点，让我们回到f和g上面的例子。让我们考虑一下我们直观地期望这些函数具有什么样的严格性：

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

    我们知道，评价b + c必须从根本上同时评估b和c，所以f必须的，起码，在两个严格b和c。是否严格a是更有趣的问题。如果seq是实际上只是flip const，它不会是，因为a不会使用，但当然的整点的seq是引入人工严格，所以实际上f也被认为是严格的a。

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

  2. 直观地说，所有上述推理f也应适用于g。唯一的区别是替换了seqwith pseq，我们知道它比dopseq提供了对评估顺序更强的保证seq，因此我们希望g至少与f…一样严格，也就是说，在所有参数中也严格。

    然而，值得注意的是，这并不是GHC 为 推断的严格性g。GHC 认为g严格 ina和c，但不是b，即使根据我们上面对g严格性的定义，在 中显然是严格的b：b 必须对其进行评估g才能产生结果！正如我们将看到的，正是这种差异使pseq如此神奇，以及为什么它通常是一个坏主意。

严格的影响

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

f a (b + 1) c

我们知道它的f所有参数都是严格的，所以根据我们上面使用的相同推理，GHC 应该b + 1急切地评估并将其结果传递给f，避免重击。

乍一看，这似乎很好，但等等：如果a是重击呢？尽管fin 也是严格的a，但它只是一个裸变量——也许它是从其他地方作为参数传入的——a如果GHCf要强制它自己，则没有理由急切地强制在这里。我们强制的唯一原因b + 1是避免创建一个新的thunk，但我们除了a在调用站点强制已经创建的东西之外什么都不保存。这意味着a实际上可能会作为未评估的 thunk 传递。

这是一个问题，因为在 的正文中f，我们写了a `seq` b，要求a在之前 进行评估b。但是根据我们上面的推理，GHC 只是先行评估b！如果我们真的，真的需要确保在bis 之后才进行评估，a则不允许这种类型的急切评估。

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

希望这说明了为什么pseq诱人，但最终会适得其反，除非您真的知道自己在做什么。当然，你保证你正在寻找的评估......但代价是什么？

外卖

希望上面的解释已经明确如何既seq与pseq各有利弊：

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

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

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

为了缓解您的恐惧，让我们退后一步，想想这里到底发生了什么。请注意，GHC从未以之前无法评估a `seq` b的方式实际编译表达式本身。给定一个像 的表达式，GHC 永远不会偷偷在你背后捅你一刀，并在评估之前评估。相反，它所做的要微妙得多：它可能会在评估整体表达式之前间接导致和单独评估，因为严格性分析器会注意到整体表达式在和 中仍然是严格的。aba `seq` (b + c)b + cabcb + cbc

如何将所有这些组合在一起是非常棘手的，它可能会让您头晕目眩，所以也许您根本没有发现上一段如此舒缓。但为了更具体地说明这一点，让我们回到foldl'这个答案开头的例子。回想一下，它包含这样的表达式：

acc' `seq` foldl' f acc' xs

为了避免 thunk 爆发，我们需要 acc'在递归调用foldl'. 但鉴于上述推理，它仍然永远是！同样，seq这里相对于的差异pseq仅与严格性分析相关：它允许 GHC 推断此表达式在fand 中也是严格的xs，而不仅仅是acc'，在这种情况下实际上根本没有太大变化：

  • 整个foldl'函数仍然不被认为是严格的f，因为在函数的第一种情况（在那里xs是[]），f是未使用的，所以对于某些调用模式，foldl'是惰性的f。

  • foldl' 可以被认为是严格 in xs，但这在这里完全无趣，因为xs这只是其中一个foldl'参数的一部分，并且严格信息根本不影响 的严格foldl'。

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

因此，这里真正的要点是，即使有时seq可能不会在第二个参数之前评估它的第一个参数，但这只是技术上正确的，它发生的方式是微妙的，并且不太可能破坏您的程序。这应该不会太令人惊讶：GHC 的作者希望程序员在这种情况下使用的工具，所以让他们做错事是相当不礼貌的！是这项工作的惯用工具，而不是，所以使用.seqseqpseqseq

那你什么时候用pseq？只有当您真的非常关心非常具体的评估顺序时，这通常仅出于以下两个原因之一才会发生：您正在使用par基于并行性，或者您正在使用unsafePerformIO并关心副作用的顺序。如果你没有做这些事情中的任何一件，那么不要使用pseq. 如果您只关心像 那样的用例foldl'，您只想避免不必要的 thunk 构建，请使用seq. 这就是它的用途。

  • @Enlico You are absolutely correct that *the Haskell Report alone* does not guarantee a useful implementation of `seq`, so if you are looking for something spelled out in a standard that mandates the behavior we all rely on `seq` having, you will never find it. Sorry. But GHC is the de facto standard these days and has been for quite some time, and though it may not mention this guarantee explicitly anywhere, I can assure you, it does provide it. I am 100% certain that if `seq` stopped working for this, it would be considered a dire bug and promptly fixed.

回答

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

seq指定任意两个任意 thunk 之间的这种关系。当seq c d被强制时，除了c被强制。请注意，我之前没有说：根据标准，实现可以在之前或之前或什至它们的某些混合之前自由强制执行。只要求不停机，则也不停机。如果要保证评估顺序，可以使用. dcd dccseq c dpseq

下图说明了差异。黑色箭头 (?) 表示真正的数据依赖性，您可以使用case; 白色箭头 (?) 表示人工依赖。

  • 强制seq a b必须同时强制a和b。

      ?
???????????
? seq a b ?
???????????
  ?     ?  
????? ?????
? a ? ? b ?
????? ?????

  • 逼迫pseq a b必须逼迫b，这必须先用力a。

      ?
????????????
? pseq a b ?
????????????
  ?
?????
? b ?
?????
  ?
?????
? a ?
?????

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

因此seq，就像data类型或BangPatterns模式中的严格字段一样，它的语法糖是通过将某些内容附加到将要评估的其他内容的评估来确保对其进行评估。经典的例子是foldl'。在这里，seq确保当递归调用被强制时，累加器也被强制：

该请求的编译器，如果f是严格，如(+)像一个严格的数据类型Int，则累加器被还原成Int在每个步骤，而不是建立的thunk的链将被仅在端部进行评价。

  • The last example is precisely what confuses me about the whole `seq` vs `pseq`. Since `seq` does not guarantee the evaluation order, it seems that there is no guarantee that `acc'` is forced _before_ the recursive call, only that it is at some point. Hence, it might indeed happen that the chain of thunks is built anyway before each `acc'` is forced. GHC does evaluate `acc'` early (AFAIK), but it looks like one should use `pseq` here (?). I'd like to be proved wrong on this, though. If I am correct, though, I can't see how `seq` can be used to ensure performance.
  • @WillNess, I don't know full details, but I imagine that kind of extreme order control will interfere with demand analysis and the worker-wrapper transformation, which are really important for optimization. In code that will be compiled with optimization, it might be better to think of `seq` as *allowing* the compiler to evaluate something earlier (which it is probably very eager to do) rather than *forcing* it to do so.
  • @WillNess You might find the discussion on https://stackoverflow.com/questions/48410245/always-guaranteed-evaluation-order-of-seq-with-strange-behavior-of-pseq-in elucidating.
以上是seq在Haskell中实际上做了什么？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>