How recursion in Prolog works from the inside. One example

Question

I have a small script here that converts a list of elements into a set. For example, the list [1,1,2,3] → set [1,2,3]. Can someone explain to me step by step what is going on inside these procedures? Can you use my example [1,1,2,3] → [1,2,3]?

list_to_set([],[]). list_to_set([A|X],[A|Y]):- list_to_set(X,Y), \+member(A,Y). list_to_set([A|X],Y):- list_to_set(X,Y), member(A,Y). 

Answer 1

The procedural analogue of the prologue program is called SLDNF. Request:

  list_to_set([1,1,2,3], Result) 

Now SLDNF is trying to match [1,1,2,3] with [A | X] using a procedure called unification. In a few words, he checks if a variable can be created. [A | X] is a shortcut, this means (freely): "A is the first element, and X is the rest." This can be done if A = 1 and X = [1,2,3] and Result = [1 | Y]. If unification succeeds, we use the same substitution in the body of the rule (which appears after :-). You may wonder why we use the second sentence, but not the third or first? The prologue is actually trying them all, try to imitate a non-deterministic choice. procedurally, although he is trying to put them in order. The first sentence cannot be unified (A = ?, There is nothing in the list). The third sentence will be checked later if our first attempt failed. Let me call it “choice point 1” because Prolog has this open path that remains uncharted and can be used if the paths that have been chosen so far fail.

Now SLDNF has reduced your initial request to:

 list_to_set([1,2,3], Y2), \+ member(1, Y2) {Result = [1 | Y2]} 

(Variables can be renamed, and we do this to avoid confusion with the program). This is where the magic happens. SLDNF now does the same as before, but with a slightly different input [1,2,3]. Recursion at its best. Therefore, he tries to combine it with the first sentence, but he does not work again. It succeeds with the second, and in the same way you get this instead of the first query element (called a literal), we again have a body with a variable replacement X = [2, 3], A = 1, Y2 = [1 | Y].

Now we have

 list_to_set([2,3], Y), \+ member (1,Y), \+ member(1, [1 | Y]) {Result = [1 | [1 | Y]]} 

I do not continue to the end. In the end, we finish checking + member (1, [1 | Y]), which means that "1 is not a member of the list with head 1 and tail Y". This is an assembly in the predicate and will not be executed because 1 is on this list (this is the head). Prolog will return to the endpoint of choice, eventually it will come to "point of choice 1". Here, the last condition in paragraph "A is a member of Y". You can make sure that this path will be successful.

Sorry for the long hasty answer, hope this helps.

Answer 2

If you look at a specific example, you will soon be buried in a multitude of non-local details. So much so that you lose sight of the important properties of your program. Let's look at the next piece of the program called the slice of failure . You get a failure fragment by adding false to your program. Failures share many interesting properties with the original program. For example, a Goal, false target Goal, false , executed with a failover, will never use more outputs than the original program. Or, conversely, the original program will use more (or, at best, the same number) outputs. So let me point out one such snippet:

  list_to_set ([], []): - false .
 list_to_set ([A | X], [A | Y]): -
    list_to_set (X, Y), false ,
     \ + member (A, Y) .
 list_to_set ([A | X], Y): -
    list_to_set (X, Y), false ,
    member (A, Y) .

And since this fragment is no longer interested in specific elements ( A no longer used, but member/2 ), we can use length/2 for most common lists. Thus, we can observe the minimum number of conclusions required for each length:

  ? - length (L, N), call_inferences ((list_to_set (L, _), false; true), Inf).
 N = 0, Inf = 3;
 N = 1, Inf = 6;
 N = 2, Inf = 12;
 N = 3, Inf = 24;
 N = 4, Inf = 48;
 N = 5, Inf = 96;
 N = 6, Inf = 192;
 N = 7, Inf = 384;
 N = 8, Inf = 768;
 N = 9, Inf = 1536;
 N = 10, Inf = 3072 ...

Using

 :- meta_predicate user:call_inferences(0,-). call_inferences( Goal, Inferences) :- statistics(inferences, Inferences0), Goal, statistics(inferences, Inferences1), Inferences is Inferences1 - Inferences0. 

The number of pins doubles with each subsequent element. That is, they grow exponentially. Thus, your implementation is worth at least an exponentially many conclusions ... No need to look at a specific example.

Your program has more problems:

 ?- L=[A,B],list_to_set(L,S), L = [a,b]. 

doesn't work whereas

 ?- L=[A,B], L = [a,b], list_to_set(L,S). 

succeeds. That is, your program is no longer a pure relation. Use maplist(dif(A),Y) instead of \+ member(A,Y) .

Answer 3

In some implementations of Prolog, for example. GNU Prolog , you can track code execution. Using this function, you can go through the assessment process as shown below.

 $ gprolog GNU Prolog 1.4.2 By Daniel Diaz Copyright (C) 1999-2012 Daniel Diaz | ?- consult('list_to_set.pro'). yes | ?- trace. yes {trace} | ?- list_to_set([1,1,2,3], X). 1 1 Call: list_to_set([1,1,2,3],_25) ? 2 2 Call: list_to_set([1,2,3],_57) ? 3 3 Call: list_to_set([2,3],_83) ? 4 4 Call: list_to_set([3],_109) ? 5 5 Call: list_to_set([],_135) ? 5 5 Exit: list_to_set([],[]) ? 6 5 Call: \+member(3,[]) ? 7 6 Call: member(3,[]) ? 7 6 Fail: member(3,[]) ? 6 5 Exit: \+member(3,[]) ? 4 4 Exit: list_to_set([3],[3]) ? 7 4 Call: \+member(2,[3]) ? 8 5 Call: member(2,[3]) ? ... 

An explanation of how to interpret Prolog traces can be found in http://remus.rutgers.edu/cs314/f2007/ryder/projects/prolog/prologTrace.html , section READING A TRACE.

Answer 4

Look at this in English and see if it makes sense intuitively. This might help rename the predicate to look a little less procedural, so I'll call it list_set .

 list_set([],[]). 

This indicates that an empty set corresponds to empty lists.

 list_set([A|X], [A|Y]):- list_set(X,Y), \+ member(A,Y). 

This suggests that the list starting with A and continuing with X corresponds to the set starting with A and continuing with Y if A is not in Y and Y is the set corresponding to X. Or, more gradually, the mode, given the list starting with A (remainder X), we have a set starting with A (remainder Y), assuming that Y is the set corresponding to X and A does not belong to Y. The negation operator always looked strange to me, and this is interesting, in part because what happens here is that A is saved in the next section, the absence of A means that it is effective Actively deleted.

 list_set([A|X], Y):- list_set(X, Y), member(A, Y). 

This is just the "else" case for the previous sentence. It says that a list starting with A and continuing with X matches the set Y, provided that Y also matches the list X and A is already in Y. This is how the elements are removed from the result, since A appears in the first argument pattern but not in the second argument pattern.