はじめに
並行論理型言語 Guarded Horn Clauses(GHC) インタプリタを書いてコンパイラが欲しくなったので作ることにします。
実を言うと、かなり前に GHC コンパイラを作ったことがあります。
各ガード付きホーン節を C++ 言語のファンクタオブジェクトにコンパイルして、実行したいゴールはキューに投入する、実行エンジンはキューから一つづつゴールを取り出して実行する、という形で書いたのですが、あまり芳しい性能ではありませんでした。
また、データ構造も、型コードと値のユニオンからなるオブジェクトを CONS セルとした LISP 的な形でしたが、これも性能が出なかった原因だと思います。
あまりに性能が低く、保守性も極端に低かった（パーサを C++ で手書きした結果、メンテナンスができなくなった）のと、当時は GitHub もなくソースコードを永続的な形で管理できなかったなど複数の理由でその当時のソースは見当たりませんが、思い起こすとこんな感じでした。
その反省を踏まえ、
- ゴールキューイングモデルでなくコンテキスト主体の（WAM 的な）制御にする
- データ構造は CONS セルベースでなくタグ付きポインタにする
- コンパイラは Prolog で書く
という方針で GHC コンパイラを作ることにします。
データ構造にタグ付きポインタを使うもう一つの理由として、タグ付きポインタをアトミック操作すれば複数スレッドの同時ユニフィケーション実行も可能ではないか？と思っているということもあります。
とはいえ、いきなり複数スレッド同時ユニフィケーションにトライするのは無謀なので、以下のようなスケジュールでコンパイラを作っていくことにします：
- 「マイ・GHC-1」 : シングルスレッド・単一コンテキスト（逐次論理のみ）
- 「マイ・GHC-2」 : シングルスレッド・複数コンテキスト（並行論理可）
- 「マイ・GHC-3」 : マルチスレッド・複数コンテキスト（複数スレッド実行）
ざっくり言うと、
- 「マイ・GHC-1」はバックトラックのない Prolog 相当
- 「マイ・GHC-2」は KLIC 相当
- 「マイ・GHC-3」はマルチスレッドで動作する夢の GHC
という感じです。
2023年 7 月時点で「マイ・GHC-1」レベルのものがなんとか動いている、というところですが、諦めずにこつこつ作っていけば、そのうち「マイ・GHC-3」に到達できるのではないかと思っています。
コンパイル手順
コンパイラは以下のプログラムで構成します。
1 GHC から中間コードへの変換: ghc_to_wam.pl
2 中間コードから C++ ソースコードへの変換: wam_to_cc.pl
3 C++ コンパイラで実行形式に変換
GHC から中間コードへの変換
GHC ソースコードを Warren's Abstract Machine (WAM) 風の中間コードに変換します。
コンパイラは、与えられたソースファイルと、組み込み述語ソースファイルの内容を両方合わせて同時に中間コードに変換します。
コンパイラを Prolog で書くことにしたので、文法が Prolog そのままの GHC は構文解析で悩む部分がなくとても楽です。
Prolog と共通部分の多い GHC に移植するのも難しくないはずなので、セルフホスティング化も容易なはずです。
マイ・GHC の記述例は main/1 述語を含めて示すとこんなふうになります：
% たらい回し
tarai(X, Y, _, R) :- X =< Y | R = Y.
otherwise.
tarai(X, Y, Z, R) :- true |
X_1 := X - 1, tarai(X_1, Y, Z, R_X),
Y_1 := Y - 1, tarai(Y_1, Z, X, R_Y),
Z_1 := Z - 1, tarai(Z_1, X, Y, R_Z)
-> tarai(R_X, R_Y, R_Z, R).
main([_, X, Y, Z]) :-
atom_number(X, Xi),
atom_number(Y, Yi),
atom_number(Z, Zi),
time(tarai(Xi, Yi, Zi, Ri))
-> writeln(Ri).
ここで、main/1 述語は C++ コードでの main 関数引数の argv をアトムのリストとして受け取る処理です。
-> はオリジナルの GHC にはない、「マイ・GHC」独自拡張の文法で、逐次実行指定を表します。
f, g, h, i -> j は f -> g -> h -> i -> j と書くのと同じで、どちらも f, g, h, i, j の順序で逐次実行します。
現状の「マイ・GHC-1」では逐次処理のみサポートしていないために -> を使った記述が必須です。
中間コードも Prolog の項の形でファイルに書き出します。
出力例（一部。コメントは後から手書きで追加したもの）は、こんな感じです：
label(tarai/4). % tarai(X, Y, _, R) :-
goal(tarai/4).
requires(14).
try_guard_else(label(tarai/4-2)).
seq(6). % X =< Y
out_value(reg(in,1),reg(out,1)).
out_value(reg(in,2),reg(out,2)).
call((=<)/2).
activate. % |
trust_me. % R = Y.
get_value(reg(in,2),reg(in,4)).
proceed.
label(tarai/4-2). % otherwise.
try_guard_else_suspend. % tarai(X, Y, Z, R) :-
activate. % true |
trust_me.
seq(6). % X_1 := X - 1
out_variable(reg(x,5),reg(out,1)).
out_structure((-)/2,reg(out,2)).
write_value(reg(in,1)).
write_constant(1).
call((:=)/2).
trust_me.
seq(7). % -> tarai(X_1, Y, Z, R_X)
out_value(reg(x,5),reg(out,1)).
out_value(reg(in,2),reg(out,2)).
out_value(reg(in,3),reg(out,3)).
out_variable(reg(x,6),reg(out,4)).
call(tarai/4).
trust_me.
seq(8). % -> Y_1 := Y - 1
out_variable(reg(x,7),reg(out,1)).
out_structure((-)/2,reg(out,2)).
write_value(reg(in,2)).
write_constant(1).
call((:=)/2).
trust_me.
seq(9). % -> tarai(Y_1, Z, X, R_Y)
out_value(reg(x,7),reg(out,1)).
out_value(reg(in,3),reg(out,2)).
out_value(reg(in,1),reg(out,3)).
out_variable(reg(x,8),reg(out,4)).
call(tarai/4).
trust_me.
seq(10). % -> Z_1 := Z - 1
out_variable(reg(x,9),reg(out,1)).
out_structure((-)/2,reg(out,2)).
write_value(reg(in,3)).
write_constant(1).
call((:=)/2).
trust_me.
seq(11). % -> tarai(Z_1, X, Y, R_Z)
out_value(reg(x,9),reg(out,1)).
out_value(reg(in,1),reg(out,2)).
out_value(reg(in,2),reg(out,3)).
out_variable(reg(x,10),reg(out,4)).
call(tarai/4).
trust_me.
tail(11). % -> tarai(R_X, R_Y, R_Z, R).
out_value(reg(x,6),reg(out,1)).
out_value(reg(x,8),reg(out,2)).
out_value(reg(x,10),reg(out,3)).
out_value(reg(in,4),reg(out,4)).
execute(tarai/4).
命令コードは WAM を参考に決めましたが、当然ながら WAM とは似て非なるものになっています。
特に違うのは、サブゴール呼び出しに以下の種類を設けたことです：
- seq-call : 逐次呼び出し。呼び出しから復帰するまでブロックして待つ。
- par-spawn : 並行実行。新しいコンテキストを作って処理をキューイング。
- tail-exec : 末尾呼び出し。スタックを消費せずジャンプする。
（「マイGHC-1」では par-spawn を使った並行処理をサポートしておらず、seq-call / tail-exec を使った逐次処理のみが実行可能です）
その他、多くの部分が WAM と異なります。
中間コードについては別記事に改めて詳しく紹介したいと思います。
中間コードから C++ ソースコードへの変換
中間コードから C++ ソースコードへの変換は、ほとんど中間コードをそのまま C++ マクロに置き換えるだけです。
C++ 上で中間コードを実行する方法として考えていたのは以下のような方法でした：
- バイトコードインタプリタにして、中間コード種別に対応する数値を並べたものをプログラムとする
- プログラムのステップ毎に case 文一つを割り当てて、ラベルジャンプは case 文へのジャンプに置き換える。
- ラベル出現毎にプログラムを分割したものを独立した関数にする。ラベルジャンプは、どの関数に飛ぶかで表現する。サブルーチン呼び出しの戻りがある場合については戻ってくる場所にもラベルをつけることで戻りをジャンプに置き換える。
いろいろ考えた結果、こんなコードを出力することにしました。
void module(VM* vm, Program* prog) {
for (;;) {
switch (vm->pc) {
(略)
case 442: // tarai/4
/* 442 */ MACRO_goal(442,atom(32));
/* 443 */ MACRO_requires(14);
/* 444 */ MACRO_try_guard_else(454);
/* 445 */ MACRO_seq(6);
/* 446 */ MACRO_out_value(reg::in(1),reg::out(1));
/* 447 */ MACRO_out_value(reg::in(2),reg::out(2));
/* 448 */ MACRO_call(232,449); // call((=<)/2)
case 449: // return_from_call((=<)/2)
/* 449 */ MACRO_activate;
/* 450 */ MACRO_trust_me;
/* 451 */ MACRO_get_value(reg::in(2),reg::in(4));
/* 452 */ MACRO_proceed;
case 454: // tarai/4-2
/* 454 */ MACRO_try_guard_else_suspend;
/* 455 */ MACRO_activate;
/* 456 */ MACRO_trust_me;
/* 457 */ MACRO_seq(6);
/* 458 */ MACRO_out_variable(reg::x(5),reg::out(1));
/* 459 */ MACRO_out_structure(atom(24),reg::out(2));
/* 460 */ MACRO_write_value(reg::in(1));
/* 461 */ MACRO_write_constant(tagvalue<TAG_INT>(1));
/* 462 */ MACRO_call(271,463); // call((:=)/2)
case 463: // return_from_call((:=)/2)
/* 463 */ MACRO_trust_me;
/* 464 */ MACRO_seq(7);
/* 465 */ MACRO_out_value(reg::x(5),reg::out(1));
/* 466 */ MACRO_out_value(reg::in(2),reg::out(2));
/* 467 */ MACRO_out_value(reg::in(3),reg::out(3));
/* 468 */ MACRO_out_variable(reg::x(6),reg::out(4));
/* 469 */ MACRO_call(442,470); // call(tarai/4)
case 470: // return_from_call(tarai/4)
/* 470 */ MACRO_trust_me;
/* 471 */ MACRO_seq(8);
/* 472 */ MACRO_out_variable(reg::x(7),reg::out(1));
/* 473 */ MACRO_out_structure(atom(24),reg::out(2));
/* 474 */ MACRO_write_value(reg::in(2));
/* 475 */ MACRO_write_constant(tagvalue<TAG_INT>(1));
/* 476 */ MACRO_call(271,477); // call((:=)/2)
case 477: // return_from_call((:=)/2)
/* 477 */ MACRO_trust_me;
/* 478 */ MACRO_seq(9);
/* 479 */ MACRO_out_value(reg::x(7),reg::out(1));
/* 480 */ MACRO_out_value(reg::in(3),reg::out(2));
/* 481 */ MACRO_out_value(reg::in(1),reg::out(3));
/* 482 */ MACRO_out_variable(reg::x(8),reg::out(4));
/* 483 */ MACRO_call(442,484); // call(tarai/4)
case 484: // return_from_call(tarai/4)
/* 484 */ MACRO_trust_me;
/* 485 */ MACRO_seq(10);
/* 486 */ MACRO_out_variable(reg::x(9),reg::out(1));
/* 487 */ MACRO_out_structure(atom(24),reg::out(2));
/* 488 */ MACRO_write_value(reg::in(3));
/* 489 */ MACRO_write_constant(tagvalue<TAG_INT>(1));
/* 490 */ MACRO_call(271,491); // call((:=)/2)
case 491: // return_from_call((:=)/2)
/* 491 */ MACRO_trust_me;
/* 492 */ MACRO_seq(11);
/* 493 */ MACRO_out_value(reg::x(9),reg::out(1));
/* 494 */ MACRO_out_value(reg::in(1),reg::out(2));
/* 495 */ MACRO_out_value(reg::in(2),reg::out(3));
/* 496 */ MACRO_out_variable(reg::x(10),reg::out(4));
/* 497 */ MACRO_call(442,498); // call(tarai/4)
case 498: // return_from_call(tarai/4)
/* 498 */ MACRO_trust_me;
/* 499 */ MACRO_tail(11);
/* 500 */ MACRO_out_value(reg::x(6),reg::out(1));
/* 501 */ MACRO_out_value(reg::x(8),reg::out(2));
/* 502 */ MACRO_out_value(reg::x(10),reg::out(3));
/* 503 */ MACRO_out_value(reg::in(4),reg::out(4));
/* 504 */ MACRO_execute(442,4); // execute(tarai/4)
(略)
default:
throw RuntimeError();
}
}
}
ジャンプしたい（あるいは述語呼び出しから復帰したい）場合には、ジャンプ先あるいは復帰先をプログラムカウンタ vm->pc に設定して continue すると、全体を囲っている switch 文によって当該アドレスから実行を継続する、という仕組みです。
case 文にあるアドレスへのジャンプのみ可能で、例えば上のコードだと case 文がない 500 にジャンプしたい、と言っても無理です。
外部から特定述語を呼び出したい、という場合には、予め準備された「述語 - case 文の値 対応表」を引いて呼び出し先アドレスを決定します。
「マイ・GHC」の構成要素
タグ付きポインタ
データ型は intptr_t を基本とします。
64bit マシンを前提に下位 3 bit をタグとして扱います。
タグとしては、以下を使う予定です：
- REF : 参照。ポインタを保持する。
- ATOM : シンボル（文字列） ID およびアリティを保持する。
- INT : 整数値を保持する。
- LIST : CAR/CDR ペアへのポインタを保持する。
- NIL :
[]を表す。 - STR : 構造体へのポインタを保持する。
- SUS : 待ち合わせ ID を保持する（現時点では未実装）。
- OBJ : オブジェクト ID を保持する（現時点では未実装）。
シンボル辞書
main/1 述語引数に与えられる文字列など、全ての文字列はシンボル辞書に登録され、ID 番号が割り当てられます。
コンパイル時に決定される述語の名前もシンボル辞書に登録され、プログラムコード上の各述語の処理開始アドレスとの対応関係もシンボル ID との対応の形で保存します。
待ち合わせ
並行論理型言語のコンパイラを作ろうとしているので、複数の並行実行コンテキストが必要になります。
複数実行コンテキストを有効に使うには、待ち合わせ機構も必要です。
GHC は未実現変数を参照しようとしたときには当該未実現変数に自身を待ちとして登録する、ということをします。
これを実現するには未実現変数に構造をもたせる必要がありますし、単一化処理も単純に値を設定するだけではだめで待ち状態のコンテキストを起床させる処理が必要です。
ちなみに現状の「マイ・GHC-1」は単一の実行コンテキストしかないのですが、単一実行コンテキストだけでも結構使いものになりそうな雰囲気も感じていて（考えてみれば、世の中では逐次処理のプログラミング言語が主流）、いっそのこと GHC のコンパイラを作るのを辞めて「バックトラックのない Prolog」に振り切ってしまうのもいいかもしれない、と思わなくもありません。
オブジェクトの扱い
シンボル辞書と同じように、C++ のオブジェクトを扱えるオブジェクト辞書を作って
オブジェクト ID の形でタグ付きポインタから扱えるようにします。
例えば、多倍長計算は多倍長数値オブジェクトを引数として扱う形で ':='/2 を拡張していけばよい、という目論見です。
実行器
WAM を参考に作っているので、実行器はレジスタマシンです。
但し、逐次実行でサブゴールを呼び出すときにレジスタの内容を退避するコストが気になったのでサブゴール呼び出しをレジスタウィンドウで実現することにしました。
レジスタウィンドウの先頭部分が引数レジスタで、それに続く部分が一時変数領域です。
サブゴールを呼び出すときにはさらにその後ろに続けて呼び出し先に渡す引数を設定してウィンドウを進めます。サブゴールから戻るときにはウィンドウを元に戻してもらいます。
（呼び出し先述語の引数をどの領域に置くかは逐次呼び出し（seq-call）、並行呼び出し（par-spawn）、末尾呼び出し（tail-exec）のどれかによって異なります。
seq / par /tail 命令は引数書き込みに先立って、書き込み先を準備する処理を行います）
また、レジスタの後方は捨ててもよい一時変数を置く領域、特にスタックとしても使用することにしました。
入れ子になったリストや構造体を組み立てるときにレジスタ上のどの位置を使うかを考えるのが大変そうだったので、素直にスタックを使っています。
このスタックをレジスタとは別に用意することもできたのですが、なんとなくレジスタを使いまわしたほうが性能的に有利そうな気がしたのでこのようにしています。
（一方で、単一化における再起処理もスタックを使って実装すべきだと思いますが、現状は手抜きをしていて C++ の再帰呼出しそのままです。これはいずれ改修が必要になるかもしれません）
同じ理由で、コールスタックもレジスタに混ぜて置く予定だったのですが、実際に処理を書いてみるとレジスタサイズ不足時の拡張においてポインタ再計算が煩雑だったので断念してコールスタックは別に用意することにしました。
コールスタックにはプログラムカウンタの情報、fail した際に継続処理位置、当該フレームにおける引数レジスタの位置など呼び出しから復帰したときに復元が必要な情報を置きます。
組み込み述語
出来合いの WAM 風中間コードの組み合わせでは実現できない機能を実現するために、あたえられたアトムをそのまま C++ ソースコードとして出力する述語 inline/1 を用意しました。
これによりコンパイラに手を入れることなく組み込み述語を追加できます。
例えば、メタコールを実現する組み込み述語 call/1 は inline を使って以下のように実装しています：
call(Goal) :- call_inline(Goal).
call_inline(Goal) :-
inline('{'),
inline(' MACRO_wait(reg::in(1));'),
inline(' const Q goal = deref(vm->in[1]);'),
inline(' vm->in[1] = goal;'),
inline(' const TAG_T tag = tag_of(goal);'),
inline(' if (tag != TAG_STR) {'),
inline(' vm->fail();'),
inline(' continue;'),
inline(' }'),
inline(' A* structure = ptr_of<A>(goal);'),
inline(' Q g = structure[0].load();'),
inline(' const int pc = prog->query_entry_point(g);'),
inline(' if (pc < 0) {'),
inline(' vm->fail();'),
inline(' continue;'),
inline(' }'),
inline(' const int arity = atom_arity_of(g);'),
inline(' MACRO_tail(2);'),
inline(' for (int i = 1; i <= arity; ++i) {'),
inline(' MACRO_out_constant(structure[i].load(), reg::out(i));'),
inline(' }'),
inline(' MACRO_execute(pc, arity);'),
inline('}').
ヒープとガベージコレクション
「マイ・GHC」はヒープ上にタグ付きポインタを作りながら動作します。
ヒープ上に [hello, world, '!'] を作ってみた例が以下です：
0x565535f7fb58 heap[ 1] : <LIST>0x565535f7fb60 %
0x565535f7fb60 heap[ 2] : <ATOM>'hello' % [hello
0x565535f7fb68 heap[ 3] : <LIST>0x565535f7fb70 % ,
0x565535f7fb70 heap[ 4] : <ATOM>'world' % world
0x565535f7fb78 heap[ 5] : <LIST>0x565535f7fb80 % ,
0x565535f7fb80 heap[ 6] : <ATOM>'!' % '!'
0x565535f7fb88 heap[ 7] : <NIL>0 % ]
ヒープは少なくともスレッド数分用意して、各スレッドが新しい変数をヒープ先頭から末尾に向かって払い出していけるようにします。
ヒープがいっぱいになったら新しいヒープを作って、新しいヒープの先頭から変数を払い出していきます。
どこまで払い出したかは各スレッドが独立して管理できるので複数スレッドの競合を心配する必要がありません。
ただし、一度変数として払い出した領域は別のスレッドから参照される可能性があるので、ヒープはアトミックなタグ付きポインタの配列ということにします。
変数を compare_exchange 操作すれば各スレッドは競合下でも正しく単一化操作できるに違いない（単一化中に状況が変わったら一旦諦めて当該ゴールの処理を最初からやりなおしてよい）、というのが「マイ・GHC-3」に向けた目論見です。
「マイ・GHC」はなにを実行するにしてもヒープに変数を作らずにはいられません。
例えば、単純に B に 1 を足してその結果を変数 A に得る、というだけの処理
A := B + 1
だけを考えても、まずヒープ上に '+'(B, 1) という構造を作って、結果 A を受け取る領域も確保して、それでようやくサブゴール ':=' を呼び出すことができます。
適当なプリプロセッサを作ればこのあたりも改善できるはずですが、このあたりに手を出すより「マイ・GHC-3」に進む方を優先したいという気持ちがあります。
いずれにせよ、実用プログラムを書くにはガベージコレクションは必須でしょう
（が、今はトイプログラムレベルのものしか動かしていないこと、現代の PC はそこそこメモリをいっぱい積んでいるのでガベージコレクションなしでも結構動く、という理由からガベージコレクションも未実装です）。
ガベージコレクションは、実行器のレジスタをルート要素としたマーク処理と、マークされたヒープ上の要素をコピーする形で実装する予定です。
簡単な性能測定
SWI-Prolog でたらい回しプログラムを実行するとこんな感じでした。
?- time(tarai(12, 11, 0, X)).
% 54,182,802 inferences, 2.873 CPU in 2.874 seconds (100% CPU, 18859762 Lips)
X = 12.
マイ・GHC の実行時間と比較したいと思ったので、似たような表示を出す述語 time/1 を作って計測してみました：
$ ./tarai 12 11 0
% 196412655 inferences, 3.34256 CPU seconds (58761215.967661 Lips)
12
マイGHC で出している推論数、Lips 表示はあまりあてにならないので、CPU 時間だけ比較して見ていただければと思います。
言い訳すると、現状では性能よりも安定動作に重点を置いていています。
例えば、デバッグのために中間コードそれぞれにトレース情報出力機能を付けていて、起動時に環境変数を見てトレース ON/OFF を切替可能、などといったこともやっています。
性能が気になり始めたときにはトレース情報出力機能を取り除くなどして比較してみたいと思います。
性能測定について追記
X_1 := X - 1 といった処理を
- 数式に対応する構造体
'-'(X, 1)をヒープ上に作る。 - 変数 X_1 を第１引数、数式を第２引数として
':='/2を呼び出す。 -
':='/2は再帰的に数式を分解して計算して、最終的に引き算を計算する組み込み述語isub/3を呼び出して得た結果をX_1に単一化する。
という形で実行しているのですが、適当なプリプロセッサを導入したならばこれを isub(X, 1, X_1) という呼び出しだけにできるはずです。
tarai(X, Y, _, R) :- X =< Y | R = Y.
otherwise.
tarai(X, Y, Z, R) :- true |
isub(X, 1, X_1), tarai(X_1, Y, Z, R_X), % ← 引き算を述語呼び出しに置き換え
isub(Y, 1, Y_1), tarai(Y_1, Z, X, R_Y), % ← 引き算を述語呼び出しに置き換え
isub(Z, 1, Z_1), tarai(Z_1, X, Y, R_Z) % ← 引き算を述語呼び出しに置き換え
-> tarai(R_X, R_Y, R_Z, R).
このような置き換えを行って同じ性能測定をすると、このような結果になりました：
$ ./tarai 12 11 0
% 74501355 inferences, 1.22644 CPU seconds (60745926.020146 Lips)
12
推論数が大幅に下がる結果、実行時間も驚くほど高速化できることがわかります。
':='/2 は比較的出現頻度が高いので、このような前処理の実装は優先度を上げてもよいのかもしれません。
今後の展望
- ガベージコレクションを実装する
- 待ち合わせ機構を実装し、複数コンテキストの並行実行を実現する
- 複数スレッドで複数のコンテキストを同時実行できるようにする