Haskell : non-strict와 lazy는 어떻게 다른가요?

Haskell : non-strict와 lazy는 어떻게 다른가요?

---

나는 lazy 가 non-strict 와 같지 않다는 것을 자주 읽었 지만 차이점을 이해하기 어렵다는 것을 알게되었습니다. 그들은 보인다 상호 교환 사용하지만 서로 다른 의미를 가지고 있음을 이해합니다. 차이점을 이해하는 데 도움을 주시면 감사하겠습니다.

이 게시물에 대해 흩어져있는 몇 가지 질문이 있습니다. 이 글의 끝에 이러한 질문을 요약하겠습니다. 몇 가지 예제 스 니펫이 있지만 테스트하지 않고 개념으로 만 제시했습니다. 나는 당신이 그들을 찾는 것을 구하기 위해 따옴표를 추가했습니다. 나중에 같은 질문으로 누군가에게 도움이 될 수도 있습니다.

비 엄격 Def :

함수 f는 종료되지 않는 표현식에 적용될 때도 종료되지 않으면 엄격하다고합니다. 즉, f bot의 값이 | . 대부분의 프로그래밍 언어에서 모든 기능은 엄격합니다. 그러나 이것은 Haskell에서는 그렇지 않습니다. 간단한 예로서 다음과 같이 정의 된 상수 1 함수 인 const1을 고려하십시오.

const1 x = 1

Haskell에서 const1 봇의 값은 1입니다. 조작 적으로 말하면 const1은 인수 값을 "필요"하지 않기 때문에 평가를 시도하지 않으므로 종료되지 않는 계산에 걸리지 않습니다. 이러한 이유로 엄격하지 않은 함수는 "지연 함수"라고도하며 인수를 "게으르게"또는 "필요에 따라"평가한다고합니다.

- 젠틀 소개 하스켈 : 함수

이 정의가 정말 마음에 듭니다. 엄격한 이해를 위해 찾을 수있는 가장 좋은 것 같습니다. const1 x = 1게으른 가요 ?

비 엄격 성은 감소 (평가를위한 수학적 용어)가 외부에서 진행되는 것을 의미합니다.

따라서 (a + (b c))가 있으면 먼저 +를 줄인 다음 내부 (b c)를 줄입니다.

- 하스켈 위키 : 비 엄격한 대 Lavy

Haskell Wiki는 정말 저를 혼란스럽게합니다. 나는 그들이 주문에 대해 말하는 것을 이해하지만 (a+(b*c))그것이 통과 되었다면 어떻게 비 엄격하게 평가할 것인지 보지 못 _|_합니까?

비 엄격 평가에서 함수에 대한 인수는 실제로 함수 본문의 평가에 사용되지 않는 한 평가되지 않습니다.

교회 인코딩에서 운영자의 지연 평가는 기능에 대한 엄격하지 않은 평가에 매핑됩니다. 이러한 이유로 엄격하지 않은 평가를 종종 "지연"이라고합니다. 많은 언어의 부울 식은 단락 평가라고하는 비 엄격 평가 형식을 사용합니다. 여기서 평가는 모호하지 않은 부울이 결과가 될 것이라는 것이 결정되는 즉시 반환됩니다. 거짓이 만나는 결합 표현 등. 조건식은 일반적으로 지연 평가를 사용합니다. 여기서 평가는 모호하지 않은 분기가 발생하는 즉시 반환됩니다.

- 위키 백과 : 평가 전략

레이지 데프 :

반면 지연 평가는 결과가 필요할 때만 표현식을 평가하는 것을 의미합니다 ( "축소"에서 "평가"로의 이동에 유의하십시오). 따라서 평가 엔진이 표현식을 볼 때 표현식을 평가하는 데 필요한 값과 표현식 자체에 대한 포인터를 포함하는 썽크 데이터 구조를 작성합니다. 결과가 실제로 필요한 경우 평가 엔진은 식을 호출 한 다음 나중에 참조 할 수 있도록 썽크를 결과로 바꿉니다. ...

분명히 썽크와 부분적으로 평가 된 표현 사이에는 강한 일치가 있습니다. 따라서 대부분의 경우 "lazy"및 "non-strict"라는 용어는 동의어입니다. 하지만 정답은 아닙니다.

- 하스켈 위키 : 비 엄격한 대 Lavy

이것은 Haskell 특정 답변처럼 보입니다. 그 걸릴 게으른 수단의 썽크 및 비 엄격한 수단 부분 평가. 비교가 너무 간단합니까? lazy는 항상 썽크를 의미하고 엄격하지 않은 것은 항상 부분 평가를 의미 합니까?

프로그래밍 언어 이론에서 lazy evaluation 또는 call-by-need 1 은 값이 실제로 필요할 때까지 (비 엄격 평가) 표현식 평가를 지연시키고 반복 평가 (공유)를 피하는 평가 전략입니다.

- 위키 백과 : 게으른 평가

명령형 예

나는 대부분의 사람들이 기능적 언어를 배울 때 명령형 프로그래밍을 잊는다 고 말하는 것을 알고 있습니다. 그러나 이것이 엄격하지 않은지, 게으른 지, 둘 다인지 또는 둘 다인지 알고 싶습니다. 최소한 익숙한 것을 제공 할 것입니다.

단락

f1() || f2()

"yield"가있는 C #, Python 및 기타 언어

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

- MSDN : 수율 (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입니까? 감소는 게으름의 정의에 맞는 것 같습니다.
• 합니까 게으른 항상 평균 썽크 및 비 엄격한 항상 평균 부분 평가 ? 이것은 일반화입니까?
• 다음과 같은 필수 개념은 지연, 비 엄격, 둘 다 또는 둘 다입니까?
  • 단락
  • 수율 사용
  • 실행을 지연하거나 방지하기 위해 콜백 전달
• 가 게으른 의 부분 집합 이 아닌 엄격한 또는 그는 반대, 또는 그들이 상호 배타적입니다. 예를 들어이 될 수 있습니다 비 엄격한 없이 지연 또는 지연 없이 비 엄격한 ?
• Haskell의 비 엄격 성은 게으름에 의해 달성됩니까?

매우 고맙습니다!

---

엄격하지 않고 게으른 것은 비공식적으로 상호 교환 할 수 있지만 다른 토론 영역에 적용됩니다.

비 엄격한는 를 의미 의미 : 식의 수학적 의미를. 엄격하지 않은 세계는 함수의 실행 시간, 메모리 소비 또는 컴퓨터에 대한 개념이 없습니다. 도메인의 어떤 종류의 값이 공동 도메인의 어떤 종류의 값에 매핑되는지에 대해 간단히 설명합니다. 특히 엄격한 함수는 ⊥ 값 ( "bottom"-이에 대한 자세한 내용은 위의 의미 링크 참조)을 ⊥에 매핑해야합니다. 엄격하지 않은 함수는이를 수행 할 수 없습니다.

Lazy 는 실제 컴퓨터에서 코드가 실행되는 방식 인 작동 동작을 나타냅니다. 대부분의 프로그래머는 프로그램을 운영 적으로 생각하므로 아마도 이것이 당신이 생각하는 것입니다. 지연 평가는 썽크 (thunk)를 사용하는 구현을 말합니다. 코드가 처음 실행될 때 값으로 대체되는 포인터입니다. 여기서 의미가없는 단어 인 "pointer", "first time", "executed"를 확인하십시오.

게으른 평가는 엄격하지 않은 의미 체계를 생성하므로 개념이 매우 가깝게 보입니다. 그러나 FUZxxl이 지적했듯이 게으름은 엄격하지 않은 의미를 구현하는 유일한 방법은 아닙니다.

이 구별에 대해 더 자세히 알고 싶다면 위의 링크를 적극 권장합니다. 그것을 읽는 것은 컴퓨터 프로그램의 의미에 대한 제 개념의 전환점이되었습니다.

---

엄격 하지도 게으르지 도 않은 평가 모델의 예 : 낙관적 평가 , 많은 "쉬운"썽크를 피할 수 있으므로 약간의 속도 향상 :

낙관적 평가는 상위 표현식을 평가하는 데 하위 표현식이 필요하지 않더라도 일부 휴리스틱을 사용하여 일부를 평가한다는 것을 의미합니다. 하위 표현식이 충분히 빨리 종료되지 않으면 실제로 필요할 때까지 평가를 일시 중단합니다. 썽크를 생성 할 필요가 없기 때문에 나중에 하위 표현식이 필요한 경우 지연 평가보다 유리합니다. 반면에 표현식이 종료되지 않으면 충분히 빨리 중단 할 수 있으므로 너무 많이 잃지 않습니다.

보시다시피이 평가 모델은 엄격하지 않습니다 . _ | _를 산출하는 것이 평가되지만 필요하지 않은 경우 엔진이 평가를 중단하므로 함수가 종료됩니다. 반면에 필요한 것보다 더 많은 표현식이 평가 될 수 있으므로 완전히 게으른 것은 아닙니다 .

---

예, 여기에는 용어의 불분명 한 사용이 있지만 대부분의 경우에 관계없이 용어가 일치하므로 문제가되지 않습니다.

One major difference is when terms are evaluated. There are multiple strategies for this, ranging on a spectrum from "as soon as possible" to "only at the last moment". The term eager evaluation is sometimes used for strategies leaning toward the former, while lazy evaluation적절하게는 후자에 크게 기울어 진 전략 군을 의미합니다. "게으른 평가"와 관련 전략의 구분은 평가 결과가 보관되는시기와 장소와 관련이있는 경향이 있습니다. 데이터 구조에 이름을 지정하고 색인화하는 Haskell의 익숙한 메모 기법은이를 기반으로합니다. 대조적으로, 단순히 표현을 서로 연결하는 언어 ( "call-by-name"평가에서와 같이)는이를 지원하지 않을 수 있습니다.

The other difference is which terms are evaluated, ranging from "absolutely everything" to "as little as possible". Since any value actually used to compute the final result can't be ignored, the difference here is how many superfluous terms are evaluated. As well as reducing the amount of work the program has to do, ignoring unused terms means that any errors they would have generated won't occur. When a distinction is being drawn, strictness refers to the property of evaluating everything under consideration (in the case of a strict function, for instance, this means the terms it's applied to. It doesn't necessarily mean sub-expressions inside the arguments), while non-strict means evaluating only some things (either by delaying evaluation, or by discarding terms entirely).

It should be easy to see how these interact in complicated ways; decisions are not at all orthogonal, as the extremes tend to be incompatible. For instance:

• Very non-strict evaluation precludes some amount of eagerness; if you don't know whether a term will be needed, you can't evaluate it yet.

• Very strict evaluation makes non-eagerness somewhat irrelevant; if you're evaluating everything, the decision of when to do so is less significant.

Alternate definitions do exist, though. For instance, at least in Haskell, a "strict function" is often defined as one that forces its arguments sufficiently that the function will evaluate to _|_ ("bottom") whenever any argument does; note that by this definition, id is strict (in a trivial sense), because forcing the result of id x will have exactly the same behavior as forcing x alone.

---

This started out as an update but it started to get long.

Laziness / Call-by-need is a memoized version of call-by-name where, if the function argument is evaluated, that value is stored for subsequent uses. In a "pure" (effect-free) setting, this produces the same results as call-by-name; when the function argument is used two or more times, call-by-need is almost always faster.
Imperative Example - Apparently this is possible. There is an interesting article on Lazy Imperative Languages. It says there are two methods. One requires closures the second uses graph reductions. Since C does not support closures you would need to explicitly pass an argument to your iterator. You could wrap a map structure and if the value does not exist calculate it otherwise return value.
Note: Haskell implements this by "pointers to code which are replaced with a value the first time they are executed" - luqui.
This is non-strict call-by-name but with sharing/memorization of the results.

Call-By-Name - In call-by-name evaluation, the arguments to a function are not evaluated before the function is called — rather, they are substituted directly into the function body (using capture-avoiding substitution) and then left to be evaluated whenever they appear in the function. If an argument is not used in the function body, the argument is never evaluated; if it is used several times, it is re-evaluated each time it appears.
Imperative Example: callbacks
Note: This is non-strict as it avoids evaluation if not used.

Non-Strict = In non-strict evaluation, arguments to a function are not evaluated unless they are actually used in the evaluation of the function body.
Imperative Example: short-circuiting
Note: _|_ appears to be a way to test if a function is non-strict

So a function can be non-strict but not lazy. A function that is lazy is always non-strict. Call-By-Need is partly defined by Call-By-Name which is partly defined by Non-Strict

An Excerpt from "Lazy Imperative Languages"

2.1. NON-STRICT SEMANTICS VS. LAZY EVALUATION We must first clarify the distinction between "non-strict semantics" and "lazy evaluation". Non-strictsemantics are those which specify that an expression is not evaluated until it is needed by a primitiveoperation. There may be various types of non-strict semantics. For instance, non-strict procedure calls donot evaluate the arguments until their values are required. Data constructors may have non-strictsemantics, in which compound data are assembled out of unevaluated pieces Lazy evaluation, also called delayed evaluation, is the technique normally used to implement non-strictsemantics. In section 4, the two methods commonly used to implement lazy evaluation are very brieflysummarized.

CALL BY VALUE, CALL BY LAZY, AND CALL BY NAME "Call by value" is the general name used for procedure calls with strict semantics. In call by valuelanguages, each argument to a procedure call is evaluated before the procedure call is made; the value isthen passed to the procedure or enclosing expression. Another name for call by value is "eager" evaluation.Call by value is also known as "applicative order" evaluation, because all arguments are evaluated beforethe function is applied to them."Call by lazy" (using William Clinger's terminology in [8]) is the name given to procedure calls which usenon-strict semantics. In languages with call by lazy procedure calls, the arguments are not evaluatedbefore being substituted into the procedure body. Call by lazy evaluation is also known as "normal order"evaluation, because of the order (outermost to innermost, left to right) of evaluation of an expression."Call by name" is a particular implementation of call by lazy, used in Algol-60 [18]. The designers ofAlgol-60 intended that call-by-name parameters be physically substituted into the procedure body, enclosedby parentheses and with suitable name changes to avoid conflicts, before the body was evaluated.

CALL BY LAZY VS. CALL BY NEED Call by need is an extension of call by lazy, prompted by the observation that a lazy evaluation could beoptimized by remembering the value of a given delayed expression, once forced, so that the value need notbe recalculated if it is needed again. Call by need evaluation, therefore, extends call by lazy methods byusing memoization to avoid the need for repeated evaluation. Friedman and Wise were among the earliestadvocates of call by need evaluation, proposing "suicidal suspensions" which self-destructed when theywere first evaluated, replacing themselves with their values.

---

The way I understand it, "non-strict" means trying to reduce workload by reaching completion in a lower amount of work.

Whereas "lazy evaluation" and similar try to reduce overall workload by avoiding full completion (hopefully forever).

from your examples...

f1() || f2()

...short circuiting from this expression would not possibly result in triggering 'future work', and there's neither a speculative/amortized factor to the reasoning, nor any computational complexity debt accruing.

Whereas in the C# example, "lazy" conserves a function call in the overall view, but in exchange, comes with those above sorts of difficulty (at least from point of call until possible full completion... in this code that's a negligible-distance pathway, but imagine those functions had some high-contention locks to put up with).

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

---

If we're talking general computer science jargon, then "lazy" and "non-strict" are generally synonyms -- they stand for the same overall idea, which expresses itself in different ways for different situations.

However, in a given particular specialized context, they may have acquired differing technical meanings. I don't think you can say anything accurate and universal about what the difference between "lazy" and "non-strict" is likely to be in the situation where there is a difference to make.

참고URL : https://stackoverflow.com/questions/7140978/haskell-how-does-non-strict-and-lazy-differ