Review PL KWD (2) - 지연 계산

프로그래밍 언어를 이해하는데 중요한 키워드들이 여러 개 있습니다. 키워드를 중심으로
관련된 주제들을 모아서 살펴보는 글을 작성해 보려고 합니다.
소프트웨어 개발과 프로그래밍 언어에 관련된 이야기들을 키워드를 중심으로 풀어보는 시리즈입니다. 

두 번째 키워드는 지연계산(delayed evaluation 또는 lazy evaluation)이라고 하는 명령형 프로그램의 실행 순서와는 좀 다른 계산 순서의 개념을 살펴보겠습니다.

이것은 함수 호출 시 매개변수의 계산에 관련된 것으로 명령형 프로그램은 매개변수 부분에 있는 수식의 계산을 모두 끝낸 후 함수를 호출할 수 있습니다. 그것을 applicative order라고 부릅니다. 즉 test(f(g()))라는 코드가 있다면 g()를 먼저 계산하고 다음에 그 값으로 f()를 계산, 그 다음에 test를 계산하는 것입니다. 이것이 현재 대부분의 프로그래밍 언어에서 사용하는 방법입니다. 이것과 반대되는 개념은 normal order입니다. 이것은 만나는 순서대로 test를 먼저 계산하고 거기서 f가 필요하면 f를 계산하고 또 그 과정에서 g() 가 필요하면 계산합니다. 이 방법의 이름은 normal이지만 사실 우리가 사용하고 있는 컴퓨팅 환경에서는 매우 드문 경우라고 할 수 있습니다.그런데 lazy evaluation 방법에서는 그 수식을 그대로 넘겨서 함수에서 그 매개변수가 필요할 때 계산합니다. 즉 매개변수가 필요하지 않으면 아예 계산되지 않을 수도 있습니다. 예를 들어 다음 코드에서 f()의 결과가 5 이하면 g() 함수는 계산될 필요가 없습니다. 만약 g() 함수가 엄청나게 많은 계산을 요구하는 경우 이 코드는 불필요한 계산을 하게 될 것입니다.

void test(a, b) {
   if (a > 5)
	   return a + b;
   else
   	   return a;
}
void main() {
   test(f(), g());
}

지연 계산이 lazy evaluation이라고 하는 이유는 게으른 학생이 과제를 할 때처럼 컴파일러가 계산을 가능한 한 미루는 방식이기 때문입니다. 그렇게 되면 정말 필요한 경우에만 계산하므로 당연히 효율적이 됩니다. (게으른 학생들은 과제를 미리 시작해서 열심히 할 필요가 없다고 생각하죠? 마감까지 상황이 바뀔 수도 있고 과제가 바뀔 수도 있고 힌트가 더 나올 수도 있습니다. 마감이 다 되가면 집중력이 올라가고 좀더 효율적으로 과제가 된다라고 얘기하죠?) 학생이라면 공부한 것이 쓸데없어지는 일은 없겠지만(공부해서 남주냐?), 컴퓨터는 사실 불필요한 계산을 하는 것은 바람직한 일이 아닙니다.

이러한 계산의 좋은 예가 단축계산(short circuiting)이라고 알려진 조건식의 계산 방식입니다. 단축계산에서는 앞의 조건식에 의해 전체 식이 계산되면 뒤의 부분은 하지 않습니다. 불필요한 계산을 생략하는 거죠. 이것은 우리가 알고 있는 것과 같이 단순히 계산의 효율성이나 불필요한 계산을 하지 않는다는 것 이외에도 여러 가지 장점을 가집니다. 예외 상황을 미리 제외시켜 주고 조건부 계산을 하나의 식으로 나타낼 수 있다는 점 등으로 인해 가독성을 높혀 줍니다. 단축계산은 컴파일러에 하드코딩되어 있는 특수한 지연 계산의 예라고 할 수 있습니다.

이러한 수식의 계산 순서가 그렇게 중요한 개념이 되는 것이 잘 이해가 되지 않을 수 있습니다. 그러나 함수형 프로그래밍 언어에서는 이러한 함수의 조합과 호출에 의해 계산이 일어나게 되고 함수 호출이 복잡하게 얽히게 되는데, 이 때 계산의 순서를 lazy evaluation을 적용하면 계산 양을 크게 줄일 수 있고 결국 성능을 높일 수 있게 됩니다.

지연계산의 두 번째 장점으로 일반적인 계산 순서(applicative order)를 적용할 때 계산할 수 없는 무한한 리스트를 다룰 수 있게 됩니다. 그런 예로 다음과 같은 것을 들 수 있습니다. 

def addOne(n) = [n] + addOne(n + 1)

// [1, 2, 3, 4, 5, 6, ...]
list = addOne(1)


oneToThree = list.takeFirst(3)
print(oneToThree) // [1, 2, 3]

addOne 같은 함수는 만약 명령형 언어에서 list = addOne(1)이라고 쓴다면 무한히 계산을 수행해서 끝나지 않는 프로그램이 될 것입니다. 그러나 lazy evaluation을 적용하는 경우 list는 그냥 실행가능한 코드로서 존재하게 되고 그것을 이용하는 시점(takeFirst(3)을 호출할 때)에 3개까지만 계산하게 된다는 것입니다. 이렇게 되면 무한 리스트를 정의한 후 그것을 언제든 필요할 때 가져다 쓸 수 있게 됩니다.

def range(start, end) =
    list.takeElementsBetween(start - 1, end - 1)
print(range(5, 10)) // [5, 6, 7, 8, 9]

lazy evaluation을 구현하기 위해서는 계산할 함수 또는 코드 부분이 언제 계산하든 결과가 동일해야 합니다. 또한 여러 번 계산되나 한번도 계산되지 않거나 코드의 다른 부분에는 영향을 미치지 않아야 합니다. 이것을 수식의 참조투명성(referential transparancy)이라고 합니다.

일반적으로 지연 계산 방식을 사용하는 함수형 언어(Haskell, Scheme, Scala 등)에서는 지정(assignment)를 최소화하고 수식이나 함수가 부수효과를 갖지 않아 이러한 참조투명성을 만족하게 언어를 설계하였습니다. 그러므로 프로그램이 디버깅하기 쉽고 수학적으로 수행 결과를 증명하는 것이 가능하게 될 수 있습니다. 이러한 점이 함수형 프로그래밍의 장점으로 알려져 있습니다. 또한 이것이 객체지향의 명령형 프로그래밍 언어에서 지연 계산을 도입하기 어려운 이유하고도 할 수 있습니다.

지연 계산의 구현은 일반적인 계산 방식에 비해 까다로운 문제를 해결해야 합니다. 문제는 어느 부분을 언제 계산할 것인지, 이미 계산되었던 것을 다시 계산하는 것을 어떻게 피할 수 있을지가 관건입니다. 즉 수식이 계산된 부분과 계산이 되지 않은 부분을 구별해서 실행엔진에서 처리할 수 있어야 합니다. (이미 계산된 것은 메모이제이션을 통해 기억해 두어야 합니다.) 코드의 어느 부분은 계산되었고 어느 부분은 아직 계산되지 않았는지 실행과정에서 계속 유지하고 추적해야 합니다.

한편 최근에는 이러한 함수형 프로그래밍 방식과 lazy evaluation이 명령형 또는 객체지향을 기반으로 하는 언어에도 도입되고 있는 추세입니다. 대표적인 예가 자바의 람다 및 스트림API를 이용한 스트림 체인 형태의 프로그래밍과 파이썬의 yeild와 제너레이터를 이용한 파이프라이닝입니다. 자바의 스트림과 람다 기능은 지연계산을 지원하기 위해 도입되었다고 볼 수 있습니다.

이러한 지연계산 방식은 성능의 향상과 무한한 계산을 가능하게 하는 장점 이외에도 기존의 프로그래밍 방식에 비해 간결하고 가독성이 우수한 코드로 가능하게 해 줍니다. 이에 대해서는 각 카테고리의 해당 글에서 다루려고 합니다.

https://medium.com/background-thread/what-is-lazy-evaluation-programming-word-of-the-day-8a6f4410053f

What is Lazy Evaluation? — Programming Word of the Day

https://www.youtube.com/watch?v=bSbCJUSaSkY