はじめに

Elxlogのコア部分が動き出しました。コードはPrologコードとElixirコードとを混在させることができます。これにより部分的に実行効率が改善されました。

決定性の関数

Prologでアッカーマン関数を計算することに意味があるとは思えないのですが、中にはそういうことに燃えてる人もいます。そこまで計算コストが大きくないにしても単純にElixirで書いた方が楽なものもあるでしょう。
次のように記述できます。


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

ack(M,N,A) :- A is elx_ack(M,N).

!elixir
defmodule Elxfunc do
  def ack(0, n), do: n + 1
  def ack(m, 0), do: ack(m - 1, 1)
  def ack(m, n), do: ack(m - 1, ack(m, n - 1))

  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

end

Prolog部分はインタプリタです。Elixir部分は読み込んだものを動的にコンパイルしています。このような計算の場合にはElixirの性能がそのまま結果に反映します。

Elxlog ver0.08
?- ['test.pl'].
true
?- time(tarai(14,7,0,X)).
"time: 4845619 micro second"
X = 14
true
?- time(ack(4,1,X)).
"time: 20672091 micro second"
X = 65533
true
?-

おそらくPrologとして世界最高速級だろうと思います。ただし、こんな計算をわざわざPrologでやらせることは無意味です。

決定性の述語

こんどは8queensです。コード中のnodiag/3は利き筋かどうかを判定するものです。これをPrologでやると効率が悪いです。バックトラックするはずがないことはわかっているのですが、最適化をしないPrologはバックトラックに備えるため、非効率です。

Elxlogでは述語　elixir/1を新設しました。nodiag/3をElixirで書いておいてこれを呼び出すことができます。

コードは次のようになります。


% 8-queens program
test() :- queen([1,2,3,4,5,6,7,8],X)。,fail().

queen(Data, Out) :-
    queen_2(Data, [], Out).

queen_2([], _, []).
queen_2([H|T], History, [Q|M]) :-
    qdelete(Q, H, T, L1),
    elixir(elx_nodiag(History, Q, 1)),
    queen_2(L1, [Q|History], M).



qdelete(A, A, L, L).
qdelete(X, A, [H|T], [A|R]) :-
    qdelete(X, H, T, R).


nodiag([], _, _).
nodiag([N|L], B, D) :-
    D != N - B,
    D != B - N,
    D1 is D + 1,
    nodiag(L, B, D1).

!elixir
defmodule Elxfunc do
    def nodiag([],_,_) do true end
    def nodiag([n|l],b,d) do
        if d != n-b && d != b-n do
            nodiag(l,b,d+1)
        else
            false
        end
    end
end

この実行結果は次の通りです。

Elxlog ver0.08
?- ['queens.pl'].
true
?- time(test()).
"time: 933124 micro second"
false
?-

8queensの実行、1回につき933ミリ秒かかっています。C言語で書かれているProlog処理系よりは遅いものの、まあまあの結果を出しています。Elixirでない普通のPrologによるnodiag/3ではこの3倍の時間がかかります。

展望

Elxlogの構想が着々と形になりつつあります。Prologは元来、一階述語論理に基づくプログラミング言語です。ところが現実問題のためにカットやif_then_elseをつかいまくると、最早、一階述語論理のエレガントな風情はありませんでした。Elxlogの方法によればこのカット使いまくりの汚い部分を排除できることがわかってきました。

ソースコード

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

Elxlog 実行効率の測定

はじめに

決定性の関数

決定性の述語

展望

ソースコード

Elxlog　実行効率の測定