Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
コンパイラ作りの魅力を語る / Making compilers is fun
Search
DQNEO
March 30, 2019
Programming
10
8.3k
コンパイラ作りの魅力を語る / Making compilers is fun
PHPerKaigi 2019で、C/Goコンパイラを作る過程で学んだことについて話しました。
DQNEO
March 30, 2019
Tweet
Share
More Decks by DQNEO
See All by DQNEO
英和辞書付きGo言語仕様書 / Word Wise Go Spec
dqneo
1
440
Go言語低レイヤー入門 Hello world が 画面に表示されるまで / Introduction to low level programming in Go
dqneo
3
1.4k
入門Go言語仕様 / Go Specification Untyped Constants
dqneo
1
1.2k
入門Go言語仕様 Underlying Type / Go Language Underlying Type
dqneo
9
4.6k
How to write a self hosted Go compiler from scratch (Gophercon 2020)
dqneo
3
1.5k
もっと気軽にOSSに Pull Requestを出そう!/ Let's make a PR to OSS more easily
dqneo
6
8k
Goコンパイラをゼロから作ってセルフホスト達成するまで / How I wrote a self hosted Go compiler from scratch
dqneo
15
14k
コンパイラをつくってみよう / How to make a compiler
dqneo
9
11k
Goのmapとheapを自作してみた / How to create your own map and heap in Go
dqneo
0
3k
Other Decks in Programming
See All in Programming
Server Driven Compose With Firebase
skydoves
0
400
Snowflake x dbtで作るセキュアでアジャイルなデータ基盤
tsoshiro
2
430
飲食業界向けマルチプロダクトを実現させる開発体制とリアルな現状
hiroya0601
1
400
Sidekiqで実現する 長時間非同期処理の中断と再開 / Pausing and Resuming Long-Running Asynchronous Jobs with Sidekiq
hypermkt
6
2.7k
カラム追加で増えるActiveRecordのメモリサイズ イメージできますか?
asayamakk
4
1.6k
C#/.NETのこれまでのふりかえり
tomokusaba
1
160
Vue.js学習の振り返り
hiro_xre
2
130
NSOutlineView何もわからん:( 前編 / I Don't Understand About NSOutlineView :( Pt. 1
usagimaru
0
150
僕がつくった48個のWebサービス達
yusukebe
18
17k
のびしろを広げる巻き込まれ力:偶然を活かすキャリアの作り方/oso2024
takahashiikki
1
410
Content Security Policy入門 セキュリティ設定と 違反レポートのはじめ方 / Introduction to Content Security Policy Getting Started with Security Configuration and Violation Reporting
uskey512
1
430
WEBエンジニア向けAI活用入門
sutetotanuki
0
300
Featured
See All Featured
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
231
17k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
46
2.1k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
47
5k
Why Our Code Smells
bkeepers
PRO
334
57k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
42
9.2k
5 minutes of I Can Smell Your CMS
philhawksworth
202
19k
RailsConf 2023
tenderlove
29
880
The Illustrated Children's Guide to Kubernetes
chrisshort
48
48k
BBQ
matthewcrist
85
9.3k
Code Review Best Practice
trishagee
64
17k
Designing the Hi-DPI Web
ddemaree
280
34k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
355
29k
Transcript
コンパイラ作りの 魅力を語る @DQNEO phperkaigi 2019.3.30
自己紹介 @DQNEO どきゅねお アメリカ版メルカリを開発しています • PHPer • C初心者 • Go中級者
目次 • デモ • コンパイラとは何か?何をしているのか? • なんで作ろうと思ったのか? • どうやって作ったのか?
趣味: コンパイラ作り Cコンパイラ https://github.com/DQNEO/8cc.go 8ccをGoに移植したもの Goコンパイラ https://github.com/DQNEO/minigo Goで書いたGoコンパイラ
デモ: Cコンパイラ Fizz Buzz
デモ: Goコンパイラ Fizz Buzz
PHPerとCコンパイラ <?php php-src (C) C compiler Assembly Binary /usr/bin/php スクリプト
処理系
コンパイラとは何か
コンパイラとは何か 広義: 言語Xのコードを言語Yに変換するソフトウェア 狭義: 言語Xのコードを低レベル言語(アセンブリ/機械語 /etc)に変換するプログラム
コンパイラは 何をしているのか
Cコンパイラ (8cc) int sum(int a, int b) { return a
+ b; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret C言語 GNU assembler
コンパイラを作ってわかったこと アセンブリの知識が必要
コンパイラを作ってわかったこと • (多くの)コンパイラはアセンブリを吐く • アセンブリを理解し読み書きするスキル必要 = CPUのはたらきを理解すること
sum: push %rbp mov %rsp, %rbp push %rdi push %rsi
mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret アセンブリ言語 ≒ マシン語 • 各行がCPUへの「命令」 • どの行も、ハードウェア に対して副作用を生じる (レジスタ(後述)またはメ モリ上のデータを変更す る)
sum: push %rbp mov %rsp, %rbp push %rdi push %rsi
mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret GNU Assembler CPUへの命令
sum: push %rbp mov %rsp, %rbp push %rdi push %rsi
mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret GNU assembler メモリ 読み書き
sum: push %rbp mov %rsp, %rbp push %rdi push %rsi
mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret GNU assembler レジスタ 読み書き
コンパイラを作ってわかったこと “レジスタ”が主役 ※私の主観です
CPU内にある超高速な一時記憶装置 CPU ← レジスタ “レジスタ”が主役 出典: http://ftp.procmail.org/~sskulrat/Courses/2006F-170/lectures/chap14/part1.html
Cコンパイラ (8cc) int sum(int a, int b) { return a
+ b; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret C GNU Assembler 関数 → 関数 変数 → メモリ何番目
コンパイラを作ってわかったこと • C言語上の関数はアセンブリ上でも関数 • アセンブリには変数がない。 ◦ ハードウェア(メモリ/レジスタ)に「書く、読む」 • 「書き込む」「読み取る」という動作が基本
値とは何か
高級言語視点 値: 式を評価すると得られる もの 1;
mov $1, %rax 低級言語視点
値とは何か 1; mov $1, %rax C GNU assembler
値とは何か 式を評価して値を得る ↓ ある手続きを実行した際に、ハード ウェアのある場所に値を書き込む
値とは副作用である ※私個人の考えです
値とは何か 8ccの場合、一連の処理の最後に必 ずraxに値を書き込む約束になってい る。 raxが保持しているデータ、 これが「値」の実体
式を評価して値を得る x + y; mov -8(%rbp), %rax mov -16(%rbp), %rcx
add %rcx, %rax 演算の結果をraxに書き込む
隠れた副作用 実はrcxに副作用が残ったまま。 コンパイラ側で、このrcx値は再利用しないよう に気をつける。 これにより、副作用が1個(式の結果が1値)のよ うに見せかけている。 x + y; mov
-8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax
関数の戻り値 int sum(int x, int y) { return x +
y; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret raxに値を書き込ん で関数を抜ける。 これが戻り値。 受け取る側は、rax から値を読み出す。 int sum(int x, int y) { return x + y; }
関数の戻り値 int sum(int x, int y) { return x +
y; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret int sum(int x, int y) { return x + y; } 「純粋な関数」 も、ハードウェア レベルでは副作 用がある
コンパイラを作ってわかったこと • if文とfor文は仕組みがほぼ同じ ◦ 条件判定とジャンプ • ローカル変数とグローバル変数は扱いが全然 違う • 「スタック」とローカル変数の関係
コンパイラ作りで得たもの1 • アセンブラの読み書き能力 • 字句解析・構文解析の知識 • 対象言語(C,Go)の仕様に詳しくなった
コンパイラ作りで得たもの2 • 原典にあたる習慣 ◦ 言語仕様書 ◦ Intel CPUマニュアル ◦ gdb,
gasマニュアル
Intel® 64 and IA-32 Architectures Software Developer’s Manual
コンパイラ作りで得たもの3 • Segmentation Fault に負けない心 ◦ gdb/gccなどのコンパイラツール系スキル
None
簡単なC/Goのコードな ら 脳内コンパイルできる
何でコンパイラを作ろうと思っ たのか?
もともとは普通の PHPアプリケーション 開発者だった
コンパイラ知識ゼロからのスタート • 字句解析・構文解析の解説を読んでも理解不能 • C,Goもそんなに詳しくない 「プログラムが動く原理を知りたい」
Rebuild.fm153回 https://rebuild.fm/153/ Rui Ueyama さんが Cコンパイラ(8cc)を作った話 きっかけ めちゃくちゃ面白い!!
• C言語製Cコンパイラ • スクラッチから開発 • インクリメンタル開発 8cc https://github.com/rui314/8cc
さっそく git clone
8cc 1コミット目 #include <stdio.h> #include <stdlib.h> int main(int argc, char
**argv) { int val; if (scanf("%d", &val) == EOF) { perror("scanf"); exit(1); } printf("\t.text\n\t" ".global mymain\n" "mymain:\n\t" "mov $%d, %%eax\n\t" "ret\n", val); return 0; } #include <stdio.h> extern int mymain(void); int main(int argc, char **argv) { int val = mymain(); printf("%d\n", val); return 0; } https://github.com/rui314/8cc/commit/3764b2071b9601067b81976d80175a0851d0f209
なんとなくわかる! しかし、ただ読んでるだけでは身につ かなそう Goに移植してみよう!
1コミット移植してみた https://github.com/DQNEO/8cc.go/commit/b711967431 07e50e0ac945383abc5b2c3bf2e302 動いた! 8cc.go (Goへの移植)
8ccのコミット履歴を1個ずつ • テストの追加分を見る • そのテストをパスするC実装を自力でやってみる • 無理なら正解をチラ見する • 自力でCで再現する •
無理なら写経 • Goに移植する 延々と繰り返す 8cc.go (Goへの移植)
• 5ヶ月半毎日継続 • 95コミット移植完了 • 基本的な文法はだいたい動く 8cc.go (Goへの移植)
移植で見えてきた問題点 • 8ccの字句読み取りの設計が複雑 • 9ccはきれいに設計できてる • 自分でもゼロから設計してみたい!
Goコンパイラ開発 • 試しにGoでGoのtokenizerを書いてみた • あっさり動いた!感動! → その勢いでGoコンパイラ開発に突入
minigo (Goコンパイラ) • 1日目:足し算が動いた! • 2日目:引き算・掛け算・関数呼び出しが動いた! • 5日目: helloworld.go が動いた!
minigo (Goコンパイラ) • 1ヶ月後:FizzBuzzが動いた!
• 5ヶ月後:自分自身のコンパイルに成功! (時間があればデモ) minigo (Goコンパイラ)
野望 • 夏〜秋ごろにセルフホスト達成予定 • 来年のアメリカのGopherConに応募するぞ
コンパイラはいいぞ
ご清聴 ありがとうございました