lazy evaluation

도입

lazy evaluation 개념자체는 어렵지 않습니다. 그래서 이번엔 활용성 측면 위주로 설명드리도록 하겠습니다~

배경 지식

여태 expression과 evaluation이 헷갈리시다면 아래 글을 참조하시면 좋을 것 같습니다.

https://jurogrammer.tistory.com/129

정의

evaluation 전략 중 하나로 expression의 value가 필요할 때까지 evaluation을 미루는 전략이라고 보시면 됩니다.

보통 성능 개선을 목적으로 lazy evaluation을 사용하지요.

어떻게 evaluation을 미룬 어떻게 성능을 개선할 수 있는지 한 번 살펴보겠습니다.

성능 개선의 예시

특정 조건을 만족해야만 해당 value를 사용하는 예시입니다.

import time

def cpuBoundJop():
    print("hard job start")
    time.sleep(3)
    print("hard job end")
    return "hard!"

def businessLogic(n, value):
    if n > 0:
        print("The value is {}".format(value))
    else:
        print("invalid")

businessLogic(1, cpuBoundJop())

보면요, n이 양수일 때만 cpuBoundJop의 value를 사용합니다. 그런데 음수일 때도 cpuBoundJop이 실행이 되죠. 따라서 businessLogic을 실행하는데 n이 어떤 값이든지 3초의 시간이 필요합니다.

음수일 땐 필요없는 연산인데 불구하고 말이죵... 이를 lazy evaluation으로 개선해보겠습니다.

어떻게 Lazy를 구현할까? (Simulating laziness in eager languages)

우선 어떻게 lazy evaluation을 구현할 지 말씀드리겠습니다. 하스켈은 Default가 lazy evaluation인 반면, 대부분의 언어는 eager evaluation이라고 보시면 됩니다.

eager evaluation 언어에서는 함수 형태로 넘겨주면 lazy evaluation을 구현할 수 있습니다. 함수를 call한 시점에 평가되니, 평가 시점을 선택할 수 있습니다.

개선

import time

def cpuBoundJop():
    print("hard job start")
    time.sleep(3)
    print("hard job end")
    return "hard!"

def businessLogic(n, supplier):
    if n > 0:
        print("The value is {}".format(supplier()))
    else:
        print("invalid")

businessLogic(0, (lambda : cpuBoundJop()))

위처럼 n이 양수일 때만 함수를 호출하여 evaluation한다면! 음수일 때는 실행이 되지 않겠죠. 이렇게 늦출 수 있습니다.

한편으로, expression을 function의 반환 값으로 놓은 형태의 함수를 supplier라고 부릅니다.

또 하나로 성능 문제를 언급하기 위해 filter 예제를 들어볼게요. javascript, ruby, java에서 아래 문제를 구현해보고 몇 번이나 log가 찍히는지 확인해보겠습니다.

Filter 예제

• 1 ~ 10까지 자연수 중에서
• 3보다 크고
• 5의 배수인
• 첫번째 수를 구하라

자바스크립트

function isGreaterThan3(number) {
    console.log(`isGreaterThan3 ${number}`);
    return number > 3;
}

function isMultipleOf5(number) {
    console.log(`isMultipleOf5 ${number}`);
    return number % 5 === 0;
}

let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
value = numbers
    .filter(isGreaterThan3)
    .filter(isMultipleOf5)
    [0]

console.log(value)

이것을 실행하면 몇 번 console.log가 호출될까요? 마지막 value를 확인하는 console.log를 제외하구용

정답은 총 17번입니다.

1. 1~10을 isGreaterThan3로 평가한 다음, (10번)
2. 참인 4~10 array가 반환됩니다.
3. 4~10을 isMultipleOf5로 평가한 것이죠 (7번)

루비

def is_greater_than_3? (number)
  puts "is_greater_than_3? #{number}"
  number > 3
end

def is_multiple_of_5? (number)
  puts "is_multiple_of_5? #{number}"
  number%5 == 0
end

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

value = numbers.filter { |number| is_greater_than_3? number }
               .filter { |number| is_multiple_of_5? number }
               .first

puts value

루비에선 어떨까요? 실행해보면 아시겠지만 루비도 17번입니다.

출력 결과

is_greater_than_3? 1
is_greater_than_3? 2
is_greater_than_3? 3
is_greater_than_3? 4
is_greater_than_3? 5
is_greater_than_3? 6
is_greater_than_3? 7
is_greater_than_3? 8
is_greater_than_3? 9
is_greater_than_3? 10
is_multiple_of_5? 4
is_multiple_of_5? 5
is_multiple_of_5? 6
is_multiple_of_5? 7
is_multiple_of_5? 8
is_multiple_of_5? 9
is_multiple_of_5? 10

자바

public class App {
    static Predicate<Integer> isGreaterThan3 = number -> {
        System.out.println("isGraterThan3 " + number);
        return number > 3;
    };

    static Predicate<Integer> isMultipleOf5 = number -> {
        System.out.println("isMultipleOf5 " + number);
        return number % 5 == 0;
    };

    public static void main(String[] args) {
        List<Integer> numbers = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

        Optional<Integer> first = numbers.stream()
                .filter(isGreaterThan3)
                .filter(isMultipleOf5)
                .findFirst();

        System.out.println(first.get());
    }
}

그렇다면 자바에서도 17번 print가 찍힐까요?

아닙니다! 자바에서는 신기하게도 7번입니다! 생각해보면 어차피 첫번째 값만 가져올건데 1~10모두를 평가할 필요는 없잖아요? 실제로 값을 필요로 하는 마지막 시점에서 평가를 시작하면 됩니다. 여기선 findFirst가 마지막에 해당되겠죠. java는 lazy evaluation을 구현했습니다; 구현하면 제대로 구현하네요... 교수님 같습니다.

oracle java tutorial의 stream쪽을 보시면 filter와 같은 operation을 intermediate operation, findFirst같은 operation은 terminal operation이라 합니다. 계산은 terminal operation에서 수행되는 것이죠.

출력 결과

isGraterThan3 1
isGraterThan3 2
isGraterThan3 3
isGraterThan3 4
isMultipleOf5 4
isGraterThan3 5
isMultipleOf5 5

출력 결과도 자바스크립트와 루비랑은 다르죠? 자바스크립트와 루비는 3보다 큰지가 쭉 나오고 5의 배수인지가 쭉 나왔는데 여기선 각 값에 대해서 3보다 큰지 5보다 큰지 판단하네요.!

아마... 제 생각엔? supplier를 담은 stream이 생성되고 마지막에서 supplier를 실행하기 때문에 위와 같이 출력되는 것이 아닌가 싶네요.

또 다른 활용성 Infinite Stream

위 예제에서 1 ~ 10까지 자연수를 담은 컬렉션을 미리 선언하고 작업했잖아요?

만약에 모든 자연수라고 한다면? 모든 자연수를 numbers에 담을 건가요?! 메모리 터져버리잖아요~

굳이 1~10을 선언할 필요없이 자연수란 개념을 나타낼 수 있는 무언가를 선언한 뒤에 그 것으로부터 필요한 값만 그때그때 받아오면 되지 않을까요?

이를 자바스크립트와 자바에서 구현해보겠습니다.

예시

javascript yield

yield?
https://en.wikipedia.org/wiki/Value_(mathematics)
https://en.wikipedia.org/wiki/Yield_(multithreading)

자바스크립트에서는 yield를 이용하여 구현할 수 있습니다. 전 yield라는 키워드가 와닿지 않았는데, 위 reference 2개를 참조하시면 꽤 와닿으실꺼라 생각합니다.

첫번째는 반환하는 의미를 나타낼 때 yield를 쓸 수 있다는 것, 그리고 멀티 스레딩 환경에서 쓰레드를 반환할 때 yield라는 system call이 사용될 수 있다는 점이죠.

function* naturalNumbers() {
    let number = 0;

    while(true) {
        number += 1;
        yield number;
    }
}

let stream = naturalNumbers();

stream.next().value

위처럼 1씩 더하는 무한 루프를 만들고 yield로 number를 반환해준다면 자연수라는 infinite stream을 만들 수 있습니다!

java

java에서는 iterate라는 api를 제공해줍니다. 조건제시법처럼 작성해주면 됩니다.

public class App {
    static Predicate<Integer> isGreaterThan3 = number -> {
        System.out.println("isGraterThan3 " + number);
        return number > 3;
    };

    static Predicate<Integer> isMultipleOf5 = number -> {
        System.out.println("isMultipleOf5 " + number);
        return number % 5 == 0;
    };

    public static void main(String[] args) {
        Optional<Integer> first = Stream.iterate(0, i -> i + 1)
                .filter(isGreaterThan3)
                .filter(isMultipleOf5)
                .findFirst();

        System.out.println(first.get());
    }
}

Python range

파이썬에선 range가 위처럼 정의되어 있어요. 2.7버전까지는 range가 eager evaluation이였는데 3부터는 lazy evaluation으로 변경되었죠.

python 2.7

python 3.7

출력 결과가 다른게 보이시죠~

Avoidance of error conditions

length(2/0, 2)

lazy로 평가하면 값이 2가 나오고 eager로 평가하면 0으로 나눌 수 없다는 error를 던집니다. 2/0을 계산하고 안하고의 차이죠.
lazy evaluation의 결과가 어색하게 느껴질 수도 있지만 다음처럼 생각하면 또 이상하진 않습니다. collection의 size를 구할 때 어떤 값인지 알 필요는 없다!
collection에 1이든 1000이든 결국 한 원소니까요. 평가할 필요가 없다는거죠.

처음에 이게 어디다가 써먹을 지 몰랐는데요... java에서 테스트 코드를 작성하다가 뇌리를 팍! 쳤습니다.

public class LazyEvaluationTest {

    @Test
    @DisplayName("0으로 나누면 ArithmeticException을 던진다")
    void throwZeroException() {
        assertThrows(ArithmeticException.class, () -> divide(1, 0));
    }

    private static double divide(double a, double b) {
        return a / b;
    }
}

자바 테스트 코드인데요..

assertThrows의 첫번째 인자로는 예상되는 exception, 두번째 인자로는 에러를 던질 것이라 예상되는 expression을 supplier 형태로 전달해주면 됩니다.

왜 이런 형식으로 작성해야 하나 의문이였는데 error avoidance 때문이였습니다!

단순히 divide(1,0) 을 전달하면 assertThrows를 call하기도 전에 error가 발생할테니까요! 따라서 lazy evaluation 전략을 사용한 것이죠. 뭐 assertThrows내부는 다음처럼 유사하게 되있겠죠?

try {
  supplier.apply();
catch (Throwable e) {
  expectedException.isInstance(e)
}

후달달~ 충격입니당 ㅎㅎ;

마지막으로...

마지막으로 다음 문제를 지니고 있긴 합니다만 간단히 언급만하고 넘어가겠습니다.

1. memory문제

filter예제에서 filter를 실행하지 않고 평가를 지연한다는 뜻은 결국 filter함수를 기억해야 한다는 뜻이겠죠? 그래야만 나중가서 필터링을 하죠. 그렇다는 건 결국 메모리를 차지한다는 뜻이 됩니다. 그래서 잘못사용하면 메모리터질수도 있습니다 ㅜ

1. 동일 값 재평가 문제 (메모이제이션 이용)

functional programming에서는 사이드 이펙트를 없애기 때문에 input이 같다면 output도 동일하게 나옵니다. 그렇기 때문에 f(3)을 호출 했을 때 한 번 연산했다면 다음 f(3)에선 굳이 연산할 필요가 없는 것이죠. 이 최적화를 위해 memozation 기법을 사용합니다.