프로그래밍 언어에 대한 내 생각을 바꾼 글들

• 프로그래밍 언어와 컴파일러에 대한 시각을 근본적으로 바꿔준 다양한 글, 논문, 동영상을 소개함
• 실용적인 GC 구현, 옵티마이저 설계, 레지스터 할당, 정규표현식 엔진 등에 대한 이해를 크게 넓혀준 자료들
• Z3와 추상 도메인, SSA 형식, E-Graphs 등 실무 알고리듬과 구조가 실제 코드 예시와 함께 쉽게 설명됨
• 각 자료는 복잡한 개념을 간결하면서도 확장 가능하고 이해하기 쉽게 풀어줌

프로그래밍 언어와 컴파일러에 관한 인식의 전환을 가져온 글들 소개

• 가끔씩 프로그래밍 언어와 컴파일러 관련 주제에 대해 내 생각을 완전히 바꿔주는 논문, 블로그 포스트, 영상 등을 발견함
• 몇몇 글의 경우 읽기 전에는 어떻게 생각했는지조차 기억이 안 날 만큼 강렬한 영향력을 받음.
• 아래는 그런 자료들에 대한 소개임 (순서 무관)

GC, 옵티마이저, 추상 도메인, 레지스터 할당 관련

• Andy Wingo의 a simple semi-space collector는 Cheney/복사/컴팩팅 가비지 컬렉터 개념을 이론에서 실제로 적용하는 과정을 잘 보여줌
  • 본문의 GC 핵심 구현은 매우 간결하며, 확장 가능하고 한나절이면 이해할 수 있음
• CF Bolz-Tereick의 Implementing a Toy Optimizer 글은 옵티마이저에서 명령어 rewrite 방식에 대한 인식 전환을 이끔
  • 단순한 찾기-치환 대신 forwarding pointer 사용을 강조하며, union-find 개념을 소개함
  • 전체 toy optimizer 시리즈는 각 글마다 새롭고 흥미로운 내용을 담고 있음
• A Knownbits Abstract Domain for the Toy Optimizer, Correctly 글은 새로운 추상 도메인과 Z3 활용법을 동시에 소개함
  • Z3가 여러 수치 연산 증명에 이용되는 방식뿐 아니라, Python 코드 검증 엔진으로 활용되는 예시를 보여줌
  • Z3가 반례를 못찾으면 코드의 정당성 보장이라는 아이디어를 소개함
• Chris Fallin의 Cranelift, Part 3: Correctness in Register Allocation에서는 입력마다 올바른 레지스터 할당을 직접 증명하는 방식을 설명함
  • 프로덕션 환경에서는 옳은 할당이나 의미있는 크래시 중 하나를 얻게 됨
  • 퍼징 기법으로 상태 공간을 탐색하고 버그를 탐지하는 접근을 도입함

파싱, 인터프리터, JIT, 추상구조 관련

• Russ Cox의 Regular Expression Matching: the Virtual Machine Approach는 정규표현식 엔진 구현을 약 50줄의 읽기 쉬운 코드로 제시함
  • 이 과정에서 코루틴, 파이버, 스케줄러 등의 원리도 알기 쉽게 설명함
• Andrej Karpathy의 micrograd는 외부 라이브러리 없이 뉴럴 네트워크를 동작시키는 초소형 구현 예시로, 머신러닝의 기본 구조와 원리 습득에 도움이 됨
• Fil Pizlo의 How I implement SSA form은 union-find 구조를 개선하는 새로운 방법을 소개함
  • SSA 변환에서 추가 포인터를 객체 내부 Identity tag로 관리하는 방식임
  • 이외에 Phi/Upsilon form, TBAA 스타일 heap 효과 등 더 생각할 거리를 제공함
• Fil Pizlo의 Speculation in JavaScriptCore는 JavaScriptCore의 다양한 옵티마이저 구현 방식을 상세히 다룸
  • 글을 다시 읽을 때마다 새로운 인사이트를 얻게 됨

컴파일러 설계, 파서, IR 구조, E-Graphs

• Chandler Carruth의 Modernizing Compiler Design for Carbon Toolchain 발표(29분 즈음)에서는 압도적으로 빠른 컴파일 타임 목표 수립과 전체 구조 설계 과정을 설명함
  • 40분 즈음부터 각 계층별로 구조를 풀어서 설명함
• Allison Kaptur의 A Python Interpreter Written in Python은 CPython 내부 바이트코드 인터프리터 작동 원리를 쉽게 이해하게 해줌
• Eli Bendersky의 Parsing expressions by precedence climbing는 전통적인 재귀하강 파서보다 이해가 쉽고 개발 부담이 작은 Precedence Climbing 파싱법을 소개함
• Takashi Kokubun의 Ruby JIT Challenge는 코드 생성과 새로운 레지스터 할당 방법(stack folding at compile-time)을 보여줌
• Abdulaziz Ghuloum의 [An Incremental Approach to Compiler Construction (PDF)(https://bernsteinbear.com/assets/img/11-ghuloum.pdf)은 기존 다단계 컴파일러 설계를 한 번에 이해할 수 있는 단일 패스 구현 방식을 설명함
  • 각 기능을 엔드 투 엔드로 차근차근 추가하는 방식을 취함
• Fernando Borretti의 Lessons from Writing a Compiler는 컴파일러 구현 전략을 명확하게 언어화해서 설명함
• egg: Fast and extensible equality saturation 논문은 옵티마이저 및 패스 순서에 대한 인식을 근본적으로 변화시킴
  • 표현식의 모든 가능한 버전을 압축된 하이퍼그래프로 만들어 두고 최적의 버전을 선택하는 사고법을 제시함
• Chris Fallin의 Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations는 실제 상용 컴파일러에서도 e-graphs가 효과적으로 작동함을 입증함
• Phil Zucker의 Acyclic Egraphs and Smart Constructors는 무환형 e-graph 구조와 스마트 생성자 활용을 탐구함
  • 초기에는 이해가 어려웠지만 시간이 지나면서 점차 이해가 깊어지는 글임

AST 저장, 대규모 병렬 동적 해석 등 기타

• Bob Nystrom의 이 Reddit comment와 Adrian Sampson의 Flattening ASTs는
  • AST를 거의 바이트코드처럼 컴팩트하게 저장하는 방법과,
  • IR 노드를 이런 식으로 저장하면 대규모 병렬 락프리 해석도 가능하다는 큰 논의를 이끌어냄
  • Cliff Click의 버퍼 할당 속도 관련 언급도 이러한 사고에 영향을 주었음