kprolog K-Prolog Compiler Version 6.0

プログラムの動作

本節ではプログラムの意味について解説します。 Prolog言語の入門または応用については書籍がたくさん出版されています。 必要に応じてそれらの資料を参照することをお勧めします。

ゴールの実行

Prologプログラムは、指令である質問や命令を実行するときに動き始めます。 

   28: ?-  質問．
   :-  命令．
命令や質問はゴールを","で区切って並べたものでした。 この","は論理的には AND を意味する演算子ですが、 Prologの処理系は、これらのゴールを左端に書かれたものから順に実行しようとします。 

［例］
   28: ?- capital(japan,C).
     は、前節の例に従えば、
   C = tokyo
     を結果として返してきます。
ゴールを実行すると、そのゴールと同じ名前で同じアリティの述語が呼び出されます。 述語が呼び出されると、その述語の節のうちで頭部がそのゴールと単一化できるものを 探します（単一化については後述します）。
呼び出された述語が組込み述語または外部述語である場合には、述語の実行手順は その述語の仕様に従います。

探す順序は上から下に節が書いてある順です。頭部が単一化できる節があれば、 その節の本体部をゴールとして実行します。 本体部は","で区切られたゴールですから、 左端のゴールから順に実行します（本体部がなければ直ちに実行が 成功します）。 本体部のゴールの実行がすべて成功すればその節（あるいはその述語） の実行が成功したことになります（成功しないことを 失敗と言います)。

ここでは、ゴールの実行が普通のプログラム言語と同じように 述語を手続きとして呼び出す形式で行うこと、 述語の実行が節の探索を含むこと、 節の本体部の実行が他の言語と同じく書いてある順に行われることを理解してください。 


［例］
   29: ?- capital(Nation,peking),population(Nation,Population).
   Nation=china,
   Population=118000

単一化

単一化とは、２つの項がまったく同一になるように、それぞれの項の変数に適 当な代入を行うことです。たとえば、 
   capital(Nation,peking)  と   capital(usa,washington)
は、Nationにどんな値を代入しても、peking と washington は、 同一にならないので単一化できません。しかし、 
   capital(Nation,peking)  と   capital(china,peking)
は、Nation=china という代入で同一になるので単一化できます。
項と項の単一化は、項の表記に対して行われるのではありませんから 、1+X と '+'(1,2) は代入 X=2 によって単一化できることに注意してください。

さて、ゴールが実行されるときには、 呼び出された述語の節の頭部と単一化されます。 このとき、節に含まれている変数は、 全く新しいものを一揃い用意するものと考えてください。 名前が同じものがたまたま存在しても別の変数であると 考えてもよいでしょう。変数名の有効範囲は１つの項の中でしたから、 １つの項である節の中の同じ名前の変数は常に同じものです。

このようにして、ゴールと節の頭部の単一化により、引数の受け渡しが行われます。 変数への値の代入は常にこの単一化によって達成されます。

単一化のプロセスを規則として書くと次のようになります。

  1. 変数は任意の項と単一化できて、変数の値はこの項自身になる（特に変数どう しを単一化した場合は、両者の変数は同一のものになる）。
  2. 同じ定数どうしは単一化できる。
  3. 複合項どうしは関数子名とアリティが同じで、対応する引数どうしが単一化できれば、単一化できる。
  4. 1、2、3以外のケースでは単一化できない。
蛇足ですが、単一化は項そのものの形を対象にしているのであって、 数式の計算などを伴いません。たとえば、3 と 1+2 や、3 と 3.0 は、 単一化できるものではありません。数式の計算を行ったり、数値の比較を行うには、 別に算術組込み述語として用意されたものを使います。

成功と失敗

ゴールの実行が、成功しない、すなわち失敗するのは、
  1. 呼び出された述語が 組込み述語か 外部述語で、 その述語の仕様に従って失敗するとき
  2. 呼び出された述語の節の頭部でゴールと単一化できるものがないとき
  3. 頭部が単一化できても、本体部のすべてのゴールの実行が成功するような節がな いとき
です。失敗することを failするともいいます。ゴールの実行が失敗すると、
  1. トップレベルの命令や指令のときは、no を表示するか、またはエラーとしてとり扱う
  2. 節の本体部のゴールのときは、本体部の実行を放棄して、本体部や頭部で行われた単 一化の効果を全部元に戻した上で、その節の次の節（代替節と呼ぶことにしま す）から始めて、単一化できる頭部を持つ節の探索を再開することになります。
重要なのは2の場合で、この手順（後戻り） によって、Prolog言語は、解の探索を行っていることになります。 これらのことを具体的な例によって説明します。 
［例］

   祖母(_祖母,_孫):- 
      母親(_祖母,_親),親(_親,_孫).  ・・・(1)
   祖父(_祖父,_孫):-
      父親(_祖父,_親),親(_親,_孫).  ・・・(2)

   親(_親,_子):-父親(_親,_子).      ・・・(3)
   親(_親,_子):-母親(_親,_子).      ・・・(4)

   母親(フネ,サザエ).               ・・・(5)
   母親(フネ,カツオ).               ・・・(6)
   母親(フネ,ワカメ).               ・・・(7)
   母親(サザエ,イクラ).             ・・・(8)
   父親(波平,サザエ).               ・・・(9)
   父親(波平,カツオ).               ・・・(10)
   父親(波平,ワカメ).               ・・・(11)
   父親(鱒夫,イクラ).               ・・・(12)
祖母/2、祖父/2 と 親/2 はプログラムとして規則を表す述語です。 母親/2 と 父親/2 は、データとして事実を表す述語です。これらの述語が読 み込まれているときに、 
    29:  ?- 祖父(波平,_孫).
つまり、波平が祖父であるような_孫はだれかという命令を実行すると、 
     _孫 = イクラ
が答として返ってきます。この命令の実行の状況を図示してみます。 

   29: ?- 祖父(波平,_孫).

              _祖父=波平,_孫=_孫

  (2)  祖父(波平,_孫):- 父親(波平,_親),親(_親,_孫).

              サザエ=_親

  (9)  父親(波平,サザエ).

              _親=サザエ,_子=_孫

  (3)  親(サザエ,_孫):- 父親(サザエ,_孫).

        失敗

              _親=サザエ,_子=_孫

  (4) 親(サザエ,_孫):- 母親(サザエ,_孫).

              _孫=イクラ

  (8)  母親(サザエ,イクラ).
まず、述語、祖父/2 が呼ばれます。第1引数の 波平 と _祖父 は単一化されます。 _孫 と _孫 も単一化されて同じものになります。

次に本体部の最初のゴール 父親(波平,_親) を実行しますが、 これは(9)の単位節により成功します。 次のゴールに進むときに、単一化の効果によって _親=サザエ になっています。

親(サザエ,_孫) は、(3)の節の頭部と単一化され、 本体部の 父親(サザエ,_孫) を実行しますが、 父親/2 にはこのゴールと単一化できる節がないので、失敗します。 ここで後戻りが発生し、その結果(3)の節の次の節が選ばれて、 (4)の頭部と単一化されます。

(4)の本体部、母親(サザエ,_孫) は(8)の単位節により、成功します。 このとき、_孫=イクラ が単一化の効果として残っていますが、 (4)の _孫 は、トップレベルの_孫と単一化されているので、結果として、 

    _孫 = イクラ
が表示されるわけです。

副作用

後戻りについて詳しく説明する前に、 Prologプログラムの実行の効果のうち、単一化以外の部分について述べておきます。 他のプログラム言語では引数や関数値による値の受け渡し以外の 入出力や外部変数の値の書き換えなどが副作用と呼ばれます。 Prologの場合も同様に、
  1. 入出力
  2. 述語や節の追加や削除
  3. 内部データベース機能
  4. その他インタプリタの状態を変える組込み述語
の効果は副作用として働きます（単一化以外のすべての状態変化が副作用です）。

入出力は、ファイルのオープン、クローズを行う see、tell や seen、told などと、 実際に読み書きを行う read、write や get、put などの組込み述語で行われます。 述語や節のうち動的なものは、assert や retract、abolish という組込み述語でプログラムの実行中に追加、削除されます。

インタプリタの状態を変える述語は他にたくさんあって、 たとえば、unknown という組込み述語は、定義されていない述語の実行の方法 を変更します。

後戻りとカット

ゴールの実行が失敗したときに、その節の次の節(代替節) から節の探索を再開することを後戻りと呼ぶことは、すでに説明しました。
後戻りが発生したときには、単一化の効果は元に戻るのですが、副作用は元に戻りません。これを例示してみると、 

   foo(x): -write(X),checka(X).
   foo(x): -write(X),checkb(X).
   checka(a).
   checkb(b).
foo/1 は引数が a または b と単一化できるときに成功する という意味を持ちますが、副作用としては、write/1 によって引数の値が書かれます。 

   foo(a)
   foo(a) :- write(a),checka(a).
   aが書かれる
   checka(a). 成功
   ;
   foo(a) :- write(a),checkb(a).
   aが書かれる
   checkb(a). 失敗

   foo(b)
   foo(b) :- write(b),checka(b).
   bが書かれる
   checka(b). 失敗
   foo(b) :- write(b),checkb(b).
   bが書かれる
   checkb(b). 成功

引数がaのときは、 

	aが書かれる→成功する→
		後戻りを起こせば→aが書かれる→失敗する
の順になります。
引数がbのときは、 
	bが書かれる→失敗、後戻り発生→
		bが書かれる→成功する→
		後戻りが起これば→失敗する
の順です。

write/1 の効果は後戻りによって元に戻りませんから、 引数が a と b の場合で動作が異なります。 write(X) のところが副作用のない述語ならば、 引数 a と b については foo/1 は対称ですから同じ動作になるのは明らかです。

foo/1 の定義を書き換えて 

   foo(X) :- checka(X),write(X).
   foo(X) :- checkb(X),write(X).
とすれば、引数 a,b に対する動作は、副作用も含めて(foo/1 の外からみれば)同じになります。

さらに 

   foo(X) :- checkc(X),write(X).
の形の節がたくさんあると仮定します。この述語は一般的に、 引数の内容に従って処理を場合分けする方法のモデルになっています （たまたま、処理は全部同じです）。

このとき、引数 a に対する動作は a を出力するだけですが、 その後後戻りによって全部の節が調べられ、 checkb/1 や checkc/1 によって失敗します。 checka/1 や checkb/1 が場合分けとして排他的になっていれば、 失敗する節の探索は無駄な動作になります。これを排除するために、 Prolog には !(カット) という組込み述語があります。 !を使って foo/1 を書き直すと、 

    foo(X) :- checka(X),!,write(X).
    foo(X) :- checkb(X),!,write(X).
    foo(X) :- checkc(X),!,write(X).
! は、その ! よりも前にその節の中で残された代替節が 選択されないようにする記号です。 foo/1 自身の他に checka/1 にも代替節があれば、選択されないようになります。 ! 自身は組込み述語として成功します。

この ! を使うと、Prolog言語にいくつかの重要な記述力が付加されます。

  1. 場合分けを効率よく記述する。 
        頭部:- 条件1,!,処理.
    頭部:- 条件2,!,処理.
           ・
           ・
           ・
    の形の述語です。
  2. 否定を表現する。 
        頭部:- 条件,!,fail.
    頭部.
    の形では、必ず失敗する組込み述語fail を使って条件の否定を表現していま す。(条件が成功するときに限り失敗する) 同じことは組込み述語 not(または \+ ) でも表現できますが、これらは、 実は、!,fail を使って実現されています。
  3. 後戻りによるループの停止 
       repeat,処理,終了条件,!,・・・
    繰り返しのループを記述するために、 この形の本体部をしばしば利用します。repeat は組込み述語で 
            repeat.
        repeat :- repeat.
    と定義されています。これは、また、 
            repeat.
        repeat.
        repeat.
          ・
          ・
          ・
    と続く無限個の節と同等です。 repeat の目的は、代替節を限りなく提供することによって 後戻りによるループを実現することです。 

   repeat,read(X),process(X),X==end_of_file,!,....
は入力中のファイルから、項を1つずつ読みとって X とし、process/1 に 渡します。process/1 は必ず成功するものと仮定しますが、 その次の X==end_of_file が終了条件です。 == は項が同一であることを調べる組込み述語で、 X が end_of_file でなければ失敗します (end_of_file はファイルの終わりをあらわす項です)。 この失敗によって後戻りが起こりますが、process/1 に 代替節がなければ（組込み述語 read/1 にもないので）、repeat の 代替節が選択されて成功し、再び read(X),process(X) が実行されます。
X が end_of_file ならば、最後の ! が実行されて、repeat の 代替節が選ばれないようになるので、その後の後戻りによってループが 再開してしまうことがありません。

さらに、！を使用した場合の利害を述べておくと、

  1. 場合分けの実行効率がよくなり、スタックの使用量が減少する
  2. 否定、if-then-else型の制御構造や、副作用を伴うループの記述が可能になる
  3. しかし、述語の意味は論理的ではなくなってしまう
ことがあげられます。

再帰とリスト処理

再帰（recursion）とは、ある述語の中から直接、または間接的にその 述語自身を呼び出すことです。再帰を使うことで、 繰り返しを含むデータを扱うプログラムの記述が容易になります。 例えば、リストの要素を全部出力するプログラムは 
   write_list([E|L]) :- write(E),nl,write_list(L).
   write_list([]).
と定義できます。リスト[1,2,3] をこの述語に与えると、 
   write_list([1|[2,3]]) :- write(1),nl,write_list([2,3]).
   1を書いて改行する。

   write_list([2|[3]]) :- write(2),nl,write_list([3]).
   2を書いて改行する。

   write_list([3|[]]) :- write(3),nl,write_list([]).
   3を書いて改行する。

   write_list([]).
この順で実行されます。
リストそのものを次のように（再帰的に）定義されているデータ構造と考えます。
  1. []は、リストである（中身がない）。
  2. [E|L]は、Lがリストであればリストである。
この定義に従って場合分けをすれば、 write_list/1 の定義が自然であることがわかります

注意しておくべきことは、再帰の際にも選択された節の変数は まったく新しいものが一揃い用意されることです。 再帰的に呼ばれた側の節の変数EやLは、呼んだ側の変数EやLとは違うものです。

リストに限らず、Prologの唯一のデータ構造である複合項自身が 再帰的な構造を持っていることから、Prologプログラムでは 再帰的な構造をもつデータ構造をひんぱんに利用します。 このような構造を持つデータを扱う場合には、 再帰によって述語を自然な形で定義できます。

一つ上に戻る 目次に戻る