哈斯克尔：非严格和懒惰有什么不同？ [英] Haskell: How does non-strict and lazy differ?

问题描述

我经常读到懒惰与非严格不一样，但我发现很难理解这种差异。他们似乎可以互换使用，但我知道他们有不同的含义。我会很感激一些帮助理解差异。

我有几个关于这篇文章的问题。我将在这篇文章结尾总结这些问题。我有几个示例片段，我没有测试它们，我只是将它们作为概念呈现。我已经添加了引号以避免您查找它们。也许它会帮助稍后出现同样问题的人。

非严格防卫：

函数f被认为是严格的，如果应用于非终结
表达式时，它也无法终止。换句话说，如果f bot的值是 | ，那么f是严格的
。对于大多数编程语言而言，所有
函数都是严格的。但在Haskell中并非如此。作为一个简单的
示例，考虑const1，常量1函数，定义如下：

const1 x = 1

Haskell中的const1 bot的值为1.从操作上来说，由于
const1不需要它的参数值，所以它永远不会试图对
进行评估，因此永远不会被捕获在无限制的
计算中。由于这个原因，非严格函数也被称为
懒惰函数，并据说评价他们的论点懒惰，
或需要。

- Haskell简介：函数

我非常喜欢这个定义。这似乎是我能找到的理解严格的最好的一个。是 const1 x = 1 懒惰吗？

非严格意味着减少（b $ b评估的数学术语）从外部开始，

所以如果你有（a +（b c）），那么你首先要减少那么你减少
的内部（b c）。

- Haskell Wiki：Lavy vs非严格的

Haskell Wiki真的让我困惑。我了解他们对订单的看法，但我不明白（a +（b * c））如果是通过在非严格评估中，对函数的参数不进行评估


$ b



在Church编码下，运算符的懒惰评估映射到函数的非严格
评估;为此，非严格的评估是
通常被称为懒惰。许多语言中的布尔表达式使用
a形式的非严格评估，称为短路评估，其中
评估只要能确定明确的
布尔值将会返回就会返回 - 例如，在遇到
true的析取表达式中，或在遇到
为false的连接表达式中，等等。条件表达式通常也使用
懒惰评估，只要明确的
分支结果就会返回评估。

- 维基百科：评估策略

$ b $另一方面，懒惰评价意味着只评价
表达式，其结果是（注意从
减少转换为评估）。因此，当评估引擎看到
表达式时，它会构建一个thunk数据结构，其中包含需要
来评估表达式的任何值，以及一个指向
表达式本身的指针。当实际需要结果时，评估
引擎将调用表达式，然后用
结果替换thunk以备将来参考。
...

显然在thunk和
部分计算的表达式之间有很强的对应关系。因此，在大多数情况下，术语懒惰和
非严格是同义词。但不完全。

- Haskell Wiki：Lavy vs非严格的

这看起来像是一个Haskell的特定答案。我认为懒惰表示thunk，非严格表示部分评估。这个比较是否简化了？ 懒惰总是表示thunk，非严格总是意味着部分评估。 b

在编程语言理论中，懒惰评估或按需呼叫 1 是
一种评估策略，推迟评估表达
直到其实际需要的价值（非严格评估）以及
避免重复评估（共享）。

- 维基百科：懒惰评估

命令式示例

我知道大多数人在学习函数式语言时忘记了命令式编程。但是，我想知道这些是非严格的，懒惰的，还是两者都不符合？至少它会提供一些熟悉的东西。

短路

  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; 
收益回报结果; 
} 
} 
  

- MSDN：yield（c＃）

回调

  int f1（）{return 1;} 
 int f2（）{return 2;} 
 $ b $ 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 
返回e2; 
} 
 
 lazy（f1，f2，x）; 
 eager（f1（），f2（），x）; 
  

问题

我知道答案是在我面前拥有所有这些资源，但我无法掌握它。看起来这个定义太容易被忽视或明显地被驳回。

我知道我有很多问题。随时回答您认为相关的任何问题。



• const1 x = 1 也懒吗？


• 如何从内向非严格评估？是否因为内向可以减少不必要的表达式，如 const1 x = 1 ？缩减似乎符合懒惰的定义。 懒惰总是指 thunks 和非严格总是表示部分评估？这只是一个泛化？


• 下面的命令式概念是懒惰的，非严格的，两者还是都不是？
  
  
  
  
  • 短路
  
  
  • 使用收益
  
  
  • 传递回调延迟或避免执行
  
  


• 是懒惰 非严格的子集，反之亦然，或者它们是相互排斥的。例如，如果不是非严格，可以非严格而不是懒惰或懒惰？


• Haskell的非严格性是否由懒惰来实现？

谢谢！ >

解决方案

非严格和懒惰，虽然非正式可互换，适用于讨论的不同领域。 非严格指 语义 ：表达式的数学含义。非严格适用的世界没有关于功能运行时间，内存消耗甚至计算机的概念。它只是谈论域中的哪些值映射到共域中的哪些类型的值。特别是，一个 strict 函数必须映射值⊥ （底部 - 请参阅上面的语义链接以获取更多关于此内容的信息）to&perp ;;一个非严格的函数是不允许的。

懒惰是指操作行为：代码在真实计算机上执行的方式。大多数程序员在操作上会考虑程序，所以这可能就是你的想法。懒惰评估是指使用thunks的实现 - 指向代码的指针，这些指针在第一次执行时被替换为值。注意这里的非语义词：指针，第一次，执行。

懒惰的评估会产生非严格的语义，这就是为什么概念看起来非常接近。但正如FUZxxl指出的那样，懒惰并不是实现非严格语义的唯一方法。

如果您有兴趣了解更多关于这个区别的信息，我强烈建议链接以上。阅读它是我对计算机程序意义概念的一个转折点。

I often read that lazy is not the same as non-strict but I find it hard to understand the difference. They seem to be used interchangeably but I understand that they have different meanings. I would appreciate some help understanding the difference.

I have a few questions which are scattered about this post. I will summarize those questions at the end of this post. I have a few example snippets, I did not test them, I only presented them as concepts. I have added quotes to save you from looking them up. Maybe it will help someone later on with the same question.

Non-Strict Def:

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

const1 x = 1

The value of const1 bot in Haskell is 1. Operationally speaking, since const1 does not "need" the value of its argument, it never attempts to evaluate it, and thus never gets caught in a nonterminating computation. 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

I really like this definition. It seems the best one I could find for understanding strict. Is const1 x = 1 lazy as well?

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

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

-Haskell Wiki: Lavy vs non-strict

The Haskell Wiki really confuses me. I understand what they are saying about order but I fail to see how (a+(b*c)) would evaluate non-strictly if it was pass _|_?

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

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

-Wikipedia: Evaluation Strategy

Lazy Def:

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

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

-Haskell Wiki: Lavy vs non-strict

This seems like a Haskell specific answer. I take that lazy means thunks and non-strict means partial evaluation. Is that comparison too simplified? Does lazy always mean thunks and non-strict always mean partial evaluation.

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

-Wikipedia: Lazy Evaluation

Imperative Examples

I know most people say forget imperative programming when learning a functional language. However, I would like to know if these qualify as non-strict, lazy, both or neither? At the very least it would provide something familiar.

Short Circuiting

f1() || f2()

C#, Python and other languages with "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#)

Callbacks

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);

Questions

I know the answer is right in front of me with all those resources, but I can't grasp it. It all seems like the definition is too easily dismissed as implied or obvious.

I know I have a lot of questions. Feel free to answer whatever questions you feel are relevant. I added those questions for discussion.

• Is const1 x = 1 also lazy?
• How is evaluating from "inward" non-strict? Is it because inward allows reductions of unnecessary expressions, like in const1 x = 1? Reductions seem to fit the definition of lazy.
• Does lazy always mean thunks and non-strict always mean partial evaluation? Is this just a generalization?
• Are the following imperative concepts Lazy, Non-Strict, Both or Neither?
  • Short Circuiting
  • Using yield
  • Passing Callbacks to delay or avoid execution
• Is lazy a subset of non-strict or vice versa, or are they mutually exclusive. For example is it possible to be non-strict without being lazy, or lazy without being non-strict?
• Is Haskell's non-strictness achieved by laziness?

Thank you SO!

解决方案

Non-strict and lazy, while informally interchangeable, apply to different domains of discussion.

Non-strict refers to semantics: the mathematical meaning of an expression. The world to which non-strict applies has no concept of the running time of a function, memory consumption, or even a computer. It simply talks about what kinds of values in the domain map to which kinds of values in the codomain. In particular, a strict function must map the value ⊥ ("bottom" -- see the semantics link above for more about this) to ⊥; a non strict function is allowed not to do this.

Lazy refers to operational behavior: the way code is executed on a real computer. Most programmers think of programs operationally, so this is probably what you are thinking. Lazy evaluation refers to implementation using thunks -- pointers to code which are replaced with a value the first time they are executed. Notice the non-semantic words here: "pointer", "first time", "executed".

Lazy evaluation gives rise to non-strict semantics, which is why the concepts seem so close together. But as FUZxxl points out, laziness is not the only way to implement non-strict semantics.

If you are interested in learning more about this distinction, I highly recommend the link above. Reading it was a turning point in my conception of the meaning of computer programs.

这篇关于哈斯克尔：非严格和懒惰有什么不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！