[OCaml] Variadic Function 구현하기

Function currying에 대해서 공부한 이후, OCaml에서 Variadic function을 구현할 수 있지 않을까?라는 의문이 들었다. Variadic function은 매개변수를 임의의 개수로 받을 수 있는 함수다. 예를 들면 C언어에서 printf 함수가 대표적인 variadic function이다.

#include <stdarg.h>
#include <stdio.h>

int
add_em_up (int count,...)
{
  va_list ap;
  int i, sum;

  va_start (ap, count);         /* Initialize the argument list. */

  sum = 0;
  for (i = 0; i < count; i++)
    sum += va_arg (ap, int);    /* Get the next argument value. */

  va_end (ap);                  /* Clean up. */
  return sum;
}

int
main (void)
{
  /* This call prints 16. */
  printf ("%d\n", add_em_up (3, 5, 5, 6));

  /* This call prints 55. */
  printf ("%d\n", add_em_up (10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10));

  return 0;
}

그러나 OCaml은 static/strongly typed 프로그래밍 언어이므로 모든 함수들이 컴파일 타임에 "확실하게" 정의되어야 한다. 만약에 x, y 두 정수를 받는 add 함수를 정의한다면, add 함수의 type은 \( int \rightarrow int \rightarrow int \) 이 될 것이다. 만약 add 함수에 세 번째 파라미터를 넣게 되면 컴파일러가 기대하는 type은 \( int \rightarrow int \rightarrow int \rightarrow int \)가 되어 컴파일 오류가 난다. 그렇다면 OCaml에서 Variadic function을 구현하는 것은 불가능할까? 약간의 트릭을 쓰면 가능하다.

 

트릭은 int 대신에 함수를 매개변수로 받는 것이다. 함수형 프로그래밍 언어에서는 당연히 "함수"도 일반 "값"처럼 취급되므로 함수를 매개변수로 받는 것은 아무런 문제가 없다. 함수는 다시 다른 함수를 매개변수로 받는다. 구체적으로 말하자면, 함수 f1을 다음과 같이 정의할 수 있다.

let f1 m f2 = f2 m

위 구문의 뜻은 f1를 정의하는데, 매개변수 m, 그리고 f2를 받는 함수이며, 함수 내용은 f2를 매개변수 m로 호출하라는 의미다.

f1 m f2 f3 ... fn

위의 구문은 f2 m f3 ... fn 가 되며, 뒤에 딸려오는 함수들도 비슷한 식으로 정의되었다면, 최종적으로 fn m을 얻게 될 것이다. 마지막 함수 fn는 m을 리턴하도록 정의하면 최종 값을 얻을 수 있다.

let add f = f 0;;
let arg i m f = f (m+i);;
let end_of_args x = x;;
let three = add (arg 1) (arg 2) end_of_args;;
let six = add (arg 1) (arg 2) (arg 3) end_of_args;;

arg라는 함수는 i (현재 integer), m (이전까지의 합), f (임의의 함수)를 받는다. three 오른쪽의 expression이 계산되는 과정을 따라가면 다음과 같다. 

add (arg 1) (arg 2) end_of_args
(arg 1) 0 (arg 2) end_of_args
(arg 2) (0+1) end_of_args
end_of_args (1+2)
end_of_args 3
3

add는 어떤 함수 f를 매개변수 0과 함께 호출한다. (arg 1)이라는 구문은 i=1인 상태에서 m과 f를 받는 함수를 의미한다. (arg 1) 0을 보면 m=0인 상태에서 m+i를 수행하고 (0+1=1) 이 값을 매개변수로 하여 다음에 딸려오는 함수를 호출(apply)한다.

 

(arg 2)는 다시 i=2인 상태에서 m(이전의 m과 다름)과 f(역시 이전의 f와 다름)를 받는 함수를 의미하는데, m은 앞에서 0+1이 넘어오므로 1+2가 계산이 되고 이 값을 매개변수로 하여 다음에 딸려오는 함수를 호출한다. 마지막으로 end_of_args라는 함수는 매개변수 3과 함께 호출되므로 최종적으로 3이 리턴된다. 복잡하긴 한데, 차근차근 apply를 하면서 최종 값을 얻어내는 로직이라고 보면 된다.

Type Inference (타입 추론)

그렇다면 type inference에는 아무런 문제가 없을까? 매개변수 이름이 같으면 헷갈리므로 arg i m f대신에 arg i m g로 다른 매개변수 이름을 사용하자.

let add f = f 0;;
let arg i m g = g (m+i);;
let end_of_args x = x;;
let three = add (arg 1) (arg 2) end_of_args;;
let six = add (arg 1) (arg 2) (arg 3) end_of_args;;

 

add의 return type은 아직 모르므로 x'라고 두면 add의 type은 다음과 같다.

\[ add: f' \rightarrow x' \]

f는 아직 뭔지 모르지만 함수 본문에서 f 0 처럼 사용되었으므로 int를 받는 함수라는 것을 알게 된다. f의 return value가 그대로 add의 return value가 되므로 return type들은 x'로 같아야 한다.

\[ f: int \rightarrow x' \]

f의 type을 대입하면 add의 type은 \( ( int \rightarrow x') \rightarrow x' \) 이 된다.

 

\[ add: (int \rightarrow x') \rightarrow x' \]

\[ f: int \rightarrow x' \]

 

arg의 return type은 아직 모르므로 y'라고 둔다. 그리고 m+i에서 m과 i는 int임을 추론할 수 있다.

\[ arg: int  \rightarrow  int  \rightarrow  g'  \rightarrow  y' \]

g는 m+i 합을 매개변수로 받으므로 int를 받는 함수다.

\[ g: int \rightarrow y' \]

g의 type을 그대로 대입하면 arg의 type을 얻는다.

\[ arg: int \rightarrow int \rightarrow (int \rightarrow y') \rightarrow y' \]

그렇다면 add (arg 1) 의 type은 무엇일까?

(arg 1)의 type은 \( int \rightarrow (int \rightarrow y') \rightarrow y' \)으로 함수 형태이다. add의 type을 보면 첫 번째 매개변수의 type으로 \( (int \rightarrow x') \)를 기대하는데, \( int \rightarrow (int \rightarrow y') \rightarrow y' \) 모양의 함수가 들어와도 크게 지장은 없다. 왜냐하면 x'는 \( (int \rightarrow y') \rightarrow y' \)를 포괄할 수 있기 때문이다. add (arg 1)의 type은 x'라고 했으므로 \( (int \rightarrow y') \rightarrow y' \)가 되어야 한다. 이제 end_of_args와 같은 함수는 x를 받아서 그대로 x를 리턴하므로 int = y'임을 추론할 수 있다. 따라서 add (arg 1) end_of_args의 type은 int가 된다.

 

그런데 OCaml에서 add (arg 1)을 실행하면 \( (int  \rightarrow  y')  \rightarrow  y' \)의 형태가 아닌 \( (int  \rightarrow  \_y')  \rightarrow  \_y' \)가 나온다. 이를 weak polymorphic type이라 한다. 이유는 이렇게 partial application한 값들은 컴파일 타임에 생성되는 것이 아니라 런타임에 생성되는 값(closure)이기 때문이다. Weak polymorphic type에서 어떤 type이라는 사실이 밝혀지면 그 type으로 고정이 된다(deferred monomorphic type). 만약 polymorphic type으로 만들고 싶으면 별도로 함수로 선언하여 임의의 type이 들어올 수 있음을 컴파일러에게 알려줘야 한다. 즉, let eta_expansion h = add (arg 1) h;; 와 같은 식이다.  이렇게 하면 h는 polymorphic type을 가질 수 있고 type checker 입장에서도 불만이 없다. 이렇게 명시적으로 polymorphic parameter를 추가해주는 것을 eta-expansion이라 한다. Weak polymorphic type에 대해서는 나중에 따로 글을 작성하도록 해야겠다.

 

(글 옮김; 2015년 10월 10일 작성)