Prolog

出典: Wikipedio


プライバシー・ポリシー Wikipedioについて 免責事項 Template:Infobox プログラミング言語

Template:プログラミング言語 Prologプロログ)は非手続き型プログラミング言語の一つ。論理型言語に分類される。名称はProgramming in Logic の略。 1972年ごろにフランスのアラン・カルメラウアーとフィリップ・ルーセルによって考案された<ref>Robert Kowalski, The Early Years of Logic Programming より</ref>。プログラム一階述語論理に基づいてデータ間の関係を示す命題として記述され、処理系がそれらにパターンマッチングユニフィケーション)を施しながら、与えられた命題が成立するか再帰的手続きによって探索する。 人工知能におけるトップ・ダウン式の問題解決と相性が良いために、人工知能研究とエキスパートシステムの実現のための主要言語として広く採用された。

Prologのもととなる演繹手法は導出と呼ばれ、自動定理証明の研究においてProlog開発以前よりよく知られていた。Prologは、導出において節を以下に述べる頭部が一つの命題からのみなるホーン節に限定したものととらえる事が出来る。 

第五世代コンピュータ(→人工知能)最初の個人用逐次推論マシン PSI のオペレーティングシステム SIMPOS を記述するために、Prologにオブジェクト指向プログラミングを取り入れた ESP が使われた。ついで、並列推論マシン PIM のために、Guarded Horn Clauses(GHC)に基づく並列演算処理を追加したKL1が設計された。

目次

基本的な言語仕様

プログラムは、ホーン節、もしくは単に節と呼ばれる形式の項を並べたもの。節は、頭部と本体部からなり、

頭部.

または

頭部 :- 本体部.

これは、それぞれ「AはBである」、「BならばCである」という命題の形式に対応する。Prologの処理系は、人間が入力した命題と一致する節があるか調べ、あった場合はその本体部に記述されている命題と一致する節があるか再帰的に調べる。

例として「ソクラテスは人間である」「人間は死ぬ」をPrologで記述すると以下のようになる。ここでXは変数である。

人間(ソクラテス).
死ぬ(X) :- 人間(X).

システムに対して以下のように入力すると、trueが返される。

?- 死ぬ(ソクラテス).

これは「ソクラテスは死ぬか」と質問したことに対して、システムが内部で推論を行なって、既知の知識から答えを出したものである。

以下のように入力すると、「死ぬのは誰か」と質問したことと同じになる。この場合もシステムが内部で推論を行なって、死ぬ(X)を満たすXを表示する。

?- 死ぬ(X).
X=ソクラテス

一般の手続き型言語と異なり、Prologは複数の計算結果がありうる。先のプログラム例を拡張して

人間(ソクラテス).
人間(アリストテレス).
死ぬ(X) :- 人間(X).

とした場合、死ぬ(X)を満たすXは複数(ソクラテスとアリストテレス)がありうる。多くのProlog 処理系ではこのような複数解が存在する時に新たな解を得る場合は

?- 死ぬ(X).
X=ソクラテス  ;
X=アリストテレス

と";"(セミコロン)記号を用いて他の解を得る。このような非決定性がコンピュータ言語としてのPrologの特徴の一つである。

もうすこし具体的なPrologプログラムの例を以下に示す。"%"以降はコメントである。 <source lang="prolog"> % member(X,Y)はXがリストYの要素として含まれている時に成功する。 % そうでないときは失敗する。

member(X, [X|_]).  % Xがリストの先頭要素と同じ場合 member(X, [_|Y]) :- member(X, Y).  % それ以外の場合 </source>

member(X,Y) は要素XがリストYのメンバーであるかを調べるプログラムであると同時に、「要素XがリストYのメンバーである」という関係も宣言的に表している。実行例を以下に示す。

要素XがリストYのメンバーであれば成功する。 <source lang="prolog"> ?- member(サザエ, [波平,サザエ,マスオ]). Yes </source>

要素XがリストYのメンバーでなければ失敗する。 <source lang="prolog"> ?- member(サザエ, [ワカメ,マスオ,タラオ]). No </source>

Xを変数のままにすると、リストYのメンバーである要素が結果として返る。 <source lang="prolog"> ?- member(X, [ワカメ,マスオ,タラオ]). X = ワカメ ; X = マスオ ; X = タラオ </source>

二つのリストの共通メンバーを求めるには単純に","で区切って並べればよい。この","はANDの意味を持つ。 <source lang="prolog"> ?- member(X, [波平,サザエ,マスオ]), member(X, [ワカメ,マスオ,タラオ]). X = マスオ </source>

要素Xを指定しリストYを変数のままにすると、それらがメンバーであるリストが結果として返る。 <source lang="prolog"> ?- member(波平, Y), member(サザエ, Y), member(マスオ, Y). Y = [波平,サザエ,マスオ|_G001] </source> 上の"_G001"はProlog処理系が作成した仮の変数で、リストの後半が不定であることを示す。

データタイプ

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

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

複合項でのアトム部分を関数子 (Functor)、引数の数をアリティ (Arity) と呼ぶ。アトムはアリティが0の複合項とみなすこともできる。アリティが異なれば同じ関数子でも別のものとして扱われる。

特別な複合項について:

"リスト"はいくつかの項を順に並べたもので、例えば [a,b,5] のように、要素となる項を","で区切り"["と"]"で囲った形で表現する。要素のないリストは "[]" と表記し、空リスト、あるいは nil と呼ぶ。リストは関数子名が'.' でアリティが2の複合項の特別な表記法と見なされる。 例: [a,b] は複合項 '.'(a, '.'(b, [])) と等価

なお、リストの表現方法として、先頭の要素と残りの要素とを"|"で区切って表現する方法もある。Prologでリスト処理を行う場合に多用される。 例: [a,b,5] は、先頭の要素 aと残りの要素 [b,5] をつなげた [a|[b,5]] と等価

"前置、中置、または後置記法された複合項"は、複合項の関数子を前置、中置、または後置記法の演算子として定義したもの。Prologではユーザが任意の演算子を定義できる。いくつかの演算子が事前に定義されており、例えば、算術式 X+Y*3 は複合項 '+'(X,'*'(Y,3)) として解釈される。また、 死ぬ(X):-人間(X) ':-'(死ぬ(X),人間(X)) に等しい。Prologのプログラムはすべて複数の項としても表現できるため、プログラムをデータとしてProlog自身で処理することは比較的容易にできる。

Prologプログラミング

述語

Prologでプログラムを記述する単位は述語 (Predicate) で、他の言語での関数やサブルーチンに相当する。つまり、Prologプログラムは述語の集まりで、述語はあるまとまった機能を表現している。述語は1つ以上の (Clause) と呼ばれる項からできている。節は以下の形をしている。

頭部 :- ゴール1, ..., ゴールn.

あるいは、

頭部.

1つの述語に属する節は、同じ述語名(関数子名)と引数の数(アリティ)を持つ頭部からできている。述語名とアリティが異なれば別の述語とみなすため、述語を指定するときは"述語名/アリティ"と表記されることもある (例: member/2) 。 1つの述語は成功、あるいは失敗のいずれかの結果を返す。ゴール1~ゴールnの間の "," はANDを意味する演算子であり、1つの節が成功するのは本体部がすべて成功した場合である。本体部の実行は左から右に行われる。頭部のみの節は 頭部 :- true. と同じ意味である。

1つの述語が複数の節からなる場合、上から順に実行され、どれかが成功したら述語自体は成功する。つまり同じ述語内の節の関係はORの関係となる。

宣言的意味と手続き的意味

Prologの基本的なアイデアは、ホーン節をプログラムと見なして実行する、ということであるため、純粋なPrologのプログラムは手続き的にもホーン節に従って宣言的にも解釈ができる。1つの節の解釈は以下のようになる。

"ゴール1"かつ ...、かつ"ゴールn"が真であれば、"頭部"は真である     (宣言的意味)
"頭部"であることを示すには、"ゴール1"かつ...、かつ"ゴールn"を示す  (手続き的意味)

手続き的に見ると、"ゴール1"~"ゴールn"がすべて成功する場合、節は本体部を順番に実行する関数やサブルーチンのように見なせ、再帰呼び出し可能な手続き型/関数型言語と動きはさほど違わない。他の言語との大きな違いは、本体部のいずれかが失敗した場合、最後に選択した節にバックトラックし次の節から再度実行を続けることである。 また、Prologの動作をプログラムが指定した条件での解の探索として見ると、深さ優先の解探索ととらえることができる。

論理変数

C言語など通常のプログラミング言語の変数は値の格納場所であって、計算が進むに従って内容が変化する。Prologなどの論理型言語での変数は数学的な変数に近いもので、何らかの値につけた名前である。値は決まっているか決まっていないかのいずれかで、一度決まってしまえば値が変わることはない。値が変わるのはバックトラックにより前回の値が消されたのちに再度値が決まった場合のみである。通常のプログラミング言語の変数と区別するために論理変数と呼ばれることもある。

変数の値の変化の例: <source lang="prolog"> ?- X=Y, Y=Z, Z=3. X = 3, Y = 3, Z = 3 Yes

?- W=5, W=3. No </source>

ユニフィケーションとバックトラック

Prologの動作の基本はユニフィケーションバックトラックである。ユニフィケーションとは双方向のパターンマッチで、述語の呼び出し時に使用される。

特定の述語を呼び出すと、処理系はその述語の節のうちで頭部がユニフィケーションできるものを上から順に探し、ユニフィケーションが成功すると、その節の本体部の述語が順番に呼び出す。実行が失敗すると直前に選択した節にバックトラック(後戻り)して次の節で再度実行を試みる。 たとえば、以下の述語に対して、 <source lang="prolog"> member(X, [X|_]).  % Xがリストの先頭要素と同じ場合 member(X, [_|Y]) :- member(X, Y).  % それ以外の場合 </source> 以下の member(Z, [ワカメ,マスオ]) というゴールを指定すると結果は次のようになる (";"を1回入力しバックトラックを行わせた例) 。 <source lang="prolog"> ?- member(Z, [ワカメ,マスオ]). Z = ワカメ  ; Z = マスオ </source> まず最初の節の頭部 member(X, [X|_]) でユニフィケーションが成功し、 Z=ワカメ member/2 自体も成功する。 この状態でバックトラックを行わせると、次の節である2番目の節の頭部 member(X, [_|Y]) でユニフィケーションが成功し、その本体部を member(Z, [マスオ]) として実行することになる。これは、最初の節の頭部 member(X, [X|_]) でユニフィケーションが成功し、 Z=マスオ member/2 は成功する。

通常のプログラミング言語との比較で考えると、Prologのユニフィケーションは以下の機能を含んでいる。

  • 変数への値のアサイン
  • パラメータの受け渡し
  • リストの作成/リストの分解/リスト各要素の読み出し・設定
  • 複合項(通常言語での構造体やレコード)の値の読み出し/値の設定
  • 条件分岐(通常言語のif文やswitch文)

バックトラックは通常のプログラミング言語にはない機能だが、強いて言うと以下の機能を含む。

  • ループ(通常言語のfor,while等)
  • 探索機能

ループの簡単な例を以下に示す。この例ではリストの先頭から0以上100以下の数値が見つかるまで繰り返す。 <source lang="prolog"> ?- member(X, [3000, 1254, -2, 3598, 88, 9618]), X>=0, X=<100. X = 88 </source>

数式

X+Y*3 などの数式は単なる項にすぎず、そのままでは評価されない。数式を評価するには"is"などの述語を使う。以下にいくつかの述語の例を示す。

  • X is Y  :評価とユニフィケーションをおこなう
  • X = Y  :ユニフィケーションをおこなう
  • X=:=Y  :評価と比較をおこなう
  • X == Y  :比較をおこなう

<source lang="prolog"> ?- X is 3+5. X = 8 YES

?- X = 3+5. X = 3+5 YES

?- 3+5 =:= 2+6. YES

?- 3+5 == 2+6. NO

?- 3+5 == 3+5. YES </source>

カットと否定

Prologは一階述語論理をベースにしているが、実用的なプログラミングのため、述語論理の範囲外の機能も用意されている。カットや否定の組み込み述語はその例である。

Prologのバックトラックは強力な機能だが、実際のプログラムでは不要なバックトラックを制限したい場合もある。"!" (カット) はバックトラックを制限するための述語である。カットが最初に実行された時には無条件で成功するが、バックトラックでカットに制御が戻ってきたとき、カットを含む述語は無条件に失敗する。つまり、1つの述語内でカット以前に制御が戻ることはない。 たとえば、通常のプログラミング言語での if p then q else r の動きは、カットを使って以下のように書ける。 <source lang="prolog"> x :- p, !, q. x :- r. </source> 通常のProlog処理系では、バックトラックで戻ってくる場合に備えて、それまでに実行した各ゴールの情報や値を設定した変数をメモリ上に記憶している。カットを実行するとそれらのうち不要な情報を開放することができるため、カットは使用メモリの削減にもつながる。

実行結果の否定のためには述語"\+"が用意されている。 \+(P) はゴールPが成功したときに失敗し、失敗したとき成功する。この述語は本当の否定 "Pは偽である" ではなく "Pは証明できない" という失敗による否定で、ある種の非単調論理による推論を行う。これは以下のように定義した述語と同じ動きをする。ここで fail は必ず失敗する述語である。 <source lang="prolog"> \+(P) :- P, !, fail. \+(_). </source>

高階述語とメタインタプリタ

Prologの述語はPrologの基本データタイプである項で表現でき、述語自身の引数として別の述語を与える高階述語を作成できる。

たとえば、引数で述語を与えそれを単純に実行させたい場合、ゴールとして変数をそのまま書けばいい。 <source lang="prolog"> eval(P) :- P. </source>

任意の述語を実行時に作成して実行することができるため、リストのすべての要素に特定の述語を適応し結果のリストを返す maplist/2 や、リストの要素を与えられた述語の結果で選択する sublist/3 などの高階述語を容易に作成できる。同様の高階述語には findall/3 setof/3 bagof/3 などがある。

また、純粋なPrologのメタインタプリタは以下のように書ける。 clause(P, Q) は頭部が P にユニフィケーション可能な節の本体部 Q を取得する述語である。 <source lang="prolog"> execute(true)  :- !.  % trueならば成功 execute((P,Q)) :- !, execute(P), execute(Q).  % P1,... ,Pnの各要素を左から順に試みる execute(P)  :- clause(P, Q), execute(Q).  % ゴールPの定義を取得し、本体Qを試みる </source>

データとプログラムの形式が同じであることや、任意の演算子がユーザ定義可能なこと、Prolog自身が強力な構文解析機能を持つことなどもあり、このようなメタインタプリタをもとにPrologの一部機能を拡張した別言語のインタプリタを作成することは、比較的容易である。

構文解析

Prologは構文解析を行うのに向いたプログラミング言語である。元々、Prologは論理を利用した自然言語処理のために開発された<ref>Alain Colmerauer and Philippe Roussel, The birth of Prolog より</ref>。実際、文脈自由文法トップダウン構文解析の動きはProlog自身の動きと同じである。

限定節文法

Prologには限定節文法 (Definite Clause Grammar) と呼ばれる特別な表記法が用意されている。文脈自由文法を拡張したもので、文法を記述する場合は  :-/2 ではなく -->/2 を用いる。 <source lang="prolog">

head --> body.

</source> 文法での非終端記号はPrologの項で、終端記号は非終端記号と区別するためリスト内の項で表現する。付加的な条件や動作を指定したい場合、文法の最後に任意のProlog述語を { } で囲んで記述する。限定節文法の例を以下に示す。この例では数式を解析し計算を行う。

<source lang="prolog"> expression(E) --> term(X), [+], expression(Y), {E is X + Y}. expression(E) --> term(X), [-], expression(Y), {E is X - Y}. expression(E) --> term(E).

term(T) --> num(X), [*], term(Y), {T is X * Y}. term(T) --> num(X), [/], term(Y), {T is X / Y}. term(T) --> num(T).

num(N) --> [+], num(N). num(N) --> [-], num(X), {N is -X}. num(N) --> [N], {number(N), between(0, 9, N)}. </source>

これはバッカス・ナウア記法で書かれた以下の文法規則に計算の動作を付加したものと同じ意味を持つ。

<expression> ::=  <term> "+" <expression> | <term> "-" <expression> | <term>
<term>       ::=  <num> "*" <term> |  <num> "/" <term> |  <num>
<num>        ::=  "+" <num> | "-" <num> | 0..9

実行結果は以下のようになる。 <source lang="prolog"> ?- expression(Z,[-, 2, +, 9, *, 2, +, 3, *, 5],[]). Z = 31 </source> このように直接計算を行うのではなく抽象構文木を作成するような文法規則を作成することもできる。構文木はPrologの項として素直に表現できるため、その後の機械語へのコンパイルや最適化などを行うことも可能である。

実際には、限定節文法の文法規則はProlog節を見やすくするためのシンタックスシュガーで、他のプログラミング言語でのマクロ展開のように、文法規則読み込み時にPrologの述語に変換される。変換規則は expand_term/2 で定義されている。たとえば、 p(X,Y) --> q(X), r(X,Y), s(Y). の文法規則は p(X,Y,S0,S) :- q(X,S0,S1), r(X,Y,S1,S2), r(Y,S2,S). の節に変換され、付加された変数間で解析の情報が受け渡される。

プログラム例

Prologのプログラム例を以下に示す。

Hello world

実行例は以下の通り。 <source lang="prolog"> ?- write('Hello world!'), nl. Hello world!

Yes ?- </source>

クイックソート

与えられたリストをソートするクイックソートのプログラム例を示す。 <source lang="prolog"> partition([], _, [], []). partition([X|Xs], Pivot, Smalls, Bigs) :-

   (   X @< Pivot ->
       Smalls = [X|Rest],
       partition(Xs, Pivot, Rest, Bigs)
   ;   Bigs = [X|Rest],
       partition(Xs, Pivot, Smalls, Rest)
   ).

quicksort([]) --> []. quicksort([X|Xs]) -->

   { partition(Xs, X, Smaller, Bigger) },
   quicksort(Smaller), [X], quicksort(Bigger).

</source>

チューリングマシン

Prologのチューリング完全性は、チューリングマシンをシミュレートすることで示すことができる。 <source lang="prolog"> turing(Tape0, Tape) :-

   perform(q0, [], Ls, Tape0, Rs),
   reverse(Ls, Ls1),
   append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, Rs0, Rs) :-

   symbol(Rs0, Sym, RsRest),
   once(rule(Q0, Sym, Q1, NewSym, Action)),
   action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
   perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []). symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). action(stay, Ls, Ls, Rs, Rs). action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]). left([L|Ls], Ls, Rs, [L|Rs]). </source>

以下のルールは簡単なチューリングマシンの例である。状態遷移と動作をPrologの節として表現している。 <source lang="prolog"> rule(q0, 1, q0, 1, right). rule(q0, b, qf, 1, stay). </source> このチューリングマシンは単進符号化("1"の並びで符号化)した数値に1を加える。つまり、任意個の"1"のセル上をループし、最後に"1"を追加する。 <source lang="prolog"> ?- turing([1,1,1], Ts). Ts = [1, 1, 1, 1] ; </source> この例から、状態間の関係をPrologで表現することで、任意の計算が状態遷移のシーケンスとして宣言的に表現できることが分かる。

動的計画法

以下のPrologプログラムは動的計画法 (dynamic programming) を使って2つのリストの最長共通部分列問題 (Longest Common Subsequence) を多項式時間で求める。Prolog節によるデータベースを部分計算の結果のメモ化に用いている。 <source lang="prolog">

- dynamic(stored/1).

memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).

lcs([], _, []) :- !. lcs(_, [], []) :- !. lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)). lcs([X|Xs], [Y|Ys], Ls) :-

   memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
   length(Ls1, L1), length(Ls2, L2),
   (   L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

</source>

実行例: <source lang="prolog"> ?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls). Ls = [m, j, a, u] </source>

処理系

多くの処理系はPrologの基本機能以外に、制約プログラミング並行プログラミングのための拡張機能やConstraint Handling Rulesなどの各種言語をライブラリとして含んでいる。

国際会議

  • INAP International Conference on Declarative Programming and Knowledge Management

参考文献

Template:Refbegin

  • William F. Clocksin, Christopher S. Mellish: Programming in Prolog: Using the ISO Standard. Springer, 5th ed., 2003, ISBN 978-3540006787.
  • Leon Sterling and Ehud Shapiro, The Art of Prolog: Advanced Programming Techniques, 1994, ISBN 0-262-19338-8.
  • D.L. Bowen, L. Byrd, F.C.N. Pereira,L.M. Pereira and David H.D. Warren: DECsystem-10 PROLOG USER'S MANUAL, University of Edinburgh,1982.
  • ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva.
  • Robert Kowalski, The Early Years of Logic Programming, CACM January 1988.
  • Alain Colmerauer and Philippe Roussel, The birth of Prolog, in The second ACM SIGPLAN conference on History of programming languages, p. 37-52, 1992.
  • David H D Warren, Luis M. Pereira and Fernando Pereira, Prolog - the language and its implementation compared with Lisp. ACM SIGART Bulletin archive, Issue 64. Proceedings of the 1977 symposium on Artificial intelligence and programming languages, pp 109 - 115.

Template:Refend <references/>

関連項目

ar:برولوغ ast:Prolog bat-smg:Prolog bg:Пролог (език за програмиране) ca:Prolog cs:Prolog (programovací jazyk) da:Prolog (programmeringssprog) de:Prolog (Programmiersprache) el:Prolog en:Prolog eo:Prolog es:Prolog et:Prolog fi:Prolog fr:Prolog gl:Prolog he:פרולוג (שפת תכנות) hu:Prolog id:Prolog io:Prolog is:Prolog (forritunarmál) it:Prolog jbo:prolog ko:프롤로그 lt:Prolog ms:Prolog nl:Prolog no:Prolog (programmeringsspråk) pl:Prolog (język programowania) pt:Prolog ro:Prolog ru:Пролог (язык программирования) sk:Prolog sl:Prolog sv:Prolog (programmeringsspråk) ta:புரொலாக் tg:Пролог (забони барноманависӣ) th:ภาษาโปรล็อก tr:Prolog uk:Пролог (мова програмування) zh:Prolog

個人用ツール