1

最近、私はプロローグを勉強し始めました、それを扱うとすぐに私はそれを理解するのに問題がありました。

append/3リストを調べていますが、2つのリストをマージする必要がある述語がどのように機能するのか理解できません。

book_append([], L, L). 
book_append([X|L1], L2, [X|L3]) :-
    book_append(L1, L2, L3).

L2正確には、メインリストにどのように追加されるのか理解できません。私はこれまでに理解したことを説明しようとしています：

境界条件は、最初のリストが空で、2番目と3番目が同じ値をとる場合にのみ統一されます。それが正しいか？

最初の質問、おそらくそれはばかげています。最初のリストが空の場合、2つのリストは同じ値を取るように統合する必要があります。しかし、それらは異なっている必要があるので、私はそれらの価値の1つを失います。

2行目では、最初のリストの先頭が3番目のリストに追加され、同じ関数が呼び出されます。

私は通常、この関数を次のように使用します。book_append([1, 2, 3], [a, b, c], X).

L1は空ではないため、最初の行はfalseです。
2番目のものは次のようになります：

book_append([1|[2, 3], [a, b, c], [1|L3]) :-
    book_append([2, 3], [a, b, c], L3).

L3最初の呼び出し中の（3番目のリストの末尾であることはすでにわかっています）の値は何ですか？空ですか？またはインスタンス化されていない変数？それともインスタンス化されていますL2か？

4

4 に答える 4

2

Prolog's logical variables (logvars) are essentially named pointers, which can be instantiated/"set" (assigned a value) only once. Each logvar can be in "not-yet-set" state, or in instantiated/set state.

No binding can be ever changed, while no backtracking has occured (on backtracking, this "setting of pointers" can be undone and the logvars can revert back to their former uninstantiated state, possibly to be instantiated again later on to some other values).

When "set", it can point to an atomic value like numbers (5), symbols ('a'), etc. Or it can point to another logvar (meaning, the two become equivalent).

Or it can point to a compound (struct-like, or named record-like) value, like f(a,B,c) whose sub-entities themselves can be fully instantiated ("ground") values, or they can be/contain not-yet-instantiated logvars themselves.

Now, lists in Prolog appear as compound terms under a name (i.e. functor) of '.' (a dot). A list [A|B] is actually a compound term '.'(A,B) with two sub-entities i.e. "arguments", A and B.

So when we "set" A = [1|B], we make A "point" at the actual bona fide structure in computer's memory, tagged with the name (functor) '.', with two fields. The first field contains a number 1, and second - a logvar named B, not yet instantiated to anything. Or in C++-terms, it's an uninitialized pointer.

And that pointer is what's getting passed (by reference) into the nested recursive call to book_append. And it is that pointer which gets set there. And that is what the second field of a "list node" "pointed to" by A is now pointing at.

So recursive calls do not need to "return" anything back to their "callers" in Prolog. They just instantiate parts of structures that were set up above them, "fleshing out" those structures more and more fully.

But if we have a handle on the top node of the list, we have access to all of its sub-entities, now that they are instantiated fully.

And all this verbose text means, in C++ terms, that append/3 operates by going along its first list while copying the list nodes aside, and when it's arrived at the end of the first list, it sets the next pointer of the last-copied list node - to point to the start of the second list with which it was called. It means that it is tail recursive modulo cons.

于 2012-08-08T08:41:15.607 に答える
2

まず、@ Will Nessによるこの回答と（私による）この回答をご覧ください。それはすでにあなたの質問に答えるはずです。

次に、特定の懸念事項に（すばやく）対処しましょう。

最初の質問、おそらくそれはばかげています。最初のリストが空の場合、2つのリストは同じ値を取るように統合する必要があります。しかし、それらは異なっている必要があるので、私はそれらの価値の1つを失います。

Prologで値がどのように変化するかを考慮する必要があります。

基本的に価値観は統一によって変化します。そして一度だけ変更してください。それは、それが変化するA可能性が[5|B]あり、その後変化する可能性があり、すべてのプログラムにとってそれになることを意味します。B最終的には変更される可能性があるためA、何らかの方法で変更されますが、バインディングは前述のように1回だけ発生します。

したがって、ここでは、何も再バインドできないため、値を「失う」ことはできません。統一は、自由変数を正しいものにバインドすることによって、List2一致するように最善を尽くします。Resultこのように、Resultがあなたの例のように自由変数である場合、それはただの値にバインドされますList2。また、両方の変数がすでにバインドされている場合、統合で実行できるのは、それらが同じ値にバインドされているかどうかをテストすることだけです。

2番目の質問については、より明確なアイデアを得るためにバインディングの詳細を説明する私の回答を特に参照してください。

于 2012-08-08T07:45:04.013 に答える
0

最初の行は、最初のリストが空で、2番目と3番目のリストが同じである場合にのみ適用されます（または、一方が変数などで、もう一方の値をとることができます）。したがって、情報が失われることはありません。

2行目を理解するために、（それを使用してデモンストレーションしている方法で）3番目の引数が結果であることを覚えておいてください（これも、考えられる使用法の1つにすぎません）。したがって、そのように使用すると、2行目は[X | L3]を返すことを示し、L3は本文に記載されています（実際には適切な用語はわかりません）-どこですか？新しいbook_append呼び出しの結果として。したがって、L3は、頭のない最初のリストを2番目のリストに追加した結果になります。

于 2012-08-08T04:29:53.777 に答える
0

データベース：

book_append([], L, L).
book_append([X|L1], L2, [X|L3]) :- book_append(L1, L2, L3).

電話をかけるとき：

?- book_append([1, 2, 3], [a, b, c], A).

コンパイラーはデータベースを調べて統合を見つけます。最初の行は統合できないため（[1、2、3]は[]と統合できない）、2番目の行が使用され、book_append（[1 | [2、3]、[a、b、 c]、[1 | L3]）：-book_append（[2、3]、[a、b、c]、L3）。統一は、「：-」の右からの条件にも統一がある場合にのみ発生します。そのため、データベースを再度調べて、book_append（[2、3]、[a、b、c]、L3）などの統合を見つけます。

統合は次のようになります（=は統合の記号です）。

book_append([1, 2, 3], [a, b, c], A) = 
    book_append([1|[2,3]], [a,b,c], [1|L3]) =
    book_append([2|[3]],   [a,b,c], [2|L3]) =
    book_append([3|[],     [a,b,c], [3|L3]] =
    book_append([],        [a,b,c], [a,b,c])  % book_append([], L, L).
=> A = 1|2|3|[a,b,c]

私が間違っている場合は訂正してください。私はプロジェクトのためにこれを学び始めたばかりです。

于 2016-05-12T13:56:28.787 に答える