Why functional programming matters?(왜 함수형 프로그래밍이 중요한가?)

Why Functional Programming Matters

1. 소개(Introduction)

이 문서는 함수형 프로그래밍이 실제로 매우 중요한 것이라는 점에 대해 설명하고자 하며, 아울러 함수형 프로그래밍의 장점이 무엇인지 명확히 함으로써 함수형 프로그래머에게 도움을 주고자 작성되었다.

 

함수형 프로그래밍은 말 그대로 프로그램 전체가 함수의 집합으로 이루어진 것을 말한다. 메인 프로그램은 그 자체가 프로그램의 입력 값을 인자로 하고 프로그램 결과 값을 출력 값으로 하는 하나의 함수이다. 대개 메인 함수는 다른 함수들에 의해 정의되며 그 함수들 역시 각각 또 다른 함수들에 의해 정의된다. 이러한 구조는 언어의 기초 문법으로만 구성된 최 하위 계층 함수에 이를 때까지 계속된다. 함수들은 일반적인 수학 함수와 매우 유사하다. 따라서 이 문서에서는 함수를 일반적인 등식으로 정의할 것이다. 비록 함수 정의 시Turner가 만든 Miranda라는 함수형 언어의 표기법을 사용하겠지만 함수형 언어에 대한 사전 지식이 없더라도 읽을 수 있을 것이다(역주: Miranda에 대한 보다 자세한 정보는 http://www.cs.kent.ac.uk/people/staff/dat/miranda/ 참조).

 

함수형 프로그래밍의 특징 및 장점은 대략 다음과 같다.

함수형 프로그램은 할당문(assignment statements)이 없으며 때문에 한번 변수에 지정된 값은 결코 변하지 않는다. 좀더 일반적으로 말하자면 함수형 프로그램은 부수 효과(side-effect)가 전혀 없다. 함수를 호출하면 그것의 결과값을 계산하는 것 외에 다른 효과가 발생하지 않는다. 이런 특성은 버그의 중요 원인(역주: 버그의 상당수는 작성자가 예상하지 못한 side-effect가 그 원인이다.)을 제거해 주며 실행 순서를 무시할 수 있게 해준다. – 표현식(expression)의 값을 변화시킬 소지가 있는 부수 효과(side-effect)가 없으므로 언제 표현식(expression)을 계산하더라도 상관없다.

이런 특성에 의해 프로그래머는 프로그램의 제어 흐름을 미리 정해야 하는 부담을 덜 수 있다. 또한 언제 표현식을 계산하더라도 상관없으므로 언제든지 변수 대신 값을 대체하거나 혹은 반대로 값 대신 변수를 대체할 수 있다. 이로 인해 프로그램은 “참조적으로 명백(referentially transparent)” 해진다. 그래서 함수형 프로그램은 기존의 다른 언어로 만든 프로그램보다 수학적으로 다루기 쉽다.

위에서 말한 장점들은 모두 타당하지만 – 함수형 언어를 사용하지 않는 - 다른 사람들이 이런 특성들에 대해 그다지 감동받지 않더라도 놀랄 것 없다. 위에서 우리는 – 명령형 프로그래밍이 가졌지만 - 함수형 프로그래밍이 가지지 않은 특징(할당문(assignment statement)이 없음, 부수 효과(side-effect)가 없음, 제어 흐름이 없음)에 대해서는 언급했지만 – 명령형 프로그래밍은 가지지 않았지만 - 함수형 프로그래밍이 가진 특징 에 대해서는 거의 언급하지 않았다. 함수형 프로그래머는 숭고함(virtuous)을 위해 삶의 쾌락(the pleasures of life)을 거부한 중세 수도승처럼 보인다(역주: 위에서 말한 할당문, 부수효과, 제어흐름을 삶의 쾌락에 비유했음. 즉, 지금까지 함수형 프로그래밍이 가진 장점보다 금지하고 있는 특성들에 대해 더 많은 이야기를 했다는 점에 대한 비유). 그러므로 실질적인 함수형 프로그래밍의 장점에 보다 흥미 있는 프로그래머에게는 위에서 말한 특성들이 그다지 매력적으로 들리지 않을 것이다.

 

(그럼에도 불구하고) 함수형 프로그래머들은 – 자신들의 방식이 - 매우 실질적인 장점을 가지고 있다고 주장한다. 함수형 프로그래머는 기존의 다른 프로그램에 비해 매우 짧은 소스로 프로그램을 작성할 수 있기 때문에 보다 생산적이다. 왜 이것이 가능할까? 위에서 언급한 장점에 비추어 그럴싸하게 추측하자면 기존의 다른 프로그램 소스의 90% 정도가 할당문(assignment statements)으로 구성되어 있는데 함수형 프로그램에서는 이것들이 생략되기 때문이라고 말할 수 있다. 그러나 이것은 사실 잘못된 주장이다. 만약 할당문(assignment statements)를 생략하는 것이 매우 뛰어난 장점이 된다면 포트란(FORTRAN) 프로그래머는 20년 동안 그렇게 해왔을 것이다. 게다가 논리적으로 볼 때 어떤 안 좋은 특성이라도 단지 그것을 사용하지 않는다고 해서 언어 자체를 강력하게 만들지는 않는다.

심지어 함수형 프로그래머 조차도 위에서 언급한 특징들이 함수형 언어를 사용하는데 그다지 크게 도움이 되는 것이 아니기에 그러한 특성들에 만족할 수는 없다. 어떤 프로그래머도 특별히 할당문(assignment statements)이 부족하거나 참조적으로 명백한(referentially transparent) 프로그램을 작성할 수는 없다. 이것이 프로그램의 품질을 결정하는 척도가 될 수는 없으며 따라서 이상적인 목표가 되지도 않는다.

확실히 함수형 프로그래밍의 이러한 특징들은 충분하지 않다. 우리는 단지 함수형 프로그래밍의 능력을 설명하는 것이 아니라 함수형 프로그래머가 지향해야 할 명확한 목표(indication)를 줄 수 있는 어떤 요소를 찾을 필요가 있다.

 

2. 구조적 프로그래밍과의 비교(An Analogy with Structured Programming)

함수형 프로그래밍과 구조적 프로그래밍 사이의 유사성을 도출해 보는 것은 유용하다. 과거 구조적 프로그래밍의 특징과 장점은 대략 아래와 같이 요약될 수 있다.

 

- 구조적 프로그램은 goto문을 가지지 않는다.

- 구조적 프로그램에서 블록은 다중 진입점(entries)과 탈출문(exit)를 갖지 않는다.

- 구조적 프로그램은 비 구조적 프로그램보다 수학적으로 보다 다루기 쉽다.

 

이러한 구조적 프로그래밍의 장점은 우리가 위에서 언급한 함수형 프로그래밍의 장점과 매우 유사하다. 그것들이 의미상 부정문이고 ‘goto의 필요성’에 대해 많은 의미 없는 논쟁을 불러 일으킨다는 점 등등......

좀 더 생각해 보면 – 위에서 언급한 - 구조적 프로그램의 속성들은 비록 유용하긴 하지만 문제의 핵심에서 벗어나 있다. 즉, 구조적 프로그램이 비 구조적 프로그램과 구별되는 가장 중요한 점은 구조적 프로그램이 모듈 방식(modular)으로 설계된다는 점이다. 모듈 방식(modular)으로 설계를 하면 생산성이 크게 향상된다.

첫 째, 작은 모듈은 빠르고 쉽게 코딩 할 수 있다.

둘 째, 일반적인 목적을 위해 만든 모듈은 재 사용이 가능하며 따라서 차후에 프로그램을 더 빠르게 개발하는 것이 가능하다.

셋 째, 프로그램의 모듈들은 독립적으로 테스트가 가능하며 따라서 디버깅 시간을 줄일 수 있다.

goto문을 없애는 등의 문제는 사소한 것이다. goto문 같은 것들이 조그만 프로그래밍에서는 도움이 될 지 모르나 큰 규모의 프로그래밍에서는 모듈 방식 설계가 더 유용하다. 따라서 포트란(FORTRAN)이나 어셈블리어에서도 구조적인 프로그래밍의 장점을 누릴 수 있다. 비록 – 그렇게 하지 않는 것보다 – 다소 번거로울지는 모르지만…

 

요즘은 성공적인 프로그래밍을 위해선 모듈 방식 설계를 하는 것이 일반적으로 인정받고 있으며 Modula-II, Ada 그리고 표준 ML 등과 같은 언어들은 모듈성을 향상시키는데 도움이 되는 특별한 특징들을 포함하고 있다. 그러나 종종 잊어버리기 쉬운 중요한 요소가 있다. 문제 해결을 위해 모듈 방식 프로그램을 작성할 때 우리는 먼저 문제를 여러 작은 부분으로 나누고 그렇게 나눈 문제를 해결한 다음 그 해결책들을 통합하게 된다. 이 때 최초 문제를 분리하는데 사용하는 방법은 분리한 문제를 다시 통합하기 위해 사용할 방법에 전적으로 의존하게 된다. 따라서 어떤 문제를 개념적으로 모듈화하는 능력을 향상시키려면 프로그래밍 언어에서 새로운 종류의 통합 방식(glue)를 제공해야만 한다. 복잡한 범위 규칙과 독립 컴파일 방법 등은 단지 형식적인 세부 방법으로만 쓸모가 있을 뿐이다. 이러한 것들이 문제를 분석하는데 새로운 개념적인 도구로써 사용될 수는 없다.

통합(glue)이 중요하다는 사실은 목공(carpentry)을 예로 들어서 생각할 수 있다. 의자는 각 부품 – 시트, 다리, 등받이 등등 – 을 만들고 적절하게 그것들을 조립함으로써 쉽게 만들 수 있다. 그러나 그러기 위해서는 이음새(joint)를 만들고 나무를 접착(glue)하는 기술이 필요하다. 이러한 능력이 부족하면 우리는 나무를 통째로 깎아서 만들어야 할텐데 그것은 매우 힘든 작업이 될 것이다. 위의 예는 모듈 방식으로 만드는 것의 강력함과 올바른 통합(glue)의 중요성을 말하고 있다.

 

이제 다시 함수형 프로그래밍으로 돌아와서 생각해 보자. 이 문서의 나머지 부분에서 우리는 함수형 언어가 모듈 통합(glue)을 위한 새롭고 매우 중요한 두 가지 방법을 제공한다는 점에 대해 언급할 것이다. 우리는 새로운 방법들을 이용해서 모듈화를 하고 그럼으로써 매우 단순화시킬 수 있는 많은 예제 프로그램을 보일 것이다. 이것이 함수형 프로그래밍의 핵심 능력이다. 함수형 프로그래밍을 이용하면 모듈화를 크게 향상시킬 수 있다. 이것 – 우리가 이제부터 설명할 새로운 통합 방식(glue)를 이용해서 더 작고, 더 단순하며 더 일반적인 모듈들을 만들고 그것들을 통합하는 것 – 은 또한 함수형 프로그래머가 나아가야 할 목표이기도 하다.

 

3. 함수들을 서로 통합하기(Glueing Functions Together)

두 가지 새로운 통합 방식 중 하나는 간단한 함수들을 서로 통합하여 보다 복잡한 함수로 만드는 것이다. 간단한 리스트 처리 – 리스트 요소들의 합계를 내는 – 문제를 가지고 설명하도록 하겠다. 우선 리스트를 아래와 같이 정의한다.

 

          listof X ::= nil | cons X (listof X)

 

위 문장의 의미는 (X가 무엇이든지 간에) ‘listof X는 nil(빈 리스트)이거나 혹은 cons X (listof X)이다.’ 라는 뜻이다(역주: cons는 ‘어떤 항목 하나를 리스트 첫머리에 써넣다.’라는 뜻을 가진 속어). 위 식에서 ‘cons X (listof X)’는 리스트의 첫 번째 요소가 어떤 X값이고 나머지 요소가 또 다른 X값들의 리스트인 것을 의미한다. 이 때 X는 어떤 타입이든 될 수 있다. – 예를 들어 X가 정수형(integer)이라고 한다면 이 때 정수형 리스트는 빈 리스트이거나 또는 하나의 정수 값과 나머지 정수 값들의 리스트의 합(cons)을 의미한다. 다음에 나오는 일반적인 예에서 우리는 리스트를 표기할 때 nil이나 cons를 사용하는 대신 리스트가 포함한 요소들을 대괄호로 둘러싼 형태로 표기하겠다.  이것은 표기상의 편의를 위한 간단한 축약 형태이다. 예를 들어,

 

          [] => 이것은 nil을 의미한다.

          [1] => 이것은 cons 1 nil 을 의미한다. (역주: 이것은 위 listof X 의 두번째 정의에 의하면 1 이 X 이고 nil 이 listof X 인 리스트이다.)

          [1,2,3] => 이것은 cons 1 (cons 2 (cons 3 nil)) 을 의미한다.

 

리스트의 요소들은 sum이라는 함수를 재귀적으로 사용하여 합계를 낼 수 있다. 우리는 sum을 두 가지 종류의 인자(빈 리스트(nil)와 cons)에 대해 정의해야 한다. 빈 리스트의 합계는 0 이므로 우리는 (nil 인자에 대해서) sum을 아래와 같이 정의한다.

 

          sum nil = 0

 

그리고 cons 의 합계는 리스트의 첫 번째 요소와 나머지 요소의 합계를 더하여 계산할 수 있다. 따라서 우리는 (cons 인자에 대해서) sum을 아래와 같이 정의한다.

 

          sum (cons num list) = num + sum list

 

이 정의를 자세히 살펴 보면, 아래의 네모 친 부분이 실질적으로 sum을 계산하는 특징이 되는 것을 알 수 있다.

                         +--+

sum nil = | 0 |

              +--+

 

                                         +--+

sum (cons num list) = num | + | sum list

                                         +--+

이것은 일반적인 재귀 패턴과 위에 네모 친 부분을 결합(glueing)함으로써 sum의 계산을 모듈화 할 수 있다는 것을 의미한다. 이러한 재귀 패턴을 보통 ‘reduce’ 라고 표현한다(역주: 원래 ‘reduce’는 수학에서 다항식을 풀거나 약분한다는 의미로 사용되며 우리말로는 ‘환산’이라고 번역할 수 있지만 혼란을 피하기 위해서 그냥 원문을 살렸음). 따라서sum을 아래와 같이 표현할 수 있다.

 

sum = reduce add 0

 

편의 상 reduce는 연산자 대신 두 개의 인자를 받는 add 함수를 전달 받는다(역주: 계산기 프로그램을 만들어 보면 알겠지만 일반적으로 중위 연산자보다는 전위 연산자나 함수를 처리하는 것이 더 편하다.). add는 아래와 같이 정의한다.

 

          add x y = x + y

 

sum의 정의를 매개 변수로 나타내면 아래와 같이 reduce를 도출할 수 있다.

 

          (reduce f x) nil = x

          (reduce f x) (cons a l) = f a ((reduce f x)  l)

 

위에서 괄호로 둘러싼 (reduce f x)부분은 sum을 대체했다는 것을 명확히 하기 위해 그렇게 한 것이다. 보통 괄호는 생략된다. 따라서 ((reduce f x) l)은 (reduce f x l)로 표기할 수 있다. reduce처럼 3개의 인자를 받는 함수는 먼저 2개의 인자를 처리한 결과가 나머지 하나의 인자를 처리하는 함수로 간주될 수 있다(예를 들어 reduce f x를 함수 g라고 한다면 reduce f x l 은 g(l) 이라 할 수 있다.). 일반화하면 n개의 인자를 받는 함수는 먼저 m(<n)개의 인자를 처리하고 난 결과가 나머지 인자를 처리하는 함수로 간주된다. 우리는 차후에 이 특성에 대해 다시 언급하도록 하겠다.

위의 방법으로 sum을 모듈화하게 되면 우리는 재 사용에 대한 장점을 가질 수 있다. reduce는 실로 대단히 흥미로운 요소이다. 그것을 이용하면 추가적인 프로그래밍 없이 리스트 요소들의 곱을 계산하는 함수를 작성할 수 있다.

 

          product = reduce multiply 1

 

또한 리스트의 어떤 요소가 불린(Boolean)값으로 참인지 아닌지를 판별하는 함수를 작성할 수도 있다.

 

          anytrue = reduce or false

 

또는 리스트의 모든 요소가 참인지를 판별할 수도 있다.

 

          alltrue = reduce and true

 

(reduce f a)를 이해하기 위해선 a에 nil이 들어가는 경우와 리스트의 모든 cons 요소에 대해 함수 f를 적용한 결과를 만들어 봐야 한다. 예를 들어 [1, 2, 3]이라는 리스트는 아래와 같이 표현된다.

 

          cons 1 (cons 2 (cons 3 nil)))

 

그리고 이것을 (reduce add 0)에 적용해 보면 아래와 같이 된다.

 

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

 

또한 (reduce multiply 1)에 적용하면 아래와 같이 된다.

 

          multiply 1 (multiply 2 (multiply 3 1)) = 6

 

여기서 우리는 (reduce cons nil)이 단지 리스트를 복사할 뿐이라는 것은 확실히 알 수 있다. 그리고 하나의 리스트에 다른 리스트를 덧붙이기 위해선 다른 리스트의 앞 쪽에 자신의 요소들을 추가하면 된다. 따라서 우리는 아래와 같이 정의할 수 있다.

 

          append a b = reduce cons b a

 

예를 들면 아래와 같다.

 

          append [1, 2] [3, 4]        = reduce cons [3, 4] [1, 2]

                                                  = (reduce cons [3, 4]) (cons 1 (cons 2 nil))[1]

                                                  = cons 1 (cons 2 [3, 4]))

(여기서 [3, 4]는 cons 3 (cons 4 nil)이 될 수 있다.)

                                                  = [1, 2, 3, 4]

 

모든 리스트의 요소를 두 배로 만드는 함수는 아래와 같이 작성할 수 있다.

 

          doubleall = reduce doubleandcons nil

          where doubleandcons num list = cons (2*num) list

 

doubleandcons는 좀 더 모듈화 시킬 수 있다. 먼저

 

          doubleandcons = fandcons double

          where    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 = reduce (cons . double) nil

 

이고 이에 대해서 좀 더 모듈화를 시켜보면 아래와 같이 만들 수 있다.

 

          doubleall = map double

          map f = reduce (cons . f) nil

 

이 때 map은 리스트의 모든 인자에 어떤 함수 f를 적용한다. map은 또 다른 유용한 일반화 된 함수이다.

우리는 심지어 리스트의 리스트로써 표현되는 행렬의 인자 전체를 합하는 함수를 작성할 수도 있다. 그것은 아래와 같다.

 

          summatrix = sum . map sum

 

map sum은 각각의 행에 대한 합을 내는데 사용한다. 그리고 (위 식에서) 왼쪽에 있는 sum은 전체 행렬의 합계를 내기 위해 각 행의 합계 값 리스트의 총합을 계산한다.

이 예제들을 통해 여러분은 작은 모듈화가 큰 일을 할 수 있다는 사실을 충분히 확인할 수 있다. “고차 함수(higher order function)”[2]와 몇몇 간단한 인수를 조합하여 간단한 함수를 모듈화 하게 되면 우리는 적은 노력으로 리스트를 다루는 많은 다른 함수들을 만들어 사용할 수 있다. 이것은 단지 리스트에 대한 함수뿐만이 아니다. 순서가 표시되는 트리 자료형을 다른 예로 들어 보도록 하겠다. 이 트리는 아래와 같이 정의된다.

 

          treeof X ::= node X (listof (treeof X))

 

위 식은 X의 트리가 X라고 이름 붙여진 노드와 - 역시 X들의 트리로 이루어진 - 하위 트리들의 리스트라는 것을 의미한다. 예를 들어 아래와 같은 트리는

 SHAPE  \* MERGEFORMAT

1

2

3

4

다음과 같이 표현될 수 있다.

 

          node 1

                (cons (node 2 nil)

                            (cons (node 3

                                                  (cons (node 4 nil) nil))

                                       nil))

 

우리는 예제를 검토하고 고차 함수(higher order function)로 추상화하는 대신에 바로 reduce와 유사한 redtree 함수를 다룰 것이다. reduce는 cons나 혹은nil로 대체될 수 있는 두 개의 인자를 받는다는 사실을 기억하기 바란다. 트리는 노드, cons 그리고 nil로써 이루어진다. redtree는 각각 이 세 종류 중 하나로 대체 될 수 있는 세 개의 인자를 받아야 한다. 트리와 리스트는 다른 타입이므로 각각의 타입에 따라 동작하는 함수 두 개를 정의해야 할 것이다. 따라서 우리는 아래와 같이 정의할 수 있다.

 

          redtree f g a (node label subtrees)             = f label (redtree’ f g a subtrees)

          redtree’ f g a (cons subtree rest)               = g (redtree f g a subtree) (redtree’ f g a rest)

          redtree’ f g a nil                                         = a

 

redtree와 다른 함수들을 서로 조합하면 많은 흥미로운 함수들을 정의할 수 있다. 예를 들어 숫자 트리의 모든 값들을 합하는 함수는 아래와 같다.

 

          sumtree = redtree add add 0

 

예제처럼 위에 언급한 트리 예제를 이 함수에 적용하면 아래와 같다.

 

          add 1

              (add (add 2 0)

                        (add (add 3

                                       (add (add 4 0) 0))

                             0)

          = 10

 

트리에 있는 모든 노드 값들의 리스트를 만드는 함수는 아래와 같이 정의한다.

 

          labels = redtree 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 = redtree (node . f) cons nil

 

이 모든 것은 함수형 언어가 기존의 다른 프로그래밍 언어에서는 더 이상 쪼갤 수 없는 함수들을 일반화된 고차 함수(higher order function)와 특정 상황에 맞게 정의된 함수의 조합을 통해 표현할 수 있기 때문에 가능하다. 이런 고차 함수(higher order function)는 한번 정의해 놓으면 많은 다른 기능을 쉽게 프로그래밍할 수 있도록 도와 준다. 새로운 자료 형이 정의되면 항상 그것을 처리할 수 있는 고차 함수(higher order function)를 작성해야 한다. 이렇게 하면 자료 형을 쉽게 처리할 수 있으며 그것을 표현하기 위한 세부 정보를 지역화할 수 있다. 이것은 마치 필요할 때마다 새로운 제어용 구조체를 통해 기능을 확장할 수 있는 확장 가능 프로그래밍 언어와 매우 유사하다.[3]

 

4. 프로그램을 서로 통합하기(Glueing Programs Together)

함수형 언어가 제공하는 또 다른 통합 방식으로 프로그램을 서로간에 결합하는 방법이 있다. 하나의 함수형 프로그램은 입력 값과 출력 값으로 구성된 하나의 함수라는 점을 기억하라. 만약 f와 g가 그런 프로그램이라면 그 때 (g . f)는 아래와 같이 적용될 수 있는 하나의 프로그램이 된다.

 

g (f input)

 

프로그램 f가 계산한 결과 값은 g 프로그램의 입력 값으로 사용된다. 기존의 프로그램들은 임시 파일에 f 프로그램의 결과 값을 저장하는 방식으로 이것을 구현할 수 있다. 이렇게 임시 파일을 이용하게 되면 많은 메모리를 사용해야 하므로 실용적으로 프로그램 간에 결합을 하지 못하는 있는 문제가 있다. 함수형 언어는 이러한 문제점을 해결하였다. f와 g프로그램은 엄격하게 동기화되어 실행된다. f 프로그램은 g 프로그램이 어떤 입력 값을 필요로 하는 순간부터 - f의 - 결과 값이 g에 전달이 되는 순간까지만 실행이 된다. 이 후에 f는 g가 또 다른 입력 값을 필요로 할 때까지 대기(suspend) 한다. 여기에 더 추가해서 만약 g 프로그램이 f의 모든 결과 값을 읽지 못한 상태에서 실행이 종료(terminate)되면 f 역시 종료(abort)된다. g가 종료되는 순간에 f 역시 강제적으로 종료될 수 있으므로 우리는 심지어 f를 무한히 결과 값을 출력하는 비 종료 프로그램으로 구현할 수도 있다. 따라서 종료 조건이 반복문의 몸체와 분리될 수 있으므로 강력한 모듈화가 가능하다.

위에서 언급한 방식을 이용하게 되면 f를 최대한 적은 시간만 실행시킬 수 있으며 이런 것을 ‘지연 수행(lazy evaluation)’이라고 부른다. 이 방법을 이용하면 가급적 큰 숫자를 생성하는 생성자 프로그램과 그 중 적절한 하나를 선택할 수 있는 선택자 프로그램을 모듈화하는 것이 가능하다. 비록 몇몇 다른 시스템에서 – 시스템 차원에서 - 이런 방식으로 프로그램을 연계하여 실행할 수 있긴 하지만 함수형 언어는 – 언어 차원에서 - 모든 함수 호출에 대해 정형화된 방식으로 지연 수행을 할 수 있으므로 프로그램의 각 부분을 모듈화할 수 있다.[4] 함수형 프로그래머가 가진 기술들 중 모듈화를 위한 가장 강력한 도구는 아마도 지연 수행(lazy evaluation)일 것이다.

 

4.1 Newton-Raphson의 제곱근

우리는 지연 수행(lazy evaluation)의 강력함을 설명하기 위해 몇몇 수학 알고리즘을 프로그래밍해볼 것이다. 먼저 제곱근을 찾을 때 사용되는 Newton-Raphson 알고리즘을 생각해 보겠다. 이 알고리즘은 N의 제곱근을 구하기 위해 근사치 a0를 초기값으로 하고 아래와 같은 공식을 적용해 나가면서 점점 더 정확한 제곱근 값을 계산해 나가는 방법이다.

 

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

 

만약 근사치가 어떤 극한 a에 수렴한다면 아래와 같이 유도가 된다.

 

          a = (a + N/a) / 2

          2a = a + N/a

          a = N/a

          a*a = N

          a = squeareroot(N)

 

사실 근사치는 극한에 빠르게 수렴된다. 제곱근 프로그램은 허용 오차(eps)를 가지며 두 개의 근사값이 eps보다 작은 차이를 보이게 되면 실행을 중단한다. 알고리즘은 대략 아래와 같이 작성한다.

 

          C           N IS CALLED ZN HERE SO THAT IT HAS THE RIGHT TYPE

                        X = A0

                        Y = A0 + 2.*EPS

          C           THE VALUE OF Y 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

 

기존 언어에서는 이 프로그램을 분리할 수 없다. 우리는 지연 수행을 사용하면 더 모듈화된 형태로 프로그램을 작성할 수 있다. 게다가 각 모듈이 다른 프로그램에서 사용될 수 있다는 것을 보일 것이다.

Newton-Raphson 알고리즘은 근사치를 순차적으로 계산하는 방식이므로 자연스럽게 근사치의 리스트로 표현할 수 있다. 각각의 근사치는 이전 계산 값을 함수에 적용함으로써 계산할 수 있다.

 

          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는 결과값을 무한정 출력하는 함수의 한 예이다. 그러나 실제로 이 함수는 프로그램이 필요로 하는 결과값까지만 계산을 수행하기 때문에 문제가 되지 않는다. 무한하다는 것은 단지 그럴 가능성을 가지고 있다는 것뿐이다. 다시 말하자면, 그것은 만약 필요하다면 어떤 근사값이라도 계산할 수 있다는 의미인 것이다.

제곱근 산출 프로그램의 나머지 부분은 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에 가까워 지는 것을 구하는 모듈을 만들 수 있다. 이 것은 매우 작은 수(연속된 두 근사값이 차가 너무 작은 값에서 시작하는 경우)나 매우 큰 수(반올림 오차(rounding error)가 허용 오차보다 훨씬 큰 경우)인 경우에 보다 유용하다. 우리가 수정해야 할 것은 단지 아래와 같다.

 

          relative eps (cons a (cons b rest)) =

                        = b,                                               if abs(a-b) <= eps*abs b

                        = relative eps (cons b rest),          otherwise

 

이제 sqrt의 새로운 버전은 아래와 같다.

 

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

 

근사값을 산출하는 함수는 수정할 필요가 전혀 없다.

 

4.2 수치 미분(Numerical Differentiation)

우리는 위에서 제곱근 근사치 리스트를 재 사용했었다. 물론 within이나 relative 함수 역시 다른 근사치 수열을 생성하는 수치 알고리즘을 위해 재 사용할 수 있다. 여기서는 수치 미분 알고리즘에 이것들을 재 사용하고자 한다.

미분 함수의 결과는 함수 그래프의 특정 지점에서의 기울기를 뜻한다. 이 미분 값은 주어진 어떤 지점과 그 지점에 근접한 또 다른 지점을 직선으로 연결한 기울기를 계산하여 구할 수 있다. 이것은 두 지점이 충분히 가까워 지면 함수 그래프에서 두 지점이 더 이상 곡선이 되지 않는다는 것을 가정한 것이다. 이것은 아래와 같이 정의할 수 있다.

 

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

 

정확한 근사값을 얻기 위해서는 h가 매우 작아야 한다. 그러나 불행하게도 h가 너무 작아져 버리면 f(x+h)와 f(x)가 매우 근접한 값이 되므로 뺄셈에서 반올림 오차(rounding error)가 발생하여 결과값이 잘못될 수 있다.[5] 그렇다면 h값을 어느 정도로 해야 적당할까? 이러한 모순(dilemma)을 해결하기 위한 방법 중 하나는 충분히 큰 어떤 값에서부터 점점 h값을 줄여나가면서 근사값을 계산하는 것이다. 비록 이러한 수열은 – 이론상으로 - 도함수(derivative)[6]값으로 수렴되긴 하지만 실제로는 반올림 오차(rounding error)가 발생하여 부정확한 값이 될 것이다. 만약 (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)

 

그런데 위에서 구한 방법도 근사치 수열을 너무 느리게 수렴하므로 그다지 만족스럽지 못하다. 여기서 다소 간단한 수학 공식이 도움이 될 것이다. 수열의 요소들은 아래와 같이 표현될 수 있다.

 

          the right answer + an error term involving h

 

그리고 이론상 오차 항(error term)[7]은 h의 제곱에 대략 비례하므로 h가 작아질 수록 점점 작아진다. 정확한 값이 A이고 오차항이 B * h^n 이라고 하면, 각각의 근사치는 다음 근사치를 계산하기 위해 h값을 두 번 사용하기 때문에 어떤 두 연속된 근사값은 아래와 같이 표현될 수 있다.

 

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

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

 

여기서 오차항은 제거될 수 있으므로 우리는 아래와 같이 유도할 수 있다.

               a(i+1) * 2(^n) – a(i)

          A = ------------------

                        2^n -1