Bootstrapping

Photo by Minh Tran on Unsplash

Bootstrapping

이 포스트는 2019년 4월 26일에 발행되었습니다.

수요일에 Programming Language 과목의 중간고사를 준비하면서 열심히 공부한 부트스트래핑이 시험에 나오지 않았기 때문에, 공부한 게 아까워 정리해서 올려봅니다.

T-Diagram

1.png

T-Diagram은 간단한 표기법입니다. Python으로 짜여진 Sort 프로그램, x86 위에서 돌아가는 Python 인터프리터, 그리고 x86 자체를 T-Diagram에서는 위와 같이 표기합니다.

2.png

인터프리터를 봤으니 컴파일러도 봐야겠죠? x86에서 C 코드를 x86 어셈블리로 바꿔주는 컴파일러는 위와 같이 표기합니다.

3.png

x86에서 C 코드를 arm 어셈블리로 바꿔주는 컴파일러 (크로스 컴파일) 는 위와 같이 표기합니다.

4.png

"C로 짜여진 Sort 프로그램을 x86-C Compiler written in x86를 이용해 x86 상에서 컴파일 하면 노란색 부분이 출력된다" 를 위와 같이 표기합니다.

Building compiler for new language

이제 x86-C Compiler written in x86가 이미 존재한다는 가정하에 x86-Rust Compiler written in x86을 만들어보는 3가지 방법을 알아봅시다.

1. 처음부터 끝까지 x86 assembly로 작성한다.

5.png

네, 저희가 원했던 바로 그 결과물이죠? x86-Rust Compiler written in x86. 처음부터 x86으로 짜버리는 방법도 있습니다. 물론 누구도 이런 방식을 택하진 않겠지만요.

2. Rust 코드를 x86 assembly로 바꾸는 C 프로그램을 짠다.

6.png

바꿔 말하면 "C로 Rust 컴파일러를 작성한다" 입니다. Rust -- C --> x86을 잘 작성한 뒤에, C -- x86 --> x86을 이용해서 위 그림의 노란색 부분을 얻는 발상입니다.

7.png

이제 우리는 Sort program written in Rust (input)을 빨간색 동그라미를 친 컴파일러를 사용해서 Sort program written in x86 (output)으로 변환할 수 있습니다. (= 컴파일할 수 있습니다.) 이 접근방식의 단점은 Rust 생태계를 키우려면 Rust와 C, 둘 다 숙련된 개발자만이 Rust 컴파일러를 발전시킬 수 있다는 겁니다. 그리고 각 언어의 자존심이기도 하죠, 니네(Rust)는 속도가 느리니까 C로 컴파일러 만든거 아니냐.

3. Bootstrapping (부트스트래핑) 한다.

마지막 방법은 부트스트래핑입니다. Rust 컴파일러를 최초로 만들 때, 처음에 한 번 다른 언어 컴파일러의 도움을 받는 방식입니다. 자세한 설명은 위키피디아를 참고하시고 이 포스트에서는 부트스트래핑의 T-diagram이 어떻게 전개되는지를 설명합니다.

  1. Rust-S라는 Rust의 subset language를 "잘" 정의합니다.

Rust의 기능 중 고수준 추상화 언어 명세를 제외한 기본적인 것들 중에 잘 골라서 Rust-S를 정의합니다. 물론 이 Rust-S는 튜링 완전해야합니다.

2.

8.png

1에서 열심히 정의한 Rust-S의 컴파일러를 C로 작성합니다.

3.

9.png

이제 우리의 핑크를 존재하던 C 컴파일러를 사용, 하늘이를 얻습니다.

4.

10.png

C로 짰던 Rust-S 컴파일러를 Rust-S로 포팅합니다. 연두를 얻습니다.

5.

11-1.png

열심히 작성한 연두를 하늘이를 사용해 노랑이로 컴파일합니다. 여기서 하늘이와 노랑이의 차이점은 source high-level programming language입니다.

6.

12.png

이제 저수준의 추상화만을 가진 Rust-S를 이용해서 전체 Rust 스펙을 구현합니다. 빨강이를 얻습니다.

7.

13.png

이제 5에서 얻은 노랑이를 사용해서 빨강이를 초록이로 컴파일합니다.

-- 부트스트래핑 설명 Q.E.D. --

처음에 설명했던 "처음에 한 번 다른 언어 컴파일러의 도움을 받는" 부분이 Step 2, 3 입니다. 그 이후에는 Rust-S만을 이용해서 우리가 얻고자 했던 초록이를 얻었습니다. 언어의 추상화 수준이 너무 높거나, 언어 스펙이 너무 방대한 경우 Rust-S1, Rust-S2와 같이 subset level을 나누는 방법도 가능합니다.