⛰️

Rust + LLVMで自作言語をセルフホスティングした話

8 min read

https://github.com/yubrot/llrl

RustとLLVMを用いて自作言語のコンパイラを実装し、自作言語上にコンパイラ実装を移植して、セルフホスティングを試みました。生成された実行バイナリが完全に一致するところまでこぎつけたので、取り組んだことを順に振り返りたいと思います。

本記事では、極力RustとLLVMを用いての自作言語のセルフホスティングについての話にフォーカスしたいと思います。筆者の動機や、筆者の言語デザイン上の選択、言語の特徴、言語固有の話などは個人ブログの方に書いたので、こちらも併せてご参照ください。

https://yubrot.github.io/2021/07/llrl/

LLVMと自作言語のセルフホスティング

LLVMについては、フロントエンド側・バックエンド側ともに既にいくらかの解説記事が見られるため、概要は省略します。今回は新たなプログラミング言語の実装が目的なので、LLVMのフロントエンド側の実装がメインとなります。セルフホスティングを目的とした取り組みにおいては、LLVMの以下の点が重要となります。

  1. 簡単なフロントエンドを実装するKaleidoscope言語のチュートリアルがある
    • LLVMを使って新たなプログラミング言語を実装するとっかかりになる
  2. LLVMはC APIを提供している
    • (C APIは多くのプログラミング言語でFFIによって呼び出せるため) 多くの言語が最初のコンパイラ実装言語として選択できる
    • 自作言語がCの呼び出し規約をサポートすれば、C APIを通して最初のコンパイラ実装と同じようにLLVMを利用できる
  3. LLVMの関数はCの呼び出し規約に対応している
    • 自作言語が関数呼び出しと呼び出すAPIに必要な型をサポートすれば、そのままLLVM C APIの呼び出しもおおよそサポートしたことになる
    • Kaleidoscopeからどのような機能を自作言語に加えればセルフホスティングが可能になるか見通しが立てやすい

(1)は本質的ではなく、(2,3)が重要な点となりますが、(1)に取り組むことで自然と(2,3)が見えてきます。順に見ていきましょう。

Kaleidoscope チュートリアル

https://llvm.org/docs/tutorial/

Kaleidoscopeは、LLVMのチュートリアルにおいて実装する非常に簡単なプログラミング言語です。短いチュートリアルですが、以下のようなプログラムを解釈、実行できるようになります。

def printdensity(d)
  if d > 8 then putchard(32)
  else if d > 4 then putchard(46)
  else if d > 2 then putchard(43)
  else putchard(42);

def mandelconverger(real imag iters creal cimag)
  if iters > 255 | (real*real + imag*imag > 4) then
    iters
  else
    mandelconverger(real*real - imag*imag + creal, 2*real*imag + cimag, iters+1, creal, cimag);

def mandelconverge(real imag)
  mandelconverger(real, imag, 0, real, imag);

def mandelhelp(xmin xmax xstep ymin ymax ystep)
  for y = ymin, y < ymax, ystep in (
    (for x = xmin, x < xmax, xstep in
       printdensity(mandelconverge(x,y)))
    : putchard(10))

言語機能を列挙すると、

  • 関数定義ができる
  • 関数を呼び出せる、引数を渡せる
  • 変数の型は常に double
  • 比較や四則演算ができる
  • 条件分岐ができる
  • forループができる
  • ...

...と、機能は限定的ながらも「プログラミングができる」言語になっています。チュートリアルはインクリメンタルに言語機能を加えていくように解説されており、前提知識無しに取り組みやすく構成されています。筆者もこれに取り組むことでLLVMのフロントエンド実装のとっかかりを掴みました。

チュートリアルはC++およびLLVMのC++ APIを用いて書かれていますが、LLVMはC APIを提供しているので他の言語でもおおよそ問題ありません[1]。セルフホスティング実装においては、 Kaleidoscopeチュートリアルの過程で実装するものはいずれ自作言語上でも実装することになる ため、むしろC APIを利用した実装のほうが将来的な移植実装とのギャップが小さくなります。Kaleidoscopeは他の言語で実装されたものがGitHub等で発見できるので[2]、C++ APIとC APIの差異に詰まったとしてもそちらを参考にすることができます。

Kaleidoscope in Rust

筆者はホスト言語(最初のコンパイラ実装を行う言語)にRustを選択したので、KaleidoscopeもRustで実装してみました。Rustを試したかったというのが主要な理由ですが、Rustがセルフホスティング実装に適している側面もあります。

繰り返しになりますが、ホスト言語によるコンパイラ実装は、 セルフホスティング時には自作言語上に移植していくことになります 。移植が最もスムーズにいくのはホスト言語と自作言語が完全に同等な言語機能を有している場合ですが、現在よく使われているプログラミング言語は機能相応に労力と時間をかけて構築されており、個人の自作言語がそれと同等な機能を有するのは難しいです[3]。ホスト言語のコンパイラ実装は できるだけミニマムで、ライブラリや言語機能への依存が少ない形 であるほど、移植時に発生しうる元の実装とのギャップを小さく抑えられます。ここで、Rustは以下の点で都合が良いです。

  • Rustはシステムプログラミング言語で、低級であり、ターゲットとなるLLVM-IRとのギャップが比較的小さい
  • コンパイル後のバイナリからも分かるように、ランタイムに相当するものがほぼ無い

Rustでの実装にあたっては、crates.ioに既にLLVM C APIのバインディングが存在するので、これを利用しました。ちなみにcrates.ioには高レベルなLLVMの抽象ライブラリも存在しますが、こちらもセルフホスティング時には移植する対象となるので、自前で極力ミニマムなC APIのラッパーを用意しました。これについては以下の記事で取り上げています。

https://zenn.dev/yubrot/articles/37b6724e41fd3c

このチュートリアルを終え、必要に応じてCLIインターフェースやリンカを呼び出してのリンク処理などを実装すると、単体で完全に動作する、ホスト言語で実装されたKaleidoscope言語のコンパイラ が得られます。またその過程で、LLVMによるコンパイラは非常に大雑把ながら、以下の仕事をすれば良いことがわかります。

  1. 入力のプログラムを解釈する
  2. LLVMのAPIを叩いてLLVM-IRを構築、マシンコードを生成する
  3. リンクなどの後処理を行う

言語機能のギャップを埋める

llrl/llrl0

Kaleidoscopeのコンパイラ実装が得られると同時に、「Kaleidoscopeを実装できる程度の言語」に求められる機能が見えてきます。

  1. 入力のプログラムを解釈する
  2. LLVMのAPIを叩いてLLVM-IRを構築、マシンコードを生成する
  3. リンクなどの後処理を行う

当然ですが、Kaleidoscope自身はまだこのような仕事はこなせません。

  • ファイルの入出力ができない
  • それ以前に文字列を操作できない
  • それ以前に文字列をデータとして持てない
  • というよりdouble型の即値以外扱えない
  • ...

このギャップを埋めていくことで、自作言語でセルフホスティングが可能な状態を目指していきます。セルフホスティングのための言語機能といいつつも、求められる機能の多くは汎用プログラミング言語に必要不可欠なものです。

Kaleidoscopeを実装した直後はホスト言語とのギャップは非常に大きく、どこから手を付けたら良いか見当が付きません。これについてもKaleidoscopeのチュートリアルはフォローしていて、チュートリアルの最後に実装を試みてみたい言語機能の例をいくつか挙げてくれています。いくつか取り組むうちに勝手がわかるとともに、Kaleidoscopeの実装の単純な拡張では限界があると感じられるかと思います。

言語デザイン

言語デザインも楽しみであり、悩みどころとなります。言語仕様が膨らむほどコンパイラの実装も大きくなりますが、言語仕様が貧弱であるほどセルフホスティングの実装も貧弱な言語で行うことになります。できるだけミニマムでありつつセルフホスティングが簡潔に済む言語デザインを考えてみるのも良いかもしれません。筆者はHaskellっぽい型システムとLispっぽいマクロ(LLVM JITを用いる)を中心に据えてみました。また、セルフホスティングを見据えるとホストと言語仕様が近い方がコンパイラの移植も行いやすくなります。

今回は、実装したい言語のデザインがある程度決まった段階で、コンパイラの仕事を細かいステップに分け、ステップごとにまとめて実装していく形を取りました。具体的には、始めに構文解析を仕上げ、プログラムが記述されたファイル群をモジュールとして読み込む機構を作り、ASTの構造を一通り考えてデータ構造に起こし、型チェック等の意味解析を順に実装し、...といった順番です。テストケースのセットも、そのようにテスト対象のステップが伸びていく(構文解析→名前解決→カインド推論→型推論→...)ように構成されています

ライブラリのギャップも埋める

llrl/std

自作言語では、コンパイラ実装と併せて、その言語用の標準ライブラリの実装も必要となります。基本的な文字列操作関数やファイルI/O、データ構造などは標準ライブラリとして適宜実装していくことになります。

言語デザイン同様、セルフホスティングを見据えるとホストのそれに近いライブラリデザインの方がコンパイラの移植も行いやすくなります。筆者はRustをホスト言語に選択したので、文字列化の型クラスDisplayや、Hash, HasherなどはRustの標準ライブラリの定義と似た形をしています。

既存の資産を利用してラクをする

汎用プログラミング言語に必要な標準ライブラリの実装は膨大なものになります。セルフホスティングに目的を絞ってもその量は少なくありません。筆者は標準ライブラリの実装にあたって多くの既存の資産を利用しました。

  • libc (C標準ライブラリ)
    • 現在のLinux環境のほとんどのプログラミング言語は内部的にlibcを使用しているのではないか
  • Boehm GC
    • 保守的なGC。ヒープアロケーションを全て GC_malloc で済ませて解放を忘れてしまう
    • また、言語機能の実装にあたっても 容赦なくヒープアロケーションを行ってしまう ように割り切る
  • 自前の極小ランタイム (rt.c)

それでも結果として、筆者の言語の標準ライブラリの実装はテストを含め10000LOC越えの結構な規模になってしまいました。一方、標準ライブラリの実装過程では、知識としては知っていたものについて実感を得るという体験が多かったように思います。例えばhash-mapord-mapはRustの HashMap, BTreeMap を参考に実装しましたが、いずれも漠然と持っていたイメージよりも密集度の高いメモリレイアウトをしていることがわかりました (メモリの局所性が重要)。

自作言語への移植

必要な言語機能とライブラリが揃ったら、自作言語へのコンパイラ実装の移植も行えます。この段階まで入ったら基本的にひたすら手を動かしていくしかありません。足りない言語機能やライブラリがあれば都度補完していきます。

自作言語上でLLVMのAPIを呼び出すため、LLVM C APIのバインディングも作成する必要があります。LLVM C APIのヘッダファイルを参照し、互換な定義を並べていきます (例: context.llrl, module.llrl)。

全体としてセルフホスティング実装は作業的なところも多く、もう少し自動化(コード変換など)を考えた方が良かったかもしれません。特にCヘッダはコンパイラ自身が読めるようにするか、あるいはCヘッダからの変換ツールを設けるのも良いかもしれません。

セルフホスティングの確認

最後にコンパイル結果の実行バイナリでdiffを取って、結果が完全に一致することを確認できました。

# Rustによる最初のコンパイラ(llrl0)でセルフホスティング実装をコンパイル -> llrl1
llrl0 ... -o llrl1

# llrl1でセルフホスティング実装をコンパイル -> llrl2
./llrl1 ... -o llrl2

# llrl2でセルフホスティング実装をコンパイル -> llrl3
./llrl2 ... -o llrl3

# 生成されたバイナリが完全に一致する
diff llrl2 llrl3

感想

セルフホスティングを目標にした自作言語の実装は予想外に大変でした。しかし、予想外だった点は「思ったよりも色々な機能の実装が必要だった」というところで、様々な機能の実装機会があり全体として楽しめたと言えます。言語デザインや実装上の課題があったり、取り組んでみたいことも色々発生したので(詳細はブログ記事)引き続き学んでいきたいと思います。

脚注
  1. OrcJIT等などの一部機能は現状(LLVM 12)C APIでは難しいが、チュートリアルの大部分はC APIでも実装できる ↩︎

  2. C実装, Rust実装, Haskell実装 など ↩︎

  3. C言語互換な言語を実装するならば、ライブラリは再利用でき、言語仕様は比較的小さく(要出典)、ランタイムもほぼ無いので可能ではある ↩︎

この記事に贈られたバッジ