Languages/Erlang2008.09.05 14:11

C같은 프로그래밍 언어에는 순환문 지원을 위한 다양한 문법들을 제공하고 있습니다. for, while, do-while 등등이 그것이죠. 물론 순환문을 위한 '특별한' 문법을 사용하지 않고도 프로그래밍을 할 수 있긴 합니다. 가령 C의 다음과 같은 프로그램을 한번 생각해 보죠.

int sum(int[] array, size_t n) {
    int sum = 0;
    for ( int i = 0; i < n; ++i ) {
        sum += array[i];
    }
}

for를 사용해 배열에 있는 모든 값들을 합산하고 있습니다. 그런데 for라는 키워드를 사용할 수가 없고, 그냥 함수 개념만 사용해 프로그래밍을 해야 한다면, 문제를 어떻게 해결할 수 있을까요?

int sum(int[] array, size_t n) {
    return sum_array(array, n, 0, 0);
}

int sum_array(int[] array, size_t n, int start_index, int sum) {
    if ( n == 0 ) {
        return sum;
    }

   return sum_array(array, n-1, start_index + 1, sum + array[start_index]);
}

뭐 이렇게도 할 수 있지 않았을까요? 여기서 주목해 볼 것은, 인자 sum을 통해 최종적으로 반환될 합계 값을 추적한다는 점입니다. 이런 프로시저는 "컴퓨터 프로그램의 구조와 해석"이라는 책에서 쓰인 용어를 빌려 말하자면, "되도는 프로시저"이고 "반복적인 프로세스"이죠. (이에 대해서는 해당 책을 참조하시길. ㅋㅋ) 반복적인 프로세스는 재귀적인 프로세스와는 달리 유한한 메모리를 사용해 문제를 풀 수 있습니다. (재귀적인 프로세스는 그 계산과정을 추적하기 위해 재귀 호출이 뻗어나간 각각의 가지에 대한 정보를 계산이 끝나서 그 결과가 '말아올려질 때 까지' 들고 있어야 합니다.)

하지만 C나 Java같은 프로그래밍 언어는 설사 프로세스가 풀려나가는 과정이 반복적(iterative)이라고 하더라도 일단 재귀적인 프로시저를 통해 구현했다면 전부 똑같이 처리합니다. 가령, 위의 sum_array 함수는 네 개의 변수만 사용하면 그 계산과정 전부를 온전히 추적할 수 있음에도, C 컴파일러는 냉정하게 함수가 새로 호출될 때 마다 그에 필요한 스택을 강제로 할당해 버립니다. 결국 배열이 길어지면 stack overflow가 나고 말죠. 그래서 for나 whie, do-while 같은 별도의 문법이 존재하는 겁니다.

하지만 Erlang이나 Scheme같은 프로그래밍 언어는 순환문을 위한 별도의 문법을 제공하지 않습니다. Erlang에서 위의 문제를 어떻게 푸는지 한번 살펴보도록 하죠. 재귀적 프로시저를 사용해 코드를 작성해야 합니다.

sum([H|T]) -> H + sum(T);
sum([]) -> 0.

위의 sum/1 함수는 리스트 하나를 인자로 받습니다. 리스트가 비어 있지 ([]) 않을 경우, 대응 규칙에 따라 이 리스트는 위의 첫 번째 절로 전달됩니다. 첫 번째 절에서 인자는 머리 (H)와 나머지(T) 부분으로 분리됩니다. 그러므로 sum이 반환해야 할 값은 H와 sum(T)의 합이 됩니다. 간단하죠?

그런데 위의 함수는 되도는 프로세스 이지 반복적인 프로세스는 아닙니다. 그다지 효율적으로 메모리를 사용하지 못한다는 뜻이 되겠군요. 이 프로세스를 반복적 프로세스로 바꿀려면, 다음과 같이 해야 할겁니다.

sum(L) -> sum(L, 0).

sum([H|T], S) -> sum(T, H + S);
sum([], S) -> S.

이렇게 하고 Erlang 셸에서 다음과 같이 해 보면 결과가 제대로 출력되는 것을 볼 수 있습니다.

14> L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
[1,2,3,4,5,6,7,8,9,10]
15> c(test).
...
20> test:sum(L).
55
21>

결국 Erlang에서 순환문은 함수를 재귀적으로 작성하여 만들게 된다는 이야기입니다. 간단한 이야기를 하려던 것이었는데 말이 너무 길어졌군요 ㅜㅜ 어쨌건 순환문을 만드는 데 있어서 재귀적 프로세스와 반복적 프로세스에 대한 차이는 반드시 알아두는 것이 좋습니다. Erlang에서는 그 차이를 정확하게 이해해야 효율적인 프로그램을 짤 수 있을 것이거든요.

"컴퓨터 프로그램의 구조와 해석"이 좀 비싸긴 합니다만 한권 장만해두시는 것도 좋겠습니다. ㅋㅋㅋㅋㅋㅋ

그럼 보는 김에 "프로그래밍 얼랭"에 나오는 예를 하나 더 살펴볼까요? 완전히 같은건 아니고 제가 좀 바꿨습니다.

odds_and_evens_acc(L) ->
    odds_and_evens_acc(L, 0, 0).

odds_and_evens_acc([H|T], Odds, Evens) ->
    case ( H rem 2 ) of
        1 -> odds_and_evens_acc(T, Odds + H, Evens);
        0 -> odds_and_evens_acc(T, Odds, Evens + H)
    end;
odds_and_evens_acc([], Odds, Evens) ->
    { {odd, Odds}, {even, Evens} }.


29> c(test).
{ok,test}
30> test:odds_and_evens_acc(L).
{{odd,25},{even,30}}
31>

홀수끼리의 합, 짝수끼리의 합을 구해서 투플 형태로 반환하는 예입니다. case 문도 사용했고, 투플에 아톰을 넣어뒀기 때문에 반환값의 의미를 좀 명확하게 볼 수 있습니다.


신고
Posted by 이병준

소중한 의견, 감사합니다. ^^