Lazy Evaluation의 장점은 무엇입니까?

Question

열심 인 평가와는 달리 지연 평가에는 어떤 이점이 있습니까?

어떤 성능 오버 헤드가 있습니까? 게으른 평가가 느려지거나 빠를 것입니까? 왜 (또는 구현에 의존 하는가?)

실제로 대부분의 구현에서 느린 평가는 일입니까? 내게는 변수가 숫자뿐만 아니라 연산을 저장해야하기 때문에 훨씬 더 느리고 메모리 집약적 인 것처럼 보일 것입니다. 그렇다면 하스켈과 같은 언어로 어떻게 작동할까요? (사실, 저는 그 언어를 실제로 알지 못합니다)? lazyness가 구현되고 실행되어 어떻게 더 느리게/더 많은 공간을 소비하지 않는가?

Answer 1

이것은 구문 트리의 평가를 나타냅니다. 구문 트리를 느리게 평가하는 경우 (즉, 표현 된 값이 필요할 때) 계산의 이전 단계를 통해 구문 트리 전체를 수행해야합니다. 이것은 게으른 평가의 오버 헤드입니다. 그러나 두 가지 이점이 있습니다. 1) 결과가 전혀 사용되지 않으면 트리를 불필요하게 제거하지 않을 것입니다. 2) 무한 구문 트리를 재귀 적 형식으로 표현하고 사용할 수 있습니다. (열망하여) 불가능할 것입니다.

저는 haskel을 모르지만 파이썬이나 ML과 같은 프로그래밍 언어는 열심히 평가합니다. 예를 들어 ML에서 지연 평가를 시뮬레이션하려면 매개 변수를 사용하지 않고 결과를 반환하는 더미 함수를 만들어야합니다. 이 함수는 빈 인자 목록으로 호출하여 언제든지 느리게 평가할 수있는 구문 트리입니다.

Answer 2

루비에서는 일반적으로 "once"라고 불리는 함수 수정자를 사용하여 메소드를 래핑하여 지연 평가를 수행합니다. 이러한 메서드는 한 번만 평가되고 캐시 된 값은 해당 값을 반환하는 후속 호출입니다.

게으른 평가를 한 번 사용 (또는 오용)하는 것은 명시 적이 아니라 암시 적으로 개체 초기화 순서를 지정하는 것입니다. 전에 : 지연 평가를

def initialize 
    setup_logging # Must come before setup_database 
    setup_database # Must come before get_addresses 
    setup_address_correction # Must come before get_addresses 
    get_addresses 
end 

def setup_logging 
    @log = Log.new 
end 

def setup_database 
    @db = Db.new(@log) 
end 

def setup_address_correction 
    @address_correction = AddressCorrection.new 
end 

def get_addresses 
    @log.puts ("Querying addresses") 
    @addresses = @address_correction.correct(query_addresses(@db)) 
end 

:

def initialize 
    get_addresses 
end 

def log 
    Log.new 
end 
once :log 

def db 
    Db.new(log) 
end 
once :db 

def address_corrector 
    AddressCorrection.new 
end 
once :address_corrector 

def get_addresses 
    log.puts ("Querying addresses") 
    @addresses = address_corrector.correct(query_addresses(db)) 
end 

다양한 객체 의존적 초기화 순서 (1) 암시, 및 (2) 자동 지금이다. 단점이라면이 트릭을 너무 많이 사용하면 제어 흐름이 불투명해질 수 있습니다.

Answer 3

지연 평가는 효율적인 상각 된 경계가있는 데이터 구조를 만드는 데 매우 유용 할 수 있습니다.

그냥 예를주고, 여기 불변의 스택 클래스입니다 : 당신은 O(1) 시간에 스택의 전면에 항목을 추가 할 수 있습니다

class Stack<T> 
{ 
    public static readonly Stack<T> Empty = new Stack<T>(); 
    public T Head { get; private set; } 
    public Stack<T> Tail { get; private set; } 
    public bool IsEmpty { get; private set; } 

    private Stack(T head, Stack<T> tail) 
    { 
     this.Head = head; 
     this.Tail = tail; 
     this.IsEmpty = false; 
    } 

    private Stack() 
    { 
     this.Head = default(T); 
     this.Tail = null; 
     this.IsEmpty = true; 
    } 

    public Stack<T> AddFront(T value) 
    { 
     return new Stack<T>(value, this); 
    } 

    public Stack<T> AddRear(T value) 
    { 
     return this.IsEmpty 
      ? new Stack<T>(value, this) 
      : new Stack<T>(this.Head, this.Tail.AddRear(value)); 
    } 
} 

,하지만에 항목을 추가 할 O(n) 시간이 필요합니다 후방. 전체 데이터 구조를 다시 빌드해야하기 때문에 AddRear은 모 놀리 식 작업입니다.

여기에 같은 불변의 스택,하지만 지금은 게으르게 평가 :

class LazyStack<T> 
{ 
    public static readonly LazyStack<T> Empty = new LazyStack<T>(); 

    readonly Lazy<LazyStack<T>> innerTail; 
    public T Head { get; private set; } 
    public LazyStack<T> Tail { get { return innerTail.Value; } } 
    public bool IsEmpty { get; private set; } 

    private LazyStack(T head, Lazy<LazyStack<T>> tail) 
    { 
     this.Head = head; 
     this.innerTail = tail; 
     this.IsEmpty = false; 
    } 

    private LazyStack() 
    { 
     this.Head = default(T); 
     this.innerTail = null; 
     this.IsEmpty = true; 
    } 

    public LazyStack<T> AddFront(T value) 
    { 
     return new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true)); 
    } 

    public LazyStack<T> AddRear(T value) 
    { 
     return this.IsEmpty 
      ? new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true)) 
      : new LazyStack<T>(this.Head, new Lazy<LazyStack<T>>(() => this.Tail.AddRear(value), true)); 
    } 
} 

이제 AddRear 기능은 분명 지금 O(1) 시간에 실행됩니다. Tail 속성에 액세스하면 헤드 노드를 반환하는 데 충분한 의을 평가 한 다음 중지하므로 더 이상 모 놀리 식 기능이 아닙니다.

Answer 4

게으른 평가는 순전히 기능적인 프로그래밍 언어의 '성능 회복'이라는 공통적 인 속성이며 아주 간단하게 작동합니다. 필요할 때만 표현식을 평가할 수 있습니다. x가 참으로 하스켈에서, 다른, 두에 X + 2이면, x + 3 평가 및 반환 같은 경우 예를 들어, 엄격한 (열망) 평가에서

if x == 1 then x + 3 else x + 2 

하스켈

고려, 그런 일이 일어나지 않는다, X + 3 단지 예를 들어, 표현에게로 구성되어, 내가 가진 말 :

let x = if x == 1 then x + 3 else x + 2 

그럼 내가 저장이 나는 결코 이제까지 이제까지 이제까지 인해 다른 조건문에이 변수를 사용하여 변수에,하지만 경우 흠? 내 CPU에 매우 비싼 정수를 낭비했다. (좋아, 실제로 당신이 이길 수는 없지만 더 큰 표현으로 아이디어를 얻는다.)

그런 다음 질문을하자. 왜 모두 게으른 언어인가?, 음, 간단한 이유는 순전히 표현식은 부작용이 전혀 없음을 보장합니다. 그들이 가지고 있었다면, 우리는 올바른 순서로 그들을 평가해야 할 것입니다. 그래서 대부분의 언어에서 열심히 평가됩니다. 표현에 부작용이없는 언어에서는 게으른 평가에 위험이 없으므로 다른 지역에서 잃는 경향이있는 실적을 되 살리는 것이 합리적입니다.

흥미로운 또 다른 부작용은 하스켈의 if-then-else가 실제로 Bool -> a -> a -> a 유형의 함수라는 것입니다. Haskell에서 이는 부울 유형의 인수 하나를 취하고 다른 유형의 다른 유형은 첫 번째 유형과 동일한 유형의 인수를 취하고 해당 유형을 다시 리턴한다는 것을 의미합니다. 값이 필요할 때만 평가되기 때문에 값이 계산되기 때문에 프로그램의 끝 부분에있는 대용량 표현식이 작성된 후 값이 평가되고 최종 결과에 대해 평가되고 버려지기 때문에 값이 계산되므로 다른 제어 분기의 무한한 평가를 수행하지 않습니다 컴파일러가 최종 결과에 필요하지 않다고 생각하는 모든 것. 예를 들어, 아주 복잡한 표현식을 그 자체로 나눌 경우 두 부분을 모두 평가하지 않고 '1'을 대치 할 수 있습니다. 일부 구문은 말을하지만

의 차이는 전통적으로 엄격하게 평가 계획에 표시되지만 if이 기능하지 않기 때문에 오류가 계획 (display (apply if (> x y) "x is larger than y" "x is not larger than y"))에 게으른 계획이라고 게으른 변종이있다, 그것은 전문 구문 (의 Scheme에서 특별한 것은 아닙니다.) 모든 인수를 반드시 평가할 필요는 없으므로, 예를 들어 팩토리얼을 계산하려고하면 메모리가 부족합니다. Lazy Scheme에서는 함수가 디스플레이와 같이 계속해서 평가를 위해 결과를 필요로 할 때까지는 아무 것도 평가되지 않으므로 잘 작동합니다.