왜 게으른 평가가 유용한 지 오랫동안 궁금해했습니다. 나는 아직 말이되는 방식으로 나에게 설명하는 사람이 없습니다. 대부분은 “나를 믿어 라”로 끝이납니다.
참고 : 나는 메모를 의미하지 않습니다.
답변
대부분 더 효율적일 수 있기 때문에 값을 사용하지 않을 경우 계산할 필요가 없습니다. 예를 들어 함수에 세 개의 값을 전달할 수 있지만 조건식의 시퀀스에 따라 실제로 하위 집합 만 사용할 수 있습니다. C와 같은 언어에서는 어쨌든 세 가지 값이 모두 계산됩니다. 그러나 Haskell에서는 필요한 값만 계산됩니다.
또한 무한 목록과 같은 멋진 것들을 허용합니다. C와 같은 언어로는 무한 목록을 가질 수 없지만 Haskell에서는 문제가되지 않습니다. 무한 목록은 수학의 특정 영역에서 상당히 자주 사용되므로이를 조작하는 능력이 있으면 유용 할 수 있습니다.
답변
지연 평가의 유용한 예는 다음을 사용하는 것입니다 quickSort.
quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)이제 목록의 최소값을 찾으려면 다음을 정의 할 수 있습니다.
minimum ls = head (quickSort ls)먼저 목록을 정렬 한 다음 목록의 첫 번째 요소를 가져옵니다. 그러나 게으른 평가 때문에 머리 만 계산됩니다. 예를 들어 목록의 최소값을 취하면[2, 1, 3,] quickSort는 먼저 2보다 작은 모든 요소를 필터링합니다. 그런 다음 이미 충분한 QuickSort를 수행합니다 (단일 목록 [1] 반환). 지연 평가로 인해 나머지는 정렬되지 않으므로 계산 시간이 많이 절약됩니다.
이것은 물론 매우 간단한 예이지만 게으름은 매우 큰 프로그램에 대해 동일한 방식으로 작동합니다.
그러나이 모든 것에는 단점이 있습니다. 프로그램의 런타임 속도와 메모리 사용량을 예측하기가 더 어려워집니다. 이것은 게으른 프로그램이 느리거나 더 많은 메모리를 차지한다는 것을 의미하지는 않지만 알아두면 좋습니다.
답변
게으른 평가는 여러 가지에 유용합니다.
첫째, 기존의 모든 게으른 언어는 순수합니다. 게으른 언어에서는 부작용에 대해 추론하기가 매우 어렵 기 때문입니다.
순수 언어를 사용하면 방정식 추론을 사용하여 함수 정의에 대해 추론 할 수 있습니다.
foo x = x + 3안타깝게도 지연이 아닌 설정에서는 지연 설정보다 더 많은 문이 반환되지 않으므로 ML과 같은 언어에서는 유용하지 않습니다. 그러나 게으른 언어에서는 평등에 대해 안전하게 추론 할 수 있습니다.
둘째, 하스켈과 같은 게으른 언어에서는 ML의 ‘값 제한’과 같은 많은 것들이 필요하지 않습니다. 이로 인해 구문이 크게 정리됩니다. 언어와 같은 ML은 var 또는 fun과 같은 키워드를 사용해야합니다. Haskell에서 이러한 것들은 하나의 개념으로 축소됩니다.
셋째, 게으름을 사용하면 조각으로 이해할 수있는 매우 기능적인 코드를 작성할 수 있습니다. Haskell에서는 다음과 같은 함수 본문을 작성하는 것이 일반적입니다.
foo x y = if condition1
then some (complicated set of combinators) (involving bigscaryexpression)
else if condition2
then bigscaryexpression
else Nothing
where some x y = ...
bigscaryexpression = ...
condition1 = ...
condition2 = ...이렇게하면 함수 본문을 이해하면서 ‘하향식’으로 작업 할 수 있습니다. ML과 유사한 언어 let는 엄격하게 평가되는를 사용하도록 강요합니다 . 결과적으로 값이 비싸거나 부작용이있는 경우 항상 평가되는 것을 원하지 않기 때문에 let 절을 함수의 본문으로 ‘리프트’할 수 없습니다. Haskell은 해당 절의 내용이 필요한 경우에만 평가된다는 것을 알고 있으므로 where 절에 대한 세부 정보를 명시 적으로 ‘푸시’할 수 있습니다.
실제로 우리는 가드를 사용하는 경향이 있으며 다음을 위해 더 축소합니다.
foo x y
| condition1 = some (complicated set of combinators) (involving bigscaryexpression)
| condition2 = bigscaryexpression
| otherwise = Nothing
where some x y = ...
bigscaryexpression = ...
condition1 = ...
condition2 = ...넷째, 게으름은 때때로 특정 알고리즘의 훨씬 더 우아한 표현을 제공합니다. Haskell의 게으른 ‘빠른 정렬’은 한 줄짜리이며 처음 몇 개의 항목 만 보면 해당 항목 만 선택하는 비용에 비례하는 비용 만 지불한다는 이점이 있습니다. 이 작업을 엄격하게 방해하는 것은 없지만 동일한 점근 적 성능을 얻으려면 매번 알고리즘을 다시 코딩해야합니다.
다섯째, 게으름을 통해 언어로 새로운 제어 구조를 정의 할 수 있습니다. 엄격한 언어로 구문과 같이 새로운 ‘if .. then .. else ..’를 작성할 수 없습니다. 다음과 같은 함수를 정의하려고하면 :
if' True x y = x
if' False x y = y엄격한 언어에서는 조건 값에 관계없이 두 분기가 모두 평가됩니다. 루프를 고려하면 더 나빠집니다. 모든 엄격한 솔루션에는 일종의 인용문 또는 명시 적 람다 구성을 제공하는 언어가 필요합니다.
마지막으로, 같은 맥락에서 모나드와 같은 유형 시스템의 부작용을 처리하는 가장 좋은 메커니즘 중 일부는 실제로 게으른 설정에서만 효과적으로 표현할 수 있습니다. 이것은 F #의 워크 플로의 복잡성을 Haskell Monads와 비교하여 확인할 수 있습니다. (엄격한 언어로 모나드를 정의 할 수 있지만, 안타깝게도 게으름과 워크 플로 부족으로 인해 모나드 법칙을 한두 번 실패하는 경우가 많습니다.
답변
일반 주문 평가와 지연 평가에는 차이가 있습니다 (하스켈에서와 같이).
square x = x * x다음 식을 평가하는 중 …
square (square (square 2))… 열심히 평가 :
> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256… 일반 주문 평가 :
> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256… 게으른 평가 :
> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256지연 평가는 구문 트리를보고 트리 변환을 수행하기 때문입니다.
square (square (square 2))
||
\/
*
/ \
\ /
square (square 2)
||
\/
*
/ \
\ /
*
/ \
\ /
square 2
||
\/
*
/ \
\ /
*
/ \
\ /
*
/ \
\ /
2… 일반 주문 평가는 텍스트 확장 만 수행합니다.
이것이 우리가 지연 평가를 사용할 때 더 강력 해지면서 (평가가 다른 전략보다 더 자주 종료 됨) 성능이 열망 평가 (적어도 O 표기법에서)와 동일한 이유입니다.
답변
RAM 관련 가비지 콜렉션과 동일한 방식으로 CPU 관련 지연 평가. GC를 사용하면 메모리가 무제한 인 것처럼 가장하여 필요한만큼 메모리에있는 개체를 요청할 수 있습니다. 런타임은 사용할 수없는 개체를 자동으로 회수합니다. LE를 사용하면 계산 리소스가 무제한 인 척 할 수 있습니다. 필요한만큼 계산을 수행 할 수 있습니다. 런타임은 불필요한 (주어진 경우) 계산을 실행하지 않습니다.
이러한 “가장”모델의 실질적인 이점은 무엇입니까? 개발자가 리소스 관리에서 어느 정도까지는 해제하고 소스에서 일부 상용구 코드를 제거합니다. 그러나 더 중요한 것은보다 광범위한 컨텍스트에서 솔루션을 효율적으로 재사용 할 수 있다는 것입니다.
숫자 S와 숫자 N의 목록이 있다고 가정합니다. 목록 S에서 숫자 N에 가장 가까운 숫자 M을 찾아야합니다. 단일 N과 N의 일부 목록 L (L의 각 N에 대해 ei)의 두 가지 컨텍스트를 가질 수 있습니다. S)에서 가장 가까운 M을 찾습니다. 지연 평가를 사용하는 경우 S를 정렬하고 이진 검색을 적용하여 M에서 N에 가장 가까운 M을 찾을 수 있습니다. 좋은 지연 정렬을 위해서는 단일 N 및 O (ln (size (S)) *에 대해 O (size (S)) 단계가 필요합니다. (size (S) + size (L))) 균등 분포 L에 대한 단계. 최적의 효율성을 달성하기위한 지연 평가가없는 경우 각 컨텍스트에 대한 알고리즘을 구현해야합니다.
답변
Simon Peyton Jones를 믿는다면 게으른 평가는 그 자체로 중요하지 않고 디자이너가 언어를 순수하게 유지하도록 강요하는 ‘헤어 셔츠’로서 만 중요 합니다. 나는이 관점에 공감한다.
Richard Bird, John Hughes 및 Ralf Hinze는 지연 평가로 놀라운 일을 할 수 있습니다. 그들의 작품을 읽으면 감사하는 데 도움이 될 것입니다. 좋은 출발점은 Bird의 웅장한 스도쿠 솔버와 Why Functional Programming Matters 에 대한 Hughes의 논문입니다 .
답변
tic-tac-toe 프로그램을 고려하십시오. 여기에는 네 가지 기능이 있습니다.
- 현재 보드를 가져와 각각 하나의 이동이 적용된 새 보드 목록을 생성하는 이동 생성 기능입니다.
- 그런 다음 이동 생성 기능을 적용하여이 항목에서 따를 수있는 모든 보드 위치를 유도하는 “이동 트리”기능이 있습니다.
- 최상의 다음 동작을 찾기 위해 트리 (또는 그 일부만)를 걷는 미니 맥스 함수가 있습니다.
- 플레이어 중 한 명이 이겼는지 판단하는 보드 평가 기능이 있습니다.
이것은 관심사를 명확하게 분리합니다. 특히 이동 생성 기능과 보드 평가 기능은 게임의 규칙을 이해하는 데 필요한 유일한 기능입니다. 이동 트리와 미니 맥스 기능은 완전히 재사용 할 수 있습니다.
이제 tic-tac-toe 대신 체스를 구현해 보겠습니다. “eager”(즉, 전통적인) 언어에서는 이동 트리가 메모리에 맞지 않기 때문에 작동하지 않습니다. 따라서 이제 보드 평가 및 이동 생성 기능을 이동 트리 및 미니 맥스 논리와 혼합해야합니다. 생성 할 이동을 결정하는 데 minimax 논리를 사용해야하기 때문입니다. 우리의 멋진 모듈 식 구조가 사라졌습니다.
그러나 게으른 언어에서 이동 트리의 요소는 minimax 함수의 요구에 응답해서 만 생성됩니다. 전체 이동 트리를 생성 할 필요는 없습니다. 그래서 우리의 깨끗한 모듈 구조는 여전히 실제 게임에서 작동합니다.
