순차적 언어 VS 논리적 언어

언어 홍수

현재 세계적으로 수천 종의 프로그래밍 언어들이 존재하고 있고, 새로운 프로그래밍 언어들이 계속 개발 중입니다. 지금 이 순간에도 어느 대학, 어느 기관에서 프로그래밍 언어를 만들었을지 모를 정도로 다양한 패러다임 속에서 만들어지고 있습니다.

 

 

유행따라 코딩

수많은 언어들 속에서 우리는 고민에 빠지게 됩니다. 도대체 어떤 언어가 개발하기 가장 쉬운 언어인가? 어느 언어가 개발 효율성이 좋은가? 원하는 결과를 얼마나 빠르게 얻을 것인가? 결정 장애를 가진 우리는 문제해결에 가장 적합한 언어가 아니라 주변에서 쉽게 접할 수 있는 언어를 사용하려는 경향이 생기게 됩니다. 이것은 결코 바람직한 현상이 아니며, 많은 추가적인 문제들을 야기하게 됩니다.

 

 

어떻게 적합한 언어를 고를까?

이 문제를 해결하기 위해, 지표 하나를 설정하겠습니다. 핵심 아이디어는 서술복잡도입니다. 서술복잡도란 어떤 알고리즘을 얼마나 간단하게 서술할 수 있는가를 측정하는 것입니다. 즉, 구현 프로그램이 짧을수록, 사용된 언어가 우수하다는 것을 보여주게 되고 이것은 서술복잡도가 낮음을 의미합니다. 예를 들어 바둑프로그램을 작성할 시, 언어 A를 사용시에는 50줄로 표현되는데, 언어 B를 사용시에는 1000줄로 표현된다면, A의 서술복잡도가 더 낮을 것입니다. 그 이유는 언어 A가 바둑 규칙을 보다 효과적으로 서술 하였기 때문이겠지요.

Let's see the code!

간단한 알고리즘들을 각 패러다임의 대표주자와 함께 코드를 적어보겠습니다. 먼저 피보나치 수열을 한번 볼까요?

순차적 언어 1번타자 C

unsigned long fib(int n) {  
  if (n >= 2)  
      return fib(n-1) + fib(n-2);  
  else  
      return 1;
}

간단하네요.

다음 대표적인 논리적 언어 Prolog를 한번 봅시다.

f(0,1).
f(1,1).
f(N,F) :-
           N > 1, N1 is N-1, N2 is N-2, f(N1,F1), f(N2,F2), F is F1+F2.

아..뭔지 모르겠지만 4번째 줄이 상당히 복잡해 보이네요.
어찌됐던 간에 두 코드의 서술복잡도는 그다지 차이가 안나 보입니다.

번외로, 피보나치수열을 가장 짧고, 이해하기 쉽게 표현할 수 있는 언어는 Haskell 인것 같아요.

f n | n <  2 = 1  
    | n >= 2 = f (n-1) + f (n-2)

지깁니다! in 갱상도 랭귀지

Anyway~

첫번째 서술복잡도 대결은 무승부라고 보죠^^

단, 한가지 집고 넣어가야 할 부분이 있습니다.
위에 적어 놓은 C 코드를 그대로 붙여 넣기 해서 실행을 해봅시다.

그럼 컴파일러가 그럼니다.

main 함수는 어따가 치워놨니~!! 입구를 못찼겠삼!

이와같이 C 언어에서는 어떤 알고리즘을 구현을 하더라도 실행 규칙/순서를 서술해 놓은 Control 구조가 꼭 필요합니다.

따라서 전체코드는 C언어가 더 길어지게 됩니다. 그럼 Prolog에게 0.5점 더 줘볼까요?

Next round is the Tower of Hanoi

하노이 탑으로 해봅시다.

홍코너 C

int Move(int source, int dest)  
{  
    int i=0,j=0;

    while(((source + i)==0)&&(i<N))i++;  
    while(((dest + j)==0)&&(j<N))j++;

    (dest+j-1) = (source+i);  
    (source + i) = 0;  
    return (dest+j-1);  
}  

void Hanoi(int n,int source, int dest, int spare)  
{  
    int i;  
    if(n==1){  
        Move(source,dest);  
        return;  
    }

    Hanoi(n-1,source,spare,dest);  
    Move(source,dest);  
    Hanoi(n-1,spare,dest,source);  
    return;  
}

이 소스코드는 제가 직접 짠것이 아니라 웹에서 훔쳐온 코드입니다. 이곳을 참조하세요.

야~악간 복잡해 보이긴 하죠?^^? 사실 핵심 코드만 가져온 것뿐입니다. 실제 코드(위 링크 참조)를 보면 출력부분과 콘트롤 부분이 더 있습니다.

청코너~ Prolog

move(1,X,Y,\_) :-    
           write('Move top disk from '),  
           write(X),  
           write(' to '),  
           write(Y),  
           nl.  
move(N,X,Y,Z) :-  
           N>1,  
           M is N-1,  
           move(M,X,Z,Y),  
           move(1,X,Y,\_),  
           move(M,Z,Y,X).

Prolog의 한판 승인가요?

예상처럼 짧습니다. 짧아요..

 

자~ 인제 딱 한 판만 더 해봅시다. 다음 과제는 정렬 Sorting

정렬알고리즘은 Mergesort로 해보겠습니다. 먼저 C 쏘우스~

typedef struct {  
    int key;  
} element;  

void merge(list,sorted,i,m,n);  
element list[], sorted[];  
int i,m,n;  
{  
    int j,k,t;  
    j=m+1;  
    k=i;  

    while(i<=m && j<=n){  
        if(list[i].key<=list[j].key)  
            sorted[k++].key=list[i++].key;  
        else  
            sorted[k++].key=list[j++].key;  
    }  
    if(i>m)  
    	for(t=j; t<=n; t++)  
		    sorted[k+t-j].key=list[t].key;  
    else  
    	for(t=i; t<=n; t++)  
    		sorted[k+t-i].key=list[t].key;  
}

 

살짝 긴가요??? 하노이 탑보다 짧아 보이네요.  

다음 Prolog

mergesort([], []).  
mergesort([A], [A]).  
mergesort([A, B | Rest], S) :-  
           divide([A, B | Rest], L1, L2),  
           mergesort(L1, S1),  
           mergesort(L2, S2),  
           my_merge(S1, S2, S).

           divide([], [], []).  
           divide([A], [A], []).  
           divide([A, B | R], [A | Ra], [B | Rb]) :-  divide(R, Ra, Rb).

           my_merge(A, [], A).  
           my_merge([], B, B).  
           my_merge([A | Ra], [B | Rb], [A | M]) :-  
           A =< B,  
           my_merge(Ra, [B | Rb], M).  
           my_merge([A | Ra], [B | Rb], [B | M]) :-  
           A > B,  
           my_merge([A | Ra], Rb, M).

 

이것 또한 조금 길군요. 비겼다 칠까요?

자,, 결론은 Prolog의 승!

 

지금까지 몇몇의 알고리즘에 대한 코드를 살펴보고 그 서술복잡도가 어느정도 되는지 봤습니다. 지금까지의 자료를 토대로 정리해보면 어떤 알고리즘은 둘다 비슷하게 서술이 가능하지만 어떤 알고리즘은 한쪽이 매우 복잡하게 서술이 됩니다.

알고리즘을 결정적 알고리즘과 비결정적 알고리즘으로 구분해 봅시다.
결정적 알고리즘이란 다음 상태가 결정적인 것을 의미하는데 피보나찌, 하노이 등이 포함됩니다.
비결정적 알고리즘이란 반대로 다음 상태가 비결정적인 것을 의미하는데 간단히 예를 들어 설명하면, 미로찾기 게임을 한다고 합시다. 시작하자마자 여러가지 갈래의 길이 나오게 되는데 어느 쪽을 선택하면 확실한 길인지 먼저 가보지 안고서는 알 수가 없습니다. 이렇게 다음 어떤 상태가 되는지 해보지 않으면 안되는 것을 비결정적 알고리즘이라고 합니다.

C언어와 같은 순차적 언어는 비결정적 알고리즘을 구현하고자 할 때 stack, queue과 같은 추가적인 자료구조를 도입하게 되고, 거기에다 콘트롤 구조를 포함시켜야 하기 때문에 결론적으로 전체적인 서술복잡도가 증가할 수 밖에 없습니다.

따라서, 순차적 언어의 서술 복잡도는 알고리즘을 A, 콘트롤 구조를 C, 자료구조를 S라 할때, A+C+S 가 되고,

논리적 언어의 서술 복잡도는 A 가 됩니다.

 모든 언어는 만든 목적과 서술방식이 다릅니다. 제가 적은 이 글은 단지 서술 복잡도만을 가지고 언어를 평가할 때 어떤 언어가 가장 우수한가를 나타내고 있습니다. 하드웨어의 성능과 용량은 날이 가면 갈 수록 우수해지기 때문에, 그 언어가 얼마나 좋은 퍼포먼스를 내느냐 보다는 얼마나 간단하게 표현할 수 있는가를 따져봐야할 시대가 점점다가 오고 있습니다. 따라서 우리는 유행처럼 '어느 언어가 좋다러라' 라는 말만 듣고 따라 할 것이 아니라

어떤 언어로 가장 쉽고 간단하고 빠르게 표현할 수 있는가를 한번 생각해봐야 할 것입니다.