느긋한 계산법
| 평가 전략 | |
|---|---|
| 엄격 평가 | |
| 비엄격 평가 | |
| 비결정 방법 | |
| 기타 | |
컴퓨터 프로그래밍에서 느긋한 계산법(Lazy evaluation)은 계산의 결과값이 필요할 때까지 계산을 늦추는 기법이다. 두 가지 관련된 항목들이 있는데 지연 계산법과 최소 계산법이다.
느긋하게 계산하면 필요없는 계산을 하지 않으므로 실행을 더 빠르게 할 수 있고, 복합 수식을 계산할 때 오류 상태를 피할 수 있고, 무한 자료 구조를 쓸 수 있고, 미리 정의된 것을 이용하지 않고 보통 함수로 제어 구조를 정의할 수 있다.
느긋한 계산법을 사용하는 언어들은 "이름으로 호출"하거나 "필요할 때 호출"하는 계산 전략을 사용하는 것으로 나눌 수 있다. 하스켈과 같은 대부분의 실제 느긋한 언어들은 성능상의 이유로 "필요할 때 호출" 전략을 사용한다. 그러나 느긋한 계산법을 이론적으로 표현한 것들은 간편하게 "이름으로 호출"하기도 한다.
느긋한 계산법의 반대되는 계산법은 조급한 계산법이 있는데 엄격한 계산법이라고도 한다. 조급한 계산법은 대부분의 프로그래밍 언어가 동작하는 방식이다.
복합 수식[편집]
(a and b)와 같은 논리식을 계산한다고 하면 a항이 거짓인 경우에, b항을 계산하지 않아도 전체 식의 답을 알 수 있다. (a or b)에서 a항이 참인 경우에도 마찬가지이다. 여기서 항이 복잡한 식이면 이점이 많고, 식에서 결과가 참이나 거짓일 가능성과 계산의 비용에 따라 어떤 항이 먼저 계산되어야 좋은지 알 수 있다. 따라서 (a or b or c)와 같은 식에서 a항이 참값을 가질 가능성이 많다면, 전체 식을 쉽게 계산할 수 있다. 이런 가능성을 보장하기 위해, 컴파일러는 더 계산해야 할 것인지, 다른 항을 지름길 계산 해야 할 것인지를 검사하기도 한다. 이런 검사는 계산을 줄이는 것을 실패할 경우나 꼭 필요한 경우 무조건 전체 식을 계산해야 할 때 시간이 더 많이 걸리게 된다.
산술식을 계산할 때에도 유사한 접근 방식을 취할 수 있다. 어떤 수에 0을 더하는 것은 의미 없고, 0이나 1을 곱하는 경우에는 특별한 효과가 있다. 그러나 이런 특별한 값들을 검사하는 것은 논리값은 2개의 값을 가지는 데 비하여 수는 여러 가지 값을 가질 수 있기 때문에 큰 이득이 되지 못한다. 그러나 0이 소수점 값으로 변환하는 데 쓰이지 않는 이상 하드웨어가 특수한 경우는 잘 계산하고 있다.
오류 회피[편집]
특정한 상황에서는 계산되면 오류 상황이 되어 오류를 발생시키는 수식이 있다고 가정하자. 그 수식은 (계산해도 안전한 식 and 수식)과 같은 형태로 보호되어 있을 수도 있다. 예를 들면 (N <> 0 and (x mod N = 0)과 같은 형태이다. 분명히, 이것은 if N <> 0 then if x mod N = 0 then ...과 같은 형태로 쓸 수 있지만 깔끔하지 못하다. 반대로, (a or b)로 검사할 때, a가 참인 경우에 b는 계산될 필요가 없을뿐더러 문제를 일으킬 수도 있다. a와 b 둘 중 하나가 참인 경우에 어떤 행동을 하고 싶다면(이 식에서 의미하는 것이다!) 친절하게 if a then action else if b then action이라고 쓸 수 있지만, action을 반복해서 쓰기 때문에 실수를 할 가능성이 있다.
좀 더 구체적으로 살펴보자. 여기 공백이 뒤쪽에 있는 텍스트 문자열이 있고, 공백이 아닌 맨 마지막 문자의 위치를 알고 싶다고 할 때,
l:=Length(t); while l > 0 and t(l) = " " do decrement l;
라고 하거나, 좀 더 유연한 언어에서는
for l:=Length(t):1:-1 while t(l) = " " do;
라고 할 수 있다. 분명히, 문자열 전체가 공백으로 차 있다면 l은 0이 될 것이다. 그러나 문자열에서 0번째 문자열을 읽는 시도는 하지 않는다. 이것은 잘해야 쓸데 없는 노력이고, 못하면 오류를 일으킬 수도 있다.
지연 계산법[편집]
지연 계산법은 함수형 프로그래밍 언어에서 주로 사용한다. 지연 계산법을 사용하면 수식이 변수에 접근하는 순간 계산되는 것이 아니라, 강제로 계산값을 출력하라고 할 때까지 계산을 늦춘다. 말하자면, x:=수식;과 같은 구문이 있다고 하면, 분명히 수식을 계산하여 결과값을 x에 넣어야 한다. 하지만 x에 들어있는 값은 나중에 참조되어 그 값을 요구한다든지 할 때까지는 상관이 없다. 비록 다른 심볼보다 바깥 세상을 보고자 하는 몇 가지 심볼을 생성하기 위해 빠르게 자라는 의존성 나무의 가지를 칠 수 있다고 할지라도, 식의 계산을 뒤로 미룰 수 있다.
수식의 계산을 기본으로 늦추는 프로그래밍 언어도 있고 함수나 특별한 구문으로 계산을 늦추는 언어도 있다. 미란다와 하스켈은 기본으로 계산을 늦춘다. 다른 언어들은 특수한 구문을 써서 계산을 늦추라고 명시하거나 성크에 수식을 감싸서 계산을 늦춘다. 예를 들어 스킴에서는 "delay"와 "force"를 써서 이런 것을 명시할 수 있다.
지연 계산법은 계산할 때 무한 반복 문제나 크기 문제 없이 계산 가능한 끝없는 목록을 만들 수 있다. 예를 들어, 피보나치 수로 (보통 스트림이라고 부르는) 끝없는 목록을 만드는 함수를 작성할 수 있다. n번째 피보나치 수는 끝없는 목록의 원소를 추출하는 것만으로도 간단하게 계산할 수 있는데, 목록의 처음 n개의 수들만 계산하도록 하면서 할 수 있다.
예를 들어 하스켈에서는 모든 피보나치 수의 목록을 다음과 같이 쓸 수 있다.
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
하스켈의 구문 ":"는 목록에 원소를 첨가하는 것이고 tail은 첫 번째 원소를 빼고 리스트를 돌려주며, zipWith는 특정한 (여기서는 (+)) 함수를 사용하여 두 목록의 각 원소를 결합하여 세 번째 항목을 생성하도록 한다.
프로그래머가 주의한다면, 특정한 결과값을 생성할 때 필요한 값만 계산할 것이다. 그러나 특정 계산이 목록의 길이를 구하는 것이라든지, 목록의 원소들의 전체합을 구하는 것과 같이 프로그램에서 무한히 많은 원소를 계산하는 것이라면 계산을 끝내지 못하거나 메모리를 다 쓰게 될 것이다.
읽을거리[편집]
비교: