 | |
|
난이도 : 고급 Jonathan Bartlett, Director of Technology, New Medio
2008 년 2 월 19 일 Lazy 프로그래밍은 결과가 필요할 때까지 함수 또는 요청의 처리를 지연시키는 개념입니다. 이러한 개념은 많은 곳에 적용할 수 있습니다. Lazy 프로그래밍 관점에서 생각하면 불필요한 연산 코드를 제거할 수 있고, 문제 지향적인 프로그램으로 재구현 할 수 있습니다.
Scheme 속의 간단한 Lazy 프로그래밍
Lazy 프로그래밍은 결과 값이 필요하기 전까지 코드의 계산을 지연시킬 수 있는 기술이다. 예를 들어, Scheme에서 Lazy 프로그래밍은 두 개의 특별한 구조를 통해 지원된다. Scheme의 delay 특수 폼은 한 블록의 코드를 취하고, 이를 실행하기 보다는 코드와 매개변수를 promise로서 저장한다. 이 promise가 값을 만들어 내도록 한다면(force), 이것이 코드를 실행한다. promise는 결과를 저장하고, 향후에 요청이 있으면 코드를 다시 실행할 필요 없이 즉각적으로 리턴될 수 있도록 한다.
다음은 delay와 force가 함께 사용되는 방법 예시이다:
Listing 1. delay와 force 사용 예제
;;The multiplication is saved but not executed
(define my-promise (delay (* 5 6 7 8 9)))
;;Again, saved but not executed
(define another-promise (delay (sqrt 9)))
;;Forces the multiplication to execute. Saves and returns the value
(display (force my-promise))
(newline)
;;This time, the multiplication doesn't have to execute. It just returns
;;the value that was previously saved.
(display (force my-promise))
(newline)
;;This produces an error, because the promise must be forced to be used
(display (+ my-promise (force another-promise)))
|
이러한 구조들은 사용하기에 매우 단순하지만, 과연 어디에 사용될 수 있을까? 일반적으로, Lazy 프로그래밍은 하나의 함수가 호출 프로그램에 의해 사용되지 않는 값을 생성할 때 사용된다. 예를 들어, 넘버 리스트의 평균, 편차, 표준 편향을 계산했던 함수가 있다고 해보자. 다음은 이를 처리하는 한 가지 방법이다:
Listing 2. 간단한 통계 계산
(define (square x) (* x x))
(define (calculate-statistics the-series)
(let* (
(size (length the-series))
(sum (apply + the-series))
(mean (/ sum size))
;variance is the sum of (x[i] - mean)^2 for all list values
(variance
(let* (
(variance-list (map (lambda (x) (square (- x mean))) the-series)))
(/ (apply + variance-list) size)))
(standard-deviation (sqrt variance)))
(vector mean variance standard-deviation)))
;Run the program
(display (calculate-statistics '(2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)))
(newline)
|
특정 조건 하에서만 표준 편향 계산이 필요하지만, 이 함수는 이것을 계산하는데 이미 너무 많은 전산을 소비했다. 이를 해결할 수 있는 여러 방법들이 있다. 평균, 편차, 표준 편향을 계산하는 개별 함수를 가질 수 있다. 하지만 이 경우, 각 함수는 평균을 계산하는 작업을 다시 해야 한다. 이 세 개가 모두 필요하다면, 평균을 세 번, 편차를 두 번, 표준 편향을 한 번 계산해야 한다. 이것은 너무나 쓸모 없는 작업이다. 이제, 평균이 표준 편향 함수로 전달되어야 하고, 사용자가 평균-계산 함수를 호출하도록 해야 한다. 가능하기는 하지만, 이것은 모든 종류의 구현 스팩 조각들을 반영하는 인터페이스를 가진 진정으로 끔찍한 API를 만들게 될 것이다.
더 나은 방법은 전산을 지연하는 Lazy 계산법을 사용하는 것이다:
Listing 3. Lazy 계산을 사용한 통계 계산
(define (square x) (* x x))
(define (calculate-statistics the-series)
(let* (
(size (delay (length the-series)))
(mean (delay (/ (apply + the-series) (force size))))
;variance is the sum of (x[i] - mean)^2
(variance
(delay
(let* (
(variance-list (map (lambda (x) (square (- x (force mean))))
the-series)))
(/ (apply + variance-list) (force size)))))
(standard-deviation (delay (sqrt (force variance)))))
(vector mean variance standard-deviation)))
;Run the program
(define stats (calculate-statistics '(2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)))
(define mean (force (vector-ref stats 0)))
(define variance (force (vector-ref stats 1)))
(define stddev (force (vector-ref stats 2)))
(display (list mean variance stddev))
(newline)
|
calculate-statistics 버전에서, 값이 필요하기 전까지는 어떤 것도 발생하지 않고, 더 중요한 것은 어떤 것도 한 번 이상은 계산되지 않았다. 편차를 먼저 요청하면, 평균을 실행하고 저장한 다음, 편차를 실행 및 저장한다. 다음에 평균을 요청하면, 이미 평균이 계산된 상태이기 때문에 간단히 값을 리턴한다. 다음에 표준 편향을 요청하면, 편차를 위해 저장된 값을 사용하고, 여기에서부터 이것을 계산한다. 어떤 불필요한 전산도 수행되지 않고, 함수 인터페이스가 보유된다.
이러한 유형의 게으름(laziness)은 객체 지향 언어에서도 똑같이 수행될 수 있다. 계산이 필요한 어느 곳에서나, 중간 값을 갖고 있는 클래스를 만들 수 있다. 컨스트럭터는 초기 값을 취하고, 계산된 값은 무효로 설정된다. force를 사용하는 대신, 값이 무효인지를 검사하여, 무효가 아닐 경우 계산을 실행하도록 각 값에 getter를 갖게 된다. 다음은 자바™ 언어에 적용된 클래스 골격이다:
Listing 4. 자바 언어에 적용한 Lazy 계산
public class StatisticsCalculator {
private List the_series;
private Double mean;
private Integer size;
private Double variance;
private Double standard_deviation;
public StatisticsCalculator(List l)
{
the_series = l;
}
public int getSize()
{
if(size == null)
{
size = the_series.size();
}
return size;
}
public double getStandardDeviation()
{
if(stddev == null)
{
stddev = Math.sqrt(getVariance());
}
return stddev;
}
...
...
}
|
클래스 자체는 다중 값을 지닌 promise로 작동하고, 인스턴스 변수들은 계산의 결과를 갖고 있다. 각 함수는 변수가 무효인지 여부를 검사함으로써, 코드가 실행되었는지 여부를 검사한다. 변수가 값을 갖고 있지 않으면, 코드가 실행되고 값이 저장된다. null이 유효 범위의 값에 있다면, 값이 무효인지를 검사하는 것이 아닌, 코드가 실행 되었는지 여부에 사용할 수 있는 보조 플래그가 필요하다.
여러분도 보듯, Lazy 프로그래밍 기술은 상호 의존적인 값을 리턴하는 함수를 위해 합리적이고 효율적인 API를 만드는데 사용될 수 있다. 또한, Lazy 기술은 Lazy 프로그래밍에 대한 직접적인 지원을 갖고 있지 않은 언어에 있는 클래스를 통해 구현될 수 있다.
중간 리스트
5의 배수가 되는 수의 리스트가 있다고 가정해 보자. 이 모든 숫자들을 계산하고 싶다. 결과를 반복하고, 이 모든 결과 중에서 500 보다 작은 값을 디스플레이 하고 한다. 무한 리스트에 대해서는 계산할 수 없을까? 당연히 된다.
무한 리스트가 생성 규칙(generative rule)에 기반하고 있는 경우, 무한 리스트는 많은 유한 리스트를 저장할 수 있는 여유가 없다. 위 예제에서, 원래 리스트는 X[i] = (i + 1) * 5 규칙에 기반하고 있는데, X[i]는 리스트 인덱스 i에 있는 값이다. X[i] 역시 이것의 선임자인 X[i] = X[i-1] + 5; X[0] = 5의 관점에서 수식될 수 있다. Scheme의 force와 delay를 사용하여, 이러한 규칙에 기반한 값의 스트림(stream)을 만들 수 있다:
Listing 5. 스트림 예제
;This is the generative rule for the list. It returns a pair
;with the car being the next value, and the cdr being a promise
;for the next pair
(define (my-generative-rule last-val)
(let (
;generative formula based on previous value
(next-val (+ last-val 5)))
;put the next value together with a promise for another one
(cons next-val (delay (my-generative-rule next-val)))))
;Since the cdr is a promise of a pair, rather than a pair itself,
;we have our own functions for getting the car and cdr.
(define (mystream-car the-stream) (car the-stream))
(define (mystream-cdr the-stream) (force (cdr the-stream)))
;Create our list
(define multiples-of-five (cons 5 (delay (my-generative-rule 5))))
;Display the fourth element of the list
(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr multiples-of-five)))))
(newline)
|
이제, 여러분이 모든 수들을 계산해야 한다. 이렇게 하기 위해서는, 기존 스트림에서 새로운 스트림과 생성 규칙(예를 들어, map 같은)를 만들 수 있는 함수가 필요하다. 다음은 그 함수이다:
Listing 6. 특화된 스트림 맵
(define (mystream-map function the-stream)
(cons
;;The first value will be the function applied to the car
(function (car the-stream))
;;The remaining values will be stored in a promise
(delay (mystream-map function (mystream-cdr the-stream)))))
(define squared-stream (mystream-map (lambda (x) (* x x)) multiples-of-five))
;Display the fourth element of this new list
(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr squared-stream)))))
(newline)
|
이제는 스트림을 반목하고 500 미만의 값을 프린트하는 일만 남았다:
Listing 7. 스트림 반복하기
(let loop (
(remaining-stream squared-stream))
(if (>= (mystream-car remaining-stream) 500)
#f
(begin
(display (mystream-car remaining-stream))
(newline)
(loop (mystream-cdr remaining-stream)))))
|
확실히, 이와 같은 간단한 프로그램에는, 주제에 보다 직접적으로 접근하는 방법들이 있다. 하지만, 이 예제에서도, 스트림을 통해서, 구현 관점 보다는 추상적인 개념의 관점에서 문제를 볼 수 있다. 스트림은 구현(implementation) 보다는 문제(problem)에 집중하게 한다. 스트림은 생성 엘리먼트를 포함하고 있는 알고리즘의 개념화와 구현 모두를 용이하게 한다.
지금까지 필자가 설명했던 스트림은 스트림 배후에 있는 개념을 배우는데 유용하다. 하지만, 구현은 수 많은 함정에 노출되어 있다. 먼저, 스트림이 터미네이터(terminator)를 필요로 할 수 있는 많은 상황들이 있다. 이 구현은 이 같은 장치를 제공하지 않는다. 또한, 여기에 나타난 스트림의 스타일은 odd streams으로 알려져 있고, odd 스트림은 구현하기가 쉽다. 이 리스트에 있는 car는 언제나 계산되므로, 이 같은 스트림은 의도했던 것 보다 더 많이 계산을 한다. SRFI-40에 정의된 것처럼, 표준 스트림은 이것은 물론 다른 문제들 까지도 다루고 있다. (참고자료)
전통적인 변수 건너뛰기
지금까지, Lazy 계산의 모든 예제들은 중간 값들이 계속 진행되기 전에 완벽히 실행되도록 한다. 일부는 우리가 풀고 있는 문제들에 대한 요구 사항에서 나오고, 일부는 delay와 force의 연산을 통해 나온다. 예를 들어, 다음 코드를 생각해 보자:
(define val1 20)
(define val2 30)
(define val3 40)
(define val4 0)
(define val5 (delay (* val1 val2)))
(define val6 (delay (* val4 val3)))
(define val7 (* (force val5) (force val6)))
이 경우, 어떤 것을 0에 곱하면 모두 0이 된다는 것을 알고 있으므로, 해답은 0이라는 것을 알 수 있다. 따라서, 이것은 Lazy 계산을 적용하기에 알맞은 상황인 것처럼 보이지만, 사실 delay와 force를 사용해도 도움이 되지 않는다.
이와 같은 경우, 중간 결과를 처리하지 않도록 프로세싱을 지연시키는 특별한 Lazy 알고리즘이 필요하다. 대신, 요청을 대기시키는 코드를 구현해야 한다. 그리고 나서, 마지막 대답이 요청되었을 때, 프로세스를 최적화 할 수 있는 값을 위해 큐를 검색하고, 그 값을 사용하여 다른 값에 대한 프로세싱을 건너뛴다. 곱셈의 경우, 0이 있으면, 모든 프로세싱을 건너뛸 수 있다.
다음은 곱셈을 위해 특화된 delay/force 쌍이다.
Listing 8. 특화된 delay/force 쌍
;This will simply use a list to keep track of the values to be multiplied
(define (multiply-delay x y)
(let (
;convert to lists if they aren't already
(x-list (if (list? x) x (list x)))
(y-list (if (list? y) y (list y))))
;append them together
(append x-list y-list)))
(define (multiply-force mul-list)
(let (
(has-zero? #f))
(for-each
(lambda (x)
(if (eqv? 0 x)
(set! has-zero? #f)
#f))
mul-list)
(if has-zero?
0
(apply * mul-list))))
(define a (multiply-delay 23 54))
(define b (multiply-delay 0 5))
(define c (multiply-delay a b))
(define d (multiply-delay c 55)
(display (multiply-force d))
(newline)
|
하지만, 이 구현 역시도 문제가 있다. 개별 조각들은 더 이상 게으르지 않으며, 값도 더 이상 저장하지 않는다. 하나의 최적화를 이루기 위해 원래의 delay와 force의 모든 혜택을 잃었다. 따라서, 모든 매개면수의 긴 리스트를 유지하는 대신, 개별 promise에 구분하여, 이전의 혜택을 여전히 누릴 수 있다. 우리에게 필요한 것은 값이 계산되었는지 여부를 말해주는 태그이다. 이러한 태그가 있다면, 계산을 필요로 하지 않는 단 한 개의 엘리먼트가 있을 것이다. 그렇지 않다면, 승수(multiplier)와 피승수(multiplicand) 모두 존재할 것이다. 다음은 새로운 코드이다:
Listing 9. 또 다른 Lazy 구조
;Unevaluated promises will have the structure ('delayed val1 val2)
;Evaluated promises will have the structure ('forced result)
;Create an unevaluated promise
(define (multiply-delay x y)
(list 'delayed x y))
;Checks promises (and values) to see if they contain any zeros
(define (has-zero promise)
(if (pair? promise)
(if (eq? (car promise) 'forced)
;check forced value
(if (eqv? (cdr promise) 0)
#t
#f)
;check unforced value
(if (or (has-zero (cadr promise)) (has-zero (caddr promise)))
#t
#f))
;Check scalar value
(if (eqv? promise 0)
#t
#f)))
;Attempts zero optimization, then defaults to regular delay/force behavior
(define (multiply-force promise)
(if (eq? (car promise) 'forced)
;if we've already been forced, return the value
(cdr promise)
;otherwise, search for a zero
(if (has-zero promise)
(begin
(set-car! promise 'forced)
(set-cdr! promise 0)
0)
(multiply-force-nonzero promise))))
;This is for promises which are known to be free of zeros
(define (multiply-force-nozero promise)
(if (pair? promise)
(if (eq? (car promise) 'forced)
;if the promise has been forced, just return the value
(cdr promise)
;otherwise, compute the value, and convert this into a "forced" promise
(begin
(set-car! promise 'forced)
(set-cdr! promise
(*
(multiply-force-nonzero (cadr promise))
(multiply-force-nonzero (caddr promise))))
;return the forced value
(cdr promise)))
;This is just a number, so return it
promise))
|
이것은 정식 delay/force의 모든 혜택을 누리고 있다. 이제, 곱셈이 매우 빠른 연산이 되었으므로, 전체 연산은 시간 낭비이지만, 좋은 예제가 된다. 이는 보다 복잡한 연산에는 많은 시간을 절약하고, 특히 정황 전환이나 많은 프로세서 사용이 필요한 연산의 경우 더욱 도움이 된다.
이러한 기술은 스트링 추가를 수행하는데 많이 사용되고 있다. 추가를 수행할 때마다 새로운 공간을 할당하는 대신, 연관시켜야 하는 스트링 리스트를 관리할 수 있다. 마지막 스트링 버전이 필요하면, 새로운 스트링을 위한 공간을 한번 할당하기만 하면 된다. 이는 여러 malloc 호출을 절약할 뿐만 아니라 각 스트링을 복사하는 시간을 줄여준다.
게으른 계산
지금까지 비 Lazy언어의 Lazy 구조에 초점을 맞춰왔다. 하지만, Haskell 같은 일부 언어들은 정상적인 계산 프로세스의 일부로 Lazy 특성을 갖고 있다. 이를 Lazy 계산(lazy evaluation)이라고 한다. Lazy 계산의 어떤 매개변수도 필요하기 전까지는 계산되지 않는다. 이 프로그램은 끝에서 시작하여 거꾸로 실행된다. 리턴이 필요한 것이 무엇인지를 파악하고, 거꾸로 실행을 계속 진행하면서 어떤 값이 이에 필요한지를 결정한다. 기본적으로 모든 함수는 각 매개변수에 대한 promise와 함께 호출된다. 연산이 값을 필요로 하면, promise를 실행한다. 코드는 값이 필요할 때에만 실행되므로, 이것을 call-by-need라고 한다. 전통적인 프로그래밍 언어에서, 값은 promise 대신 전달되는데, 이를 call-by-value라고 한다.
Call-by-need 프로그래밍은 여러 장점들을 갖고 있다. 스트림이 자동으로 구현된다. 불필요한 값들은 절대로 계산되지 않는다. 하지만, Lazy 프로그램의 작동은 예견하기 힘들다. call-by-value 프로그램에서, 계산 순서는 예견 가능하기 때문에, 시간 또는 순서 기반 계산이 비교적 쉽다. 이는 monads 같은 특별한 구조가 확실한 순서를 가진 이벤트를 기술하기 위해 필요한 Lazy 언어에서는 훨씬 더 어렵다. 이 모든 것 역시 다른 언어들과의 인터페이싱을 더욱 어렵게 한다.
Haskell과 Clean을 포함하여 Lazy 프로그래밍을 기본적으로 수행하는 여러 언어들이 있다. Scheme, ML 등을 포함한 많은 언어들의 Lazy 버전들이 있다.
결론
가끔씩, 값이 필요하기 전까지 계산을 지연시킴으로써, 프로그램의 속도를 최적화 하거나, 프로그램을 더욱 지능적인 형태로 만들 수 있다. Lazy 프로그래밍 기술이 가치가 있지만, 폭넓게 실행되지 않고 있으며, 심지어 잘 알려져 있지 않다. 이 기술을 여러분의 기술 레파토리에 추가시키는 것은 어떨까?
참고자료 교육
제품 및 기술 얻기
-
SEK for Linux 주문하기, 두장의 DVD로 이루어진 최신 IBM 시험판 소프트웨어(리눅스용): DB2®, Lotus®, Rational®, Tivoli®,
WebSphere®.
-
IBM 시험판 소프트웨어, 디벨로퍼웍스에서 다운로드 하여 차기 리눅스 개발 프로젝트에 활용해보라.
토론
필자소개
기사에 대한 평가
|
| 이 문서 북마킹 하기
|
| |
