需要帮助了解Prolog append / 3和inverse / 2以及跟踪输出 [英] Need help understanding Prolog append/3 and inverse/2 and trace output

问题描述

这是问题

找到值A。

---

  inverse（[]，[]）。 
 
逆（[H | T]，D）：-
逆（T，Z），
追加（Z，[H]，D）。 
 
 append（[]，X，X）。 
 
 append（[X | L]，M，[X | N]）：-
 append（L，M，N）。 
  

---

这是答案：

请帮助我理解这一点！

解决方案

您发布的Prolog代码的图像显示了一些不寻常或很旧的Prolog，尤其是列出了 [H ：T] 现在完成为 [H | T] ，请注意的更改：到 | ，而< = 更常见为：-。

要理解Prolog代码，从下往上开始比较容易。我不会介绍

---

从OP注释：

从字母到数字和theta符号的一些替换使我难以理解。

虽然绑定（θ）更特定于逻辑语言，数字也可以在基于堆栈的功能性语言，请参见德布赖恩索引。同样，我也不想使用垂直线分隔符（---）来编写绑定，而是更喜欢使用（↦），如这里。

第1 -4行只是再次说明了源代码。

通常带有跟踪的目标是传达执行（调用）的树结构，但是使用这些行，除非您知道Prolog的工作原理，否则很难看到有树结构。

带有横线的行旨在帮助您了解发生了什么，但是如果您只是按照执行流程（调用）进行操作，则可能会发现我这样做是因为它们只会引起混乱，可以忽略。

在您的注释中， Res（_，_）引用跟踪中的前几行。因此，可以将第6行上的Res（5,2）读为第6行，这是第5行进行调用后再调用第2行的结果。

绑定（θ）显示为集合。我不确定上级脚本和子级脚本的编号代表什么，但是它们显然与De Bruijn索引相关联。您将不得不请您的老师解释上级脚本和子级脚本。

在尝试了几次仅用文本进行解释之后，我终于诉诸于使用Microsoft Visio进行操作

即使不需要它，我也将SWI-Prolog中的线迹输出添加到图像中，然后仅将呼叫线路放置在树中的相应位置，以便您可以将两者关联起来。我自己做了一个检查，以确保它是正确的。

如果有一些拼写错误，我不会感到惊讶，因为我不得不重做部分错误很多次，以便于理解。希望我实现了这个目标。

< img src = https://i.stack.imgur.com/IUEVD.png alt =在此处输入图片描述>

This is the question

find value A.

---

inverse([],[]).

inverse([H|T],D) :-
  inverse(T,Z),
  append(Z,[H],D).

append([],X,X).

append([X|L],M,[X|N]) :-
  append(L,M,N).

---

This is the answer:

Plese help me to understand this!

解决方案

The images of the Prolog code you posted show some unusual or very old Prolog, in particular for list the use of [H:T] is now done as [H|T], notice the change from : to |, and <= is more common as :-.

To understand the Prolog code it is easier to start from the bottom up. I will not cover unification or backward chaining in this as going to that level of detail would require a chapters worth here.

The first predicate to understand is append/3. Normally you never see the code for append given as it is a built-in predicate, but here it is given.

Append/3 has three parameters which are all list. The first two are appended together to form the third.

?- append_01([],[],R).
R = [].

?- append_01([a],[],R).
R = [a].

?- append_01([],[a],R).
R = [a].

?- append_01([a],[b],R).
R = [a, b].

but Prolog predicates can have other modes of operation which can bind values to what would be considered input parameters in other programming languages, e.g.

?- append(X,[b],[a,b]).
X = [a] ;
false.

?- append_01([a],Y,[a,b]).
Y = [b].

?- append(X,Y,[a,b]).
X = []    , Y = [a, b] ;
X = [a]   , Y = [b]    ;
X = [a, b], Y = []     ;
false.

or can just be used to verify the arguments

?- append([a],[b],[a,b]).
true.

?- append([a],[c],[a,b]).
false.

Next is the predicate inverse/2 which is more commonly known in Prolog as reverse/2, and again the source code is given here.

This simply takes one list and reverses it, e.g.

?- inverse([],X).
X = [].

?- inverse([a],X).
X = [a].

?- inverse([a,b],X).
X = [b, a].

however this version of the source code does not do well in other modes, e.g.

?- inverse(X,[]).
X = [] ;

Action (h for help) ? abort
% Execution Aborted

but that doesn't matter to answer the question.

---

The next part of what you posted is a trace of the execution of the query

?- inverse([[1,2,3],[5,4]],A).

In order to use the trace on your code, since there is a built-in predicate for append/3 I had to rename the predicate. Here is the code I used.

inverse([],[]).

inverse([H|T],D) :-
  inverse(T,Z),
  append_01(Z,[H],D).

append_01([],X,X).

append_01([X|L],M,[X|N]) :-
  append_01(L,M,N).

Using SWI-Prolog

set up the trace

?- visible(+all),leash(-all). 

start the trace

trace.

execute the query

[trace] ?- inverse([[1,2,3],[5,4]],A).

returns

   Call: (8) inverse([[1, 2, 3], [5, 4]], _7548)
   Unify: (8) inverse([[1, 2, 3], [5, 4]], _7548)
   Call: (9) inverse([[5, 4]], _7794)
   Unify: (9) inverse([[5, 4]], _7794)
   Call: (10) inverse([], _7794)
   Unify: (10) inverse([], [])
   Exit: (10) inverse([], [])
   Call: (10) append_01([], [[5, 4]], _7802)
   Unify: (10) append_01([], [[5, 4]], [[5, 4]])
   Exit: (10) append_01([], [[5, 4]], [[5, 4]])
   Exit: (9) inverse([[5, 4]], [[5, 4]])
   Call: (9) append_01([[5, 4]], [[1, 2, 3]], _7548)
   Unify: (9) append_01([[5, 4]], [[1, 2, 3]], [[5, 4]|_7792])
   Call: (10) append_01([], [[1, 2, 3]], _7792)
   Unify: (10) append_01([], [[1, 2, 3]], [[1, 2, 3]])
   Exit: (10) append_01([], [[1, 2, 3]], [[1, 2, 3]])
   Exit: (9) append_01([[5, 4]], [[1, 2, 3]], [[5, 4], [1, 2, 3]])
   Exit: (8) inverse([[1, 2, 3], [5, 4]], [[5, 4], [1, 2, 3]])
A = [[5, 4], [1, 2, 3]].

I will not explain the details of a trace as other SO Q&A do that.

---

The trace you posted also has more detail than generated by using the trace, e.g. the bindings (θ).

To see the bindings use gtrace/0

?- gtrace.
% The graphical front-end will be used for subsequent tracing
true.

then execute the query

[trace]?- inverse([[1,2,3],[5,4]],A).

and press space bar to single step. You will have to experiment with it to learn how it works; AFAIK there is no posted documentation on how to use it.

---

From OP comment:

There are some replacements from letters to numbers and theta symbol that make me hard to understand.

While the bindings (θ) are more specific to logic languages, the numbers are also seen in stack based functional languages, see De Bruijn index. Also instead of writing the bindings using vertical line separator (---) , I prefer to use (↦) as seen here.

The lines 1 -4 are just the source code stated again.

Normally with a trace the goal is to covey a tree structure of the executions (calls) but with these lines unless you know how Prolog works it is really hard to see that there is a tree structure.

The lines with the over-bars are meant to help understand what is going on, but if you just follow the flow of the executions (calls) then you may find as I do that they just cause confusion and can be ignored.

At you noted in the comments the Res(_,_) are referring to previous lines in the trace. So Res(5,2) on line 6 can be read as Line 6 is the result of a call from line 5 and which then calls line 2.

The unifications or bindings (θ) are show as as sets. I am not exactly sure what the super and sub script numbers represent but they are clearly linked to De Bruijn indexes. You will have to ask your teacher to explain the super and sub scripts.

After trying several times to explain this with just text, I finally resorted to using Microsoft Visio to do it as graphical tree which was much easier, faster and more accurate.

Even though it was not needed, I added the line trace output from SWI-Prolog into the image and then placed only the call lines in the corresponding places in the tree so that if you want to correlate the two you can. I did it for myself as a check to make sure it was correct.

I would not be surprised if there are a few typo mistakes as I had to redo parts of it many times to make it easy to comprehend. Hopefully I achieved that goal.

这篇关于需要帮助了解Prolog append / 3和inverse / 2以及跟踪输出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！