19

从我读到的真实世界的 Haskell

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

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

Hackage我读到

seq a b如果是底部,则的值为a底部,否则等于b。换句话说,它评估a弱头范式(WHNF)的第一个参数。seq通常引入它是为了通过避免不必要的惰性来提高性能。

关于评估顺序的说明:表达式seq a b不保证a将在b. 唯一的保证seq是两者都abseq返回值之前进行评估。特别是,这意味着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评估in ,例如?bbaseq a (a + x)
4

3 回答 3

26

其他答案已经讨论了 的含义及其seq与 的关系pseq。但是,对于's 警告的确切含义,似乎有些混乱。seq

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

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优化器在认为它有特别好的理由时必须做出不同决定的灵活性。

理解seqpseq严格

要理解这意味着什么,我们必须学会像 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
    

    ga在and中会被认为是严格的c,但不是 b

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

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

    foo (x + y)
    

    一个朴素的 Haskell 编译器会为表达式构造一个 thunkx + y并将生成的 thunk 传递给foo. 但是我们知道,评估必然会foo迫使这种重击,所以我们并没有从这种懒惰中获得任何好处。最好立即评估,然后将结果传递给以保存不必要的 thunk 分配。x + yfoo

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

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

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

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

    我们知道,评估b + c必须从根本上同时评估bc,因此f必须至少对b和都严格c。是否严格a是更有趣的问题。如果seqwas 实际上只是flip const,则不会, asa不会被使用,但当然整个重点seq引入人为的严格性,所以实际上f在 中也被认为是严格的a

    令人高兴的是,f我上面提到的严格性完全符合我们对它应该具有什么严格性的直觉。f正如我们所期望的那样,它的所有论点都很严格。

  2. 直觉上,以上所有的推理f都应该适用于g。唯一的区别是替换seqwith pseq,我们知道这pseq提供了比do 更强大的评估顺序保证seq,所以我们希望g至少与f... 一样严格,也就是说,在所有参数中也严格。

    然而,值得注意的是,这不是GHC 推断的严格性g。GHC 考虑g严格 inac,但不考虑b,即使根据我们上面对严格性的定义,在 :g中很明显是严格的bb 必须对其求值g才能产生结果!正如我们将要看到的,正是这种差异使人pseq如此神奇,以及为什么它通常是一个坏主意。

严格的含义

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

f a (b + 1) c

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

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

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

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

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

外卖

希望以上解释清楚地说明了两者seqpseq优缺点:

  • 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 推断此表达式在 和 中也是严格的fxs而不仅仅是acc',在这种情况下实际上并没有太大变化:

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

  • foldl' 可以认为是严格的xs,但这在这里完全没意思,因为xs这只是其中的一个foldl'论点,而且严格性信息根本不会影响 的严格性foldl'

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

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

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

于 2021-04-06T09:04:02.387 回答
11

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

seq指定任意两个任意 thunk 之间的这种关系。当seq c d被强制时,c被强制 d。请注意,我没有说之前:根据标准,实现可以c在之前d d之前自由强制,c甚至是它们的某种混合。只要求如果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声称它适用于任何类型a,并且b,没有任何约束。它曾经属于一个类型类,但由于类型类版本被认为具有较差的人体工程学设计,因此被移除并制作成一个原语:添加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 链。

于 2021-04-04T18:23:33.197 回答
0

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

于 2021-04-04T18:21:46.043 回答