⛰️

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

2021/07/08に公開

Rust

LLVM

compiler

tech

https://github.com/yubrot/llrl

llrlは自作のプログラミング言語です。大きな特徴が2つあります。

Hindley-Milnerベースの型推論による静的型付け (+型クラス)
Lisp-likeなS式によるシンタックスとLLVM JITによるマクロ

この言語の処理系をRustとLLVMを用いて実装し、それをllrl上に移植してセルフホスティングを試みました。無事セルフホスティングを達成したので、取り組んだことやモチベーションなどを順に振り返りたいと思います。

LLVMについては、フロントエンド側・バックエンド側ともに既にいくらかの解説記事が見られるため、概要は省略します。今回は新たなプログラミング言語のバックエンドとしてLLVMを用いるので、LLVMのフロントエンド側の実装がメインとなります。

事の発端: LLVM 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のフロントエンド実装のとっかかりを掴みました。LLVMを用いるコンパイラフロントエンドは、非常に大雑把ながら、以下の仕事をすれば良いことがわかります。

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

チュートリアルはC++およびLLVMのC++ APIを用いて書かれていますが、LLVMはC APIを提供しているので他の言語でもおおよそ問題ありません^[1]。筆者はRustでプログラミングしてみたいと思いRustで実装しました。

このチュートリアルを終えた後、LLVM-C APIを眺めていて、チュートリアルを延長してC APIを呼び出すための基本的な言語機能(関数呼び出し、静的型、ポインタ等)を備えていけばセルフホスティングも視野に入ると思ったのと、もっとRustを書いてみたい^[2]と思ったのが自作言語をRust + LLVMで始めた事の発端でした。

目標設定: セルフホスティング

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

今回、いくつかの理由から自作言語はセルフホスティングの達成を目標に据えることにしました。

セルフホスティングは明確なゴールがある

「自分自身をコンパイルして生成された実行バイナリが、元の実行バイナリと完全に一致するかどうか」によって、セルフホスティングが達成できたかを判定できます。

セルフホスティングに必要な機能が明確である

現代の汎用プログラミング言語に求められる機能は多岐に渡ります。理想的なプログラミング言語というものは存在しないか、ユースケースの数だけ存在してしまうでしょう。また到底個人の手で実装しきれるものでもありません。
セルフホスティングを目標とすることで、自作言語に最低限必要な言語機能が何かを判別できます。特にLLVM-C APIを用いる場合、C APIを呼び出すための一連の機能...

C呼び出し規約のサポート
LLVM-C APIで使用されているデータ型のサポート
- 各種数値
- NULL終端の文字列
- C互換な構造体
- ポインタ

等が必要となる一方、リッチなランタイムシステムなどは必要ありません。

Rustとセルフホスティングという目標の親和性

ホスト言語をRustとする選択は、セルフホスティングという目標にも適しています。ホスト言語によるコンパイラ実装は、セルフホスティング時には自作言語に移植していく必要がありますが、この際に障害となるのはホスト言語と自作言語のギャップです。ホスト言語と自作言語が近しい書き心地であるほど移植はスムーズに進められますが、自作言語がモダンな実用プログラミング言語と同等な利便性を得るには途方もない工数がかかります。 Rustもモダンなプログラミング言語ではありますが、一方で、システムプログラミング言語として設計されたRustの特徴は (リッチなランタイムシステムを持たないなど) 上述の「セルフホスティングに必要な機能」に挙げた特徴に近いため、セルフホスティングを目標に据えてデザインする自作言語とのギャップが比較的小さく済む見込みがあります。

言語デザイン

目標は定めましたが、それでも言語デザインは悩みどころです (楽しみでもあります)。前述した通り、移植は自作言語がホスト言語に近いほど楽ですが、言語仕様が膨らむほどコンパイラの実装自体が大変になります。結果として浮かび上がったのが、記事冒頭の特徴2つでした。

Hindley-Milnerベースの型推論による静的型付け (+型クラス)

型システムも、拘り始めると無限に時間が溶けていくことが容易に想像できます。自作言語の型システムは、よく枯れておりRustの型システムとも似ている「Hindley-Milner型システムをベースに、型クラスを加えたもの」としました。Typing Haskell in Haskellをおおよそ踏襲した形とも言えます。
型クラスはセルフホスティングの観点では過剰な言語機能ですが、Rustではtrait(型クラス相当の機能)が多用されるので、型クラスが無いとホスト言語と自作言語のギャップが大きくなりがちです。

Lisp-likeなマクロ

モダンなプログラミング言語には、使い心地を支える細かい言語機能が沢山ありますが、自作言語でこのような対応を逐一行っていくのは非常に大変です。

Lisp-likeなマクロを言語機能として持っていれば、 言語機能を小さく保ったままある程度の書き心地が得られるのではないか と思い、これを言語の核として取り入れることにしました。LLVMのJIT機能を活用して、コンパイル時にマクロのコンパイル→マクロ実行というのを試みたかったというのもあります。

コンパイラの実装 (llrl0)

実装したい言語のデザインがある程度決まったので、コンパイラを実装していきました。

コンパイラの実装について、例えば低レイヤを知りたい人のためのCコンパイラ作成入門ではインクリメンタルに言語機能を加えていく方式が取られています。今回はKaleidoscopeの経験が既にあったのと、意味解析周りのデータ構造に迷ったので、コンパイラの仕事を細かいステップに分け、ステップごとにまとめて実装していく形を取りました。

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

標準ライブラリの実装 (llstd)

基本的な算術演算から、文字列操作、イテレータ、配列やマップなどのデータ構造、タプル、ファイルI/Oなど、様々なプログラミングで必要な機能を標準ライブラリとして実装していきます。

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

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

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

libc (C標準ライブラリ)
- とはいえGo以外に標準でlibcに頼らないプログラミング言語をほぼ知らない
Boehm GC
- 厳密にはランタイムレベルで依存している
- 保守的なGC。ヒープアロケーションを全て GC_malloc で済ませて解放を忘れてしまう
- また、言語デザインにあたっても 容赦なくヒープアロケーションを行ってしまう ように割り切る
自前の極小ランタイム (rt.c)
- マクロとして定義されているlibcの stdin, stdout, stderr 等を関数として改めて提供したりとか
- 効率的な実装がきわめて難しい浮動小数点数の文字列化とか
- 自作言語が言語機能として持たないグローバル変数について、どうしても必要な場所だけC言語上の実装で代用したりとか

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

自作言語への移植 (llvm1, llrl1)

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

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

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

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

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

感想

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

脚注

OrcJIT等などの一部機能は現状(LLVM 12)C APIでは難しいが、チュートリアルの大部分はC APIでも実装できる ↩︎
言語実装はデータ構造を結構こねくり回すことになるので、Rustの所有権システムの実際の書き心地を試せそうだなとも ↩︎