CODEWITHSUNDEEP
prolog
DJPlayer
DJPlayer

Reputation: 3294

Prolog variable names

for example..

insert(X,Ys,[X|Ys]).
insert(X,[Y|Ys],[Y|Zs]) :- insert(X,Ys,Zs)

why the use of Zs as a variable.. the base case is obviously simple.. head of X::YS. but the recursive statement is going to be a continuation from the 1st goal.

so for insert(a,[b,c],L) you get L=[a,b,c] second time around you get [b,a,c] third time you get [b,c,a]

but what is the actual technical definition of Zs in the program? 

[trace] 1 ?- insert(a,[b,c],L).
   Call: (6) insert(a, [b, c], _G522) ? creep
   Exit: (6) insert(a, [b, c], [a, b, c]) ? creep
L = [a, b, c] ;
   Redo: (6) insert(a, [b, c], _G522) ? creep
   Call: (7) insert(a, [c], _G595) ? creep
   Exit: (7) insert(a, [c], [a, c]) ? creep
   Exit: (6) insert(a, [b, c], [b, a, c]) ? creep
L = [b, a, c] ;

Does the continuation begin at the recusive call? Meaning that the 1st goal ended @ the base case.. so we start next time @ the recursive? Also I can see start using different variable locations for L (aka _G522 vs _G595).

Upvotes: 1

Views: 1080

Answers (2)

zslevi
zslevi

Reputation: 409

There are no continuations in Prolog, but there's built in backtracking.

To be honest it took me some time too to understand the program.

The thing is that Prolog heavily relies on pattern matching, and choicepoints are inserted when there's more than one pattern that matches. If you want a deterministic program (i.e. without choicepoints) you have to ensure that at a time only one pattern matches (this is the recommended way), or the undesired execution path fails somewhere (this means you throw away all the calculations done in this path). The simplest way to ensure one choicepoint is using the cut operator (!/0).

"what is the actual technical definition of Zs in the program?"

In Prolog you don't have to declare variables, they can be introduced anywhere, and where they get bound (get an actual value, that's immutable) is sometimes hard to follow. Without the first predicate there would be always an unbound variable at the and of the second list, but that variable gets bound when being unified with [X|YS] in the first predicate after the recursive call. As the first predicate doesn't contain a body, the program terminates, and offers a solution to the user. As you see your program can't terminate in the second predicate, only in the first, but that's not surprising from a recursive function, just think of the classic factorial example.

factorial(0,1). 

factorial(N,F) :-  
   N>0, 
   N1 is N-1, 
   factorial(N1,F1), 
   F is N * F1.

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363627

Zs is the result of inserting X into Ys.

In Prolog, you don't usually speak of continuations, but of choice points. When insert(a,[b,c],L) has returned its first result and you start backtracking, the Prolog compiler goes back up into the call chain to find the last choice point:

  • the last operation was execution of insert's first clause, which was deterministic and bound L;
  • before that, the last operation was choosing between both clauses, which was a choice point.

Since at this choice point, the first clause was selected, the second one is chosen upon backtracking, causing Zs to be bound in the predicate. L is unbound by backtracking from the first clause and re-bound when the second option returns.

Upvotes: 1

Related Questions