More than 1 year has passed since last update.

言語実装Advent Calendar 2022

@Kray-G

Kinx から Kilite へ

Last updated at 2022-12-20Posted at 2022-12-20

おひさしぶりでございます

お気づきのように、毎年12月21日を狙って投稿してます。

本稿は言語実装アドベントカレンダー 2022 の 21 日目の記事です。
- https://qiita.com/advent-calendar/2022/lang_dev

おさらい

さて、ずっと Kinx という自作言語について記事を書いてきていたわけですが、ここ 1 年ほどほとんど活動しておりませんでした。理由は本業が忙しかったからなのですが、なんといっても、2 回くらい仕事が変わりました。今はコーディングとは全く縁もゆかりもない、なんだったら ビジネスを企画する、といった企画系のお仕事をしております。ほとんどプログラムを書くことがないですな。

本題に入る前に、Kinx についておさらいしておきましょう。また、今回のネタにつながる記事もあります。

手に馴染む道具(プログラミング言語) ... 2020年02月05日
- ここから始まりました。
- 【要約】職人らしく、「手に馴染む言語」が欲しいのだ。
スクリプト言語 KINX（ご紹介） ... 2020年02月21日
- 実行に移したのだ。
- 「見た目は JavaScript、頭脳(中身)は Ruby、安定感は AC/DC」 がコンセプト。
- 地道な記事投稿でかなり充実した感じに。各種記事はこのページから飛んでみてくださいませ。
Kinx 基礎文法最速マスター ... 2020年12月21日
- 一昨年のアドベントカレンダー記事。
- 基礎文法最速マスターシリーズ。
Kinx での JIT、そして MIR の話 ... Ruby だけでは勿体ないネ ... 2020年12月21日
- 一昨年のアドベントカレンダー記事。
- 一昨年は気張って 2 本書いた。頑張ってたな。
- ここで触れている MIR が今回のネタにつながります。
- MIR については、記事をお読みください...、ではアレなので、↓コレです。
  - https://github.com/vnmakarov/mir
Kinx Update 2021（パッケージ管理サポートなど） ... 2021年12月21日
- 昨年のアドベントカレンダー記事。
- はい、今年(2022年度)の目標は未達です。
- ただ、スターは若干増えて、今 227 になりました。ありがたいことです。

この後、活動がピタッと止まりました。昨年のアドベントカレンダー記事でも触れてますが、当時の本業で激震が走り、それが続いて今に至るという。まあ、今の仕事楽しいので、悪くはない。

本題

さて、本業では全くプログラミングしない生活ですが、ここにきて一部コーディングはじめました。というのも、MIR 使ったプロジェクト立ち上げよう、と思い立ったからです。

名前は Kilite 。Kinx Lite です。リポジトリは以下。いつものように気軽に★を押していただけますよう、よろしくお願いいたします。

https://github.com/Kray-G/kilite

ええ、ロゴも作りましたよ。特に意識はせずに全くのゼロベースでデザインしたのですが、作った後、「あれ？つーか N〇KE のロゴに似てねえ？」と一瞬思ったり。思ったのだが、違ったのでよし。コンセプトは Kinx と一緒です。というより、Kinx を引き継いで、こちらでパワーアップさせたい、という願望が芽生えています。

さて、今回はこの Kilite、特長とか、イマイマ時点でのステータスなんかをご報告しよう、というわけです。MIR との関係とか。

Kilite

特長、目標

Kinx よりもっと C とうまくやれますように。
- C 言語出力したらそのままコンパイルして実行形式を作るのも可能にする。
- C 言語からの呼び出し、ネイティブ関数からの呼び出しももっと便利に。
- Lua でも目指してみるか。
Kinx より速く動きますように。
- バイトコード VM 方式の限界が見えてきたので、ブレークスルーが欲しい。
- なんだかんだ言って、速くないとイマイチ感が漂う。
もう少しコンパクトになりますように。
- ソースコードベースがだいぶ汚くなって来ていた。
- 最初に dll で拡張する設計にしたので、それも複雑さの要因。
- WASM にも対応できると良いな。（dll だとできないっぽい）

最終的には、KiTTy 相当の組版システムをよりシンプルに作ってみるところを今の目標にしてみる予定。

KiTTy - Kinx Tiny Typesetting
- かなりきれいに組版できるのだが、実行速度が遅い。
  - PDF ... こんな感じの PDF が作れます。
- また、ソースコードもイマイチ。Kinx は全てソースを一度にロードしないといけなかったので。
  - 次は別の設計にしよう...。
- これを改善したい。

今こんな感じ

今回のアイデアをやってみて、今までになかったメリットにもいろいろ気づいた。

ネイティブ関数とスクリプト関数のつながりがシームレス。全て C 関数に置き換わって実行されるので、今まで VM ➡ Native実装部分 ➡ VM みたいな入れ子関係が問題だったのだが、想像以上に格段にシームレス。
速い。何だったら C コンパイルしてしまえば、luajit とか PyPy とかよりも速い。
それでいて、多倍長整数(BigInteger) や正規表現、XML なんかも普通に使えるので、C で多倍長整数や正規表現など 便利機能が簡単に使える。

参考までに、Windows 上での結果ですが fib(38) での速さの比較を載せておきましょう。ソースコードや詳細は、README.md をご参照ください。つか、gcc -O3 が速いな。

	Version	Time	Result	Remark
C (-O3)	gcc 8.1.0	0.14s	39088169	Simple C code.
Kilite(C compiled)	(beta/gcc MinGW 8.1.0)	0.17s	39088169	Compiled the output from Kilite.
C (-O2)	VS2019	0.18s	39088169	Simple C code.
Kilite(C compiled)	(beta/cl VS2019)	0.22s	39088169	Compiled the output from Kilite.
luajit	2.1.0-beta3	0.35s	39088169	-
PyPy	7.3.9	0.40s	39088169	-
Kinx(native)	1.1.1	0.57s	39088169	-
Kilite	(beta)	0.68s	39088169	-
Lua	5.4.4	2.59s	39088169	-
Ruby	3.1.2p20	4.02s	39088169	-
Kinx	1.1.1	5.18s	39088169	-
Python	3.11.0	5.94s	39088169	-

作ってきた流れ

基本

まず、目標性能が出せそうかどうかをトライアル。

C コードを出力して MIR に処理させるので、どんな感じの出力にすると良いか出力イメージを手書きで色々試してみて、何となく行けそうな感触をつかむ。この辺だけで 1 ～ 2 日かかったが、ここがうまくいかないとやる意味ないしね。

で、何となく行けそう、となった時点でレキサーとパーサーを書き始める。今回は Yacc は使わず、手書きの再帰下降パーサーで実装。色々と自由がきくので。あと、Yacc を使ってもあまり実装量が変わらないなー、というのもあり、コードベースをシンプルにするのにも良いかもしれないと思ったので。

字句・構文解析 ➡ AST ➡ 内部表現(KIR) ➡ Cソースコード、というフローを通る。AST 後の内部表現は、単純に C コードを出力しやすくするためのものなので汎用的ではないが、AST の構造を C 言語の構造に直すのに役立つように挿入してある。やはり構造に大きな差があるので、少々抽象度の高いイメージで変換して、それを一気に C コードに変換する形にしてみた。

基本的な構文と関数呼び出し（再帰含む）ができるようになったので、例のごとくフィボナッチ関数でのベンチマークに挑む。ここまで超特急で集中してこなして、約 1 週間くらいでベンチマークできた。

10/20 くらいに作り始めて、10月末あたりでここまで。一気に走ってフィボナッチ数列でベンチマークした。

で、色々追加

演算子や構文を色々と実装したりした。概ね以下の順序で実装。

演算子（++、--、&、| とか）を追加。
例外機構。try-catch-finally
while、do-while、for あたりを最初に。
そのあと、クラス、モジュールの実装。継承とか mixin 等も含む。
Fiber と yield。ちょっと頑張ったところ。
&&、||、?? あたりを短絡演算子として追加。
少し遅れて switch-case、switch-when、for-in あたりを。
あと、Integer の Range だけ実装。
基本型も一通り用意。（Binary だけまだ用意してない...）
名前空間の実装。
各種ライブラリ (XMLとかZIPとか)

いくつか要素技術的なところを。

例外機構

例外は、例外情報を持ちまわって return していく形。setjmp/longjmp とかは使わず、例外が発生していた場合、律儀に情報を伝達していって catch 節がある場合にそこに goto する。そのほうが、スタックトレースを記録しやすいので。スタックトレースは、C 言語上の位置ではなく、kilite コード上の位置を保存していかないといけないため、longjmp で戻ってしまうとどの呼び出し経路でどのように呼び出されたかを管理するのが面倒な気がしたため。やればできるとは思うけど。

Fiber

Fiber の実装をどうしようか、は少し悩んだ。

が、今回もマルチスレッドは使わず、シングルスレッドの中で行ったり来たりする感じに。スタックは、C 言語変換された関数が直接持っているので、それを保存して復帰させる仕組みが必要。また、どこから再開するかの場所も保存しておく必要がある。

yield のときに Yield 値みたいな整数値を保存しておいて、帰ってきたときにその値を元に該当の場所にジャンプする。具体的には switch-case で分岐して goto するようにしている。

また、直接 yield した関数だけではなくて、途中通り過ぎるだけの関数がいるかもしれないことに注意。以下のようなケース。

Fiber ➡ 関数 A ➡ 関数 B ➡ 関数 C で yield

関数 C で yield されると一気に Fiber の外まで戻って、次に resume されたときには関数 A、B の状態も復元させた上で関数 C に戻ってこないといけない。

ということで、yield で戻ってきたときには関数 A、B も状態を保存しておき、resume されたらその都度復元しながら関数 C 呼び出しまで戻る。関数 C で晴れて return された場合、関数 B は関数 C 呼び出しの次のステートメントの場所に goto してプログラムを再開させる感じ。

XML

XML は Kinx では libxml2 を使っていたのだが、手書きで簡単なパーサーを書いた。まだ完全な形にはなっていないが、基本的な DOM 操作だけなら 500 行くらいで書けた。DOM ノードの挿入、削除などの操作系と、あと XPath を実装しないといけないが、外部ライブラリとの整合性を意識する必要がないので、こっちのほうが楽かも。

特に XML 系はメモリ管理がややこしいので、外部ライブラリを使うとメモリの開放忘れとか、ライブラリと言語処理系の両方でデータを保持する感じで多少の無駄感もある。

XML の構文解析自体は難しくないしね。

ZIP

一方で、XML と違って Zip は自分で実装するのは困難を極める（やったことあるけど、というかその時でさえ OpenSSL は使った）。

最初、miniz という単一ソースライブラリが便利そうだったのでそれを使って実装し、実際に超簡単に実装できたのだが、やはり暗号化をサポートしたいということで一度ご破算にして zlib と minizip-ng で再実装中です。この後、PDF で使おうと思っている harupdf でも zlib が要求されるし、結局いつかは通る道。

今、ちょうどこの辺。というか、記事の公開に間に合ってほぼほぼ実装完了。

正規表現

記事に間に合った感じだが、仕様変更しようかどうか迷っている。今までは以下のようにできた。

var a = "111/aaa/bbb/ccc/ddd";
while (group = (a =~ /\w+\//)) {
    for (var i = 0, len = group.length(); i < len; ++i) {
        System.println("found[%2d,%2d) = %s"
            % group[i].begin
            % group[i].end
            % group[i].string);
    }
}

ただこれ、JavaScript だと無限ループになるパターンだということに気づいた。というか、正規表現リテラルをループ条件に置くのはご法度だったのをあまり気にせず、「こう書けたらいいなー」的なノリで書けるようにしてしまったところに問題が。たしかに Kinx 仕様の場合、途中ブレークすると正規表現オブジェクトの状態が中途半端になるという問題は抱えていたのだが。。。ということで、JavaScript に合わせるか、Kinx との後方互換を維持するかでちょっと考えます。既にいくつか違いはあったりするので¹。

ということで、以下のように書く必要がある。

var re = /\w+\//;
var a = "111/aaa/bbb/ccc/ddd";
while (group = (a =~ re)) {
    for (var i = 0, len = group.length(); i < len; ++i) {
        System.println("found[%2d,%2d) = %s"
            % group[i].begin
            % group[i].end
            % group[i].string);
    }
}

PDF

KiTTy 相当の実装に挑むには PDF ライブラリが必要。harupdf を使う予定だが、もう少し先になりそう。

直接 exe ファイル出力

これは最初予想していたよりも、かなり使える気がしました。C 言語ソースを出力するので、そのまま Native ビルドして実行可能ファイルが作れます。ただ、実行ファイルを作るには、別途コンパイラが必要です。kilite では以下のように必要なライブラリもリンクした上で、直接 exe を出力できます（裏でコンパイラを動かして）。

$ kilite.exe -X examples\fib.klt
Temp path: .
Command: cl /O2 /MT /nologo /Fefib.exe ".\fib.c" /link /LIBPATH:"." kilite.lib
Creating executable successful: fib.exe

Linux だとこんな感じ。

$ ./kilite -X examples/fib.klt
Temp path: .
Command: gcc -O3  -o fib ./fib.c -L/home/kazuya/git/hub/kilite -lkilite -lm
Creating executable successful: fib

ちなみに、どんな C コードを出力しているか見たい場合は、以下のどちらかのオプションで出力できます。

$ ./kilite --cfull examples/fib.klt > fib.c
$ ./kilite --csrc examples/fib.klt

--cfull で出力した場合、そのまま先ほどの -X で出ているコマンドラインのソースコードとして利用できる形で、余計なものまで全部入ってますが同じようにコンパイルできます。--csrc で出力した場合はそのままコンパイルできませんが、スクリプト部分に特化して出力されるので見やすいです。

さて、コンパイルしてしまうと実行時の構文解釈からコンパイルの時間が丸ごとなくなるので速度的にも良好。例えば上記のフィボナッチ関数を普通にスクリプトとして動かすとこんな感じ。

$ time ./kilite examples/fib.klt
39088169

real    0m0.702s
user    0m0.663s
sys     0m0.040s

700ms かかってますね。最初はもっと速かったのですが、標準ライブラリを増やしていったらスタートアップでのロード時間が若干伸びてきて多少速度ダウンが...。では、次に実行形式にして測ってみましょう。

$ ./kilite -X examples/fib.klt
Temp path: .
Command: gcc -O3  -o fib ./fib.c -L/home/kazuya/git/hub/kilite -lkilite -lm
Creating executable successful: fib
$ time ./fib
39088169

real    0m0.115s
user    0m0.114s
sys     0m0.000s

115ms で動かせました。試しに luajit と PyPy いってみましょう。勝った感満載です。

$ time luajit examples/bench/fib.lua
39088169

real    0m0.316s
user    0m0.316s
sys     0m0.000s
$ time pypy3 examples/bench/fib.py3
39088169

real    0m0.356s
user    0m0.316s
sys     0m0.040s

この exe 化、非常に便利で期待が高い一方、たぶん一つ問題があって、eval() がおそらく使えない。eval() 自体まだ実装していないのだけど、exe 化したプログラムで eval() を実現するためには exe の中に kilite のコンパイラ部分を丸ごと抱え込んだ上で、出力した C コードは MIR でコンパイルされたコードで JIT 実行されることになる。これは、最初から最後まで MIR による JIT 実行の中で行うには問題ないのだけれども、exe 形式にすると元の出力ソース自体は Visual C とかでコンパイルされたコードを使うことになる。そうすると、JIT で使われるコードと微妙に異なる可能性が高い。例えば、構造体のレイアウトとかがちょっとでも違うと、きっとあっという間にクラッシュすることでしょう（混ぜるな危険）。

つまり、通常の実行と以下のように違いがある。

【通常】  Kilite コード ➡ C コード ➡ MIR ワールドで実行。
          eval()コードも MIR ワールドで実行。
【exe化】 Kilite コード ➡ C コード ➡ VS/gcc ワールドでコンパイル。
          eval()コードは MIR ワールドで実行。

このワールドの違いの中での情報のやり取りをケアする必要があるのだが、スマートな方法が思いつかない。ひとまず exe 化 + eval() は無理せず後回しにしておく予定。

今後

Kinx 自体が実は割と高機能だったりするので、そのレベルにするのが一苦労、ということもあり、どこかでペースダウンするかとは思いますが、まぁ気長に続けます。今はアドレナリンが出ているので、一気に突っ走っているモードですが。Kinx の SpecTest をちょこちょことコピーしてきているのだが、現時点で 200 くらいは通るようになった。

ということで、Kinx だけではなく、Kilite のほうもよろしくお願いします。お手すきの際に★でも押しておいてください。★を押しやすいようにもう一度リポジトリへのリンクを張っておきますね

https://github.com/Kray-G/kilite

今後としては、Kinx に追いつくことを KiTTy 相当を実現したいところですが、さらに次のステップとしては、以下でしょうか。

動的型付け言語のまま exe 化できる ことをアピールできるような何か。
一方で、まだほぼほぼ実装してませんが 型指定によるコンパイル時チェックと最適化 の実現。
実行形式だけではなく、.lib とか .a 形式にも対応して C から直接扱えるライブラリも作れる、みたいな。

では、また。

XMLの nextSibling とかが関数でなくてプロパティになっている、とか、もう少し簡便に書けるように func を function の代わりに使えるようにして予約語になってたりとか（それでテストケースを一部書き換えた... func という名前の関数が使えなくなっており）、例外の文言が若干変わっていたりとか。あと、これは Kinx にもフィードバックできるけど、zip.addString() で AES 暗号化できる方法が分かったので、サポートしました。 ↩

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