How does pruning choice points in the code below make it more efficient (Prolog)?

Question

In the code given below, there is the ! (cut) that prunes the choice point for efficiency. I am pretty certain that the reverse predicate and the agent_do_moves predicate are essential.

solve_task(Task,Cost):-
    agent_current_position(oscar,P),
    solve_task_a(Task,[b(0,0,P)],[],R,Cost,_NewPos),!,  % prune choice point for efficiency
    reverse(R,[_Init|Path]),
    agent_do_moves(oscar,Path).

Cullum

What exactly is your question? Do you need an explanation of how ! works in general? – Bedstraw

@Lenz yes, I am a bit confused as to why an essential part of the predicate is being cut for efficiency. – Cullum

I take it you didn't write this predicate yourself, but rather you are trying to understand somebody else's code. In short: the cut doesn't cut off reverse/2 and agent_do_moves/2, but rather it cuts off alternative solutions to agent_current_position/2 and solve_task_a/6. So once these two have been proven once, they won't be reconsidered for other possible solutions (no backtracking). – Bedstraw

@Bedstraw No I didn't write these predicates, and I was just confused as agent_current_position does not give more than one answer. – Cullum

Answer 1

The cut in above examples has the following effect:

Ideally, it commits the search which might happen within solve_task_a/6 to the first answer found. This frees resources for finding further answers which improves space consumption.

Scope problems

However, at the same time, it might also hide further answers to agent_current_position/2. Of course, it does not make much sense to have further answers for this goal, but it might be an error that happens to sleep for a while, only to become active but still undiscovered in the worst possible situation.

For this reason, it would be preferable to write instead of the cut

    ...,
    once( solve_task_a( ... ) ),
    ...

This limits the scope precisely to what you want to express.

Steadfastness problem

But this is not the only possible source of problems. I see this variable Cost. Will it be instantiated when you call solve_task(Task, Cost) or not? I could do a lot of guessing here. But at least this variable might influence the answer Prolog will commit to. So solve_task(Task, 99) and solve_task(Task, Cost), Cost = 99 might produce different answers. In fact, the latter might even fail. Predicates that have such problems are said to lack steadfastness.

To illustrate how steadfastness is easily lost in such a situation consider this (runnable) sketch of your (already improved) program:

solve_task(Task,Cost):-
    % agent_current_position(oscar,P),
    once(solve_task_a(Task,[b(0,0,P)],[],R,Cost,_NewPos)),
    true.

solve_task_a(_, _, _, _, 20, _).
solve_task_a(_, _, _, _, 30, _).

Now

?- solve_task(a, Cost).
   Cost = 20.
?- solve_task(a, 30).
   true.
?- solve_task(a, Cost), Cost = 30.
   false.

There would be an easy way out of this problem by cleanly testing variable Cost, e.g. Cost >= 0 which produces an instantiation error should Cost be an uninstantiated variable. But if you want (as you indicate in your comment) to determine the cost, you need to put it like so:

solve_task(Task,Cost):-
    % agent_current_position(oscar,P),
    once(solve_task_a(Task,[b(0,0,P)],[],R,CostX,_NewPos)),
    CostX = Cost
    true.

In this manner we can be sure that Cost cannot influence the outcome of solve_task_a/6 (euh - provided there is no aliasing between Cost and Task - but let's assume that for the moment). One says also that output unifications are put behind the commit.

Many people will tell you that such extra care is not needed, as you will never use solve_task(Task, Cost) with a given cost. That might be the case, but are you sure you will remember it? And are you sure the source code will remember it (without any dynamic check)? Such implicit assumptions easily accumulate to a degree were your mental capacities are overburdened.

There is not always an easy way out. But quite often it is possible to stick to logical purity logical-purity. In that case, you do not have to remember any such assumptions.

---

_{In any case, I would recommend that you do not go into these parts of Prolog for the moment. Rather stick to successor-arithmetics, clpfd, and other clean, monotonic programs preserving logical-purity. There is a lot to learn!}

Nietzsche

perfect answer once again. The fact that there might be more answers to agent_current_position and even if there were, cutting them wouldn't be for efficiency but for accuracy, was baffling me – Cullum

to answer your question, Cost is instantiated after calling solve_task, so I guess it is steadfast? This code isn't mine and I am currently doing an assignment. Therefore, I unfortunately do not have a choice about what I can learn. – Cullum