C语言中的懒惰算法

Question

据我所知，C语言在逻辑表达式中使用惰性计算，例如在表达式中：

f(x) && g(x)

g(x)只有在f(x)为真时才会被调用。

但是对于像算术表达式这样的情况呢？

f(x)*g(x)

如果f(x)为零，g(x)会被调用吗？

- user1150105

Answer 1

是的，算术运算是急切的，而不是懒惰的。

因此，在f(x)*g(x)中，f和g都会被调用（严谨地说，编译器将其转换为某些A-normal form，如果未观察到，则甚至可以避免一些调用），但不能保证在调用f之前还是之后调用g。当x为0时，评估x*1/x或y*1/x是未定义行为。

据我所知，这在Haskell中并不成立。

- Basile Starynkevitch

---

符合标准的实现可以在 x 为 0 时对 1/x 做任何它想做的事情（包括结束宇宙）。我听说在某些 PowerPC 编译器上进行一些优化时，它会在没有运行时错误的情况下给出 -1（但我不确定）。 - Basile Starynkevitch

有趣，我不知道这个..谢谢！ - Grijesh Chauhan

在 C 计算模型中，g 总是被调用。然而，在实际机器的优化代码中，如果 g 没有副作用，就不能保证 g 实际上被执行。根据 C 标准定义，程序结果是无法区分的，但观察执行时间或指令执行可能会发现理论上没有执行 g 的指令。 - Eric Postpischil

Answer 2

是的，g(x)仍然会被调用。

通常情况下，因为左侧为零就有条件地省略右侧的计算会导致速度变慢。除非右侧是一个昂贵的函数调用，否则编译器不会假设它知道这一点。

- Dolda2000

Answer 3

它被称为"短路"而不是懒惰。至少就标准而言，是的——也就是说，它没有为*指定短路求值。

如果编译器可以确定g()没有副作用，那么它可能能够进行短路求值，但只能在遵循as-if规则的情况下（即它只能通过找到没有外部可观察差异来这样做，而不是因为标准直接允许它这样做）。

- Jerry Coffin

Answer 4

在逻辑运算符&&和||的情况下，评估顺序从左到右进行，并发生短路。在&&（逻辑AND）、||（逻辑OR）的左右操作数的评估之间存在一个序列点（作为短路评估的一部分）。例如，在表达式*p++ != 0 && *q++ != 0中，所有子表达式*p++ != 0的副作用都在尝试访问q之前完成，但在算术运算符的情况下不是这样。

- haccks

---

应该补充说明逻辑运算符引入了序列点，并使用短路作为附注。 - Grijesh Chauhan

@Jerry的回答："它被称为“短路”而不是“懒惰”。" - Grijesh Chauhan

@D.Ross 请阅读Jerry的回答。 - Grijesh Chauhan

@D.Ross 呃，是有的。如果你去商店买一条面包，你愿意收到一瓶牛奶吗？ - user529758

@H2CO3：“短路”只是C标准中使用的“懒惰”一般术语的同义词。 - user1150105

Answer 5

虽然这种优化是可能的，但有一些反对意见：

• 您可能会为了优化而付出比得到的更多的代价：与逻辑运算符不同，对于算术运算符来说，优化可能只在少数情况下有益，但同时需要对每个操作进行额外的0检查。

  因为布尔真值只有两个可能的值，使用短路布尔表达式时第二个操作数不必评估的理论概率是50％（1÷2）。 （这假定均匀分布，这也许并不现实，但请见谅。）也就是说，在相当大的一部分情况下，您很可能从优化中获益。

  相比之下，整数则不同，其中0只是数百万种可能值中的一个。第一个操作数为0的概率要低得多：1 ÷ 2 ³²（对于32位整数，再次假定均匀分布）。即使0确实比这更有可能发生（即存在非均匀分布），处理与真值相同数量级的概率仍然不太可能。

  浮点数计算进一步加剧了这个问题。这里需要处理舍入误差和非规格化的可能性。某些计算产生恰好0的概率可能会比使用整数更低。

  因此，这种优化很少会导致剩余操作数不被计算。但它将每一次都增加0检查！

• 如果您希望评估规则保持相对一致，就必须重新定义&&和||的短路计算顺序：除法有一个重要的边界情况，即除以0：即使第一个操作数为0，商也不一定为0。除0应视为错误（除非在IEEE浮点数学中），因此，您始终需要评估第二个操作数，以确定计算是否有效。

  /的另一种可选优化是：除以1。在这种情况下，您根本不必进行除法，而只需返回第一个操作数。因此，/最好通过从第二个操作数（除数）开始进行优化。

  现在，除非您希望&&、||和*以第一个操作数开始评估，但/以第二个操作数开始评估（这可能看起来不直观），否则您必须通常重新定义短路行为，使得第二个操作数始终首先得到评估，这将是一种从现状的改变。

  这本身并不是问题，但如果C语言被改变，它可能会破坏很多现有代码。

• 优化可能会与C++代码"兼容性"不符，其中运算符可以重载。优化是否仍适用于重载的*和/运算符？还是必须存在两种不同的这些运算符形式，一种进行短路计算，另一种使用急切评估？

  同样，这不是短路算术运算符固有的缺陷，而是如果C（和C ++）语言引入这种短路行为作为破坏性变更，则会出

- stakx - no longer contributing

---

+1 这是一个很棒的答案，不过我对“直观性”部分有些看法：我认为除法的类比优化应该是，如果第一个操作数为零，则不计算第二个操作数。 - user529758

@H2CO3：感谢您的意见。如果没有0的除法，您绝对是正确的。请查看我的编辑回答。 - stakx - no longer contributing

布尔对象有两个值并不意味着它们是同等可能的。 - Eric Postpischil

显然，10 ** -20在乘法中不会被视为零，除非编译器能够进一步确定乘法的结果实际上是零（由于浮点下溢）或不会影响后续结果（由于加到已知值的添加，例如，足够大，以至于添加小产品不会产生变化）。这些问题和重载*运算符是不同的问题，与本问题不相关。 - Eric Postpischil

这个答案中的离题和错误陈述削弱了它的可信度。 - Eric Postpischil

@EricPostpischil：我已经重构了我的回答。这样好吗？ - stakx - no longer contributing