Why does changing the order of facts change the behavior of the predicate?

Question

This is my first idea:

perm([X|Y],Z) :- takeout(X,Z,W), perm(Y, W). perm([],[]). 

When did I try to run -? perm([1, 2, 3], P). -? perm([1, 2, 3], P). , he found a problem.

But if we change the order of the two statements, it will work.

 perm([X|Y],Z) :- perm(Y, W), takeout(X,Z,W). perm([],[]). 

Why? I am new to Prolog, please help.

Answer 1

takeout/3 you are referring to is usually called select(X, Xs0, Xs)

Here is another definition - to illustrate the unusual use of DCG.

 perm(Xs,Ys) :- phrase(perm(Xs),[],Ys). perm([]) --> []. perm([X|Xs]) --> perm(Xs), ins(X). ins(X),[X] --> []. ins(X),[Y] --> [Y], ins(X). 

Answer 2

Well, your takeout predicate might look like this:

 takeout( X, [X|R], R ). takeout( X, [F|R], [F|S] ) :- takeout( X, R, S ). 

SWI-Prolog has a useful predicate to name trace .

In the first case:

 X = [1, 2, 3] ; Redo: (10) takeout(3, _G477, _G485) ? creep Call: (11) takeout(3, _G480, _G483) ? creep Exit: (11) takeout(3, [3|_G483], _G483) ? creep Exit: (10) takeout(3, [_G479, 3|_G483], [_G479|_G483]) ? creep Call: (10) perm([], [_G479|_G483]) ? creep Fail: (10) perm([], [_G479|_G483]) ? creep Redo: (11) takeout(3, _G480, _G483) ? creep Call: (12) takeout(3, _G486, _G489) ? creep Exit: (12) takeout(3, [3|_G489], _G489) ? creep Exit: (11) takeout(3, [_G485, 3|_G489], [_G485|_G489]) ? creep Exit: (10) takeout(3, [_G479, _G485, 3|_G489], [_G479, _G485|_G489]) ? creep Call: (10) perm([], [_G479, _G485|_G489]) ? creep Fail: (10) perm([], [_G479, _G485|_G489]) ? creep Redo: (12) takeout(3, _G486, _G489) ? creep Call: (13) takeout(3, _G492, _G495) ? creep Exit: (13) takeout(3, [3|_G495], _G495) ? creep Exit: (12) takeout(3, [_G491, 3|_G495], [_G491|_G495]) ? creep Exit: (11) takeout(3, [_G485, _G491, 3|_G495], [_G485, _G491|_G495]) ? creep Exit: (10) takeout(3, [_G479, _G485, _G491, 3|_G495], [_G479, _G485, _G491|_G495]) ? creep Call: (10) perm([], [_G479, _G485, _G491|_G495]) ? creep Fail: (10) perm([], [_G479, _G485, _G491|_G495]) ? creep Redo: (13) takeout(3, _G492, _G495) ? creep Call: (14) takeout(3, _G498, _G501) ? creep Exit: (14) takeout(3, [3|_G501], _G501) ? creep Exit: (13) takeout(3, [_G497, 3|_G501], [_G497|_G501]) ? creep Exit: (12) takeout(3, [_G491, _G497, 3|_G501], [_G491, _G497|_G501]) ? creep Exit: (11) takeout(3, [_G485, _G491, _G497, 3|_G501], [_G485, _G491, _G497|_G501]) ? creep 

In the second case:

 X = [1, 2, 3] ; Redo: (8) takeout(1, _G451, [2, 3]) ? creep Call: (9) takeout(1, _G532, [3]) ? creep Exit: (9) takeout(1, [1, 3], [3]) ? creep Exit: (8) takeout(1, [2, 1, 3], [2, 3]) ? creep Exit: (7) perm([1, 2, 3], [2, 1, 3]) ? creep 

So, the order of enumeration of predicates is really important. In the first case, you created many states with unknown values. It would be a good idea (if possible) to take a piece of paper by running trace and drawing what is really happening.

But in short, in the first case, you create many unknown variables covered by the fact of takeout that cannot be matched with perm .

Answer 3

Prolog uses SLD resolution , and therefore the order of sentences and the order of literals within a sentence really matters. Basically, the engine tries to resolve the heads of the clauser, first looking from top to bottom. In other words, at the top of declarative semantics is procedural semantics. This difference sometimes confuses beginners, but on the other hand, this is the key reason why Prolog is really a programming language (i.e., Turing Completion).

Answer 4

your base perm register ([], []) should appear first, otherwise it will continue to descend into the perm predicate until the stack space runs out. Keep this in mind for future predicates, it is very important in the prologue.

In addition, you should probably switch perm and takeout order in another predicate.