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

Last updated at 2024-12-24Posted at 2024-12-21

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

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

この記事は mast Advent Calendar 2024 - Adventar の 21 日目の記事です．20 日目の記事は筑波大学から逃げるなさんによるパチスロは合法です。｜わらびもっちもちでした．パチスロしたことないので，いつかはしてみたいですね．

TL;DR

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

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

java -noverify EmojinMain

はじめに

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

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

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

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

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

それぞれ検討してみます．

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

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

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

（JDK 8セットアップ - ソフトウェアエンジニアリング - Torutk より画像をお借りしました．）

周辺技術について

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

Java

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

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

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

コンパイラ

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

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

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

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

設計と Java クラスファイルの理解

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

50 回のくどい挨拶をする例（emojin）

♻️❤️🌀0️⃣➰5️⃣0️⃣🔜
  📢💬Hello💬⛔️
🔚

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

Java クラスファイル

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

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

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 に記述がある
constant_pool_count：定数プール（後述）の要素数
constant_pool：定数プール（後述）
methods_count：このクラスで定義されたメソッドの数
methods：メソッドデータ

定数プール

面倒なので Claude 3.5 Sonnet 君に説明を書かせました．

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

具体的に格納される情報

リテラル値
- 文字列定数
- 数値定数
- その他のプリミティブ型定数
シンボリック参照
- クラスとインターフェースの名前
- フィールドの名前と型
- メソッドの名前、引数、戻り値の型

主な特徴

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

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

メソッドデータ

メソッドデータには，method 構造体の配列が生起します．method 構造体は次のような構造です（Chapter 4. The class File Format より引用）．

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 によって定められる一次元的な JVM 命令のストリームへと変換され，CodeAttribute として attributes に生起します．

CodeAttribute

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

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 文などで変数が出現します．多くのプログラミング言語での変数スコープ¹⁵は，ブロックスコープと呼ばれるような，ブロック内でのみ有効なスコープを持ちます．例えば JavaScript での let や const 宣言によるスコープです．このような場合の処理系の変数管理の一実装方式として，ローカル変数スタック¹⁶ を利用する方法があります．Java の変数もブロックスコープが採用されているため，おそらくこの方法が有効でしょう．

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

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

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

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 命令が利用されますが，インデックスによる命令の種類を変えたり，適切にオペランドを設定する処理も必要です．次にその実装を示します（仕様）¹⁸．

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 になるまで処理を繰り返すものです．まずはこのコンパイルをしていきます．

For 文

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

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

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

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

変数 ❤️ へ 0 を格納する

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

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

変数 ❤️ の値が 50 以上の場合，ブロックを飛ばして 6. へ移る

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

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

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

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

バックパッチ

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

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

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

変数 ❤️ の値を 1 増やす

この操作には iinc 命令（仕様）が利用できます．この命令は index（ローカル変数スタックのインデックス）と const（定数）の 2 つのオペランド²⁰をとり，index の指す変数に const ぶんの値を加算します．これは次のようにコンパイルできます．

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

ジャンプ

ジャンプには goto 命令（仕様）が使用されます．オペランドには 2 つの数値をとり，この数値から offset = (offset1 << 8) | offset2 が計算されます．なお，現在位置より前の位置にジャンプしたい場合には，offset に 65536 を足した値を指定します．

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

[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 メソッドを呼び出します．

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

終わりに

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

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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up