6

正規表現マッチングを実行しようとしています。すべての関数を書き出しましたが、正常に機能していません。私が知る限り、リストを比較しようとすると問題が発生します。
たとえば、「re_contains(a,a)」です。"re_contains(union(a,b),a)" と同様に (明らかに) true を返します。

しかし、リストにするとすぐに失敗します。「re_contains(seq(a,b), [a,b])」。false を返します。Append は可能なすべての組み合わせを調べて一致を見つける必要がありますが、これらの関数はどれも正しく機能しません。これは、おそらく私が基本的なケースを見逃していると私に思わせます。しかし、私は「re_contains(X, L) :- X == L.」だと思います。世話をする必要があります。ここで何か重要なことを見過ごしているに違いない。

これが私のコードです：

re_contains(empty, []).

re_contains(X, L) :-
    X == L.

re_contains(seq(X, Y), L) :-
    append(L1, L2, L),
    re_contains(X, L1),
    re_contains(Y, L2). 

re_contains(union(X, _), L) :-
    re_contains(X, L).

re_contains(union(_, Y), L) :- 
    re_contains(Y, L).  

re_contains(kleene(X), L) :- 
    append([Car|L1], L2, L),
    re_contains(X, [Car|L1]),
    re_contains(kleene(X), L2).

re_contains(kleene(_),[]).
4

2 に答える 2

8

いくつかの問題があります。最も明白なものは次のとおりです。

タイピング。 述語re_contains/2は、2 番目の引数としてリストを想定しています。それre_contains(a,a).が成功するのは意図というより偶然です。

単調性。別の問題は、re_contains([a],[a])成功するがre_contains([X],[a])失敗することです。または、別の角度から見ると、re_contains([X],[a])失敗しますが、X = a, re_contains([X],[a])成功します。ゴールX = aを追加することで、クエリが特殊化されたため、最初に失敗したクエリが再び失敗するはずです。

同一性 ( ) のテストは、等価性 ( )==/2に置き換えて、何らかのリストがあることを確認する必要があります。そう：=/2

re_contains(X, L) :-
    % X == L .
    X = L、
    追加 (X,_,_)。

これは、X がリストであることを確認するためだけに使用されていることに注意してくださいappend/3。実際の追加機能は使用されません。

効率。3 番目の問題は、連結を表す実際の方法に関するものです。次のルールを見てみましょう。

re_contains(seq(X, Y), L) :-
    追加 (L1、L2、L)、
    re_contains(X, L1),
    re_contains(Y, L2)。

ここで、 length のリストがあるとしますN。ゴールに対していくつの答えが可能append(L1, L2, L)ですか? 実はN + 1。そしてこれは、関連する実際の値に関係なく。今考えてみましょう：

?- 長さ(L,1000000)、時間(re_contains(seq([a],[]),[b|L]))。
% 2,000,005 推論、0.890 秒で 0.886 CPU (100% CPU、2258604 リップ)
間違い。

re_contains/2ここでは、リストの長さに比例する時間が必要です。しかし、これが不可能であることを理解するには、最初の要素を見るだけで十分です。

したがって、背後にある問題はの使用ですappend/3。Prolog には簡単な経験則があります。使いすぎている場合は、append/3の使用を検討してください— Definite Clause Grammars。詳細については、タグを調べてください。また、プロローグの紹介テキストを参照してください。手始めに、定義のサブセットを次に示します。

re_contains(RE, L) :-
    フレーズ（re（RE）、L）。

re([]) --> [].
re([E]) --> [E].
re(seq(X,Y)) -->
    re(X)、
    re(Y)。

リスト全体を調査しなくなりました。

?- 長さ(L,1000000)、時間(句(re(seq([a]、[]))、[b|L]))。
% 6 推論、0.000 秒で 0.000 CPU (88% CPU、127313 リップ)
間違い。

ところで、ここに完全な定義があります。

終了/非終了。効率に関連するのは、終端の特性です。理想的には、ソリューションのセットを有限表現できる場合、クエリは終了します。つまり、有限数の回答によるものです。OK、それが私たちが目指している理想です。Prolog のシンプルだが非常に効率的な実行アルゴリズムは、限られた数の回答が可能な場合にループすることがあります。非終了の理由そのものを理解することは、非常に難しい場合があります。トレースやデバッガーを使用したステップ実行などの通常のデバッグ戦略は、あまりにも多くの詳細を表示するため機能しません。幸いなことに、より優れたテクニックがあります。

プログラム全体を見る代わりに、プログラムのごく一部だけを見ていきます。このフラグメントは障害スライスです(詳細については、リンクを参照してください)。それははるかに小さいですが、元のプログラムについてかなり多くのことを伝えています — それが純粋で単調なプログラムであった場合:

障害スライスが終了しない場合、元のプログラムは終了しません。

したがって、そのような失敗スライスを見つけた場合、プログラム全体についてすぐに結論を出すことができます。続きも読まずに！

これは、興味深い失敗のスライスです。

...
 re_contains(X, L) :- false,
     X = L
re_contains(seq(X, Y), L) :-
    append(L1, L2, L), false, 
    re_contains(X, L1) ,
     re_contains(Y, L2) .
re_contains(union(X, _), L) :- false,
     re_contains(X, L) .
...

ここでゴールを考えてみましょre_contains(seq([],[]),L).うL = []。append(L1, L2, L)ただし、終了しないため、ループします。これを で終了する上記の DCG ソリューションと比較してphrase(re(seq([],[])),L)ください。

于 2012-09-25T07:54:24.820 に答える