| authors | title | date | license | link |
|---|---|---|---|---|
John Hughes |
Why Functional Programming Matters |
1990 |
CC BY-NC-SA 3.0 |
[cs.utexas.edu](https://www.cs.utexas.edu/~shmat/courses/cs345_spring08/whyfp.pdf) |
소프트웨어가 복잡해짐에 따라, 소프트웨어의 구조를 잘 만드는 것도 더욱 중요해지고 있다. 좋은 구조를 가진(well-structured) 소프트웨어는 작성하기 쉽고, 디버깅하기 쉬우며, 미래의 프로그래밍 비용을 줄이기 위한 재사용성 모듈도 제공해준다. 이 논문에서는 모듈화에 상당히 기여할 수 있는 함수형 언어의 두 가지 기능인 고차 함수(higher-order functions)와 지연 평가(lazy evaluation)를 제시한다. 예시로 리스트와 트리를 다루며, 여러 수치 알고리즘을 프로그래밍해보고, 알파-베타 휴리스틱(게임 프로그램에서 사용하는 인공지능 알고리즘)을 구현한다. 마지막으로 모듈화는 성공적인 프로그래밍을 위한 핵심이기 때문에 함수형 프로그래밍이 소프트웨어 개발에 중요한 이점을 제공해준다는 결론을 낸다.
이 논문은 더 많은 프로그래머(함수형 프로그래밍을 하지 않는 프로그래머) 커뮤니티에게 함수형 프로그래밍의 중요성을 보여주려는 시도이며, 함수형 프로그래머에게 함수형 프로그래밍의 장점이 무엇인지 명확히 짚어줌으로써 그 장점을 최대한 활용할 수 있도록 돕는 시도이기도 하다.
함수형 프로그래밍은 인자에 함수를 적용(application)하는 방식으로 기초적인 동작을 구성하기 때문에 함수형 프로그래밍이라고 불린다. 메인 프로그램은 그 자체로 인자를 입력으로 받아 결과를 출력으로 내는 하나의 함수다. 일반적으로 메인 함수는 다른 함수들의 관점에서 정의되며, 그 함수들은 언어의 기본 함수로 정의되는 지점까지 다른 함수들도 정의된다. 이러한 함수들은 수학에서의 함수와도 매우 유사하며, 이 논문에서는 일반적인 방정식으로 이들을 정의할 것이다. 여기에서는 터너(Turner)의 프로그래밍 언어인 미란다[4]1의 표기법을 따르지만, 미란다에 대한 구체적인 지식이 없어도 읽을 수 있다.
함수형 프로그래밍의 특성과 장점은 주로 다음과 같이 요약할 수 있다. 함수형 프로그램은 할당 구문을 사용하지 않기 때문에 변수에 한 번 값이 할당되면 절대로 변하지 않는다. 더 일반화하자면, 함수형 프로그램에는 부수 효과(side-effects)가 전혀 없다. 함수 호출은 자신의 결과를 연산하는 것 외에 다른 효과를 일으키지 않는다. 이렇게 하면 버그의 주요 원인을 제거할 수 있으며, 실행 순서를 중요하지 않게 만들 수 있다. ― 표현식의 값을 변경하는 부수 효과가 없으면 어느 시점에든 표현식을 평가할 수 있기 때문이다. 이는 프로그래머가 제어 흐름을 지정해야 하는 부담을 덜어준다. 표현식을 언제든 평가할 수 있다면, 자유롭게 변수를 값으로 대체할 수 있으며, 그 반대도 가능해진다. ― 이러한 프로그램을 "참조 투명하다"(referentially transparent)고 말한다. 이러한 자유는 함수형 프로그램을 기존의 프로그램보다 수학적으로 다루기 쉽게 만들어준다.
이러한 "장점"의 목록이 훌륭하기는 하지만, 외부인들은 이것을 진지하게 받아들이지 않는다. 이 목록은 함수형 프로그래밍이 하지 않는 것들(재할당의 부재, 부수 효과의 부재, 제어 흐름의 부재)에 대해 설명하지만, 함수형 프로그래밍 자체가 어떤 것인지에 대해서는 말하지 않는다. 함수형 프로그래머는 자신의 고결함을 위해 금욕적인 삶을 사는 중세 수도승처럼 보인다. 물질적 이득에 더 관심있는 외부인들에게 이러한 "장점"은 전혀 설득력이 없다.
함수형 프로그래머들은 대단한 물질적 이득이 있다고 주장한다. ― 함수형 프로그램의 코드가 더 짧기 때문에 몇 배나 생산적이라는 것이다. 하지만 왜 그래야 하는가? 이러한 "장점"에 기반해 제시할 수 있는 하나의 어렴풋한 이유는 기존 프로그램의 90%가 할당 구문으로 이뤄져있으며, 함수형 프로그램에서는 이 구문들을 생략할 수 있다는 점이다! 이것은 확실히 터무니없다. 만약 할당 구문을 생략하는 것이 막대한 이익을 가져다 준다면 포트란(FORTRAN) 프로그래머들은 20년간 그렇게 했을 것이다. 기능을 생략함으로써 언어가 더 강력해진다는 것은 논리적으로 불가능하며, 그 기능이 아무리 나쁜 것이라고 해도 마찬가지다.
심지어 함수형 프로그래머도 그런 장점들만으로 만족해서는 안 된다. 이것만으로는 함수형 언어의 힘을 제대로 활용하는 데 도움이 되지 않기 때문이다. 할당 구문을 사용하지 않는다거나, 참조 투명하다는 것만으로는 프로그램을 작성할 수 없다. 여기에는 프로그램 품질에 대한 척도가 없으며, 따라서 목표로 삼을 이상도 없다.
함수형 프로그래밍의 이러한 특성만으로는 분명히 부적절하다. 그 자리에 놓을 무언가를 찾아야 한다. ― 함수형 프로그래밍의 힘을 설명하는 것 뿐만 아니라 함수형 프로그래머가 지향해야 하는 분명한 지점을 알려주는 무언가 말이다.
함수형 프로그래밍과 구조적 프로그래밍의 유사점을 살펴보면 도움이 된다. 과거에 구조적 프로그래밍의 특성과 장점은 다음과 같이 요약할 수 있었다. 구조적 프로그램에는 goto 구문이 없다. 구조적 프로그램의 블록에는 여러 개의 진입점과 종료점(exits)이 없다. 구조적 프로그램은 비구조적 프로그램보다 수학적으로 다루기 쉽다. 구조적 프로그래밍의 이러한 "장점"은 앞서 언급한 함수형 프로그래밍의 "장점"과 매우 비슷하다. 둘 다 본질적으로 부정문이며, "goto의 본질"에 대한 유용한 논의를 이끌어내지 못한다.
돌이켜 생각해보면 구조적 프로그램의 이러한 특성들이 도움이 되기는 하지만, 문제의 핵심에는 다가가지 못한다는 점이 분명하다. 구조적 프로그램과 비구조적 프로그램의 가장 중요한 차이는 구조적 프로그램의 경우 모듈화된 방식으로 프로그램을 설계한다는 것이다. 모듈식 설계는 굉장한 생산성 개선을 가져다준다. 첫 번째로, 작은 모듈은 빠르고 쉽게 코딩할 수 있다. 두 번째, 범용 모듈은 재사용할 수 있으며, 이를 통해 후속 프로그램을 더욱 빨리 개발할 수 있다. 세 번째, 프로그램의 모듈은 독립적으로 테스트할 수 있어 디버깅 시간을 줄여준다.
goto가 없다는 것은 모듈화와는 거의 관련이 없다. 이는 "소규모 프로그래밍"에 도움이 되는 반면, 모듈식 설계는 "대규모 프로그래밍"에 도움이 된다. 따라서 조금의 수고를 들이면 포트란이나 어셈블리어로도 구조적 프로그래밍의 이점을 누릴 수 있다.
오늘날 모듈식 설계가 성공적인 프로그래밍의 열쇠라는 주장은 널리 받아들여진다. MODULA-II[6]나 에이다[5]와 같은 최근의 언어들은 모듈화를 위해 특별히 설계된 기능을 포함하고 있다. 하지만, 종종 놓치는 매우 중요한 점이 있다. 문제를 해결하기 위해 모듈화된 프로그램을 작성할 때는 먼저 문제를 여러 개의 부분 문제로 나눈 뒤 부분 문제를 풀고, 마지막으로 부분 문제에서 찾은 해결책들을 합친다. 원 문제를 나누는 방법은 해결책을 서로 접합하는 방법에 직접적으로 의존한다. 따라서 문제를 개념적으로 모듈화하는 수준을 높이기 위해서는 프로그래밍 언어가 새로운 종류의 접합제를 제공해야 한다. 복잡한 스코프 규칙과 분할 컴파일은 세부적인 것에만 도움이 되며, 모듈화에 직접적으로 큰 기여를 하지는 않는다.
앞으로 이 논문에서는 함수형 언어가 두 가지의 새롭고, 매우 중요한 접합제를 제공한다고 주장할 것이다. 여기에 몇 가지 프로그램을 예시로 들어 새로운 모듈화 방식과 이를 통한 간소화를 제시할 것이다. 모듈화 개선은 함수형 프로그래밍이 가진 힘의 핵심이다. 또한 더 작고 단순하며, 더 범용적인 모듈들을 새로운 접합제로 접합하는 것은 함수형 프로그래머들이 고민해야 하는 목표이기도 하다.
두 접합제 중 하나는 단순한 함수를 서로 접합해 복잡한 함수 하나를 만들 수 있게 해준다. 리스트에 요소를 추가하는 간단한 리스트 처리 예시로 설명할 수 있다. 리스트2는 아래와 같이 정의할 수 있다.
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) = num + sum list
위 정의를 살펴보면 합을 계산하는 데 특정되는 부분은 아래와 같이 꺾쇠로 감싼 부분 뿐이라는 것을 알 수 있다.
sum Nil = <0>
sum (Cons n list) = n <+> sum list
이것는 일반적인 재귀 패턴과 꺾쇠로 감싼 부분을 접합하므로써 합의 계산을 모듈화할 수 있음을 의미한다. 이 재귀 패턴은 보통 foldr라고 부르며, 이제 sum을 아래와 같이 표현할 수 있다.
sum = foldr (+) 0
foldr의 정의는 sum의 정의를 파라미터화(parameterizing)함으로써 유도할 수 있다.
(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)으로 쓸 수 있다. foldr처럼 인자가 세 개인 함수를 인자 두 개에만 적용하면 남은 인자 하나를 취하는 함수가 된다. 일반화하면, 인자가 n개인 함수를 m개 인자(m < n) 에만 적용했을 때 이 함수는 n - m개의 남은 인자를 취하는 함수가 된다. 이 논문에서는 앞으로 이러한 관례를 따를 것이다.
이렇게 sum을 모듈화하면 코드의 일부를 재사용할 수 있다. 가장 흥미로운 부분은 foldr인데, 이를 이용하면 추가적인 코드없이 리스트의 요소를 곱하는 함수를 만들 수 있다.
product = foldr (*) 1
불리언 리스트에 참(true)인 요소가 하나라도 있는지 확인할 때 사용할 수도 있다.
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는 아래와 같이 정의한다.
length = foldr count 0
count a n = n + 1
count는 0에서부터 Cons 개수만큼 증가한다. 리스트의 모든 요소의 값을 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) Nill
추가적인 모듈화로 아래와 같이 만들 수 있다.
doubleall = map double
map f = foldr (Cons . f) Nil
범용적으로 유용한 함수인 map은 리스트의 모든 요소에 함수 f를 적용한다.
행렬의 모든 요소를 더하는 함수를 작성한다면, 행렬을 리스트의 리스트로 표현하면 된다.
summatrix = sum . map sum
함수 map sum은 sum을 사용해 모든 행을 더하며, 맨 왼쪽의 sum은 모든 행의 합을 계산하여 전체 행렬의 합을 구할 수 있다.
이러한 예시를 통해 작은 모듈화가 긴 과정으로 이어진다는 것을 충분히 알 수 있다. 간단한 함수(sum)를 "고차 함수"(higher-order function)와 간단한 인자들의 조합으로 모듈화함으로써, 추가적인 프로그래밍 노력없이 다른 함수를 작성하는 데 사용할 수 있는 부품(foldr)을 만들 수 있다.
리스트에 대한 함수에서 그치지 않는다. 또 다른 예시를 통해 순서 레이블 트리(ordered labeled tree) 데이터 타입을 살펴보자. 아래와 같이 정의한다.
treeof * ::= Node * (listof (treeof *))
이 정의는 *의 트리가 노드이며, 노드는 *을 레이블로 가지고, 하위 트리의 리스트 역시 *의 트리임을 말해준다. 예를들어 아래와 같은 트리를 생각해보자.
1
/ \
2 3
|
4
이 트리는 아래와 같이 표현할 수 있다.
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))
= 10
트리에 있는 모든 레이블을 리스트로 만드려면:
labels = foldtree Cons append Nil
같은 예시에 적용하면:
Cons 1
(append (Cons 2 Nil)
(append (Cons 3
(append (Cons 4 Nil) Nil))
Nil))
= [1, 2, 3, 4]
마지막으로, 트리에 있는 모든 레이블에 함수 f를적용하기 위해 map과 유사한 함수를 정의할 수 있다.
maptree f = foldtree (Node . f) Cons Nil
이 모든 것이 성립 가능한 이유는 함수형 언어가 전통적인 프로그래밍 언어에서는 분리할 수 없는 함수들을 범용적인 고차 함수와 일부 특수 함수의 조합으로 표현할 수 있도록 해주기 때문이다. 고차 함수를 한 번 정의해두면 많은 연산을 매우 쉽게 프로그래밍할 수 있다. 새로운 데이터 타입이 정의할 때마다 이를 처리하기 위한 고차 함수를 작성해야 한다. 이는 데이터 타입을 쉽게 다룰 수 있도록 해주며, 데이터 타입에 대한 표현의 상세 정보가 한 곳에 모여 지역화(localize)할 수 있게 해준다. 기존 프로그래밍 언어와 가장 유사한 점은 확장 가능한 언어(extensible language)다. ― 프로그래밍 언어가 필요할 때마다 새로운 제어 구조로 확장될 수 있기 때문이다.
함수형 언어가 제공하는 또 다른 접합제는 프로그램을 서로 접합하도록 해준다. 완전한 함수형 프로그램은 입력과 출력이 있는 함수라는 것을 기억하자. 만약 f와 g가 각각 프로그램이라면, (g . f) 역시 프로그램이다. 입력값에 이를 적용하면 아래와 같다.
g (f input)
프로그램 f의 출력은 프로그램 g의 입력이 된다. 이는 전통적으로 f의 출력을 임시 파일에 저장하는 방식으로 구현할 수 있다. 그런데 프로그램을 서로 접합하는 데 임시 파일을 사용하기에는 임시 파일이 메모리를 너무 많이 점유한다는 문제가 있다. 함수형 언어는 이러한 문제의 해결책을 제공한다. 두 프로그램 f와 g를 엄격하게 동기화하여 실행하는 것이다. 프로그램 f는 g가 입력을 읽으려 할 때만 시작되며, g가 읽고자하는 출력을 전달할 때까지만 실행된다. 이어서 f는 중지(suspended)되고, g는 또 다른 입력을 읽을 때까지 실행된다. 여기에 추가로, 만약 g가 f의 출력을 모두 읽지 않고 종료된다면 f도 종료(aborted)된다는 이점이 있다. 심지어 프로그램 f는 g의 종료를 통해 강제 종료할 수 있기 때문에 무한한 출력을 내는 비종료 프로그램이 될 수도 있다. 이를 통해 종료 조건을 루프 본문(body)에서 분리할 수 있으며, 이는 강력한 모듈화로 이어진다.
이러한 평가 방식은 f의 실행을 최소화하기 때문에 "지연 평가"(lazy evaluation)이라고 부른다. 이를 통해 프로그램을 많은 수의 응답을 만들어내는 생성자(generator)와, 적절한 응답 하나를 선택하는 선택자(selector)로 모듈화할 수 있다. 다른 시스템에서도 이런 방식을 따라 프로그램을 함께 실행할 수 있지만, 오직 함수형 언어만이(심지어 그 중에서도 일부만이) 모든 함수 호출에 대해 일관된 지연 평가를 사용하며, 이를 통해 프로그램의 어떠한 부분이라도 모듈화할 수 있다. 지연 평가는 함수형 프로그래머의 도구 중에서도 가장 강력한 모듈화 도구일 것이다.
앞서 함수영 언어의 맥락에서 지연 평가를 설명했는데, 이렇게 유용한 기능인 지연 평가를 비함수형 언어에도 추가할 수 있는가? 지연 평가와 부수 효과가 공존할 수 있는가? 안타깝게도 그럴 수 없다. 사실 지연 평가를 명령형(imperative) 언어에 추가하는 것이 불가능하지는 않다. 그러나 지연 평가와 명령형 언어의 조합은 프로그래머의 삶을 개선하기 보다는 어렵게 만들 것이다. 지연 평가의 힘은 프로그램의 특정 부분에 대한 실행 순서를 프로그래머가 직접 제어하지 않음으로써 발휘된다. 따라서 부수 효과가 있는 프로그램에서 지연 평가는 프로그래밍을 더 어렵게 만들 수 있는데, 이는 부수 효과의 실행 순서 또는 실행 여부를 예측하기 위해 부수 효과를 포함하는 맥락에 대해 많은 것을 알아야 하기 때문이다. 그러한 전역 상호 의존성은 함수형 언어가 지연 평가를 통해 개선하고자 하는 모듈화를 오히려 악화시킨다.
수치 알고리즘을 프로그래밍함으로써 지연 평가의 힘을 설명할 것이다. 첫 번째로, 제곱근을 찾기 위한 뉴턴-랩슨 알고리즘을 살펴보자. 이 알고리즘은 어떤 수 n의 제곱근을 찾기 위해 초기 근삿값 a0부터 시작하여 아래 규칙에 따라 점점 더 나은 근삿값을 계산한다.
만약 근삿값이 어떤 극한값 a로 수렴한다면:
따라서
실제로 근삿값은 빠르게 극한으로 수렴한다. 제곱근 프로그램에는 허용오차(eps)가 주어지며, 이웃한 두 근삿값의 차이가 eps보다 작아지면 프로그램을 멈춘다.
뉴턴-랩슨 알고리즘은 보통 아래와 같이 프로그래밍한다.
C N은 여기서 ZN이라고 부르므로 올바른 타입을 갖는다
X = A0
Y = A0 + 2. * EPS
C ABS(X-Y).GT.EPS라면 Y의 값은 중요하지 않다
100 IF ABS(X-Y).LE.EPS GOTO 200
Y = X
X = (X + ZN/X) / 2.
GOTO 100
200 CONTINUE
C ZN의 제곱근은 이제 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)
이제 제곱근 근사 프로그램의 부품을 모두 얻었고, 조금 다른 방법으로 이들을 합칠 수 있게 되었다. 먼저 이웃한 두 근삿값의 비율이 0 대신 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)
근삿값을 생성하는 부분은 다시 작성할 필요가 없다.
앞에서는 제곱근을 근사하기 위해 근사값 리스트를 재사용했다. 물론 within과 relative를 근삿값 리스트를 생성하는 다른 수치 알고리즘에 재사용하는 것도 가능하다. 이제 수치 미분 알고리즘에서 이를 재사용해볼 것이다.
어떤 점에서 함수를 미분한 결과는 해당 점에서의 함수 그래프 기울기다. 이 값을 추정하려면 주어진 점과 이웃한 또 다른 점에서 함수 값을 구하고, 두 점을 이은 직선의 기울기를 계산하면 쉽게 할 수 있다. 이 방식은 두 점이 충분히 가까워서 두 점 사이의 함수 그래프에 곡선이 거의 없음을 가정한다. 아래와 같이 정의할 수 있다.
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의 초기값이며, 반복적으로 반감(halving)하며 값을 만든다. 이 함수를 이용해 어떤 점에서의 미분계수를 아래와 같이 구할 수 있다.
within eps (differentiate h0 f x)
근사값 수열이 천천히 수렴하기 때문에 이 방법도 아주 만족스럽지는 않다. 간단한 수학이 여기에 도움을 줄 수 있다. 수열의 요소를 아래와 같이 표현할 수 있다.
올바른 해 +
h를 포함하는 오차항
이론적으로 오차항의 값은 대략 h의 제곱에 비례하기 때문에 h가 작아질수록 오차항도 작아진다. 올바른 해를 h 값은 다음 근삿값을 계산할 때 사용하는 값보다 두 배 크므로, 이웃한 두 근삿값을 아래와 같이 표현할 수 있다.
또한
이제 오차항을 제거할 수 있다. 결론적으로:
물론 오차항이 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 = x에 대해 밑이 2인 로그
이제 근삿값 수열을 개선하는 일반화된 함수를 정의할 수 있다.
improve s = elimerror (order s) s
함수 f의 미분계수는 아래와 같이 improve를 이용하여 더욱 효율적으로 계산할 수 있다.
within eps (improve (differentiate h0 f x))
함수 improve는 근삿값을 계산할 때마다 반감하는 h 인자로 계산한 근삿값 수열에 대해서만 동작한다. 그러한 수열에 improve 함수를 적용해도 결과는 수열이 된다! 즉, 근삿값 수열을 한 번 이상 개선할 수 있다는 의미다. 오차항을 제거할 때마다 수열은 더 빠르게 수렴한다. 따라서 아래와 같이 미분계수를 매우 효율적으로 계산할 수 있다.
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만큼 복잡한 알고리즘도 쉽게 표현할 수 있다는 점이다.
이 섹션에서 설명할 마지막 예시는 수치 적분이다. 문제는 단순하다: 하나의 실수 인자를 받는 함수 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는 또 다른 표준 리스트 처리 함수다. 이 함수는 두 개의 리스트를 받아 리스트 페어(pair)를 반환하며, 각 페어는 두 리스트의 요소들로 구성된다. 따라서 첫 번째 페어는 첫 번째 리스트의 첫 번째 요소와 두 번째 리스트의 첫 번째 요소로 구성된다. zip2는 아래와 같이 정의한다.
zip2 (Cons a s) (Cons b t) = Cons (a, b) (zip2 s t)
integrate에서 zip2는 두 부분구간(subinterval)의 적분값에 각각 대응하는 근삿값들의 페어를 만든다. map addpair는 각 페어의 요소를 서로 더해 원본 적분값에 대한 근삿값 리스트를 만든다.
사실, 앞서 만든 버전의 integrate는 f 값을 계속 다시 계산하기 때문에 비효율적이다. 위에서 작성한 것처럼 easyintegrate는 점 a에서의 f와 점 b에서의 f를 계산하며, integrate를 재귀 호출함으로써 두 값을 매번 다시 평가한다. 또한 (f mid) 역시 매 재귀 호출마다 평가한다. 따라서 아래와 같이 f 값을 다시 계산하지 않는 버전의 integrate를 사용하는 것이 좋겠다.
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에 대한 다섯 번의 평가만을 필요로하며, 이는 소수점 아래 다섯 자리까지 정확하다.)
이 섹션에서는 여러 수치 알고리즘을 살펴보고, 이러한 알고리즘들의 부품을 접합하기 위한 접합제로 지연 평가를 사용하여 함수형으로 프로그래밍해 보았다. 이 덕분에 within, relative, improve와 같이 범용적으로 유용한 함수를 만들어 새로운 방식으로 모듈화를 할 수 있었다. 이 부품들을 다양한 방식으로 합침으로써 매우 간단하고 쉽게 상당히 좋은 수치 알고리즘을 만들 수 있었다.
앞서 함수형 언어가 두 가지 새로운 접합제인 고차 함수와 지연 평가를 제공하기 때문에 강력하다고 주장했다. 이 섹션에서는 더 큰 예시인 인공지능을 통해 두 접합제를 이용하여 어떻게 인공지능을 쉽게 프로그래밍할 수 있는지 보인다.
여기서 선택한 예시는 알파-베타 휴리스틱이다. 이는 게임에서 좋은 위치를 추정하기 위한 알고리즘이다. 이 알고리즘은 게임이 어떻게 전개될지 내다보는 방식으로 작동하며, 이득이 되지 않는 선택을 피한다.
게임에서의 위치를 position 타입 객체로 표현하자. 이 타입은 게임에 따라 다를 것이며, 여기서 타입에 대해서는 어떠한 가정도 하지 않을 것이다. 특정 위치에서 움직일 수 있는 다음 위치에 대해 알 수 있는 방법이 필요한데, 그러한 함수를 아래와 같이 가정한다.
moves :: position -> listof position
이 함수는 게임 위치를 인자로 받고, 한 번의 이동으로 도달할 수 있는 모든 위치의 리스트를 반환한다. 예시로 든 그림 1은 틱택토(tic-tac-toe)에서 두 위치에 대한 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: 틱택토 게임 트리의 일부분.
알파-베타 알고리즘은 주어진 위치를 바탕으로 게임이 유리하게 진행될지 불리하게 진행될지 내다보는 방법이지만, 이를 위해서는 더 내다보지 않고 특정 위치의 가치를 대략적으로 추정할 수 있어야 한다. 이러한 "정적 평가"(static evaluation)는 미리 내다보는 과정의 마지막에 사용해야 하며, 알고리즘 초기에 가이드로 사용할 수도 있다. 정적 평가의 결과는 컴퓨터 플레이어 관점에서 해당 위치가 얼마나 가치있는가에 대한 측정치다. (컴퓨터가 사람을 상대로 게임을 플레이한다고 가정한다.) 결과 값이 클수록 컴퓨터에게 유리한 위치이며, 작을수록 불리한 위치가 된다. 가장 간단한 정적 평가 함수는 컴퓨터가 유리하게 선점한 위치에 대해서는 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 함수는 각각 숫자 리스트에서 최댓값과 최솟값을 반환한다. 위의 정의는 재귀 호출을 무한히 반복하기 때문에 완전하지는 않다. ― 베이스 케이스(base case)가 없다. 하위 노드가 없는 경우에도 노드의 값을 결정할 수 있도록 정의해야 하며, 이 경우에는 노드의 정적 평가 가치(노드의 레이블)를 값으로 결정한다. 따라서 정적 평가는 두 플레이어 중 하나가 이미 승리했거나, 게임 진행을 미리 내다보는 과정의 마지막에 사용한다. maximize와 minimize의 완전한 정의는 아래와 같다.
maximize (Node n Nil) = n
maximize (Node n sub) = max (map minimize sub)
minimize (Node n Nil) = n
minimize (Node n sub) = max (map maximize sub)
이 단계에서 어떤 위치를 받아 해당 위치의 진짜 가치를 반환하는 함수를 거의 작성할 수 있다.
evaluate = maximize . maptree static . gametree
이 정의에는 두 가지 문제가 있다. 첫 번째는 무한한 트리에 대해 동작하지 않는다는 점이다. maximize가 하위 노드가 없을 때까지 재귀 호출을 반복하기 때문이다. ― 즉, 트리의 끝까지 반복한다. 만약 트리에 끝이 없다면 maximize 함수는 결과를 반환하지 않을 것이다. 두 번째 문제도 관련이 있다. ― 심지어 유한한 게임 트리(틱택토와 같은 게임)도 매우 커질 수 있다. 게임 트리 전체를 평가하려는 것은 현실적이지 않다. ― 다음 몇 번의 이동만 탐색하도록 제한이 있어야 한다. 트리를 정해진 깊이까지 가지치기(pruning)하면 된다.
prune 0 (Node a x) = Node a Nil
prune (n + 1) (Node a x) = Node a (Map (prune n) x)
함수 prune n은 트리를 받아 루트에서 n보다 멀리 있는 모든 노드를 잘라낸다. 만약 게임 트리가 가지치기 되면 더 이상 순회하지 않고 깊이 n에 있는 노드를 정적 평가하기 위한 maximize가 강제된다. 따라서 함수 평가는 아래와 같이 정의할 수 있다.
evaluate = maximize . maptree static . prune 5 . gametree
이는 이동을 다섯 단계까지 내다본다.
여기까지 개발하면서 이미 고차 함수와 지연 평가를 사용했다. 고차 함수 reptree와 maptree는 게임 트리를 쉽게 구축하고 조작할 수 있도록 해준다. 더 중요한 것은 지연 평가가 이러한 방식으로 evaluate를 모듈화할 수 있도록 만들어 줬다는 것이다. gametree가 잠재적으로 무한한 결과를 낼 수 있기 때문에, 이 프로그램은 지연 평가 없이는 절대로 종료되지 않을 것이다. 지연 평가가 없다면 아래와 같이 작성하는 대신:
prune 5 . gametree
두 함수를 하나로 합쳐(fold) 트리를 처음부터 다섯 단계까지만 구축해야 했을 것이다. 심지어 처음 다섯 단계도 너무 커서 메모리에 한번에 올리지 못할 수 있다. 여기서 작성한 프로그램에서 아래 코드는:
maptree static . prune 5 . gametree
maximize가 필요로하는 만큼의 트리만을 구축한다. 각 부분은 maximize가 완료되자마자 버려져도(가비지 컬렉터에 의한 회수) 상관없기 때문에 트리 전체가 메모리가 올라갈 일은 없다. 오직 트리의 작은 일부만 한번에 저장된다. 따라서 지연 프로그램은 효율적이다. 이러한 효율은 maximize(합성 체인의 마지막 함수)와 gametree(첫 번째 함수) 사이의 상호작용에 따른 것이다. 지연 평가가 없이 이러한 효율을 달성하려면 체인의 모든 함수를 하나의 큰 함수로 합칠 수 밖에 없다. 이러한 방식은 모듈화를 방해하지만, 빈번히 일어난다. 각 부분을 손질함으로써 비교적 쉽게 평가 알고리즘을 개선할 수 있다. 전통적인 프로그래머는 전체 프로그램을 한 단위로 수정해야 하는데, 이는 훨씬 어렵다.
지금까지는 간단한 최소최대(minimaxing) 알고리즘만 설명했다. 알파-베타 알고리즘의 핵심은 트리 전체를 보지 않고도 maximize와 minimize가 반환하는 값을 계산할 수 있는 경우가 있다는 것이다. 아래와 같은 트리를 생각해보자.
max
/ \
/ \
/ \
/ \
min min
/ \ / \
/ \ / \
1 2 0 ?
이 트리를 평가하기 위해 물음표의 값을 알 필요는 없다. 왼쪽의 최솟값은 1로 평가되지만, 오른쪽의 최솟값은 최대 0으로 평가된다. 따라서 두 최솟값의 최댓값은 1이어야 한다. 이 관찰을 일반화해 maximize와 minimize에 반영할 수 있다.
첫 번째 단계는 maximize를 숫자 리스트에 대한 max의 적용으로 분리하는 것이다. maximize를 아래와 같이 분해한다.
maximize = max . maximize'
(minimize도 비슷한 방식으로 분해한다. minimize와 maximize는 전체적으로 대칭적이므로 여기에서는 maximize만 논하며, minimize도 비슷하게 다룬다고 전제한다.) 이러한 방식으로 분해하고 나면, maximize는 minimize 자체를 사용하는 대신 minimize'를 사용함으로써 minimize가 어떤 숫자들에서 최솟값을 얻으려 했는지 알 수 있다. 이제 모든 값을 확인하지 않고 일부를 소거할 수 있다. 지연 평가 덕분에 maximize가 모든 리스트의 모든 값을 확인하지 않는다면 일부는 계산되지 않을 것이며, 이를 통해 계산 시간을 줄일 수 있을 것이다.
maximize의 정의에서 max를 "인자로 빼내는 것"(factor out)은 쉽다.
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'는 해당 리스트의 최솟값을 반환해야 한다. 그러나 이 리스트의 최댓값만이 중요하다. 여기에서는 중요하지 않은 리스트를 생략하는 새로운 버전의 mapmin을 정의할 것이다.
mapmin (Cons nums rest)
= Cons (min nums) (omit (min nums) rest)
함수 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'를 정의하고 나면 새로운 평가자(evaluator)를 작성하는 것이 쉽다.
evalute = 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는 리스트의 첫 n개 요소(리스트가 n보다 짧다면 더 적은 요소)를 반환하는 함수 (take n)을 이용해 트리의 모든 노드가 최대 n개의 하위 노드만 갖도록 만든다.
또 다른 개선점은 가지치기를 다듬는 것이다. 위 프로그램은 위치가 매우 동적일 때도 고정된 깊이를 내다본다. ― 가령 체스에서 퀸이 위협받는 위치가 있다면 더 멀리 내다보지 않기로 결정할 수 있다. 특정 "동적" 위치를 정의하고 그 위치에서는 더 이상 내다보지 않는 것이 일반적이다. dynamic 함수로 그러한 위치를 식별할 수 있다고 한다면, prune에 하나의 정의만 추가하면 된다.
prune 0 (Node pos sub)
= Node pos (map (prune 0) sub), if dynamic pos
잘 모듈화된 프로그램에서는 이러한 변경이 쉽다. 앞서 언급했듯이 프로그램의 효율성이 체인의 마지막 함수인 maximize와 체인의 첫 함수인 gametree 사이의 상호 작용에 결정적으로 의존하기 때문에 지연 평가가 없이는 프로그램을 한 덩어리(monolithic)로 작성할 수 밖에 없다. 그러한 프로그램은 작성하기도 어렵고, 수정하기도 어려우며, 이해하기도 매우 어렵다.
이 논문에서는 모듈화가 성공적인 프로그래밍의 핵심이라고 주장했다. 생산성에 초점을 맞춘 언어들은 모듈러 프로그래밍을 잘 지원해야 한다. 그러나 새로운 스코프 규칙이나 분할 컴파일 매커니즘만으로는 충분치 않다. ― 모듈화는 모듈 자체보다 많은 것을 의미한다. 문제를 분리해 쪼개는 능력은 해결책을 서로 접합하는 능력에 직접적으로 의존한다. 모듈러 프로그래밍을 지원하기 위해 언어는 좋은 접합제를 제공해야 한다. 함수형 프로그래밍 언어는 고차 함수와 지연 평가라는 새로운 두 종류의 접합제를 제공한다. 이 두 접합체를 이용해 새롭고 유용한 방법으로 프로그램을 모듈화할 수 있으며, 이 논문에서 그러한 예시를 보인 바 있다. 작고 범용적인 모듈은 광범위하게 재사용할 수 있으며, 후속 프로그래밍을 쉽게 만든다. 이것은 기존 프로그램보다 함수형 프로그램이 왜 훨씬 작고 작성하기 쉬운지 알려준다. 이는 함수형 프로그래머들이 중점을 두는 것이기도 하다. 만약 프로그램의 일부가 지저분하거나 복잡하다면, 프로그래머는 프로그램을 모듈화하고 일부분을 범용적으로 사용할 수 있도록 개선해야 한다. 이를 위해 프로그래머는 고차 함수와 지연 평가를 도구로 사용할 수 있음을 염두에 둬야 한다.
물론 고차 함수 및 지연 평가의 우아함과 힘을 이야기하는 것이 이 논문이 처음은 아니다. 예를 들어 터너는 두 특성을 화학적 구조를 생성하는 프로그램에 사용할 때 큰 이점이 있음을 보였다[3]. 아벨슨(Abelson)과 서스먼(Sussman)은 스트림(stream, 지연 리스트)이 프로그램을 구조화하기 위한 강력한 도구라고 강조한다[1]. 핸더슨(Henderson)은 함수형 운영 체제를 구조화하기 위해 스트림을 사용했다[2]. 이 논문에서는 앞선 저자들에 비해 함수형 프로그램의 모듈화에 더 주안점을 두었다.
또한 이 논문은 지연 평가를 두고 벌어지는 현재의 논쟁과도 관련이 있다. 어떤 이들은 함수형 언어들이 지연 연산을 해야 한다고 믿으며, 어떤 이들은 그렇지 않다고 믿는다. 그 타협점으로, 지연 리스트만을 제공하는 특별한 문법으로 이를 구축하기도 한다. (가령, SCHEME[1]). 이 논문은 지연 평가를 부차적인 것(second-class citizenship)으로 두기에는 너무나도 중요하다는 추가 증거들을 제시한다. 지연 평가는 함수형 프로그래머들이 가진 가장 강력한 접합제일 것이다. 이와 같은 필수적인 도구에 접근하는 것을 방해해서는 안 된다.
이 논문은 옥스포드 프로그래밍 연구 그룹(Programming Research Group at Oxford)의 필 워들러(Phil Wadler)와 리처드 버드(Richard Bird)와 나눈 많은 대화에 영향을 받았습니다. 예테보리 샬머스 대학교(Chalmers University, Göteborg)의 마그누스 본데슨(Magnus Bondesson)은 수치 알고리즘의 초기 버전에서 심각한 오류를 지적해줬고, 덕분에 다른 알고리즘을 개발하는 데 도움을 줬습니다. 햄 리처드(Ham Richards)와 데이비드 터너(David Turner)는 표기법을 미란다로 변경하는 등 훌륭한 편집 작업을 했습니다. 이 연구는 영국 과학기술 연구 위원회(U.K. Science and Engineering Research Council)에서 연구 펠로십 지원을 받았습니다.
- [1] Abelson, H. and Sussman, G. J. The Structure 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 (이 글을 비롯해 미란다에 대한 다른 논문은 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.