함수형 프로그래밍

함수형 프로그래밍이란 무엇인가?

이 튜토리얼이 꽤 진행되었지만 아직도 함수형 프로그래밍을 진짜로 고려해보지 않았다. 지금 까지 살펴본 기능들-풍부한 자료형, 패턴 매칭, 타입 추론, 중첩 함수-은 "슈퍼 C" 언어에도 있을지도 모를 그런 기능들이다. 물론 멋진 기능들이며, 코드를 간략하고, 읽기 쉽고, 그리고 버그가 적게 만들어 주지만 사실 함수형 프로그래밍과는 별로 상관이 없다. 사실 함수형 언어가 그렇게 멋진 이유는 함수형 프로그래밍에 있는 것이 아니고 우리가 C-같은 언어에 몇 년동안 머물러있었기 때문이다. 그 동안 프로그래밍의 최첨단은 많은 진전을 이루었다. 그래서 우리가 struct { int type; union { ... } } 이라고 수 없이 코드를 작성하는 동안 ML이나 Haskell프로그래머들은 "safe variant"와 자료형에 대한 패터 매칭을 사용했다. 우리가 malloc한 메모리를 모두 free하기위해 애쓰는 동안 80년대 부터 가비지 콜렉션을 사용하여 손으로 작성한 코드를 능가하였다.

어쨌던, 함수형 프로그래밍에 대해 애기를 계속해야겠다.

기본적이고 별로 멋지지도 않은 정의는 다음과 같다: 함수형 언어에서 함수는 일등 시민이다.

별로 와닿지 않는 말이다. 그렇다면 예를 들어보자:

# let double x =
    x * 2
  in
  List.map double [ 1; 2; 3 ];;
- : int list = [2; 4; 6]

이 예에서 double이라는 중첩된 함수를 선었했다.이 함수는 x를 인자로 받아 x * 2를 반환한다. 함수 map은 리스트 ([1; 2; 3])의 각 원소에 double를 적용한다. 그 결과는: 각 원소가 2배가 된 리스트.

map 함수는 higher-order function (HOF)라고 한다. Higher-order functions 는 함수를 인자로 받는 함수를 멋지게 표현한 것이다.

지금까지는 아주 간단하다. 만일 C/C++언어에 익숙하다면 단지 함수 포인터를 전달하는 것과 비슷해 보일것이다. Java는 "익명 클래스(anonymous class)"라고 하는 좀 혐오스러운 수준 낮고, 느리며, 긴 클로져(closure)가 있다. 만일 Perl을 알고 있다면 Perl의 클로져(closure)와 map 함수를 아마 이미 알고 있고 사용해보았을 것이다. 바로 우리가 이야기 하고 있는 것이 그것이다. 사실 Perl은 꽤 훌륭한 함수형 언어이다.

클로져(Closures)는 자신이 정의된 "환경"의 일부를 동반하고 있는 함수이다. 특히 클로져는 정의된 시점에서 참조할 수 있었던 변수들을 사용할 수 있다. 위의 함수를 일반화 하여 임의의 정수형 리스트를 받아서 임의의 값(n)을 각 원소에 곱하는 함수를 만들어 보자:

let multiply n list =
  let f x =
    n * x
  in
  List.map f list
  ;;

그러므로

# multiply 2 [1; 2; 3];;
- : int list = [2; 4; 6]
# multiply 5 [1; 2; 3];;
- : int list = [5; 10; 15]

multiply 함수에 있어서 주목할 점은 중첩된 함수 f이다. 이 함수는 클로져이다. 함수 f가 어떻게 인자로 전해지지 않은 nf 내에서 참조하는지 살펴보자. 함수 fn를 인자로 넘겨받는 대신에 환경에서 읽어온다. nmultiply 함수의 인자이며 따라서 multiply 내에서 사용가능하다.

매우 자명해 보인다. 하지만 map을 호출하는 것을 자세히 살펴보자: List.map f list.

map함수는 List 모듈에서 정의되어있으며, 이 모듈은 지금 코드와는 동떨어져 있다. 즉 우리는 f 함수를 "아주 오래전에, 은하계 먼 곳에서" 정의된 모듈에게 넘겨주는 것이다. 우리가 알고있는 사실은 함수 f를 다른 모듈에 넘겨줄 수 도 있고, 혹은 f에 대한 참조를 어딘가에 저장했다가 나중에 호출할 수 있다는 사실 뿐이다. 그렇게 하던 혹은 하지 않던 클로져에 의해서 함수 f는 항상 부모 환경에 접근할 수 있으며, 따라서 n를 항상 사용할 수 있다.

liblgtk에서 발취한 실례를 살펴보자. 이것은 사실 어떤 클래스의 매소드이다(아직 클래스나 객체에 대해서는 언급하지 않았지만 지금은 하나의 함수 정의로 단순히 생각하자).

class html_skel obj = object (self)
  ...
  ...
  method save_to_channel chan =
    let receiver_fn content =
      output_string chan content;
      true
    in
    save obj receiver_fn

우선 함수 save 매소드의 마지막에 호출되는데, 그 두번째 인자로서 함수 (receiver_fn)를 사용한다. receiver_fn 함수는 저장하고자 하는 위젯(widget)의 문자 일부를 인자로 반복적으로 호출된다.

이제 함수 receiver_fn의 정의를 살펴보자. 이 함수는 클로져이다. 왜냐하면 환경으로 부터 chan에 대한 참조를 가지고 있기 때문이다.

부분 함수 적용과 커링

두 정수를 더하는 더하기 함수 plus를 정의해보자:

let plus a b =
  a + b
  ;;

수업 시간에 졸았던 사람을 위해서 몇 가지 질문을 하겠다

  1. plus는 무엇인가는?
  2. plus 2 3는 무엇인가는?
  3. plus 2는 무엇인가는?

질문 1은 쉽다. plus 은 함수이다. 이 함수는 두 개의 정수를 인수로 받고 정수를 반환한다. 유형(타입:type)은 다음과 같다:

plus : int -> int -> int

질문 2 는 더 쉽다. plus 2 3 는 숫자이며, 그 값은 정수로5이다. 값과 유형은 다음과 같다:

5 : int

그렇다면 질문 3의 답은 무엇인가? 마치 plus 2 는 실수이거나 버그같다. 그러나 사실은 그렇지 않다. 만일 OCaml 인터프리터에서 입력한다면 다음과 같은 결과를 얻을 것이다:

# plus 2;;
- : int -> int = 

이것은 전혀 오류가 아니다. OCaml은 plus 2 가 사실은 함수라고 애기한다. 이 함수는 int를 받아서 int를 반환하는 함수이다. 그렇다면 이 함수는 과연 어떤 함수인가? 일단 실험을 해 보자. 이 이상한 함수를 (f라고)이름을 붙이고, 몇가지 정수 값을 주어서 무슨 일이 일어나는지 살펴보자:

# let f = plus 2;;
val f : int -> int = 
# f 10;;
- : int = 12
# f 15;;
- : int = 17
# f 99;;
- : int = 101

공학적으로 이 실험은 plus 2가 2를 더하는 함수라고 애기해도 충분하다.proof by example

다시 처음의 함수 정의로 돌아가보자. 첫번째 인수 (a) 를 2로 대입하면:

let plus 2 b =       (* This is not real OCaml code! *)
  2 + b
  ;;

plus 2 가 2를 더하는 함수인지 알 수 있을 것이다.

다음의 표현식들의 유형을 살펴보면 함수 유형에 사용되는 요상한 -> 화살표에 대한 논리를 알 수 있을 것이다:

    plus : int -> int -> int
  plus 2 : int -> int
plus 2 3 : int

이러한 과정은 커링(currying)이라고 불린다 (혹은 아마도 언커링(uncurrying)이라고 불릴 것이다. 어느게 어느건지 정확히 잘 모르겠다). 이 이름의 유래는 헤스켈 커리(Haskell Curry)라는 수학자의 이름에서 유래되었는데 그는 람다 칼큐러스(lambda calculus)로 관련된 몇가지 중요한 업적을 이루었다. OCaml과 관련된 수학은 매우 따분하여 이 튜토리얼하고는 별로 상관이 없기 때문에 더 이상 깊이 들어가지는 않겠다. 커링에 관한 더 자세한 정보는 Google을 검색하면 된다.

함수 doublemultiply가 기억나는가? multiply 함수는 다음과 같이 정의되었다:

let multiply n list =
  let f x =
    n * x
  in
  List.map f list
  ;;

이제 우리는 함수 double, triple을 다음과 같이 정의할 수 있다:

let double = multiply 2;;
let triple = multiply 3;;

이들은 진짜 함수이다. 다음을 살펴보자:

# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]

혹은 f 를 사용하지 않고 부분 적용(partial application)을 직접사용할 수 도 있다:

# let multiply n = List.map (( * ) n);;
val multiply : int -> int list -> int list = 
# let double = multiply 2;;
val double : int list -> int list = 
# let triple = multiply 3;;
val triple : int list -> int list = 
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]

위 예에서 ((*) n)(*) (times) 함수의 부분 적용이다. 일부러 공백을 사용하여 OCaml이 (*를 주석의 시작과 혼동하지 않도록 한 점에 주의하자.

괄호 사이에 중위(infix)연산자를 넣으면 함수가 된다. 다음은 plus함수를 다르게 정의한 것이다:

# let plus = (+);;
val plus : int -> int -> int = 
# plus 2 3;;
- : int = 5

다른 커링 함수에 대한 예를 몇가지 더 살펴보자:

# List.map (plus 2) [1; 2; 3];;
- : int list = [3; 4; 5]
# let list_of_functions = List.map plus [1; 2; 3];;
val list_of_functions : (int -> int) list = [; ; ]

함수형 프로그래밍은 무엇을 하기에 좋은가?

다른 모든 좋은 프로그래밍 기법들이 그러하듯이 함수형 프로그래밍은 어떤 유형의 문제를 해결하는데 유용한 도구이다. 함수형 프로그래밍은 event-driven loop을 통하여 사용되는 GUI에 사용되는 콜백(callback)을 작성하는데 유용하다. 함수형 프로그래밍은 일반적인 알고리즘(generic algorithm)을 작성하는데 매우 유용하다. List.map 함수는 어떠한 유형(type)에도 적용할 수 있는 일반적인 알고리즘이다. 마찬가지로 트리(tree)에 적용되는 일반적인 함수를 작성할 수 있다. 어떤 종류의 수치적인 문제는 함수형 프로그램을 사용하면 빨리 풀 수 있다(예를 들면 수학적 함수의 미분(derivative)을 수치적으로 계산하는 문제 같은 경우).

순수 함수형 프로그래밍과 불순한 함수형 프로그래밍

순수 함수(pure function)는 어떠한 사이드 이펙트(side-effects)도 없는 함수이다. 사이드 이펙트는 함수가 내부에 감춰진 어떤 상태를 가지고 있다는 말이다. C언어의 strlen 함수는 순수 함수의 한 예이다. 같은 문자열을 가지고 strlen 를 반복해서 호출한다면 항상 같은 길이를 반환할 것이다. strlen 함수의 반환값(문자열의 길이)는 입력(문자열)에 의해서만 결정되며 다른 어떤것 과도 상관이 없다. 하지만 불행하게도 많은 C의 함수들은 순수 함수가 아니다. malloc함수를 예로 들어보자 - 만일 malloc을 같은 숫자를 주고 반복해서 호출한다면 같은 포인터를 반환하지는 않을 것이다. 물론 malloc 함수는 어마어마한 양의 감춰진 상태가 있다(힙(heap)에 할당된 메모리, 사용된 할당 방법, 운용체제의 메모리 관리, 등.).

OCaml같은 ML계열의 언어는 "대부분 순수하다". 비록 reference나 array와 같은 방법을 통해 사이드 이펙트를 허용하지만 대부분의 코드들은 순수 함수형 프로그래밍이 될것이다. 이는 OCaml이 함수형 사고를 장려하기 때문이다. 다른 함수형 언어인 Haskell은 순수 함수형 언어이다. 반면에 Ocaml은 보다 실용적인 언어이다. 때로는 불순한(impure) 함수를 작성하는 것이 유용하기 때문이다.

순수 함수에는 많은 이론적인 장점들이 있다. 그중 한 가지는 순수함수의 경우 같은 인수로 여러번 호출되더라도 컴파일러는 실제로는 한 번만 호출하면 된다는 것이다. C 언어의 예를 보자:

for (i = 0; i 
    

이 루프는 O(n2)의 복잡도를 가진다. 왜냐하면 strlen (s) 함수가 매 번 호출되며, strlen함수는 호출될 때 마다 s를 살펴보기 때문이다. 만일 컴파일러가 똑똑하다면 strlen함수가 순수 함수이고 그리고 루프 내에서 s가 바뀌지 않았다는 사실을 발견할 수 있을 것이다. 그렇다면 불필요한 부가적인 strlen함수 호출을 없애고 루프를 O(n)으로 만들 수 있을 것이다. 정말로 컴파일러가 그런일을 할까? strlen 함수의 경우에는 "그렇다" 이다. 그렇다면 다른 경우에는 어떨까? 아마도 "아니오" 일 것이다.

작은 순수 함수를 작성하는데 집중함으로써 "상향식" 접근방법으로 재사용 가능한 코드들을 작성할 수 있으며, 매번 각각의 작은 함수들을 테스트하면서 개발을 진행할 수 있다. 현재의 유행은 "하향식" 개발 방법으로 개발전에 주의 깊은 계획을 세워야 한다. 하지만 필자의 견해는 이러한 하향식 접근법은 종종 프로젝트의 실패로 귀착된다는 것이다.

엄격함 대 게으름

C 언어나 ML 언어에서 파생된 언어들은 (계산순서에) 엄격하다. Haskell과 Miranda는 엄격하지 않다. 즉 게으른 언어이다. Ocaml은 기본적으로 엄격한 계산 순서를 유지하지만 필요할 경우 게으른 방식의 프로그래밍을 할 수 도 있다.

엄격한 언어에 있어서, 인수들은 함수에 전달되기 전에 항상 먼저 계산된 후 그 결과가 함수에 전달된다. 엄격한 언어에서 다음의 코드는 항상 "divide-by-zero" 오류가 발생한다:

give_me_a_three (1/0);;

만일 다른 어떠한 일반적인 언어를 사용하던 프로그래머였다면 이건 당연한 결과이며 당연히 그러하여야 한다. 아마도 다른 방식으로 동작할 수 도 있다는 사실을 알게되면 놀랄것이다.

게으런 언어에서는 뭔가 다른 일이 발생한다. 함수의 인수는 함수에서 실제로 사용할 때 계산되어진다. 함수 give_me_a_three가 인수를 모두 무시하고 무조건 3을 반환하는 함수라는 것을 기억하고 있는가? 게으런 언어에서는 위의 코드는 오류를 발생시키지 않는다. 그 이유는 give_me_a_three함수가 첫번째 인수를 필요로 하지 않고, 따라서 첫번째 인수는 전혀 계산될 필요가 없기 때문이다. 따라서 0으로 나누는 일은 일어나지 않는다.

게으른 언어는 정말로 이상한 것들을 가능하게 해 준다. 예를 들면 무한 리스트와 같은 것들이다. 무한 리스트 전체를 살피는 일을 하지않는다면 (예를 들어 처음 10개의 사용한다든가) 무한 리스트를 사용할 수 있다.

OCaml은 엄격한 언어지만 Lazy 모듈을 사용하면 게으른 표현식도 사용할 수 있다. 예를 들어보자. 우선 1/0에 대한 게으른 표현식을 만든다:

# let lazy_expr = lazy (1/0);;
val lazy_expr : int lazy_t = 

게으른 표현식의 유형이 int lazy_t임에 주목하자.

give_me_a_three 함수는 'a (any type)유형이므로 게으른 표현식을 인자로 호출될 수 있다:

# give_me_a_three lazy_expr;;
- : int = 3

게으른 표현식을 계산하기 위해서는 Lazy.force함수를 사용하여야 한다:

# Lazy.force lazy_expr;;
Exception: Division_by_zero.

Boxed vs. unboxed types

One term which you'll hear a lot when discussing functional languages is "boxed". I was very confused when I first heard this term, but in fact the distinction between boxed and unboxed types is quite simple if you've used C, C++ or Java before (in Perl, everything is boxed).

The way to think of a boxed object is to think of an object which has been allocated on the heap using malloc in C (or equivalently new in C++), and/or is referred to through a pointer. Take a look at this example C program:

#include 

void
printit (int *ptr)
{
  printf ("the number is %d\n", *ptr);
}

void
main ()
{
  int a = 3;
  int *p = &a;

  printit (p);
}

The variable a is allocated on the stack, and is quite definitely unboxed.

The function printit takes a boxed integer and prints it.

The diagram below shows an array of unboxed (top) vs. boxed (below) integers:

boxedarray.png

No prizes for guessing that the array of unboxed integers is much faster than the array of boxed integers. In addition, because there are fewer separate allocations, garbage collection is much faster and simpler on the array of unboxed objects.

In C or C++ you should have no problems constructing either of the two types of arrays above. In Java, you have two types, int which is unboxed and Integer which is boxed, and hence considerably less efficient. In OCaml, the basic types are all unboxed.