Choice points and Redo's in Prolog

Question

After asking a question here about when exactly a Redo is called in Prolog with new variables, or when it is attempted with the same, I thought I figured it out. In the following piece of code, however, I thought that an additional Redo were to be called, but that does not seem to be the case.

My knowledge base is the following:

location(desk,office).
location(apple,kitchen).
location(flashlight,desk).
location('washing machine',cellar).
location(nani,'washing machine').
location(broccoli,kitchen).
location(crackers,kitchen).
location(computer,office).

edible(apple).
edible(crackers).

My query was

?-location(X,kitchen),edible(X).

with the following trace:

   Call: (9) location(_5612, kitchen) ? creep
   Exit: (9) location(apple, kitchen) ? creep
   Call: (9) edible(apple) ? creep
   Exit: (9) edible(apple) ? creep
X = apple ;
   Redo: (9) location(_5612, kitchen) ? creep       <====
   Exit: (9) location(broccoli, kitchen) ? creep
   Call: (9) edible(broccoli) ? creep
   Fail: (9) edible(broccoli) ? creep
   Redo: (9) location(_5612, kitchen) ? creep
   Exit: (9) location(crackers, kitchen) ? creep
   Call: (9) edible(crackers) ? creep
   Exit: (9) edible(crackers) ? creep
X = crackers.

Why is there not an additional Redo after the first solution along the lines of Redo: (9) edible(apple) (which would then fail, before going on to the next Redo) since there is still another fact in the code with the functor edible, which would mean that there was a choice point that created? I found an annotated trace of the same query here. I will post a short snippet from it, because it has the additional Redo that I feel is missing here:

Can someone point me in the right direction as to what is to be expected in this case?

Thanks.

Answer 1

It has to do with Indexing.

From SWI-Prolog Glossary of Terms

Indexing is a technique used to quickly select candidate clauses of a predicate for a specific goal. In most Prolog systems, indexing is done (only) on the first argument of the head. If this argument is instantiated to an atom, integer, float or compound term with functor, hashing is used to quickly select all clauses where the first argument may unify with the first argument of the goal. SWI-Prolog supports just-in-time and multi-argument indexing. See section 2.18.

This is one of those cases where the concept and implementation diverge.

Think of it like this, if you were to write the logic engine for Prolog and then the users wanted it to work faster you would add enhancements that made it faster, but in so doing, the way it works would not be the same as the conceptual model.

Now that the engine has enhancements you should really have a switch that turns off those enhancements when debugging so that you see what is really happening.

From Prolog Programming in Depth by
Michael A. Covington
Donald Nute
Andr´e Vellino

Sec. 4.14. Indexing pg. 111

When a Prolog system executes a query, it doesn’t have to search the entire knowledge base for a matching clause. All Prologs use INDEXING (a hashing function or lookup table) to go directly to the right predicate. For example, with FAMILY.PL, a query to mother/2 does not search the clauses for father/2.

Most modern Prologs use indexing to go further than that. They index, not only on the predicate and arity, but also on the principal functor of the first argument. For example, if you have the knowledge base

a(b).  
a(c).  

d(e).
d(f).  

then the query ‘?- d(f).’ not only won’t search the clauses for a/1, it also won’t look at d(e). It goes straight to d(f), which is the only clause whose predicate, arity, and first argument match those in the query.

Question in comment

Is there some kind of 'vanilla' or 'standard' Prolog environment for beginners where those kinds of enhancements are limited, in order to see more clearly how all the small details work and interact?

Meta-interpreters

From: A Couple of Meta-interpreters in Prolog

An interpreter for a language similar or identical to its own implementation language is called meta-interpreter (MI).

Learning about Prolog MIs are an excellent way to understand how Prolog works and also learn about MIs which are extremely useful, e.g.

Use of Prolog for developing a new programming language

Implementation in another language

Another way to see how unification works is to use the unification algorithm with backtracking implemented in another language and then use that to enhance the code outputting information you want to see. There is a miniProlog written in OCaml, but I don't suspect that many people know OCaml.

A lot of the more extensive books on Artificial Intelligence implement it.

"Paradigms of Artificial Intelligence Programming" by Perter Norvig (Lisp)

"Artificial Intelligence Structures and Strategies for Complex Problem Solving" by George F Luger (Pseudo Code)

Prolog implementations can be found on GitHub. smallProlog is very basic and done in C.

And for the theory of unification there is the classic in

"Handbook of automated reasoning" Chapter 8

Unification theory by Franz Baader and Wayne Snyder

Derivation trees

See: Prolog derivation trees, choices, and unification

Answer 2

You can visualize the redo with Byrd's box model, in this model a predicate call P has 4 ports:

            +-------+
--- call -->|       |--- exit -->
            |   P   | 
<-- fail ---|       |<-- redo ---
            +-------+

As a rule when there are no cuts for every exit there is a redo. And for every call there is ultimately a fail sometime later, except in SWI-Prolog (and maybe some other Prolog systems?):

• redo's are supressed when P deterministically succeeded
• fail's are supressed when P deterministically succeeded

Deterministic success usually results for the last clause in an index bouquet, and is seen in the non-debug top-level that the semicolon prompt is supressed. See also here:

Making "deterministic success" of Prolog goals explicit

In Jekejeke Prolog this "optimization" has not yet been implemented for the debugger. It has also deterministic success, but not when the debugger is on, thats why there are two different traces:

SWI-Prolog Trace:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.5.8)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- location(X,kitchen),edible(X).
   Call: (9) location(_3980, kitchen) ? creep
   Exit: (9) location(apple, kitchen) ? creep
   Call: (9) edible(apple) ? creep
   Exit: (9) edible(apple) ? creep
X = apple 
   Redo: (9) location(_3980, kitchen) ? creep
   Exit: (9) location(broccoli, kitchen) ? creep
   Call: (9) edible(broccoli) ? creep
   Fail: (9) edible(broccoli) ? creep
   Redo: (9) location(_3980, kitchen) ? creep
   Exit: (9) location(crackers, kitchen) ? creep
   Call: (9) edible(crackers) ? creep
   Exit: (9) edible(crackers) ? creep
X = crackers.

Jekejeke Prolog Trace:

Jekejeke Prolog 2, Development Environment 1.2.2
(c) 1985-2017, XLOG Technologies GmbH, Switzerland

?- location(X,kitchen),edible(X).
    0 Call location(X, kitchen) ? 
    0 Exit location(apple, kitchen) ? 
    0 Call edible(apple) ? 
    0 Exit edible(apple) ? 
X = apple ;
    0 Redo edible(apple) ? 
    0 Fail edible(apple) ? 
    0 Redo location(apple, kitchen) ? 
    0 Exit location(broccoli, kitchen) ? 
    0 Call edible(broccoli) ? 
    0 Fail edible(broccoli) ? 
    0 Redo location(broccoli, kitchen) ? 
    0 Exit location(crackers, kitchen) ? 
    0 Call edible(crackers) ? 
    0 Exit edible(crackers) ? 
X = crackers ;
    0 Redo edible(crackers) ? 
    0 Fail edible(crackers) ? 
    0 Redo location(crackers, kitchen) ? 
    0 Fail location(X, kitchen) ? 
No