目的・現在の状況
マイ・GHC コンパイラを、ほそぼそと改良し続けています。
ようやく未実現変数の実現待ち合わせ処理を含めて動作するようになってきました。
まだ本来の目標であるマルチスレッド推論は未実装で、ガベージコレクションも未実装です。ですが、GHC や KL1 のソースコードを移植して動かせる程度にはなってきました。
動作確認も兼ねて、KLIC(KL1 to C コンパイラ) のサンプルコードを動かしてみます。
ハノイの塔
hanoi.kl1 をhanoi.ghcとして移植しました。
main 述語、I/O ストリームをマイ・GHC の形式に書き換えて、結果を表示する述語を追加していますが、ハノイの塔本体の処理はそのままです。
% ハノイの塔
go(N, X) :-
move(N, left, center, right, X, []).
move(0, _, _, _, O1, O2) :- true | O1 = O2.
move(N, A, B, C, O1, O4) :-
N > 0 |
M := N-1,
move(M, A, C, B, O1, [m(A,B)|O3]),
move(M, C, B, A, O3, O4).
N-Queen
kkqueen.kl1をqueen.ghcとして移植しました。
KL1 のソースコードだとガード部に ; を使っていたのですが、現状のマイ・GHC コンパイラでこの構文はサポートしていないので使わない形に書き換えています。
% N-Queens
go(N, X) :-
gen(N, L),
queen(L, [], [], X, []).
queen([], [], L, I, O) :- I = [L|O].
queen([], [_|_], _, I, O) :- I = O.
queen([P|U], C, L, I0, I2) :-
check(L, P, 1, U, C, L, I0, I1),
queen(U, [P|C], L, I1, I2).
check([], T, _D, U, C, B, I, O) :-
concat(U, C, N),
queen(N, [], [T|B], I, O).
check([P|R], T, D, U,C, B, I, O):-
T =\= P+D,
T =\= P-D |
D1 := D+1,
check(R, T, D1, U,C, B, I, O).
check([P|_R],T, D,_U,_C,_B,I, O):-
T =:= P+D | I=O.
check([P|_R],T, D,_U,_C,_B,I, O):-
T =:= P-D | I=O.
concat([], Y, Z) :- Z = Y.
concat([W|X], Y, WZ) :- WZ = [W|Z], concat(X, Y, Z).
gen(N, X) :- N > 0 | X = [N|Xs], M := N-1, gen(M,Xs).
gen(N, X) :- N =:= 0 | X = [].
性能比較
未実現変数の実現待ち合わせがない GHC プログラムは、コミットバー | を ! や -> に、:=/2 を is/2 に置き換えるなどすることでほぼそのまま Prolog プログラムとして実行できます。
マイ・GHC の実行性能を SWI-Prolog と比較してみます（KLIC と比較してどうなのかも気になるところですが、KLIC が動く環境を準備できていないので）。
現状のマイ・GHC コンパイラ開発では実行性能に重点を置いていないため、性能の比較自体にたいした意味はないのですが、それでもあまりに性能に食い違いが出ていればなにか実装が致命的におかしい可能性を疑うきっかけにはなります。
桁違いの性能差がなければまあそこそこ問題なく作れているような気がする、という程度には感触を掴めるのではないかと思いました。
SWI-Prolog は 10 回実行してそれぞれの実行時間を計測するループを組んで、その中でのベストタイムを実行時間としています（Just-in-time clause indexing があったりで初回実行は遅いので）。
マイ・GHC コンパイラのほうは実行を数回繰り返してそのなかでのベストタイムを拾いました。
ハノイの塔の実行時間比較
ハノイの塔の実行時間（CPU 時間、単位は秒）の比較です。
| N | SWI-Prolog | マイ・GHC |
|---|---|---|
| 5 | 0.000 | 0.00002 |
| 10 | 0.000 | 0.00043 |
| 15 | 0.009 | 0.00932 |
| 20 | 0.353 | 0.24384 |
| 21 | 0.364 | 0.47476 |
| 22 | - | 0.94289 |
| 23 | - | 1.87889 |
SWI-Prolog の側の実行時間がちょっと不自然な感じです。これは実行を繰り返そうとするとヒープ不足で落ちてしまうため、十分な繰り返し回数を実行できないからだと思います。
N-Queen の実行時間比較
N-Queens の実行時間（CPU 時間、単位は秒）の比較です。
| N | SWI-Prolog | マイ・GHC |
|---|---|---|
| 7 | 0.002 | 0.0039 |
| 8 | 0.008 | 0.0146 |
| 9 | 0.033 | 0.0644 |
| 10 | 0.164 | 0.3091 |
| 11 | 0.899 | 1.6503 |
| 12 | - | 9.5578 |
| 13 | - | 58.3004 |
| 14 | - | - |
当方の環境（32GBメモリ）ではマイ・GHC でも N=14 以上での解は得られませんでした。
ちなみに、https://swish.swi-prolog.org/example/queens.pl にあったソースコード（The Craft of Prolog 掲載のもの）のを使って findall/3 での全解取得にかかる時間を計測すると、以下のように SWI-Prolog の圧勝です。
| N | SWI-Prolog |
|---|---|
| 7 | 0.000 |
| 8 | 0.001 |
| 9 | 0.005 |
| 10 | 0.021 |
| 11 | 0.102 |
| 12 | 0.538 |
| 13 | 3.016 |
| 14 | 18.031 |
多分、自分で条件を列挙するコードを書くより組み込み述語の select/3 を使ったほうが効率的、といった理由もあるのでしょう。
実行環境に応じた適切なアルゴリズムの選択が重要であることを再認識させられます。
たらい回し
tarai(N, N-1, 0) 相当の処理をする時間を比較してみました。
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).
未具体化変数の待ち合わせ処理を強化していった結果、残念ながら実装初期より実行時間が伸びています。
| N | SWI-Prolog | マイ・GHC |
|---|---|---|
| 10 | 0.070 | 0.1023 |
| 11 | 0.441 | 0.6088 |
| 12 | 2.871 | 4.0136 |
| 13 | 19.919 | 27.7972 |
（ちなみに、日本語版 Wikipedia での説明 では「tarai が正当で tak は記憶違いによる亜種に過ぎない」という書き方なのに対して、英語版 Wikipedia での説明 だと「メモ化で簡単に高速化できる tarai より tak の方がベンチマークとして優れている」という感じで書かれているのがちょっとおもしろいと思います）
敢えて記述順序を変えて、変数の具体化待ち合わせを頻繁に起こすようにすると、その分実行時間も伸びます。
tarai(X, Y, _, R) :- X =< Y | R = Y.
otherwise.
tarai(X, Y, Z, R) :- true |
tarai(R_X, R_Y, R_Z, R), % ← R_X, R_Y, R_Z の具体化待ちが発生する
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).
| N | マイ・GHC | resume 発生回数（参考） |
|---|---|---|
| 10 | 0.124 | 165860 |
| 11 | 0.757 | 1029804 |
| 12 | 4.890 | 6772851 |
| 13 | 33.734 | 46983239 |
記述順序を変えるとかなり実行効率が落ちるに違いない、と想像していたのですが実際には 1.2 倍程度の実行時間の伸びに留まっています。
まとめ
動作確認を兼ねて、マイ・GHC コンパイラでいくつかのサンプルコードを動かしてみました。
変数の具体化待ち合わせがない前提では GHC プログラムはほぼそのまま Prolog 上で実行できるため、SWI-Prolog と実行時間を比較してみました。
N-Queens やたらい回しについては想像どおり SWI-Prolog の方が高速です。
また、Prolog では、GHC 流のストリームを使ったプログラムより、バックトラックと findall/3 を使ったプログラムの方が効率よく探索できます。
問題サイズに関しては、メモリ使用についてなにも自主規制をかけていないマイ・GHC コンパイラの方がより大きい問題サイズについても実行できることが多いようです。
GC を実装すればさらに大きい問題サイズについても実行可能になるはずです。
意外にもハノイの塔に関してはマイ・GHC コンパイラは SWI-Prolog と比較してもいい勝負をしています。この理由はちょっとわかりません。
変数の具体化待ち合わせがあると若干性能インパクトがありますが、想像していたほどの影響は出ていません。もっとも、具体化待ちがない状態でも遅いのでそれほどのインパクトとして見えていないだけ、という見方もできます。
今後は
- そこそこ安定動作するようになってきたのできれいな形に書き直す。
- マルチスレッド化する。マルチスレッド化したときに実行性能がどの程度変化するか、そもそもマルチスレッドで正しく推論できるかどうかを見てみたい。
という方向でさらに改善していきたいと思います。