B-プロローグ

B-Prolog は、マッチング節、イベント処理のアクション規則、有限領域制約解決、配列とハッシュ テーブル、宣言的ループ、およびテーブル化を含むいくつかの拡張機能を備えた標準Prolog言語の高性能実装でした。1994 年に最初にリリースされた B-Prolog は、現在広く使用されているCLPシステムです。B-Prolog の制約ソルバーは、第 2 回国際ソルバー コンペティションの 2 つのカテゴリでトップにランクされ、^[1]第 2 回 ASP ソルバー コンペティションの P クラスで 2 位を獲得し、 ^[2]第 3 回 ASP ソルバー コンペティションでは総合 2 位を獲得しました。^[3] B-Prolog は、論理ベースの確率的推論および学習システムである PRISM システムの基盤となっています。B-Prolog は商用製品ですが、学習および非営利の研究目的では無料で使用できます (バージョン 7.8 以降、商用個人ユーザーを含む個人ユーザー向けの B-Prolog は無料です^[4] )。 B-Prolog は現在は積極的に開発されていませんが、Picat プログラミング言語の基礎を形成しています。

マッチング節は、決定性と入力/出力の統一が明示的に示される節の形式です。コンパイラは、マッチング節をマッチングツリーに変換し、すべての入力引数のインデックスを生成します。マッチング節のコンパイルは、複雑なプログラム分析や特殊化が不要なため、通常の Prolog 節のコンパイルよりもはるかに簡単です。また、生成されるコードはよりコンパクトで高速になる傾向があります。B-Prolog コンパイラとライブラリ述語のほとんどは、マッチング節で記述されています。

一致する句は次の形式になります。

H 、 G  =>  B

ここで、Hはアトミック式で、GはB2 つのアトミック式のシーケンスです。は節のHヘッド、Gガード、本体と呼ばれます。 の呼び出しはの変数をバインドできず、 のすべての呼び出しはインライン テストでなければなりません。つまり、ガードはフラットでなければなりません。次に、2 つのソートされたリストをマージするマッチング節の述語の例を示します。 BGHG

マージ([], Ys , Zs )  =>  Zs = Ys 。
merge ( Xs ,[], Zs )  =>  Zs = Xs 。
マージ([ X | Xs ],[ Y | Ys ], Zs )、X < Y  =>  Zs = [ X | Xs ] ZsT ]、マージ( Xs ,[ Y | Ys ], ZsT )。
マージ( Xs ,[ Y | Ys ], Zs )  =>  Zs = [ Y | Ys ] ZsT ]、マージ( Xs 、Ys 、ZsT )。

cons は[Y|Ys]3 番目の節のヘッドと本体の両方に出現します。項の再構築を避けるために、この節を次のように書き直すことができます。

マージ([ X | Xs ], Ys , Zs )、Ys = [ Y | _ ]、X < Y  =>  Zs = [ X | ZsT ]、マージ( Xs 、Ys 、ZsT )。

Ys=[Y|_]ガード内の呼び出しはYsパターンと一致します[Y|_]。

環境に反応できる「アクティブな」サブゴールをプログラミングする機能がないことが、論理プログラミングの弱点の 1 つと考えられてきました。これを克服するために、B-Prolog は、エージェントをプログラミングするためのアクション ルール (AR) と呼ばれる、シンプルでありながら強力な言語を提供します。エージェントは、遅延でき、後でイベントによってアクティブ化できるサブゴールです。エージェントがアクティブ化されるたびに、何らかのアクションが実行されることがあります。エージェントは、インスタンス化、ドメイン、時間、およびユーザー定義のイベントを含むさまざまな種類のイベントに応答できるという意味で、初期の Prolog システムおよび並行論理プログラミング言語のプロセスの遅延構造よりも一般的な概念です。

アクションルールは次のようになります

H 、 G 、 { E }  =>  B

ここでH、 はエージェントのパターン、Gはエージェントの条件のシーケンス、Eはエージェントをアクティブ化できるイベントのパターンのセット、 はBエージェントがアクティブ化されたときに実行されるアクションのシーケンスです。イベント パターンEとそれを囲む中括弧がない場合、アクション ルールは一致する句に退化します。

制約プロパゲータと対話型グラフィカル ユーザー インターフェイスをプログラミングするために、組み込みイベントのセットが提供されています。たとえば、ins(X)は変数がインスタンス化されるときにポストされるイベントですX。ユーザー プログラムは独自のイベントを作成してポストし、それらを処理するエージェントを定義できます。ユーザー定義イベントは、という形式になります。event(X,O)ここで、Xはイベントをその処理エージェントに接続するサスペンション変数と呼ばれる変数であり、はOエージェントに送信される情報を含む Prolog 項です。組み込みはpost(E)イベントをポストしますE。

次の例を考えてみましょう。

echo ( X ),{ event ( X , Mes )} => writeln ( Mes ). 
ping ( T ),{ time ( T )}  =>  writeln ( ping ).

エージェントはecho(X)受信したメッセージをエコーし​​ます。たとえば、

?- echo ( X )、post ( event ( X 、hello ))、post ( event ( X 、world ))。

メッセージを出力し、helloその後に が続きますworld。エージェントはping(T)タイマーからの時間イベントに応答しますT。時間イベントを受信するたびに、メッセージ を出力しますping。たとえば、

?-タイマー( T 、1000 )、ping ( T )、繰り返し、失敗。

毎秒時間イベントを投稿するタイマーを作成し、ping(T)イベントに応答するエージェントを作成します。エージェントを永続的にするには、エージェントの後のループが必要です。

AR は、単純な並行処理のプログラミング、制約プロパゲータの実装、インタラクティブなグラフィカル ユーザー インターフェイスの開発に役立つことがわかっています。制約処理ルール(CHR) と回答セット プログラム(ASP) をコンパイルするための中間言語として機能してきました。

多くの Prolog ベースの有限領域制約ソルバーと同様に、B-Prolog の有限領域ソルバーはCHIPシステムの影響を強く受けています。最初の本格的なソルバーは、1997 年 3 月に B-Prolog バージョン 2.1 でリリースされました。そのソルバーは、AR の初期バージョンで実装され、delay 句と呼ばれていました。過去 10 年間で、実装言語 AR は、制約プロパゲータをプログラミングするための豊富なドメイン イベント クラス ( ins(X)、、、および) をサポートするように拡張され、システムは新しいドメイン (ブール、ツリー、および有限セットbound(X)) 、グローバル制約、および特殊な高速制約プロパゲータで強化されました。最近、2 つの組み込み と が拡張され、正および負のテーブル (拡張とも呼ばれる) 制約を使用できるようになりました。 dom(X,E)dom_any(X,E)in/2notin/2

実装言語として AR を採用したおかげで、B-Prolog の制約解決部分は比較的小さく (コメントとスペースを含めて Prolog コードで 3800 行、C コードで 6000 行)、パフォーマンスは非常に優れています。 AR 言語は、問題固有のプロパゲータを実装するためにユーザーに開放されています。 たとえば、以下は制約 のアーク一貫性を維持するためのプロパゲータを定義しますX+Y #= C。 の内部要素Eyが のドメインから除外されるたびに、このプロパゲータがトリガーされ、 の対応する要素 がのドメインからY除外されます。 制約 については、アーク一貫性を維持するために、 との2 つのプロパゲータを生成する必要があります。 これら 2 つのプロパゲータに加えて、除外された値が境界である場合にイベントがポストされないため、区間一貫性を維持するためのプロパゲータも生成する必要があります。プロパゲータを生成する前に、制約 をアーク一貫性にするために前処理する必要があります。 ExEyXX+Y #= C'X_in_C_Y_ac'(X,Y,C)'X_in_C_Y_ac'(Y,X,C)dom(Y,Ey)

'X_in_C_Y_ac' ( X 、Y 、C )、var ( X )、var ( Y )、
   { dom ( Y 、Ey )} 
   =>          
   Ex は C - Ey 、        
   domain_set_false ( X 、Ex )。
'X_in_C_Y_ac' ( X 、Y 、C )  =>  true 。

B-Prolog では、構造体の最大アリティは 65535 です。これは、構造体を 1 次元配列として使用でき、多次元配列を構造体の構造体として表すことができることを意味します。配列の作成を容易にするために、B-Prolog は と呼ばれる組み込み関数を提供します new_array(X,Dims)。ここで、 はXインスタンス化されていない変数と、Dims配列の次元を指定する正の整数のリストである必要があります。たとえば、 の呼び出しは、最初の次元に 10 個の要素があり、2 番目の次元に 20 個の要素がある 2 次元配列にnew_array(X,[10,20])バインドしますX。配列のすべての要素は、自由変数として初期化されます。

組み込み述語をarg/3使用して配列要素にアクセスできますが、結果を格納するための一時変数と、多次元配列の要素にアクセスするための一連の呼び出しが必要です。配列要素へのアクセスを容易にするために、B-Prolog は配列の添え字表記 をサポートしています。X[I1,...,In]ここで、 はX構造体で、各 はIi整数式です。ただし、配列にアクセスするためのこの一般的な表記は、標準の Prolog 構文の一部ではありません。この表記に対応するために、パーサーは^変数トークンと の間にトークンを挿入するように変更されます[。したがって、 表記はX[I1,...,In]の省略形にすぎませんX^[I1,...,In]。この表記は、算術式、制約、または の呼び出しの引数で出現する場合、配列アクセスとして解釈されます@=/2。その他のコンテキストでは、用語自体として扱われます。配列の添え字表記は、リストの要素にアクセスするためにも使用できます。たとえば、nth/3述語 は次のように定義できます。

n番目( I 、L 、E )  :-  E  @=  L [ I ]。

Prolog はループを記述するために再帰に依存しています。強力なループ構造がないため、ループ用の小さな補助的な再帰述語を定義するのが面倒なことが多いため、Prolog は初心者には受け入れられにくく、経験豊富なプログラマーには生産性が低いと言えます。CLP (FD)foreachなどの制約プログラミング構造の出現により、モデリング言語としての Prolog のこの弱点がさらに明らかになりました。B-Prolog は、コレクションを反復処理するための と呼ばれる組み込み関数と、リストを構築するためのリスト内包表記法を提供します。

組み込みforeach関数の構文と意味は非常にシンプルです。例えば、

foreach ( A が [ a , b ]にあり、  I が1..2にある場合、(( A , I )))と記述する    

は、4 つのタプル、、、およびを出力します(a,1)。構文的には、(a,2)は可変長の呼び出しであり、最後の引数は、コレクションのシーケンス内の値の各組み合わせに対して実行される目標を指定します。呼び出しでは、各反復に対してローカルな変数のリストと、各反復からの値を蓄積するために使用できるアキュムレータのリストも指定できます。アキュムレータを使用すると、を使用して集計を計算するための再帰を記述できます。再帰は手続き的に読み取る必要があるため、Prolog には適していません。このため、関数型言語のリスト内包表記を採用しています。リスト内包とは、最初の要素に関数 ' ' があるリストです。この形式のリストは、の呼び出しや算術制約ではリスト内包として解釈されます。たとえば、クエリ (b,1)(b,2)foreachforeachforeach:@=/2

X  @=  [( A , I )  :  Aは [ a , b ]の範囲内、  Iは1..2 の範囲内]   

Xリストにバインドします[(a,1),(a,2),(b,1),(b,2)]。リストの内包表記は、foreach実装ではアキュムレータを使用した呼び出しとして扱われます。

呼び出しforeachとリスト内包表記は末尾再帰述語に変換されます。したがって、再帰を使用する場合と比較して、これらの構造を使用することによるペナルティはまったくないか、またはわずかです。

ループ構造は CLP(FD) のモデリング能力を大幅に強化します。以下は B-Prolog での N クイーン問題のプログラムです。

queens ( N ):- 
    length ( Qs , N )、
    Qs  ::  1. . N 、
    foreach ( I  in  1. . N - 1 、 J  in  I + 1. . N 、
            ( Qs [ I ]  #\=  Qs [ J ]、
             abs ( Qs [ I ] - Qs [ J ])  #\=  J - I ))、
    labeling ([ ff ]、Qs )、
    writeln ( Qs )。

リストの配列表記は説明を短くするのに役立ちます。配列表記がなければ、foreachプログラム内のループは次のように記述する必要があります。

foreach ( I が 1. . N - 1の場合、 J が I + 1. . N の場合、[ Qi 、Qj ]、
        ( nth ( Qs 、I 、Qi )、
         nth ( Qs 、J 、Qj )、
         Qi  #\=  Qj 、
         abs ( Qi - Qj )  #\=  J - I ))、

ここでQi、 およびQjは各反復に対してローカルに宣言されます。以下は、ボード上の各マスにブール変数を使用する N クイーン問題のプログラムです。

bool_queens ( N ):- 
   new_array ( Qs ,[ N , N ]), 
   Vars  @=  [ Qs [ I , J ]  :  Iは 1です 。. N 、Jは1です。. N ], Vars :: 0..1 、foreach ( I in 1. . N 、% 各行にクイーンが 1 個、合計([ Qs [ I , J ] : J in 1. . N ]) #= 1 )、foreach ( J in 1. . N 、% 各列にクイーンが 1 個、合計([ Qs [ I , J ] : I in 1. . N ]) #= 1 )、foreach ( K in 1 - N .. N - 1 、% 各左下対角線にクイーンが最大 1 個、合計([ Qs [ I , J ] : I in 1. . N 、J in 1. . N 、I - J =:= K ]) #=< 1 )、foreach ( K in 2..2 * N 、% 各左上対角線にクイーンが最大 1 個、合計([ Qs [ I , J ] : I in 1. . N 、J in 1. . N 、I + J =:= K ]) #=< 1 )、ラベル付け( Vars )、foreach ( I in 1. . N 、[ Row ]、( Row @= [ Qs [   
     
          
                 
          
                 
      
                     
        
                     
   
     
             I , J ]  :  J  in  1. . N ]、 writeln (行)))。

テーブル化は、初心者が実用的な宣言型プログラムを書くのに役立つだけでなく、自然言語処理、モデル検査、機械学習アプリケーションなどの実際のアプリケーションを開発するためにもますます重要になっています。B-Prolog は、固定点を計算するためにサブゴールを一時停止するのではなく、ループするサブゴールの反復計算に基づく線形テーブル化と呼ばれるテーブル化メカニズムを実装しています。テーブル化に大きく依存する PRISM システムは、B-Prolog のテーブル化システムの設計と実装の主な原動力となっています。

テーブル化の考え方は、テーブル化された呼び出しに対する応答を記憶し、その応答を使用して後続のバリアント呼び出しを解決することです。B-Prolog では、XSB と同様に、テーブル化された述語は次の形式の宣言によって明示的に宣言されます。

:-テーブル P1 / N1 、...、Pk / Nk 。

たとえば、次の表の述語は、によって与えられる関係の推移閉包をedge/2定義します。

:-テーブル パス/ 2.
パス( X 、Y ):-エッジ( X 、Y )。
パス( X 、Y ):-パス( X 、Z )、エッジ( Z 、Y )。

テーブル化により、用語のサイズが制限されている限り、プログラムへのすべてのクエリが終了することが保証されます。

デフォルトでは、テーブル呼び出しのすべての引数はバリアントチェックに使用され、テーブル述語のすべての回答はテーブル化されます。B-Prologはテーブルモードをサポートしており、システムはバリアントチェックで入力引数のみを使用し、選択的にテーブル回答を使用できます。テーブルモード宣言

:-テーブル p ( M1 ,..., Mn ) : C .

は、での回答の表作成方法をシステムに指示します。p/nここで、 はカーディナリティ制限Cと呼ばれ、表作成する回答の数を制限する整数です。また、 はそれぞれ、、 、(入力)、または(出力)のいずれかのモードです。モードがまたはの引数は、出力であるとみなされます。カーディナリティ制限が の場合、前に ' ' を付けて省略できます。 Miminmax+-minmaxC1:

テーブル モードは、動的プログラミングの問題を宣言的に記述するのに非常に便利です。たとえば、次のプログラムは、一対のノード間の最小の重みを持つパスを見つけるための Dijkstra アルゴリズムをエンコードします。

:- table  sp ( + , + , - , min ). 
sp ( X , Y ,[( X , Y )], W )  :- 
    edge ( X , Y , W ). 
sp ( X , Y ,[( X , Z )| Path ], W )  :- 
    edge ( X , Z , W1 ), 
    sp ( Z , Y , Path , W2 ), 
    Wは W1 + W2です 。

テーブル モードでは、各ノード ペアに対して最小の重みを持つ 1 つのパスのみがテーブル化されます。

• Prolog実装の比較
• Prologの構文と意味論

• 公式サイト
• B-Prologで解決する方法
• B-Prolog の言語機能とアーキテクチャ
• PrologとCLP(FD)システムのパフォーマンス比較
• Logtalkのパフォーマンス