コンテンツにスキップ

Prolog/データタイプ

出典: フリー教科書『ウィキブックス(Wikibooks)』

Prologが扱うデータは(英: term)と呼ばれる。項は定数変数複合項のいずれかである。

  • 定数はアトム、数値のいずれか。
    • アトムは任意の名前を表す記号。変数と区別するため、英大文字か下線「_」で始まる場合はシングルクォートで囲む。 例: atomプロログ'This is atom'
    • 数値は整数や浮動小数点など。 例: 10243.14150xffff
  • 変数は英大文字か下線「_」で始まる記号で表す。通常の変数と無名変数がある。変数は任意の項と単一化(ユニフィケーション)できる。
    • 通常の変数は無名変数以外の変数。例: X _リスト
    • 無名変数は下線「_」のみから成る変数で、その出現ごとに異なった変数とみなす。1つの節で1回しか使われず内容を意識する必要のない変数に用いる。
  • 複合項は、「人間(ソクラテス)」のように、アトムの後にいくつかの引数をカッコで囲んで並べたもの。任意の項を引数として指定できる。
    • 通常の複合項 例: person(磯野波平,54) f(g(x),125)) '.'(X,L)
    • リスト リストは複合項の中でも特別な記法があたえられ、Prologプログラムで重用される。ここではその例を示すに止め、この後、別項を設けて詳しく述べる。 例: [namihei,sazae,masuo] [member, X, [1,2,3]]
    • 前置、中置、または後置記法された複合項 特別な複合項についての記述を参照。例: X+Y*3 死ぬ(X):-人間(X)

複合項でのアトム部分を関数子(英: functor)、引数の数をアリティ(英: arity)と呼ぶ。アトムはアリティが0個の複合項とみなすこともできる。アリティが異なれば同じ関数子でも別のものとして扱われる。アリティは英語に由来し、英語の語彙としても馴染みの少ないものであるが、適切な訳語が見つからず現在もこの表現が使われている。

前置・中置・後置記法された複合項は、複合項の関数子を前置・中置・後置記法の演算子として定義したものだが、これは表記法の問題でしかない。Prologではユーザが任意の演算子を定義できる。いくつかの演算子が事前に定義されており、例えば、算術式での"+","-","*","/"などが代表である。 X+Y*3 は実は複合項 '+'(X,'*'(Y,3)) として処理系に解釈され、そのような構造体を表現するものとして実装される。また、 死ぬ(X):-人間(X) ':-'(死ぬ(X),人間(X)) に等しい。このことから、Prologのプログラムは複数の項、すなわち述語 :- の集合、として記述されていると考えることができるため、プログラムをデータとしてProlog自身で処理することは比較的容易にできる。

ユーザが演算子を定義するには、組込述語op/3を使う。下記のようにプログラム中でop/3の実行して宣言を要求することもできるし、インタプリタのトップから ?- op(600,xfx,は). のように実行して直接宣言することもできる。opの第一引数は項の結合強度を、第二引数はオペレータの型を表す。演算子は第三引数で指定する。

死ぬ(X) :- 人間(X).

:- op(600,xfx,).
:- op(600,xfx,).

ソクラテス  人間.

X  Y :- X  Y.

X  死ぬ :- X  人間.

と定義すると、述語は は/2,が/2 に変わってしまって、全く別の定義だと言えるが、我々には意味的に同様のものと理解できる。これは中置記法の例であるが、以下のように、前置記法の"必ず"、後置記法の"ならば" を加えて意味的に補強することも可能だろう。( _ :- _ の中にその義を含むから、本来その必要はないが)

:- op(600,xfx,).
:- op(600,xfx,).
:- op(500,fx,必ず).
:- op(700,xf,ならば).

X  必ず 死ぬ :- X  人間 ならば.

Prologは動的型付き言語であり、型を宣言することはしない。論理変数は関数または述語の引数の中にしか現れず、この変数の型を指定する(例えば integer:X のような)記述をしたとしても、その変数を型に制約することはできない。

質問がなされ述語が呼び出された時に処理系は単一化のルールによって論理変数を可能であれば束縛するが、その際、型を検査することはしない。その引数が例えば、整数であるか、あるいは浮動小数点数に束縛されているかは、組込述語 integer/1 float/1 でそれを随時質問することによって検査することができるのみである。

リスト

[編集]

複合項の中で特別な扱いを受けているものとしてリストがあり、LISP以来の記号処理プログラミングの伝統に則りPrologでも極めて多用される。実際のところ、Prologのデータ構造は単位節定義とリスト以外にはないと言っても過言ではない。

リスト'はいくつかの項を順に並べたもので、その先頭要素を取り出せば、残りはまたリストであるというように再帰的である。例えば [a,b,5] のように、要素となる項を「,」で区切り「[」と「]」で囲った形で表現する。要素のないリストは [] と表記し、空リスト、あるいは nil と呼ぶ。

リストをグラフとして示すと、 リスト [a,b,5] の構造は

      . ------ . ------ . ------[]
      |        |        |
      a        b        5

のようになるだろう。

Prologのリストの表記として、要素を"|"で区切る方法がある。この記法があるためにPrologのリスト処理は視覚的で読みやすい。先頭からいくつかの要素の後に"|"が来て、その後にはリストか[]が来る。 例: [a,b,c,5,6] は、先頭の要素 a,bと残りの要素 [c,5,6] をつなげた [a,b|[c,5,6]] と等価である。 ただし、[[a,b]|[c,5,6]]ではない。Prologの複雑なリスト処理をそれでも宣言的と見なすことができるのは、専らこの記法あってのことである。

この記法はPrologのプログラムではリストを先頭要素と残りリストに分解する場合に多用される。[1,2,3]=[H|R]の場合、Hは単一の項(複合項であることも含めて)を表すパターンだから、H=1,R=[2,3] に分解される。後に示されるプログラム例の章には、リスト要素の加算,append,組合せ,クイックソート 他、多数の事例がある。重複するからここでは二例だけを示す。

member(H,[H|T]).
member(H,[_|T]) :- member(H,T).

append([],L,L).
append([H|X],L2,[H|Z]) :- append(T,L2,Z).

?-  member(H,[1,2,3]).
H = 1;
H = 2;
H = 3 .

Prologを代表する述語 member/2 の[H|T]と[_|T] と append/3の[H|X]と[H|Z] の所にこの記法が使われている。

 ?- member(H,[1,2,3]). にあっては、第一番目の定義節から

[1,2,3] が [1|[2,3]] に分解できて H = 1, T = [2,3] となるから、最初の解である

H = 1

が表示されるのである。

以下では、二つのリストを単一化することを通して、リスト記法の各部分がどのような関係にあるかの理解を深めよう。

?- [a,b,c,5,6] = [a,b|[c,5,6]].
true.

?- L = [c,5,6],
   [a,b,c,5,6] = [a,b|L].
true.

?- [a,b,c,5,6] = [a,b,c,5,6|[]].    % |の後に[]が来る。
true.

?- [a,b,c,5,6] = [[a,b]|[c,5,6]].
false.

?- [a,b,c,5,6] = [a,b|c,5,6].
false.

最後の例の[a,b|c,5,6]のc,5,6はリストと看做されない。

'|' を使ってリストを区切る用法もグラフ化すると、リスト [a|[b,c,5,6]] = [H|T] の構造は

    [ H   |    T ]

      . --|--- . ------ . ------ . ----- . -----[]
      |        |        |        |       |
      a        b        c        5       6

である。

リストは簡単に成長させることができる。

リストを成長させる(_追加要素,_リスト,[_追加要素|_リスト]).

?- リストを成長させる(3,[1,2],L).
L = [3,1,2].

リストを成長させる/3では単一化のからくりを巧みに使って、リストの先頭に要素を追加している。

リストの要素をひとつ切り取るには、反対に

リストの要素をひとつ切り取る([_切り取る要素|_リスト],_リスト).

?- リストの要素をひとつ切り取る([1,2,3],L).
L = [2,3].

リスト要素の切り貼りはこのようなパターンで行われる。リストは先頭から要素を加え、先頭から要素を検査し、先頭から要素を取り去るのに適したデータ構造を持っている。

ここまで示してきた通り、リストは読みやすいように特別な表記法を与えられた複合項であるが、実は一般の複合項と同様の構造で実現されている。 リストは関数子名が'.' と決められていて、以下の例のように実現されたアリティが2の複合項である。 例: [a,b] は複合項 '.'(a, '.'(b, [])) と等価である。

?- [a,b] = '.'(a, '.'(b, [])).
true.

形式記述言語の多くがそうであるように、Prologはその制御の大半が再帰処理によっている。リストは再帰的な構造データの中でも最も簡素で扱いやすいものであり、制御構造とデータ構造の一致という点からもリストが多用される十分な理由がある。

複合項もまた再帰的構造データではあるが、生成、分解、置換などの際の扱いが複雑になるため、グラフやオートマトンなどの定義/表示以外にはあまり使われない。'.'(a,'.'(b,[]))の構造で分る通り、リストも実は複合項である。リストは生成、分解、置換などが容易くできる構造を持つ特別な複合項であり、それ故に特別な表記法を与えて、さらなる便宜を供しているのである。


Prologではリストの内包表記はできないsetoffindall の表現が意味的にそれに近いが、ここでの表記をリストを表す項として、遅延して評価するために持ち回ることはできない。

例えば

?- findall(N,(member(N,[1,2,3,4]),0 is N mod 2)),L1),
   append(L1,[8,10],L).
L1 = [2,4],
L = [2,4,8,10].

であるが、findallを関数表現として、

?- L1 = findall(N,member(N,[1,2,3,4]),0 is N mod 2)),
   append(L1,[8,10],L).

と表記したとしても、この項だけ例外的に単一化を免れ関数評価する特別な機構を付加しない限り、この第一引数はリストと看做されることはなく、エラーとなり、Lに期待する [2,4,8,10] は得られない。このことから単一化がリストの内包表記を阻んでいる理由の一つであることが解る。

Prologには集合を表す特別な表現がなく、リストでこれを代用するのが普通である。この問題については、Prologプログラミングの 章で詳述する。