(번역) 왜 함수형 프로그래밍이 중요한가 — John Hughes 1989

이 글은 John Hughes의 글 “Why functional programming matters”를 번역한 것입니다. 84년 버전과 89/90년 버전 중 89/90년 버전 PDF를 기준으로 하였습니다. 번역 PDF는 인쇄에 더 적절합니다.

Copyright belongs to The British Computer Society, who grant permission to copy for educational purposes only without fee provided the copies are not made for direct commercial advantage and this BCS copyright notice appears.


John Hughes
The University, Glasgow

Abstract

소프트웨어가 점점 더 복잡해지면서 구조를 잘 잡는 일이 더욱 중요해졌다. 잘 구조화된 소프트웨어는 작성하기 쉽고, 디버깅하기도 쉬우며, 나중에 재사용을 통해 프로그래밍 비용을 줄여줄 모듈들도 제공한다. 이 페이퍼에서 우리는 함수형 언어의 두 기능, 고차 함수(higher-order function)와 지연 연산(lazy evaluation)이 모듈화 수준을 매우 높여준다는 점을 보여주려 한다. 예제로서 리스트와 트리 자료 구조를 다루고, 몇가지 수치 알고리즘을 구현해보고, 알파-베타 휴리스틱(게임에 사용되는 인공지능의 한 알고리즘)을 구현해본다. 모듈화 수준이 성공적인 프로그래밍에 매우 중요하기 때문에 함수형 프로그래밍이 소프트웨어 개발에 있어서 중요한 이점을 제공한다는 얘기로 끝을 맺는다.

1 도입

이 페이퍼는 (비 함수형) 프로그래머 커뮤니티에 함수형 프로그래밍의 중요성을 보여주고, 또 함수형 프로그래머들에게는 함수형 프로그래밍의 장점을 명확히 함으로써 그 장점을 충분히 활용할 수 있도록 돕기 위한 시도이다.

함수형 프로그래밍을 함수형 프로그래밍이라 부르는 이유는 가장 기본적인 동작 방식이 함수를 인자에 적용(혹은 호출, application)하는 것이기 때문이다. 메인 프로그램은 그 자체로 인자를 입력(input)받아 결과를 출력(output)하는 함수로 작성된다. 메인 함수는 다른 함수들을 이용하여 정의되는 것이 일반적이며 그 함수들은 다시 더 많은 함수들로 정의된다. 이 모든 함수들은 수학에서 다루는 보통의 함수와 매우 비슷하다. 이 페이퍼에서 함수들은 보통의 등식 형태로 정의된다. 우리는 Turner의 언어, Miranda[4]를 이용하지만 Miranda를 몰라도 표기법을 이해하는데 어려움은 없을 것이다.

함수형 프로그래밍이 가지는 특장점은 대개 다음과 같이 요약된다. 함수형 프로그램은 대입문(assignment statement)이 없고, 그래서 변수는 한번 값이 지정되면 절대 변경되지 않는다. 더 일반적으로 보자면 함수형 프로그램은 부작용(side-effect)이 전혀 없다. 함수 호출은 결과 값을 계산하는 이상의 다른 효과(effect)를 가지지 않는다. 이로써 버그의 주요 원인이 사라지고, 실행의 순서가 중요하지 않게 된다–표현식(expression)의 값을 변경할 수 있는 부작용이 없기 때문에 표현식은 아무 때나 평가될 수 있다. 이는 다시 프로그래머로 하여금 제어 흐름을 지정해야 하는 짐을 덜어주다. 표현식이 아무 때나 평가될 수 있으므로 변수를 원래의 값으로 치환하거나 거꾸로 치환하는 것이 자유롭게 된다–즉 프로그램이 “참조 투명성(referential transparency)”을 가지게 된다. 이러한 자유로 인해 함수형 프로그램은 기존 방식의 프로그램에 비해 수학적으로 더 쉽게 추적할 수 있다.

이런 “장점” 목록이 훌륭하기는 하지만 외부에서는 이 장점들을 그다지 심각하게 받아들이지 않는다는 걸 알아야 한다. 이는 함수형 프로그래밍이 아닌 것(대입문이 없고, 부작용이 없고, 제어 흐름이 없는 등)에 대해서는 이야기하지만 함수형 프로그래밍이 실제 어떤 것인가 하는 것은 별로 말해주지 않는다. 함수형 프로그래머는 마치 고결해지기 위해 금욕하는 중세 수도사처럼 들린다. 물질적 이득에 더 관심있는 이들에게 이러한 “장점”은 전혀 설득력을 가지지 못한다.

함수형 프로그래머들은 물질적 이득도 크다고 주장한다–함수형 프로그램이 훨씬 짧기 때문에 함수형 프로그래머가 몇 배나 생산성이 높다고 한다. 하지만 왜 꼭 그래야 할까? 누군가 이 “장점”들에 기반하여 근거를 대려면 기존의 프로그램들이 90%는 대입문으로 작성되고 함수형 프로그램에서는 이 대입문들이 모두 제거될 수 있다고 해야 그나마 말이 될 것이다. 이건 한마디로 터무니 없다. 대입문을 없애는 것만으로 그 정도의 이득이 생긴다면 FORTRAN 프로그래머들은 이미 20년전부터 그렇게 했을 것이다. 기능을 제거해서 언어가 더 강력해진다는 건 논리적으로 불가능하다. 그 기능이 아무리 나쁜 것이라 하더라도.

함수형 프로그래머 입장에서도 소위 장점이라고 하는 이것들만으로 만족해서는 안된다. 그렇게 해서는 함수형 언어가 가진 힘을 제대로 활용하는데 도움이 되지 않기 때문이다. 단지 대입문만 없는, 혹은 “참조 투명성”만으로는, 프로그램을 작성할 수 없다. 거기엔 프로그램의 품질을 따질 척도도 없고 지향할 목표도 없다.

분명히 함수형 프로그래밍의 이 특징들 만으로는 부족하다. 우리는 그 자리에 놓을 무언가를 찾아야 한다–함수형 프로그래밍의 힘을 설명해 줄 수 있고 또 함수형 프로그래머가 지향해야 할 분명한 지점이 되어줄 무언가를.

2 구조적 프로그래밍과 비교

함수형 프로그래밍과 구조적 프로그래밍을 비교해 보는 것이 좋을 것 같다. 과거 구조적 프로그래밍(structured programming)의 특성이나 장점은 대략 다음과 같이 요약되었다. 구조적 프로그램은 goto문이 없다. 구조적 프로그램의 블럭은 시작점(entry)과 종료점(exit)을 여러 개 가지지 않는다. 구조적 프로그램은 기존의 비 구조적 프로그램에 비해 수학적으로 더 쉽게 추적할 수 있다. 이러한 구조적 프로그래밍의 “장점”은 이미 논의한 함수형 프로그래밍의 “장점”과 매우 비슷하게 느껴진다. 이들은 사실 부정적 진술이며 “goto의 본질”과 관련한 유용한 논의를 이끌어내지 못한다.

지금 돌이켜보자면 구조적 프로그램이 갖는 이러한 성질들이 문제의 본질에 다가가진 못한다는 것이 뚜렷하게 보인다. 구조적 프로그램과 비 구조적 프로그램의 가장 중요한 차이점은 구조적 프로그램이 모듈 방식으로 설계된다는 점이다. 모듈화 설계로 생산성이 크게 향상된다. 첫째, 작은 모듈들은 빨리 쉽게 작성할 수 있다. 둘째, 모듈을 일반화하여 재사용할 수 있으며 이로 인해 다른 프로그램을 더 빨리 개발할 수 있다. 셋째, 한 프로그램의 모듈들을 독립적으로 테스트할 수 있어서 디버깅 시간을 줄일 수 있다.

goto가 없고 등등의 것들은 이런 장점과 연관 짓기 어렵다. 이런 것들은 “작은 단위의 프로그래밍”을 도와주지만 모듈화 설계는 “큰 단위의 프로그래밍”에 도움을 준다. 그래서 조금 더 수고를 들여야 하겠지만 누구든 FORTRAN이나 어셈블리 언어로도 구조적 프로그래밍의 이득을 얻을 수 있다.

모듈화 설계가 성공적인 프로그래밍에 필수적이라는 점은 이제 일반적으로 인정되고 있으며, MODULA-II[6]와 Ada[5] 같은 최신 언어들은 특별히 모듈화 수준을 향상시키기 위한 기능들을 포함한다. 그런데 흔히 놓치는 매우 중요한 포인트가 있다. 어떤 문제를 해결하기 위해 모듈화된 프로그램을 작성할 때에는 먼저 문제를 작은 문제로 나누고, 그 작은 문제들을 해결한 다음 마지막으로 각 해결안들을 결합한다. 원래의 문제를 어떻게 나눌 것이냐 하는 것은 나중에 해결안들을 어떤 식으로 결합할 수 있느냐에 직접적으로 영향을 받는다. 따라서 문제를 모듈화 할 수 있는 수준을 높이려면 프로그래밍 언어 차원에서 새로운 형태의 접착제(glue)를 제공해야만 한다. 복잡한 스코프 규칙이나 분할 컴파일 방법 등은 저수준의 도움을 제공할 뿐이다–모듈화에 직접적으로 큰 기여를 하지 않는다.

이제부터 우리는 함수형 언어가 제공하는 두 가지 새로운, 그리고 매우 중요한 접착제를 설명하겠다. 몇 가지 예제 프로그램을 통해 새로운 방식으로 모듈화 함으로써 더 단순해질 수 있음을 보여줄 것이다. 함수형 프로그래밍이 가지는 힘의 핵심은 모듈화를 향상시킨다는 점이다. 더 작고, 더 간단하고, 더 범용적인 모듈들을 새로운 형태의 접착제로 결합하는 것, 이것은 함수형 프로그래머들이 얻고자 노력해야 하는 목표이기도 하다.

3 함수 결합하기

두 종류의 새로운 접착제 중에서 먼저 다룰 것은 간단한 함수들을 서로 결합하여 더 복잡한 함수들을 만들 수 있게 해준다. 간단한 리스트를 다루는 문제를 가지고 설명하겠다. 리스트에 새로운 요소를 하나 추가하는 문제이다. 우리는 먼저 아래와 같이 리스트를 정의할 수 있다.

listof * ::= Nil | Cons * (listof *)

*의 리스트(*는 무엇이든 가능)는 Nil(빈 리스트)이거나 * 하나와 또 다른 *의 리스트로 만들어진 Cons라는 의미이다. 하나의Cons는 첫 번째 요소가 *이고 두 번째 이후의 요소들이 또 다른 * 의 리스트의 요소들과 같은 리스트를 표현한다. 여기서 *는 어떤 타입이든 가능하다–예를 들어, *가 “정수”라면 정수 리스트를 비어 있거나 혹은 정수 하나와 또 다른 정수 리스트로 만들어진 Cons로 정의된다는 의미이다. 일반적 관례에 따라 앞으로 리스트를 표시할 때 Cons와 Nil을 사용하는 대신 요소들을 [ ]로 감싸는 형식으로 표시할 것이다. 이는 표기법에 있어서의 편의를 위한 것일 뿐이다. 예를 들어,

  • [ ]는 Nil을 의미한다.
  • [1]는 Cons 1 Nil을 의미한다.
  • [1, 2, 3]는 Cons 1 (Cons 2 (Cons 3 Nil))을 의미한다.

리스트의 요소들은 재귀 함수 sum을 이용하여 모두 더할 수 있다. sum 함수는 두 종류의 인자에 대해 정의되어야 한다. 하나는 빈 리스트(Nil), 다른 하나는 Cons에 대해서이다. 리스트가 비었을 때 그 합은 0이므로 우리는 다음처럼 정의한다.

sum Nil = 0

그리고 Cons의 합은 첫 번째 요소를 다른 리스트의 합에 더하는 방법으로 계산할 수 있다. 따라서 아래처럼 정의한다.

sum (Cons n list) = n + sum list

이 정의를 살펴보면 합을 계산하는 문제에 국한된 것은 굵은 글씨 부분(0과 +)뿐이라는 것을 알 수 있다.

sum Nil = 0
sum (Cons n list) = n + sum list

리스트 요소들의 합을 계산하는 것이 범용적인 재귀 패턴과 네모 표시 부분을 접착하는 방법으로 모듈화 가능하다는 것을 의미한다. 이러한 재귀 패턴은 일반적으로 foldr이라고 부르며 이제 sum은 다음처럼 표현될 수 있다.

sum = foldr (+) 0

sum의 정의를 파라미터화하면 foldr의 정의를 유도할 수 있다.

(foldr f x) Nil = x
(foldr f x) (Cons a l) = f a ((foldr f x) l)

(foldr f x)에 괄호를 치긴 했지만 이는 sum의 정의에서 바꿔치기 한 것을 분명히 드러내기 위한 것이다. 보통은 괄호를 생략하여 ((foldr f x) l)을 (foldr f x l)로 쓸 수 있다. foldr처럼 인자가 세 개 인 함수에 인자를 두 개만 적용하면 그 결과는 남은 인자 하나를 취하는 함수가 되며, 보다 일반적으로 말해서, 인자가 n 개인 함수에 n보다 작은 m 개의 인자만 적용되었을 때 이는 다시 n-m 개의 남은 인자를 취하는 함수가 된다.

sum을 이렇게 모듈화하고 나면 우리는 그 부품들을 재사용함으로써 이득을 취할 수 있다. 여기서 가장 흥미로운 부품은 foldr이다. foldr을 재사용하면 추가적인 프로그래밍 노력을 들이지 않고 리스트의 모든 요소들을 곱하는 함수를 작성할 수 있다.

product = foldr (*) 1

불(bool) 값의 리스트에서 참 값이 있는지 확인할 때에도 사용할 수 있다.

anytrue = foldr (⋁) False

혹은 모두 참인지 확인할 수도 있다.

alltrue = foldr (⋀) True

(foldr f a)는 리스트를 구성하는 모든 Cons를 f로, Nil을 a로 바꿔치우는 함수로 이해할 수도 있다. [1, 2, 3] 리스트를 예로 들자면, 이는 원래 다음과 같으며

Cons 1 (Cons 2 (Cons 3 Nil))

(foldr (+) 0)을 통해서 다음처럼 바뀐다.

(+) 1 ((+) 2 ((+) 3 0)) = 6

(foldr (*) 1)을 통해서는 다음처럼 바뀐다.

(*) 1 ((*) 2 ((*) 3 1)) = 6

이제 (foldr Cons Nil)이 리스트를 단순히 복사할 뿐이라는 것을 쉽게 알 수 있다. 어떤 리스트를 다른 리스트에 이어 붙이려면 뒤쪽 리스트의 앞 부분에 요소들을 Cons하여 붙이면 되므로 다음을 쉽게 알 수 있다.

append a b = foldr Cons b a

예를 들어,

append [1, 2] [3, 4] = foldr Cons [3, 4] [1, 2]
= foldr Cons [3, 4] (Cons 1 (Cons 2 Nil))
= Cons 1 (Cons 2 [3, 4]))
(Cons를 Cons로, Nil을 [3, 4]로 바꾼 것)
= [1, 2, 3, 4]

리스트 요소들의 갯수를 세는 함수 length는 다음처럼 정의된다.

length = foldr count 0
count a n = n + 1

count를 이용하여 Cons 갯수만큼 0에서 1씩 증가한다. 리스트의 모든 요소들에 2를 곱하는 함수는 다음처럼 작성할 수 있다.

doubleall = foldr doubleandcons Nil
doubleandcons n list = Cons (2 * n) list

doubleandcons는 더 모듈화할 수 있다.

doubleandcons= fandcons double
double n = 2 * n
fandcons f el list = Cons (f el) list

그리고 다시 다음처럼 고쳐 쓸 수 있다.

fandcons f = Cons . f

여기서 “.”(함수 합성 표준 연산자)는 다음처럼 정의되어 있다.

(f . g) h = f (g h)

fandcons의 새로운 정의에 인자를 적용해보면 올바르다는 것을 알 수 있다.

fandcons f el = (Cons . f) el
= Cons (f el)

이므로 다음처럼 된다.

fandcons f el list = Cons (f el) list

최종 버전은 다음과 같다.

doubleall = foldr (Cons . double) Nil

추가적인 모듈화를 통해 다음을 얻을 수 있다.

doubleall = map double
map f = foldr (Cons . f) Nil

여기서 map이라는 일반화된 유용한 함수는 리스트의 모든 요소들에 함수 f를 적용한다.

행렬을 리스트의 리스트로 표현하면 행렬의 모든 요소들을 합하는 함수도 작성할 수 있다.

summatrix = sum . map sum

map sum 함수는 sum이용하여 모든 행(row)을 합하고, 다시 맨 왼쪽의 sum이 행 별 합을 합하여 전체 행렬의 합을 구한다.

이 예제들을 통해 독자들은 모듈화가 꽤 멀리 진행될 수 있음을 알 수 있었을 것이다. 간단한 함수 하나(sum)를 “고차 함수(higher-order function)”와 간단한 인자 몇 개로 모듈화함으로써 우리는 foldr이라고 하는 부품에 도달할 수 있었다. foldr을 이용하면 리스트를 다루는 많은 함수들을 추가적인 프로그래밍 노력 없이 구현할 수 있다.

리스트 처리 함수에서 멈출 필요가 없다. 또 다른 예제로서 트리 자료형을 고려해보자. 트리 자료형은 다음처럼 정의된다.

treeof * ::= Node * (listof (treeof *))

이 정의에 따르면, *의 트리는 노드이며, 노드는 *를 레이블로 가지고 다시 하위 트리를 * 트리의 리스트로 가진다. 예를 들어 다음의 트리를 보자.

이 트리는 다음과 같이 표현된다.

Node 1
(Cons (Node 2 Nil)
(Cons (Node 3
(Cons (Node 4 Nil) Nil))
Nil))

예제를 살펴보고 그것으로부터 고차 함수를 추상화 해나가는 대신 foldr과 유사한 foldtree 함수를 바로 만들어 보겠다. foldr 함수의 인자는 두 개였다. 하나는 Cons를 대신할 어떤 값이고, 다른 하나는 Nil을 대신할 어떤 값이다. 트리는 Node와 Cons, 그리고 Nil로 만들어지므로 foldtree는 각각을 대신하기 위해 인자를 세 개 가져야 한다. 따라서 다음처럼 정의할 수 있다.

foldtree f g a (Node label subtrees) =
f label (foldtree' f g a subtrees)
foldtree' f g a (Cons subtree rest) =
g (foldtree f g a subtree) (foldtree' f g a rest)
foldtree' f g a Nil = a

foldtree와 다른 함수들을 결합하여 재미있는 함수를 많이 정의할 수 있다. 예를 들어 수로 만들어진 트리의 레이블을 모두 더하는 함수는 다음과 같다.

sumtree = foldtree (+) (+) 0

앞서 예로 살펴본 트리에 sumtree를 적용하면 다음과 같다.

(+) 1
((+) ((+) 2 0)
((+) ((+) 3
((+) ((+) 4 0) 0))
0))

트리를 구성하는 모든 레이블을 리스트로 가져오는 함수는 다음과 같다.

labels = foldtree Cons append Nil

앞의 예제 트리에 적용하면 다음과 같다.

Cons 1
(append (Cons 2 Nil)
(append (Cons 3
(append (Cons 4 Nil) Nil))
Nil))

마지막으로 map에 상응하는 함수로서 트리의 모든 레이블에 함수 f를 적용하는 함수를 정의해 볼 수 있다.

maptree f = foldtree (Node . f) Cons Nil

지금까지 진행한 모든 내용은 함수형 언어가 함수를 표현할 때 부분들–일반화된 고차 함수와 구체화 함수들–의 결합으로 표현할 수 있게 허용하기 때문에 가능했다. 고차 함수를 한번 정의하고 나면 많은 연산을 매우 쉽게 프로그래밍할 수 있다. 새로운 자료형(datatype)을 정의할 때마다 이를 처리하는 고차 함수도 함께 작성되어야 한다. 이렇게 하면 자료형을 쉽게 다룰 수 있게 되고 자료형의 세부적 표현 정보가 한 군데 모이게 된다. 기존의 프로그래밍에서의 확장 가능한 언어와 비견될 수 있다. 사실상 필요할 때마다 프로그래밍 언어가 새로운 제어 구조로 확장될 수 있기 때문이다.

4 프로그램 결합하기

함수형 언어가 제공하는 또 하나의 새로운 접착제는 프로그램들끼리 서로 결합할 수 있게 해준다. 온전한 함수형 프로그램은 입력과 출력을 가지는 함수일 뿐이라고 했다. 만약 f와 g가 그런 프로그램이라면 (g . f)도 프로그램이다. 입력 input에 적용하면 다음을 계산한다.

g (f input)

프로그램 f가 출력값을 계산하면 그 값은 다시 프로그램 g의 입력으로 사용된다. 이는 전통적으로 f의 출력값을 임시 파일에 저장하는 방법으로 구현될 수 있다. 이 방법의 문제는 임시 파일이 너무 많은 메모리를 필요로 하여 프로그램을 이런 방법으로는 연결할 수 없을 수 있다는 것이다. 함수형 언어는 이 문제의 해결 방법을 제공한다. 두 개의 프로그램 f와 g를 엄격한 동기화하여 함께 실행하는 것이다. 프로그램 f는 프로그램 g가 입력을 읽으려 할 때에만 시작되며 g가 읽으려 한 만큼의 출력을 전달할 때까지만 실행된다. 그런 다음 f는 중지(suspend)되고 g가 다시 입력을 읽으려 할 때까지 실행된다. 추가로 얻게 되는 이득은, 만약 g가 f의 출력을 모두 읽지 않고 종료되면 f도 종료(abort)된다. 프로그램 f는 비종료 프로그램, 즉 출력값을 무한히 생성하는 프로그램일 수도 있다. 프로그램 g가 끝나면 바로 강제 종료될 것이기 때문이다. 이 같은 방식 덕분에 종료 조건을 루프에서 분리할 수 있다–이는 강력한 모듈화이다.

이러한 평가 방식은 f를 가능한 최소로 실행하기 때문에 “지연 평가(lazy evaluation)”라고 불린다. 이 방식으로 인해 프로그램을 1) 많은 수의 가능한 답안을 생성하는 생성기(generator)와 2) 적절한 답안을 선택하는 선택기(selector)로 모듈화할 수 있게 된다. 다른 시스템 중에도 이 같은 방식으로 프로그램들을 동시에 실행할 수 있게 하는 경우가 있기는 하지만 오직 함수형 언어만이 모든 함수 호출에 대해 일관되게 지연 평가를 사용한다(심지어 함수형 언어라고 모두가 지원하지는 않는다). 아마도 지연 평가는 함수형 프로그래머의 도구 중에서도 가장 강력한 도구일 것이다.

함수형 언어라는 환경 하에서 지연 평가를 설명했는데, 비 함수형 언어에도 추가되어야만 할 정도로 유용한 기능이다. 하지만 그럴 수 있을까? 지연 평가와 부작용(side-effect)이 공존할 수 있을까? 불행하게도 불가능하다. 지연 평가를 명령형(imperative) 언어에 추가하는 것이 실제로 불가능하지는 않다. 하지만 이 둘의 조합은 프로그래머의 삶을 더 쉽게 하기보다는 더 어렵게 만들것이다. 지연 평가의 강력함은 프로그래머가 프로그램의 각 부분이 어떤 순서로 실행될 것인가를 결정하는 직접적인 제어권을 포기하는 것을 필요로 하기 때문에 부작용을 가진 프로그래밍을 더 어렵게 만들 것이다. 부작용이 어떤 순서로 일어날 지 혹은 실제로 일어날 지 아닐 지를 예측하려면 부작용을 포함하는 문맥에 대해 더 자세히 알아야만 한다. 그러한 전역적 상호 의존성이 바로 모듈화 가능성을 낮추게 된다–함수형 언어에서는 지연 평가를 통해 모듈화 가능성을 증대시키는 것과 대비된다.

4.1 뉴튼-랩슨의 제곱근

우리는 여기서 몇 가지 수치 알고리즘을 구현하면서 지연 평가의 힘을 보여줄 것이다. 처음 살펴볼 알고리즘은 제곱근을 찾기 위한 뉴튼-랩슨(Newton-Raphson) 알고리즘이다. 이 알고리즘은 어떤 수 n의 제곱근을 계산하기 위해 최초 추정값 a(0)로부터 다음의 규칙에 따라 점점 더 나은 추정값을 계산한다.

a(i+1) = (a(i) + n / a(i)) / 2

추정값이 어떤 극한값 a로 수렴한다면

a = (a + n / a) / 2

이므로, 아래와 같이 a는 n의 제곱근이다.

   2a = a + n / a
a = n / a
a * a = n
a = sqrt(n)

실제로 추정값은 빠르게 극한값으로 수렴한다. 제곱근 프로그램은 주어진 허용 오차(eps)에 따라 두 추정값의 차이가 eps보다 작아지면 멈춘다.

알고리즘은 보통 아래와 같은 프로그램으로 구현된다.

C   N IS CALLED ZN HERE SO THAT IT HAS THE RIGHT TYPE
X = A0
Y = A0 + 2. * EPS
C Y'S VALUE DOES NOT MATTER SO LONG AS ABS(X-Y).GT.EPS
100 IF ABS(X-Y).LE.EPS GOTO 200
Y = X
X = (X + ZN/X) / 2.
GOTO 100
200 CONTINUE
C THE SQUARE ROOT OF ZN IS NOW IN X.

이 프로그램을 기존 언어로 구현한다면 더 이상 나누어지지 않는다. 지연 평가를 이용하면 더 잘게 모듈화하여 표현할 수 있고, 또 그 부분을 다른 곳에 재사용할 수 있는 예도 보여주겠다.

뉴튼-랩슨 알고리즘은 추정값을 계속 이어서 계산하는 알고리즘이므로 이를 프로그램 내부에서 명시적인 추정값 리스트로 표현하는 것이 자연스럽다. 앞 단계의 추정값으로부터 다음 추정값을 계산하는 함수는 다음과 같다.

next n x = (x + n / x) / 2

이제 (next n)은 하나의 추정값을 다음 추정값으로 매핑하는 함수이다. 이 함수를 f라고 한다면 추정값 리스트는 다음과 같다.

[a0, f a0, f (f a0), f (f (f a0)), ...]

이 같은 리스트를 계산하기 위해 다음의 함수를 정의할 수 있다.

repeat f a = Cons a (repeat f (f a))

그러면 추정값 리스트는 아래와 같이 계산된다.

repeat (next n) a0

repeat 함수가 바로 출력값을 “무한히” 생성하는 함수의 예이다–이것이 문제가 되지 않는 이유는 프로그램의 다른 부분에서 실제 계산에 필요한 만큼 이상의 추정값은 계산되지 않기 때문이다. 무한하다는 것은 그럴 수 있다는 것일 뿐이다. 실제 의미는 필요하다면 얼마든지 추정값이 계산될 수 있다는 것이며, repeat 자체에서는 제한을 두지 않는다.

제곱근 계산 프로그램에서 남은 부분은 within 함수이다. 이 함수는 허용 오차와 추정값 리스트를 입력으로 받아 리스트에서 이어진 두 추정값이 주어진 허용 오차 내에서 같을 때까지 리스트를 살펴본다. 아래와 같이 정의할 수 있다.

within eps (Cons a (Cons b rest))
= b, if abs(a - b) ≤ eps
= within eps (Cons b rest), otherwise

부분들을 모두 합치면 다음과 같다.

sqrt a0 eps n = within eps (repeat (next n) a0)

이제 제곱근 계산 프로그램이 완성되었으니, 이 부분들을 다른 방식으로 합칠 수 있는 방법을 찾아보자. 먼저 이어진 두 추정값의 비율이 1에 가까워질 때까지 기다리도록 고쳐볼 수 있다. 제곱근을 찾으려는 수가 매우 작은 수 이거나(이어진 두 추정값이 처음부터 매우 작을 때) 매우 큰 수 일 때(반올림 오차가 허용 오차보다 훨씬 클 수 있다) 더 적절한 방법이다. within을 대신할 함수만 정의하면 된다.

relative eps (Cons a (Cons b rest))
= b, if abs(a / b - 1) ≤ eps
= relative eps (Cons b rest), otherwise

이제 새로운 버전의 sqrt를 아래와 같이 정의할 수 있다.

relativesqrt a0 eps n = relative eps (repeat (next n) a0)

추정값을 생성하는 부분을 다시 작성할 필요가 없다.

4.2 수치 미분

앞의 제곱근 문제에서 우리는 추정값의 리스트를 재사용했다. within이나 relative를 다른 수치 알고리즘에 재사용하는 것 역시 가능하다. 수치 미분(numerical differentiation) 알고리즘에서 어떻게 재사용되는지 살펴보자.

함수를 특정 지점에서 미분한 값은 함수를 그래프로 나타냈을 때 해당 지점에서의 그래프 기울기이다. 이 값은 주어진 점과 이웃한 다른 점에서 함수 값을 구한 다음 두 점 사이의 직선 기울기를 계산하는 방법으로 쉽게 추정할 수 있다. 이 방법은 두 점이 충분히 서로 가깝고, 함수 그래프가 두 지점 사이에서 크게 변화하지 않음을 가정한다. 다음과 같이 정의할 수 있다.

easydiff f x h = (f (x + h) - f x) / h

좋은 추정값을 구하려면 h 값이 매우 작아야 한다. 하지만 h가 너무 작으면 f(x+h)와 f(x)값 역시 너무 작아서 빼기 연산의 반올림 오차가 결과값을 망쳐버릴 수 있다. 적절한 h 값을 어떻게 결정할까? 이 딜레마를 해결할 수 있는 한 가지 방법은 충분히 큰 값을 시작으로 h를 점점 작게 바꿔가며 추정값 수열을 계산하는 것이다. 이 수열은 분명 미분 값으로 수렴할 것이다. 하지만 반올림 오차 때문에 결국에는 부정확해지게 된다. (within eps)를 사용하여 충분히 정확한 첫 번째 추정값을 결정할 수 있다면 반올림 오차의 영향을 크게 줄일 수 있다. 우선 수열을 계산하는 함수가 필요하다.

differentiate h0 f x = map (easydiff f x) (repeat halve h0)
halve x = x / 2 $

여기서 h0는 h의 시작값이고, 계속 반으로 나누어가며 값을 만들어낸다. 이 함수를 이용하면 특정 지점의 미분 값을 아래와 같이 계산할 수 있다.

within eps (differentiate h0 f x)

이 방법은 추정값이 매우 느리게 수렴하기 때문에 그다지 만족스럽지 않다. 여기서 수학의 도움을 약간 받을 수 있다. 이 수열의 각 요소들은 아래 식으로 표현할 수 있다.

정답 + h를 포함한 오류항

이론적으로 오류항의 값은 대략 h의 지수승에 비례하며 h가 작아짐에 따라 오류항도 작아진다. 정답을 A, 오류 항을 B * h^n라고 하자. 각 추정값을 계산할 때 사용되는 h 값은 다음 추정값을 계산할 때보다 두 배 큰 값이므로 이어진 두 추정값을 다음처럼 표현할 수 있다.

a(i) = A + B * 2^n * h^n
a(i + 1) = A + B * h^n

이제 오류항의 B를 제거할 수 있다. 결과는 다음과 같다.

     a(i+1) * (2^n) - a(i)
A = -----------------------
2^n - 1

물론 오류항이 h의 지수승이라는 것도 대략적인 것이므로 앞의 결과 역시 추정값이다. 하지만 훨씬 정확한 추정값이다. 이제 이 개선 내용을 적용하여 이어지는 추정값 쌍들에 대해 다음 함수를 적용할 수 있다.

elimerror n (Cons a (Cons b rest))
= Cons ((b * (2^n)-a) / (2^n- 1)) (elimerror n (Cons b rest))

추정값 수열에서 오류항을 제거하면 또 하나의 수열이 만들어지며, 이 수열은 훨씬 더 빠르게 수렴한다.

elimerror를 사용하려면 n 값을 정해야 하는 문제가 남았다. 이 값을 일반적으로 예측하기는 어렵지만 측정하기는 쉽다. 다음의 함수로 그 값을 정확하게 추정할 수 있다는 것을 증명하는 것은 어렵지 않지만 여기서 증명을 포함하진 않겠다.

order (Cons a (Cons b (Cons c rest)))
= round (log2 ((a - c) / (b - c) - 1))
round x = x를 가장 가까운 정수로 반올림
log2 x = 2를 밑으로 하는 x의 로그 값

이제 추정값 수열을 개선할 수 있는 일반화된 함수를 다음처럼 정의할 수 있다.

improve s = elimerror (order s) s

함수 f의 미분값은 improve를 이용하여 더 효율적으로 계산할 수 있다.

within eps (improve (differentiate h0 f x))

improve 함수는 h 인자, 즉 추정값을 계산할 때마다 1/2씩 작아지는 값으로 계산한 추정값 수열에 대해서만 동작한다. 하지만 이 함수를 수열에 적용하였을 때 그 결과 역시 수열이다! 따라서 추정값 수열을 한번 이상 더 개선할 수 있다. 매번 오류항이 추가로 제거되면서 결과 수열은 점점 더 빨리 수렴한다. 따라서 다음의 식을 통해 미분값을 매우 효율적으로 계산할 수 있다.

within eps (improve (improve (improve (differentiate h0 f x))))

수치 해석의 용어로 말하자면 “4차 방법(fourth-order method)”과 비슷하다. 이 방법은 정확한 값을 매우 빠르게 계산한다. 심지어 다음과 같이 정의할 수도 있다.

super s = map second (repeat improve s)
second (Cons a (Cons b rest)) = b

여기서 repeat improve는 추정값 수열을 점점 더 개선하는 수열을 계산한다. 이렇게 만들어진 추정값 수열의 수열에서 각 추정값 수열의 두 번째 값을 취하면 새로운 추정값 수열이 만들어진다(여기서 두 번째 값을 취하는 것이 최선이라는 것을 발견했는데, 첫 번째 값을 취했을 때보다 더 정확하여 더 계산할 필요가 없다). 이 알고리즘은 사실 매우 복잡하다–이 방법은 추정값이 계산됨에 따라 점점 더 나은 수치적 방법을 사용한다. 이제 다음과 같이 미분값을 매우 효율적으로 계산할 수 있다.

within eps (super (differentiate h0 f x))

아마도 이 방법은 닭을 잡는데 도끼를 쓴 격일 수도 있겠지만, 요점은 super처럼 복잡한 알고리즘이라 하더라도 지연 연산을 이용하여 모듈화하면 쉽게 표현된다는 점이다.

4.3 수치 적분

마지막으로 다룰 예제는 수치 적분(numerical integration)이다. 문제는 매우 간단하다. 실수 영역에 정의된 함수 f와 두 점 a, b가 주어졌을 때 두 점 사이의 f 곡선 아래 영역의 크기를 계산하는 것이다. 가장 쉬운 방법은 f가 직선에 가깝다고 가정하고 아래의 식처럼 추정하는 것이다.

easyintegrate f a b = (f a + f b) * (b - a) / 2

하지만 이 추정값은 a와 b가 매우 가깝지 않으면 부정확하다. a와 b 구간을 반으로 나누어 각 영역을 계산하여 합치면 더 나은 추정값을 얻을 수 있다. 위의 공식을 이용하여 첫 추정값을 만들고, 이후 구간을 반으로 나누어 구간 별 추정값을 구해 합치는 방법으로 점점 더 정확한 추정값의 수열을 만들 수 있다. 이 수열은 다음의 함수로 계산된다.

integrate f a b = Cons (easyintegrate f a b)
(map addpair (zip2 (integrate f a mid)
(integrate f mid b)))
where mid = (a + b) / 2

여기 사용된 zip2 함수는 리스트를 처리하는 또 하나의 표준 함수이다. 이 함수는 두 개의 리스트를 받아서 짝의 리스트를 반환한다. 각 짝은 두 리스트의 요소들로 구성된다. 두 리스트의 첫 번째 요소들이 결과 리스트의 첫 번째 짝을 구성하고, 두 리스트의 두 번째 요소들 결과 리스트의 두 번째 짝을 구성하는 식이다. zip2 함수는 다음처럼 정의된다.

zip2 (Cons a s) (Cons b t) = Cons (a, b) (zip2 s t)

integrate에서 zip2는 현재 구간을 반으로 나눈 반쪽 구간에 해당하는 추정값들의 짝을 계산한다. 그리고 map addpair는 각 짝을 더하여 원래 구간의 적분값에 대한 추정값 리스트를 만든다.

사실 이 버전의 integrate는 f 값을 계속 반복 계산하기 때문에 꽤 비효율적이다. easyintegrate의 정의를 보면 a와 b에서 f를 평가하는데, integrate가 재귀 호출될 때마다 두 값을 또 평가한다. (f mid) 역시 재귀 호출마다 평가된다. 따라서 다음과 같이 수정하여 f 값을 매번 평가하지 않도록 하는 것이 더 낫다.

integrate f a b = integ f a b (f a) (f b)
integ f a b fa fb = Cons ((fa + fb) * (b - a) / 2)
map addpair (zip2 (integ f a m fa fm)
(integ f m b fm fb)))
where m = (a + b) / 2
fm = f m

integrate 함수는 앞 절의 differentiate와 마찬가지로 적분값에 대한 점점 더 나은 추정값의 무한 리스트를 계산한다. 따라서 원하는 정확도의 적분값을 구하기 위해 아래의 둘 중 하나로 작성할 수 있다.

within eps (integrate f a b)
relative eps (integrate f a b)

이 적분 알고리즘은 앞 절에서 보여줬던 첫 번째 버전의 미분 알고리즘과 마찬가지의 약점을 가진다–다소 느리게 수렴한다. 역시 마찬가지로 개선할 수 있다. 수열의 첫 번째 추정값은 오직 두 지점과 두 지점 사이의 거리 b-a 만을 이용하여 easyintegrate로 계산된다. 두 번째 추정값은 중간값을 이용하며 (b-a)/2 간격을 기준으로 계산된다. 세 번째 추정값은 각 간격을 다시 반으로 나누어 (b-a)/4의 간격과 각각의 이웃점들을 이용하여 계산된다. 다음 추정값을 계산할 때마다 이웃한 점들의 간격이 반으로 좁아진다. 이웃점 간의 간격을 h라고 본다면, 이 수열은 앞 절에서 정의한 improve 함수로 개선할 수 있는 후보라고 볼 수 있다. 따라서 빠르게 수렴하는 적분 추정값 수열을 다음처럼 작성할 수 있다.

super (integrate sin 0 4)

다음과 같이 작성할 수도 있다.

improve (integrate f 0 1)
where f x = 1 / (1 + x * x)

(두 번째 수열은 π/4를 계산하기 위한 “8차 방법”이다. 두 번째 추정값은 f를 5번만 계산하면 계산할 수 있으며 그 값은 소숫점 아래 다섯 자리까지 정확하다.)

이번 절에서 우리는 몇 가지 수치 알고리즘을 다루었고 그 알고리즘들을 함수형 스타일로 구현하면서 지연 연산을 이용하여 각 부분을 연결해 보았다. 지연 연산 덕분에 우리는 알고리즘을 새로운 방식으로 모듈화하여 within, relative, improve 같은 일반적인 유용한 함수를 얻을 수 있었다. 이들 부품들을 다양한 방식으로 결합하여 꽤 멋진 알고리즘을 아주 간단하고 쉽게 구현할 수 있었다.

5 인공지능 예제

함수형 언어는 고차 함수와 지연 연산이라는 두 가지 새로운 접착제를 제공하기 때문에 강력하다고 주장했다. 이번 절에서는 “인공 지능”이라는 더 큰 예제를 가지고 이 두 가지 접착제를 이용하여 꽤 간단히 구현될 수 있음을 보여주려 한다.

예제로 사용할 것은 알파-베타 “휴리스틱”이다. 이 알고리즘은 게임 플레이어의 위치가 얼마나 좋은지를 추정하기 위한 것이다. 이 알고리즘은 앞으로 게임이 전개될 양상을 미리 내다보는 방법이며, 손해가 되는 길로 접어들지 않게 한다.

게임 위치를 나타내는 값이 position 타입이라고 하자. 이 타입은 게임마다 다를 것이며 우리는 위치 타입과 관련하여 아무것도 가정하지 않을 것이다. 어떤 위치로부터 다음 가능한 위치를 알 수 있어야 하며 이를 계산해주는 다음의 함수가 있다고 가정하자.

moves :: position → listof position

moves 함수는 위치를 인자로 받아 다음 차례에 이동 가능한 모든 위치를 리스트로 반환한다. 예를 들어 그림 1은 틱택토 게임에서의 위치와 그에 해당하는 moves 결과를 보여준다. 이 예에서는 위치가 주어지면 현재 어느 플레이어의 차례인지 항상 알 수 있다고 가정한다. 틱택토 게임에서는 x와 o의 갯수를 세어보면 알 수 있다. 체스와 같은 게임이라면 position 타입에 명시적으로 차례 정보를 포함시켜야 할 것이다.

그림 1. 틱택토 게임에서의 moves

moves 함수가 주어지면 첫 단계는 게임 트리를 만드는 일이다. 이 트리의 각 노드는 위치 값을 레이블로 사용하고, 노드의 자식들은 해당 노드로부터 진행될 수 있는 다음 위치들을 가리킨다. 즉 어떤 노드의 레이블이 위치 p라면 그 자식들은 (moves p)의 위치들로 레이블이 붙는다. 게임 트리의 크기가 모두 제한적이진 않다. 어떤 게임이 두 플레이어 모두 이기지 못하고 영원히 계속될 수도 있다면 게임 트리는 무한히 확장된다. 게임 트리는 2절에서 논의했던 바로 그 트리 자료형이다. 각 노드는 레이블(위치를 표현한다)과 자식 노드들의 리스트를 가진다. 따라서 게임 트리를 표현하는데 같은 자료형을 사용할 수 있다.

게임 트리는 moves를 반복적으로 호출하여 만들 수 있다. 최초 위치부터 시작하여 moves를 호출하면 그 다음 단계 트리들의 레이블이 만들어진다. 자식 트리들마다 같은 방법을 적용하여 그 하위의 트리를 계속 만들 수 있다. 이런 재귀 패턴은 고차 함수로 표현할 수 있다.

reptree f a = Node a (map (reptree f) (f a))

이 함수를 이용하면 특정 위치로부터 게임 트리를 만드는 함수를 정의할 수 있다.

gametree p = reptree moves p

그림 2의 예를 살펴보자. 여기 사용된 고차 함수(reptree)는 이미 다루었던 무한 리스트를 생성하는 repeat 함수와 대응된다.

그림 2. 틱택토 게임 트리의 일부분

알파-베타 알고리즘은 주어진 위치를 기준으로 앞으로 게임이 좋은 방향으로 전개될 지 나쁜 방향으로 전개될 지 내다보는 방법이다. 하지만 이를 위해서는 특정 위치의 가치를 더 내다보지 않고서도 대략적으로나마 평가할 수 있어야 한다. 이런 “정적 평가”는 미리 내다보기의 맨 끝에서 사용되어야 하며, 알고리즘 전개 초기에 가이드로 사용할 수도 있다. 정적 평가의 결과는 컴퓨터 플레이어 입장에서 보았을 때 그 위치가 얼마나 좋은지에 대한 값이다(여기서는 컴퓨터와 사람이 대결하는 게임을 가정한다). 이 값이 클 수록 컴퓨터에게 더 유리한 위치고, 작을 수록 불리한 위치다. 정적 평가를 가장 간단하게 구현한다면 컴퓨터가 이미 이긴 경우에 1, 이미 진 경우에 -1, 나머지 경우에는 0을 반환하는 식으로 구현할 수 있다. 현실에서는 정적 평가 함수가 해당 위치가 좋다고 판단될만한 요소들을 따져야 한다. 예를 들어 체스에서는 기물 점수 상의 우위나 센터에서의 장악력 등을 고려할 것이다. 이 함수도 주어졌다고 가정하자.

static :: position → number

게임 트리는 (treeof position)이기 때문에 (maptree static) 함수를 적용하여 트리 상의 모든 위치를 정적 평가하여 (treeof number)로 변환할 수 있다(트리는 무한히 클 수도 있다). 여기 사용한 maptree는 2절에서 정의한 함수이다.

이처럼 정적 평가가 적용된 트리가 주어졌을 때 게임 트리 상의 각 위치가 가지는 진짜 가치는 얼마나 될까? 예를 들어 트리의 루트, 즉 시작점이 되는 위치의 가치는 얼마이어야 할까? 그 위치의 진정한 값어치는 정적으로 계산한 값과는 다를 것이다. 그건 단지 대략적인 추측일 뿐이니까. 특정 노드의 가치는 하위 노드들의 진짜 가치들로부터 결정되어야 한다. 각 게임 플레이어가 자기 차례에서 최선의 선택을 할 것이라고 가정한다면 이 값을 계산할 수 있다. 높은 값이 컴퓨터 플레이어의 입장에서 좋은 위치를 의미한다고 했으니 컴퓨터는 자신의 차례에서 자식 노드들 중 진짜 가치가 가장 큰 위치로 이동할 것이다. 마찬가지로 상대편은 자식 노드들 중에서 진짜 가치가 가장 작은 위치로 이동할 것이다. 컴퓨터와 상대편이 번갈아가며 자기 차례를 플레이한다고 가정하면 어떤 노드의 진짜 가치를 (컴퓨터 차례인 경우) maximize 함수와 (상대 차례인 경우)minimize 함수로 계산된다.

maximize (Node n sub) = max (map minimize sub)
minimize (Node n sub) = min (map maximize sub)

위 정의에서 max와 min 함수는 각각 수의 리스트에서 최댓값과 최솟값을 반환한다. 위의 두 정의는 무한히 재귀 호출을 반복하기 때문에 아직 완전한 정의되지 않았다–재귀를 마칠 수 있는 베이스 케이스가 빠졌다. 자식 노드가 없는 경우에 대해서 노드의 값을 결정할 수 있어야 하며, 우리는 이 경우에 노드의 정적 평가 가치(노드의 레이블)를 사용하기로 한다. 따라서 정적 평가는 특정 플레이어가 이미 이겼거나 혹은 미리 내다보기의 맨 끝에서만 이용된다. maximize와 minimize의 완전한 정의는 다음과 같다.

maximize (Node n Nil) = n
maximize (Node n sub) = max (map minimize sub)
minimize (Node n Nil) = n
minimize (Node n sub) = min (map maximize sub)

여기까지의 설명이면 위치를 입력 받아 진짜 가치를 반환하는 함수를 다음과 같이 작성할 수 있을 것이다.

evaluation = maximize . maptree static . gametree

이 정의에는 두 가지 문제가 있다. 무엇보다도 이 정의로는 무한히 큰 트리에 대해서 동작하지 않는다. maximize 함수는 자식 노드가 없을 때(즉, 트리가 끝날 때)까지 계속 재귀 호출되기 때문이다. 트리에 끝이 없으면 maximize는 결과를 반환하지 않을 것이다. 두 번째 문제는 심지어 틱택토처럼 유한한 게임 트리일지라도 그것이 매우 클 수 있다는 점과 관련된다. 게임 트리 전체를 평가하려는 것은 현실적이지 못하다–내다보는 단계에 제한을 둬야 한다. 이는 지정된 깊이에서 트리를 가지치기 하면 된다.

prune 0 (Node a x)       = Node a Nil
prune (n + 1) (Node a x) = Node a (map (prune n) x)

(prune n) 함수는 트리를 입력 받아 루트로부터 n 보다 깊은 노드들을 모두 잘라낸다. 게임 트리를 가지치기 하고 나면 maximize 함수에서 깊이 n의 노드들에 대해 정적 평가가 그대로 사용된다. 따라서 evaluate 함수는 다음과 같이 정의될 수 있다.

evaluate = maximize . maptree static . prune 5 . gametree

이 방법은 움직임을 다섯 단계까지 미리 내다본다.

여기까지 구현하면서도 벌써 고차 함수와 지연 평가를 사용했다. 고차 함수 reptree와 maptree 덕분에 게임 트리를 쉽게 다룰 수 있었다. 지연 평가는 evaluate를 위와 같이 모듈화하는데 더 중요한 역할을 했다. gametree가 무한한 크기의 트리를 반환할 수 있기 때문에 지연 평가 없이는 프로그램이 종료되지 않을 것이다. 지연 평가가 없다면 아래처럼

prune 5 . gametree

조합하는 대신 이 두 함수를 하나로 합쳐 트리를 처음부터 다섯 단계까지만 만들어야 했을 것이다. 게다가 다섯 단계까지만 만들더라도 트리가 너무 커서 한꺼번에 메모리에 올리지 못할지도 모른다. 우리가 작성한 프로그램에서 아래 코드는

maptree static . prune 5 . gametree

그 결과를 사용할 maximize에서 필요한 만큼만 트리를 만든다. 그리고 각 부분들은 maximize가 처리를 끝내고 나면 버려져도 상관없기 때문에(가비지 컬렉터에 의해 회수된다) 메모리에 전체 트리가 모두 올라가는 경우는 없다. 어느 순간이든 트리 상의 작은 부분만이 저장된다. 이 때문에 지연 프로그램은 효율적이다. 이 효율성은 maximize(합성으로 연결된 고리의 마지막 함수)와 gametree(연결 고리의 첫 함수) 사이의 상호 연동에 따라 결정된다. 따라서 지연 평가 없이는 이런 수준의 효율성을 얻기 위해 연결 고리의 함수들을 모두 합쳐 하나의 큰 함수를 만들어야만 한다. 이는 결국 모듈화 수준을 크게 떨어뜨리는 결과를 가져오는데, 실제로 흔히 벌어지는 일이기도 하다. 이제 우리는 각 부분을 하나하나 뜯어보면서 이 평가 알고리즘을 개선해 볼 수 있다. 이 과정은 모듈화 수준이 낮은 경우와 비교할 때 상대적으로 쉽다. 기존 방식의 프로그래머들은 한 덩어리로 작성된 전체 프로그램을 수정해야만 하는데 이는 훨씬 더 어렵다.

지금까지 설명한 방법은 간단한 버전의 최소최대(minimax) 방법이다. 알파-베타 알고리즘의 핵심은 게임 트리 전체를 들여다보지 않아도 maximize나 minimize의 결과 값을 계산할 수 있는 경우를 활용하는 것이다. 다음의 트리를 살펴보자.

이 트리의 가치를 평가하기 위해서 꼭 ? 위치의 값을 알 필요가 없다. 왼쪽 최솟값이 1로 평가되고, 오른쪽 최솟값은 0이거나 혹은 더 작은 값이다. 따라서 두 최솟값의 최댓값은 1임이 분명하다. 이런 관찰을 일반화하여 maximize와 minimize에 반영할 수 있다.

먼저 maximize를 리스트를 만드는 것과 여기에 max를 적용하는 것으로 나눈다. 아래와 같이 나눌 수 있다.

maximize = max . maximize'

(minimize도 같은 방식으로 분할한다. minimize와 maximize는 완전한 대칭 형태이므로 여기서는 maximize만 다룬다.) maximize를 이렇게 분할하고 나면 maximize에서 minimize를 사용하는 대신 minimize’를 바로 사용하여, 원래 minimize에서 어떤 값들로부터 최솟값을 구하려 했는지 알 수 있다. 이제 그 값들을 전부 읽지 않고 일부를 버리는 것이 가능하다. 지연 평가 덕분에 만약 maximize가 리스트의 값들을 전부 들여다보지 않는다면 그 뒤의 값들은 계산되지 않을 것이고 불필요한 계산 시간을 줄일 수 있다.

maximize 정의에서 max를 “공통 인자”로 빼내는 것은 쉬운 일이다.

maximize' (Node n Nil) = Cons n Nil
maximize' (Node n l) = map minimize l
= map (min . minimize') l
= map min (map minimize' l)
= mapmin (map minimize' l)
where mapmin = map min

minimize’는 minimize에서 최솟값을 계산할 수 있게 수의 리스트를 반환하는 함수이므로, (map minimize’ l)의 결과는 수의 리스트의 리스트이고, maximize’는 그 리스트들의 최솟값들을 반환해야 한다. 하지만 maximize’의 결과 리스트에서는 최댓값만이 중요하다. 그래서 우리는 mapmin을 새로 정의하여 최솟값을 구해봤자 도움되지 않을 리스트들을 제외시킬 것이다.

mapmin (Cons nums rest)
= Cons (min nums) (omit (min nums) rest)

여기서 omit 함수에 전달하는 것은 “최댓값 후보”이다–지금까지 계산된 최솟값들 중에서 가장 큰 값이다. omit 함수는 이 값보다 작은 최솟값들을 제거한다.

omit pot Nil = Nil
omit pot (Cons nums rest)
= omit pot rest, if minleq nums pot
= Cons (min nums) (omit (min nums) rest), otherwise

minleq 함수는 리스트와 “최댓값 후보”를 받아서 만약 리스트의 최솟값이 “최댓값 후보”보다 크지 않으면 True를 반환한다. 이는 리스트 전체를 살펴보지 않아도 가능하다! 리스트 요소들 중에서 최댓값 후보보다 작거나 같은 값이 하나라도 있으면 리스트 전체의 최솟값도 당연히 최댓값 후보보다 작거나 같다. 그런 값을 하나라도 읽으면 그 뒤의 다른 요소들은 볼 필요가 없다–바로 위의 예제 트리에서 ? 와 마찬가지다. 이제 minleq를 다음처럼 정의할 수 있다.

minleq Nil pot = False
minleq (Cons n rest) pot = True, if n ≤ pot
= minleq rest pot, otherwise

이렇게 maximize’와 minimize’를 정의하고 나면 새로운 평가 함수를 작성하는 일은 간단하다.

evaluate = max . maximize' . maptree static . prune 8 . gametree

지연 평가 덕분에 maximize’가 트리의 더 작은 부분만 본다는 것은 프로그램 전체가 더 효율적으로 동작한다는 것을 의미한다. prune을 통해 무한히 큰 트리를 가지치기하여 트리의 일부분만 살펴봄으로써 프로그램이 무한히 계속되지 않고 종료되는 것과 마찬가지다. maximize’에 적용된 최적화는 꽤 단순하기는 하지만 효과는 매우 커서 평가하는 데 걸리는 시간이 단축되었고, 이로써 더 많은 단계를 내다보고 평가할 수 있게 되었다.

평가 프로그램에 다른 최적화 방법들을 적용할 수 있다. 예를 들어 여기서 설명한 알파-베타 알고리즘은 가장 유리한 이동을 먼저 고려할 때 가장 효과적이다. 아주 좋은 수를 읽었다면 더 나쁜 수는 더 이상 고려할 필요가 없기 때문이다. 고려해봤자 상대방에게 유리한 수가 있다는 걸 확인할 뿐이다. 따라서 각 노드의 자식 트리들을 정렬하여 컴퓨터 차례에서는 큰 값들을 먼저 살펴보게 하고 상대편 차례에서는 작은 값들을 먼저 살펴보게 만들 수 있다. 아래 함수들이 그 일을 한다.

highfirst (Node n sub) = Node n (sort higher (map lowfirst sub))
lowfirst (Node n sub) = Node n (sort (not . higher) (map highfirst sub))
higher (Node n1 sub1) (Node n2 sub2) = n1 > n2

여기 사용된 sort는 일반적인 정렬 함수이다. 이제 평가 프로그램은 아래처럼 바뀌었다.

evaluate
= max . maximize’ . highfirst . maptree static . prune 8 . gametree

탐색 범위를 제한하기 위해 각 단계마다 가장 좋은 수를 3개만 살펴봐도 충분하다고 볼 수 있다. 이를 적용하기 위해서는 highfirst를 (taketree 3 . highfirst)로 바꾸기만 하면 된다.

taketree n = foldtree (nodett n) Cons Nil
nodett n label sub = Node label (take n sub)

taketree 함수는 트리의 모든 노드들이 (take n)을 이용하여 자식 노드를 최대 n 개만 가지도록 만든다. (take n)은 리스트의 처음 n 개 요소만 (n 개보다 작은 경우에는 그 만큼만) 반환한다.

가지치기를 개선하는 방법도 있다. 위 프로그램은 위치가 매우 동적인 경우에도 고정된 단계만큼 내다보기를 한다. 하지만 체스에서 여왕이 위협 받는 상황이라면 더 이상 내다볼 필요가 없다고 판단할 수도 있다. 어떤 “동적” 위치를 정의해 두고 해당 위치에서는 더 이상 내다보기를 멈추는 것이 일반적이다. dynamic이란 함수로 그런 위치를 판별할 수 있다고 가정하면 prune의 정의에 아래 내용을 추가하기만 하면 된다.

prune (n + 1) (Node pos sub)
= Node pos (map (prune n) sub), if dynamic pos

이 프로그램처럼 모듈화가 잘 된 프로그램이라면 이런 식의 수정이 쉬운 일이다. 앞에서 이미 언급했듯이 이 프로그램의 효율성은 연결 고리의 맨 마지막 함수인 maximize와 연결 고리의 첫 함수인 first 사이의 상호 연동에 의해서 크게 결정되기 때문에, 지연 평가가 없다면 한 덩어리(monolithic) 프로그램으로 작성될 수 밖에 없다. 그런 프로그램은 작성하기도 어렵고 수정하기도 어려우며 이해하기도 매우 힘들다.

6 결론

이 페이퍼에서 우리는 모듈화 수준이 성공적인 프로그래밍의 핵심이라는 점을 다뤘다. 생산성 향상을 꾀하는 언어는 프로그램의 모듈화를 잘 지원해야만 한다. 하지만 스코프 규칙이나 분할 컴파일 만으로는 충분하지 않다–모듈화 수준은 모듈 그 자체보다 더 큰 의미를 가진다. 문제를 부분으로 나눌 수 있는 수준은 부분 해결안들을 다시 결합할 수 있는 수준에 달려있다. 모듈화 프로그래밍을 지원하기 위하여 언어는 좋은 접착제를 제공해야만 한다. 함수형 프로그래밍 언어는 두 가지 새로운 접착제–고차 함수와 지연 연산–를 제공한다. 이러한 접착제를 이용하면 프로그램을 새롭고 유용한 방식으로 모듈화할 수 있으며, 우리는 그러한 예제를 여럿 살펴봤다. 더 작고, 더 일반적인 모듈은 보다 폭넓게 재사용될 수 있어서 프로그래밍을 점점 쉽게 만든다. 이것이 바로 기존 방식의 프로그램에 비하여 함수형 프로그램이 훨씬 작고 작성하기도 쉬운 이유이다. 이는 함수형 프로그래머들이 지향해야 할 목표이기도 하다. 프로그램의 어떤 부분이 지저분하고 복잡하다면 프로그래머는 그것을 모듈로 나누고 부분들을 일반화하려 노력해야 한다. 이를 위한 도구로서 고차 함수와 지연 연산의 사용을 고려해야 할 것이다.

고차 함수와 지연 연산의 힘과 우아함을 우리가 처음 이야기하는 것이 아니다. Turner는 화학적 구조를 생성하는 프로그램에서 이 둘을 이용하여 큰 효과를 보았다[3]. Abelson과 Sussman은 스트림(stream, 지연 리스트)이 프로그램 구조화의 강력한 도구임을 강조했다[1]. Henderson은 함수형 운영체제의 구조를 설계하면서 스트림을 사용했다[2]. 하지만 우리는 다른 이들에 비해 함수형 프로그램의 모듈화 가능성을 더 강조한다.

또한 이 페이퍼는 지연 연산을 두고 벌어지는 지금의 논쟁들과도 관련이 있다. 함수형 언어는 지연 연산이 기본이어야 한다고 믿는 이들이 있고, 그렇지 않은 이들도 있다. 타협점으로서 특별 문법을 통해 지연 리스트를 제공하기도 한다(예를 들어 SCHEME[1]). 이 페이퍼는, 지연 연산이 이등시민의 지위를 가지기엔 너무나 중요하다라는 추가적인 근거들을 제시한다. 지연 연산은 아마도 함수형 프로그래머가 가진 가장 강력한 접착제일 것이다. 이 필수적인 도구를 사용하지 못하게 막아선 안된다.

감사

이 페이퍼는 옥스포드 Programming Research Group의 Phil Wadler와 Richard Bird와 나눴던 대화에 많은 영향을 받았다. Chalmers University(예테보리, 스웨덴)의 Magnus Bondesson은 초기 버전의 수치 알고리즘에서 중요한 결함을 지적해줬다. Ham Richards와 David Turner가 표기를 Miranda로 고치는 등의 편집 작업을 멋지게 해줬다. U.K. Science and Engineering Research Council의 Research Fellowship 지원에 힘입어 이 일을 끝낼 수 있었다.

참고문헌

[1] Abelson, H. and Sussman, G. J. The Stucture and Interpretation of Computer Programs. MIT Press, Cambridge, Mass., 1984.

[2] Henderson, P. “Purely functional operating systems”. In Functional Programming and its Applications. Cambridge University Press, Cambridge, 1982.

[3] Turner, D. A. “The semantic elegance of applicative languages”. In ACM Symposium on Functional Languages and Computer Architecture (Wentworth, N.H.). ACM, New York, 1981.

[4] Turner, D. A. “An Overview of Miranda”. SIGPLAN Notices, December 1986 (Miranda에 대한 페이퍼들은 http://miranda.org.uk 에 있다).

[5] United States Department of Defense. The Programming Language Ada Reference Manual. Springer-Verlag, Berlin, 1980.

[6] Wirth, N. Programming in Modula-II. Springer-Verlag, Berlin, 1982.