Corouting allows a Prolog programmer to inject additional logic into called code without modifying it. The following examples show how certain common predicates can be rewritten with constraints in mind to support richer queries with very little to no changes.

The focus is on integral number constraints, namely indices and all code assumes the following import:

:- use_module(library(clpfd)).

<aside> ❗ Example implementations are intentionally naive. In-built implementations are much more robust and usually use different sub-predicates to handle different variable instantiation etc. or call optimized C code.

</aside>

Lists

A quick implementation of a length predicate looks similar to this:

length(List, Length) :-
	length(List, Length, 0).
length([], Length, Length).
length([_|T], Length, Acc) :-
	Acc2 is Acc+1,
	length(T, Length, Acc2).

This implementation leaves room for improvement: it needs to compute the whole length, even if the query could be answered without it, meaning that eg:

• length(VeryLongList, 1) will run for a very long time even if looking at the first two elements gives enough information to fail
• Cycle = [1 | Cycle], length(Cycle, 42) will loop indefinitely
• Length #< 42, length(List, Length) will either run for O(Length) or loop if List is cyclic, even tho the query could be decided in a bound time.
• Length in 5..9, length(List, Length) will loop after generating lists of length 5 to 9, despite there being no further answers.

All these problems stem from the fact, that while we iterate the list, computing its length Length in an accumulator Acc, we maintain no relationship between them until the very end of computation. In principle this is a very imperative approach: 1. compute value, 2. assign it to variable. Whatever constraints we have for the variable, we are at the mercy of the first step to first deliver the value to be checked, unless we were able to somehow inject them into the computation.

There is a relationship between Acc and Length in the form of invariant 0 <= Acc <= Length. If we put these constraints explicitly in the code, we arrive at an implementation that is just as simple as the one we started with:

/** c_length(-List, -Length)
 * Computes `Length` of `List`.
 * If Length is constrained, the predicate only goes as deep as necessary
 * to disprove the costraint.
 */
c_length(List, Length) :-
    Length #>= 0,
    c_length(List, Length, 0).

c_length([], Length, Length).
c_length([_|Tail], Length, MinLength) :- 
    Length #> MinLength,
    NewMinLength #= MinLength + 1,
    c_length(Tail, Length, NewMinLength)

In contrast to the first implementation, the new one handles the problematic queries listed above correctly, ie. it does not loop for either cyclic or unbound input, and tracing logs show that it stops as soon as the length constraints are disproved without reaching the end.

We can apply the same technique to another commonly used predicate: nth, which returns list element at the specified index. A quick implementation could look like this:

nth(List, Index, Elem) :- 
    nth(List, Index, 0, Elem).

nth([Elem|_], Index, Index, Elem).
nth([_|Tail], Index, Acc, Elem) :-
    Acc2 is Acc + 1,
    nth(Tail, Index, Acc2, Elem).