지연 평가로 실행 늦추기 (1)

표현식 평가

 

즉시 평가

대부분의 명령형 언어에서 사용되고 코드를 바로 실행한다.

 

int i = (x + (y * z));

 

직관적이다. y * z를 먼저 계산하고 그 결과를 x에 더한다.

 

int OuterFormula(int x, int yz) { return x + yz; }
int InnerFormula(int y, int z) { return y * z; }

int result = OuterFormula(x, InnerFormula(y, z));

 

함수로 작성하면 위와 같다. OuterFormula 호출 시, InnerFormula가 호출되어 결과값을 반환하여 인자로 넘겨준다.

 

 

지연 평가

int OuterFormulaNonStrict(int x, int y, int z, std::function<int(int, int)> yzFunc)
{
    return x + yzFunc(y, z);
}
int InnerFormula(int y, int z) { return y * z; }

int result = OuterFormulaNonStrict(x, y, z, InnerFormula);

 

InnerFormula 함수를 함수 객체로 넘겨서 코드의 실행 순서를 바꾼다. + 연산자를 먼저 처리하고 (y * z)는 나중에(지연) 처리된다.

인자로 넘겨진 함수 객체는 호출되기 전까지 실행을 지연하므로 결과적으로 실행 순서가 변경된다.

 

코드의 실행 순서

 

 

 

 

지연 평가에 필요한 기술

 

처리 흐름 늦추기

template<class T>
class Delay {
public:
    Delay(std::function<T()> func) : m_func(func) {}
    T fetch() { return m_func(); }
private:
    std::function<T()> m_func;
};

 

생성자의 매개변수로 함수를 받는다. 해당 함수는 fetch가 호출되지 않는 한 실행되지 않는다. (인스턴스 생성X)

 

Delay<int> multiply([a, b]() { ... });
Delay<int> division([a, b]() { ... });

int c = multiply.fetch();
int d = division.fetch();

 

multiply와 division 인스턴스가 생성될 때, 생성자에 넘겨준 람다 표현식은 인스턴스 생성 시점에 같이 인스턴스화 되지 않고 명시적인 호출 시점에 인스턴스화 되면서 호출이 이루어진다.

 

 

메모이제이션으로 값 캐싱

함수 호출 결과를 저장해 두었다가 동일한 입력이 발생하면 저장된 결과를 반환해준다.

 

template<class T>
class Memoization
{
public:
    Memoization(std::function<T()> func)
        : m_func(func), m_subRoutine(&forceSubroutine), m_recordedFunc(T()) {}
    T fetch() { return m_subRoutine(this); }

private:
    std::function<T const& (Memoization*)> m_subRoutine; // fetch에 의해 호출되는 함수 객체
    std::function<T()> m_func; // 연산이 담길 함수 객체
    mutable T m_recordedFunc; // 값 저장 변수

    static T const& forceSubroutine(Memoization* d) { return d->doRecording(); }
    static T const& fetchSubroutine(Memoization* d) { return d->fetchRecording(); }

    T const& fetchRecording() { return m_recordedFunc; } // 저장된 값 반환
    T const& doRecording() {
        m_recordedFunc = m_func(); // 연산 값 저장
        // forceSubroutine=>doRecording으로 호출되던것을 forceSubroutine=>fetchRecording으로 변경
        // doRecording은 이후 호출되지 않는다.
        m_subRoutine = &fetchSubroutine;
        return fetchRecording();
    }
};

int a = 10;
int b = 5;
int multiplexer = 0;
Memoization<int> multiply_impure([&]() { return multiplexer * a * b; } );

for (int i = 0; i < 5; ++i) {
    ++multiplexer;
    std::cout << multiply_impure.fetch() << '\n';
}

 

외부 값을 참조 캡처하여 그 연산 결과를 반환하는 함수를 생성자에 넘겨준다.

반복문 내에서 multiplexer의 값이 변하기 때문에 본래라면 fetch를 호출할 때마다 다른 값이 반환되어야 한다.

하지만 fetch가 최초로 호출 될 때만 연산 및 그 결과값을 객체에 저장하고, 그 뒤에 fetch에서 호출하는 함수가 바뀌기 때문에 이후 호출되는 fetch는 저장된 값만을 동일하게 반환받는다.

 

메모이제이션을 사용할 때, 비순수 함수는 부작용이 발생할 수 있으므로 반드시 배제시켜야 한다.

결과값을 재사용 하기 때문에 최적화가 이루어진다.

 

덧붙여서 메모이제이션 수행 시 데이터가 한번 변하기 때문에 불변 객체가 아니라고 생각할 수도 있지만 외부에서 바라봤을때는 불변으로 보이기 때문에 불변 객체로 볼 수 있다.

 

 

메모이제이션으로 코드 최적화

동일한 인수를 가지고 같은 함수가 여러번 호출되었을 때, 만약 함수 내의 연산량이 많고 복잡하다면 그 연산들을 항상 수행하는 것은 성능적인 면에서 비효율적이다.

하지만 위에서 작성한 코드처럼 결과값을 캐싱해서 가지고 있는다면 성능의 최적화를 이룰 수 있다.