haskell - 非严格和惰性有何不同？

Question

我经常读到惰性与非严格不同，但我发现很难理解其中的区别。它们似乎可以互换使用，但我知道它们有不同的含义。我希望能得到一些帮助来理解其中的差异。

我有一些关于这篇文章的问题。我将在本文末尾总结这些问题。我有一些示例片段，我没有测试它们，我只是将它们作为概念呈现。我添加了引号，以免您查找它们。也许它会对以后遇到同样问题的人有所帮助。

非严格定义:

A function f is said to be strict if, when applied to a nonterminatingexpression, it also fails to terminate. In other words, f is strictiff the value of f bot is |. For most programming languages, allfunctions are strict. But this is not so in Haskell. As a simpleexample, consider const1, the constant 1 function, defined by:

const1 x = 1

The value of const1 bot in Haskell is 1. Operationally speaking, sinceconst1 does not "need" the value of its argument, it never attempts toevaluate it, and thus never gets caught in a nonterminatingcomputation. For this reason, non-strict functions are also called"lazy functions", and are said to evaluate their arguments "lazily",or "by need".

-A Gentle Introduction To Haskell: Functions

我真的很喜欢这个定义。这似乎是我能找到的最好的理解严格的方法。 const1 x = 1 也是懒惰的吗？

Non-strictness means that reduction (the mathematical term forevaluation) proceeds from the outside in,

so if you have (a+(bc)) then first you reduce the +, then you reducethe inner (bc).

-Haskell Wiki: Lazy vs non-strict

Haskell Wiki 真的让我很困惑。我理解他们所说的关于顺序的内容，但我不明白如果通过 _|_，(a+(b*c)) 将如何非严格地评估？

In non-strict evaluation, arguments to a function are not evaluatedunless they are actually used in the evaluation of the function body.

Under Church encoding, lazy evaluation of operators maps to non-strictevaluation of functions; for this reason, non-strict evaluation isoften referred to as "lazy". Boolean expressions in many languages usea form of non-strict evaluation called short-circuit evaluation, whereevaluation returns as soon as it can be determined that an unambiguousBoolean will result — for example, in a disjunctive expression wheretrue is encountered, or in a conjunctive expression where false isencountered, and so forth. Conditional expressions also usually uselazy evaluation, where evaluation returns as soon as an unambiguousbranch will result.

-Wikipedia: Evaluation Strategy

懒惰定义:

Lazy evaluation, on the other hand, means only evaluating anexpression when its results are needed (note the shift from"reduction" to "evaluation"). So when the evaluation engine sees anexpression it builds a thunk data structure containing whatever valuesare needed to evaluate the expression, plus a pointer to theexpression itself. When the result is actually needed the evaluationengine calls the expression and then replaces the thunk with theresult for future reference....

Obviously there is a strong correspondence between a thunk and apartly-evaluated expression. Hence in most cases the terms "lazy" and"non-strict" are synonyms. But not quite.

-Haskell Wiki: Lazy vs non-strict

这似乎是 Haskell 的具体答案。我认为惰性意味着thunk，非严格意味着部分评估。这样的比较是不是太简单化了？ lazy 是否总是意味着 thunk，而 non-strict 总是意味着部分评估。

In programming language theory, lazy evaluation or call-by-need1 isan evaluation strategy which delays the evaluation of an expressionuntil its value is actually required (non-strict evaluation) and alsoavoid repeated evaluations (sharing).

-Wikipedia: Lazy Evaluation

命令式示例

我知道大多数人都会说在学习函数式语言时忘记命令式编程。但是，我想知道这些是否符合非严格、惰性、两者兼有或两者都没有的资格？至少它会提供一些熟悉的东西。

短路

f1() || f2()

C#、Python 等具有“yield”的语言

public static IEnumerable Power(int number, int exponent)
{
    int counter = 0;
    int result = 1;
    while (counter++ < exponent)
    {
        result = result * number;
        yield return result;
    }
}

-MSDN: yield (c#)

回调

int f1() { return 1;}
int f2() { return 2;}

int lazy(int (*cb1)(), int (*cb2)() , int x) {
    if (x == 0)
        return cb1();
    else
        return cb2();
}

int eager(int e1, int e2, int x) {
    if (x == 0)
         return e1;
    else
         return e2;
}

lazy(f1, f2, x);
eager(f1(), f2(), x);

问题

我知道答案就在我面前，拥有所有这些资源，但我无法捕获它。看起来这个定义太容易被认为是隐含的或明显的而被忽视。

我知道我有很多问题。请随意回答您认为相关的任何问题。我添加了这些问题以供讨论。

• const1 x = 1 也是懒惰的吗？
• 如何从“内部”进行评估是非严格的？是因为 inward 允许减少不必要的表达式，比如 const1 x = 1 吗？减少似乎符合懒惰的定义。
• 惰性是否总是意味着thunk，而非严格总是意味着部分评估？这只是一个概括吗？
• 以下命令式概念是惰性概念、非严格概念、两者兼而有之还是两者都不是？
  • 短路
  • 使用产量
  • 传递回调以延迟或避免执行
• 惰性是非严格的子集吗？反之亦然，或者它们是互斥的。例如，是否可以做到非严格而不惰性，或者惰性而不非严格？
• Haskell 的非严格性是通过懒惰实现的吗？

非常感谢!

Answer 1

非严格和惰性虽然非正式地可以互换，但适用于不同的讨论领域。

非严格指的是 semantics :表达式的数学含义。非严格适用的世界没有函数的运行时间、内存消耗甚至计算机的概念。它只是讨论域中的哪些类型的值映射到共域中的哪些类型的值。特别是，严格函数必须将值 ⊥(“bottom”——有关更多信息，请参阅上面的语义链接)映射到 ⊥；允许非严格函数不执行此操作。

惰性指的是操作行为:代码在真实计算机上执行的方式。大多数程序员从操作角度考虑程序，所以这可能就是您的想法。惰性求值是指使用 thunk 的实现——指向代码的指针，这些代码在第一次执行时被值替换。注意这里的非语义词:“指针”、“第一次”、“执行”。

惰性求值会产生不严格的语义，这就是为什么这些概念看起来如此接近的原因。但正如 FUZxxl 指出的那样，惰性并不是实现非严格语义的唯一方法。

如果您有兴趣了解有关此区别的更多信息，我强烈推荐上面的链接。阅读这本书是我对计算机程序含义概念的转折点。