30 億のデバイスで走る絵文字プログラミング言語 emojin

年の瀬ですね．2024 年も残すところあと 10 日，卒論に追われている方も多いのではないのでしょうか．御多分に洩れず，私も追われまくっているところです．

アドカレといえばおもしろ開発です．今年もおもしろ開発をしたので，その報告です．卒論執筆，あるいはレポート，小テスト，労働，風呂，移動等々の片手間にぜひお読みください．

:::note info
この記事は [mast Advent Calendar 2024 - Adventar](https://adventar.org/calendars/10425) の 21 日目の記事です．20 日目の記事は[筑波大学から逃げるな](https://x.com/Nohananonano)さんによる[パチスロは合法です。｜わらびもっちもち](https://note.com/watabimottimoti/n/na0d2f47e6339)でした．パチスロしたことないので，いつかはしてみたいですね．
:::

# TL;DR
emojin が Java（クラスファイル）へのコンパイルへ一部対応しました！
https://emojin.itsu.dev で遊べます．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/237903/d4a748b2-0c3c-c933-6914-e6036b938663.png)

コンパイルできそうなコードを入力し，「Java コンパイル」ボタンを押下して得られたファイルを，次のコマンドを用いて実行できます[^21] :tada: 

```sh
java -noverify EmojinMain
```


# はじめに

さて，今年の 6 月末に絵文字プログラミング言語 emojin を公開しました．下は当時のツイートです（https://emojin.itsu.dev で遊べます！）．

https://x.com/chururi_/status/1805841996982173833

emojin はチャーミングでとても面白いプログラミング言語ですが，一つ重大な欠点があります．それは **emojin Playground でしか動作しない**ということです．これではただのお遊び言語にとどまってしまい，全く実用性のない言語となってしまいます（まあお遊びですが）．しかしお遊びに全力で取り組めるのは，このアドカレの時期しかありません．せっかくの機会ですので，このお遊び言語を少しでも実用的にしてみようと思います．

## どのように実用的にするか？

はじめに，どのようにして emojin を実用的にするかを考えてみます．言語の実用性は，例えば次のようなポイントで評価できることでしょう．

- プログラムの記述量と表現力とのバランスが取れていること
- 標準ライブラリが充実していること
- 同じプログラムが様々なプラットフォーム上で動作すること

それぞれ検討してみます．
- **プログラムの記述量と表現力とのバランスが取れていること**
    - 行いたい表現をするために必要なプログラムの記述量が，それ相応のものであるかどうかということ
    - emojin が絵文字でプログラミングを行うというコンセプトが根幹にある言語である以上，捨てざるを得ない
- **標準ライブラリが充実していること**
    - 基本的に，各種制御構文や式ができるだけの言語は使い道があまりなく，そこにネットワーク操作やファイルの入出力などの機能が統合されて，初めて実用的になるということ
    - そもそも emojin に関数の概念がないので，標準ライブラリの導入の余地がない[^4]
- **同じプログラムが様々なプラットフォーム上で動作すること**
    - そのまま
    - emojin Playground を超えて emojin が何らかのプラットフォームの上で動作できるようになれば，このポイントを満たすことができそう．また最初に挙げた問題についても，この方針で進めていけば解決が図れそう

ということで，「**同じプログラムが様々なプラットフォーム上で動作すること**」を満たす方針で進めていきたいと思います．幸いなことに，多くの言語はマルチプラットフォーム化が進んでいます．JavaScript は一部の機能を除いて様々な Web ブラウザの上で動作しますし，WebAssembly も同様[^2]です．古くから人気の Java も **Write Once, Run Anywhere** を昔から掲げ，様々なデバイスにインストールされた JVM の上で共通の Java プログラム[^1]が動作します．

今回は，emojin を 30 億のデバイスで走らせたいので，**Java へのコンパイル[^3]を目標**に emojin の Java コンパイラを実装していくことにします[^8]．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/237903/47c8ce53-5532-aa22-9cd7-3e7d7151a359.png)
（[JDK 8セットアップ - ソフトウェアエンジニアリング - Torutk](https://www.torutk.com/projects/swe/wiki/JDK_8%E3%82%BB%E3%83%83%E3%83%88%E3%82%A2%E3%83%83%E3%83%97) より画像をお借りしました．）

## 周辺技術について
ここから早速設計！実装！の話に移ってもいいのですが，この記事は**誰一人取り残されない、人に優しい記事**[^5]をミッションに掲げています．そのため，少しだけ周辺の話をします．

### Java
ﾊﾟﾌﾞﾘｯｸｽﾀﾃｨｯｸｳﾞｫｲﾄﾞﾒｲﾝ[^10] や `System.out.println` で有名なアイツです．多くの場合[^6]，人々が書いた Java プログラムは，一度 **Java クラスファイル**と呼ばれる中間コード（IR）に変換され，それを **JVM（Java Virtual Machine）** と呼ばれる実行機械（仮想マシン）に入力することで実行がなされます．Java を使ったことがある方ならお分かりだと思いますが，`javac` コマンドが前者，`java` コマンドが後者の操作にあたります．

**Java クラスファイル**はバイナリファイルであるため，訓練された人間[^9][^11]でない限り読むことはできません．一方で，Java クラスファイルは Java のマルチプラットフォーム性を担保するために重要な役割を果たしています．このファイル形式はプラットフォームに依存しない形式です．従って，この Java クラスファイルを解釈できるソフトウェアが動作する環境であれば，どこでも Java を実行可能になるわけです．

また **Java でない言語から Java クラスファイルにコンパイルすることができれば，その言語も 30 億のデバイスで動く言語に**なります．Kotlin[^7] や Scala はその際たる例で，このような形で Java のエコシステムに乗っかることでその地位を確立しました．emojin もこの Big Wave に乗っていきます．

### コンパイラ
コンパイラとは，プログラミング言語で書かれたソースコードを、（コンピュータが実行できる）低レベル言語に変換するソフトウェアのことを指します．ここで言う低レベルとは，より機械語に近い，あるいは人間に優しくないといったニュアンスです．

一般的なコンパイラでは，次のような処理がこの順序で走ります．

- 字句解析：入力プログラムをトークンごとに区切り，識別していく
- 構文解析：トークンの流れから構文を割り出す
- 意味解析：構文がどのような意味であるかを解析する
- 中間表現生成：最適化やコード生成を行う前段階として，内部で扱いやすい形式に変換する
- （最適化：不要なコードを削除するなど，入力プログラムの改善を行う）
- コード生成：出力となる機械語やプログラムを生成する

このうち，字句解析〜意味解析の段階をコンパイラにおける**フロントエンド**，中間表現生成〜コード生成をコンパイラにおける**バックエンド**と呼びます．

# 設計と Java クラスファイルの理解
先にお断りをしておきます．卒論が大炎上であまりにも時間がありません．そのため，今回は **50 回 Hello と表示できればよし**とします．参考までに，emojin での FizzBuzz は次の通りです（ここでは emojin の言語仕様については立ち入りません．構文については https://emojin.itsu.dev のヘルプをご参照ください）．

```emojin:50 回のくどい挨拶をする例（emojin）
♻️❤️🌀0️⃣➰5️⃣0️⃣🔜
  📢💬Hello💬⛔️
🔚
```

現状の emojin は意味解析までが実装されており[^13]，その結果が内部的に木（Tree）のデータ構造で表現されています（ある意味ではこの木が中間表現でもある）．そしてこの木を辿っていくことにより emojin の実行が行われています[^12]．今回は，意味解析以降をこれから実装するコンパイラに接続することで Java のコンパイラを実装していくこととします．即ち，現状フロントエンド部分は実装済みのため，バックエンド部分（とりわけ**コード生成**部分）を実装していく形になります．

## Java クラスファイル
さて，コンパイル後の出力結果が正しく実行できるようになっているためには，その結果が正しいフォーマットとなっている必要があります．**Java クラスファイル**はJavaの実行可能形式であり，一般的な Java コンパイラはこの形式への出力を目指してコンパイルをしていきます．

Java クラスファイルの形式は[仕様](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html)によって明確に定められています（今回は **Java8** の仕様に則ってコンパイルをしていきます）．次のコードは，Java クラスファイルに含まれるデータの内容を C ライクな構造体で表したものです．基本的には `型名 データ名` で表され，例えば型名である `u4` は `unsigned` な 4 バイトの整数，即ち**符号なし 32 ビット整数**を表します．Rust などでは `u32` ですね．

```c:Java クラスファイルの構造
ClassFile {
    u4             magic;  // マジック
    u2             minor_version;  // マイナーバージョン
    u2             major_version;  // メジャーバージョン
    u2             constant_pool_count;  // 定数プール長
    cp_info        constant_pool[constant_p ol_count-1];  // 定数プール
    u2             access_flags;  // アクセスフラグ
    u2             this_class;  // this で参照されるクラス（への定数プー ルへのインデックス）
    u2             super_class;  // super で参照される親クラス（への定数プールへのインデックス）
    u2             interfaces_count;  // 実装インタフェースの数
    u2             interfaces[interfaces_count];  // 各インタフェース（への定数プールへのインデックス）
    u2             fields_count;  // クラスに含まれるフィールドの数
    field_info     fields[fields_count];  // 各フィールド（への定数プールへのインデックス）
    u2             methods_count;  // クラスに含まれるメソッドの数
    method_info    methods[methods_count];  // 各メソッド（への定数プールへのインデックス）
    u2             attributes_count;  // 属性の数
    attribute_info attributes[attributes_count];  // 属性
}
```

これらの値を過不足なく設定し，直列化することで Java クラスファイルが得られます．特に今回で必要な部分について簡単に述べます．

- `magic`：Java クラスファイルであることを識別するための値．`0xCAFEBABE (= 3405691582)` で固定
- `minor_version`：マイナーバージョン．基本的に 0 でよい
- `major_version`：コンパイルされた Java 仕様のメジャーバージョン．Java8 なら `52`．他の値は [List of Java class file format major version numbers? - Stack Overflow](https://stackoverflow.com/questions/9170832/list-of-java-class-file-format-major-version-numbers) に記述がある
- `constant_pool_count`：定数プール（後述）の要素数
- `constant_pool`：定数プール（後述）
- `methods_count`：このクラスで定義されたメソッドの数
- `methods`：メソッドデータ

### 定数プール
面倒なので Claude 3.5 Sonnet 君に説明を書かせました．

クラスファイルの定数プールは、Javaクラスファイル内で使用される情報（文字列、数値、クラス名、メソッド名、フィールド名など）を格納するテーブルです。


**具体的に格納される情報**
- リテラル値
  - 文字列定数
  - 数値定数
  - その他のプリミティブ型定数
- シンボリック参照
  - クラスとインターフェースの名前
  - フィールドの名前と型
  - メソッドの名前、引数、戻り値の型

**主な特徴**
- 各エントリには 1 から始まるインデックスが割り当てられる
- 重複する情報は 1 つのエントリにまとめられる
- エントリ同士が相互に参照可能
- クラスファイルのロード時やリンク時に使用される

定数プールは、クラスファイルのサイズを小さくし、実行時のメモリ使用を効率化する重要な役割を果たしています。

### メソッドデータ
メソッドデータには，`method` 構造体の配列が生起します．`method` 構造体は次のような構造です（[Chapter 4. The class File Format](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.6) より引用）．

```c:method 構造体
method_info {
    u2             access_flags;
    u2             name_index;
    u2             descriptor_index;
    u2             attributes_count;
    attribute_info attributes[attributes_count];
}
```

ここで `name_index` にはメソッド名の定数プールのエントリへのインデックスが，`descriptor_index` にはディスクリプタ（メソッドのシグネチャ：引数と戻り値の型情報を文字列で表したもの）へのインデックスが入ります．例えば Java のメイン・メソッドである `public static void main(String args[])` であれば，それぞれ `main`，`([Ljava/lang/String;)V` です．

実際の Java コードは [Chapter 6. The Java Virtual Machine Instruction Set](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html) によって定められる**一次元的な JVM 命令のストリーム**へと変換され，`CodeAttribute` として `attributes` に生起します．

### CodeAttribute
**Attribute とは Java クラスファイルや各データに付随する属性**で，メタデータです．Attribute には様々な種類がありますが，本稿においてはとりわけ `CodeAttribute` が重要です．`CodeAttribute` には Java コードをコンパイルした際の命令やローカル変数の数，最大スタック長などが入ります．次のコードは [Chapter 4. The class File Format](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.7.3) からの引用で，`CodeAttribute` 構造体です．

```c:CodeAttribute 構造体
Code_attribute {
    u2 attribute_name_index;
    u4 attribute_length;
    u2 max_stack;  // 最大スタック長
    u2 max_locals;  // 最大ローカル変数スタックの数
    u4 code_length;  // （コンパイル済みの）JVM 命令長
    u1 code[code_length];  // JVM 命令
    u2 exception_table_length;  // 例外テーブル（使用しない）
    {   u2 start_pc;
        u2 end_pc;
        u2 handler_pc;
        u2 catch_type;
    } exception_table[exception_table_length];
    u2 attributes_count;
    attribute_info attributes[attributes_count];
}
```

## 実装の方針

ここまでで Java クラスファイルの構造についてさらっと述べました．これだけでもざっくりとしたコンパイル方針が見えてきます．おおよそですが，「**emojin のプログラムをコンパイルして CodeAttribute へ突っ込み，それを `main` メソッドの構造体の中に入れつつ必要な値を定数プールへ格納する**」でしょうか．

# 実装
何はともあれ，ここまで焦らしすぎました．やっていきます．

## （ローカル）変数の取り扱い
今回，変数宣言・代入文はコンパイル対象としませんが，後述する For 文などで変数が出現します．多くのプログラミング言語での変数スコープ[^16]は，**ブロックスコープ**と呼ばれるような，ブロック内でのみ有効なスコープを持ちます．例えば JavaScript での `let` や `const` 宣言によるスコープです．このような場合の処理系の変数管理の一実装方式として，**ローカル変数スタック[^15]** を利用する方法があります．Java の変数もブロックスコープが採用されているため，おそらくこの方法が有効でしょう．

一方の私にはそんな時間はなく，できるだけ実装時間を短くしたいです．そのため，今回のコンパイラ実装において，全ての変数は**関数スコープ**を持つこととします．これは一つの変数が関数内全てで有効であるスコープであり，例えば JavaScript において `var` 宣言された変数や，Python における変数が該当します．この場合，**一次元配列で管理できます**．

JVM において，ローカル変数は `n 番目` のようなインデックスにて参照されます．例えば `int` 型の変数の値を読み出すには `iload`命令を，格納には `istore` 命令を使用し，オペランド（命令の引数）に対象のインデックスが生起します（0-4 番目の変数はよく使用されるため，オペランドを持たない専用の命令 `iload0` や `istore3` などがあります）．従って，**変数の参照に変数の名前は必要なく**，名前からインデックスを割り出す処理を書く必要が生じます[^17]．

emojin は TypeScript で実装しており，また先ほど，変数を**一次元配列**で管理することにしました．今回は，**新しい変数が出るたびに配列に変数名を追加し，解決時にインデックスを算出する**ナイーブな実装を行います．次のコードに実装例を示します．

```ts
const variables: string[] = [];

const newVariable = (name: string): number => {
    variables.push(name);
    return variables.length - 1;
}

const getVariable = (name: string): number => {
    return variables.find((n) => n === name);
}
```

また，変数名から変数読み出し命令・格納命令を生成する処理も必要です．今回は簡単のため，`int` 型変数のみを取り扱います．これらの操作は上述のように `iload` `istore` 命令が利用されますが，インデックスによる命令の種類を変えたり，適切にオペランドを設定する処理も必要です．次にその実装を示します（[仕様](https://docs.oracle.com/javase/specs/jvms/se17/html/jvms-6.html#jvms-6.5.iload)）[^19]．

```ts
const getILoadInstruction = (name: string): number[] => {
    const i = getVariable(name);
    const index = i !== -1 ? i : newVariable(name);

    switch (index) {
        case 0:
            return [Inst.ILoad0];
        case 1:
            return [Inst.ILoad1];
        case 2:
            return [Inst.ILoad2];
        case 3:
            return [Inst.ILoad3];
        case 4:
            return [Inst.ILoad4];
        default:
            return [Inst.ILoad, index];
        }
}

const getIStoreInstruction = (name: string): number[] => {
    // getILoadInstruction と同様なので省略
}
```

さて，先ほどemojin コードを `main` メソッドの中身としてコンパイルする方針を述べました．その都合上，`main` メソッドの引数も考慮しなければなりません（Java においては，メソッドの引数はローカル変数として扱われます）．従って，**コンパイル処理の初めに emojin からは参照できない変数を一つだけ追加しておく**ことにします．

## For 文のコンパイル
次の emojin コードは，❤️ の値をまず 0 で初期化し，値を 1 ずつ増やしていきながらその値が 49 になるまで 処理 を繰り返すものです．まずはこのコンパイルをしていきます．

```emojin:For 文
♻️❤️🌀0️⃣➰5️⃣0️⃣🔜
  🪧 処理(ここはコメント)
🔚
```

この処理をもう少し噛み砕いてみます．おおよそ次のようになりそうです．

1. 変数 ❤️ へ 0 を格納する
2. 変数 ❤️ の値が 50 以上の場合，ブロックを飛ばして 6. へ移る
3. ブロック内の処理を行う
4. 変数 ❤️ の値を 1 増やす
5. 2. へジャンプ
6. 後続の処理

順を追ってそれぞれを JVM 命令へハンドコンパイル[^14]してみます．

### 変数 ❤️ へ 0 を格納する
変数への格納は `istore` 命令で行われます，この命令はスタック先頭の値を指定された変数へ格納する命令ですので，格納に先立って 0 をスタックへ積む必要があります．この操作は `iconst0` 命令で行われるので，変数の節で示した関数を用いて次のようにコンパイルできます．

```ts
[IConst0, ...getIStoreInstruction("❤️")]
```

### 変数 ❤️ の値が 50 以上の場合，ブロックを飛ばして 6. へ移る
**〜以上という動作を行うには，`if_icmpge` 命令**が利用できます．これはスタックの値 `..., value1, value2` について，`value1 ≥ value2` を満たす場合にプログラムカウンタにオペランド `offset` の値を追加してジャンプする命令です．今回，`value1` には変数 ❤️ の値，`value2` には 50 が該当するので，次のようにコンパイルできます．

```ts
[...getILoadInstruction("❤️"), 50, Inst.IfICmpGE, ??]
```

後続の処理のために，**ここでコンパイルした結果の `iload` 命令の全体の JVM 命令列における位置を `loopStart` として記録**しておきます．

ここで問題が生じます．`offset` には何の値を入れればいいのでしょうか．現時点では後続の処理が確定していないため，`offset` に該当する命令長がわかりません．そんなあなたに**バックパッチ**です．次の節でこれについて述べます．

### バックパッチ
バックパッチとは，**あらかじめ不明なオフセット値にプレースホルダとなる値を入れておいて，後続の処理が確定した時に後で戻ってきてそこの値を埋める手法**です．先の状況では，`Inst.IfICmpGE` を追加した後にオフセットにプレースホルダを設定し，`for` 文の中をコンパイルしてから戻ってくれば良いわけです．そのためには `Inst.IfICmpGE` 命令の位置を記憶しておく必要があります．

Java クラスファイルは，全体として `u8` = 符号なし 1 バイト整数のストリームとしてバイナリが構成されます．従って，`u8` は `0-255` までの値しかとらないため，例えば **`99999` のような数値が JVM 命令を管理する配列に生起することはありません**．そのため，**このような値がプレースホルダに適している**と言えるでしょう．

ここでは実装方針のみにとどめ，実装手法は疲れたので省略します．

### 変数 ❤️ の値を 1 増やす
この操作には `iinc` 命令（[仕様](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.iinc)）が利用できます．この命令は `index`（ローカル変数スタックのインデックス）と `const`（定数）の 2 つのオペランド[^20]をとり，`index` の指す変数に `const` ぶんの値を加算します．これは次のようにコンパイルできます．

```ts
[Inst.IInc, getVariable("❤️"), 1]
```

### ジャンプ
ジャンプには `goto` 命令（[仕様](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.goto)）が使用されます．オペランドには 2 つの数値をとり，この数値から `offset = (offset1 << 8) | offset2` が計算されます．なお，現在位置より前の位置にジャンプしたい場合には，`offset` に 65536 を足した値を指定します．

今回はジャンプによってインデックス変数の比較部分に移りたいので，`c` を `goto` 命令の位置として `offset = loopStart - c + 65536` を指定します．`loopStart` は先の「変数 ❤️ の値が 50 以上の場合，ブロックを飛ばして 6. へ移る」で保存しておいた値です．

```ts
[Inst.Goto, offset >> 8, offset & 0xff]
```

## Print 文のコンパイル
`System.out.println` の呼び出しは，次のようにコンパイルされます（`#n` の部分はオペランドであり，定数プールへのインデックスです）．

```
getstatic     #13                 // Field java/lang/System.out:Ljava/io/PrintStream;
ldc           #15                 // String Hello
invokevirtual #21                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
```

`getstatic` 命令によって `System.out` 変数の参照をスタックに積み，定数プールから文字列 `Hello` を取り出してスタックに積み，最後 `invokevirtual` 命令によって `println` メソッドを呼び出します．

基本的な方針は示しましたが，時間がなさすぎるので要望があれば追記します......

# 終わりに
この文字数を卒論に費やしたかった．

[^1]: 厳密には Java クラスファイル．
[^2]: 厳密には言語ではないが，Wasm バイナリが共通なので...
[^3]: 「Java クラスファイルへのコンパイル」が正しいが，簡単のためこの表現をしている．
[^4]: 関数の概念を追加しても良かったが，そこまで面白くはないので却下した．
[^5]: https://www.digital.go.jp/about/organization
[^6]: GraalVM 等の AoT コンパイラに配慮した．時代は多様性．
[^7]: Kotlin は Java 以外にも JS や Wasm，そして各 OS のネイティブなどにもコンパイル可能であり，化け物級のマルチプラットフォーム性を持っている．すごい．
[^8]: JavaScript へのトランスパイラを作っても楽しそうだったが，[最近似たようなこと](https://github.com/itsu-dev/vue2-vue3-transpiler)をしたので却下した．
[^9]: 私は読めます．
[^10]: 最近無くてもよくなった．詳細：[JEP 445: Unnamed Classes and Instance Main Methods (Preview)](https://openjdk.org/jeps/445)
[^11]: [Chapter 4. The class File Format](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html) を読むと訓練できる．
[^12]: いわゆる Tree Walker 方式のインタプリタ．
[^13]: ちなみに構文解析アルゴリズムは LL で実装されている．
[^14]: 頭で考えてコンパイルしてみること．
[^15]: この方式では，ブロックに入るたびに変数表をスタックに積み，変数を解決する際にスタックの先頭から底に向かって探索していく．
[^16]: 雑に言えば，変数を使用できる範囲のこと．
[^17]: Java クラスファイルにすら変数の名前が書き込まれないことがあるが，[LocalVariableTableAttribute](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.7.13) として変数の名前等を保持する属性が作成され `CodeAttribute` の属性として書き込まれることもある．
[^19]: `iload` `istore` 命令のオペランドには 1 バイトしか取れないので，256 個以上の変数が利用できないというエッジケースがあるが，本来の Java コンパイラでは `wide` 命令を使用することで回避されている．ここでは省略．
[^20]: これも 1 バイトのオペランドしか扱えないので，256 以上のインデックスの変数を利用する場合には `wide` 命令が使用される．また定数が 256 以上になる場合には，`iconst` + `istore` の 2 つの命令が使用される．ここではともに実装を省略．
[^21]: ジャンプ命令に必要なメタデータを出力していないので，普通の実行だと Java クラスファイルの検証段階で落ちてしまう．そのため `-noverify` オプションをつけて回避している．