A Prolog fail loop is a way of doing iteration in Prolog. For example, in this predicate (methods and functions are called predicates in Prolog because the method name is used in the predicate position of propositions used to write Prolog code), we iterate over all facts in the knowledge base that match the given ‘edge’ pattern:
buildEdges(MiddleNode, RightNode) :- LeftNode #< MiddleNode, %ECLiPSe feature: constrain LeftNode to be an int smaller than MiddleNode edge(LeftNode, MiddleNode), addEdge(LeftNode, RightNode), fail.
The reason that putting ‘fail’ at the end leads to iteration is that Prolog automatically searches for other ways of satisfying conditions, unless you tell it not to. So, if there is a fact matching the ‘edge’ pattern, and if ‘addEdge’ also succeeds, then when the interpreter reaches ‘fail’ it “backtracks” to the addEdge call to see if there were any unexplored ways of satisfying it (aka, it checks if there were any other “choicepoints”). If there were such unexplored options in addEdge, the interpreter tries the first one; if this succeeds, we return to ‘fail’; if the first one fails, it tries any others for addEdge. Once the options in addEdge are exhausted, the interpreter takes another step “upward” to see if there were any unexplored matches for the ‘edge’ pattern.
As you can see, forcing backtracking by putting ‘fail’ at the end of your conditions is one way of implementing iteration over a set of matching facts. But what you may not have expected, and what you probably don’t want, is for the interpreter to try calling ‘addEdge’ several times before looking for the next edge match. There are two standard ways of avoiding this:
- Put a condition at the start of all definitions of ‘addEdge’ that allow it to be entered only under the intended circumstances. (This isn’t a good match for the current example, because you can’t specify a condition that says “only call me once when iterating over edges”.)
- Put a cut (denoted with an exclamation point, !, in Prolog) at the end of all definitions of addEdge. A cut tells the interpreter to forget about any other choicepoints for this call of this predicate. Other tutorials about fail loops neglect to emphasize that the cut must be put at the end, because otherwise backtracking from the fail loop will explore any choicepoints remaining after the cut, even ones in your definitions of ‘addEdge’.
Side note: One can replace ‘fail’ with a condition to get do-while behavior instead of exhaustive iteration. And if one wanted to isolate a block of code for iteration (say, you want to avoid repeating the #< step), one could put “repeat,” at the start of the block, and then backtracking would never go above that point.
