素朴な自作言語Ruccolaのコンパイラをセルフホストした

自作言語 Ruccola のコンパイラがセルフホストできました！

https://github.com/sonota88/ruccola/tree/main/selfhost

<!--
[github.com/sonota88/pric/tree/main/examples](https://github.com/sonota88/pric/tree/main/examples) にいくつか Pric 言語で書いたサンプルコードがあります。
-->

（2021-06-26 追記）
[Pric という名前はよろしくなさそう](https://twitter.com/sakuro/status/1407679707194093569)という情報をいただきました。自分では気づけていなかったので大変ありがたいです。k が付いたものと発音がおそらく同じになるので、ダメそうですね。何か別の名前を考えようと思います。

（2022-01-12 追記）
名前を Pric から Ruccola に変えました。記事の記述などはおいおい修正していきます。



# 概要


## これまでのあらすじ

これまで vm2gol（virtual machine to game of life）というプロジェクト名で以下のようなことをやってきました。


- (2018) [RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話](https://qiita.com/sonota88/items/f9cb3fc4a496b354b729)
    - vm2gol-v1
    - 高水準言語の代わりに構文木を直接書き、それをコンパイルして VM で動かすところまで
    - ライフゲームだけコンパイル + 実行できればOK
    - コンパイラ作ったことなかった人がなんとかしてむりやり入門した、という話
    - 雑、汚い
- (2019〜) [Rubyで素朴な自作言語のコンパイラを作った](https://qiita.com/sonota88/items/2b95378b43a22109513c)
    - vm2gol-v2
    - v1 のリライト版（機能的にはほぼ同じ）にフロントエンド部分を追加したもの
- (2020〜) [vm2gol-v2 をいろんな言語に移植](https://memo88.hatenablog.com/entry/2020/08/30/132314)
    - アセンブラ・VM は除いてコンパイラ部分のみ
    - TypeScript / Python / Dart / Java / C / Perl / C♭ / PHP / Go / LibreOffice Basic / Zig / Kotlin / Crystal / Rust / Julia / Pascal / OCaml ... 気が向けば続く予定

<!--
    - 今回ここに Pric 言語自身が加わった形
今回のセルフホスト編は何もないところから全部書いたわけではなく、v2 をベースにした追加開発です。
-->

今回のセルフホスト編は何もないところから全部書いたわけではなく、すでに v2 がある状態から出発しています。



## 概観



<!--
（図では名前が Pric のままになっていますが、後で修正します。Ruccola に読み替えてください。）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/72df9d6b-1e86-f986-3d75-9bbfe58c017d.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/6f069eb0-8f3a-0430-5d60-af4844be043f.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/39ceee23-4fdf-8279-f2cc-4c43cd58df58.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/26b38f3e-f33b-5991-3429-b4069328b098.png)

-->

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/c8323645-d9db-400f-009d-5b177253f863.png)


<!--
※ 実際にコンパイラが出力するのはアセンブリコードですが、説明の簡略化のためアセンブルの過程は省略しています。
-->

※ 独自VM向けなので「仮想機械語」のように呼ぶべきかもしれませんが、この記事では単に「機械語」とします。
※ 図ではコンパイラが直接機械語を出力しているように見えますが、実際はアセンブルの過程があります。説明の簡略化のために省略しています。

---

T図式でも描いてみました。図の「Ruccola M」は Ruccola VM 向けの機械語。

<!--
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/049452d5-53bf-25b6-394c-bded1da76296.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/494999b5-8679-b658-3b24-48de31731598.png)
-->

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/3ab4039a-d4da-0b07-eba7-0271bfb37a3c.png)


## 期間

2021-01-12 〜 2021-02-21

<!--
機能を絞ったのが功を奏してか、一ヶ月ちょっとでセルフホストできました。
-->


## 規模

第2世代コンパイラのサイズ（行数）はこのくらい（2021-06-21 現在）:

```sh
$ wc -l lexer.pric parser.pric codegen.pric \
>   lib/json.pric lib/std.pric lib/types.pric lib/words.pric
  250 lexer.pric
  973 parser.pric
 1325 codegen.pric
  170 lib/json.pric
  536 lib/std.pric
  461 lib/types.pric
  305 lib/words.pric
 4020 合計
```

```sh
# 補助ツール的なもの
$ wc -l check.rb preproc.rb
 110 check.rb
  19 preproc.rb
 129 合計
```

# バージョンと世代

以下、v2/v3 と 第1世代/第2世代 という表現が出てくるので先に説明しておきます。

- バージョン: 言語仕様＝機能セットの違い
    - Ruccola v2: ライフゲームはコンパイルできる。セルフホストはできない。
    - Ruccola v3: セルフホストに必要な機能を v2 に足したもの
- 世代: 記述言語の違い
    - 第1世代コンパイラ: Ruby で書いたもの
    - 第2世代コンパイラ: Ruccola で書いたもの

※ 今回作った v3 ではライフゲーム（game of life）専用ではなくなるのと、やっぱり呼びやすい名前がほしくなって **Ruccola** という名前を付けました。 vm2gol ＝ Ruccola （プロジェクト名・言語名）という雑な捉え方でだいたい大丈夫です。 vm2gol がコードネームで Ruccola が正式名みたいな雰囲気。



# 工程

## ステップ (1) 第1世代 v2 コンパイラにセルフホストに必要な機能を追加

第1世代なのでここは Ruby のコードの修正です。どのような機能を追加したかについては後述。

<!--
160% でスクショする
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/d61f6fe7-c69b-7ed3-3d32-a198d85105de.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/b87ba835-70fa-84b0-8c50-3f468af93cec.png)
-->

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/52c64224-121f-6dcd-8258-faa4b2cd5126.png)



できたもの: 第1世代-v3 なコンパイラ



## ステップ (2) Ruccola 言語 v3 でコンパイラ v2 を書く


別の言い方でいえば:

- コンパイラ v2 を Ruccola 言語 v3 に移植
- ステップ (1) で作った第1世代-v3 なコンパイラで第2世代-v2 なコンパイラをコンパイルできるようにする

<!--
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/6b8bfd9b-17e4-c7ae-aaf5-3e116c337b7e.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/5851a19b-a74d-7d3b-1b63-36640effd42f.png)
-->

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/09d6a2d4-0bf1-97f9-bdb6-cbc61bb549b4.png)

ここからは Ruccola 言語でもりもり書いていきます。
第2世代コンパイラはこの時点では v2 の機能しかサポートしておらず、ライフゲームはコンパイルできますがセルフホストはまだできません。

v2 コンパイラの移植作業はこれまで何度もやってきていてだいぶ慣れています。Ruccola 版に一番近い [C 言語版](https://memo88.hatenablog.com/entry/2020/09/06/043607)もすでにありますし、実装で悩んだら C言語版を見ながら移植していけばOK。また、これまでの移植の過程で整備されてきたテスト用データもそのまま使えます。

できたもの: 第2世代-v2 なコンパイラ




## ステップ (3) 第2世代コンパイラ v2 を v3 にしていく

やることはだいたいステップ (1) と同じ。

<!--
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/9900436b-14a9-40b0-843c-482c764b5fa9.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/fb03ec01-5826-7ac3-16fa-5ee70b49ea11.png)
-->

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/1fcd8072-a8e1-2d6a-5df8-24550345ea95.png)


できたもの: 第2世代-v3 なコンパイラ … これができれば完成

----

ステップ (2) の移植作業はこれまでやってきた移植作業と同じようにやればいい。

<!--
ステップ (3) は Ruby で (1) をやったことをなぞって Pric で繰り返せばいい。
-->

ステップ (3) は (1) でRuby でやったことを繰り返して Ruccola で同じように書けばいい。

<!--
というわけで、今回自分にとって一番収穫の大きかった工程は (1) でした。ステップ (1) が今回のハイライト＜目玉＞です。
-->

というわけで、全体の中ではステップ (1) が今回の目玉でした。今回自分にとって一番収穫の大きかったのがステップ (1)。

(1) ができた時点で (3) で何をやればいいか大体の目星が付き、後はやっていけば終わるなという感じで割と気楽に進めていきました。とはいえ、退屈な作業というわけではなく、自作の言語でこれくらいの分量のプログラムを書くのは初めての経験でしたから、 (2) も (3) も十分新鮮でおもしろかったです。





# 方針

<!--
    - なるべく凝ったことをせず、多少冗長な書き方だったり遅い書き方でもよいのでバグりにくそうな方に倒す（そこらへんの改善はセルフホストできた後でよい）
-->

- セルフホストに必要かどうかで機能を選ぶ
    - v1 では「ライフゲームのコンパイルに必要か？」で決めていたが、
      今回も同様に「セルフホストに必要か？」で判断する。
    - なるべく寄り道しない / まずは曳光弾を通す / 後回しにできるものは後回し
        - ここらへんも v1 のときと同じ。目標を絞って集中し、長期化させないように。
        - 「とにかくセルフホストできれば細かいところはどうでもいい」くらいの気持ちで
        - セルフホストすることが目的で機能追加はそのための手段
    - 後回しにした機能については後述の「TODO」の節を参照
- なるべく少ない機能で
    - ミニマル・シンプルに作りたい気持ち
    - 禁欲的に / ケチケチと
    - (1) で機能を盛りすぎると (3) が大変になりそう
        - ステップ (1) で機能を追加するとき、つねに「これを追加するとステップ(3) で大変にならないか？」と考える。ステップ (3) の負担がなるべく小さくなるように意識する。
        - [DQNEO さんの minigo のセルフホストの話](https://qiita.com/DQNEO/items/2efaec18772a1ae3c198)などで大変そうな話を見聞きしていたのが影響していると思います。先達の経験談、ありがたや……。
- C言語を参考にするが、あくまで参考程度。C への準拠にはこだわらない。
- 自作言語でセルフホストするのは今回初めてなので、無理しない。適宜ハードルを下げる。
    - 空間効率、速度効率は気にせず富豪的に。開発効率的に辛くなってきたらそのときなんとかする。先回りしすぎないように。
    - なるべく凝ったことをせず、多少冗長な書き方だったり遅い書き方でもよいので確実に動きそうな方に倒す（そこらへんの改善はセルフホストできた後でやればよい）

<!--
    - 外側にもう一段メタなレイヤーが必要になるなら実装する。
        - 例: 配列操作
    - ほんとに必要か？ すでにある機能で実現できないか？ と考えることで対象についてよく考えることができる
        - 結果として必須度の高いものだけが残り、シンプルなものができあがる。たぶん。

-->


# セルフホストに必要な機能

はっきり決めていたわけではありませんが、基本的には C言語版に近い感じになるのかなとイメージしていました。
そうすると、 C言語版では使っていて Ruccola v2 にない機能をリストアップしていけば、それが v3 で追加すべき機能の候補ということになります。

- 入出力
- ポインタ
- ヒープ / malloc
- 配列
- 文字列
- 構造体
- グローバル変数
- プリプロセッサ
  - ファイル分割 / `#include`
  - マクロ / `#define`

ざっとこんなところかなあとぼんやり考えて、後は作りながら決めていきました。
以下、思い出しながらそれぞれについて書いてみました。

※ 以下は説明のために整理していて、実際に考えたり作った順番とは多少違いがあります。

※ ちなみに、私はC言語はずっと前にちょっとやった程度でだいぶ忘れています。素人が書いていると思って読んでいただきたく……勘違い・浅い理解・不正確な記述などあると思います。



## 入出力

1文字ずつ読み書き。これは必要。
VM に命令を追加: `read`, `write` 

入り口と出口で文字と数（アスキーコード）との変換を行い、コンパイル処理本体で扱っているのはすべて単なる数（整数）となるイメージです。

```
"def main()\n ..."

↓ read

100 101 102 32 109 97 105 110 40 41 10 ...

↓コンパイル

32 32 99 97 108 108 32 109 97 105 110 ...

↓ write

"  call main\n  exit\n ..." （アセンブリコード）
```

<!--
こういうイメージですね。
-->

こうやって見てみると、コンパイラがやっていることは「ある数の並びを別の数の並びに変換する」処理だと見ることができます。おもしろいですね。結局それしかやっていないというか。

<!--
これだけでもだいぶ進歩した感じがあって嬉しいものです。
-->

それはさておき、出力ができるようになると print デバッグができるようになります。また、出力を検証する形でテストできるようになり、これだけでもだいぶ進歩を感じるものです。「おっ、この機能ができたらアレとアレができるようになるじゃん！」という、ブートストラップの楽しさ。

hello world はこんな感じ。こんなのでも動くと嬉しい。

```ruby
def putchar(c)
  write(c, 1);
end

def main()
  putchar( 72); # H
  putchar(101); # e
  putchar(108); # l
  putchar(108); # l
  putchar(111); # o
  putchar( 44); # ,
  putchar( 32); # (SPACE)
  putchar( 87); # W
  putchar(111); # o
  putchar(114); # r
  putchar(108); # l
  putchar(100); # d
  putchar( 33); # !
  putchar( 10); # (LF)
end
```




## 比較演算子

演算子としては小なり `<` だけ追加しました。これだけ追加すれば、 v2 からある `==`、`!=` と組み合わせてあれこれできます。

VM にレジスタを追加: `sf` （sign flag）
VM に命令を追加: `jump_g` ... x86 の `jg` 命令を参考に


## ファイル分割

```
#include lib/std.pric
```

<!--
今思えば単に cat コマンドで繋げるだけでも良かったですね。
-->

のような行を探し、指定されているファイルを読み込んでその場に埋め込むスクリプトを Ruby で書きました。
が、これは単に cat コマンドで繋げるだけもよかったですね。そうしておけばさらに簡略化できた。

※ 機能として挙げましたが、この部分はコンパイラの本体に含めず、補助ツールの類である（セルフホストの対象外）ということにしました。



## アドレス演算子・デリファレンス演算子

C の `&` と `*`

- ステップ (1) の中ではここがキモ
    - キモといいつつちょっと怪しいので改めて整理したい……
- 「[ふつうのコンパイラをつくろう](https://www.sbcr.jp/product/4797337958/)」を読み返す
    - デリファレンス演算が左辺にあるときと右辺にあるときの違い
- [chibicc](https://github.com/rui314/chibicc) や [cbc](https://github.com/aamine/cbc) の出力するアセンブリを観察
    - なるべく最適化されていないアセンブリ出力を見たい
    - [Compiler Explorer](https://gcc.godbolt.org/) もお手軽・便利
- アドレス演算のために VM に `lea` 命令を追加
    - x86 の `lea` 命令を参考に
- 「ポインタがある」というか「アドレス演算とデリファレンス演算と、アドレスの入った変数がある」といった雰囲気（一緒？）


<!--
- v2 では間接参照が base, disp だけだったところに index を追加 … 結局使ってない？
-->

---

デリファレンスの括弧の中の部分は単なる式ということにしています。

```
*( some_addr_ + 2 )
   ^^^^^^^^^^^^^^
   この部分は単なる式
```

<!--
（`*( {起点アドレス}, {起点からのずれ} )` ）
-->

途中紆余曲折があって `*(some_addr_, 2)` のような書き方を試したりしましたが、括弧の中にはただの式を書くことにして単純化し、C っぽい見た目に落ち着きました。

デリファレンス演算の視点（？）では「とにかく何か値（式の評価結果＝アドレス）が渡されるので、そのアドレスが指している場所を操作対象とする」のように考えればよい、ということに。

----

（余談）乗算の `*` と被るのでデリファレンス演算子には別の記号を使うのはどうかと考えて `^` にしてみたり、前置じゃなくて後置にするのはどうだろう？ と考えて `( ... )^` にしてみたり……という試みが途中ありました。

<!--
下手な考え休むに似たりかと思いきや、Pascal ではそのように書くのだと後から知りました。たまたまとはいえ同じところに辿りついたようで、ちょっとおもしろかったです。
-->

下手な考え休むに似たりかと思いきや、Pascal ではそのように書くのだと後から知りました。図らずも似たところに辿りついていたようでちょっとおもしろかったです。

<!--
他のボツ案としては `addr(some_var)`, `deref(some_addr_)` のように普通の関数っぽい構文にしてしまう、というものもありました。
-->

他には `addr(some_var)`, `deref(addr_expr)` のように普通の関数っぽい構文にしてしまう、という案もありました。パースは少し楽になりそうですが、視認性が悪そう（普通の関数と見分けにくそう）な気がしてボツに。




## ヒープ / malloc

<!--
（ `Memory#stack` 、名前変えないと……）
-->

メモリのスタック領域として使っていた部分のうち、アドレスの小さい方の端をヒープとしました。

malloc もまじめに作らないといけないのかなと思ってあれこれ調べていたんですが、単に確保した分だけカーソルを動かすだけなら簡単で私でもすぐ作れそうね、じゃあそれで、ということになりました。

<!--
とにかくまずは簡単な方法でセルフホストできるところまで逃げ切りたい。
-->

※ bump allocator とか stack allocator と呼ばれている方式だそうです。 参考: [Allocator Designs | Writing an OS in Rust](https://os.phil-opp.com/allocator-designs/)

というわけで allocate 関数の中身はこれだけ。

```ruby
def allocate(g_, size)
  # 変更前のカーソル位置
  var head_addr = *(g_ + GO_ALLOC_CURSOR());
  # 変更後のカーソル位置
  var next_addr = *(g_ + GO_ALLOC_CURSOR()) + size;
  # カーソル位置を更新
  *(g_ + GO_ALLOC_CURSOR()) = next_addr;

  # スタックと衝突していないかチェック
  check_heap_stack_overlap(g_);

  # 確保した領域の始点アドレスを返す
  return head_addr;
end
```

（`g_` はグローバル変数構造体のアドレス。後述。）

<!--
※ 引数で渡されている `g_` はグローバル変数構造体（後述）のアドレス
-->

free はありません（C言語版でも free してなかった）。ここは富豪的に。
富豪的にやってどのくらいメモリが必要だったかというと、最終的には番地の数で 2,600,000 となりました。1 byte/番地で換算すると約 2.6 MB。

<!--
今の私の知識でXX年前に転生してもメモリ不足によりコンパイラ動かせないですね。
50年前に転生しても今の私ではセルフホストできない。
-->

あと、ヒープとスタックの衝突を Ruccola コードのレイヤーで検出する作りにしていて、そのためにレジスタ `sp` の値を取得する組み込み関数を追加しました。ここはちょっとやっつけ。




## 配列

配列は作る前からイメージがあって特に詰まらずに作れました。
「[低レイヤを知りたい人のためのCコンパイラ作成入門](https://www.sigbus.info/compilerbook)」にならって、普通のローカル変数と同じようにスタックに置きます。

構造体の配列を使いたい場合は構造体のデータそのものは持たせず、ポインタというかアドレスを持たせる形で使います。もしデータそのものを持たせるとしたら各要素のオフセットの計算は自前でやらないとダメ（言語によるサポートはない）。

---

`配列変数名[添字]` で配列の要素にアクセスする構文を一度用意して、ステップ (1) では実装までしましたが、ステップ (3) でやることが増えるので取りやめにして実装も削除しました。

デリファレンス演算子があれば

```ruby
a = *(xs_ + 1);
*(xs_ + 1) = 2;
```

<!--
のように配列の要素を読み書きできます。ポインタ演算のシンタックスシュガーですね。
機能はなるべく少なくしたいという方針に沿って、今回は `[]` 演算子は取りやめにして実装も削除しました。
-->

のように配列の要素を読み書きできます。つまりポインタ演算のシンタックスシュガーなわけですね。だったらなくてもいいかなと。

<!--
ただし、実際は下記のような関数を介して操作するようにしています。「これは配列を扱っているんだな」という意図を表すため。
-->

ただし、「これは配列を扱っているんだぞ」という意図を表すために実際は下記のような関数を介して操作するようにしています。

```ruby
def aset(array_, i, val)
  *(array_ + i) = val;
end

def aget(array_, i)
  return *(array_, i);
end
```

Ruccola 言語で書けるものに関してはこのようにユーティリティ関数を作っていきました。

----

それで、結局配列のために手を加える必要があったのは

- 変数宣言時に幅を考慮（スタックポインタを幅1つ分ではなく配列の長さの分ずらす）
- 変数名からスタック上の位置を割り出す際に配列変数の幅を考慮

これだけといえばこれだけですね。
「配列という機能を追加した」というよりは「変数の幅の考慮とポインタ演算を組み合わせることによって配列の操作に相当する操作ができるようになった」という感覚です。



## 文字列

配列があればOK。プログラマ（私）が「これは文字列なのだ」と思い込むことにより文字列として扱うことができます。

たとえば C だったらこのように書くところを、

```c
char str[] = "hello";
```

Ruccola では次のように書きます。

```ruby
var [6]str;
aset(&str, 0, 104); # h
aset(&str, 1, 101); # e
aset(&str, 2, 108); # l
aset(&str, 3, 108); # l
aset(&str, 4, 111); # o
aset(&str, 5,   0); # (NUL)
```

さすがに毎回手で書くのは面倒なので適当なスクリプトで生成してターミナルからエディタに貼り付けていました。

また、コード上での行数が多くて邪魔なのと、複数箇所で同じ文字列を使うケースがあることから、実際は次のように文字列に値を詰める処理を関数にして使っています。

```ruby
var [6]s_hello; set_s_hello(&s_hello);
```

ちなみに、文字列関連の何かを調べていたときに Pascal の文字列（先頭に文字列長を持つ）について知りました。Pascal 方式の方がバグが発生しにくそうな感じがしてちょっとなびきかけましたが、ひとまず C に寄せました（Pascal よりは C の方がなじみがあるため）。




## 構造体

- 構造体のサイズ分の領域の確保ができて、
- 起点と、各メンバのオフセットと幅が扱えて、
- あとはポインタ演算ができれば読み書きできる

<!--
ということにしました。
-->

心の目で見ると構造体のようなものに見える何か。これもすでにある機能でまかなえてしまいます。

構造体のデータはヒープに置いていていますが、これはそういう制約がある訳ではなくとりあえずのルールです。たぶんスタックにも置けるはず。

<!--
スタックに置いてよい場合は適宜スタックに置けば良かったかな……と今書いていて思いました。
-->

`some_struct.some_member` や `some_struct->some_member` のような構文は用意せず、操作用のインターフェイスとなる関数を作ってその中でごにょごにょしています。
例を挙げると以下は List 構造体の size メンバの値を返す getter 関数です。アドレスがあればそれで操作できるぞい、というノリ。

```ruby
def List_size(self_)
  var size = *(self_ + LIST__SIZE());
  return size;
end

# 呼び出し側
# C でいえば list_->size に相当
var list_size = List_size(list_);
```

結局、メモリ上の位置とデータがあって操作がある、ということでしょうか（それはそう）。

<!--
いろんなものがシンタックスシュガーなんだなあ、という気付きがあります。
-->



## グローバルな定数

<!--
先頭の方で定義しておいて、コード中に出現したら置き換えるという方式を考えていましたが、

ソースコード中の特定の文字列を単純に置換するだけなら、別に難しくなさそうだけど……
などと考えていましたが、これも機能少なめの方針により・・・
Ruby なら簡単ですが、 Ruccola で書くとなるとちょっとめんどくさそうというか大変そうです。

定数マクロにすればよいのかなとか考えていたのですが、
関数は大体どこからでも呼び出せるので、値を返す関数を作っておけば
グローバルな定数と同等なものとして扱えます。
マクロの仕組みを追加しなくてもすでにある関数を使えばOK。
じゃあそれで。

ソースコード中の特定の文字列を単純に置換するだけなら、別に難しくなさそうだけど……などと、当初は単純な置換マクロ的なものを想定していました。
-->

関数はどこ（他のどの関数）からでも呼び出せますから、固定値を返す関数があればグローバルな定数と同等なものとして扱えます。マクロのような仕組みを追加しなくても、すでにある関数を使えばOK。じゃあそれで。

※ ということにしましたが、コンパイラの機能に含めないことにしてプリプロセッサでやってしまってもよかったかも。

たとえば 1つ前の「構造体」の節のコード例に出てくる `LIST__SIZE()` がこれです。





## グローバル変数

たとえば ELF だと .data セクションや .bss セクションに置く、という話があります。
しかし、その方向で進めるとなるとアセンブリ・機械語のファイルのフォーマットやメモリレイアウトも考えないといけなくなります。話が大きくなってハードルが上がってしまう（完成までの道のりが長くなってしまう）ように思われました。

<!--
それに、グローバル変数が必要とはいっても使っているのは数個程度なんですよね。それだけのために大げさな仕組みを導入するのもなあ……という気分もありました（数の問題ではないかもしれませんが）。
-->

そこで、グローバル変数に関してもすでにある機能でなんとかできないかと。

要するに

- どこでも使えて
- 読み書き両方できる

という要件を満たせれば、その何かをグローバル変数相当のものとして使えます。

そこで思いついたのが、エントリポイントである main 関数で構造体を1つ用意して、そのアドレスを関数の引数でバケツリレーしていく方法です。よし、じゃあそれで。

<!--
構造体のアドレスが分かれば構造体のフィールドをどこでも読み書きできるということになります。

というわけで、エントリポイントである main 関数で構造体を1つ用意して、そのアドレスを関数の引数でバケツリレーしていけばどこからでも読み書きできるじゃん、ということにしました。
これなら新たな機能を追加せずともここまでに出てきた機能だけで実現できます。
-->







## 機能追加まとめ

- 入出力: 追加した
- 比較演算子: `<` だけ追加した
- ファイル分割: セルフホストの対象外とした
- アドレス演算子・デリファレンス演算子: 追加した
- ヒープ / malloc: ほぼ追加なし
- 配列: 幅を考慮して変数を扱えるようにした
- 文字列: 追加なし
- 構造体: 追加なし
- グローバルな定数: 追加なし
- グローバル変数: 追加なし

こうして見てみると、今回は

- アドレス演算子・デリファレンス演算子を使って間接参照ができるようになった
- メモリ上のある範囲をまとめて扱えるようになり、間接参照と組み合わせて配列・文字列・構造体相当のデータが扱えるようになった

<!--
ことの比重が大きく、これらを利用することでさまざまなことができるようになった、と振り返ることができそうです。
-->

ことの比重が大きく、これらを利用することでできることの幅がかなり広がった、と振り返ることができそうです。

<!--
ことが全体の中での比重が大きいようです。
※ 細かい部分で漏れがある気がします。思い出したら追記します。

関数によって可能になることの範囲が広い
守備範囲が広い
関数の持つ抽象化の力でしょうか。
（なので、現状では論理演算子の短絡評価はありません）
-->

また、グローバルな定数や配列・構造体操作用の関数に加えて  `-`, `<=`, `&&`, `||` などの演算子も関数でなんとかしていて、関数があることでなんとかなっている部分も多いですね。関数えらい。抽象化の力。

<!--
それから、この程度の機能追加で済んでいるということは、Pric コンパイラがこの程度の機能しか使っていない（この程度で済むように作った）ためでもあります。
高度な数学的知識が必要ということもないですし、面倒な並列処理が必要ということもなく、単純なコンパイラはそういう意味では難しい部類のプログラムではない、と今は思えます。
-->

<!--
★ ここらへんは「感想」の節に移動するとよいかも
-->




# 感想など

- v1 のときほどのがんばりは必要なく（そういう意味では盛り上がりに若干欠け）比較的落ち着いて進めた感じでしたが、
  それはそれでOK。十分楽しく、達成感もありました！
- 先にC言語版を作っていたのが結果として良かった。ここで悩まずに済んだのも大きかった。
- 今回セルフホストまで達成できましたが、思い返してみれば
  一度 v1 を作ったことが足がかりとなり、視界が開けて「自走できるようになった感」が得られたように思います。
  がんばって v1 作って良かったなあとしみじみ。
- ステップ (1) の部分は単純に知識・経験が得られてよかった（低レイヤーの知識がまたちょっと増えた）
    - メモリ操作用言語でメモリ操作している、みたいな感覚が体験できた
- （今回は）構造体や文字列など、いろんなものを「見立て」でなんとかしている。つまり、概念は開発者（＝自分）の頭の中にある。「これ不便だからこうしたら便利じゃね？」みたいなアイデア（シンタックスシュガーなど）も同様。
    - 現在使われている言語の機能も、かつて開発者の頭の中にあったものが歴史を経て少しずつコードに落とされてきたものの蓄積……と考えると感慨深いものがありますね。今もいろんな人の頭の中に未来の便利機能のアイデアが眠っているのでしょう。
- 節目で何度か[言語処理系Slack](https://prog-lang-sys-ja-slack.github.io/wiki/)で進捗報告してリアクションをいただけたのがたいへん励みになりました。ありがとうございました。



# TODO

まずは文字列リテラル（に相当する部分）を静的なデータとして使いまわせるようにするところから手を付けたいですね。
おそらくここが速度的に一番のボトルネックになっているので、ここをなんとかするだけでかなり速くなって、後が楽になるんじゃないかと。

----

パッと思いつくもの、やりたいなーと思いつつ自重していたのはこのあたり。「これらがなくてもセルフホストまでできた」という機能の一覧にもなっています。

- 文字列リテラル
- 配列アクセス演算子 `[]`
- 演算子の優先順位
    - 明示的に `(` `)` で囲めば済むので結局今回もお流れとなった
- 単項演算子 `-`
- 演算子の追加 `-`, `/`, `%`, `>`, `!`, `&&`, etc.
- `&&`, `||` の短絡評価
- まともな構造体
- まともなグローバル変数
- 型
- 関数の途中での return
- break/continue
- その他、雑多な改善: リファクタリング・パフォーマンス改善

あんまり詳しく考えてないですが、C に近づいていくのかなあ。

<!--
v2 は初心者（＝自分）向け、ライフゲーム専用という設定なので割と禁欲的な仕様にしていたのですが、
rui さんの 8cc/9cc/chibicc のソースはまだ読んでいないのですが、このあたりまで作ったら答え合わせ的に読もうと思っています。


v3 ではその縛りをなくしてあれこれ追加していこうかなと。

v1, v2 では初心者向け教材っぽくしたい（想定読者＝どうやってコンパイラを作ればいいのか分からなかった頃の自分）という考えがあり「なるべくベタな仕様・見た目にしたい」「高度な機能や独自色をなるべく入れない」という考えがあったのですが、v3 ではその縛りは外してしまってもいいかなと思っています。
-->

v1, v2 では初心者向け教材っぽくしたくて（想定読者＝どうやってコンパイラを作ればいいのか分からなかった頃の自分）「なるべくベタな仕様・見た目にしたい」「高度な機能や独自色をなるべく入れない」という気持ちがあったのですが、v3 ではその縛りは外してしまってもいいかなと思っています。

---

というわけで本体は以上で終わりです。以下、苦労話や枝葉な部分のメモです。




# 苦労話

## 遅い

lexer, parser, codegen を全部コンパイルすると現状では 15分くらいかかります（第2世代コンパイラが育つに連れて伸びていき、最終的にこのくらい）。
ふつうに辛いのですが、終盤ではゴールが近いと分かっていたので下手にジタバタせず逃げ切りました。特に対策せず、実行して待ってる間に部屋の掃除、実行して部屋の掃除、を繰り返していました。部屋がちょっときれいになりました。

※ 「TODO」の節で書いたようにこれから速くしていく予定です


## 配列の範囲外アクセス

プログラムが大きくなってくるとアセンブリや機械語やメモリのダンプを見てもさっぱり分からん……ので `git reset --hard` して歩幅を小さくしてやり直して、という対処で8割くらいはなんとかなった気がします。残りの2割はがんばってなんとか。gdb とか便利なものがないのでここはちょっと辛いですね。

ただ、長くても数時間くらいでなんとかなるレベルで、バグの原因が判明するまで何日もかかるということはありませんでした。
なるべく複雑なことをしないように作っていたのが良かったかもしれません。


## エラー発生時にスタックトレースが見れない

print デバッグなどでがんばる……。

ある関数で配列の範囲外アクセスが原因と思われるエラーが発生し、おそらく呼び出し元で範囲指定をミスしており、そして呼び出し元がたくさんあり、まず呼び出し元の特定が必要……のようなパターン。

セルフホスト達成後に試したところ、VM などにちょいと細工をするだけでスタックトレースを見られるようにできました。若干チート感がありますが、これはさっさとやっておけばよかったかも。


## 関数呼び出し時の引数の個数のまちがい

これは結構鬱陶しくて、よく間違えるのと、個数が違うのが原因だと分かりにくく不毛だったため、さすがに対策しました。
構文木の段階で関数の定義と呼び出しを突き合わせてチェックする数十行程度のスクリプトを、これは補助ツールだから……と言い訳しつつ Ruby で書き、パース処理とコード生成処理の間に挟みました。
すごく原始的な静的解析でしょうか。


# おまけ・細かい話

v2 から v3 への変更のうち、セルフホストにはそんなに関係ない部分、その他。

## 文頭の set, call, call_set を廃止

v2 では文頭に `set`, `call`, `call_set` を明示的に書く方式にしていましたが、これを不要にしました。ある程度量を書くとなると、やはり鬱陶しいので。これは割と小さめの修正でOK。

```diff
-set a = 123;
+a = 123;

-call foo_func();
+foo_func();

-call_set a = foo_func();
+a = foo_func();
```

----
関数の引数として任意の式を書けるようにし、また、関数呼び出しを式として扱うようにしました。これにより、たとえば次のように関数呼び出しを関数の引数として書けるようになります。

```ruby
foo_func(bar_func());
```

だいぶ普通の言語っぽくなりました。



## case 文の else

v2 には else がなく

```ruby
case
when ...
  # ...
when (0 == 0) # else の代わり
  # ...
end
```

のように書いていたところを、次のように else で書けるようにしました。

```ruby
case
when ...
  # ...
else
  # ...
end
```

## if 文

case文があれば if文はなくていいかなと思っていたのですが

- あればあったでちょっと書きやすい
- 少しの手間（数行の変更）で実現できそう

ということで書けるようにしました。

レキサで処理しています。`if` が来たら `case` `when` の2つのトークンに変換するだけ。

```ruby
if ( ... ) ... end
↓ 変換
case when ( ... ) ... end
```

これだけで `else` 節のある if文も書けるようになります。

```ruby
if ( ... )
  # ...
else
  # ...
end

↓ 変換

case when ( ... )
  # ...
else
  # ...
end
```

## Ruby っぽい見た目に変更

すでにここまで貼ったコード片で見てきた通りで、 Ruby っぽい見た目に変えてみました。見た目は Ruby っぽいけど中身は C っぽい、ちょっと不思議な書き味です。

これはなんとなくできそうだったので、試してみて、なんとなくこうなったというものです。
v2 とのギャップを小さくするために JavaScript っぽい構文に戻そうかなとも考えていましたが、元に戻すのが億劫になるところまで進めてしまって、めんどくさくなって結局そのままという。

アドレス演算子、デリファレンス演算子があるため Ruby と文法コンパチにはなっていないと思います。

<!--
Ruby コンパチにできないかなーと考えてはいたのですが、アドレス演算子、デリファレンス演算子が入ってきたので諦めました。
-->


# ポインタ変数

コードの見た目だけでは通常の変数なのかアドレスが入ってる変数なのか、使用箇所を見ても宣言を見ても分かりません。

```ruby
var a; # 普通の整数が入る
var b; # アドレスが入る
```

そこで、見た目で瞬時に判別できるように、アドレスが入っている変数には末尾に `_` を付けています。

```ruby
def foo(
  arg1, # 普通の変数
  arg2_ # アドレスが入っている
)
  # ...
end

foo(
  a, # 普通の整数を渡している
  b_ # アドレスを渡している
);
```

-----

というわけでおまけコーナーは以上です。また何か思い出したら追記するかもしれません。