gimmesilver's blog

Agbird.egloos.com

포토로그



40줄짜리 J 인터프리터 구현 소스 프로그래밍

 애자일 블로그를 통해 '테스트에서 버그까지' 라는 글을 봤는데 그 중에 J 언어의 초기 구현 버전에 대한 소개가 간단하게 나옵니다.
 J 언어는 외계어라 불러도 손색(?)없을 정도로 특이한 언어인데 연산이 배열 단위로 이루어지며 다차원 배열에서 dimension order를 통해 loop 를 제어합니다. 개념은 매우 훌륭한데 언어에서 사용되는 기본 함수나 예약어 등이 대부분 단일 문자나 특수 문자로 이루어져있기 때문에 가독성이 꽝이며 따라서 결코 대중화되기 어려운 언어이기도 합니다...:)
 근데 이 언어의 최초 프로토타입 구현 소스를 보니 C로 만들었는데도 불구하고 가독성 면에서 볼 때 J 소스랑 별 차이가 없네요... -_-
 전체 소스는 다음과 같습니다.

typedef char C;typedef long I;
typedef struct a{I t,r,d[3],p[2];}*A;
#define P printf
#define R return
#define V1(f) A f(w)A w;
#define V2(f) A f(a,w)A a,w;
#define DO(n,x) {I i=0,_n=(n);for(;i<_n;++i){x;}}
I *ma(n){R(I*)malloc(n*4);}mv(d,s,n)I *d,*s;{DO(n,d[i]=s[i]);}
tr(r,d)I *d;{I z=1;DO(r,z=z*d[i]);R z;}
A ga(t,r,d)I *d;{A z=(A)ma(5+tr(r,d));z->t=t,z->r=r,mv(z->d,d,r);
 R z;}
V1(iota){I n=*w->p;A z=ga(0,1,&n);DO(n,z->p[i]=i);R z;}
V2(plus){I r=w->r,*d=w->d,n=tr(r,d);A z=ga(0,r,d);
 DO(n,z->p[i]=a->p[i]+w->p[i]);R z;}
V2(from){I r=w->r-1,*d=w->d+1,n=tr(r,d);
 A z=ga(w->t,r,d);mv(z->p,w->p+(n**a->p),n);R z;}
V1(box){A z=ga(1,0,0);*z->p=(I)w;R z;}
V2(cat){I an=tr(a->r,a->d),wn=tr(w->r,w->d),n=an+wn;
 A z=ga(w->t,1,&n);mv(z->p,a->p,an);mv(z->p+an,w->p,wn);R z;}
V2(find){}
V2(rsh){I r=a->r?*a->d:1,n=tr(r,a->p),wn=tr(w->r,w->d);
 A z=ga(w->t,r,a->p);mv(z->p,w->p,wn=n>wn?wn:n);
 if(n-=wn)mv(z->p+wn,z->p,n);R z;}
V1(sha){A z=ga(0,1,&w->r);mv(z->p,w->d,w->r);R z;}
V1(id){R w;}V1(size){A z=ga(0,0,0);*z->p=w->r?*w->d:1;R z;}
pi(i){P("%d ",i);}nl(){P("\n");}
pr(w)A w;{I r=w->r,*d=w->d,n=tr(r,d);DO(r,pi(d[i]));nl();
 if(w->t)DO(n,P("< ");pr(w->p[i]))else DO(n,pi(w->p[i]));nl();}

C vt[]="+{~<#,";
A(*vd[])()={0,plus,from,find,0,rsh,cat},
 (*vm[])()={0,id,size,iota,box,sha,0};
I st[26]; qp(a){R  a>='a'&&a<='z';}qv(a){R a<'a';}
A ex(e)I *e;{I a=*e;
 if(qp(a)){if(e[1]=='=')R st[a-'a']=ex(e+2);a= st[ a-'a'];}
 R qv(a)?(*vm[a])(ex(e+1)):e[1]?(*vd[e[1]])(a,ex(e+2)):(A)a;}
noun(c){A z;if(c<'0'||c>'9')R 0;z=ga(0,0,0);*z->p=c-'0';R z;}
verb(c){I i=0;for(;vt[i];)if(vt[i++]==c)R i;R 0;}
I *wd(s)C *s;{I a,n=strlen(s),*e=ma(n+1);C c;
 DO(n,e[i]=(a=noun(c=s[i]))?a:(a=verb(c))?a:c);e[n]=0;R e;}

main(){C s[99];while(gets(s))pr(ex(wd(s)));}

어떻게...알아들 보시겠습니까? 사실 보기엔 무지하게 복잡해 보이지만 여기 저기 반복적으로 사용되는 구문을 매크로를 이용해서 극단적으로 줄여서 표기했을 뿐 전체 구조는 그다지 어렵지 않은 소스입니다. 물론 단지 초기 K&R 스타일의 C문법을 이용했기 때문에 warning이 좀 많이 날 뿐 컴파일은 무난하게 됩니다. 어쨌든 이 소스를 다듬고 warning도 좀 정리하고 해서 좀 더 알아보기 편한 형태로 바꾸면 다음과 같습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _A { int t,r,d[3],p[2]; }*A;

int *ma(n) { return(int*)malloc(n*4); }

void mv(int *d, int *s, int n) {
 int i = 0;
    for (; i < n; ++i)
        d[i]=s[i];
}

int tr(int r, int *d) {
    int z=1, i=0;
    for (; i < r; ++i)
        z=z*d[i];
    return z;
}

A ga(int t, int r, int *d) {
    A z=(A)ma(5+tr(r,d));
    z->t=t, z->r=r;
    mv(z->d,d,r);
    return z;
}

A iota(A w) {
    int n=*w->p, i=0;
    A z=ga(0,1,&n);
    for (; i < n; ++i)
        z->p[i]=i;
    return z;
}

A plus(A a, A w) {
    int r=w->r, *d=w->d, n=tr(r,d), i=0;
    A z=ga(0,r,d);
    for (; i < n; ++i) {
        z->p[i] = a->p[i] + w->p[i];
    }
    return z;
}

A from(A a, A w) {
    int r=w->r-1, *d=w->d+1, n=tr(r,d);
    A z=ga(w->t,r,d);
    mv(z->p, w->p+(n* *(a->p)), n);
    return z;
}

A box(A w) {
    A z=ga(1,0,0);
    *z->p=(int)w;
    return z;
}

A cat(A a, A w) {
    int an=tr(a->r,a->d), wn=tr(w->r,w->d), n=an+wn;
    A z=ga(w->t,1,&n);
    mv(z->p,a->p,an);
    mv(z->p+an,w->p,wn);
    return z;
}

A find(A a, A w) { return (A)0; }

A rsh(A a, A w) {
    int r=a->r?*a->d:1, n=tr(r,a->p), wn=tr(w->r,w->d);
    A z=ga(w->t,r,a->p);
    mv(z->p,w->p,wn=n>wn?wn:n);
    if(n-=wn)
        mv(z->p+wn,z->p,n);
    return z;
}

A sha(A w) {
    A z=ga(0,1,&w->r);
    mv(z->p,w->d,w->r);
    return z;
}

A id(A w) { return w; }

A size(A w) {
    A z=ga(0,0,0);
    *z->p=w->r?*w->d:1;
    return z;
}

void pi(int i) { printf("%d ",i); }
void newline() { printf("\n"); }

A(*vd[])()={0,plus,from,find,0,rsh,cat},
 (*vm[])()={0,id,size,iota,box,sha,0};

char vt[]="+{~<#,";
int st[26];

int qp(a) { return a>='a' && a<='z'; }
int qv(a) { return a<'a'; }

int noun(char c) {
    A z;
    if(c<'0'||c>'9')
        return 0;
    z=ga(0,0,0);
    *z->p=c-'0';
    return (int)z;
}

int verb(char c) {
    int i=0;
    for(;vt[i];)
        if(vt[i++]==c)
            return i;
    return 0;
}

void pr(A w) {
    int r=w->r, *d=w->d, n=tr(r,d), i=0;
    for (; i < r; ++i)
        pi(d[i]);
    newline();
    if(w->t) {
        for (i=0; i < n; ++i) {
            printf("<");
            pr((A)w->p[i]);
        }
    } else {
        for (i=0; i < n; ++i)
            pi(w->p[i]);
    }
    newline();
}

A ex(int *e) {
    int a=*e;
    if (qp(a)) {
        if(e[1]=='=') {
         st[a-'a']=(int)ex(e+2);
            return (A)st[a-'a'];
        }
        a = st[ a-'a'];
    }
    return qv(a)?(*vm[a])(ex(e+1))
                    :e[1]?(*vd[e[1]])(a,ex(e+2))
                        :(A)a;
}

int *wd(char *s) {
    int a,n=strlen(s),*e=ma(n+1), i=0;
    char c;
    for (; i < n; ++i) {
        c = s[i];
        if ((a = (noun(c))))
            e[i] = a;
        else if ((a = verb(c)))
            e[i] = a;
        else
            e[i] = c;
    }
    e[n]=0;
    return e;
}

int main() {
    char s[99];
    while(gets(s))
        pr(ex(wd(s)));
    return 0;
}

이제 좀 알아보기가 편해졌죠? 근데 사실 위 초기 구현 버전은 버그 문제가 (적어도 제가 발견한 것은) 하나 있습니다. 원래 J 언어는 배열 언어이고 따라서 다음과 같은 식의 값은
1 + 2,3,4

3,4,5 가 나와야 합니다. 근데 위 소스를 컴파일해서 실행시키면 이상한 값이 나옵니다. 버그는 plus() 함수에 있으며 plus()함수에 있는 아래 구문을
z->p[i] = a->p[i] + w->p[i];

다음과 같이 수정하면 됩니다.
z->p[i] = a->p[0] + w->p[i];

이렇게 하면 원래 J언어처럼 덧셈 연산을 수행합니다.

추가: 다시 생각해보니 제가 제안한 수정안은 잘못된 방법입니다. 프로토타입 버전에서는 배열을 바로 표현할 수 있는 방법이 없기 때문에 덧셈의 왼쪽 피연산자를 배열로 만들 수 없다고 생각했었는데 지금 생각해보니 변수에 대입해서 계산할 수 있네요...즉,
x=3,4,5
y=4,5,6
x+y
이렇게 하면 7,9,11 이 나와야 합니다. 이럴려면 원래 구현이 맞고 제가 수정한 것은 잘못된 것이죠. 따라서 두 경우를 모두 허용하려면 a와 w의 길이에 따라 다른 처리가 필요합니다. 가령 아래와 같은 식이 되겠죠...
A plus(A a, A w) {
    int r=w->r, *d=w->d, n=tr(r,d);
    A z=ga(0,r,d);
    int i = 0;
    if (tr(a->r, a->d) == 1)
     for (i=0; i < n; ++i) {
         z->p[i] = a->p[0] + w->p[i];
    else
     for (i=0; i < n; ++i) {
         z->p[i] = a->p[i] + w->p[i];
     }
    return z;
}
참고로 위의 소스를 좀 더 확장하자면 두 피연산자의 차원 및 크기가 다른 경우에 대한 에러 처리가 추가될 수 있겠습니다.

어쨌든 결론은...


덧글

  • xeraph 2008/04/23 23:25 # 답글

    해설하는 사람도 변태입니다 ;ㅅ;
  • 애자일컨설팅 2008/04/23 23:59 # 답글

    "가독성이 꽝이며" <-- 이부분은 논쟁의 여지가 있습니다. 예컨대 수학적 훈련이 되지 않은 사람에게는 어떤 수식(예를 들면 맥스웰의 방정식 같이 아름다운 수식)도 가독성이 꽝이라고 볼 수 있다는 것이 J를 쓰는 사람들의 주장입니다. 가독성은 그 언어적 훈련을 받지 않은 사람을 기준으로 보는 것과, 그 훈련을 받은 사람이 전혀 새로운 코드를 봤을 때 그 두 경우를 나눠서 생각해야 할 것입니다.

    제 경험으로 보면 J 언어로 1) 언어적 훈련을 받은 사람은 J 코드에서 놀라울 정도의 가독성을 느낄 수 있으며 2) 언어적 훈련을 받지 않은 사람(심지어는 비프로그래머)도 높은 가독성을 느끼게 J로 코딩 가능합니다. 하지만 반대로, 3) 가독성이 정말 꽝이 되도록 코딩할 수도 있습니다 -- 이것은 어느 언어든 비슷할 것입니다.

    마지막으로, 버그가 있다고 하셨는데, 제 생각에는 버그가 아닙니다. noun함수가 아직 구현 초기이기 때문에 드러난 문제인데, plus는 정확하게 구현되었습니다. 왜냐하면 J같은 array-oriented programming language에서는 1 + 2 3 4보다 3 4 5 + 6 7 8이 더 primitive한 연산(0-rank op)이기 때문입니다.
  • 백승우 2008/04/24 08:27 # 답글

    제가 스몰토크 첨봤을 떄.. '아 펄보다 심하다' 했는데.. 지나고 보니.. 나름 깔끔하게 보이더라고요..^^
    위에 소스 .. 정말 쵝오! 입니다. ㅡ,.ㅡ
  • silverbird 2008/04/24 10:29 # 답글

    // xeraph
    켁...

    // 애자일 컨설팅
    1. 가독성은 다소 주관적인 문제일 수 있는데...(그래서 논쟁의 여지가 있다고 하셨겠죠) 물론 J는 어떤 작업을 표현하는데 논리적이고 직관적인 문장을 매우 간결하게 만들수 있다는 점에서 직관적인 언어라 할 수 있습니다. 그러나 제 생각에 J는 동일한 의미를 가진 문장을 이해하는데에 있어 자연언어를 사용한 다른 프로그래밍 언어에 비해 추가적인 학습을 필요로 한다는 점에서 가독성이 나쁜 언어라 생각합니다(코딩을 할 때 변수나 함수의 적절한 작명을 중요시 여기는 것은 이런 이유겠죠. 어쨌든 우린 모두 사회적 동물이지 않습니까? ^^). 참고로 전 가독성과 직관성을 구분해야 한다고 생각하며 이에 대해서는 예전에 http://agbird.egloos.com/3389993 에서 좀더 구체적으로 생각을 정리한 바 있습니다.

    2. 맞습니다. plus 는 사실 원래 J 문법을 전부 구현했다면 버그가 아닙니다. 다만 프로토타입 버전에서는 배열끼리의 계산이 불가능한 상태였기 때문에 버그처럼 보일 뿐이겠죠...(지금보니 버그라는 표현이 좀 거칠군요...^^)

    // 백승우
    펄도 좀 변태적이죠...^^
  • ㄴㅇㄱ 2008/04/24 16:19 # 답글

    흠좀무 .. 꼬ㅏ당
  • corba 2008/05/11 00:16 # 삭제 답글

    소스를 보고 속이 울렁거리긴 처음입니다...-_-;
  • silverbird 2008/05/13 22:10 # 답글

    // corba
    멀미엔 귀미테~
댓글 입력 영역