부트스트랩 (컴파일러)

3. 장점

컴파일러를 부트스트래핑하는 것은 다음과 같은 장점들을 가진다:^[16][17][6]

• 컴파일되는 언어에 대한 중요한 테스트이며, 이로 인해 도그푸딩의 한 형태가 된다.
• 컴파일러 개발자와 버그 보고자는 컴파일되는 언어만 알면 된다.
• 컴파일러 개발은 컴파일되는 해당 고급 언어로 이루어질 수 있다.
• 해당 컴파일러의 백엔드 개선은 범용 목적 프로그램뿐만 아니라 해당 컴파일러 자신 또한 개선한다.
• 컴파일러가 언어 자신의 목적 코드를 재생산해 내어야 하므로 포괄적인 일관성 검사가 된다.

4. 닭이 먼저냐, 달걀이 먼저냐 문제

X 언어로 작성될 컴파일러를 만들어야 할 때, 특히 그 컴파일러 자체가 X 언어로 작성된다면 '첫 번째 컴파일러를 어떻게 컴파일할 것인가?'라는 문제가 발생한다. 이는 마치 닭이 먼저냐, 달걀이 먼저냐 문제와 같다. 이 문제를 해결하기 위한 다양한 방법들이 존재한다.

4. 1. 해결 방법

• 다른 언어(Y)를 사용하여 X 언어용 인터프리터나 컴파일러를 작성한다. 예를 들어, 니클라우스 비르트는 최초의 파스칼 컴파일러를 포트란으로 작성했다고 밝혔다.^[7]
• X 언어를 위한 인터프리터나 컴파일러가 이미 다른 언어(Y)로 작성되어 있는 경우 이를 활용한다. 스킴이 종종 이런 방식으로 부트스트랩된다.
• 컴파일하려는 언어(X)의 일부 기능만을 사용하여 컴파일러의 초기 버전을 작성한다. 이 방식은 해당 언어의 하위 집합(subset)을 컴파일할 수 있는 다른 컴파일러가 이미 존재할 때 가능하다. 자바, 하스켈, 초기 프리 파스칼 컴파일러 등이 이 방법을 사용했다.
• 컴파일러를 구현할 때 특정 컴파일러에 의존적인 비표준 확장 기능이나 선택적 기능을 사용하지 않고 작성한다. 이렇게 하면 동일한 기본 언어를 지원하는 다른 컴파일러(예: 다른 확장 기능 집합을 지원하는 컴파일러)를 사용하여 컴파일할 수 있다. 예를 들어, C++ 컴파일러인 clang의 주요 부분은 g++와 Microsoft Visual C++ 모두에서 컴파일 가능한 C++의 하위 집합으로 작성되었다.
• X 언어 컴파일러가 이미 존재하는 다른 아키텍처에서 크로스 컴파일한다. C 언어 컴파일러를 다른 플랫폼으로 이식할 때 흔히 사용되며, 초기 부트스트랩 이후의 프리 파스칼에서도 사용되는 방식이다.
• X 언어로 컴파일러를 작성한 뒤, 소스 코드를 직접 손으로 컴파일한다(이 경우 보통 최적화 수준은 낮다). 이렇게 얻은 초기 컴파일러를 사용하여 다시 컴파일러 자신의 소스 코드를 컴파일함으로써 최적화된 컴파일러를 얻는다. 도널드 커누스는 그의 WEB 리터럴 프로그래밍 시스템에 이 방법을 사용했다.

• OCaml: OCaml로 작성된 네이티브 코드 컴파일러는 소스 코드와 함께 바이트코드 형태의 컴파일러도 배포한다.
• 글래스고 하스켈 컴파일러(GHC): 하스켈로 작성되었으며, 중간 언어로 C를 사용하는 옵션을 활용한다. 부트스트래핑을 위해 C 컴파일러로 컴파일할 수 있는 C 소스 코드를 배포한다.

5. 역사

어셈블러는 스스로를 부트스트랩(bootstrap)하기 위한 첫 번째 언어 도구였다.

최초로 부트스트랩을 구현한 고급 언어는 1958년의 NELIAC이었다. NELIAC은 ALGOL의 한 종류이다. 널리 사용된 초기 사례로는 1961년 Burroughs B5000의 Algol 컴파일러와 1962년 LISP가 있다. 상용 구현 중에서는 PL/I의 구현이 최초였다.

LISP의 경우, 1962년 MIT의 하트(Hart)와 레빈(Levin)이 LISP를 사용하여 LISP 컴파일러를 작성했다. 이들은 기존에 존재하던 LISP 인터프리터 내에서 컴파일러를 테스트했다. 컴파일러가 개선되어 자신의 소스 코드를 컴파일할 수 있는 수준에 이르자, 컴파일러는 자체 호스팅(self-hosting)이 가능해졌다.^[9]

이러한 부트스트랩 방식은 컴파일하려는 언어와 동일한 언어로 작성된 인터프리터가 이미 존재할 때 가능하다. 이는 프로그램이 자기 자신을 입력으로 받아 실행하는 개념을 활용한 것으로, 이론 전산학에서 정지 문제가 해결 불가능함을 증명하는 과정(예: 라이스의 정리 활용)에서도 유사한 아이디어가 사용된다.

6. 종류

언어 X로 작성된 컴파일러를 처음 컴파일해야 할 때, 마치 닭이 먼저냐, 달걀이 먼저냐와 같은 문제가 발생한다. 즉, 컴파일러를 컴파일하기 위한 컴파일러가 필요한 상황이다. 이 문제를 해결하기 위해 여러 가지 방법이 사용된다.

6. 1. 해결 방법

• 언어 X의 인터프리터나 컴파일러를 다른 언어 Y로 구현한다. 예를 들어, 니클라우스 비르트는 최초의 파스칼 컴파일러를 포트란으로 작성했다고 알려져 있다.^[7]
• 언어 X를 위한 다른 인터프리터나 컴파일러가 이미 언어 Y로 작성되어 있는 경우 이를 활용한다. 이는 스킴에서 자주 사용되는 방식이다.
• 언어 X의 일부 기능만을 사용하는 서브셋 컴파일러를 먼저 만들고, 이 서브셋 컴파일러를 이용해 완전한 X 언어 컴파일러를 작성한다. 자바, 하스켈, 초기 프리 파스칼 컴파일러 등이 이 방식으로 부트스트랩되었다.
• 언어 X 컴파일러가 이미 존재하는 다른 플랫폼에서 크로스 컴파일을 통해 새로운 플랫폼용 컴파일러를 생성한다. C 언어 컴파일러를 다른 플랫폼으로 이식할 때 일반적으로 사용되며, 프리 파스칼도 초기 부트스트랩 이후 이 방법을 사용한다.
• 언어 X로 작성된 컴파일러 소스 코드를 사람이 직접 기계어나 어셈블리어로 번역("핸드 컴파일")하여 최초의 컴파일러를 만든다. 도널드 커누스는 그의 문학적 프로그래밍 시스템 WEB에서 이 방식을 사용했다.
• 언어 X의 인터프리터가 이미 구현되어 있다면, 그 인터프리터 상에서 X 언어로 작성된 컴파일러 소스 코드를 실행하여 컴파일러 자체를 컴파일한다. UCSD 파스칼의 P-Code 방식이 이에 해당한다.

7. 셀프 호스팅 컴파일러를 가지고 있는 언어 목록

아래 프로그래밍 언어들은 셀프 호스팅 컴파일러를 가지고 있다:

• Ada
• BASIC
• Burroughs ALGOL
• C
• C++ (컴파일러 : Visual C ++, clang 등)
• C# 및 Visual Basic .NET( Microsoft Roslyn을 통해)
• CoffeeScript
• Common Lisp
• Crystal
• Delphi
• Eiffel
• F#
• FASM
• 팩터
• 팬시
• 프리 파스칼
• 고
• 하스켈
• 자바
• 머큐리
• Modula-2
• 님로드
• 오베론
• OCaml
• 파스칼
• 펄 6 (컴파일러: Rakudo Perl과 Niecza Perl 6 모두 자기 호스팅)
• PL/I
• 파이썬
• 러스트
• 스킴
• 스칼라
• 스몰토크
• SML
• TypeScript
• 발라
• XPL

• OCaml: OCaml로 작성된 네이티브 코드 컴파일러는 소스 코드뿐만 아니라 바이트 코드도 배포한다.
• 글래스고 하스켈 컴파일러: Haskell로 작성되었으며, 부트스트래핑을 위해 중간 언어로 C 언어 코드를 생성하는 옵션을 제공한다. 이 C 코드는 일반적인 C 컴파일러로 컴파일할 수 있다.

8. 현재의 노력

신뢰할 수 없는 신뢰 공격(컴파일러가 컴파일하는 프로그램에 은밀한 백도어를 삽입하거나, 심지어 컴파일러 자체의 미래 버전에서 악의적인 수정을 복제하여 영구적인 불신의 순환을 만드는 것을 포함하는 공격)과 같은 보안 문제 및 바이너리 신뢰성에 대한 다양한 공격 때문에, 여러 프로젝트에서는 소스 코드로부터 직접 부트스트랩하는 과정을 단순화하고, 누구나 소스 코드와 최종 실행 파일이 일치하는지 검증할 수 있도록 노력하고 있다. 이러한 노력의 일환으로 부트스트랩 가능한 빌드(Bootstrappable Builds) 프로젝트^[10]와 재현 가능한 빌드(Reproducible Builds) 프로젝트^[11] 등이 진행 중이다.

참조

_[1] 학술지 Bootstrapping a self-compiling compiler from machine X to machine Y https://dl.acm.org/d[...] 2003-12
_[2] 학술회의 Perspectives of Systems Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27 – July 1, 2011, Revised Selected Papers Springer
_[3] 웹사이트 Installing GCC: Building https://gcc.gnu.org/[...]
_[4] 웹사이트 rust-lang/rust: bootstrap https://github.com/r[...]
_[5] 웹사이트 Advanced Build Configurations — LLVM 10 documentation https://llvm.org/doc[...]
_[6] 서적 Compilers and Compiler Generators: An Introduction With C++ International Thomson Computer Press
_[7] 학술지 50 years of Pascal Association for Computing Machinery (ACM) 2021-02-22
_[8] 웹사이트 Bootstrapping a simple compiler from nothing http://homepage.ntlw[...] 2003-04-23
_[9] 웹사이트 AI Memo 39-The new compiler ftp://publications.a[...] 2008-05-23
_[10] 웹사이트 Bootstrappable builds https://bootstrappab[...]
_[11] 웹사이트 Reproducible Builds — a set of software development practices that create an independently-verifiable path from source to binary code https://reproducible[...]
_[12] 학술지 Compiler bootstrapping and cross-compilation http://www.currentsc[...]
_[13] 웹인용 Installing GCC: Building - GNU Project https://gcc.gnu.org/[...] 2022-06-03
_[14] 웹인용 rust/src/bootstrap at master · rust-lang/rust https://github.com/r[...] 2022-06-03
_[15] 웹인용 Advanced Build Configurations — LLVM 15.0.0git documentation https://llvm.org/doc[...] 2022-06-03
_[16] 서적 Compilers and Compiler Generators: An Introduction With C++ International Thomson Computer Press
_[17] 문서 Compiler Construction and Bootstrapping
_[18] 웹인용 Bootstrapping a simple compiler from nothing http://homepage.ntlw[...] 2022-06-03