Haskell의 엄격함은 무엇입니까?

Haskell의 엄격함은 무엇입니까?

---

우리 모두는 Haskell이 기본적으로 게으르다는 것을 알고 있습니다 (또는 알아야합니다). 평가할 때까지 아무것도 평가되지 않습니다. 그렇다면 언제 무엇을 평가해야합니까? Haskell이 엄격해야하는 점이 있습니다. 나는 이것을 "엄격 점"이라고 부른다. 비록이 특정 용어가 내가 생각했던 것만 큼 널리 퍼지는 것은 아니지만. 나에 따라:

Haskell의 감소 (또는 평가) 는 엄격 성 지점 에서만 발생합니다.

질문은 그래서 : 무엇을 정확하게 , 하스켈의 엄격 포인트입니까? 내 직감에 따르면 main, seq/ 뱅 패턴, 패턴 매칭 및을 IO통해 수행되는 모든 작업 main이 주요 엄격 점이지만 그 이유를 실제로 알지 못합니다.

(그들은 "엄격 포인트"라고하지 않는 경우 또한, 무엇 이다 그들이라고?)

좋은 대답에는 WHNF 등에 대한 토론이 포함될 것이라고 생각합니다. 나는 또한 람다 미적분에 영향을 미칠 것이라고 상상합니다.

---

편집 :이 질문에 대한 추가 생각.

이 질문에 대해 생각해 보았 듯이 엄격 점의 정의에 무언가를 추가하는 것이 더 분명하다고 생각합니다. Strictness points는 다양한 컨텍스트 와 다양한 깊이 (또는 엄격함)를 가질 수 있습니다 . "하스켈에서의 감소는 엄격 성 지점에서만 발생한다"라는 제 정의로 돌아가서,이 정의에이 절을 추가하겠습니다. "엄격 성 지점은 주변 컨텍스트가 평가되거나 축소 될 때만 트리거됩니다."

그래서 제가 원하는 종류의 답변을 시작하도록하겠습니다. main엄격함입니다. 특히 문맥의 주요 엄격 점 인 프로그램으로 지정됩니다. 프로그램 ( main의 컨텍스트)이 평가되면 main의 엄격 성 포인트가 활성화됩니다. Main의 깊이는 최대이며 완전히 평가되어야합니다. Main은 일반적으로 IO 작업으로 구성되며, 이는 컨텍스트가 main.

이제 시도해보십시오. seq이러한 용어에 대해 논의 하고 패턴 매칭을 수행하십시오. 함수 적용의 뉘앙스를 설명하십시오 : 얼마나 엄격합니까? 어때요? 어때 deepseq? let및 case진술? unsafePerformIO? Debug.Trace? 최상위 정의? 엄격한 데이터 유형? 뱅 패턴? Etc. 이러한 항목 중 몇 개를 시퀀스 또는 패턴 매칭으로 설명 할 수 있습니까?

---

시작하기 좋은 곳은이 논문을 이해하는 것입니다 : Lazy Evalution을위한 Natural Semantics (Launchbury). 그러면 GHC의 Core와 유사한 작은 언어에 대해 표현식이 평가되는시기를 알 수 있습니다. 나머지 질문은 전체 Haskell을 Core에 매핑하는 방법이며 대부분의 번역은 Haskell 보고서 자체에 의해 제공됩니다. GHC에서 우리는이 과정을 "desugaring"이라고 부릅니다. 그 이유는 문법적 설탕을 제거하기 때문입니다.

글쎄요, 그것이 전체 이야기가 아닙니다. GHC에는 탈당과 코드 생성 사이에 최적화 된 전체 뗏목이 포함되어 있고, 이러한 변환 중 상당수가 Core를 재 배열하여 사물이 서로 다른 시간에 평가되도록 할 것입니다 (특히 엄격 성 분석은 사물이 평가되도록 할 것입니다). 일찍이). 그래서 정말 방법을 이해하는 당신 , 당신은 코어 GHC에 의해 생산 볼 필요가 프로그램 평가됩니다.

아마도이 대답은 당신에게 약간 추상적 인 것처럼 보이지만 (나는 특별히 뱅 패턴이나 seq를 언급하지 않았습니다), 당신은 정확한 것을 요청 했고 이것은 우리가 할 수있는 최선에 대한 것입니다.

---

나는 아마도이 질문을 Haskell이 어떤 상황에서 표현을 평가할 것인가? (아마도 "머리가 약한 정상 형태"에 압정을 붙일 것입니다.)

첫 번째 근사치로 다음과 같이 지정할 수 있습니다.

• IO 작업을 실행하면 "필요한"모든식이 평가됩니다. (따라서 IO 액션이 실행되는지 알아야합니다. 예를 들어 이름이 main인지, 아니면 main에서 호출되었는지 그리고 액션에 필요한 것이 무엇인지 알아야합니다.)
• 평가중인 표현식 (이건 재귀 적 정의입니다!)은 필요한 모든 표현식을 평가합니다.

직관적 인 목록에서 기본 및 IO 작업은 첫 번째 범주에 속하고 시퀀스 및 패턴 일치는 두 번째 범주에 속합니다. 하지만 첫 번째 범주는 "엄격 점"에 대한 당신의 생각과 더 일치한다고 생각합니다. 사실 그것이 우리가 Haskell에서 평가 를 사용자에게 관찰 가능한 효과 로 만드는 방법이기 때문입니다 .

Haskell은 큰 언어이기 때문에 모든 세부 사항을 구체적으로 제공하는 것은 큰 작업입니다. Concurrent Haskell은 결국 결과를 사용하지 않더라도 추측 적으로 평가할 수 있기 때문에 매우 미묘합니다. 이것은 평가를 유발하는 세 번째 유형입니다. 두 번째 범주는 꽤 잘 연구 되어 있습니다. 관련된 기능 의 엄격함 을 살펴보고 싶습니다 . 이 때문에 약간의 사기 비록 첫 번째 범주는 너무, "엄격"의 일종으로 생각 될 수 evaluate x와 seq x $ return ()실제로 다른 것들! IO 모나드에 어떤 종류의 의미를 부여하면 적절하게 처리 할 수 ​​있지만 (명시 적으로 RealWorld#토큰을 전달하는 것은 간단한 경우에 작동 함) 일반적으로 이런 종류의 계층화 된 엄격 성 분석에 대한 이름이 있는지 모르겠습니다.

---

C에는 특정 연산에 대해 한 피연산자가 다른 피연산자보다 먼저 평가된다는 것을 보장하는 시퀀스 포인트 개념 이 있습니다. 그 가장 가까운 기존의 개념이라고 생각하지만, 기본적으로 해당 기간 엄격 포인트 (또는 가능하게 힘 점 )보다 하스켈 생각과 일치한다.

실제로 Haskell은 순전히 게으른 언어가 아닙니다. 예를 들어 패턴 일치는 일반적으로 엄격합니다 (따라서 패턴 일치를 시도하면 적어도 일치를 수락하거나 거부 할 수있을만큼 충분히 평가가 발생합니다.

…

프로그래머는 seq결과가 사용되는지 여부에 관계없이 표현식을 강제로 평가 하기 위해 프리미티브를 사용할 수도 있습니다 .

$!로 정의됩니다 seq.

— Lazy vs. Non-strict .

에 대한 당신의 생각 그래서 !/ $!과 seq본질적으로 잘하지만, 패턴 매칭이 미묘한 규칙이 적용이됩니다. ~물론 지연 패턴 일치를 강제 하는 데 항상 사용할 수 있습니다 . 같은 기사에서 흥미로운 점 :

엄격도 분석기는 또한 외부 표현식에 항상 하위 표현식이 필요한 경우를 찾아서이를 즉시 평가로 변환합니다. 의미론 ( "하단"측면에서)이 변경되지 않기 때문에이를 수행 할 수 있습니다.

토끼 구멍 아래로 계속해서 GHC에서 수행하는 최적화 문서를 살펴 보겠습니다.

엄격 성 분석은 GHC가 컴파일 타임에 어떤 데이터가 반드시 '항상 필요'할 것인지 결정하려고 시도하는 프로세스입니다. 그런 다음 GHC는 계산을 저장하고 나중에 실행하기위한 일반 (더 높은 오버 헤드) 프로세스가 아니라 이러한 데이터를 계산하는 코드를 빌드 할 수 있습니다.

— GHC 최적화 : 엄격도 분석 .

즉, 엄격한 코드가 생성 될 수 있습니다 어디서나 썽크를 생성하는 데이터가 항상 필요합니다 (및 / 또는 한 번만 사용할 수 있습니다) 때 불필요하게 고가이기 때문에, 최적화 등.

… 값에 대해 더 이상 평가를 수행 할 수 없습니다. 그것은 정상적인 형태 라고합니다 . 값에 대해 최소한 몇 가지 평가를 수행하기 위해 중간 단계 중 하나에 있으면 WHNF (Wak Head Normal Form )입니다. ( 'head normal form'도 있지만 Haskell에서는 사용되지 않습니다.) WHNF에서 무언가를 완전히 평가하면 정상적인 형태로 축소됩니다.

— Wikibooks Haskell : 게으름

( 헤드 위치 ¹ 에 베타 redex가없는 경우 용어는 헤드 정규 형식 입니다. redex는 redex가 아닌 ² 의 람다 추상 자만 앞에 오는 경우 헤드 redex 입니다.) 따라서 썽크를 강제하기 시작하면, 당신은 WHNF에서 일하고 있습니다. 강제 할 썽크가 더 이상 남아 있지 않으면 정상적인 상태입니다. 또 다른 흥미로운 점 :

… 어떤 시점에서 사용자에게 z를 인쇄해야하는 경우이를 완전히 평가해야합니다…

이는 실제로 IO수행되는 모든 작업 main 이 강제 평가를 수행 한다는 것을 의미합니다. 이는 Haskell 프로그램이 실제로 작업을 수행 한다는 점을 고려할 때 분명해야합니다. 에 정의 된 시퀀스를 거쳐야하는 모든 것은 main정상적인 형식이어야하며 따라서 엄격한 평가를 받아야합니다.

C. A. McCann got it right in the comments, though: the only thing that's special about main is that main is defined as special; pattern matching on the constructor is sufficient to ensure the sequence imposed by the IO monad. In that respect only seq and pattern-matching are fundamental.

---

Haskell is AFAIK not a pure lazy language, but rather a non-strict language. This means that it does not necessarily evaluate terms at the last possible moment.

A good source for haskell's model of "lazyness" can be found here: http://en.wikibooks.org/wiki/Haskell/Laziness

Basically, it is important to understand the difference between a thunk and the weak header normal form WHNF.

My understanding is that haskell pulls computations through backwards as compared to imperative languages. What this means is that in the absence of "seq" and bang patterns, it will ultimately be some kind of side effect that forces the evaluation of a thunk, which may cause prior evaluations in turn (true lazyness).

As this would lead to a horrible space leak, the compiler then figures out how and when to evaluate thunks ahead of time to save space. The programmer can then support this process by giving strictness annotations (en.wikibooks.org/wiki/Haskell/Strictness , www.haskell.org/haskellwiki/Performance/Strictness) to further reduce space usage in form of nested thunks.

I am not an expert in the operational semantics of haskell, so I will just leave the link as a resource.

Some more resources:

http://www.haskell.org/haskellwiki/Performance/Laziness

http://www.haskell.org/haskellwiki/Haskell/Lazy_Evaluation

---

Lazy doesn't mean do nothing. Whenever your program pattern matches a case expression, it evaluates something -- just enough anyway. Otherwise it can't figure out which RHS to use. Don't see any case expressions in your code? Don't worry, the compiler is translating your code to a stripped down form of Haskell where they are hard to avoid using.

For a beginner, a basic rule of thumb is let is lazy, case is less lazy.

---

This is not a full answer aiming for karma, but just a piece of the puzzle -- to the extent that this is about semantics, bear in mind that there are multiple evaluation strategies that provide the same semantics. One good example here -- and the project also speaks to how we typically think of Haskell semantics -- was the Eager Haskell project, which radically altered evaluation strategies while maintaining the same semantics: http://csg.csail.mit.edu/pubs/haskell.html

---

The Glasgow Haskell compiler translates your code into a Lambda-calculus-like language called core. In this language, something is going to be evaluated, whenever you pattern match it by a case-statement. Thus if a function is called, the outermost constructor and only it (if there are no forced fields) is going to be evaluated. Anything else is canned in a thunk. (Thunks are introduced by let bindings).

Of course this is not exactly what happens in the real language. The compiler convert Haskell into Core in a very sophisticated way, making as many things as possibly lazy and anything that is always needed lazy. Additionally, there are unboxed values and tuples that are always strict.

If you try to evaluate a function by hand, you can basically think:

• Try to evaluate the outermost constructor of the return.
• If anything else is needed to get the result (but only if it's really needed) is also going to be evaluated. The order doesn't matters.
• In case of IO you have to evaluate the results of all statements from the first to the last in that. This is a bit more complicated, since the IO monad does some tricks to force evaluation in a specific order.

참고URL : https://stackoverflow.com/questions/7490768/what-are-haskells-strictness-points