LoginSignup
12
5

More than 3 years have passed since last update.

言語実装Advent Calendar 2019Day 4
@sym_num(笹川 賢一)infukuoka.ex：福岡Elixirコミュ

ISO-PrologからGHC,独自拡張Prologへ

Last updated at Posted at 2019-12-03

自己紹介

1980年代にコンピューターに出会いました。当時は第二次AIブームでありLispとPrologの洗礼を受けました。5年ほど前からLispとPrologの処理系実装に取り組んできました。2018年の後半にElixirのことを知りました。

はじめに

5年ほど前からO-Prologという処理系（実装１）に取り組んでいました。ISO規格準拠のものです。SWIやGNU-Prologのような老舗の処理系並みの実行速度を出すこと、そしてISO準拠を目標としていました。それは部分的に達成はしたものの、ISO-Prolog規格に疑問を持つようになりました。ヨーロッパのISOのメンバーやフリーの研究者たちと連絡がとれ、資料を入手、取り組んでいました。その過程で分かったことはISOの規格はアンバランスなことでした。規格制定当時、有力なベンダーの意向がまとまらずモジュールの規格は極めて中途半端に終わっていました。そうした中、ISOのメンバーはモジュールなど実用に必要な規格の制定を諦めて言語のコア部分の緻密化の方向に進んだようです。規格が要求する水準は高く、ISO準拠のProlog処理系の制作は極めて難しいものとなっています。

私は、そんな状況に嫌気が差してしまい、もっとシンプルなSLDリゾルーションに絞ったProlog規格、処理系実装を模索することにしました。2018年後半にElixirのことを知りました。これは並列機能に優れており、予てより興味のあったGHC（Guarded　Horn　Clauses)の実装にも応用できるように思えました。2019年に入り、Elixirに習熟するとともにElixirによりシンプルなProlog処理系を３つ作りました。１つめは極めて単純なエジンバラPrologのサブセットです。２つめはGHCのElixirによる実装です。最後はエジンバラシンタックスをベースにしつつもAND並列、関数の拡張、決定性述語の拡張を目指したものです。それらについて概略を報告いたします。

極めてシンプルなPrologインタプリタ

文献１のインタプリタを参考にしてElixirでPrologインタプリタを作りました。Small Prolog(実装２)はGitHubにて公開しています。独自に工夫をした点は下記の通りです。

変数のα変換

Prologの変数のスコープは節を単位としています。この節は再帰する場合が多々あります。再帰した場合において失敗したときにはバックトラック動作をする必要があります。このため再帰動作時においては節の変数をα変換し、再帰の都度、異なる変数名を割り当てる必要があります。文献１でのCommon Lispの実装ではgensymを使い、異なるシンボルを割り当てる実装となっています。しかし、Elixirにおいてはアトムの数に限界があるうえにGCにおいて不要なアトムは回収されないことがわかりました。アトムを大量に生成するわけにはいきません。そこで変数をtupleを使って表現しています。　{:X,1} のようにしています。数の部分は再帰によりネストした場合に２，３・・・と割り当て変数を唯一のものとしています。その工夫を除けば、ほぼ文献１の考え方に沿っています。

文脈に依存しないシンタックス及び簡素化

エジンバラProlog、ISO-Prologでは次のように引数がない述語を定義することが可能です。

foo :- write('Hello').

fooというアトムが述語なのか？単なるアトムなのか？がパースの段階で判然としません。O-Prologにおいては文脈依存のパーサでこれに対応しました。これを下記のように明記することに変更しました。

foo() :- write('Hello')

これによりfooは述語名であることが明確になります。パーサを大幅に簡素化することができました。また、演算子の定義、再定義の機能を排除しました。項には数、アトム、変数のみを許容することとしパーサをシンプルなものとしました。Small Prologは実用を目的としたものではなく、SLDリゾルーションの仕組みをElixirで明確に記述することを目的としていました。

GHC実装

GHCは第五世代コンピューター計画において核言語として設計されたものです。
以下、Wikipediaより引用
Guarded Horn Clauses (GHC)は、1984年末に設計され1985年に発表された並行論理プログラミング言語である[1]。第五世代コンピュータプロジェクトで並列マシンの核言語の検討をしていた上田和紀により設計された。核言語の候補だったConcurrent Prologを分析する過程で問題点を見付け、それを解決するさらに単純化した言語として設計した。
引用終わり

以前よりGHCに興味があり、安価なラズパイをクラスタ接続した並列マシンを作って実装、実験をしようと思っていました。ところがElixirの並列機能を使えば手軽にGHCの実装を試みることができそうなことがわかり、Elxghc（実装３）を作りました。効率のことは考えず、まずは動作すること、GHCの仕組みを理解することを目標としました。Elixirはspawnにより軽量マイクロプロセスを大量に生成することができます。これを利用しました。

AND並列

各節の本体部の述語は並列動作することとされています。そこでその述語ごとにマイクロプロセスを生成し並列実行することとしました。述語間に依存関係がない場合には一斉に並列動作してもいいのですが、 foo(X,Y),boo(Y,Z). のように変数に依存関係がある場合には逐次に動作させています。本体部の述語をキューに溜めておいて、依存関係を調べつつ独立しているものは並列で実行する仕組みとしています。

OR並列

GHCでは複数の節を並列で動作することとされています。このため中断という仕組み、そしてガード部を設けて、実行可能になったものから並列で推論する仕組みになっています。この中断の仕組みの理解に苦慮しました。参考文献は文献５しかありません。この説明を読みながら試行錯誤しつつ中断を実装しました。GHCでは各節は並列に実行され、一番最初に実行が終わったものをもって変数値を確定する仕組みと解釈し、そのように実装しています。

疑問点

おそらく、私の理解、実装は間違えています。Wikipediaの例コードに次のクイックソートがあります。


qsort([Pivot|Xs], Ys0, Ys2) :- part(Xs,Pivot, Small, Large),
                               qsort(Small, Ys0, [Pivot|Ys1]),
                               qsort(Large, Ys1, Ys2).
qsort([],         Ys0, Ys1) :- Ys0 = Ys1.

part([X|Xs],Pivot,Small,Large) :- Pivot< X | Large=[X|L1], part(Xs,Pivot,Small,L1).
part([X|Xs],Pivot,Small,Large) :- Pivot>=X | Small=[X|S1], part(Xs,Pivot,S1,Large).
part([],    _,    Small,Large) :-            Small=[], Large=[].

qsort/3の第一節の本体部は次のようになっています。


qsort(Small, Ys0, [Pivot|Ys1]),qsort(Large, Ys1, Ys2).

変数Ys1が共通に使われています。私の実装ではこのような依存関係にある場合、逐次に処理しています。しかし、GHCではこれが並列動作することとされています。述語間でプロセス間通信をする必要があるように思います。しかし、私にはこれをElixirで並列処理する方法を思いつきません。

GHCでは変数が具体化されるまでは実行を中断するとされています。Ys1が具体化されるまでは中断するという考え方だと思います。GHCが想定しているのは同期式の並列のようです。一方、Elixirが採用しているのは非同期式です。根本的に考え方が異なるように思います。

効率の問題

本体部のAND並列においては素朴にすべての述語に各１つのマイクロプロセスを割り当てています。これは再帰の場合においても同様です。このため再帰動作時において、大量のマイクロプロセスが生成されることとなります。Elixirは大量のマイクロプロセスを扱えますので、一応は動作するのですが、計測してみますと逐次処理よりも遅くなってることがわかりました。（文献８）

課題

中断の概念をよく理解できてないこと、マイクロプロセスの大量生成による非効率など問題点は多々あるものの、それらしく動作するようにはなりました。文献５のconcat/3が並列で動作しています。あれこれと試行錯誤しつつGHCは逐次型のPrologとはかなり発想の異なるものであることは理解できてきました。

エジンバラPrologの独自拡張

GHCと並行して逐次型のPrologについて独自に拡張することを考えました。３つのことを拡張しました。これを取り込んだものが Elxlog(実装４）です。

（１）is/2における右辺にElixirによる関数を記述できるようにした。
（２）決定性の述語につきElixirで述語を記述できるようにした。
（３）本体部につきAND並列を入れた。

is/2における関数記述

Prologは非決定性の計算をするところに特徴があり、竹内関数やフィボナッチ数の計算をすることには向いていません。なぜならバックトラックに備えて変数束縛を解除できる仕組みが必要だからです。このためそれらの計算をするとたちまち処理系が落ちてしまいます。カットを入れまくればコンパイラによっては最適化、決定性の計算に置き換えてくれる処理系も中にはあるのかもしれません。しかし、カットの多用はコードを著しくわかりにくくします。

文献９にis述語を拡張して独自に関数を記述することにより論理型と関数型を融合させるというような話があったことを思い出しました。決定性の計算はElixirのような普通の関数型言語で処理した方が遥かに効率的でありわかりやすい記述となります。Elixirの動的コンパイルの仕組みを利用してElixirで記述されたコードをインタプリタで取り込めるようにしました。この結果、次のような記述を可能としています。

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

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

!elixir
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

!elixir は以下のコードがElixirのコードであることを示しています。

関数計算はElixirと同程度の実行効率を確保できます。通常のProlog処理系より高速に実行、処理系が落ちるということもありません。

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

決定性の述語のElixirによる記述

下記のコードはQueens問題のコードの一部です。


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

queenの利き筋に他のqueenがないかどうかを判定する述語です。このnodiagはバックトラックをしません。決定性の述語です。賢いコンパイラはこれを末尾再帰の決定性の計算に変換して効率を稼いでいます。しかし、これをElixirに任せてしまってもいいのではないかと考えました。

以下はElixirでの記述を交えたものです。

% 8-queens program
test() :- queen([1,2,3,4,5,6,7,8],X),write(X),nl(),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

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

elixir/1という述語を用意しました。これはElixirの関数を述語とみなして実行するものです。Elixirは末尾再帰の効率のよいコードに変換します。計測してみると3倍ほど高速になることがわかりました。

おそらく初期のPrologはpureなものであり、カットのような手続き的なものは存在していなかったはずです。しかし、実用言語として実行効率を稼ぐにはカットもやむを得ず必要だったのでしょう。しかし、これが論理型言語の良さに対する足枷、分かりにくさの原因となっていることは否めないでしょう。決定性の述語をElixirで記述できるのであれば、カットを排除することが可能です。

AND並列

ElxghcによりGHCの実装を試みる過程で、GHC方式の並列は普通の人にはわかりにくいように思えてきました。元来、人間は並列を考えることは苦手であり、逐次に考えているということを読んだ記憶があります。OR並列を取り込むと頭の切り替えが必要になるとともに、全解探索がやりにくくなります。

そこで、逐次型Prologの本体部に並列実行可能なものがあった場合にだけ、AND並列をできる機能を付加してみました。シンタックスもエジンバラそのままにするために、独自の述語を追加する方法としました。parallel/Nという述語を追加しました。任意個の引数をとることができます。それぞれの引数は述語です。それらを並列に実行するようにしています。GHCと異なり非同期式並列です。

下記はその応用例で、Fibonacci数を計算するものです。pfib/2が並列処理です。


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.

GHCでのクイックソートの例とは異なり、２つの述語は完全に独立しています。プロセス間通信の必要はありません。独立にマイクロプロセスで実行できます。

実行結果は下記の通りです。なお、Elxogにはコンパイラも実装したため、コンパイルした場合も併記してあります。

インタプリタ

?- time(fib(15,X)).
"time: 2793170 micro second"
X = 610
true
?- time(pfib(15,X)).
"time: 1127453 micro second"
X = 610
true
?-

コンパイラ

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

このように並列用の述語　parallel/Nを使うことにより、単純なコードで、かつ、並列の恩恵が受けられることがわかりました。コンパイラもまずまず機能しているようです。

クイックソートの例題も次のコードで並列動作しました。GHCのような難しさもなく、すぐに理解できるものです。


pqsort([],[]).
pqsort([X],[X]).
pqsort([X|Xs],Y) :-
  part(X,Xs,S,L),parallel(pqsort(S,S1),pqsort(L,L1)),append(S1,L1,Y).

part(A,[],     [A],[]).
part(A,[X|Xs],S0,L) :- A>=X,S0=[X|S], part(A,Xs,S,L).
part(A,[X|Xs],S,L0) :- A < X,L0=[X|L], part(A,Xs,S,L).

Elxlog ver0.14
?- ['test.pl'].
true
?- pqsort([2,3,1,7,5,0],X).
X = [0,1,2,3,5,7]
true
?-

まとめ

ISO-Prolog規格に対する疑問からスタートし、シンプルなPrologシンタックス、決定性の関数、述語の記述、簡素なAND並列を取り込んできました。Prologにはまだまだ可能性があるように思えます。第五計画で渕一博先生は並列の時代が来ることを予測していました。現在、並列の時代に突入しています。また、Deep Learningの成功によりAIが見直されています。DLにより視覚、聴覚をコンピューターは獲得したと言えるだろうと思います。さらにDLとPrologによる論理的推論が組み合わされれば面白いことができるのではないかと考えています。

Elixirは比較的新しい言語ではありますが、コアの部分はErlangの技術が使われており円熟したものがあります。並列の時代においてElixirが大活躍することでしょう。そして、かつて1980年代に研究され、発展したPrologが再度、活躍することもあり得るのではないかと思っています。

文献

[1] Code for Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp (Peter Norvig)
邦訳　実用Common Lisp
[2] O-Prologの仕様、覚書
https://qiita.com/sym_num/items/e6e35d3e1bff41f0efe5
[3] O-Prologのコンパイラ
https://qiita.com/sym_num/items/e6e0032f2547010dfb3e
[4] Pure Prolog in Elixir (実装２の覚書）
https://qiita.com/sym_num/items/715b5fabd0455e366ee3
[5] 並列論理型言語GHCとその応用　淵一博　監修　古川康一・溝口文雄　共編　共立出版
[6] Elxghc -Elixir によるGHC実装の試み-
https://qiita.com/sym_num/items/89b4269ad7e55eb8b5d3
[7] Elxghc　-中断の実装-
https://qiita.com/sym_num/items/a55b5e616da2e21a46b0
[8] Elxghc -並列動作とその測定-
https://qiita.com/sym_num/items/da64d5d15375aea85288
[9]　記号処理プログラミング　後藤滋樹著　岩波書店
[10] Elxlog シンプルでわかりやすい論理&関数型をめざして
https://qiita.com/sym_num/items/9ce1b6a79ad4954d5f51
[11] Elxlog　実行効率の測定
https://qiita.com/sym_num/items/a7091abfffdb2df5c5d5
[12] エジンバラ文法内でのAND並列の試み
https://qiita.com/sym_num/items/abfc569188a6a3c0aa35

実装

[1] O-Prolog
https://github.com/sasagawa888/opl

[2] Small Prolog
https://github.com/sasagawa888/Prolog

[3] Elxghc
https://github.com/sasagawa888/Elxghc

[4] Elxlog
https://github.com/sasagawa888/Elxlog

12
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
12
5