14

Ulle Endrissの講義ノートを読んで、Prologプログラミングの感触をつかもうとしています。エクササイズの解決策が期待どおりに機能しない場合、適切な説明をするのは難しいと思います。これは、Prologが式を評価する方法についての私の不安定な理解と関係があると思います。

last120ページの演習2.6では、組み込みの述語のように動作する述語の再帰的な実装が必要lastです。私の試みは次のとおりです。

last1([_ | Rest], Last) :- last1(Rest, Last).
last1([Last], Last).

正解ですが、複数の要素を含むリストの場合、クエリを終了するにはセミコロンを入力する必要があります。これはlast1、組み込みのとは異なりlastます。

?- last1([1], Last).
Last = 1.

?- last1([1, 2], Last).
Last = 2 ;
false.

ルールとファクトを宣言した順序を切り替える場合は、どちらの場合もセミコロンを入力する必要があります。

last1私は、Prologがそれがもう1つの解決策（したがってセミコロン）を持っているかもしれないと考える理由を知っていると思います。評価シーケンスに従っていると思います

last1([1, 2], Last).
==>  last1([2], Last).
==>  last1([], Last).    OR    Last = 2.
==>  false    OR    Last = 2.

Restこれは、との一致を回避する方法を探す必要があることを示唆しているよう[]です。とにかく、宣言の順序を切り替えることがなぜ効果があるのか​​、私には説明がありません。

質問1： の振る舞いの正しい説明は何last1ですか？

質問2：last1組み込みと区別がつかない 述語を実装するにはどうすればよいlastですか？

4

3 に答える 3

13

質問1：

Prologシステムは、条項を実行する前に、条項が適用されるかどうかを常に判断できるとは限りません。正確な状況は実装に依存します。つまり、一般的にその決定に頼ることはできません。システムはここでリリースごとに改善されます。最も単純なケースとして考えてみましょう。

？-X = 1; 1=2。
X = 1;
false。

非常に賢いPrologは、それが1 = 2常に失敗することを検出できるため、代わりに単に答えることができますX = 1.。一方、このような「賢さ」は実装に非常にコストがかかり、より頻繁なケースを最適化するためにより多くの時間が費やされます。

では、なぜプロローグはこれをまったく示していないのでしょうか？主な理由は、Prologがそれ以上の答えがないことをすでに知っている場合、別の答えを素直に尋ねることを避けることです。したがって、この改善の前に、変数を含むすべてのクエリに対して別の回答を求められ、1つの回答falseだけですべてのクエリに「いいえ」が表示されました。これは以前は非常に面倒だったため、多くのプログラマーは次の答えを求めなかったため、意図しない答えについて警告を受けませんでした。

そして二次的な理由は、実装の制限を認識し続けることです。Prologがこの一般的なクエリで別の答えを求めた場合、これは、すべてのコンピューティングリソースを蓄積して消費する可能性のあるスペースをまだ使用していることを意味します。

あなたの例でlast1/2は、そのようなケースに遭遇します。そして、あなたはすでに非常に賢いことをしました、ところで：あなたは予期しない振る舞いの最初の発生を見るためにクエリを最小化しようとしました。

あなたの例のクエリlast1([1,2],X)では、Prologシステムはリスト全体を見るのではなく[1,2]、主要なファンクターだけを見る。last1([_|_],X)したがって、Prologシステムの場合、クエリは、適用する句を決定するときと同じように見えます。この目標は現在両方の条項に当てはまります。これが、Prologが試してみる代わりに2番目の条項を覚えている理由です。

しかし、考えてみてください。この選択は、最後の要素を除くすべての要素で可能になりました。つまり、要素ごとにいくらかのメモリを支払うということです。非常に長いリストを使用することで、実際にこれを観察できます。これは私の小さな32ビットラップトップに搭載されています—より大きなシステムではさらに0または2を追加する必要があるかもしれません：

？-長さ（L、10000000）、last1（L、E）。
エラー：ローカルスタックが不足しています

一方、事前定義last/2はスムーズに機能します。

？-長さ（L、10000000）、last（L、E）。
L = [_G343、_G346、_G349、_G352、_G355、_G358、_G361、_G364、_G367|...]。

実際、それは一定のスペースを使用します！

これには2つの方法があります。

  1. 定義を最適化してみてください。はい、あなたはこれを行うことができますが、あなたは非常に賢くなければなりません！たとえば、@back_dragonによる定義は正しくありません。初心者が実際にそのセマンティクスを破壊しているときに、プログラムを最適化しようとすることがよくあります。

  2. と同じ述語を実際に定義しているかどうかを自問してくださいlast/2。実際、あなたはそうではありません。

質問2：

検討：

？-last（Xs、X）。
Xs = [X];
Xs = [_G299、X];
Xs = [_G299、_G302、X];
Xs = [_G299、_G302、_G305、X];
Xs = [_G299、_G302、_G305、_G308、X]
..。

と

？-last1（Xs、X）。
**ループ**

したがって、この場合の定義はSWIの定義とは異なります。句の順序を交換します。

？-長さ（L、10000000）、last2（L、E）。
L = [_G343、_G346、_G349、_G352、_G355、_G358、_G361、_G364、_G367 | ...];
false。

繰り返しますが、これfalse！しかし今回は、大きなリストが機能します。今回は、最小限のクエリは次のとおりです。

？-last2（[1]、E）。
E = 1;
false。

そして状況は非常に似ています：繰り返しますが、Prologはクエリを同じように見て、last2([_|_],E)両方の条項が適用されると結論付けます。少なくとも、線形オーバーヘッドではなく一定のオーバーヘッドがあります。

このオーバーヘッドをクリーンな方法で克服する方法はいくつかありますが、それらはすべて実装の内部に大きく依存しています。

于 2012-07-31T08:29:04.170 に答える
5

SWI-Prologは、解決策がないと判断できる場合、解決策の追加を求めるプロンプトを回避しようとします。インタプリタはメモリを調べて残っているものを探していると思います。メモリchoice pointが見つからない場合は、単に終了を記述します。それ以外の場合は、ユーザーが移動を選択できるように待機します。

私はこの方法でlast1を決定論的にしようとします：

last1([_,H|Rest], Last) :- !, last1([H|Rest], Last).
last1([Last], Last).

でも前回indistinguishableからではないと思います。ライブラリのソースコードに潜んでいます（それは単純です）?- edit(last).

%%  last(?List, ?Last)
%
%   Succeeds when Last  is  the  last   element  of  List.  This
%   predicate is =semidet= if List is a  list and =multi= if List is
%   a partial list.
%
%   @compat There is no de-facto standard for the argument order of
%       last/2.  Be careful when porting code or use
%       append(_, [Last], List) as a portable alternative.

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

よく考えられた実装に感謝することができます。

于 2012-07-31T10:34:39.243 に答える
0

このコードは機能します：

last1([Last], Last).
last1([_ | Rest], Last) :- last1(Rest, Last), !.

これは、プロローグのものにはもっと多くの組み合わせがあるかもしれないが、この記号で：！、プロローグはこのポイントに達した後は戻らないからです

于 2015-10-11T14:54:36.457 に答える