Failure driven loops

Question

I am trying to understand the failure driven loop for an graph for example but I don't understand how it works and when to use it. When to use fail driven loops and when to use normal recursive loops? I have some examples to check if they are correct or not. The first example has to verify that there are no vertices in a graph having an edge with the given weight.

no_given_weight(W) :-
    is_edge(X, _, W), !,
    no_given_weight(W).
no_given_weight(D) :-
    writeln("no vertex has an edge with weight D").

is_edge(X, Y, D) :-
    edge(X, Y, D);
    edge(Y, X, D).

This example is incorrect but I don't know what is incorrect. It has to verify that there are SOME vertices in graph having an edge with the given weight.

given_weight(W) :-
    is_edge(X, _, W), !,
    assertz(found(X)),
    given_weight(W).
given_weight(D) :-
    writeln("no vertex has an edge with weight D").

is_edge(X, Y, D) :-
    edge(X, Y, D);
    edge(Y, X, D).

Given the edge representation of an undirected graph, the predicate difference_graph below generates the difference graph Gdiff of G1 and G2 (assuming a predicate is_edge is present for each of the 3 graphs - G1, G2, and Gdiff):

difference_graph :-
    is_edge_1(X, Y), 
    not(is_edge_2(X, Y)), !,
    not(is_edge_diff(X, Y)),
    assertz(edge_diff(X, Y)),
    fail.
difference_graph.

is_edge(X, Y) :-
    edge(X, Y);
    edge(Y, X).

Answer 1

In general, failure-driven loops are useful when you are producing some kind of side-effect, like writing to standard output. I feel like they are a bit dirty; you are twisting the Prolog machine to make it do something for you that isn't really what it is built to do. I would always prefer to do something with recursion because failure-driven loops can hide unexpected failures, turning them into successes, and when you decide later on that you do need some result from your failure-driven loop, you can't usually have it because the bindings created are lost upon backtracking. Using the fact database to persist something behind the scenes strikes me as kind of old-school. I feel like these days we are much more inclined to think "functionally" and treat the fact store as something like a place for holding constants and maybe application configuration.

Negation is its own interesting problem in Prolog, but I think you're on the right track by thinking about the relationship between "none" and "some." To prove there are no edges with the desired weight, you try to prove that there is some edge with the desired weight, and notice that you cannot. Negation-as-failure is a consequence of what's called the "closed world assumption," basically the idea that you have told Prolog everything about the world it would need to know to make correct answers, and that there is nothing about the world that Prolog does not know (which would be the "open world assumption.") So it's better to start by writing predicates that have a positive character (find me an edge with weight D) rather than a negative character (true if there are no edges of weight D) because you can easily turn the former into the latter but you can't turn the latter into the former without tricks. For instance, given_weight/1 and no_given_weight/1 should probably look like this:

given_weight(W, X) :- is_edge(X, _, W).

no_given_weight(W) :-
    once(given_weight(W, _)) -> 
        fail 
    ; (
        format("no vertex has an edge with weight ~s", D), 
        true
    ).

In the original code, the X binding in no_given_weight/1 is a singleton variable, meaning it doesn't do anything. Pay attention to warnings about this because, especially for beginners, they often represent real failures to comprehend what is going on.

Also, these days we write \+ pred(...) instead of not(pred(...)) because that is the standard, so I suggest you adopt this notation.