5일만에 뚝딱 스크립트 언어 만들기 PGLight (5/5)

저번에는 가상 머신을 설계하는 작업을 했습니다. 이번에는 가상머신의 명령어셋을 통해 어떻게 PGLight 코드가 실행되는지를 살펴보고, 코드 생성부분을 만들어볼거에요.

먼저 크고 아름다운 우리의 PGLight 예제 코드를 볼게요.

Print("Hello World!"); Print(10 + 11 + 12); var foo = 10; foo = foo * 2; Print(foo);

매우 단순한 코드입니다. 먼저 첫줄의 작업은 어떻게 실행되는지 살펴봅시다.

Print("Hello World!");

이 문장은 단순히 함수를 호출하고 있네요. 함수 호출은 함수 객체를 스택에 넣고, 나머지 인수들을 차례로 스택에 넣은뒤, CALL 명령어를 호출함으로써 이루어집니다.

PUSH (Print 객체의 주소) ;

PUSH ("Hello World!" 리터럴의 주소) ;

CALL 1 ; 인자가 1개

두 번째 문장은 다음과 같아요.

Print(10 + 11 + 12);

첫 번째 보다 조금 복잡해졌는데, 연산자가 중간에 들어가서 그렇죠. 하지만 연산은 트리를 후위순회하는 것으로 쉽게 구현가능합니다.

10 + 11의 경우 먼저 10을 스택에 넣고, 11을 스택에 넣은뒤 ADD 명령어를 호출하면 됩니다. 그러면 스택에는 10 + 11의 결과인 21이 남아있을겁니다. (10 + 11) + 12 같은 경우는 10을 스택에 넣고, 11을 스택에 넣고, ADD 명령어를 호출한 뒤에 12를 스택에 넣고 다시 ADD 명령어를 호출하면 되는거죠. 그러면 스택에는 33이 남아있겠죠.

PUSH (Print 객체의 주소) ;

PUSH (10 리터럴의 주소) ;

PUSH (11 리터럴의 주소) ;

ADD ;

PUSH (12 리터럴의 주소) ;

ADD ;

CALL 1 ; 인자가 1개

세번째 문장은 변수 선언이네요.

var foo = 10;

지역변수는 스택 안에 베이스 스택 주소에 따라 상대적으로 저장되고, 전역변수는 전역객체와 리터럴이 저장되는 전역 주소공간에 저장됩니다.

사실 변수 선언이 함수 밖에서 이루어졌으니, 전역변수 선언이지만, 여기서는 설명을 위해 두 경우다 보이겠습니다.

지역변수의 경우는 우측의 초기값을 평가하여 스택에 넣음으로써 변수 선언이 끝납니다. 만약에 초기값이 없다면 NULL이라도 넣어주면 되구요. 그래서 지역변수 선언의 경우 다음과 같은 어셈이 생성됩니다

PUSH (10 리터럴의 주소) ;

전역변수의 경우는 우측의 초기값을 평가하여 전역 주소공간으로 올려야 합니다. 스택의 자료를 전역 주소공간을 옮기는데에는 STORE 명령어가 사용됩니다.

PUSH (10 리터럴의 주소) ;

STORE (foo 전역변수의 주소) ;

그 다음 문장은 변수를 참조하여 연산을 하고 그 결과를 다시 변수에 넣는 작업입니다.

foo = foo * 2;

이 작업 역시 foo가 지역변수냐 전역변수냐에 따라 다른 어셈 코드가 사용됩니다.

지역 변수의 경우 foo의 값을 가져오기 위해서는 스택에 있는 값을 복사해서 스택 끝에 다시 추가하는 작업이 필요합니다. 이는 COPY 명령어를 통해 수행됩니다. 그리고 우측의 식을 평가한 뒤에는 그 결과를 다시 스택 상의 foo에 넣어야 하는데, 이는 WRITE 명령어를 통해 수행됩니다.

COPY (foo 지역변수의 상대 주소) ;

PUSH (2 리터럴의 주소) ;

MUL ; 곱하기

WRITE (foo 지역변수의 상대 주소) ;

전역변수의 경우 전역 주소공간에서 값을 가져오는데는 PUSH를 사용하면 됩니다. 전역변수 공간에 값을 쓰는데에는 STORE를 이용하면 되구요.

PUSH (foo 전역변수의 주소) ;

PUSH (2 리터럴의 주소) ;

MUL ; 곱하기

STORE (foo 전역변수의 주소) ;

마지막 문장은 어려울게 없네요.

Print(foo);

이 역시 foo가 지역변수냐 전역변수냐에 따라 코드가 달라지겠죠?

지역변수의 경우

PUSH (Print 객체의 주소) ;

COPY (foo 지역변수의 상대주소) ;

CALL 1 ; 인자 1개로 호출

전역변수의 경우

PUSH (Print 객체의 주소) ;

PUSH (foo 변수의 주소) ;

CALL 1 ; 인자 1개로 호출

이제 조금 어려운 코드를 볼까요? 사전과 배열을 다루는 코드입니다.

var arr = [1, 2, 3, 4, 5]; arr[0] = 10; Print(arr[4]); var dict = {"a" = 1, "b" = 2}; dict["c"] = 3; Print(dict["a"]);

첫번째 문장은 변수를 선언하고 배열을 만들어 넣는것입니다.

var arr = [1, 2, 3, 4, 5];

변수 선언은 지역이냐 전역이냐에 따라 달라진다는 것 앞에서 많이 얘기했으니 생략하구요, 여기서는 지역변수라 가정하고 진행할게요. 배열을 만들기 위해 사용되는 명령어는 ASSEMBLE입니다. 1, 2, 3, 4, 5를 차례로 스택에 넣고 ASSEMBLE 5를 실행하면, 스택에서 5개를 빼와 배열로 만들어주는 역할을 합니다. 그래서 위 코드는 아래 어셈으로 번역될 수 있습니다.

PUSH (1 리터럴의 주소) ;

PUSH (2 리터럴의 주소) ;

PUSH (3 리터럴의 주소) ;

PUSH (4 리터럴의 주소) ;

PUSH (5 리터럴의 주소) ;

ASSEMBLE 5 ; 5개를 배열로 묶음

다음 문장은 배열의 값을 설정합니다.

arr[0] = 10;

배열의 값을 설정하기 위한 명령어에는 SET이 있습니다. SET 명령어는 배열(array) 혹은 사전(dictionary)을 받고, 그 키를 받아서 값을 설정해주는 역할을 합니다. 어셈으로는 다음과 같이 번역할 수 있어요.

PUSH (10 리터럴의 주소) ; 값(value)을 지정합니다.

COPY (arr 지역변수의 상대 주소) ; 배열 혹은 사전을 지정합니다

PUSH (0 리터럴의 주소) ; 키(key)를 지정합니다

SET ;

다음 문장은 배열의 값을 참조합니다.

Print(arr[4]);

배열의 값을 참조하는 명령어는 AT 입니다. AT 명령어는 배열 혹은 사전을 받고, 키를 받아서 값을 가져옵니다. 따라서 위 문장은 다음과 같은 어셈으로 번역할 수 있죠.

PUSH (Print 객체의 주소) ;

COPY (arr 지역변수의 상대 주소) ; 배열 혹은 사전을 지정합니다

PUSH (4 리터럴의 주소) ; 키(key)를 지정합니다

AT ; 값을 가져오고

CALL 1 ; 인자 1개로 함수 호출

그 다음에 있는 사전의 경우도 마찬가지로 어셈으로 번역됩니다.

var dict = {"a" = 1, "b" = 2};
dict["c"] = 3;
Print(dict["a"]);

사전을 만들때는 NEWDICT 명령어를 사용합니다.

PUSH ("a" 리터럴의 주소) ; 키

PUSH (1 리터럴의 주소) ; 값

PUSH ("b" 리터럴의 주소) ; 키

PUSH (2 리터럴의 주소) ; 값

NEWDICT 2 ; 2개의 키-값 쌍을 사전으로 만든다

PUSH (3 리터럴의 주소) ; 새로운 값

COPY (dict 지역변수의 상대 주소) ; 배열 혹은 사전을 지정합니다

PUSH ("c" 리터럴의 주소) ; 키를 지정합니다.

SET ;

PUSH (Print 객체의 주소) ;

COPY (dict 지역변수의 상대 주소) ; 배열 혹은 사전을 지정합니다

PUSH ("c" 리터럴의 주소) ; 키(key)를 지정합니다

AT ; 값을 가져오고

CALL 1 ; 인자 1개로 함수 호출

이제 더 어려운 코드를 봅시다. 람다와 클로져!

var foo = x : x + 1; Print(foo(1)); var sq = (a, b, c) : (x : a*x^2 + b*x + c); var f = sq(1, 2, 1); Print(f(10));

람다 표현식(Lambda Expression)입니다. 이해가 어려우신 분들을 위해 부연설명 하자면 var foo = x : x + 1은 var foo = function(x){return x 1;}과 같은 의미랍니다.

아예 좀더 이해가 쉽게 위 코드를 함수형태로 바꿔서 써볼까요.

function anonym1(x) { return x + 1; } function anonym2(a, b, c) { function anonym3(x) { return a*x^2 + b*x + c; } return anonym3; } var foo = anonym1; Print(foo(1)); var sq = anonym2; var f = sq(1, 2, 1); Print(f(10));

(PGLight는 함수 속의 함수를 지원합니다. 또한 내부 함수가 외부의 변수를 참조할 경우 자동으로 클로저가 됩니다.)

람다 표현식이라는게 애초에 이렇게 익명함수들을 간편하게 쓰기 위한 문법인 만큼 일반함수로 풀어서 작성할 수도 있습니다. 실제로 코드를 생성할 때도 이와 같은 방법으로 풀어 쓰게 되지요. anonym1이나 anonym2와 같은 함수는 단순한 함수로써 별 어려움이 없습니다. 그런데 문제가 되는건 anonym3 함수가 되겠죠. 이 함수는 외부의 a, b, c라는 변수를 참조합니다.

여기서 먼저 첫번째 문제가 발생합니다. 베이스 스택 주소가 다른 내부 함수가 어떻게 외부의 변수를 참조할 것인가? 또한 anonym3 함수가 사용하는 a, b, c값은 anonym2 함수가 종료되면 스택에서 사라집니다. 여기서 두 번째 문제가 발생하죠. 참조하는 외부 변수의 생명주기가 클로저보다 짧을 경우 어떻게 할 것인가?

이 문제들을 해결하는 것이 클로저 구현에서 제일 중요한 부분입니다. PGLight에서는 다음과 같은 방법으로 이를 해결했습니다.

1. 클로저 함수는 (보이지 않는) 첫번째 인자로 참조하는 외부변수들의 배열을 받는다.

2. 참조당하는 외부 변수는 shared_ptr을 이용해 참조하는 쪽과 상태와 소유권을 공유한다. 

이를 위해 필요한 명령어가 REF(값을 공유가능한 shared_ptr로 바꿔준다)와 DEREF(shared_ptr을 사용가능한 값으로 바꿔준다)인 것이죠.

anonym2 함수 내에서 anonym3에 의해 변수가 캡쳐될 때 어떤 일이 발생하는지 살펴봅시다.

1. 지역변수 a, b, c가 anonym3에 의해 캡쳐되므로, 함수에 진입하자 마자 a, b, c는 shared_ptr로 값을 공유하게 만든다. (REF 명령어)

2. anonym3가 외부로 반환되는 순간이 클로져가 생성되는 순간이다. 먼저 shared_ptr로 값을 공유할 수 있게 된 a, b, c를 모아 배열의 형태로 만든다. (ASSEMBLE 명령어)

3. 만들어진 배열은 anonym3 함수의 주소와 함께 묶여져서 클로저가 된다. (MAKECLOSURE 명령어)

4. anonym3 함수 측에서는 자신이 호출될 때, 첫번째 인자로 a, b, c를 묶어두었던 배열을 가져오고, 그 배열을 통해 외부 변수를 참조한다. (ATD 명령어)

MAKECLOSURE 명령어는 스택에 있는 함수 주소와 배열을 이용해 클로저 객체를 만드는 일을 합니다.

ATD 명령어는 배열에서 x번째 있는 요소의 값을 가져옵니다. x는 오퍼랜드로 직접 설정됩니다.

그럼 anonym2 함수와 anonym3 함수의 어셈 번역코드를 살펴봅시다.

; anonym2 함수

; 베이스 스택 0, 1, 2 위치에 인자 a, b, c가 위치합니다

COPY 0 ; a를 복사하여

REF ; shared_ptr화시킨다

WRITE 0 ; 그 결과를 a에 써 넣는다

COPY 1 ; b를 복사하여

REF ; ...

WRITE 1 ; ...

COPY 2 ; c를 복사하여

REF ;

WRITE 2 ;

; 클로저 생성 준비

PUSH (anonym3 함수의 주소) ;

COPY 0 ; a

COPY 1 ; b

COPY 2 ; c

ASSEMBLE 3 ; [a, b, c]가 생성됨

MAKECLOSURE ; 변수 a, b, c가 캡쳐된 anonym3 클로저가 생성됨

RETURN 1 ; 인자 1개를 반환함

; anonym3 함수

; 베이스 스택 0에는 캡쳐된 변수 배열 [a, b, c]가 위치. 베이스 스택 1에는 인자 x가 위치합니다

COPY 0 ; [a, b, c] 배열을 가져와서

ATD 0 ; 0번째 인자인 a의 shared_ptr를 가져온다

DEREF ; 역참조하여 a를 구함

COPY 1 ; x를 가져옴

PUSH (2 리터럴의 주소) ;

POW ; x^2를 계산

MUL ; a*x^2을 계산

COPY 0 ; [a, b, c] 배열을 가져와서

ATD 1 ; 1번째 인자인 b의 shared_ptr를 가져온다

DEREF ;  역참조하여 b를 구함

COPY 1 ; x

MUL ; b*x

ADD ; a*x^2 + b*x

COPY 0 ; [a, b, c]

ATD 2 ; c

DEREF ; c

ADD ; a*x^2 + b*x + c

RETURN 1 ;

만약 위와 같은 경우에는 anonym3 함수에서 a, b, c의 값을 변경시키지 않으므로 굳이 shared_ptr화시켜서 값을 넘기지 않아도 괜찮습니다. 그럴경우 REF나 DEREF작업을 생략할 수 있겠지요.

조금더 복잡한 경우로 멤버함수를 호출하는 경우도 있습니다. 이때는 첫번째 인자로(만약 클로저라면 이미 첫번째 인자가 캡쳐리스트이므로 두번째 인자로) this를 넘겨준다는 게 포인트입니다. 다이나믹 타이핑인 덕분에 클래스 객체들은 모두 사전형태일수 밖에 없어요. 그래서 멤버 변수 참조는 사전을 참조하는 것과 동일한 방법으로 작동합니다.

마지막으로 조건문과 반복문의 경우만 살펴보면 왠만한 코드는 다 어셈으로 번역할 수 있겠죠

if(a > 0) { Print("+"); } else if(a < 0) { Print("-"); } else { Print("0"); }

if문은 단순합니다. 물론 elseif와 else가 붙는것에 따라 처리가 까다로워질수 있지만, 모든 if-elseif-else 문은 if-else문의 중첩으로 바꿀 수 있다는 사실만 명심하면 단순화시키는건 어렵지 않아요. 위 if문 그룹은 아래와 같이 변경 가능합니다.

if(a > 0) { Print("+"); } else { if(a < 0) { Print("-"); } else { Print("0"); } }

if 구현을 위해서는 조건 분기 개념이 필요합니다. PGLight 어셈블리에서는 무조건 분기로는 JMP, 조건부 분기로를 UNLESSJMP를 지원합니다. JMP는 현재 PC(프로그램 카운터)로부터 지정한 변위만큼 점프하는 것이구요, UNLESSJMP는 스택 값을 조사하여 거짓일 경우에만 현재 PC로부터 지정한 변위만큼 점프합니다. 따라서 위 코드를 번역하면 아래처럼 될 거에요.

;; if (a > 0) 블록

COPY (a 지역변수의 상대 주소) ;

PUSH (0 리터럴의 주소) ;

GT ; 비교연산

UNLESSJMP 8; 조건이 거짓일 경우 if 블록이 끝나는 곳으로 이동

PUSH (Print 객체의 주소) ;

PUSH ("+" 리터럴의 주소) ;

CALL 1 ;

JMP 21; else 블록이 끝나는 곳으로 이동

;; else if(a < 0) 블록

COPY (a 지역변수의 상대 주소) ;

PUSH (0 리터럴의 주소) ;

LS ; 비교연산

UNLESSJMP 8; 조건이 거짓일 경우 if블록이 끝나는 곳으로 이동

PUSH (Print 객체의 주소) ;

PUSH ("-" 리터럴의 주소) ;

CALL 1 ;

JMP 6; else 블록이 끝나는 곳으로 이동

;; else 블록

PUSH (Print 객체의 주소) ;

PUSH ("0" 리터럴의 주소) ;

CALL 1 ;

반복문 역시 어렵지 않을테니 생략하도록 하지요. for문은 while문으로 바꾸어 쓸수 있다는 사실. while문은 조건문 goto(JMP 명령어)가 포함된 무한루프로 바꿀수 있다는 사실을 이용하면 쉽게 코드로 변환 가능합니다.

글이 길어진 관계로 추상구문트리를 이용해 코드를 생성하는 방법은 다음으로 넘겨야겠네요... 결국 분량조절 실패...