Prolog/データタイプ
Prologが扱うデータは項(英: term)と呼ばれる。項は定数、変数、複合項のいずれかである。
複合項でのアトム部分を関数子(英: 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).を
と定義すると、述語は は/2,が/2 に変わってしまって、全く別の定義だと言えるが、我々には意味的に同様のものと理解できる。これは中置記法の例であるが、以下のように、前置記法の"必ず"、後置記法の"ならば" を加えて意味的に補強することも可能だろう。( _ :- _ の中にその義を含むから、本来その必要はないが)
Prologは動的型付き言語であり、型を宣言することはしない。論理変数は関数または述語の引数の中にしか現れず、この変数の型を指定する(例えば integer:X のような)記述をしたとしても、その変数を型に制約することはできない。
質問がなされ述語が呼び出された時に処理系は単一化のルールによって論理変数を可能であれば束縛するが、その際、型を検査することはしない。その引数が例えば、整数であるか、あるいは浮動小数点数に束縛されているかは、組込述語 integer/1 float/1 でそれを随時質問することによって検査することができるのみである。
複合項の中で特別な扱いを受けているものとしてリストがあり、LISP以来の記号処理プログラミングの伝統に則りPrologでも極めて多用される。実際のところ、Prologのデータ構造は単位節定義とリスト以外にはないと言っても過言ではない。
リスト'はいくつかの項を順に並べたもので、その先頭要素を取り出せば、残りはまたリストであるというように再帰的である。例えば [a,b,5] のように、要素となる項を「,」で区切り「[」と「]」で囲った形で表現する。要素のないリストは [] と表記し、空リスト、あるいは nil と呼ぶ。
リストをグラフとして示すと、 リスト [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,組合せ,クイックソート 他、多数の事例がある。重複するからここでは二例だけを示す。
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] となるから、最初の解である
が表示されるのである。
以下では、二つのリストを単一化することを通して、リスト記法の各部分がどのような関係にあるかの理解を深めよう。
最後の例の[a,b|c,5,6]のc,5,6はリストと看做されない。
'|' を使ってリストを区切る用法もグラフ化すると、リスト [a|[b,c,5,6]] = [H|T] の構造は
である。
リストは簡単に成長させることができる。
リストを成長させる/3では単一化のからくりを巧みに使って、リストの先頭に要素を追加している。
リストの要素をひとつ切り取るには、反対に
リスト要素の切り貼りはこのようなパターンで行われる。リストは先頭から要素を加え、先頭から要素を検査し、先頭から要素を取り去るのに適したデータ構造を持っている。
ここまで示してきた通り、リストは読みやすいように特別な表記法を与えられた複合項であるが、実は一般の複合項と同様の構造で実現されている。 リストは関数子名が'.' と決められていて、以下の例のように実現されたアリティが2の複合項である。 例: [a,b] は複合項 '.'(a, '.'(b, [])) と等価である。
形式記述言語の多くがそうであるように、Prologはその制御の大半が再帰処理によっている。リストは再帰的な構造データの中でも最も簡素で扱いやすいものであり、制御構造とデータ構造の一致という点からもリストが多用される十分な理由がある。
複合項もまた再帰的構造データではあるが、生成、分解、置換などの際の扱いが複雑になるため、グラフやオートマトンなどの定義/表示以外にはあまり使われない。'.'(a,'.'(b,[]))の構造で分る通り、リストも実は複合項である。リストは生成、分解、置換などが容易くできる構造を持つ特別な複合項であり、それ故に特別な表記法を与えて、さらなる便宜を供しているのである。
Prologではリストの内包表記はできない。setof や findall の表現が意味的にそれに近いが、ここでの表記をリストを表す項として、遅延して評価するために持ち回ることはできない。
例えば
であるが、findallを関数表現として、
と表記したとしても、この項だけ例外的に単一化を免れ関数評価する特別な機構を付加しない限り、この第一引数はリストと看做されることはなく、エラーとなり、Lに期待する [2,4,8,10] は得られない。このことから単一化がリストの内包表記を阻んでいる理由の一つであることが解る。
Prologには集合を表す特別な表現がなく、リストでこれを代用するのが普通である。この問題については、Prologプログラミングの 章で詳述する。