CODEWITHSUNDEEP
prologprolog-cut
eshtabel3asal
eshtabel3asal

Reputation: 51

how does the cut placement in prolog affect output?

I'm very confused about the placement of cuts. Not sure how they impact the output. What is the difference between each of the cuts in the following positions?

subset([], _) :- ![1].
subset([H|T], S) :- ![2], member(H, S), ![3], subset(T, S), ![4].

Can you please explain it in simple English? and how does each position affect the output?

Upvotes: 1

Views: 73

Answers (1)

brebs
brebs

Reputation: 4438

Here's a theory-heavy explanation, as my attempt to explain cuts clearly and concisely:

Prolog executes a program from top to bottom, then left to right, as per standard languages, and what we would intuitively assume. Execution order is completely predictable (otherwise, reliable programs would be impossible to write).

As the code execution proceeds, Prolog chooses the first previously-untried choice available, but makes a note of alternative code paths available at that point to try instead ("choicepoints"), for when backtracking is triggered.

A cut will remove those choicepoints within the same predicate, i.e. the combination of same predicate name and predicate arity. Arity is simply the number of arguments in the head of a predicate. All other choicepoints previously encountered will remain as valid choicepoints.

After a cut is executed, the only way within that predicate is forward. Backtracking is still possible to a choicepoint in a previously-encountered, different predicate.

A predicate can contain zero, one or many cuts.

Two immediately-consecutive cuts is valid code, but pointless, because there will have been no choicepoints encountered in-between for the second cut to remove.

The implicit program flow in Prolog can be demystified by using e.g. trace and gtrace - Prolog programs can be debugged.

Upvotes: 1

Related Questions