Wikipedia

「Prolog」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
つもりやもり (会話) による ID:80672465 の版を取り消し Wikibooks からの転載を取り消す。一応、記事の内部に Wikibooks へのリンクが張られているのであるが、これが帰属表示として認められるか分からないし、もし認められても Wikibooks の内容を Wikipedia に転記する必要はないと思われる。
タグ: 取り消し
21行目:
{{lang|en|'''Prolog'''}}（プロログ）は[[論理プログラミング|論理プログラミング言語]]の一つであり、該当分野で最もよく知られている論理型言語の代表格である。主に[[人工知能]]研究や[[計算言語学]]との関連性を持つ。[[定理証明系|定理証明]]、[[エキスパートシステム]]、[[自動計画]]、[[自然言語処理]]とも繋がりが深い。[[一階述語論理]]と[[数理論理学|形式論理]]を基礎にして、事実群と規則群の表現および[[関数 (数学)|関係]]の観点に立った[[宣言型プログラミング|宣言型パラダイム]]に準拠しており、その[[関数 (数学)|関係]]に則った質問によって計算が開始されるという性質を持つ。
 
Prologは、1972年に[[マルセイユ大学]]のアラン・カルメラウアーとフィリップ・ルーラッセルによって開発された。フランス語の「''{{lang|fr|'''pro'''grammation en '''log'''ique}}''」がその名の由来である<ref>Alain Colmerauer, Philippe Roussel. ''The birth of Prolog'', p.2.</ref>。Prologの誕生には[[エディンバラ大学]]のロバート・コワルスキが考案した[[ホーン節]]が大きく寄与している。カルメラウアーによる元祖版はマルセイユPrologと呼ばれている。その後、コワルスキの門弟のデービヴィッド・H・D・ウォワーレンが1977年に改訂開発したエディンバラProlog（DEC-10 Prolog）が標準になってPrologは広く普及した<ref name="Kowalski1974">Robert Kowalski. ''The Early Years of Logic Programming'', p.38.</ref>。
 
== 概要 ==
168行目:
 
== Prologプログラム例 ==
 
{{Wikibooks|Prolog|Prolog}}
=== クイックソート ===
<syntaxhighlight lang="prolog">
quicksort([],[]).
quicksort([X|Xs], Ys) :-
partition(Xs, X, Smaller, Bigger),
quicksort(Smaller, L1),
quicksort(Bigger, L2),
append(L1, [X|L2], Ys).
 
 
partition([], _, [], []).
partition([X|Xs], Pivot, [X|Smalls], Bigs) :-
X @< Pivot,
partition(Xs, Pivot, Smalls, Bigs).
partition([X|Xs], Pivot, Smalls, [X|Bigs]) :-
X @>= Pivot,
partition(Xs, Pivot, Smalls, Bigs).
 
</syntaxhighlight>
<code>Pivot</code>とは軸要素のことである。軸要素より小さい要素を整列、軸要素より大きい要素も整列。それを軸要素を挟んで結合したものが整列したリストだ。実行例はこうなる。<syntaxhighlight lang="Prolog">
?- quicksort([3,2,1,6],L).
 
L = [1,2,3,6]
 
</syntaxhighlight>
 
=== ハノイの塔 ===
[[ハノイの塔]]は最も {{lang|en|Prolog}} 向きの課題のひとつとして知られる。ここでは、N枚の円盤を三本の柱のうち、一番左の柱から右の柱に移すケースを示す。円盤は下から上に向かうほど小さくなるように積まれ、常にその状態が維持されなくてはならない。
<syntaxhighlight lang="prolog">
:- op(500,xfx,から).
:- op(400,xf,へ).
 
ハノイの塔(N,_移動履歴) :-
length(Ln,N),
ハノイの塔(Ln,左柱,中柱,右柱,_移動履歴).
 
ハノイの塔([_],_左,_中,_右,[_左 から _右 へ]).
ハノイの塔([_|Ln],_左,_中,_右,_移動履歴) :-
ハノイの塔(Ln,_左,_右,_中,_移動履歴_1),
ハノイの塔(Ln,_中,_左,_右,_移動履歴_2),
append(_移動履歴_1,[_左 から _右 へ|_移動履歴_2],_移動履歴).
</syntaxhighlight>
冒頭、<code>から</code> を中置演算子、<code>へ</code> を後置演算子として定義している。それを使って <code>_移動前の位置</code> から <code>_移動後の位置</code> という項を表現して、それを履歴として残している。このプログラムは {{lang|en|Prolog}} が宣言的であることを顕著に示す好例である。この述語で述べられていることは、三回が一組となって同じパターンが繰り返されるということ。さらに最も下の一枚が順に、この課題では右柱に積まれるのだが、新しい最下層の円盤が右柱の最上位に積まれた時には、それより上の塔は中柱、左柱と交互に完全に積み上がっている。それを、[[ハノイの塔]]述語の本体の二番目の副目標で、どちらの柱を起点として以後の移動を開始するかを、引数の位置を入れ替えることだけによって、表現している。このように全体の骨格と僅かな引数の置き換えだけによって、手続的動作の全てを暗示している。このような表現力に対して「宣言的」と言うのである。実行例はこうなる。<syntaxhighlight lang="prolog">
?- ハノイの塔(4,L),
member(A,L),
writef('%t\n',[A]),
fail;
true.
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
左柱 から 中柱 へ
右柱 から 左柱 へ
右柱 から 中柱 へ
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
中柱 から 左柱 へ
右柱 から 左柱 へ
中柱 から 右柱 へ
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
true.
</syntaxhighlight>
 
=== nクイーン ===
nクイーン問題も {{lang|en|Prolog}} 向き問題の代表のひとつである。チェス盤が8×8であることから、8クイーンとして課題になることが多いが、ここでは盤面の大きさを一般化したnクイーンである。チェスのクイーンは縦横斜め、盤面の自分の位置から盤面の端までが全て利き筋となる駒である。この駒を各行に適宜ひとつずつ配置して、全てのクイーンの利き筋に他のクイーンがいないように、全ての列にクイーン配置せよという問題である。一つの解は列番号のリストで得られる。nクイーンの {{lang|en|Prolog}} 定義は随分と工夫され、多くの作品がある。ここでは最も一般的な戦略の解法を示す。駒の利き筋という概念を示すために、可能な限り説明的な {{lang|en|Prolog}} をコードを試みている。途中に現れる <code>Qs</code> という論理変数に、一つずつ解候補のクイーン位置が成長していく。
<syntaxhighlight lang="prolog">
nクイーン(_nクイーン,_一解) :-
'1からnまでの数リストを得る(縦横の利き筋検査はこれを行ごとに一つずつ選択することで回避される)'(_nクイーン,_数リスト),
行ごとに順に駒を置き利き筋を調べて一解を得る(_数リスト,[],_一解).
 
行ごとに順に駒を置き利き筋を調べて一解を得る([],_一解,_一解).
行ごとに順に駒を置き利き筋を調べて一解を得る(_位置リスト,Qs,_一解) :-
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(_駒の位置,
_位置リスト,_残り駒の位置リスト),
斜めの利き筋に駒はない(_駒の位置,1,Qs),
行ごとに順に駒を置き利き筋を調べて一解を得る(_残り駒の位置リスト,[_駒の位置|Qs],_一解).
 
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(_駒の位置,
[_駒の位置|_残り駒の位置リスト],_残り駒の位置リスト).
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(X,[H|T],[H|T1]) :-
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(X,T,T1).
 
斜めの利き筋に駒はない(_,_,[]).
斜めの利き筋に駒はない(Q,_隔たり,[Q1|Qs]) :-
Q + _隔たり =\= Q1,
Q - _隔たり =\= Q1,
_隔たり_2 is _隔たり + 1,
斜めの利き筋に駒はない(Q,_隔たり_2,Qs).
 
'1からnまでの数リストを得る(縦横の利き筋検査はこれを行ごとに一つずつ選択することで回避される)'(_nクイーン,_数リスト) :-
findall(M,between(1,_nクイーン,M),_数リスト).
</syntaxhighlight>
これは非決定的な述語である。上記の定義では、表示幅の制限から引数の途中で改行している部分があるが、引数の区切りである「<code>,</code>」の前後であるならば、これは構わない。6クイーンの場合の実行例を示す。<syntaxhighlight lang="prolog">
?- nクイーン(6,L).
L = [5, 3, 1, 6, 4, 2] ;
L = [4, 1, 5, 2, 6, 3] ;
L = [3, 6, 2, 5, 1, 4] ;
L = [2, 4, 6, 1, 3, 5] ;
false.
</syntaxhighlight>
ここでは4つの解が得られたが、8クイーンだと92解になる。
 
== 処理系 ==
「https://ja.wikipedia.org/wiki/Prolog」から取得