Wooden-Robot.net

How to avoid unexpected backtracking in Prolog fail loops
Posted on February 18th by david
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 ...