Go to Qiita Advent Calendar 2024 Top
LoginSignup
96
52

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@spica314

自作言語でセルフホストしてみた

Last updated at Posted at 2020-04-10

はじめに

自作言語でセルフホストできたので，やったこと，考えたこと，得たこと，思ったことなどをまとめました．

きっかけなど

  • 「低レイヤを知りたい人のためのCコンパイラ作成入門」がまとまっててうれしい
  • x86_64などのプロセッサで直接動作するアセンブリを生成してみたかった
  • セルフホストできる程度の言語のコンパイラを実装したことがなかった
  • 自作言語を一通り設計・実装したことがなかった
  • 気軽に遊べる言語がほしかった
  • 関数呼び出しで括弧を使わない世界線のRustの雰囲気を感じたかった
  • GitLabの操作に慣れておきたかった
  • 現実逃避
  • ...などなど

コンパイラの名前はnecoです．HaxeのNekoと被るのでnecoにしています．言語の名前は決まってないけど拡張子は.necoにしています．necoは なんちゃら compiler の略ですと言いたいけれども略称はまだ決まってないです． コメントをいただいてneco is a compilerの略になりました．

リンク

やったこと

全体としては，自作言語以外の言語(今回はRust)で書かれた自作言語のコンパイラと，自作言語で書かれた自作言語のコンパイラを実装しました．終わり．

...はさすがにそっけないので，実装の流れの話をすると，ある程度機能が揃ってきたらRust製のコンパイラと自作言語製のコンパイラを同時に書いていきました．Rust製のコンパイラを書ききってから自作言語製のコンパイラを書かなかったのは，少しずつでも動いたほうが飽きないのと，ある程度自作言語のプログラムを書かないと使い勝手がわからなかったのが理由です．

実装量はRustが3400行ぐらい，自作言語が5200行ぐらいとなりました．たぶんもうちょっと減らせると思います．

どんな言語?

見た目

HaskellよりのRustみたいな感じにしている．
型がまだ適当なので見た目が怪しい．mutって付けてるけど何もチェックしてない．
スラッシュ2つで行コメントになって，各サンプルコードの先頭はmainの戻り値の想定値(もともとはテスト用)．

hello, world

// 14
fn main () : i64 = {
    let mut s: &[i8; 1] = b"hello, world!\n";
    _syscall 1 1 s 14 0 0 0
}

gcd

// 21
fn gcd (x: i64) (y: i64) : i64 = 
  if y == 0 then x else gcd y (x % y)

fn main () : i64 = {
    gcd 1071 1029
}

前置演算子をつけるたびに括弧をつけるのは面倒なので，
直前が前置演算子かwhitespaceか括弧で，直後がwhitespaceでないときは，二項演算子としてパースさせないようにしました．たぶんうまくいくはず．

Deref

// 3
fn f (x: i64) : i64 = x + 2

fn main () : i64 = {
    let mut y: i64 = 1;
    let mut x: &i64 = &y;
    f *x // この*はDeref
}

乗算

// 15
fn main () : i64 = {
    let mut f: i64 = 3;
    let mut x: i64 = 5;
    f * x // この*は乗算
}

// 15
fn main () : i64 = {
    let mut f: i64 = 3;
    let mut x: i64 = 5;
    f*x // この*も乗算
}

enum(ただの列挙体)とstruct
Rustっぽくしてみたけれどもカンマ入るしHaskellのdataっぽくしようかなぁと思っている．

// 3
enum Color {
    Black,
    White,
}

struct P {
    x: i64,
    y: i64,
    color: Color,
}

fn main () : i64 = {
    let mut p: P;
    p.x = 1;
    p.y = 2;
    p.color = Color::Black;
    match p.color {
        Color::Black => p.x + p.y,
        Color::White => 0,
    }    
}

参照でも.でアクセスできる．メンバのアクセスと配列のアクセスのときは，左側のアドレスを計算したあとで，左側の型の参照がとれるまで参照を外すようにした．

// 42
struct A {
    x: i64,
}

fn main () : i64 = {
    let mut a: A;
    let mut ref_a: &A = &a;
    ref_a.x = 42;
    a.x
}

(とりあえず)手を抜いた部分

"自作言語の"コンパイラ

手を抜いたというのは少し違うけれども，"今のところ"，トータルでは手間が省けているつもりでいるのでここに入れておく．
自作言語の場合，文法を構文解析しやすくできるし，C言語などの細かい仕様は全部無視できるし，実装がめんどくさい機能の実装を飛ばせる．

ただ文法はバグりまくる

関数呼び出しの引数はスタックに積む

libcなどのライブラリを使っていないのと，システムコール用の関数のアセンブリを埋め込んだことから，(現時点では)他の言語で書かれた関数を呼びだすことがない．なのでABIを無視しても問題ないはずで，引数をすべてスタックに積むことにしても動く．

戻り値はレジスタに入るサイズのみ

戻り値をraxレジスタで返すことにしたので，raxに入らない値は返せない．
構造体とかを返したい場合は参照を渡して書く．
冷静に考えるとこっちもスタックで返したほうが一貫性があった気がする．

おもしろかったこと・得たこと

テストは通るのにコンパイラを全然コンパイルできない

テストとはなんだったのかと言いたくなるレベルでコンパイラをコンパイルできなかった(コンパイルできない，コンパイルが終わらない，生成コードがバグる，etc.)．
原因は，文法が曖昧で構文解析が意図通りに動かなかったり，比較を符号ありのところを符号なしの命令でやってたり，関数を呼び出したあとで引数をpopし忘れていたり，letで前の変数を隠すときに右辺を計算する前に記号表に登録したり，そもそも実装しきってない使い方だったり...

落ちるたびにテストを追加して直していった...つもりでいたけどログを振り返ってみたら追加していないのがそこそこある．スタックの使い方が間違えてた場合とかのテストが作りづらいのを飛ばしがちっぽい．多少意識しようかな．

セルフホストしたコンパイラでコンパイルすると落ちるやつ

これはなぜかあまり起きなかった．解決時間1日ぐらい．
ほぼ同じアセンブラを出力する，(セルフホストするコードに手を入れずに使える)デバッグコード書き放題のコンパイラのコード(今回ならRust製)があるのが影響してるんだろうか．アセンブリを比較すれば違うところが(比較的)すぐにわかった．

他に考えられる理由としては，似たようなコードが多くて，使ってる機能と使い方が偏ってるというのもありそう．たぶん今回書いたコンパイラ以外のコードならいくらでもバグる(なんか違う気もする)．

この部分で時間とられると思ってたけどあっけなくセルフホストできてしまい，なんか感動する間がなかった．

FLAGSレジスタのAlignment Check(AC)の使い方

アラインメント周りの処理を間違えていたら落としたかったので，ACを有効化した．
以下のアセンブリを入れればいいはず．

    pushfq
    pop rax
    mov rdi, 0x0000000000040000
    or rax, rdi
    push rax
    popfq

手元ではうまくいってるけども環境依存かもしれない．

最初アラインメントがずれてても落ちないようにするフラグだと思ってて0にしてたら何もおきなくてあれ?ってなった．名前を読めばそれはそう...

参考: https://en.wikipedia.org/wiki/FLAGS_register

インクリメンタルなコンパイラ実装

「低レイヤを知りたい人のためのCコンパイラ作成入門」に書かれていたインクリメンタルなコンパイラ実装っぽくやってみていた．

やる気の維持に効果があったと思う．セルフホストまでいけたし，とりあえずでも動くのは楽しい．
あまり苦なくテストを増やせていけるのも良かったと思う．

やってみて思ってたのと違ったのは，〜を実装しようと実装を始めたら，あれもいるしこれもいるしってなって思ってたより実装が多くなってぐぬぬ...ってなることが多かった．
ある機能を追加するときに何が必要か考えて実装順とかをもうちょっと考えようと思った(それはそう...)．
最初からlibcなしでやってた影響で，libcに入ってるような機能の実装が必要だったのもあるかもしれない．

GitLab

Merge RequestのWIP

WIPを付けているときにはMergeを押せないので，間違えづらくてよかった．
この記事を書いてて知ったけどGitHubにもDraft Pull Requestというのがあるらしい．

Merge when pipeline succeeds

基本GitHub Flowっぽく開発をしていた．
作業を終わりたいけどCIがまだ終わらない...っていうときに，Merge when pipeline succeedsを押しておけばCIが通ったらマージしてくれるので便利だった．

今後

  • とりあえずはbootstrap用のコンパイラのコードとセルフホストできるコンパイラのコードを合わせた全体をシンプルにしようかなぁと思っている(言語設計を含め)．
  • モジュール，標準ライブラリ，IR，ABI，型のジェネリクス，最適化，...
  • RustでGPGPUしたときにCUDA Driver APIの使い方を動かせる程度には理解したので，PTXコードを生成できるようにすればGPGPUできるよやったね
  • そのうち Calculus of Inductive Constructions でも入れて no error compiler にしたさあるけど100万年ぐらいかかりそう
  • そのうち Calculus of Inductive Constructions でも入れて証明をね，やりたい

感想

  • コンパイラへの興味・関心度が増えた
  • 感情をあまり消費しなくていい感があるのでゆるめの趣味にちょうどよさそう(?)
  • 自作コンパイラは(も)いいぞ
96
52
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
96
52

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?