序言 - 这是什么逻辑

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).