Functional Programming - Lazy Evaluation
Haskell에서 특이한 점은 lazy evaluation을 한다는 점입니다. scala등 다른 언어에서도 lazy evaluation을 지원하지만, Haskell은 strict로 만들지 않는 이상 모든 부분이 lazy evaluation을 한다는 점입니다.
Introduction
지금까지 우리는 evaluation이 Haskell expression에 대해 어떻게 이루어지는지 자세하게 다룬 적이 없었습니다. 사실 우리는 다음과 같은 단순한 방법으로 evaluation을 수행하였습니다.
- 불필요한 평가(unnecessary evaluation)을 피해라.
- 프로그램이 더 모듈화(modular) 될 수 있도록 하라.
- 무한(infinite) list에 대해 프로그램이 수행할 수 있도록 하라.
위에 따라 Haskell의 평가 기술(evaluation technique)은 게이른 평가(lazy evaluation)이며, 따라서 Haskell은 lazy functional language라고 말 할 수 있습니다.
Evaluating Expressions
기본적으로 expression은 더이상 단순하게 되지 않을 때까지 연속적으로 definition이 적용되는 식으로 평가되거나 줄어들게(reduced) 됩니다.
예를 들어 square n = n * n과 같이 definition되어 있을 경우, square(3 + 4) expression은 다음과 같은 연역(reduction)에 의해 평가됩니다.
square (3 + 4)
= square 7
= 7 * 7
= 49
하지만, 위와 같은 방법만 있는 것은 아닙니다. 다른 것을 보자면 다음과 같습니다.
square (3 + 4)
= (3 + 4) * (3 + 4)
= 7 * (3 + 4)
= 7 * 7
= 49
지금은 더하기(+)를 하기 전 square 를 적용하였지만, 결과는 같습니다. 실제로 위와 같이 평가 순서(evaluation orders)가 다를 경우 결과가 다를 수 있습니다. 하지만 haskell을 사용하는데 있어서 고려할 필요는 없습니다. 왜냐하면 다음과 같기 때문입니다.
FACT
In Haskell, two different (but terminating) ways of evaluating the same expression will always give the same final result.
Reduction Strategies
우리는 지금까지 두가지 reduction 방법을 보았습니다. 앞으로 점더 알아보겠습니다.
expression에 대한 평가를 하는 모든 단계에서 definition을 적용가능한 많은 subexpression이 있을 수 있습니다.
아래는 두가지 흔히 사용하는 전략으로 redex(reducible subexpression)결정하는 방법입니다.
- Innermost reduction: An innermost redex is always reduced
- Outermost reduction: An Outermost redex is always reduced
앞에서 본 것과 같이, 어떠한 전략을 사용하더라도 연역가능한(reducible) 결과를 준 다는 점은 같습니다. 그럼 어떻게 두가지 전략을 비교할 수 있을까요?
Termination
예를 보면서 설명을 이어가겠습니다. 여기 보면 다소 이상한 재귀함수가 정의(definition)되어 있습니다.
loop = tail loop
이와 동시에 fst (1, loop) expression을 앞서 배운 두가지 연역 전략(reduction strategies)을 이용하여 평가해보겠습니다.
Innermost reduction
fst (1, loop)
= fst (1, tail loop)
= fst (1, tail (tail loop))
= ...
위와 같이 Innermost reduction 전략은 종료되지 않습니다.(not terminate)
Outermost reduction
반면 Outermost reduction 전략을 이용하면 다음과 같이 해결됩니다.
fst (1, loop)
= 1
위의 경우 fst 가 먼저 평가되, 인자로 주어진 tuple의 첫번째 값인 1을 바로 돌려주게 됩니다.
Facts
이를 통해 다음과 같이 정리할 수 있습니다. * Innermost reduction 전략의 경우 종료에 실패(fails to terminate)할 경우 Outermost reduction은 결과를 돌려줄 수 도 있습니다. * 만일 주어진 expression에 대해 어떤 reduction sequence가 종료된다면, Outermost reduction 또한 같은 결과로 종료됩니다.
Number of reductions
-- Innermost
square (3 + 4)
= square 7
= 7 * 7
= 49
-- Outermost
square (3 + 4)
= (3 + 4) * (3 + 4)
= 7 * (3 + 4)
= 7 * 7
= 49
그럼 두가지 전략의 reduction 수를 비교하면 위와 같이 Outermost 경우가 비효율적(inefficient)입니다. 왜냐하면 square 를 reduce할 때 (3 + 4) 가 중복되기 때문입니다.
따라서, Outermost 방법은 Innermost 방법보다 더 많은 step을 요구 할 수 있습니다.
하지만, 위에서 본 것과 같이 Innermost Reduction 전략은 종료되지 않을 수 있습니다. 그럼 이를 해결할 수 있는 방법은 없을까요?
이런 문제는 평가 도중 expression의 공유(sharing)을 나타내는 pointer를 사용하여 해결 할 수 있습니다. 위의 예의 경우 다음과 같이 (3 + 4) 를 단순 복사하는 것이 아닌 뒤와 동일하다는 것을 나타내는 pointer로 표현합니다.
square (3 + 4)
= (. * .) (3 + 4) -- (. * .) is same with (3 + 4)
= (. * .) 7
= 49
이는 다음과 같이 새로운 reduction 전략입니다.
Lazy evaluation = Outermost reduction + sharing
또한, 다음과 같은 특성을 가집니다. * innermost reduction 전략에 비해 더 많은 step을 절대(never) 요구하지 않습니다. * Haskell은 Lazy Evaluation을 사용합니다.
Infinite lists
종료에 대한 이점뿐만 아니라, Lazy Evaluation을 사용할 경우 infinite list를 가지고 프로그램을 만들 수 있습니다.
다음과 같은 recursive definition을 고려해 봅시다.
ones :: [Int]
ones = 1 : ones
여기서 사용된 recursion을 풀면 다음과 같이 infinite list를 돌려주게 됩니다.
ones = 1 : ones
= 1 : 1 : ones
= 1 : 1 : 1 : ones
만일 이런 상황속에서 head ones expression을 평가하고자 innermost reduction과 lazy evaluation을 사용하는 경우를 생각해봅시다.
상상하는 것처럼 innermost reduction의 경우 종료되지 않을 것입니다. 하지만 lazy evaluation은 바로 해결이 가능하지요.
Lazy evaluation
우리는 통상 이런 slogan을 생각할 수 있습니다.
Using lazy evaluation, expressions are only evaluated as much as required to produce the final result.
아래와 같은 예를 통해서 말이죠.
ones = 1 : ones
잠재적으로 무한대인(potentially infinite) list에 대해 오직 필요한 만큼만 평가하게 됩니다. (1번만 말이죠.)
Modular programming
lazy evaluation을 통해 프로그램을 더욱 모듈화(modular)하게 해줍니다. 다음과 같이 infinite list에 대해 finite list를 돌려줍니다.
? take 5 ones
[1,1,1,1,1]
? take 5 [1..]
[1,1,1,1,1]
아래와 같이 주어진 data로부터 control부분을 나누기 때문입니다.
take 5 [1..]
------ -----
control data
lazy evaluation을 통해 data로 부터 control부분에 필요한 만큼만 평가하게 됩니다.
Example: generating primes
예를 통해 더 알아보겠습니다. 무한한 소수(prime numbers) list를 생성하는 절차는 다음과 같습니다.
- list 2,3,4,... 을 작성합니다.
- list 내 첫번째 값인 p를 prime으로 표시합니다.
- list 내 모든 p의 배수를 지웁니다.
- step 2로 돌아갑니다.
이 알고리즘은 굉장히 오래된 알고리즘으로 유명합니다. 이를 그림으로 보면 다음과 같습니다. 첫번째 줄부터 보면 됩니다.
이를 직접적으로 Haskell로 옮기면 다음과 같습니다.
primes :: [Int]
primes = sieve [2..]
sieve :: [Int] -> [Int]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
위의 결과는 infinite list를 돌려주게 됩니다. 하지만 앞서 배운 모듈화(modular)를 통해 경계 조건(boundary condition)을 부여하여 finite list를 얻을 수 있습니다.
-- Selecting the first 10 primes:
? take 10 primes
[2,3,5,7,11,13,17,19,23,29]
-- Selecting the primes less then 15:
? takeWhile (<15) primes
[2,3,5,7,11,13]
이 경우 필요한 값만 계산하기 때문에 Lazy evaluation이 효율적인 것을 확인 할 수 있습니다.