prologprolog-coroutining

What is the approach for dealing with "residual goals" in Prolog?


Consider this program as an example. It uses a delayed goal

room(green).
room(blue).
room(red).
room(white).

location(jimmy,red).
location(ricky,blue).
location(cindy,green).

% "Is a certain room unoccupied?"
   
not_occupied(Room) :-
   nonvar(Room),
   assertion(room(Room)),
   \+ location(_Person,Room).

% If no specific "Room" has been given, the negated goal is
% delayed until the "Room" has been instantiated.

not_occupied(Room) :-
   var(Room),
   !,
   when(
      ground(Room),
      (\+ location(_Person,Room))
   ).

If I now ask

?- not_occupied(R).

then Prolog succeeds and outputs a residual goal

?- not_occupied(R).
when(ground(R),\+location(_7676,R)).

In effect, it doesn't really succeed. It succeeds optimistically (because in order to not stop the computation, succeed it must) but the actual logical success is dependent on actual success of the residual goal.

How do I find out programmatically whether a subgoal succeeded with a residual goal? (And what do I do then?) What is the approach?

P.S.

Having a secondary Prolog truth value might be a nice Prolog extension, in that a true+ would indicate "success under condition that the residual goals succeed". This actually seems to be of some necessity:

In SWI-Prolog, take this inherently ambiguous goal:

do :- not_occupied(_).

Calling it does not even print out any residual goal at all:

?- do.
true.

Did the goal succeed? Not really, it's still in logical limbo, but the toplevel doesn't even tell me. On the other hand there is no way to feed more information into the program to resolve residual goals. But defaulting to "success" because the computation ran to its end feels wrong.


Solution

  • A query that cannot resolve its residual goals is called a floundering query. Computations can flounder when they are intended to succeed or finitely fail. Residual goals introduce a third state that is neither success nor finitely failed.

    Constraint logic programs can fail to invoke certain constraint solvers because variables are insufficiently instantiated or constrained. To avoid floundering in constraint solvers, they often offer labeling as a last resort.

    The third state is seen in the top level, when residual goals are listed. And it is implementation dependent how residual goals can be queried. Typical predicates are:

    That SWI-Prolog doesn't print the residue variables in the toplevel, is a service by SWI-Prolog, to only show the projected variables. But you can neverthless query the residue:

    /* SWI-Prolog */
    ?- do.
    true.
    
    ?- call_residue_vars(do, X).
    X = [_5968],
    when(ground(_5968), \+location(_6000, _5968)).
    

    Pitty that SWI-Prolog doesn't support call_residue/2. copy_term/3 is not really a substitute. In my Prolog system I have stopped computing a projection in the top-level and display everthing. Also I do support call_residue/2:

    /* Jekejeke Prolog */
    ?- do.
    when(ground([_A]), \+ location(_B, _A))
    
    ?- call_residue_vars(do, X).
    X = [_A],
    when(ground([_A]), \+ location(_B, _A))
    
    ?- call_residue(do, X).
    X = [when(ground([_A]), \+ location(_B, _A))],
    when(ground([_A]), \+ location(_B, _A))
    

    call_residue/2 is also found in ECLiPSe Prolog and SICStus Prolog. In SICStus Prolog it returns a pair list, also showing principal variables. ECLiPSe Prolog on the other hand only returns dummy variables. And then there are compatibilty issues for call_residue_vars/2 like here.