Cコンパイラ作りはじめました

こんにちは。自分のブログを書くのはものすごく久しぶりのid:rskyです。何年知的便秘だったんだって感じですね。

表題のとおりこれからCコンパイラを作っていこうかと思います。同僚のDQNEOさんが＜8cc.go＞というコンパイラを作られていて、それに触発されて「Rustでやってみよう」ということで、＜低レイヤを知りたい人のためのCコンパイラ作成入門＞をCでなくRustでやっていきます。 Rust自体も初めてなので、それも含めてどんなものになっていくのか、自分でも楽しみです。

なお、今後このシリーズでは＜低レイヤを知りたい人のためのCコンパイラ作成入門＞を二重鉤括弧つきの『入門』と表記します。

開発環境

自分の開発マシンはMacですが、macOSはターゲットとせずLinuxで動くものを作っていきます。『入門』にも

macOSはLinuxとアセンブリのソースレベルでかなり互換性がありますが、完全互換ではありません。この本の内容に従ってmacOS対応のCコンパイラを作成するのは不可能ではないものの、実際に試してみると、細かな点でいろいろな非互換性に悩まされることになるでしょう。Cコンパイラ作成のテクニックと、macOSとLinuxの差異を同時に学ぶというのは、あまりお勧めできることではありません。何かがうまく動かない場合、どちらの理解が間違っているのかよくわからなくなってしまうからです。したがって現時点では、本書ではmacOSは対象外とします。macOSではDockerなどを使ってLinux環境を用意するようにしてください。

とあるように、コンパイラ作成の本質に注力するためです。 予断ですがサブでWindowsも使っており、WSL2とWindows Terminalの出来如何ではいよいよメイン開発環境をWindowsにしてもいいかなと思っています。

コラム: macOSでの差異

Linuxとシンプルかつ最大の違いといえば、macOSでは公開シンボルにアンダースコアのprefixが必要なことでしょうか。main関数はアセンブリでは_mainという名前で宣言しないといけません。

また、これは教えていただいたことですが、レジスタにも違いがあるらしいです。このあたりの知識は今の自分に全く欠けていることもあり、素直にLinuxのみをターゲットにすることにしました。将来的にはクロスコンパイルにもチャレンジしてみたいですね。

Repository

既に作成済みの9cc.rustをcloneして作業します。

$ git clone [email protected]:rsky/9cc.rust.git
$ cd 9cc.rust

Dockerfile

Ubuntu 18.04 LTSベースのイメージを作ります。

FROM ubuntu:18.04

# Install build tools
RUN apt-get update && apt-get install -y gcc make git curl binutils libc6-dev

# Install Rust
RUN curl https://sh.rustup.rs -o rustup-init.sh && chmod +x rustup-init.sh && ./rustup-init.sh -y

WORKDIR /9cc.rust

COPY . /9cc.rust

Getting Started

このシリーズで作るコンパイラのバイナリ名は r9cc とします。それではさっそくプロジェクトを作成しましょう。今まさに読み始めたばかりの＜プログラミングRust＞に従ってパッケージを作成します。

$ cargo new --bin r9cc
     Created binary (application) `r9cc` project
$ tree r9cc
r9cc
├── Cargo.toml
└── src
    └── main.rs

1 directory, 2 files

しかし既に9cc.rustプロジェクト内で作業しているのでこれではちょっと都合が悪い、ということでリネームしました。

$ mv -v r9cc/* .
r9cc/Cargo.toml -> ./Cargo.toml
r9cc/src -> ./src
$ rmdir r9cc

Hello, Rust!

まずは引数も取らず、固定のアセンブリコードを吐くだけのプログラムを書いてみます。僕自身初のRustコードです。

src/main.rs

fn main() {
    println!(".intel_syntax noprefix");
    println!(".global main");
    println!("main:");
    println!("  mov rax, 1");
    println!("  ret");
}

これをビルドします。※ここから先はコンテナ上での作業ですが、そこら辺の説明はざっくり省いています。

$ cargo run
   Compiling r9cc v0.1.0 (/9cc.rust)
    Finished dev [unoptimized + debuginfo] target(s) in 5.60s
     Running `target/debug/r9cc`
.intel_syntax noprefix
.global main
main:
  mov rax, 1
  ret

target/debug/r9cc にバイナリが作られたようなので、これを実行、生成物をアセンブルして実行します。

$ ./target/debug/r9cc > tmp.s
$ cat tmp.s
.intel_syntax noprefix
.global main
main:
  mov rax, 1
  ret
$ gcc -o tmp tmp.s
$ ./tmp
$ echo $?
1

OKですね。引き続き引数として取った数値を返すようにします。

Take Arguments

コマンドライン引数の処理は＜プログラミングRust＞の第2章序盤に書かれており、そのまま使えました。

use std::io::Write;
use std::str::FromStr;

fn main() {
    let mut numbers = Vec::new();

    for arg in std::env::args().skip(1) {
        numbers.push(u8::from_str(&arg).expect("error parsing argument"))
    }

    if numbers.len() != 1 {
        writeln!(std::io::stderr(), "Invalid number of arguments.").unwrap();
        std::process::exit(1);
    }

    println!(".intel_syntax noprefix");
    println!(".global main");
    println!("main:");
    println!("  mov rax, {}", numbers[0]);
    println!("  ret");
}

ビルドして実行してみます。引数のパースエラーも処理できていてありがたいですね。

$ cargo run
   Compiling r9cc v0.1.0 (/9cc.rust)
    Finished dev [unoptimized + debuginfo] target(s) in 0.41s
     Running `target/debug/r9cc`
Invalid number of arguments.

$ ./target/debug/r9cc
Invalid number of arguments.

$ ./target/debug/r9cc 42
.intel_syntax noprefix
.global main
main:
  mov rax, 42
  ret

$ ./target/debug/r9cc 65535
thread 'main' panicked at 'error parsing argument: ParseIntError { kind: Overflow }', src/libcore/result.rs:997:5
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

$ ./target/debug/r9cc foo
thread 'main' panicked at 'error parsing argument: ParseIntError { kind: InvalidDigit }', src/libcore/result.rs:997:5
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

というわけで、引数を指定して出力したコードをアセンブル、実行します。

$ ./target/debug/r9cc 42 > tmp.s
$ cat tmp.s
.intel_syntax noprefix
.global main
main:
  mov rax, 42
  ret
$ gcc -o tmp tmp.s
$ ./tmp
$ echo $?
42

OKですね。これでようやく『入門』のステップ1の途中、「コンパイラ本体の作成」まで完了しました。 次回は「ユニットテストの作成」です。

ありのままに起こったことを話すぜ

regular

これは某定年まであと2年になったことだし、おっさんらしくスピリチュアルな文章のひとつでも書こうと思っていた矢先に起こった事件の顛末である。

èµ·

最近、自転車をサボっていたので軽く走りに行こう、と思ったのが発端であった。

目的地は彩湖。サイクリングコースがあり、以前から行ってみたかった所だ。自宅からもそんなに遠くないし、ほぼ道なりに北に進むだけという分かりやすさが良い。

というわけで出発。井荻トンネルは軽車両通行禁止—つまり自転車では通れないので降りて地下道を通らねばならないのが少々面倒なものの、サイクリングそのものは順調に進んだ。

承

実はここで小さなミスを犯している。車道をまっすぐ進んで笹目橋に向かうのが正解だったのだが、地図を確認するために停車した所からだと理研の前を通って外環道（の側道）から行くことになった。

外環道も地図の上では彩湖に直接行けるから良さそう、と思いきや側道のアップダウンが激しく、鈍った脚にはちょっとしんどかった。ちょっとだけ。しかし橋の上から見る彩湖がきれいだったのでよしとする。

荒川※写真は彩湖でなく隣の荒川

無事到着。母上様ほどではないが、やや方向音痴な僕が目的地にほぼ一発で行けたのは珍しい。出発したのが遅かったし、暗くならないようにと一周だけ回って帰路に就く。

転

エネルギー切れを感じたのと、TLに1000円マックを食べた人が多かったのを思い出し、マクドナルド笹目通り高松店に入る。そういえば現金あったかな、とオーダーする前に財布を確認したら204円しかなかったので回れ右。ふたたび愛車に跨り、南へ。

そして井荻まで戻ってきた。セブンイレブン井荻駅北口店でお金を下ろし、軽く調達。いざ帰ろう、と自転車のロックをはずそうとしたところ、、、

＿人人人人人人＿
＞　鍵がない　＜
￣ＹＹＹＹＹＹ￣

店内に戻り不審者のように床を見回しても、ない。

自転車の鍵だけでなく、自宅その他の鍵をまとめたキーホルダーがないのだ。

このような紳士淑女にしかわからないネタで強がってみるのが精いっぱいであった。

不幸中の幸いは鍵を落とした場所が限定されることである。井荻駅と練馬区高松6丁目交差点との間は2km強。もし仮にポケットから落ちたとしても、目を皿のようにして探せない距離ではない。ちなみに以前にあった不幸な出来事の反省から自転車に乗るときは鍵をポケットに入れないように気をつけており、その可能性は低い。

となれば駐輪場で落とした公算が大きい。ならばあとは歩くのみ。ロックがかかったままの自転車を有料駐輪場に預け、徒歩で引き返す。僕の足取りは力強かった。

実際は凹んでいたけどな！

結

件のマクドナルドに帰還。駐輪場には落ちてなかったので店員さんに尋ねてみる。どうやら届けられているようだが、念のため鍵の特徴を訊かれる。ホイホイ渡すわけでもなく、ちゃんと確認してくれるあたり、教育が行き届いていることが伺えて安心できた。

よし1000円マックでも食って帰るか・・・ない！ 取り扱ってない店舗だったでござる。

べつにむしゃくしゃしてないのに「ムシャクシャしたのでクォーターパウンダー ルビースパークをムシャムシャしている」と書きたかった僕の純情が討ち死に。

黙ってクォーターパウンダー BLTを食べる。味は悪くない、崩れやすさが残念。バーガー袋を用意しといてほしい。

その後は特に突発イベントもなく、無事に帰宅できましたとさ。めでたしめでたし。

今思えば、井荻が西武新宿線によって南北に分断されていたおかげで被害が最小限に抑えられたのではないか。あのセブンイレブンは帰還不能点、西武新宿線はまさにルビコン川であった。（言いたいだけその2）

駐輪場に落とした鍵を店に届けてくださった御仁にはこの場を借りて御礼申し上げる。

第4回 闇PHP勉強会レポート

regular php

ちょっと遅くなってしまいましたが、スライドを公開します。

スライドだけでなくて壁にマーカーで書いたり、ソースコードを参照しながら発表させてもらいました。

ミックスイン

今回の発表の目玉（？）でもあったミックスイン記法は既存のPHPコード/ユーザーが自然にステップアップできる記法にできたなと自負しているので、是非とも次の次のPHP、おそらくPHP 5.6に入れるべく提案する計画です。（自負とか言ってもScalaの真似ですが）

ミックスイン記法とは別に拡張モジュールとしてAOPサポートを入れようと目論んでおり、それがやりやすいようにAPIを整えるという本末転倒な事も企んでいたり。

Zend Engineのcompilerからexecutorあたりの読みづらさは特筆に値するものがあり、これを改造してちゃんと動くものにするのは多少の慣れが必要ですが、まだまだ改善の余地のある子なので良くしていく手助けができればと思います。

しかしながら、長いことZend Engine 2をウォッチしているとメジャーバージョンアップの度に良くなっている面と、継ぎ接ぎを重ねてつらくなっている面の両方を感じており、CRubyに対するmrubyのような実装が出てくると面白いな、と。

お前が作れと言われたら、できるかできないかわからないけど、やってみたいのでフルタイムでできるお金ください。（笑）

雑感

懇親会では普段PHP界隈で会わない方々とお話できたのも良かったです。PHPの勉強会と思ったら違う何かだったような気がしないでもないですが、楽しんでいただけたなら幸いです。

あと塙さんと「PHPのメジャーバージョンアップで動かなくなるプログラムは、大抵PHPでなくて書いたやつが悪い」という共通の見解が得られたのがちょっと嬉しかったです。「ランタイムでなくコンパイルタイムでもっと大胆にバイトコードを弄る」（超意訳）というアイデアも刺激になりました。

他の方々の発表

追記

このブログでは意図的に「です・ます調」を避けていたのに、うっかり使ってしまいました。以後気をつけます＞＜

ウノウの縁

regular

本文を書く前に言っておくッ！
おれは今やつのスタンドをほんのちょっぴりだが体験した
い…いや…体験したというよりはまったく理解を超えていたのだが……

あ…ありのまま　あのとき　起こった事を話すぜ！

『おれはウノウを受けていたと
思ったらいつのまにかジンガジャパンに勤めていた』

な…　何を言ってるのか　わからねーと思うが
おれも何をされたのかわからなかった…

頭がどうにかなりそうだった…

ベンチャーだとかスタートアップだとか
そんなチャチなもんじゃあ　断じてねえ

もっと恐ろしいものの片鱗を味わったぜ…

…さて、1ヶ月以上遅れてのウノウアドベントカレンダー記事です。（ごめんなさいごめんなさい）

僕がウノウに入ろうと思ったきっかけは、やはりウノウラボの存在が大きかった。

2000年代後半のPHP界ではあのブログを読んでなかったらモグリと断定できるぐらいあのブログはエッジが効いていた。

拙作のMeCabエクステンションが知られる事になったのもウノウラボで紹介されたのが大きかった。(もちろんDo You PHP はてなの存在も)

そんなこんなで三十路も近づき、いっぺん東京で働いてみっかー、と思ったとき、まず誘ってくれたのがウノウの人—自称非モテの@cocoitibanで、TKビルに行ったときの最初の面接官が@hiro_yだったのが物語の始まり。

ところで個人的にはここいちさんが妻帯者になっても非モテを名乗るのは奥さん(@no_ugat)に失礼だからやめたほうがいいんじゃないかな、とか思ったりする。のだけど、どうなんだろう? 正直そこらへんの機微はよくわからん。

閑話休題。

で、冒頭に書いたようにいつのまにかジンガジャパンに勤めることになり、そこでも以前からネットでは知っていた凄い人、知らなかったけど凄い人たちと仕事ができて面白かった。ジンガジャパンという会社は僕が入りたかったウノウとは明らかに別の会社だったけど、それはそれ。

そしてジンガジャパンに入社して約1年半、転機が訪れて転職。今の会社で一緒のチームにいるのが@hiro_yと@no_ugatで、縁とは不思議なものだなあ、と思っている。

ウノウに勤めることはなかったけど、僕の人生においてウノウという会社の影響は少なくない、というお話。

よみがえるQIQ

regular PHP

別エントリで実装等について書く前に、これまでの経緯のまとめ。

以前のエントリ で↓のように書いていたのだが、

Scalaライクなミックスイン はエイプリルフールネタです。申し訳ない。

本気で取り組みたいですが、なかなか難しいですね。

求む、フルタイムでやらせてくれるお大尽。

プログラミングをしない人にPHPを少しわかりやすくする関数 “not” #phpadvent2012 に触発されて

と言ってしまい、その流れでphp-srcをforkしてnot演算子を実装したり、until文/unless文を実装したりしているうちに気分がノってきて、Synfomy勉強会で@itemanと話したのが決め手で「もう一度トライしてみよう」と相成った。

そして、寝て起きてPHPのソースコードを見ていたら、なんか出来そうな気がしたので選挙に行ってから作業を始めると、割とあっさりできてしまって我ながらびっくり。難しいと思い込んで敬遠していたのはなんだったのか。

構想8ヶ月半というか、着想してから8ヶ月半といった方が正確かも。

こうしてできたScala風ミックスインと、以前からやっていたClang Blocks風無名関数にインライン呼出構文を加えたもの、全部入りのQIQブランチも作成。QIQはPHPのアルファベットを一つずつ進めたもので、PHPの次を意味する由緒正しい名前。（僕の中では）

ダウンロード

configure生成済のソースコード一式と、特定環境向けのバイナリを用意したので、気軽に試してみてほしい。

追記：20121220 にはミックスイン済クラスの再利用に関するバグがあったので修正版の 20121221 と差し換え

続：JPEGハフマン表の分割について

regular

前回の記事にはだいぶ誤認識があったようなので訂正。

確かに符号化が効きやすいようにブロックが並べ替えられてはいるようなのだけど、JPEGとしては特別なことをしていない、ただのプログレッシブJPEG (フレームヘッダ:SOF2) だった。

ベースラインJPEG (同SOF0) は常にSOSは一つで、ハフマン表を分けたりもできるのは拡張シーケンシャルJPEG (同SOF1) らしいについては使えるハフマン表の種類が増えるということまでしか調べられていない。

JPEGハフマン表の分割について

regular

JPEGに絡んでよやさんと話すことになった。発端はここらへん。

予習としてiPhone 5の“slide to unlock”アニメーションで使われている変態JPEGファイル (unlock_001.jpg) について調査したツイートを以下に貼り付ける。

ざっくり言うと先頭には輝度・色差の変化が少ないSOSセグメントが配置されており、後になるにつれてハフマン表を追加・更新しつつ変化の大きいSOSセグメントが配置されている。 画像を見れば大体そんな感じかなと察しはつくものの、実際に調べてみるとやっぱりこれを考えた人はかなりキているなと思わざるをを得ない。

ブロックの再配置が許される場合にしか使えない手法で、一般的な画像の高効率圧縮には不適だけど、技術的にはとても刺激になった。