깜지로 쓰려는 블로그

잠깐 쉬고나서 10장 컴파일러를 시작한다는게

너무 놀다가 11시가 되버렸다.

오늘 좀 늦게 자려고 중간에 잠깐 자기도 했지만 너무 늦어버리긴 했지만

일단 하는데까지는 해봐야지

이번 글 제목을 적는데서 부터 조금 불편한게

10장이 신텍스 에날리시스인데 아날리시스랑 파서랑의 차이가 뭔가 싶었다.

지난 번에 vm 부분이었었나 어셈블리어였엇나. 아 어셈블리어 파트구나 파서를 구현하라고 하는데

파서의 뜻이 그냥 파서라고 봐왓다보니까 그냥 파서라 생각하고 대충 넘겨왔지만

잠깐 찾아보니 분석하다라는 의미였었다.

이번 장 제목이 신텍스 에날리시스인데, 

아날리시스도 결국에는 분석하다는 의미였지 않았던가.

아날리시스와 파서가 한국어로는 동일한거 같아도 영어에서의 의미는 조금 다를거란 생각이 들었다.

 영영 사전을 보니 아날라이즈가 이해하도록 조사 연구하는 식으로 분석한다면, 파스는 문장을 분할한다는 의미더라. 결국에 이번 장 제목인 신텍스 에날리시스는 문법 분석이고, (파싱의 의미) 파싱은 주어진 문법에 따라서 토큰들을 분석하여 나누는 것/분류하는 것 정도로 생각하면 되는거같다. 다른 개발 블로그에서도 파싱, 파서를 그런식으로 설명하고.

신텍스/문법 분석기 개요

 자. 이제 시작하면 컴파일이야 고급 언어를 중간 언어로 생성하는 걸 말하고,  크게 문법 분석과 코드 생성 작업으로 구분된다. 이번 장에서는 문법 분석을 다루며 문법 분석기는 토크나이저와 파서, 그러니까 형태소 분리기?와 토큰을 문법에 따라 분류하고 xml로 생성하는 파서로 구성된다.

 그런데 컴파일러 만드는법을 배우는게 왜 필요할까? 저자분은 컴파일러를 만들면서 프로그래밍 언어를 분석하는데 쓰는 규칙과 문법/방식들이 컴퓨터 그래픽스나, 통신, 네트워크, 머신러닝 등 다양한 분야에서도 사용된다고 한다.  그런 분야 중 하나로 자연어 처리, 언어 번역 같은 곳에서도 텍스트를 분석하고 의미를 가진 단어들을 합성을 하기 때문이란다. 

 확실히 전에 자연어 처리 잠깐 볼때 토크나이저가지고 단어 나누고 어째저쨰하면 자연어 처리 모델이 문장을 만드는걸 보긴 했었다. 이런데는 아니더라도 데이터, 텍스트같은걸 다룰대 비슷한 내용들을 마주치긴한다.

 아까 잭 컴파일러가 문법 분서기와 코드 생성기로 구분할 수 있다고 했는데, 문법 분석기는 토크나이징/형태소화와 파싱/형태소 구조화이 두가지 작업으로 나뉜다고 한다. 문법 분석기의 출력으로는 XML 파일인데 이 XML로 작업이 잘 됬는지를 쉽게 확인할수 있고, 완전한 코드를 생성하는데 사용할 수가 있다.

 여기서는 문법 분석기가 어떻게 사람처럼 프로그램 구조가 어떤지, 문법이 틀렸는지, 어디서 클래스/메소드가 시작하고 끝나는지 등을 분석할수 있도록 만드는지를 다룰건데, 이것들을 하려면 가장 먼저 프로그램을 토큰화(형태소화)를 하는것에서 부터 시작한다.

 이 신텍스/문법 분석기에서 사용되는 개념들로 어휘 분석 lexical analysis, 문맥에 얽히지 않은 문법 context free grammars, 파스 트리 parse tree, 재귀 하강 파싱 알고리즘 recursive descent parsing 등을 살펴보자.

어휘 분석 lexical analysis

 모든 프로그래밍 언어는 각 언어마다 고유의 토큰 종류들을 가지고 있다. JACK 언어의 경우 토큰들을 5가지 키워드, 심볼, 정수 상수, 문자열 상수, 식별자로 분류한다. 토큰화기/형태소화기는 주어진 프로그램을 형태소/의미를 가진 최소의 낱말 단위로 분할하여 우측의 xml 형태의 파일로 만들어낸다.

 문법

 문법 컴파일에서 당 연하게 중요해 보이는데, 프로그래밍 언어의 문법은 토크나이저로 분리한 토큰들의 흐름/모음을 보고 이게 어떤 종류인지 구문인지, 표현식인지, 구문이면 if구문인지 while구문인지, let구문인지, 표현식이라면 용어 하나만 있는지 연산자와 따른 용어가 또 있는지 등으로 주어진 토큰들의 종류를 판단하는데 사용한다. 또, 토큰 뭉치가 그 종류의 구문/표현식의 문법을 따르는지 보고 올바른 문장인지 아닌지를 확인하는데 쓸수 있다. 

 문법 왼편과 오른편으로 나눠보자 : 저자 분은 문법을 메타 언어라고 하는데, 언어가 어떻게 되어있는지 표현하는 언어라고 한다. 이 경우에는 JACK이란 프로그래밍 언어가 어떤 형식과 규칙을 가지고 있는지를 영어로 표현한게 문법이 되는거같다. 컴파일 이론에서 언어, 메타언어, 문법, 추론 등의 내용이 있지만 여기서는 단순하게 왼편 오른쪽편만 나눠서 보자.

 문법 규칙 왼편의 예시 : 위 그림의 왼편에는 규칙의 이름으로 실제로 프로그래밍 언어에 쓰이는건 아니지만 규칙끼리 구분하고, letStatement: 'let' varName '=' expression';' 처럼 letStatement라는 규칙 안에 varName이라는 규칙과 expression이라는 규칙이 들어가는데 이런식으로 다른 규칙 내용안에 포함되기도 한다.

 문법 규칙 우측의 형태 : 규칙의 오른쪽 편에는 이 규칙이 어떻게 생겻는지 언어적으로 패턴이 나와있다. 이 언어 패턴은 3가지 블록 터미널, 비터미널 nonterminal, 수식어 qualifier로 구성된다. 여기서 말하는 터미널은 토큰(형태소)이고, 비터미널은 다른 규칙의 이름, 수식어 qualifier는 |, *, ?, (, ) 이 5가지 심볼로 구성된다.

 토큰을 터미널이라고 하는건 터미널이 끝단이란 의미니까 의미를 가진 단어의 최소 단위/끝이므로 이걸 토큰을 터미널이라 하고, 터미널 외에 단어는 비터미널이라고 하는거같다. 위 문법 내용에서는 터미널 요소인 'if'처럼 볼드체에다가 따옴표가 붙어있고, expression같은 비터미널 요소에는 이탤릭체를, *나 ?처럼 수식어는 그냥 일반 폰트로 나타낸다.

 문법 규칙 우측의 예시 : 예시로 하나를 보면 언어 규칙 ifStatement: 'if' '(' expression ')' '{' statements '}' 라고 되어있는데 이 의미는 모든 if문은 'if'라는 토큰으로 시작하고, 그다음에는 '('라는 토큰이, 그다음에는 expression이라는 비터미널이, 그다음에는 토큰), 또 토큰 '{', 뒤엔 비터미널 statements, 마지막으로 '}'토큰이 붙어 있다면 이게 유효한 ifStatement가 된다!

 수식어의 역활 : 수식어 *는 0, 1 혹은 그 이상을 의미하는데 statements: statement*는 구문이 여러개 올수 있다는 의미가 된다. ?는 0, 1개만 온다는 의미로 expression: term (op term)? 이란 규칙에서 (op term)이 없거나 1개만 추가 될수 있다고 보면 될거같다. 수식어 (, )는 그룹핑으로 바로 윗줄의 (op term)?의 경우 op가 먼저 오고 term이 붙어서 한덩어리가 된다는 의미다.

파스 트리 : 토큰들을 문법에 따라 분류한 트리

 앞에서 프로그램을 토큰화기를 통해 토큰들과 각 토큰들의 종류를 xml로 정리했었다. 또, JACK의 문법 규칙들이 어떤 형태로 되어있는지도 봤다. 문법과 토큰, 토큰의 종류를 봤으니 이제 토큰들을 문법에 따라서 분류를 파스 트리를 만들 차례이다.

 위 문법을 보고 코딩하던걸 생각해보면 문법을 재귀적으로 따르던걸 알수 있다.

void main()
{
    int num = 0;
    while (1)
    {
       if(num == 10)
       {
           printf("out");
           break;
       }
       num = num + 1;
    }
}

 재귀적으로 반복되는 문법 규칙들 : 이 코드는 Jack은 아니지만 간단한 c언어를 작성했는데, jack 언어의 문법 규칙을 참고해서 보면 while (1)은 while구문 바로 뒤에 수식어 ()와 수식어 안에는 1이라는 expression이 존재한다. 근데 이 표현식은 용어 term이 1개인 표현식이며, 이 용어는 변수 용어가 아닌 상수 용어이다.

 수식어 )뒤에는 수식어 {}가 오며 이 안에는 구문들 statements이 들어가 있는데, 이 구문들은 if 구문과 num = num +1이니 let 구문 2개로 구성되어 있다고 볼수 있을거 같다. 또 이 구문안에는 또 다른 구문이 들어가 있는 식으로 문법 규칙들이 재귀적으로 계속 반복되고 있다.

 파스 트리 : 이와 같은 식으로 문법 규칙을 기준으로 구문들을 구문으로 구문의 종류에 따라서 또 분리하고, 들어가서 또 분리하기를 반복하며 모든 토큰들을 분류해낸 결과물이 파싱 트리이다. 위 그림은 while 구문을 규칙에 따라서 분류해 만든 결과물이다.

 파스 트리 XML : 파스 트리를 만들면 이걸 어떻게 표현할까? nand2tetris에서는 XML형태 파일로 만드는데, 바로 위 while구문의 파스트리를 XML 파일로 만들면 이런 형태가 된다. 

파서와 재귀 하강을 통한 파싱 처리

  앞에서 문법 규칙에 따라서 파스 트리를 만들었는데, 파서는 프로그램을 입력받아서 파스 트리를 xml로 만들어내는 프로그램이 된다. 여기서 파스 트리를 만들기 위해 사용하는 방법은 재귀 하강 파싱이다. 

 파서의 구현 : 파스 트리는 문법 규칙에 따라서 재귀적으로 구문을 내려가며, 끝에는 토큰단위로 분해해내었는데, 이 동작을 재귀적으로 호출해서 처리 할 수 있도록 각 문법 규칙 때마다 컴파일 하도록 구문 종류별 컴파일 함수 compileStatements(), compileIfstatement() 들을 구현해내면 된다.

 compileWhile() 슈도 코드 : 위 그림은 while 구문의 컴파일 구현 슈도 코드로 어떻게 while 구문을 파싱 트리로서 xml 출력을 낼지를 보여주는데, 가장 먼저 <whileStatement>를 출력한 후, process("while")을 통해 이 문자열을 XML 토큰으로 출력한다.

 그 다음 수식어 (를 처리하고, while 구문 규칙상 수식어 ( 뒤에는 표현식 Expression이 오므로 compileExpression()를 호출한다.

 이와 같은 식으로 내부에 존재하는 수식어를 출력하고, 구문들을 컴파일 하면서 필요한 경우 재귀적으로 더 내려가면서 반복하게 되고 모든 재귀 연산을 마치고 나머지 수식어 출력도 마치면 </whileStatement>로 이 while 구문의 xml 부분 출력을 마무리한다.

 이쯤 되면 대강 파싱 XML 만드는 과정이 감이 잡힐탠대 PPT 내용을 일일히 캡처해서 while 구문을 xml로 만드는 과정을 gif로 찍어왔다..

 방금 본 문법 규칙들 외에도 실제 객체 지향 언어의 문법 규칙은 더 복잡한데 jack에서 클래스 레벨의 static이나 인스턴스 레벨의 field 변수의 경우 이런 규칙을 쓴다.

 LL 문법 (var, let, while 토큰의 역활) : 이런식으로 재귀를 이용하여 쉽게 파싱 동작을 수행할수 있게 만들었다. 이쯤되면 왜 jack에서 let이니 var이니 같은걸 쓰는걸 궁금했을텐데, 앞에다가 let이나 var 같은 토큰을 두면서 이게 무슨 동작을 하는건지 let 구문 규칙을 비교해야할지, var 구문 규칙이랑 비교해야할지 구분할 수 있게 해준다. 위 gif 예시에서도 while이라는 토큰이 맨 앞에 있어서 while 구문인걸 알고 compilewhile()을 호출해서 썻다.

 위 문법 표처럼 첫번째 토큰으로 어느 문법 규칙을 봐야할지 판단할수 있으면 LL(1), 이걸로는 부족해서 두번째 토큰도 봐야한다면 LL(2)를 이와 같은 방식을 LL 문법이라 하며 이 덕분에 백트래킹 없이도 효율적인 재귀 파싱 알고리즘을 구현해냈다.

JACK 문법 정리

 이제 앞서 본 문법 표기법에 따라서 JACK의 문법을 정리한 내용은 우측의 그림과 같다. 

첫번째 토큰만으로는 애매할 때

 위 그림처럼 foo라는 토큰 뒤에 (, . , [ 같은 심볼이 올때가 있다. 그러면 foo[인 경우, foo. 인 경우, foo(인 경우 등 경우에 따라서 다른 형태의 문법 규칙을 사용해서 컴파일을 해야하는데 첫째 토큰인 foo 만으로는 어느 컴파일 함수를 해야할지 판단할 수 없다. 그러므로 LL 문법에 따라서 2번째 토큰이나 필요한 경우 3번째 토큰 혹은 그 이상을 확인하는 식으로 판단하면 된다.

마무리

 모든 파트가 그렇듯이 구현하는 부분도 있지만 넘어가고, jack으로 짜여진 프로그램에서 vm 코드를 생성하기 위해 이번 장에서는 토큰화기와 파서로 구성된 신텍스 분석기로 파싱 트리 XML을 만드는 과정 전반을 살펴봤다.

 와 하루만에 챕터 2장 봤어. 지난 주에는 삽질도 제대로 하면서 구현까지 하느라 기본 1장에 이틀은 걸렸는데 진짜 금요일에 OS까지 훑어보고 이젠 nand2tetris 좀 그만 끝내고싶다 ㅋㅋㅋㅋㅋㅋ

 실제 구현도 하면 더 기억에 오래남겠지만 가산기도 제대로 못만들어서 끄적대다가 원서도 이만큼 읽고 ppt의 도움으로 여기까지 왔으니 나중에 하고싶어지면 구현해야지 싶다 지금은 이렇게 CS 지식을 좀 더 쌓은것만으로도 충분히 잘한거라 생각한다.

----

05.26

어제 하루만에 2장을 급히 훑어보고

11장, 12장만 하면 되는데 오늘 급 의욕이 떨어졌다.

처음에 시작할때는 괜찬았는데 대강 지금까지 한 내용들만해도 내가 궁금했던거 거의 다 보기도 했고

OS 파트를 좀 보긴 해야되는데 나중에 하고싶어지면 보고 일단 nand2tetris는 여기까지 마무리하는걸로?

이 다음으로는 임베디드나 이용성 교수님이 알려주신 프로테우스로 회로 만들고 시뮬레이션 하는걸 해볼까 싶다.

이제 가상 머신 파트를 끝나고 컴파일러와 운영체제에 다와간다.

이번에 봐야하는 장은 고급 언어로 HACK에서 사용하는 고급언어인 JACK에 대해서 보면된다.

JACK은 JAVA나 C++ 같은 객체지향 언어 비슷한거라 저자분 말로는 배우는데 1시간이면 충분하다고 한다.

이런 고급언어 처럼 상속같은건 안되지만 왠만한 건 다 가능해서 테트리스나 스네이크, 퐁, 스페이스 인베이더 등 게임도 만들수가 있다.

이번 장 학습 개요와 절차 지행 프로그래밍

이번 장에서 다루는 내용은 아래와 같다.

1. JACK을 이용한 프로그래밍 예제,  절차지향, 객체지향, 리스트 처리 등

2. 문법 관련 예시들

3. 응용 어플리케이션 개발 관련 내용

 모든 언어를 공부할때 처음 만나는 hello world 출력하기 예제, 자바랑 거의 비슷하다. 우측에 주석문에 대한 내용이 있는데 /**    */ 가 API 설명 블록인지는 처음알았다.

 이번에는 절차와 배열을 이용한 프로그래밍 예시인데 키보드 입력을 받아서 배열에다가 담아내는 내용이네. 이 예제 코드로 JACK 언어에 대해서 좀 보면

1. JACK 프로그램은 여러 개의 .jack 클래스 파일을 모아서 Main.jack의 main 함수서 시작한다.(Main.jack은 꼭있어야함)

2. 흐름 제어도 제공하고

3. 기본 자료형으로 int, char, boolean, 클래스 정의한 타입인 OS에서 제공하는 Array와 String, 그리고 추상 자료형을 구현한 사용자 정의 클래스도 사용할수 있다.

4. 제공되는 OS 서비스로 Keyboard.readInt, Output.printString 등이 있다.

 5. OS에서 배열 자료형을 제공하는데, jack arrays are not typed 이 부분은 뭔 의미인지 잘모르겠다.

객체 지향 프로그래밍

 다른 언어처럼 JACK도 필요한 클래스를 추상 데이터 타입 ADT로 표현할수 있으니 구현해놓고 이걸 보고 쓰면된다.

 JACK에서는 기본 자료형으로 int, char, boolean만 제공하고 있다. 소수점 자리 날라가는거 없이 분수 표현을 하기 위해서 만들어진 Fraction 클래스가 있는데, field는 맴버 변수가 된다.

 Jack의 서브 루틴으로는 메서드와 생성자 그리고 함수가 있는데 메소드는 이 클래스 외부서 접근해서 사용할 수 있지만 function의 경우 이 함수 내부에서만 사용된다. 생성자는 생성자고, JACK에서는 가비지 컬랙터가 제공되지 않으니 사용하지 않는 객체는 명시적으로 해제해야되며 JACK의 모든 서브루틴은 return문으로 종료되어야한다.

서브루틴 전반에 대해서 봤는데, 그러면 JACK에서 클래스 객체는 어떻게 만들어지는지를 보자. 생성자는 기본적으로 OS와 컴파일러에서 어느 RAM 공간에다가 객체를 저장할지 다뤄준다. 또, 객체를 생성하면 스택에는 객체의 주소(객체의 값들이 있는 곳의 주소)가 올라가고, 힙 영역에는 그 객체의 값들이 보관된다.

 좌측 클라이언트 코드에서 a = Fraction.new(2, 3)한 결과 지역 변수 a는 스택에 올라갔고 이 스택의 값은 이 변수의 값들의 주소(heap에 위치)를 나타낸다. 이 지역 변수이자 분수인 a의 값들은 힙 영역 RAM[15087], RAM[15088] 에 저장 되어있다.

 빨리 넘어가기위해 생략하지면 연결 리스트를 제공하고 있어 리스트 처리도 가능하다.

OS를 구성하는 클래스는 위 8개고, 우측의 기능들을 제공한다.

 서브루틴 작성할 때 다른 클래스에 있는 내용을 가져와서 쓰면되지, 또 작성하지 말아야 한다.

JACK 언어 특징

 이제 JACK 언어를 이용한 고급 언어 프로그래밍을 마치고 JACK 언어의 문법, 데이터 타입, 클래스 등 언어적 특징을 살펴보자

 JACK은 토큰, 우리나라 말로 하면 형태소랑 비슷할거 같은데, 의미를 가진 최소 단위인 토큰들로 이뤄져있는데 이 토큰들은 신텍스 요소 그러니까 문법적 요소로 분류하면 위의 표와 같다. 이 부분들은 뒤의 컴파일러 파트에서 필요해서 간단하게 짚고 넘어간다. 대충 코딩하면 몰라도 되긴한데 컴파일러를 만들어야되니

 공백이나 주석문은 //, /*, /** 같은 식이고,   (), [], {}, ,, ;, +, - 같은 것들을 심볼, int, boolean, class, true 같은 것들은 예약어, 이도 저도 아닌 숫자는 상수, 그 외의 숫자 이외로 시작하는 문자들의 모음을 식별자라고 부른다.

 클래스의 맴버 변수, 정적 변수는 맨 앞에다가 선언해줘야 되고, 그 뒤에는 서브루틴들을 선언한다.

 서브루틴 그러니까 생성자, 메소드, 함수 같은 것들은 위의 형태로 선언과 구현을 한다. 함수 function은 외부에서 사용 불가능한 static 메소드이고, 그냥 메소드는 이 객체를 생성해서 외부에서 쓸수있다. 

 이제 데이터 타입을보면, 아까 어떤 기본타입이 있는지 말했으니 넘어가고 

객체는 위와 같이 선언하고 할당할 수 있으며, let 객체명 = 다른 객체; 시에는 얕은 복사가 이뤄진다.

객체의 선언 : var 클래스명 객체이름;

객체 할당 : let 객체명 = 객체 인스턴스;

 문자열 String은 OS에서 제공하는 String 클래스의 인스턴스며, 특이한점이라면 charAt(index) 라는 함수로 특정 문자 갑을 가져올수 있다.

 JACK 언어의 타입은 약한 타입, 약한 형태를 가지고 있는데, 이 말은 한 타입의 값을 다른 타입에다가 어떻게 할당할지 형 변환이 이뤄질지를 정의하지 않았다는 말을 의미한다. 왜냐면 다른 타입 끼리 할당하거나 어떻게 처리할지까지 정의하면 컴파일러가 너무 복잡해지다보니 간단한 컴파일러를 만들다보니 이렇게 됬다.

 변수의 경우 1) 해당 클래스와 모든 클래스의 서브루틴에서 접근가능한 정적 변수(같은 클래스 인스턴스끼리 공유하는 변수라 공유 변수라고도 함), 2) 클래스 단위에서 정의되어 객체의 속성을 나타내는 필드 변수, 3) 해당 서브루틴 안에서만 사용되는 로컬 변수와 4) 콜러가 서브루틴으로 전달하는 파라미터 변수 4 종류로 나눌수 있다.

  클래스와 필드 변수는 그 클래스(정적 변수, 해당 클래스의 모든 인스턴스), 그 클래스 인스턴스(필드 변수)에서만 접근이 가능하여 외부에서는 사용이 불가하고, 개발자가 작성한 경우 접근자 accessor(자바로 따지면 게터, 세터같은거)와 메소드로 접근이 가능하다.

 구문 statement는 변수에 값을 할당할때 쓰는 let, 조건문 if, 반복문 while, 함수 호출하는 do, 값을 반환하는 return 정도가 있다.

 각 구문들은 변수 명과 또 다른 구문 그리고 표현식 expression으로 이뤄져 있는데, 다음과 같은 표현식들이 존재한다.

1. 상수

2. 변수명 : 변수는 static( 그 클래스와 인스턴스 전체), field(그 클래스 인스턴스 내), local(그 서브루틴 안), parameter(그 서브루틴 안) 중 하나에 속한다.

3. this : 현재 객체의 포인터를 의미한다.

4. arr[expression] : arr은 Array 클래스의 한 타입으로 arr의 요소를 이와 같이 접근한다.

5. 서브루틴 : non-void type을 반환한다는데, return;으로 끝나는 메인함수는 뭔가 싶은데 아직은 잘모르겠다.

6. -expression, ~expression : 이 경우 -는 산술 부정 연산, ~는 논리 부정 연산을 한다.

 서브루틴 호출 : 서브루틴에 함수, 메소드, 생성자가 있는데 매번 호출 가능 범위가 햇갈린다. 이걸 보면서야 정리가 됬는데, 함수는 해당 클래스 안에서만, 메소드는 해당 클래스 그러니까 인스턴스 밖에서, 생성자/소멸자도 밖에서 사용가능하다.

JACK 프로그램

 이제 JACK 언어에 대해서 대부분을 살펴봤고, 이제 JACK으로 구현한 어플리케이션, OS 사용 등 예시를 둘러보고 이번 장을 마치자.

 JACK으로 개발한 이런 프로그램들이 있고

 잭 응용 프로그램을 만들려면 하나의 폴더에다가 구현한 .jack 클래스 파일들과 컴파일러를 놓고 컴파일을 하자. 생성된 vm 파일들을 가상 머신으로 로드해서 실행하면 된다.

 JACK OS 클래스로 이런것들이 있다.

1. Output : 화면에 문자 출력

2. graphics : 화면에 선, 원, 픽셀, 사각형 등 출력

3. inputs : 키보드 입력 읽기

4. Math, String, Array : 수학, 문자열, 배열 처리

5. Memory : 메모리 읽기, 쓰기, 할당, 해제

6. Sys : 중지, 에러 등, 가상머신 파트 마지막 부팅 내용에서 sp=256   sys.init 인가로 시작한다 했던거 같은데 init 이 왜없는지는 아직 모르겠다.

 와 대강 2 ~ 3시간만에 9장 내용을 대강 정리했다. 이번 금요일에 OS까지 하는걸 목표로 하다보니까. 이번장이야 이미프로그래밍은 익숙하니 금방 끝내겠지 하고 9, 10장을 한번에 끝낼 생각으로 시작했었다.

 그런데 오늘 수업 중에 여유있을때 컴파일러 파트 PPT 자료를 보는데 문법, 구문, 표현식, 파싱 같은 내용들이 수두룩한걸 보고나서 정리를 시작하려고 보니까 대충 넘겨서는 안될 부분들이 좀 있더라.

 원래 생각햇던것 보다는 이번장 양이 많아지기는 했는데, 책만 봤을때에 비하면 PPT 자료가 이해하기가 너무 좋게 잘 정리되어있어서 이덕분에 빨리 마무리 할 수 있었다.

 다음 장은 컴파일러 1 : 문법 분석 파트다. 좀 쉬고 10장 시작해야지.

이전 글에서 가상 머신이 런타임에서 어떻게 동작하는지를 대강 봤었고

이제 구현하기에 앞서 잠깐 VM 프로그램에 대해서 짚고 넘어가야할 부분이 있다.

VM 프로그램 구현 시 유의사항

책에서 이미 나온 내용들은 대충 패스하고

아 JACK 언어로 만든 프로그램들을 컴파일하면 vm 파일이 나온다했는데

FileName.jack -> FileName.vm 같은 식을 된다.

 VM 프로그램에서의 함수명 : 그런데 FileName.jack 에 bar라고 하는 생성자든, 함수가 있다고 하자

VM 함수 명은 전역적이다 보니까 그러면 이런 함수는 여러 vm 파일들을 합쳐서 어샘블리어로 만들 때 동일한 함수명이 존재하는 경우 충돌나게 되므로 서로 다른 vm 파일에 있는 동일한 이름의 함수를 구분해주기 위해서

VM 프로그램의 함수는 FileName.functionName과 같은 식으로 되어야 한다.

foo.jack에 mult라는 함수가 있는 경우 컴파일 하면 foo.vm에는 foo.mult 같은 식으로 함수 이름이 만들어진다.

 프로그램 시작점은 Main.jack 파일의 main 함수가 된다 그러므로 VM 프로그램 상에서는 Main.vm에 위치한 Main.main이란 함수가 프로그램의 시작하는 위치가 되겠다. 그리고 이 함수에서는 이제 프로그램이 시작되면서 운영체제의 초기화를 위한 함수인 Sys.init 을 호출하면서 시작된다. 다시 말하면 Main.vm 에 있는 Main.main 함수에서 프로그램이 시작하며 가장 먼저 초기화 함수인 Sys.init을 실행한다.

 프로그램 실행 과정 :제공되는 VM emulator로 돌리려면 프로그램 폴더에다가 하나든 여러개든 .vm 파일을 넣고 에뮬레이터로 로드하면된다.

VM 명령어와 VM 번역기로 번역한 어셈블리어 (슈도) 코드 

 VM 명령어로 함수를 호출하고 반환하는걸 어떻게 어셈블리어로 쓰나 싶었는데 이렇게 슈도 코드로 알려준다.

HACK 컴퓨터 가상 머신 표준

1. 스택

 앞에서 여러번 말한거지만 RAM 0 ~ 15번지까지는 가상 레지스터/포인터들이 차지하고 있고, 16 ~ 255번지까지는 정적 변수, 그리고 256번지 부터는 스택 영역으로 차지하고 있다. 그래서 일단 VM 번역기는 0 ~ 256까지 초기화 하는 내용으로 시작해야 하고, 값이 스택에 값이 추가되거나 뺄때 SP가 변경되도록 해야한다.

2. 특별한 심볼들

  어셈블리어와 마찬가지로 가상 머신이 다뤄야하는 특별한 심볼 두 가지가 있는데, 하나는 어셈블리어에서 봤던 선정의된 심볼들. 두번째는 return address와 함수 시작점을 표기하기 위한 심볼릭 라벨이다.

 내가 앞에서 생략한건데 소프트웨어 파트 시작할때 PointDemo.jack이라는 프로그램을 잠깐 소개했었다. 이 프로그램은 Main.jack과 Point.jack이라는 파일 두개가 PointDemo라는 폴더에 들어있었는데, 컴파일러를 돌리면 파일이 두개니까 두 vm 파일이 나온다. 컴파일 하면 서로 다른 파일의 함수를 구분 시켜주기 위해 기존의 jack 함수 명앞에 파일 명을 붙인다고 했었으므로, Main.vm에는 Main.main이, Point.vm에는 Point.new, Point.get 등으로 바뀐다.

 이 폴더를 VM 번역기로 돌리면 같은 폴더에 있는 vm 프로그램들을 읽어서 하나의 어셈블리어 파일인 PointDemo.asm을 만들어내며 이 asm 까지오면 더이상 추상화 된것 없이 심볼릭으로 전체가 구현된다. 

가상 머신 번역기의 함수 호출과 반환 어셈블리어 생성

 그러면 어셈블리어에서 함수를 호출하면서 점프하려면 함수 시작점을 어떻게 표시하고, 함수의 결과를 반환하는건 어떻게 표현할까? 아까 위에서 함수 호출, 결과 반환시에 대한 VM 명령어와 VM 번역기가 생성한 어셈블리 코드 표를 붙여넣기는 했었지만 이 PointDemo.asm에서는 아래와 같은 식으로 어셈블리어가 만들어진다.

 VM 코드의 Main.main에서 call Point.new 를 호출한게 어셈블리어 상에서 점프문으로 'goto 함수명', 점프할 위치는 심볼릭 라벨인 (함수명)의 형태하여 goto Point.new와 (Point.new)로 함수의 호출과 함수의 시작점을 표현하였고, (Point.new)아래 부분에 이 함수에서 어셈블리어로 구현된 연산 명령어들이 위치한다.

 이번에 리턴의 경우 vmcode function Point.new 의 맨 끝에 return이 위치하고 있다. 이 리턴문에는 반환 값은 없어 보이지만 goto Main.main$ret0라고, (Main.main$ret0)의 위치로 점프하라고 적혀있으며 이 심볼릭 라벨은 goto Point.new 바로 다음 줄에 위치하므로 함수를 실행 한 후에 마치면 메인 함수의 함수 호출문 바로 다음줄로 돌아와서 나머지 메인 함수의 명령어를 실행하게 되었다!

가상머신 번역기가 생성하는 특별한 심볼들

 앞에서 나온 .vm 파일의 명령어가 .asm 파일에서 어떻게 가상머신 번역기를 통해 생성되는지는 위 표를 참고하면 될거같다.

- SP, LCL, ARG, THIS, THAT이야 스택 포인터, 로컬 변수 메모리 세그먼트 베이스 주소, 매개변수 메모리 세그먼스 베이스 주소, 포인터 2개인걸 앞에서 여러번 봤었다.

- Xxx.i : Xxx.vm 이란 vm 파일에 존재하는 i번째 정적변수는 어셈블리어 상에서 Xxx.i로 생성된다.

- functionName$label : 이건 내가 놓쳣는지 앞에서 본적이 없었는데, 달라 앞부분만 보면 Xxx.vm 파일에 foo 라는 함수가 있는 경우 어셈블리어 상에서 Xxx.foo라는 심볼로 나오는건 알지만 이 foo 함수 안에 여기선 라벨이라고 하는데 변수라고 이해하면 될지 좀 햇갈리지만 ... 아 조건문일때 내용이구나 조건문을 만족하면 함수 내의 목적지를 Xxx.foo$bar라는 식으로 표기하는거 같다.

- functionName : 이거야 앞에서 봤지만 Xxx.vm 파일의 Xxx.foo 함수는 어셈블리어 상에서 함수의 시작점으로 (Xxx.foo)형태의 심볼릭 라벨로 표기된다.

- functionName$ret.i : 이것도 앞의 예시에서 본거지만 functionName 이라는 함수에서 i 번째 리턴후 시작하는 지점을 나타내며 (functionName$ret.i) 의 심볼릭 라벨로 어셈블리어로 생성된다. 아까의 경우 Main.main 함수의 첫번째 함수 호출 바로 다음줄에 위치하여, 첫번째 함수를 다 실행하면 이 심볼릭 라벨로 점프하여 다시 메인 함수 내용을 실행하도록 되어있었다.

- R13-R15 : 이거는 필요할때 쓰라고 남겨둔거라고 한다.

 와!! 아직 가상 머신 파트 조금 남기는 했지만 거의 다와갔다. ppt 자료는 장난아니게 많아서 걱정좀 했었는데 보다 보니까 전역 스택에서 어떻게 상태를 저장하고 왔다갔다 하는지를 한페이지씩 보여주다 보니까 이런식으로 페이지 양이 장난아니게 많았더라. 조금만 더하면 실제 VM 구현을 제외한 내용이 끝난다.

 잠깐 쉬었더니 마무리하기 진짜 귀찬네 ㅋㅋ

일단 다시 돌아와서 VM 번역기가 하는 일을 이제 제대로 정리하자

 VM 번역기는 hack 플랫폼의 가상 머신으로 컴파일러가 번역하여 생성한 VM 코드를 hack에서 실행가능한 어셈블리어로 번역해주는 역활을 한다. 이번 장에서 배운 VM 명령어는 산술논리연산 명령어, 메모리 제어 명령어, 분기 명령, 함수 명령어로 이뤄져있었으며, 이게 우측 하단의 타겟 언어의 내용처럼 되어있는 hack 어셈블리어로 번역된다.

 조금 더 자세히 보자

VM 번역기를 이용한 어셈블리어 생성

1. 호출 제어 어셈블리어 생성

 맨 좌측의 VM 코드를 보면 먼저 call Bar.mult 2라는 명령어가 있는데, 이 명령어는 위 상수 19와 지역변수 3을 매개변수을 가지고 Bar.mult 라는 함수를 호출하게 된다. 우측의 어셈블리어 코드를 보면 메인 함수 프레임을 저장하는거나 다른 해야되는 연산 내용은 없지만 goto Bar.mult로 호출한 함수로 이동하는거랑 콜리의 연산을 마치고 돌아올 수 있도록 Foo 함수 내부의 함수 호출 후 1번째 반윈 위치를 나타내는 (Foo$ret.1)이 있다.

 이 과정은 우측의 어셈블리 코드와 전역 스택을 보면 더 자세히 나와있는데, 함수를 호출하는 vm 코드는 슈도 어셈블리어로 맨 먼저 리턴주소와 다른 정보들을 스택에다가 넣어두고 foo,main 함수 프레임 저장을 완료하면, 호출된 함수의 매개변수 세그먼트 베이스 어드레스를 ARG = SP-5-nArgs로 지정해준다. 그 다음에는 현재 스택 포인터를 로컬 메모리 세그먼트 베이스 주소로 잡아주고

 이 그림과 같이 Bar.mult 함수 어셈블리어 시작점으로 넘어와 이 함수에 관한 명령어들이 실행된다.

2. 함수 제어 어셈블리어 생성

 함수 제어 어셈블리어의 경우에는 함수 내용에 따라서 만들어야 하는 어셈블리어는 다르지만 일단 공통적으로는 이 함수의 지역변수 만큼 공간을 잡고 0으로 초기화 시켜준 다음, 필요한 연산을 수행하게 되고 리턴문 그러니까 goto Foo$ret.1까지 진행하게 된다. 연산 결과를 어떻게 foo.main 함수로 넘어갈지는 다음의 반환 제어 어셈블리어 파트를 보자

3. 반환 제어 어셈블리어 생성

 이제 진짜 VM 번역기 동작 끝에 거의 다왔다. 이제 반환 연산을 어셈블리어로 나타낼 차례인데 좌측의 코드를 보면 LCL-5로 리턴 어드래스를 구하는데, 이 리턴 어드레스가 (Foo$ret.1) 심볼릭 라벨의 명령어 메모리상의 주소를 의미하는거 같다.

 아무튼 이렇게 돌아가야할 명령어 주소를 구해낸뒤, *ARG = pop()을 통해 글로벌 스택 최상단에 위치한 연산 결과를 매개변수 포인터 위치 즉, 콜러의 워킹 스택 최상단에다가 넣음으로서 콜리의 연산 결과를 콜러의 스택에다가 옮겼다! 그리고 연산 결과를 담았으니 스택 포인터도 그 위로 옮겨주고, 스택 포인터 뒤는 메인 함수 프레임을 가져와 저장하고 나서는 이재 재활용해서 쓴다.

 이제 콜러의 프레임들얼 다시 되찾아올수 있도록 endFrame(=LCL) - 1, 2, 3, 4를 하여 나머지 포인터 값들도 다시 읽어들인 뒤에 goto retAddr 으로 (Foo$ret.1)일로 점프해서 함수 호출 후 남은 main 함수의 명령어들을 수행하는게 VM 번역기가 하는 호출, 함수 처리, 반환하면서 어셈블리어 생성하는 과정이 되겠다.

프로그램 컴파일과 부팅 과정

 프로그램 컴파일 및 번역 과정을 정리하자면 한 폴더 myProg에 있는 모든 jack 파일들을 컴파일러가 vm 파일로 바꾸고, vm 파일의 함수 명은 앞에 파일명.함수로 바뀌어서 만들어 진다. 그리고, VM 번역기에 의해 vm code 함수명은 심볼릭 라벨로 생성되어 함수의 시작할 주소를 의미한다.

 VM 프로그램이 부팅하기 위해서는 VM 프로그램 중에 하나는 프로그램 시작점을 나타낼 수 있도록 Main.vm과 이 파일 안에 Main.main이라는 함수가 존재해야한다.

 그리고 hack 표준 맵핑에 나왔듯이 스택은 256번지부터 시작했었는데, 여기서 Sys.init 그러니까 Sys.vm의 Sys.init 함수를 호출하면 초기화 동작과 Main.main 함수를 호출에 무한 루프를 돌며 동작하게 된다!

8장 정리

 이번 장에서는 추상적인 분기화 함수 명령어를 hack 플랫폼의 어셈블리어로 구현하는 과정을 거치면서 VM 번역기가 어떻게 어셈블리어를 생성하는지 이해할 수 있었다. 이 내용은 2단계 컴파일 모델의 백앤드 파트로 이제 다음장에서 JACK을 배운 후 10, 11장에서 프론트 엔드 파트인 컴파일러에 대해서 정리하자!

 wa 드디여 8장을 마무리했다. 코드 구현하지 못한건 아쉽긴한데 그래도 이걸 보면서 가상 머신이 어떻게 된거고 중간 언어를 가지고 어셈블리어를 생성하고, 상세한 함수 호출, 동작, 반환 루틴을 알게 되니까 참 멀리왔다 ㅠㅜ

이번주 금요일까지 코드 구현까지는 아니더라도 OS 내용까지 마무리하면 진짜 뿌듯할거같다 

와 오늘 저녁까지 수업하고, 밥먹고 다시 정리하려고 하니까 졸려 죽겠다.

낮에 수업 중간중간에 8장 PPT 볼때는 그래도 괜찬았는데

밥먹은 직후라 그런지 원래 매일 이쯤에는 이랬으니까.

아무튼 오늘 안에는 8장 가상 머신을 이용한 제어 파트를 마무리 하는게 목표인데,

어제도 봤었지만 이번 장 분량이 장난아니기도 하고, 어제 짚고 넘어갔어야 했는데 빨리 진행한다고 안보고 넘어간게 있어서 오늘 안에 마무리 할수 있을지는 모르겠다.

오늘 오전에 마이컴 인터럽트 다루고, 오후에는 밀린 과제 숙제하느라 중간에 여유있을때 PPT 보면서 오늘 어떤 내용을 다뤄야할지 좀 보기는 했는데 하다보면 졸음이 가든가하겠지 생각하고 정신차려야지.

함수

 모든 고급 프로그래밍 언어에서 일정한 연산 과정을 하나로 모은 것을 함수라고 한다. CS 공부하다보면 마주치는 서브루틴, 프로시저, 메서드 같은것들도 결국에는 함수같은거라 할수 있다.

잠깐 함수 파트를 하기전에 지난 시간에 정리를 제대로 안한

HACK 플랫폼에서의 표준 가상머신 맵핑을 잠깐 짚고 넘어어가야 할거같다.

이걸 뭐라고 해야할까. 그냥 메모리 맵처럼 변수가 RAM의 어디에 위치하게 되는지를 나타낸다고 하면 될거같은데 좀 더 잘표현할수 있을거같긴한데 아직은 잘모르겠다.

 local, argument, this, that이야 이전 글에서 봤다시피 각 가상 메모리 세그먼트의 베이스 주소값을 보관하고 있다. 위에는 없는데 SP야 스텍 베이스 어드레스에서 시작해서 push, pop에 됨에 따라 바뀌는 주소를 보관하는 곳이고, constant는 어짜피 연산을 할때 담을 곳이 줘서 그런가 별 말이없다. 

 static 변수 경우의 설명이 좀 특이한데 Foo.vm에 있는 static i에 접근하기 위해서는 파일 이름을 붙여서 Foo.i라는 변수를 사용해야한다고 한다. 정적 변수이다보니 초기화는 되는데, 동일한 변수명으로 덮어씌워지는걸 방지하기 위해서 저런가 싶다. temp는 5-12 번지를 차지하고 있다 하고, 아 THIS와 THAT이 뭐하는건가 싶었는데 그냥 포인터 역활을 하는거였구나 이제 이해했다.

 결국에는 HACK 플랫폼에서 돌아가는 가상머신, 가상머신 번역기를 만들어내려면 이런 선정의된 심볼들을 쓸수 있도록 고려해서 구현해야한다. 이 내용도 어셈블러 파트에서 봤는데 정적 세그먼트 부분이랑 스택이 추가된게 다르네.

 다시 돌아와서

가상 머신 언어에서의 함수

 가상 머신에서의 연산이라 하면 기본 연산인 add, sub 같은 것들과 추상화된 연산(함수) multiply, sqrt같은 것들이 있다. 이 기본 연산과 함수는 둘다 스택의 맨 위에 있는 값들을 매개변수로 쓰고 연산 결과를 스택의 위에다가 놓는건 똑같다. 

 한번 세 함수로 이뤄진 VM 언어가 런타임에서 어떻게 돌아가는지 보자 우측의 스택은 전역 스택이 아닌 각 함수만의 공간을 나타내고 있다. main 함수의 call hypot을 통해 hypot 함수로 매개변수인 3, 4를 가지고 갔다. 

 hypot의 첫번째 곱샘 연산인 call mult의 경우 x를 스택에 2번 넣고 곱샘 연산을 수행하게 되는데 곱샘 연산한 뒤에는 3 두개는 더이상 없고 결과인 9만 남는다. 그 다음에 yy를 스택에다가 넣고 곱 연산을 하게 되어 결국에는 9, 16이 스택에 들어와있다. 

 그러면 mult의 private 스택에서는 어떨까. mult(3, 3)을 호출했을때 19번 줄 시점에서는 막 시작하면서 스택은 비어있고, 로컬 메모리 세그먼트에 sum, i 변수가 0으로 초기화 되어있다. 이 함수가 연산 수행 되고 나면 끝날때 쯤인 36번 명령 실행 후를 보면 mult 함수의 private 스택에는 곱샘 연산 결과인 9가 나오고 이 값이 hypot으로 반환된다.호출한다고 하자. 그러면  그 결과 hypot의  8번 라인 실행 후 private stack에는 9들어오게 된다.

 콜링 체인 : 위의 예시 처럼 한 실행 시점에서 main -> hypot -> mult 같은 함수들의 관계가 나타나는대 이를 콜링체인이라고 부른다. 위에서 main, hypot, mult 이외에도 sqrt가 있었지만 현재는 실행되지 않았듯이, 컴퓨터 프로그램은 수 많은 함수로 이뤄지고 있지만 실행 시점에는 콜링 체인으로 이뤄진 일부 함수들만 일을하고 있는 상황이 된다. 근데 실제로는 콜릭 체인의 함수들은 자기가 호출한 함수가 동작이 종료되고 값을 반환할 때까지 기다리기 때문에 실제로는 콜링 체인의 맨 끝에 있는 함수가 활동하며 이 함수를 현재 함수 current function(현재 실행중인 함수)이라 한다.

 위 main -> hypot -> mult 하는 예시에서 나왔드시 각 함수는 함수마다 고유의 지역 변수와 매개 변수를 가지고 있는데, 이 변수들은 함수가 호출되고 반활할때까지만 유지된다. 그러면 콜링 체인이 깊어지고, 재귀적이면 엄청 복잡할탠대 어떻게 메모리 관리를 해줄수 있을까? 

호출과 반환 로직

 이를 구현한 방법이 호출과 반환 로직인데 call and return logic 스택에서 이게 잘 동작한다. 이 호출과 반환 로직을 사용하기 위해서 포인터인 LCL, ARG, THIS, THAT을 사용한다. 책이랑은 조금 다르지만 위 예시의 hypot 함수에서 yy를 매개변수로 mult 함수를 호출한다고 생각해보자.

 mult 함수로 넘어가기전에 hypot 함수를 중지하고 넘어간다고 했는데 mult 함수의 동작이야 hypot의 작업 스택에 간섭없이 mult 함수만의 작업 스택을 이용한다. 위 그림에서 나와있듯이 hypot의 작업 스택과 mult의 작업스택은 완전히 분리되어있다. 그러니 hypot함수의 내용들을 덮어씌울 일이 없으니 걱정할 필요가 없고 중지한 함수의 내용을 잘 보관만 하고 있으면 된다.

 전역 스택에서의 호출 제어 handling call 과정

 그러면 호출과 반환이 어떻게 스택에서 동작하는지 조금 더 자세히 보자. 전역 스택에서 프로그램이 돌아가다가 값들이 쌓아 놓고 아래의 값 몇개를 매개변수로 지정해서 foo 라는 함수를 호출했다. 그러면 어디서 부터가 매개변수인지 콜리에서 알수 있도록 표기해두어야 한다.

  어디서부터가 매개변수인지는 포인터인 ARG에다가 매개변수 시작점의 주소를 담아두면 된다. 즉, 현재 호출하는 함수 foo의 매개변수 메모리 세그먼트를 만들었다!  그런데 이 다음에는 콜리에서 콜리만의 지역 변수, 콜리안에서 새로운 매개변수, this, that 같은 포인터가 사용되면서 콜러의 것을 덮어씌우면 안되니 콜러만의 정보를 저장해 두어야 한다. 콜러의 정보인 프레임을 스택에다가 추가하여 저장하면 아래와 같이 된다.

 매개변수 뒤에다가 돌아와야 할곳의 (스택이자 메모리상의)주소인 return address, 다음에는 현재 함수의 LCL 어드레스, 현재 지정한 ARG 어드레스, 그외 THIS와 THAT 포인터까지 5개의 값(프레임)을 저장해두면 호출 제어는 끝나고, 이제 함수를 제어할 차례이다.

 전역 스택에서의 함수 제어 handling function 과정

 먼저 콜리의 로컬 세그먼트부터 설정해주고,  호출된 함수 동작을 하며 워킹 스택을쌓아나간다. 그러다가 반환해야할 값을 만들었다. 이제 반환 제어를 하면 된다. 반환이 되면 콜리의 내용은 필요 없으므로 나중에 재사용한다. 반환하려면 결과 값을 어디에다가 넣으면 될까?

 전역 스택에서의 반환 제어 handling return 과정

1. 콜리의 리턴 값은 콜리의 매개변수 세그먼트 베이스 주소, 그러니까 콜러에서 첫번째 매개변수 자리에다가 넣으면 된다. 콜리를 호출할때 쓴 매개변수랑 콜리 내용들은 이제 필요없다.

2. 콜리의 결과를 기존 콜러의 워킹 스택 맨위에다가 넣었으니 콜리의 맨 위에있던 스택 포인터도 결과값 다음으로 위치를 옮겨주자.

 이렇게 하면 콜리에서 연산한 결과를 콜러로 잘 가져왔다! 그러면 이게 끝인거 같지만 콜러의 정보를 저장해둔 프레임이 남아있다.

3. SP를 원래 자리로 옮긴 뒤에 기존에 콜러의 프레임에 있던 LCL, ARG, THIS, THAT을 복원 시키면서 그림 상에 있었던 콜리의 LCL과 ARG는 사라졌다. 

4. 그 다음에는 return address로 점프하면 되는데, 이 부분이 정확하게 이해가 잘 되지는 않는다. 스택 포인터로 원 자리에 되돌렸으니 끝난게 아닌가 싶기는한데, 콜리의 어셈블리 명령을 마치면서 워킹 스택 상 데이터 정리는 끝났으니 콜리 호출했던 부분 다음의 어셈블리어 명렁어로 점프해서 나머지 명령어가 실행되도록 하라는 뜻인가 싶다.

 콜리 함수 연산을 마치고 값도 반환받고 스택 포인터와 명령어 위치도 되돌리고 나면 콜러가 다시 실행이 되는데, 기존에 매개변수 세그먼트나 프레임, 콜리 내용들은 이후 콜러 연산 과정에서 덮어씌우면서 재사용 된다. 그런 의미에서 우측 상단에서 블록이라 적어놓은거같다. 아무튼 call foo 매개변수 한 결과는 아래처럼 정리된다.

고급 언어 -> VM 코드 -> 런타임 상 동작과 전역 스택의 변화

 위 그림은 고급 언어로 구현한 팩토리얼 코드를 VM 코드로 컴파일 한 후에, 어떻게 전역 스택 상에서 동작되는지를 보여준다.

 동작 과정을 쭉 적었는데 이렇게 정리할수 있을거같다.

1. 메인 함수에서 factorial(3)을 하면서 3을 매개변수 세그먼트로 잡고 호출했다.

2. f(3)을 연산하기 전에 메인 함수의 정보들인 메인 프레임을 저장해두고, 연산하며 3 -1 한 2를 매개변수 세그먼트에 잡고 f(2)를 호출했다.

3. f(2)을 호출하면서 f(3) 프레임을 저장하고, 전역 스택이 깊어지며 매개 변수 1 세그먼트 잡은 채 f(1)을 또 호출했다.

4. f(1)에서 f(2) 프레임을 저장했지만 바로 1을 반환한다.

5. f(2) 함수에서 2와 f(1)에서 받은 1을 곱한 결과를 구하고, f(2) 프레임을 복원한뒤 값을 반환한다.

6. f(3) 함수에서 3과 f(2)로부터 전달 받은 2를 곱하여 결과를 구하여 메인 함수로 반환하고, f(3) 프레임을 복원한다.

7. 메인 함수는 f(3) 함수로부터 값을 반환받고, 메인 프레임을 복원하며 프로그램이 종료된다.

이제 이동해야하는 시간이라 여기까지 하고

지금까지 가상 머신에서 추상화된 함수 제어의 전반에 대해서 보면서

이번 글에서는 대강 이 5가지 정도 정리된거 같다.

1. HACK의 표준 매모리 맵핑 형태

2. 호출 제어

3. 함수 제어

4. 반환 제어

5. 런타임 때 전역 스택의 동작 과정

이번 장 남은 내용은 HACK 플랫폼 가상 머신 구현이다.

이걸 마무리하면 지난번에 못한 어셈블리어부터 VM 구현까지 직접 해봐야할거같긴한데 

안할수도 있고, 그냥 결과물 참고해서 따라 코딩할수도 있고

예전 처럼 계속 삽질하기에는 시간 아까워서 어떻게 할지는 좀 고민해야겠다.

한시간 전쯤에 7장 가상 머신의 동작 정리를 마치고

좀 피곤하니까 8장을 빨리 마무리 하고 자야지 싶었는데, 8장 ppt 자료만 182페이지나 된다

7장께 120페이지 정도만 해도 장난아니게 많았는데;;

아무래도 오늘 8장을 정리 다하려고하면 잠은 좀 늦게 자야할거같긴한데 피곤해서 할수있는데까지는 해야겠다. 빠르게 진행하기 위해서 책 내용보다는 PPT 자료를 가지고 잘못 된 부분이 있더라도 그냥 넘어가야될거같다.

 지난 장에서 가상머신의 기본적인 내용과 추상화와 구현에 대해서 봤다면 이번 장에서는 위의 ppt와 같이 분기와 함수, 그리고 함수 호출과 반환 마지막으로 HACK 플랫폼에서 가상 머신 구현 등의 내용을 다루고 있다.

 아까 스택가지고 산술 논리 연산을 어떻게 하는지 봤지만 이번에는 이걸 가지고 어떻게 중첩 함수 호출, 파라미터 전달, 재귀, 메모리 할당, 테스크 재활용 등 프로그램 동작에 필요한 복잡한 작업들이 이뤄지는 지볼 건데, 그동안 당연한 것이라고 생각했던것들이 어떻게 동작하고 있는지 알아보자.

 아 PPT 자료를 추가해놓자면 이번 장에서는 고급 언어를 컴파일 하면 나오는 VM 코드에서 나오는 분기와 함수 관련 명령어들을 다루는거같다. 

 런타임 시스템

 모든 컴퓨터 시스템은 런타임 시스템 보델을 따르는데, 어떻게 프로그램을 실행하고, 프로그램을 언제 종료해야하고, 어떻게 함수에서 다른 함수를 호출할때 매개변수를 넘길지, 함수를 돌릴때 어떻게 매모리를 관리해야할지, 그리고 더이상 필요없을때 어떻게 메모리 자원을 해재해야하는지 전부 구체화 할수 있어야 한다.

 이 책 nand 2 tetris에선 이 문제들을 HACK 플랫폼의 표준 맵핑을 이용해서 VM 언어 상세화 vm language specification를 다루고자 한다. VM 번역기가 이 규칙을 따르도록 만든다면, 런타임 시스템에서 동작할수 있게 되며 push, pop, add 같은 단순한 VM 명령어를 어셈블리어로 번역할 뿐만 아니라 프로그램이 동작하면서 감싸진 내용들에 대한 어셈블리 코드 전체를 만들어 낼수 있개 된다.  이 내용들이 어떻게 프로그램을 시작하고, 함수 호출과 반환을 처리할지에 대한 내용은 이 동작을 하는 완전한 어셈블리 코드를 만들어 내면 이해할수 있을거다. 

(완전히 이해하기가 힘들어 편하게 번역체로 썻다.)

고급 언어의 효과(?) magic 

 고급 언어를 이용하면 아래와 같은 분모가 1인 근의 공식같이 루트나 제곱이 들어간 복잡한 수식도 sqrt(), power()같은 함수를 이용해서 프로그램으로 쓸수가 있다. 이와 같이 함수를 이용해서 무한히 늘릴수 있는게 고급 언어의 중요한 특징이라 할수 있는데, 더 나아가 sqrt, power 같은 이름으로 구현하면 이게 어떻게 만들었는지랑은 상관없이 응용 어플리캐이션 개발자들은 이게 뭘하는지 알고 사용할수 있을거다.

 그리고 분기의 효과도 큰데, 분기를 이용하면 복잡한 로직/알고리즘도 코드로 표현할수가 있다. 예를들어 a== 0이 아닐때는 위의 이차식을 a가 0일때는 아래의 1차식의 근을 구하도록 구현이 가능하다.

 근대적인 프로그래밍 언어들은 개발자들이 쓰기 쉽게 만들어져있어서 쉽고 강력한 추상화를 쓸수가 있지만 결국에는 고급 언어가 얼마나 고급스럽던지간에/ 사람이 쓰기 쉽던지간에 결국에는 어느 하드웨어 플랫폼에 동작할수 있는 기계어로 되어있다보니까 결국에는 컴파일러와 VM 개발자들이 분기와 함수 호출, 반환 명령어들을 구현해서 저수준 언어로 변활 할수 있도록 만들어야한다.

 함수는 함수 하나 하나가 각자의 동작을 가지고 있는 독립적인 기능 단위라고 할수 있다. solve라는 계산 하는 함수가 있는경우 이 함수는 sqrt() 함수를 호출하고, 또 호출하고, power() 함수를 호출 할수도 있을 것이고, 어떤 경우에는 재귀적으로 아주 깊이 들어갈수도 있다. 이런 호출하는 함수를 콜러 caller라 부르며, 호출 받는 함수를 콜리 callee라고 한다.

 콜러는 콜리를 호출하면 콜리가 작업을 끝낼때 까지 중지하고, 콜리는 매개변수가 있거나 없을수도 있지만 매개변수를 이용해서 연산을 하고 계산 결과가 있을지 없을지는 모르지만 콜러에게 반환해주면서 콜러가 다시 실행하게 된다.

컴파일러, VM 설계자가 고려해야하는 오버해드들

* 네이버에 검색해보니 개발에서 오버해드란 결과를 얻는데 추가적인 자원, 요소들이라고 한다.

- 콜리가 연산을 마치고 결과를 반환해야하는 주소의 저장

- 콜러의 자원 저장

- 콜리에서 필요한 메모리 할당하기

- 콜러의 매개변수를 콜리로 전달하기

- 콜리 코드를 시작하기

 콜리가 연산이 끝나고 값을 반환시에는 다음의 오버해드들도 다뤄야한다.

- 콜리의 반환 결과를 콜러에서 사용할 수 있도록 하기

- 콜리에서 썻던 메모리 공간을 재활용하기

- 콜리 연산을 하기전에 콜러를 멈추면서 저장했던 메모리 자원들을 다시 사용하기

- 이전에 저장해둔 반환 주소를 찾아내기

- 콜러를 다시 실행하기

 그리고 보통 함수를 쓰면서 위와 같은 오버해드가 발생하고는 하는데, 보통의 응용 어플리케이션 개발자들은 어셈블리어 코드야 컴파일러가 만들어주고, 2단계 컴파일 모델에선 컴파일러의 백앤드 단, VM 번역기가 알아서 다뤄주니 알필요가 없다. 하지만 지금 VM에대해서 배우면서 이것들이 어떻게  VM 상에서 동작하고 처리되는지를 알아보자.

분기 branching

 어셈블리어를 봤다시피 프로그램은 한줄 한줄 읽어가면서 순서대로 진행하는데 어느 과정을 반복하도록 루프를 사용하기도 하고, 조건을 주기위해 분기 명령을 주기도 했었다. 이전에 사용한 goto 그러니까 조건에 따라서 JUMP한게 분기의 예시라고 할수 있을거 같은데 이전 장에서는 라벨 심볼을 이용해서 어셈블리어를 만들었다가 이게 실제 주소로 바뀐걸 봤었다.

 VM에서도 이런 라벨 심볼로 분기를 처리할 것이고, 무조건적인 분기는 goto를 조건부 분기의 경우는 if goto 심볼 명령을 사용할 거고 이때 스택의 맨 꼭대기에 있는 값이 참인지 거짓인지를 보고 판단한다. 위의 장은 고급 프로그램에서 컴파일한 결과 VM code 상에서 어떻게 표현되는지가 나온다. 이건 컴파일러의 영역이니까 지금 다루는건 아니고, 이번 장에서 구현해야하는 VM 번역기로 위의 분기 명령을 어떻게 타겟 플랫폼에서 어셈블리 명령어로 바꿀지를 고민해야한다.

 지금까지 VM 언어로 산술 논리연산 명령어와 메모리 세그먼트 명령어 그리고 분기 명령어에 대해서 까지 알아봤고, 이제 함수 명령어가 남았다. 

 잠깐 분기 파트를 넘어가기전에 책의 내용을 조금 더 짚고 넘어가면, 위의 VM 코드로 표현한 곱셈 연산의 경우 VM 프로그램인 만큼 컴파일러가 만들어내고 그 다음에 VM 번역기로 어셈블리어로 만들어 동작시키고, 저 코드는 비트 단위를 이용한 곱셈 나눗셈 알고리즘을 쓴게 아니라서 비효율 적이다. 이 알고리즘은 OS 장에서 Math 클래스의 함수를 구현하면서 다룰 건데 그 코드를 JACK 컴파일러에 돌리면 Math.vm이 나온다.

 이 외에도 OS에서는 수학 연산 뿐만이 아니라 메모리 관리를 위한 Memory.vm, 문자열 처리를 위한 String.vm, 배열 처리를 위한 Output.vm, 화면 처리를 위한 Screen.vm, 키보드 출력을 위한 Keyboard.vm, OS API를 제공하는 Sys.vm까지 8개의 파일로 컴파일된다.

 욕심 같아서는 오늘 가상머신을 끝내고는 싶었는데, 생각보다 VM 2장 내용이 장난아니게 많아서 좀 일찍 자고, 내일 일찍 일어나서 해야되겠다.

지난 금요일 까지만해도 주말에 가상머신을 끝내야되겠다고 마음먹고

집에 갔었지만

막상 가니 너무 편해서 쉬기만 하고 와버리고 말았는데

오늘부터는 구현은 가능한 넘어가고 빠르게 이론부터 진도를 나가야될거같다.

지난 금요일날 어셈블러까지 보면서 이책의 하드웨어 파트 절반이 완전히 끝났고

이번 장부터는 소프트웨어 영역으로 넘어가게 된다.

가상머신 장이 시작하기 전에 중간에 소프트웨어 파트 전반에 관해 설명이 나오기는 하지만

굳이 짚고 넘어가기는 귀찬아서 바로 가상머신을 시작하려고한다.

기존에는 책만 보고 이해한 내용을 바탕으로 정리를 해왔지만

잠깐 난드 투 테트리스 홈페이지에 나와있는 강의 자료를 봤는데

생각보다 책만 봤을때보다 이해하기 좋게 동작과정을 그림으로 잘 정리되어있더라.

그래서 이론 내용을 정리하면서 강의 자료도 참고하고자한다.

그렇게 바로 가상머신 내용을 시작하려고했지만

막상 보니 가상 머신이 중간 코드를 타겟 플랫폼의 어셈블리로 바꿔주는 걸로 시작하는데

이 내용이 간단하게 소프트웨어 개요 부분에서 나오다보니 안짚고 넘어갈수가 없을거같다.

소프트웨어 파트 앞으로 배울 내용들

아무튼 하드웨어 절반을 지나와서 앞으로는 소프트웨어에 대해서 정리하게 될건데

지금까지 공부한 내용으로 컴퓨터라는 블랙박스가 하드웨어적으로 어떻게 구성이 된건지 알수 있었고, 앞으로는 이 블랙박스가 소프트웨어로 어떻게 원하는 동작을 하게 되는지 배우게 된다.

 9장에서는 hack 컴퓨터에서 사용가능한 객체지향언어 JACK에 대해서 알아볼 것이고, 이 언어로 게임이나 OS 같은 것들을 만들 예정이다. 그리고 고급 언어로 응용 어플리케이션과 운영체제 구현으로 넘어가기 전에 여전히 어샘블리어와 고급 언어 사이에 공부하지 못해서 잘 모르는 중간 다리가 있는데 어떻게 하길래 우리가 구현한 고급 언어가 어샘블리어로 로 컴파일하는지 컴파일러, 가상머신, 운영체제 등에 대해서 배우게 된다.

 JACK 언어에 대해서 공부 한 뒤에는 JACK 컴파일러를 알아볼건데 이 컴파일러는 신텍스 분석과 코드 생성 파트로 구성되어 있어 10장, 11장에서 다루게 된다. 그리고 근데 이 컴파일러가 뭘 하냐면, C 언어 컴파일러처럼 타겟 플랫폼에 맞는 컴파일러를 선택하여 바로 그 플랫폼에서 쓸수있는 저급 언어를 생성하는게 아니라 자바 가상머신이나 C#처럼 가상 머신을 돌릴 수 있는 VM 코드를 만들어 내고, 컴파일러가 만들어낸 VM 코드를 각 플랫폼의 가상 머신에서 돌려 어셈블리어로 만들고 이 어셈블리어를 번역하여 컴퓨터를 동작하게 되는 과정이 된다.

 이와 같이 고급언어 -> 저급언어로 바로 컴파일 하는 컴파일러를 1단계 컴파일러라 하고, 고급 언어 -> VM 언어 -> 저급 언어와 같이 2번 컴파일하는 과정을 거치는걸 2단계 컴파일러(2 tier compiler)라고 한다. 내가 앞에서 어딘가에다가 가상머신과 관련된 내용을 정리했던거 같기도 하고, 기억이 가물가물한데 아ㅏ.. 그때 C언어 이식성과 어셈블리어에 대해서 설명하면서 정리했던거 같다.

 뒤의 책 내용 본 바로는 C언어의 이식성과 가상 머신이 결국 한 언어로 여러 플랫폼에서 사용한다는 큰 틀에서는 같아보이긴한데 조금 더 들어가서 보면 차이가 있었던거 같다. 아무튼 좀더 정리하면서 다시 봐야될거같고. 가상머신이 VM code를 기계어로 바꾸게 된다. 

 가상화.. 컴퓨터 가지고 이것저것하면서 vm player, 버추얼박스에서 라든가, 가상 메모리라든가, 앞에서 공부하면서 가상 레지스터에 대해서 잠깐 봤고, 클라우트 컴퓨팅에서도 가상화가 쓰이면서 가상화라는 개념이 엄청 중요한거라고 한다. 이 가상화에 대해서 7, 8장에서 살펴볼수 있을거같다.

 9장에서 JACK 언어, 10, 11에서 컴파일러(신텍스 분석과 코드 생성), 7, 8장에서 가상머신에 대해서 배운다고 했고 그러면 이제 OS만 남는거 같은데 이 OS는 정처기나 운영체제 수업을 들어도 OS가 프로세스니 응용과 하드웨어 사이를 연계해주니 자원 관리하는다고 배웠던거 같기는한데 그렇게 와닿지는 않았었다.

 당장 여기서는 OS가 라이브러리들을 모은 것이라고 설명하고 있다. 문자열 처리나, 메모리 관리, 그래픽 처리, 유저 인터페이싱 등을 처리하는 라이브러리들의 모음. OS라고 하면 프로그래밍 언어로 컴파일해서 돌아가는 뭔가라 생각했는데, 라이브러리의 집합이라고 하니 조금 생소하게 느껴지긴하다. 아무튼 이 OS가 저급 언어와 JACK 사이의 그동안 아무리 들어도 외우기만 했지 막연했던 연결고리 같은 역활을 한다고 하며,

  JACK이라는 프로그래밍 언어를 쓸수 있게 만드는 프로그램(OS를 말하는건지는 아직 잘 모르겠지만)을 어떻게 JACK으로 구현하는지를 배우게 되는데 이 방법을 부트스트래핑이라고 한다. 이 부분의 말이 잘 이해가 가지는 않는데, JACK을 VM 코드로 변환해주는 컴파일러를 JACK으로 만드는 방법을 배운다고 이해하면 되는건지 아직 감은 잘 안잡히지만 지금은 그냥 넘어가야 될거같다.

 아무튼 12장에서 OS를 만드는 과정에서 하드웨어와 주변 장치를 효율적으로 제어 할수있게 하는 자료 구조와 알고리즘 기법들에 대해서 배우고 JACK으로 구현하는게 소프트 웨어 파트 전체적인 틀인거 같다.

중간에 JACK 코드 예시나

운영체제가 뭔지 컴파일러가 뭔지 조금 나오는데 보고 싶은 부분만 잠깐 짚고 넘어가면

OS : main 함수 단에서 문자열을 출력할때, 여기다가 코드가 어떻게 된지는 적지는 않았지만, output.printString 이라는 함수를 쓰는데, 이 함수가 OS API, OS에서 에서 제공하는 표준 클래스? 라이브러리 내용이란다. 그리고 객체를 생성할때 RAM 상에 새 객체의 주소가 어딘지, 어떻게 프로그램 동작 과정에 메모리를 효율적으로 관리할지가 OS의 영역이다.

컴파일 : 심볼릭한 고급 언어를 돌리려면 기계어로 바꿔야하는데 이 과정이 컴파일이며, 고급 언어 프로그램을 컴파일하는 프로그램이 컴파일러가 된다. 근데 아까 2 단계 컴파일에 대해서 언급했는데, JAVA, C#, python 등이 이런 2단계 컴파일을 하는 고급언어라고 한다. JAVA의 경우에는 컴파러로 컴파일을 하면 bytecode라고 하는 중간 코드가 나오고 이를 타겟 플랫폼의 JVM에서 기계어로 번역되어 동작한다. 

 2단계 컴파일을 하는 이유는 7장 끝에서 자세히 나오니 지금은 넘어가야지

nand 2 tetris PPT에서 이해하기 좋게 나와있으니 좀 복사해와서 쓰면

7장 가상머신 동작에서 배울 내용들을 아래와 같다. 

굳이 한글로 다시 정리한다면 이럴거같은데. 

개요

- 앞으로 배울거

- 컴파일

VM 요악

- 스택

- 메모리 세그먼트

 abtraction 이걸 그냥 앱스트랙션이라 하는게 나을지, 요약이라 할지 아니면 인터페이싱이라고 할지 고민하다가, 다른데는 추상화라고 하는거같기는 한데, 추상화라고 하면 너무 막연한 단어인거같아서 요약이라고 적었지만 인터페이싱이 더 맞는 느낌인거 같다. 추상화나 인터페이싱이나 거기서 거기긴한데 abstrction 적힌걸 인터페이싱이라 하면 뜬금없는거같고, 추상화라고 하기에는 거부감이 좀 든다. 아무튼 추상화라 하면 실제 타겟 플랫폼에 맞게 구현하는건 아니지만 여러 플랫폼에서 사용 가능한 전체적인 틀을 짜는 정도?로 알고 넘어가면 충분할거같다.(1장인가 2장인가 쯤에서 이 개념을 입출력이 어떻게 되는지만 정의한거라고 썻던거 같은데 그게 그거지)

VM 구현

- 스택

- 메모리 세그먼트

VM 구현 플랫폼

- VM 에뮬레이터

- VM 번역기

VM 번역기

- 구현법

- 구현하기

JACK 언어로 Hello World를 하려면 알아야 할것들과 추상화

 보통 코딩을 처음 공부할때 hello world를 치는 방법을 배울때 언어 기초 문법을 잠깐 배우고 바로 적어서 해내기는 했지만, 이 장을 시작하기 전에 JACK언어로 문자열을 출력하려면, OS API를 써야 된다고 짧게 말하고 넘어갔어도 실제로는 화면 띄우기, 클래스와 함수 처리하기, do와 while(와일은 위 jack 프로그램에 보이지는 않지만 os 라이브러리 어딘가에 있어서 넣은거같다.), 함수 호출과 리턴, 운영체제 등이 다뤄지고 있다.

 하지만 프로그래밍 하는 사람들 중에서 하드웨어와 운영체제 단에서 이런걸 이해하고 코딩하는 사람은 비교적 적을거같다. 이런걸 몰라도 알아서 다해주니까, 위 내용들을 몰라도  output.printString()만 치면 알아서 자원 할당하고, 함수 호출해서 화면에 띄워주는데 맨 앞에만 알아도 되는걸, 다시 적으면 output.printString()이란 함수와 매개변수, 출력만 알아도 원하는 동작이 되는걸 추상화라 생각해도 충분할거같다. 아깐 abstraction을 요약이라고 했지만 요약이라고 하기에는 부족한거 같아서 앞으로는 추상화라고 하지만 그때 그때 병행해서 써야겠다.

 이 글을 처음 쓸때는 책의 SOFTWARE 개요 파트만 보면서 정리했는데, 지금 강의 자료 앞부분을 보니 아까 적은 내용들이 나온다. 강의 자료 내용을 앞에다가 다시 끼워 넣으면 꼬이는 글이 더꼬일거같아서 그림이랑 같이 반복하면

1단계 컴파일	2단계 컴파일

1단계 컴파일에다가 gcc 예시를 갖다 붙이려 했는데 번거로울거같아서 그냥 생략하고, Atmega 128같은 마이크로 프로세서에다가 컴파일 해서 짚어넣으려고 하면 각 타겟 보드/플랫폼이 뭔지 선택해야하는데 각 타겟에 맞는 컴파일러를 써야하는게 1단계 컴파일의 특징이고

2단계 컴파일 같은 경우에는 자바로 프로그램 짜고 컴파일을 시키면 바이트 코드라고 하는 가상머신 코드(중간 언어)가 나오는데, 이걸 각 플랫폼에 맞게 구현한 JVM에 돌리면 프로세스가 동작할수 있는게 특징이 된다. 아, 다시 정리하면 2단계 컴파일에서 1번째 번역기를 컴파일러, 2번째 번역기를 가상머신(번역기)가 된다.

 근데 이렇게 적었지만 여전히 각 플랫폼에 맞는 컴파일러를 작성한거나, 각 플랫폼에 맞는 JVM 을 만들어서 돌리는거나 결국에는 둘다 각각 컴파일러랑 가상머신이 필요하다는 점에서 뭔 차이인가 싶어서 그렇게 와닿지는 않는다. 책에서 계속 2단계 쓰는게 효율적이라고는 하는데, 각 플랫폼 컴파일러 짜는것 보다는 가상머신 만드는게 일이 적어서 그런건지. 아무튼 뒷부분에 역사적인 배경이 나오긴 하는데 그걸 다시 봐야 더 이해할수 있을거같다.

 이 책을 보면서 7장에서 가장 햇갈렷던 부분에 VM 에뮬레이터랑 VM 번역기였는데, PPT로 보니까 좀 다르기는 하네. 글 순서에는 맞진 않는데 HACK 컴퓨터에 맞는 기계어를 만드는게 VM 번역기고, 지금 사용하는 PC에서 JACK 중간 언어를 돌릴수 있게하는게 VM 에뮬레이터인거같다. 잠깐 든 생각은 넘어가고 여기서 우선 VM 추상화? 추상 모델에 대해서 정리하면서 VM이 어떻게 된건지 어떻게 동작하는지를 보고 HACK에 맞는 VM 번역기 프로그램 구현에 대해서 다루게 된다. 

 그래서 계속 VM 코드가 나오는데 VM 코드는 산술, 논리 연산과 메모리 제어 명령인 push와 pop, 분기 명령, 함수 호출 반환 명령 등으로 이뤄져 있다. 이 장에서는 기본 VM 번역기를 만들면서 산술논리연산과 push/pop 연산을 다루고, 다음 장에서는 분기와 함수 관련 명령을 배워 기본적이지만 완전한 가상 머신을 구현하게 된다. 그리고 이번 장에서 가장 중요한 스택의 동작 과정을 정리해보자.

스택 머신과 동작 과정

 저자 분은 앞으로 VM 코드는 컴파일러로 쉽게 생성할수 있을 만큼 충분히 "고급 언어에 가까"워야 하며, VM 번역기로 효율적으로 기계어를 생성할 수 있을 만큼 "저급"이 아니라 "기계어에 가까워야" 한다고 한다. 즉, VM 코드는 고급어와 저급어의 차이를 잘 매꿔줘야 하는데 이를 가장 잘 정리할수 있는 자료 구조가 스택이며, 이 스택으로 번역 과정을 처리하는 아키텍처/구조를 스택머신이라고 한다.

 스택이 어떻게 된건지, 연산하는건지는 자료구조 공부하면 나오는거니 그냥 넘어가고, VM code를 stack에서 어떻게 산술 논리 연산을 하는지 보면

 우선 산술 d = (2-x) + (y+9) 라는 산술연산의 과정을 보자.

1. push 2 : sp에 상수 2가 들어간다.

2. push x : sp에 변수 x의 값이 들어간다.

3. sub : 스택 최상위 2개의 값을 매개변수로 받아 뺀다. 2 - x

4. push y : sp에 변수 y의 값이 들어간다

5. push 9 : sp에 상수 9가 들어간다.

6. add : 스택 최상위 값인  y와 9를 꺼내 +연산 후 결과인  21를 push 한다

7. add : 최상위에 있는 -5와 21를 pop 한 뒤 -한 결과인 16을 push 한다.

8. pop d : 최상위에 있는 값을 pop 하여 메모리 변수 d 공간에 넣는다.

이번에 논리 연산 경우를 보자.

과정인 산술 연산과 동일하지만

논리 연산의 결과 true, false가 push 된다.

가상 메모리 세그먼트

 특히 이 부분이 부족한 영어 실력으로 봐도 봐도 이해가 잘안가는 부분이었는데, ppt를 같이 봐야 이해가 좀 쉽더라

 일단 메모리 세그먼트를 보기에 앞서 고급 언어를 공부하면 변수로 위의 소스코드 처럼 클래스 단의 static 변수나 함수 선언 문의 매개변수, 그리고 함수 안의 지역변수, 그리고 각 인스턴스의 속성 field 변수 등이 있다고 배웠을 것이다.

 하지만 JVM이나 hack 플랫폼에서는 위의 s1, s2, a, b, c같은 심볼릭한 변수를 사용하지 않고, 가상 메모리 세그먼트의 일부로 표현하는데 이게 무슨소리냐면 static int s1, s2가 있으면 이 변수를 s1, s2라는 이름이 아닌 static 0, static 1 같은 식으로 변수로 사용하며, static 외의 변수 argument, local, static, constant, this, that, pointer도 뒤에 해당 변수의 번호를 붙여 쓴다.

 예를 들어 지역 변수 x가 local 1, 인스턴스 속성 y를 this 3이라 할때 let x = y를 한다면, 스택에다가 y라는 값을 넣은 후(push), 스택의 값을 꺼내서(pop) x에다가 저장해야한다. 다시 정리하면 let x = y 연산은 아래와 같다.

push this 3  // 인스턴스 속성 변수 y(=this 3)을 스택에 넣어라 

pop local 1 // 지역 변수 x(local 1)에다가 스택 최상위 값을 꺼내서 넣어라

 위 내용만 봐서 가상 메모리 세그먼트가 뭔가 싶은데, ram 안에 argument, local, static, constant, this, that 등 각각의 메모리 세그먼트(일부 공간)이 존재한다고 보면 될거같다. 아래의 그림을 보면 이해가 더 잘될거 같은데 고급 언어 코드가 어떻게 VM 코드로 변환되는지 각 가상 메모리 세그먼트와 같이 정리되어있다.

그러면 위 그림의 고급언어 소스코드 let c = s1 + y; 부분을 컴파일한 VM Code 결과가 우측과 같이 된다.

차례를 정리하면 우측 항(s1 + y)를 한 후 좌측 항(let c)에다가 대입 해야하므로 다음과 같이 정리할수 있을거같다.

s1 + y 연산

1. push static 0 // static 가상 메모리 세그먼트의 0번째 값(s1)을 stack에다가 넣는다.

2. push argument 1 // argument 가상 메모리 세그먼트의 1번째 값 y를 넣어라.

3. add // stack 최상단 2개 값을 꺼내(pop), 덧셈 연산한 뒤에 스택에다가 다시 넣어라(push).

let c = s1 + y 연산

4. pop local 2 //스택 최상단 값(s1 + y)을 꺼내 local 2에다가 넣어라

스택 연산과 가상 메모리 세그먼트

 스택과 가상 메모리 세그먼트 두가지만 놓고 본다면 위 처럼

push segment i

pop segment i

같은 문법으로 스택과 메모리 세그먼트 간에 값을 넣고, 꺼내고의 연산이 수행된다.

로컬 메모리 세그먼트의 3번지 값(200)과 4번지 값(1000)을 더한 후 static 메모리 세그먼트의 2번지에다가 넣는다면 다음과 같이 쓸수 있을거같다. (진작에 PPT랑 같이 볼껄, 괜히 잘 이해도 안되면서 그동안 책만 보느라 너무 해맨거같다.)

push local 3

push local 4

add

pop static 2

타겟 플랫폼(HACK)을 고려한 VM 구현

 앞서 언급한 VM과 스택 머신에 대한 내용은 특정한 하드웨어 플랫폼을 고려하지 않은 추상화/요약한 것이라. 실제로 만들어 내려면 특정 하드웨어 플랫폼을 고려해서 표현해야 한다. 여기서는 VM 번역기를 구현하려고 하는데, 이를 만들려면 스텍과 타겟 플랫폼의 가상 메모리 세그먼트를 어떻게 할것인지를 고민해야하고, 또 VM 코드를 어떻게 타겟 플랫폼의 저급언어인지를 정리해야한다.

 추상화와 구현의 차이 : 다시 정리하자면 이 앞의 내용은 VM 코드를 타겟 플랫폼의 어셈블리어를 고려하지 않은체 어떤 가상 메모리 세그먼트가 있고, 어떻게 연산할 것인지 대략적으로 정리했는데 어느 플랫폼에 한정하지 않고 대략적인 동작을 정리한 앞의 내용들을 VM 추상화 한것이라 하고, VM 코드와 타겟 플랫폼의 어셈블리어를 고려해서 맞춰 나가는걸 VM 구현이라 하는 거 같다.

 만들고자 하는 플랫폼이 폰 노이만 아키텍처를 따르고, VM 스택이 메모리 공간의 블록이며 이 VM 스택 블록은 고정된 베이스 주소에서 시작한다고 하자. 그리고 스택이 쌓일 수록(= 위에서 스택 연산 그림처럼 내려가는걸) RAM 상의 주소가 증가하고, 스택을 초기화/처음 만들면 스택 포인터를 스택 베이스로 지정해놓자.

 그러면 이제 vm 코드인 push x과 pop x를 슈도 코드로 다음과 같이 표현 할수있다.

RAM[sp++] = x // push x = RAM[sp]에다가 x를 대입 후 sp를 1증가시켜라

x = RAM[sp--] // pop x = 변수 x에다가 RAM[sp]를 대입 후 sp를 1 낮춰라

이렇게 슈도 코드를 작성했으니 이번에는 이걸 어셈블리어로 표현시켜보자. 우리가 만들 HACK 컴퓨터는 스택 베이스 주소를 256로 잡고 있다. 그래서 SP = 256으로 설정해서 어셈블리어로 스택 초기화부터 시켜주면

@256

D=A

@SP

M=D

를 하면 SP 라는 가상 메모리 레지스터(R0)에다가 스텍 베이스 어드레스 256가 등록된다.

 => RAM[0] = 256 // ram 0번지가 스택 포인터이며, 베이스 어드레스 256 등록

그럼 이제 push x와 pop x는 아래의 연산이므로

1. RAM[256] 번지에 x를 넣고, sp++ 

2. RAM[256] 번지 값을 변수 x에다 넣고, sp --

어셈블리어로 표현하면 다음과 같을거 같다(책에 있는게 아니라 그냥 내가 짠거라 맞는지는 모르겠지만 대강 고급 언어랑 비슷한 슈도 코드를 위 SP 초기화 부분을 참고해서 이렇게 어셈블리어로 써봤다.)

1. RAM[SP++] = x

@x

D=M

@SP

A=M //SP(RAM[0])에 있는 값인 M(256)을 꺼내서 어드레스 레지스터 A에다가 넣어라

M=D //RAM[256]번지에 데이터 레지스터의 값(변수 x의 값)을 넣어라

@SP

M=M+1 //SP++

**

@SP

M=D

위 코드처럼 해버리면 R[0] = D가 되버리는거같아서 @SP에 있는 값인 256을 어드레스 레지스터 A에다가 담은 후 M으로 RAM[256]에 접근해 RAM[256] =D가 되도록 썻다.

2. x = RAM[SP--]

이 코드의 경우 현재 SP가 257이지만 꺼내고자하는 값은 257번지가 아닌 256번지에 있으므로 SP--와는 다르게 먼저 SP부터 -1해주자

@SP

M=M-1 // SP-- => SP가 257에서 256이 된다.

@SP

A=M     //어드레스 레지스터에 256을 넣어 RAM[256]에 접근가능하도록하자

D=M     // RAM[256]의 값을 데이터 레지스터에 저장한 뒤

@x

M=D     // 변수 x에 데이터 레지스터에 저장해둔 RAM[256]의 값을 넣자

내가 책만 보고 이해한 내용은 위와 같은데 강의 자료에서는 그림과 같이 보기 좋게 추상화와 구현을 보여주고있다.

 위 그림에서 보면 위의 abstaction 부분에서 push constant 17이라는 추상화된 VM 명령을

아래의 구현 파트에서 HACK 플랫폼에 맞게 어셈블리어로 정리하여 보여주고 있다.

구현 파트의 좌측 메모리를 보면 스택 포인터가 258을 가리키고, 258번지는 비어있었으나

push constant 17을 한 결과 sp는 259으로 +1이 되고, 스택 포인터가 가리키던 258번지에 17이 들어가 져있다.

다시 정리하자면 이와 같이 추상적인 VM 명령어들로 특정한 타겟 하드웨어에 맞는 저급언어를 만들어 내는것을 VM 구현 혹은 VM 번역기라 한다.

VM 프로그램

 VM 프로그램은 다음 장에서 제대로 정리할거지만 VM 명령으로 이뤄진 프로그램이고, 확장자는 .vm으로 한다. 이 프로그램은 가상 머신 번역기로 한줄 한줄 읽어서 저급 언어로 번역되어 foo.vm을 번역후에는 foo.asm 파일이 나오게 된다. 

가상 머신과 RAM

 앞 장에서 이미 봤었지만 Hack의 RAM은 32K 16비트 워드로 이뤄져 있었다.(하드웨어 만들때 16K RAM에다가 8K 스크린, 1개의 키보드 레지스터를 합쳐서 만들었던거 같긴한데 그냥 넘어가자) 여기서 RAM 주소 상 0 ~ 15는 가상 레지스터, 16 ~ 255는 정적 변수, 256 ~ 2047 은 스택 영역으로 사용하고 있으며, RAM[0]에서 RAM[4]번지 까지를 SP, LCL, ARG, THIS, THAT이라는 심볼릭한 변수 명으로 접근해서 쓸수 있고 이 주소들에 대한 내용은 아래의 표를 참고하자.

local 메모리 세그먼트 구현

 앞서 스택의 상수 연산을 어셈블리어를 통해 구현한것 처럼 로컬 변수를 사용한 VM code를 번역한 결과 우측의 어셈블리 슈도 코드처럼 만들수 있다. 실제 위 슈도 코드를 어셈블리어로 정리하는건 시간 부족으로 그냥 생략하고 넘어간다. 그래도 잠깐 내용을 언급하고 넘어가면 LCL은 RAM[1]에 위치하고 있으며 베이스 어드레스가 1015가 된다. 

 LCL의 경우 값을 넣거나 뺄때마다 +1 혹은 -1 되던 SP와는 다르게 항상 고정된 값, 로컬 메모리 세그먼트의 베이스 주소를 가지고 있고 이 값은 변하지 않는다. 대신 pop/push local i 명령어가 올때마다 addr=LCL + i를 하듯이 기존 베이스 어드레스에서 해당 로컬 변수의 번호를 더한 주소에다가 값을 넣거나 가져온다.

 다시말하면 LCL은 1015인 베이스 주소를 가지고 있고, push local 1을 한다면 addr = LCL+1, *SP = *addr, SP++ 연산을 하는데, RAM[1016]의 값을 스택 포인터가 가리키고 있는 위치에다가 대입하고, SP를 ++한다.

local, argument, this, that 메모리 세그먼트가 필요한 이유

 결국에는 이런식으로 메모리의 일부, 세그먼트를 만들어서 사용하는 이유는 뭘까. 각 가상 메모리 세그먼트 이름에서 알 수 있다시피 local 세그먼트는 로컬 변수들을 보관하기 위해서, argument는 매개변수를 보관하기 위해서 this의 경우 현재 객체의 속성값을 다루기 위해서, that은 각 객체들(인가?)을 배열 처럼 다루기 위해서 만든 공간인거 같다.

 이번 장을 공부하면서 아직 제대로 파지 않은 부분도 있고, VM 구현도 하기는 해야되지만 한동안은 이론 내용을 전체적으로 전보다는 좀 빠르게 훑어보려고 한다. 그래도 책만 아니라 PPT도 같이 본 더분에 많은 내용이지만 생각보다 빠르게 진도 나갈수가 있었다.

7장 VM 동작

1. 스택 머신

2. 메모리 세그먼트

3. VM 추상화와 구현

 이번 장에서 정리한걸 크게 구분하면 위 세가지가 될거같고, 어느 정도 이해한거 같으니 이제 넘어가자.

 여기서 만들 hack 어셈블러는 아무 고급 언어로 만들어도 된다고 한다. c나 자바같은 다른 언어는 공부한지 오래되서 다까먹엇다보니, 그냥 파이썬으로 구현해봐야될거 같고, 그러면 이런식(pyinstaller로 실행 파일로 만들지 않은 이상)으로 입력하면 기계어 파일을 만들도록 할거같다.

 >python myAssembler Mult.asm

하면 Mult.hack이라는 기계어 바이너리가 나오도록

 그런데 어떻게 어셈블러를 만드는게 좋을까?

 책에서 말하기를 처음부터 다 하기보다는 두 단계로 나누어서 처음에는 심볼릭 참조 처리(대치)하는걸 고려하지 않은 어셈블러를 만들고, 동작이 잘 되면 심볼릭 참조 처리가능한 어셈블러를 만들라고 한다. 테스트 스크립트도 심볼릭을 쓴것과 안쓴 버전이 있다.

 베이직 어셈블러 만들기

 일단 베이직 어셈블러는 심볼 테이블을 제외한 내용들 그러니까 주석, 스페이스바를 넘기고 기계어록 하는 정도를 할수 있으면 되는거같은데, 베이직 어셈블러 구성요소로 파서 모듈과 코드 모듈을 만드는걸 추천하고 있다. 파서.. 프로그래밍 하다보면 종종 마주치는 용어인데 사전 보면 분석하다라고 나와있다.  근데 보통 동작은 다른 형태로 변환시키는게 주인거 같았는데, 당장은 입력을 분석해서 어째 저째한다는 의미 정도로 이해하고 넘어가야 겠다.

 코드 모듈은 한글로 코드라 하면 늬앙스가 전달이 잘 안되는거 같고, 부호화라 하기에는 너무 딱딱하단 생각이 든다. 그냥 어셈블리어를 기계어로 부호화(변환) 시켜주는 부분이라 생각하자. 정리하면 파서는 어셈블리어 분석기, 코드는 어셈블리어 변환기 정도?

 파서 모듈 & 코드 모듈

 친절하게도 저자 분이 구현해야할 각 모듈별로 추천하는 함수와 매개변수, 반환값 동작들을 다 정리해주고 계신다. 근데 내가 정리하기는 싫어서 구현해놓고 그냥 동작하는지만 보고 코드나 올려야겠다. 

22.05.23

위 내용은 지난 금요일날 어셈블러 구현하면서 작성했었는데

기본어셈블러야 구현자체는 할수있겠는데, 책에서 요구하는 

함수, 매개변수 등을 어떻게 맞춰야할지 고민하다가 시간을 다보내버렸다.

구현하고 에러잡는데 너무 시간을 많이낭비해서 좀 고민해봤는데

구현은 2-3시간 정도만하고 안된건 기존 내용참고해서 하려고한다.

일단 기본 어셈블러 구현하다만게있는데 나중에 다시하고싶어지면하고

이론내용부터 정리해봐야겠다.

어제 겨우 겨우 HACK 구현을 마무리하고

SW로 넘어가기 전에 어셈블러에 대해서 짚고 넘어가야한다.

어셈블러야 4장에서 기계어 바이너리와 심볼릭한 기계어(어셈블리어)에 대해서

살펴보고 직접 구현했고, 어떻게 어셈블리어가 기계어가 매칭되는건지 알고 있다.

근데 4장에서 시뮬레이션을 돌릴때

작성한 어셈블리어 코드 한줄 한줄은

ROM에서 각자의 주소를 가지고 있었고 이들을 PC를 통해 넘어가거나 JUMP해서 다음 명령어를 수행할수 있었다.

라벨 심볼, 변수와 심볼 테이블

그런데 (LOOP), (END) 같은 라벨 심볼과 점프하기 전에 이 라벨심볼이 있었을때나 @LOOP, @END

@i, @sum과 같이 변수 준 경우까지 분명 어떤 주소를 가리킨게 아니었어도, 시뮬레이션을 실행시키면  @LOOP 이던데가 @23이라던가 @i가 @53로 바뀌어져 있었다.

 위는 4장에서 진행한 mult.asm 코드와 이를 cpu 에뮬레이터에 올렸을때 rom에 올라간 각 명령어들의 주소를 보여준다.

이 어셈블코드는 중간에 주석이 없음에도 총 26줄이었지만 ROM에 올라가면서 미리 정의된 심볼이 상수 주소로 바뀌었고, 라벨 심볼 (LOOP)는 사라졌었다. 그러면 이 라벨 심볼을 가리키고 있던 @LOOP는 어떻게 되었는지를 보면 @10으로 바뀌어 있다. 

 뒤에나오지만 미리 정의된 심볼이야 그 심볼들의 고유의 주소를 갖고, 라벨 심볼의 경우 그 라벨 심볼의 다음 줄에 있는 명령어를 가리키게 된다. Mult.asm의 경우 @LOOP는 기존의 (LOOP) 다음에 @R1(그리고 그 뒤에는 D=M)이 있었으므로 @LOOP는 @1(원래는 R1이므로 미리 할당된 주소 1으로 대체됨) 명령어의 주소인 @10으로 바뀌게 되었다.

 이 때 라벨, 변수 심볼릭의 주소를 정리하기 위한 심볼 테이블이 사용되는데 어떻게 심볼릭 라벨과 변수가 각자의 주소를 가지게 되었는지를 그리고 심볼 테이블과 어셈블러의 동작 원리를 알아보고, 직접 구현한다.

HACK 어셈블리어 복습

 hack의 심볼릭과 바이너리 명령어를 정리한 테이블인데 또 복습을 할 필요가 있나 싶지만 잠깐 짚고 넘어가면 심볼릭에 따라 위 테이블의 바이너리가 나온다.

 심볼릭에는 선정의된 심볼릭으로 가상 레지스터(R0, R1 ..., R15)가 있었고, 주소를 나타내는 SP, LCL, ARG, THIS, THAT, SCREEN, KBD도 선정의된 심볼릭이다(SP, LCL, ARG 등은 가상 머신 파트에서 다룬다). 라벨 심볼은 미리 정의되지 않았지만 어셈블리어를 작성하는 사람이 임의로 정할수 있는 점프 주소를 나타내는 심볼릭이 된다. 그리고 변수 심볼이 있지만 대충 넘어가고, 어쨋든 어셈블리의 과정에서 심볼릭으로 작성한 A 명령어들은 이 심볼들의 실제 주소를 나타내는 심볼 테이블의 값을 참조하여 대체된다. 

 심볼릭 규칙이야 심볼은 _, ., $,  : 같은 특수기호로 시작되면 안되고, A 명령어 상수(주소)의 경우 0-32767(접근 가능 주소 공간 크기 : 2^15-1)의 범위 내여야 하며, 공백이나 빈줄은 넘어가니 ok, 위 동작을 나타내는 심볼릭<->기계어 테이블에도 나오지만 변수나 상수를 제외한 대부분의 경우 대문자로 써야한다.

어셈블러의 동작

 일단 어셈블러의 동작을 크게 두가지로 나누면 명령어 처리와 심볼 처리가 있다.

1. 명령어 처리

 어셈블러는 입력된 어셈블리어를 위 표처럼 기계어로 변환시켜야하고, 심볼릭 참조/참조 심볼릭이라고나와 있기는 한데 그냥 숫자 주소로 나타내는, 그러니까 실제로는 숫자 주소인 곳을 참조(의미)하는 라벨 심볼, 변수 심볼을 문자가 아닌 숫자(실제 주소)로 바꿀수 있어야한다. 

2. 심볼 처리

 일단 어셈블러로 어셈블리어를 변환시킬때 라벨 심볼이나 변수같은거 없이 상수만 쓰라고 할수도 있겠지만 어셈블리어로 코드를 짜야하는 사람들을 위해서 심볼릭을 쓸수 있게 해두었는데, 이를 위해서 어셈블러는 어셈블리어 코드 전체를 두번 봐야한다. 어셈블리어를 두번 읽어(한번은 심볼테이블만 만들고, 다음에는 심볼테이블을 참고하여 기계어로 변환) 변환하는 어셈블러를 투 패스 어셈블러라고 부른다.

 투 어셈블러의 동작 과정은 두번 통과하기 전에 초기화 과정에서 우선 심볼 테이블을 만들고, 거기다가 선 정의된 심볼들과 그의 주소들을 넣어둔다.

 첫 번째 통과 과정에서는 한줄 한줄 읽어가면서 라벨 심볼을 선언하거나 주석인 경우를 제외하여 A나 C 명령어를 만날때마다 0에서 시작하여 +1씩 카운팅을 하는데, 그러던 중에 (LOOP) 같은 라벨 심볼 선언문을 만났을때 심볼 테이블에다가 추가하고 그 라벨 심볼을 만났을때 카운팅 한 값 + 1 한 것을(라벨 심볼 다음 명령어 ROM 상의 주소)을 넣어주는 식으로 (LOOP)를 만났을때 카운팅된 값이 25이면, 라벨 테이블 상에서는 26이 등록된다.

 위 심볼 테이블의 LOOP 같은 경우에는 주석문을 제외하고 보면 @i가 ROM의 0번을, M=1가 ROM의 1번을, @sum이 ROM의 2번을, M=0가 ROM의 3번을 받고, 그 다음에 (LOOP)를 만났으므로 심볼 테이블에 LOOP : 3 + 1=4가 심볼 테이블에 추가된다 하지만 라벨 심볼이 선언되었으므로 아직은 +1하지 않고, 그 다음의 @i는 ROM의 4번 주소를 받게 된다. 이 부분이 조금 했갈리지만 (LOOP)에서도 +1 카운팅을 했다면 @i는 ROM의 5번 주소를 받게 될것이다. 아무튼 이 과정에서는 변수는 아니지만 라벨 심볼의 주소들을 심볼 테이블에 등록해는것 까지만 하였다.

 두 번째 통과 과정에서는 기계어로 번역하면서 변수도 처리하는데, 변수를 만난날 때 어떻게 되는지 예를들어 생각해보자. 만약 번역 중에 @R0을 만났을 때 하자 R0은 이미 심볼 테이블에 ROM의 0번 주소라고 정의되어있으므로 0으로 대치하여 기계어로 번역하게 된다. 하지만 심볼 테이블에 등록 되지 않은 경우에는 이 변수를 심볼 테이블에다가 추가하고, RAM 상의 주소를 할당받게 된다.

 잠깐 앞에서 햇갈렸던거 같은데 (LOOP), @LOOP 라벨 심볼의 경우 @LOOP는 점프할 명령어 주소, 그러니까 ROM 상의 주소로 대치되고, @i, @sum과 같이 라벨 심볼이 아닌 변수의 경우는 명령어의 주소가 아닌 데이터의 주소 RAM 상의 주소로 대치된다. 

 아무튼 다시 돌아와서 심볼 테이블에 없는 새 변수를 처음 만나게 된다면 RAM의 16번지를 할당 받게 되는데 0 ~ 15까지가 가상 레지스터 선정의 된 심볼들의 저장 공간으로 먼저 할당 받았기 때문이다. 그래서 그 다음 또 새 변수를 만나면 17, 18, ... 씩 올라가며 주소를 값으로 가지게 된다.

 다시 어셈블리어와 심볼 테이블을 보면, 첫번째 패스로 LOOP와 STOP의 ROM 상의 주소가 선정의된 심볼들(KBD 뒤에 LOOP) 다음에 추가 되어 있고, 두 번째 패스때 가장 먼저 변수 @i를 만나 RAM 16번지를, 그 다음에 @sum을 만나면서 RAM 17번지가 할당되어있다.

 이번 장은 간단한 어셈블러를 만드는거다 보니까 투패스와 심볼 테이블 말고는 크게 새로운 내용도 없고 분량도 적었다. 이제 어셈블러 구현으로 넘어가자.

이전 글에서 겨우 겨우 CPU를 완성하고,

그 다음으로 만들건 32K ROM이다 32K니까 2^5 * 2^10 = 32 * 1024이고 2^15만큼의 주소를 갖는다.

1. ROM 32K

 롬이야 읽기 전용 기억장치이니 쓰기를 위한 load 단자는 필요없고, 지난번에 16K까지 만들었는데 그냥 RAM16K 2개를 디먹스로 연결해주면 될거같다.

 근데 5장에서 롬을 만들려고 하니까 ROM.hdl은 없고 남은건 memory(ram)와 computer 뿐이다. rom은 어샘블러로 만든 기계어를 넣어둿다가 꺼내서 실행하니까 별도로 만드는건 아닌거같다.

2. RAM

 그래서 바로 램을 구현하게 잠깐 살펴보자. 여기선 RAM이랑 다른 입출력장치 매모리맵을 합쳐서 memory라고 하고 있네, RAM은 이전에 본 대로 16K 크기에다가 16K인 이유는 A 명령어가 14개의 비트 크기의 값과 주소를 저장해서 사용하기 때문이며, 그 뒤에는 스크린과 키보드의 공간이 존재한다.

 스크린은 16K램뒤에 바로 붙기 때문인지 16,384부터 시작하며, HACK의 스크린은 256 x 512 크기로 2^8 x 2^9 = 2^17 이나 레지스터 한개에 16=2^4개의 픽셀 값이 매핑되어있으므로 메모리 맵 상에서는 2^17/2^4 = 2^13 = 8K의 크기를 갖는다.  키보드야 키보드 베이스 레지스터 한개만 읽으면 되니 주소는 24,576 하나 뿐이다.

 HACK 컴퓨터의 메모리에 관한 설명은 여기까지 하고 바로 구현해보자

RAM16K(렘), RAM8K(스크린 매모리맵), register(키보드 메모리맵) 각각 한개씩에다가 어째저쨰 잘 연결하면 될거같다.

 어떻게 할까 생각해봣는데 일단 address[15]를 sel단자에 받는 디먹스를 놓고 생각해봐야할거같다.

CHIP RAM64 {
    IN in[16], load, address[6];
    OUT out[16];

    PARTS:
    DMux8Way(in=load, sel[2]=address[5], sel[1]=address[4], sel[0]=address[3],
    a=ram0load, b=ram1load, c=ram2load, d=ram3load, e=ram4load,
    f=ram5load, g=ram6load, h=ram7load);

    RAM8(in=in, load=ram0load, address[2]=address[2], address[1]=address[1], address[0]=address[0], out=r0);
    RAM8(in=in, load=ram1load, address[2]=address[2], address[1]=address[1], address[0]=address[0], out=r1);
    RAM8(in=in, load=ram2load, address[2]=address[2], address[1]=address[1], address[0]=address[0], out=r2);
    RAM8(in=in, load=ram3load, address[2]=address[2], address[1]=address[1], address[0]=address[0], out=r3);

    RAM8(in=in, load=ram4load, address[2]=address[2], address[1]=address[1], address[0]=address[0], out=r4);
    RAM8(in=in, load=ram5load, address[2]=address[2], address[1]=address[1], address[0]=address[0], out=r5);
    RAM8(in=in, load=ram6load, address[2]=address[2], address[1]=address[1], address[0]=address[0], out=r6);
    RAM8(in=in, load=ram7load, address[2]=address[2], address[1]=address[1], address[0]=address[0], out=r7);

        
    Mux8Way16(a=r0, b=r1, c=r2, d=r3, e=r4, f=r5, g=r6, h=r7,
    sel[2]=address[5], sel[1]=address[4], sel[0]=address[3], out=out);
}

 지난번에 RAM 구현할때 디먹스랑, 먹스를 동시에 사용하면 편했는데 이걸 모르고 한참 삽질했었다.

이걸 참고해서 메모리를 구현해보자

잠깐 디먹스 파트를 생각해봤는데 대강 이정도면 될거같다

다만 키보드 레지스터의 경우 addr[0..12]가 00000...001이여야만 레지스터에 로드해야하는데

그 이상의 공간이 없으니 주소가 잘못 오는 경우가 없다고 생각하고 일단 구현해봐야겠다.

ram8k는 없어서 demux와 4k 2개로 대체한다.

CHIP Memory {
    IN in[16], load, address[15];
    OUT out[16];

    PARTS:
    //DMux part : set load bit
    DMux(in=load, sel=address[14], a=ram16kload, b=ram8kload);
    DMux(in=ram8kload, sel=address[13],a=ram8kload2, b=registerload);
    //ram 16k
    RAM16K(in=in, load=ram16kload, address=address[0..13], out=ram16kOut);
    //screem memory map
    DMux(in=ram8kload2, sel=address[12], a=ram4kload1, b=ram4kload2);
    RAM4K(in=in, load=ram4kload1, address=address[0..11], out=ram4k1Out);
    RAM4K(in=in, load=ram4kload2, address=address[0..11], out=ram4k2Out);
    //keyboard memory map
    Register(in=in, load=registerload, out=registerOut);

    //Mux part : get selected register output

}

일단 DMux 파트부터 구현했는데 오류는 뜨지 않는다.

이제 먹스 파트로 가서 주소에 따라 해당 메모리 값을 가져올수 있도록 하자.

잘 돌아가는데 키 입력이 되지를 않았다.

도저히 안되서 찾아보니

스크린 칩을 안쓰고 RAM4K 2개, 키보드 칩을 안쓰고 레지스터를 쓴게 문제였다 ..

빌트인으로 준건데!

위 그림처럼 다시 수정하면

CHIP Memory {
    IN in[16], load, address[15];
    OUT out[16];

    PARTS:
    //DMux part : set load bit
    DMux(in=load, sel=address[14], a=ram16kload, b=screenLoad);
    DMux(in=screenLoad, sel=address[13], a=screenload2);
    //ram 16k
    RAM16K(in=in, load=ram16kload, address=address[0..13], out=ram16kOut);

    //screem memory map
    Screen(in=in, load=screenload2, address[0..12]=address[0..12], out=screenOut);
    //keyboard memory map
    Keyboard(out=keyboardOut);

    //Mux part : get selected register output
    Mux16(a=screenOut, b=keyboardOut, sel=address[13], out=screenKeyboardOut);
    Mux16(a=ram16kOut, b=screenKeyboardOut, sel=address[14], out=out);
}

구현한 메모리 칩 테스트 돌려보니 키보드 입력도 잘받고 스크린 출력도 잘된다.

3. HACK 컴퓨터 구현하기

 드디여 nand2tetris 하드웨어 마지막 과제인 컴퓨터 구현까지 왔다. 앞서 어려운 로직들은 다 구현했으니까 이젠 연결만 하면 끝날거같다 ㅠㅜ

 동작이야 ROM32K에 입력된 명령어가져와서 CPU에서 연산하고 memory에 저장하고, 다음 명령어 이동해서 실행하고를 반복이고, reset 입력이 들어가면 프로그램 카운터가 0을 가리키면서 처음부터 재시작 된다.

 앞에서 하도 해매니까 컴퓨터 구현이 가장 쉽네 ㅋㅋㅋ

CHIP Computer {

    IN reset;

    PARTS:

    CPU(inM=inM, instruction=instruction, reset=reset, outM=outM,
    writeM=writeM, addressM=addressM, pc=pc);
    Memory(in=outM, load=writeM, address=addressM, out=inM);
    ROM32K(address=pc, out=instruction);
}

테스트가 너무 빨리 끝나서 screen 모드와 출력 모드 둘다 볼수 있게 찍었다.

이제 난드 게이트로 컴퓨터 구현까지 하드웨어 파트는 마무리했고,

이 다음부터는 소프트웨어 영역으로 넘어가게 된다.

익숙한 SW니까 금방 할수있을까 생각하다가 하드웨어에서 시간 엄청 낭비한걸 생각하면

소프트웨어도 HW 못지않게 해맬수도있을거같다.

 거의 일주일 동안 수업 시간을 제외해서는 하루종일 nand2tetris하면서 시간을 보냈다. 내가 이걸 하려는건 디지털 논리 회로 설계하려는건 아니고 컴퓨터 동작 원리를 제대로 공부하고 싶어서였는데 기계어, 어셈블리어, HW 구조 만큼은 제대로 굴럿다.

 이 다음에는 어셈블러, 가상머신, 고급언어, 운영체제, 어플리케이션 등이 나오는데, 끝날때까지 이것만 팔지 아니면 다른거랑도 병행해야할지는 좀 고민된다. 아마 이것만 올인하기는 시간아까워서 이전에 하다만 파이썬이나 공업수학이나 같이 병행하던가해야지.

우측 Mux16

 우측 먹스 16은 a 단자에 A registor, b 단자에 inM이 들어온다. 그러면 어떨때 A reg의 값을, 어떨때 inM의 값이 전달되는지 판단해야한다.

일단 1번지 명령어 실행한 결과 M=0이 실행되었지만 M/A에는 inM이 아닌 @A가 들어와있다.

지금 보니까 dest=(A or D or 1)+M 같은 경우가 아니라면 inM을 연산에 사용하는 경우가 아니면,

M/Ainput에 들어올 필요가 없을거같다.

그러면 A+M의 경우는 어떻게 해야할까.

다행이 hack의 alu는 A+M연산을 할일이 없다.

comp 연산 테이블을 자세히 보면

a==0인 경우 A를 연산에 사용하고, a==1인경우 M을 연산에 사용한다.

그러니까 여기까지만 보면 a==0의 여부에 따라서 우측 Mux16의 sel 단자를 선택해주면 될거같다.

우측 mux16는 기존에 이런식으로 되어있으면

명령어의 opcode가 1이고, a비트가1인 경우 우측 먹스 16의 sel 단자에 1을 넣는다(and 연산). 그 외 경우에는 c=0이

    //right Mux16
    And(a=instruction[15], b=instruction[12], out=mIsUsed);
    Mux16(a=aRegistor, b=instruction, sel=mIsUsed,out=inputMA);

이제 마지막으로 ALU를 정리하자

ALU의 제어비트 테이블

C명령어 제어 비트 테이블 ALU 입출력

 위 테이블을 보면 c 명령어의 c비트를 그대로 alu의 c비트로 넣어주면 될거같고.

zr과 ng는 구현은 했지만 어디다가 쓰라는 말은 없었다.

C 명령어때는알겠는데,

A명령어 때는 ALU는 어떤 출력을 하는지 잠깐 보면 이전 C 명령어의 연산 결과가 그대로 유지되고있다.

하지만 A 명령어의 11 ~ 6비트 자리의 값에 따라서 멋대로 ALU가 연산하고 결과를 내보내면 안되니 별도의 로직이 필요하고

ALU는 기억장치가 아닌데 값을 유지하려면 기존의 ALU 출력을 다시 피드백해서 내보내고 있어야한다.

ALU 출력 결과를 그대로 가져온다면 

1. D Registor의 값을 받아서 ALU가 그대로 내보내거나

2. 좌측 먹스에서 ALU OUT이 선택되고, A레지스터에 선택된후 우측 먹스를 통해 넘어온게 다시 출력으로 간다고 봐야할거같다.

아무튼 결국 A 명령어인 경우 a 혹은 b 입력을 그대로 전달해주기만 하면될거같은데.

a 단자를 전달한다면 001100, b단자의 값을 내보낸다면 110000을 제어 비트 단자에 넣어주면 되겠지만

어쩔때 a 혹은 b 입력을 전달할지 판단 기준이 필요하다.

....

와 CPU 구현하는데만 순수하게 6-7시간 쯤 걸린거 같다. 

어제 저녁부터 새벽 내내 하고, 오늘도 수업 시간 중에 틈틈이 계속하고 지금이 8시 좀 넘었는데 지금까지 했으니

원래는 글 적어가면서 전체 틀잡고, 에러 고쳐가려고했는데 수정해야될게 너무 많더라

책에서는 어떻게 회로들을 연결하면 CPU가 만들어지는지 친절하게 설명해줘서

CPU야 금방 만들겟꺼니 했는데

단순 연결을 떠나서 각 회로의 제어 비트를 어떻게 값을 넣일지 조정하는게 너무 어렵더라

A, D 레지스터의 로드 비트, 

좌 우측 먹스에 어쩔때 a를 넘길지 b를 시킬지

가장 힘들었던건

프로그램 카운터 점프 시점을 조절하는게 너무 힘들었다.

8가지의 점프 조건과 D 값이 일치하는 경우에만 load 자리에 1을 대입시켜 전달 받은 A 레지스터의 값을 저장시키도록

로직 구현하는데 CPU 구현하는 시간의 2/3정도 낭비했다.

이건 어떻게 배치해야할까 생각하면서 정리한 내용인데 중간에 instruction[15]와 and 게이트 여러개 있는건 명령어로부터 ALU 제어 비트를 뽑아내기 위한 로직이고, 아래에는 writeM, addressM, 목적지 고민하면서 끄적데던 흔적이다.

나는 처음에는 점프를 C 명령어 j 비트에 값이 존재한 경우에 무조건 PC의 load 비트에 1을 대입하여 점프하도록 시켰었는데, 그랬더니 jjj의 조건에 맞지 않는 연산 결과가 나와도 점프 해버리는 문제가 발생했었다.

 그 문제때문에 어떻게 하면 jjj 비트에 따라서 올바른 조건을 찾아 그 조건이 성립하는지에 따라 load 비트로 값을 전달하는 로직을 고민하면서 mux를 이용했다. jjj로 먹스의 셀렉트할 단자를 선택하고 각 입력에서는 jjj 비트별 연산 출력을 받도록 하는데, JEQ, JGT, JNE 등 각 연산을 해서 조건에 맞으면 1, 안되면 0을 출력하는걸 sel 비트로 선택해서 load로 전달하는게 되겠다.

CHIP CPU {

    IN  inM[16],         // M value input  (M = contents of RAM[A])
        instruction[16], // Instruction for execution
        reset;           // Signals whether to re-start the current
                         // program (reset==1) or continue executing
                         // the current program (reset==0).

    OUT outM[16],        // M value output
        writeM,          // Write to M? 
        addressM[15],    // Address in data memory (of M)
        pc[15];          // address of next instruction


    PARTS:

    //PC PARTS
    Or(a=instruction[0], b=instruction[1], out=jmp12or);
    Or(a=jmp12or, b=instruction[2], out=jmp123or);
    And(a=instruction[15], b=jmp123or, out=isJump);         //c instruction and jmp



    // jump condition implementation * comp = outMLoop
    Mux(a=true, b=false, sel=true, out=noJump);                 // jump con 1. 000 no jump
    Not(in=ng, out=isNotNegative);                              // jump con 2. 001 JGT comp > 0 jump   = not zero & not negative
    And(a=isNotNegative, b=isNotZero, out=isPositive); 
    Mux16(a=false, b=true, sel=isPositive, out=isJGT16);        // end JGT
    Mux16(a=false, b=true, sel=zr, out=isJEQ16);                // jump con 3. 010 JEQ
    Or16(a=isJGT16, b=isJEQ16, out=isJGE16);                    // jump con 4. 011 JGE, comp >= zero, jump
    Mux16(a=false, b=true, sel=ng, out=isJLT16);                // jump con 5. 100 JLT 
    Not(in=zr, out=isNotZero);                                  // jump con 6. 101 JNE, comp != zero, jump
    Mux16(a=false, b=true, sel=isNotZero, out=isJNE16);         // end JNE
    Or16(a=isJLT16, b=isJEQ16, out=isJLE16);                    // jump con 7. 110 JLE
    Mux16(a=false, b=true, sel=true, out=jump16);               // jump con 8. 111 JMP, always jump
    Mux8Way16(a=false, b=isJGT16, c=isJEQ16, d=isJGE16,
            e=isJLT16, f=isJNE16, g=isJLE16, h=jump16,
            sel[2]=instruction[2], sel[1]=instruction[1], 
            sel[0]=instruction[0], out[0..7]=isJump0to7, out[8..15]=isJump8to15);
    Or8Way(in=isJump0to7, out=jumpRes1);
    Or8Way(in=isJump8to15, out=jumpRes2);
    Or(a=jumpRes1, b=jumpRes2, out=isJumpCondition);
    And(a=isJump, b= isJumpCondition, out=isPCLoad);

    Not(in=reset, out=isNotReset);
    PC(in=aRegistorOut, load=isPCLoad, inc=isNotReset, reset=reset, out[0..14]=pc);

    //A registor PARRTS
    Not(in=instruction[15], out=opcodeOut);                 // A instruction == store to A registor
    And(a=instruction[15], b=instruction[5], out=loadA);    //if instruction is C and dest is a, store outM to A registor
    Or(a=opcodeOut, b=loadA, out=aRegistorLoad);
    //if opcode is 0 (== A instruction) -> opcodeOut = 1 -> load = 1
    ARegister(in=leftMuxOut, load=aRegistorLoad, out=aRegistorOut, out[0..14]=addressM);

    //D registor PARTS
    And(a=instruction[15], b=instruction[4], out=loadD); //if instruction is C and dest is d, store outM to A registor
    DRegister(in=outMLoop, load=loadD, out=dRegistorOut);


    //right Mux16
    And(a=instruction[15], b=instruction[12], out=mIsUsed);
    Mux16(a=aRegistorOut, b=inM, sel=mIsUsed, out=inputMA);

    //left Mux16
    And(a=instruction[5], b=instruction[15], out=isOutMLoop);
    Mux16(a=instruction, b=outMLoop, sel=isOutMLoop, out=leftMuxOut);

    //ALU parts
    And(a=instruction[15], b=instruction[11], out=zx);
    And(a=instruction[15], b=instruction[10], out=nx);
    And(a=instruction[15], b=instruction[9], out=zy);
    And(a=instruction[15], b=instruction[8], out=ny);
    And(a=instruction[15], b=instruction[7], out=f);
    And(a=instruction[15], b=instruction[6], out=no);
    ALU(x=dRegistorOut, y=inputMA, zx=zx, nx=nx, zy=zy, ny=ny, f=f, no=no, out=outMLoop, out=outM, zr=zr, ng=ng);

    //writeM
    And(a=instruction[15], b=instruction[3], out=writeM);
}

이 코드가 HDL을 이용해서 우리가 앞서 구현한 칩들을 잘 조합해서 만든 CPU이고,

테스트 코드도 잘 동작한다.

다른 사람이 만들어둔거 참고해서 할수도 있었는데

조금만 더하면 해결되겠지 싶어서 계속하던게 너무 오래걸렸다.

그래도 결국에는 난드 게이트로 CPU를 만들었다!

잠깐 되돌아볼까?

난드 게이트로 and, or, mux, demux 등을 만든 후 이걸 조합해서 alu를 만들었고

데이터 플립플롭을 앞의 조합논리회로랑 결합하여 레지스터, 메모리, 프로그램 카운터를 구현했다.

그리고 이것들을 오늘 다합쳐서 CPU를 완성한거고.

CPU는 다했으니 끝이면 좋겠지만 이번 장은 이게 끝이 아니지.

일단 이번 장은 여기서 한번 끊는다.