序言 - 這是什麼邏輯

Question

我試圖理解這段代碼如何工作，但我失敗了。 它連接兩個列表，然後反轉結果。

reverse(L, RL):- reverse(L, [], RL). 
reverse([], RL, RL). 
reverse([H|T], S, RL):- reverse(T, [H|S], RL). 


concat([], L, L). 
concat([H|T1], L2, [H|T]):- concat(T1, L2, T). 


concat_reverse(L1,L2,L):-concat(L1,L2,LN),reverse(LN,L) 

我的老師告訴我去調試模式和跟蹤查詢瞭解，但它沒有幫助。

這裏有一個例子

5 ?- trace,concat_reverse([1,3],[4,5],S). 
    Call: (7) concat_reverse([1, 3], [4, 5], _G1444) ? creep 
    Call: (8) concat([1, 3], [4, 5], _G1569) ? creep 
    Call: (9) concat([3], [4, 5], _G1564) ? creep 
    Call: (10) concat([], [4, 5], _G1567) ? creep 
    Exit: (10) concat([], [4, 5], [4, 5]) ? creep 
    Exit: (9) concat([3], [4, 5], [3, 4, 5]) ? creep 
    Exit: (8) concat([1, 3], [4, 5], [1, 3, 4, 5]) ? creep 
    Call: (8) reverse([1, 3, 4, 5], _G1444) ? creep 
    Call: (9) reverse([1, 3, 4, 5], [], _G1444) ? creep 
    Call: (10) reverse([3, 4, 5], [1], _G1444) ? creep 
    Call: (11) reverse([4, 5], [3, 1], _G1444) ? creep 
    Call: (12) reverse([5], [4, 3, 1], _G1444) ? creep 
    Call: (13) reverse([], [5, 4, 3, 1], _G1444) ? creep 
    Exit: (13) reverse([], [5, 4, 3, 1], [5, 4, 3, 1]) ? creep 
    Exit: (12) reverse([5], [4, 3, 1], [5, 4, 3, 1]) ? creep 
    Exit: (11) reverse([4, 5], [3, 1], [5, 4, 3, 1]) ? creep 
    Exit: (10) reverse([3, 4, 5], [1], [5, 4, 3, 1]) ? creep 
    Exit: (9) reverse([1, 3, 4, 5], [], [5, 4, 3, 1]) ? creep 
    Exit: (8) reverse([1, 3, 4, 5], [5, 4, 3, 1]) ? creep 
    Exit: (7) concat_reverse([1, 3], [4, 5], [5, 4, 3, 1]) ? creep 
S = [5, 4, 3, 1]. 

Answer 1

讓我們來看看這點點滴滴。

您使用：

concat_reverse([1,3],[4,5],S). 

的Prolog試圖統一這一點。

concat_reverse(L1,L2,L) 

比賽。 L1與[1,3]和L2合併爲[4,5]。所以我們看右邊：

concat_reverse(L1,L2,L):-concat(L1,L2,LN),reverse(LN,L) 

序言確實爲統一的深度優先搜索，所以它與統一L1和L2檢查concat(L1,L2,LN)，再次。

讓我們來看看這兩個concatš在一起：

concat([], L, L). 
concat([H|T1], L2, [H|T]):- concat(T1, L2, T). 

如果有幫助，認爲這種模式匹配的是落空如果邏輯。第一個將匹配一個空的列表，一些東西，以及相同的東西。這實際上是Prolog所做深度優先搜索的一個停止條件。

第二個匹配一個頭部和尾部列表，某些東西，以及具有相同頭部和可能不同尾部的列表。在這一點上，我們匹配這個，因爲統一是如何工作的。沒有什麼重要的是綁定到第三個列表。統一時，我們會改變這個「沒有什麼重要」的東西。現在我們匹配，所以我們用下一個concat遍歷，傳遞第一個列表的尾部，第二個列表，以及另一個「沒有重要的」。

在下一級，我們匹配相同的條件。我們再次這樣做，我們達到了停止條件。我們沒有什麼重要的是第二個列表。所以我們試圖通過統一來抓取深度優先搜索。我們在搜索樹中預先填充了我們上面匹配的第一個列表的頭部。統一。我們再次爬上去。我們預先考慮下一個級別。統一。你怎麼知道的，我們能夠統一第一個concat_reverse比賽的concat任期。

現在我們來看看concat_reverse匹配的reverse部分。這是你的堆棧跟蹤中的Exit(8)/Call(8)。下來，我們又來了，做這些深度優先搜索：

reverse(L, RL):- reverse(L, [], RL). 
reverse([], RL, RL). 
reverse([H|T], S, RL):- reverse(T, [H|S], RL). 

嘛，只有一個比賽，一個有兩個方面。但是現在我們搜索reverse的三個選項。我們的名單不是空的，所以我們不匹配第一個（再次，這將是我們的停止條件）。我們可以匹配第二個。

我將停止，因爲繼續這不會添加任何新東西。基本上，prolog解釋器的工作是匹配，統一和深度優先搜索之一。

希望您已經或者已經有了一堂關於爲什麼prolog會深度優先搜索以及爲什麼這意味着它無法完整反駁（以及您可以作爲程序員做什麼以防止無限深度搜索）。

基本上，當你編寫序言代碼時，你會像寫歸納證明或遞歸函數那樣編寫它。從停止條件開始，然後根據停止條件處理一般情況。根據構圖定義事物，如concat_reverse。

我想你應該看看一個更簡單的例子來更好地理解統一。這個例子有不必要的複雜性（儘管這些複雜性總是會幫助你，當你需要編寫你自己的prolog代碼作家庭作業時）。嘗試單獨查看reverse，無需concat和concat_reverse。

Answer 2

在閱讀（或寫作）Prolog時，我喜歡講一個小故事。

例如，讀取concat_reverse時，我將如何解釋它： 「如果首先LN是L1和L2的連接，並且其次L是LN的反向，則L是L1和L2的concat_reverse。

當我閱讀concat時，我說： 「[]和L的連接是L.」 「如果T1和L2的級聯是T，[H | T1]和L2的級聯是[H | T]。」

基本上，解釋應該以某種方式簡化表達式。如果我要寫「concat」，我會認爲「什麼是concat的簡單真相？將任何列表連接到空列表就是原始列表。那麼[H | T]的一般情況呢？連接L到這個如果M的頭部是H並且M的其餘部分是T到L的級聯，換句話說，如果M是[H | RM]並且concat（T，M）是concat（[H | T] L）是RM。「

至於相反，故事有點複雜，因爲沒有簡單的說「RL是L的倒過來......」。但我們仍然可以想出一個故事。例如，如果L的適當後綴反過來，然後將S連接到結果，我們可以說「S是L的後綴（稱爲RL）」。因此，對於空白後綴，我們有反向（[]，RL，RL） - RL是RL的後綴，如果L的空後綴反過來並且RL連接到RL後綴。

在一般情況下，如果L的後綴是[H | T]，那麼RL的後綴只有在[H | S]也是RL的後綴時纔是S.

這有點令人困惑，尤其是當謂詞被稱爲「反向」時。我們必須使用一些想象力。但是，如果我們叫什麼它是這樣的：

concat_of_reversed_suffix_and_S([H|T], S, RL) :- concat_of_reversed_suffix_and_S(T, [H|S], RL).

這是一個有點清晰 - 的反向[H | T]爲T，隨後H.相反如果[H | T]爲後綴的L和S是後綴或RL，那麼T的反過來跟H跟S是RL。我們說這個長句子以這樣的方式

reverse([H|T], S, RL) :- reverse(T, [H|S], RL).

調試器可以告訴你的過程，但最好是在你的頭一個故事，解釋它，然後你可以用調試器確認。

在這種情況下，可以看到：

Call: (10) reverse([3, 4, 5], [1], _G1444) ? creep 
    Call: (11) reverse([4, 5], [3, 1], _G1444) ? creep 

[3,4,5]是L的後綴，[1]是RL的後綴。只有當[3,1]也是RL的後綴時，這纔是真實的，而將[4,5]作爲L的（小）後綴留待考慮。

Answer 3

免責聲明：我不知道你的老師，所以也許你會以不同的方式把這個...

告訴你有很多困難和問爲什麼代碼沒有閱讀：

 
concat_reverse(L1,L2,L):-reverse(L2,R,L),reverse(L1,[],R). 

然後：

 
seq([]) --> 
    []. 
seq([E|Es]) --> 
    [E], 
    seq(Es). 

iseq([]) --> 
    []. 
iseq([E|Es]) --> 
    iseq(Es), 
    [E]. 

concat_reverse2(L1,L2,L) :- 
    phrase((iseq(L2), iseq(L1)), L). 

通常，我不會建議使用調試器來理解謂詞。

Answer 4

concat_reverse(L1,L2,L) :- 
     concat_reverse(L1,L2,[],L). 

concat_reverse([],[],L,L). 
concat_reverse([],[B|R2],L3,L) :- 
     concat_reverse([],R2,[B|L3],L). 
concat_reverse([A|R1],L2,L3,L) :- 
     concat_reverse(R1,L2,[A|L3],L).