ElixirでPrologコンパイラを作ったお話

この記事は、fukuoka.ex Elixir／Phoenix Advent Calendar 2019 の6日目です。
昨日は@tuchiro さんの「 Elixir製MQTTクライアントtortoiseを使ってみた」でした．

#自己紹介
昭和30年代後半の生まれです。ドリフターズの全員集合をリアルタイムで見てました。聖子ちゃんより、明菜ちゃん派でした。Z80どっぷりでしたけど、6809に憧れてました。なんだか平均年齢を引き上げているような気がして恐縮です。1980年代にパソコンが出現し、激しい知的ショックを受けました。当時は第二次AIブーム。PrologとLispの洗礼を受けました。

#アンタも好きねぇ
また、Prolog処理系を作っています。C言語で作っていた頃は、仏教でいう難行苦行のようでした。書かなければならないコードが多いですし、ガベージコレクションも自前でなんとかしないといけません。バグとりにも苦労させられました。ところがどっこい、Elixirでやってみると鼻歌まじりでスイスイです。GCもElixirにお任せできますし、並列処理をProlog処理系に組み込んで計算実験するなんてことも気楽なものです。ElxlogというElixirで作ったProlog処理系にコンパイラを付けて遊んでました。

#WAMじゃないのよ、仮想マシンは　
Prologコンパイラといえばウォーレンさんの抽象マシン、WAMにコンパイルするのが常道です。しかし、これは高性能なものの、WAMを最初から作っていたのでは、とても時間がかかります。どうしようかな？と考えているとfukuoka.exのメンバ－さんから啓示がありました。

Codeモジュールを使いなはれ！

Codeモジュールを調べてみると、compile_string/1 とか　eval_string/1　とか、言語処理系好きにはたまらんものが満載です。これは弄り甲斐があるというものです。

アイディアはこうです。
（１）Prologのコードをインタプリタの仕組みを利用して、構文木を表すリストに変換します。
（２）コンパイラはその構文木のリストを解析して対応するElixirコードの文字列を生成します。
（３）全部のPrologコードをElixirの文字列に変換したら、Fileモジュールを使って識別子を”o"に変えたファイルに書き出します。
（４）reconsult述語は識別子が"o"のファイルである場合には、Fileモジュールでこれを文字列として読み込みます。
（５）さらに（４）の文字列をCodeモジュールのcompile_stringを使って動的にコンパイルします。

#半日で動いたインスタントコンパイラ
このコンパイラは11月のある土曜日の午後に書いたものです。実は昼飯を食ったら睡魔に襲われまして不覚にもお昼寝をしてしまったのでした。３時頃に目が覚めて、書き始めたんでした。ところがElixirの生産性の高さには驚くばかりです。２時間ほど書いていたら、それらしくコンパイルするところまで漕ぎつけました。Elixirの生産性の高さには驚くばかりです。

#生成されるコードは？
PrologというのはSLDリゾルーションというかなり変わった計算原理で動いています。Cなどの普通の言語に翻訳するのは骨がおれます。Elixirのcatch・throwに助けられました。階乗計算をするfact/2は、こんなコードに変換されています。見易さのためにformatしています。

fact(0,1).
fact(N,A) :- N1 is N-1,fact(N1,A1),A is N*A1.

Prologコードとの対応を示すコメントを付加しておきました。

defmodule Elxcomp do
  #述語がコンパイルされた述語であるかどうかを判定するためのもの
  def is_compiled([_, [name | _]]) do
    Enum.member?([:fact], name)
  end
　
　#fact/2のコード
  def prove_builtin([:fact | args], y, env, def, n) do
    try do
　　　#第一節　fact(0,1).　に対応するコード
      env1 = Prove.unify(args, [0, 1], env)
　　　#unifyが成功するのであれば後続の述語を実行（証明）する。
      if env1 != false do
        {result1, env1a, _} = Prove.prove_all(y, env1, def, n + 1)
　　　　#成功したのであれば真であることと環境、定義を返す
        if result1 == true do
          throw({true, env1a, def})
        end
      end
　　　#第一節が失敗した場合には第二節　fact(N,A) :- N1 is N-1,fact(N1,A1),A is N*A1.
　　　#を試す。
      env2 = Prove.unify(args, [{:N, n}, {:A, n}], env)
　　　　#unifyが成功であるならば本体部を実行（証明）する。
      if env2 != false do
        {result2, env2a, _} =
          Prove.prove_all(
            [
              [:builtin, [:is, {:N1, n}, [:formula, [:-, {:N, n}, 1]]]],
              [:pred, [:fact, {:N1, n}, {:A1, n}]],
              [:builtin, [:is, {:A, n}, [:formula, [:*, {:N, n}, {:A1, n}]]]]
            ] ++ y,
            env2,
            def,
            n + 1
          )
　　　　#第二節の本体部が成功であるならば真であること、環境、定義を返す
        if result2 == true do
          throw({true, env2a, def})
        end
      end
　　　
　　　#第二節も失敗した場合には偽と以前の環境、定義を返す。
      {false, env, def}
    catch
      x -> x
    end
  end
end

defmodule Elxfunc do
end

第一節が失敗した場合には第二節の証明に移るのですが、関数型言語であるElixirにはgotoがありません。さて、どうしましょう？としばらく悩んでいたのですが、catch、throwでできることに気が付きました。

#弾丸（タマ）よりも速く
コンパイルしたら速くなってくれてないといけません。どのくらい高速になったのかな？
8queensが動作するようになったので実行時間を計測しました。

インタプリタ

?- time(test()).
.....
[8,4,1,3,6,2,7,5]
"time: 1263587 micro second"
false
?-

コンパイラ

?- time(test()).
.....
[8,4,1,3,6,2,7,5]
"time: 786521 micro second"
false
?-

おおよそ4割程度、高速化しています。

さすがにCでゴリゴリと書いたSWI-PrologやGNU-Prologには及びません。しかし、半日でできたコンパイラにしては上出来というものです。

#決定性の計算が取柄！　
SWI-PrologとかGNU-Prologってのは20世紀の頃から開発が継続されています。めっちゃ高性能なのです。9Queensみたいなのは最適化されているので、新興のモダン言語より遥かに高速だったりします。これを超える性能をもつProlog処理系を作るのはとてもたいへん！　

しかし、Elxlogには１つだけそれらを超える取り柄があるのです。それは決定性の述語をElixirで記述できることです。竹内関数やアッカーマン関数をそれらの処理系で計算させると簡単に処理系が落ちます。ところがElxlogは涼しい顔して高速実行です。

tarai(X,Y,Z,A) :- A is elx_tarai(X,Y,Z).

!elixir
def tarai(x, y, z) do
  cond do
    x <= y -> y
    true -> tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
  end
end

Elxlog ver0.14
?- ['test.pl'].
true
?- time(tarai(12,6,0,X)).
"time: 122125 micro second"
X = 12
true
?-

#並列もあるでよ！
Elixirの得意技、並列も織り込んでいます。AND並列を実験的に入れてみました。parallelという述語で並列実行します。Fibonacciの再帰定義で効率がよくなります。parallel/Nという述語を入れてみました。

fib(0,0).
fib(1,1).
fib(N,A) :-
  N1 is N-1,N2 is N-2,
  fib(N1,A1),fib(N2,A2),A is A1+A2.

pfib(0,0).
pfib(1,1).
pfib(N,A) :-
  N1 is N-1,N2 is N-2,
  parallel(pfib(N1,A1),pfib(N2,A2)),A is A1+A2.

Elxlog ver0.14
?- ['test.pl'].
true
?- time(fib(15,X)).
"time: 2816025 micro second"
X = 610
true
?- time(pfib(15,X)).
"time: 1111898 micro second"
X = 610
true
?-

コンパイルするとさらに高速になります。

Elxlog ver0.14
?- compile('test.pl').
true
?- ['test.o'].
true
?- time(fib(15,X)).
"time: 732218 micro second"
X = 610
true
?- time(pfib(15,X)).
"time: 288258 micro second"
X = 610
true
?-

おお！　コンパイル＆並列でけっこうイケルんじゃないかぁ。

#渕先生、並列の時代の到来です！
20世紀後半の国家プロジェクト、第五世代計画、ICOTの渕一博先生は、当時から「並列の時代」を予言していました。先生の予想は早すぎたのでしょうか。今や、並列の時代に突入しています。この並列の時代にあってElixirは牽引役を果たしていくことでしょう。Prologと少なからず因縁のあるElixirが21世紀に活躍するのを渕先生は天上界でニコニコしながらご覧になっていることと思います。

#遊び甲斐たっぷりのElixir
Elixirには高性能なWEBアプリケーションライブラリであるPhoenixがあります。しかし、私は言語処理系いじりが好きな変わり者。WEBはさっぱりわからないもので、変なことをして遊んでいます。WEB以外にもかなりなポテンシャルをElixirは有しているらしいことがわかってきました。Joseさん、ありがとう。Elixirは大したヤツです。

#Githubにおいてあります。
https://github.com/sasagawa888/Elxlog

#次回
次回は@koga1020さんです！こちらも是非どうぞ～