Teaching pure LP with prolog and a fair search rule.

Classic Prolog has many features, and even more in its modern incarnations. Many of these features are well aligned with the view of pure Logic Programming as both a specification tool and a programming language. However, some other Prolog aspects depart from this view. Classic examples that have received much attention are assert/retract or the cut. Our focus here is however on the depth-first search rule. While well justified by practical concerns, using only depth-first from the start also introduces early on the need to reason about termination, and also possibly a need to use impure features to make different modes produce answers in finite time. Termination of course has to be faced sooner or later by any programmer, but having to do it right at the start can detract from being able to convey early on the vision of Prolog as a declarative language where one can first concentrate on problem specification and/or knowledge representation and only later worry about efficiency. We review a number of ways in which some of these issues can be tackled when teaching Prolog, while still using throughout a Prolog system. The aim is tutorial, in the hope that these ideas can help other instructors that are teaching or plan to teach Prolog. We believe that some of these considerations may also come in handy when combining Prolog with modern, AI-assisted programming methodologies.