Full relationality: Prolog tutorial

What full relationality is

Informally, a Prolog predicate is said to be fully relational if all its arguments can be handled as either input or output. More specifically, when called with a variable in an argument, resolution successfully attempts to iterate over all the inputs that would satisfy the predicate. Often this behaviour can also be obtained for groups of arguments, or for all arguments. Often, however, this property cannot be achieved, especially for complex algorithms.

When achieved, the property really lets you obtain many functions with a single predicate: find can be used to find in lists, to iterate lists, or to generate lists.

Full relationality of find/2 at work

File relationality.pl. The programs below repeat find/2, position/3 and join/3 from the previous lessons, plus sum/3 and mul/3 on Peano numbers.

% find, position and join, over [H|T] lists
find([E|_], E).
find([_|T], E) :- find(T, E).

position([E|_], zero, E).
position([_|T], s(N), E) :- position(T, N, E).

join([], L, L).
join([H|T], L, [H|M]) :- join(T, L, M).

% sum/3 and mul/3, repeated from the Peano program
sum(X, zero, X).
sum(X, s(Y), s(Z)) :- sum(X, Y, Z).

mul(_, zero, zero).
mul(X, s(Y), Z) :- mul(X, Y, W), sum(W, X, Z).

?- find([a, b, c], E)

?- find(L, a)

?- position([a, b, c], N, E)

?- join(L, M, [a, b, c])

?- sum(N1, N2, s(s(s(zero))))

?- mul(N1, N2, s(s(s(s(zero)))))

The answers are:

find([a,b,c], E) iterates the list: E = a, b, c;
find(L, a) generates lists: L = [a|_], then [_, a|_], then [_, _, a|_], ... infinitely many;
position([a,b,c], N, E) enumerates indexed elements;
join(L, M, [a,b,c]) enumerates all ways to split a list in two;
sum(N1, N2, 3) gives the four ways to write 3 as a sum, and mul(N1, N2, 4) the products giving 4 (4·1 and 2·2), after which the search goes on without finding any further answer.

The resolution trees show find running on a list and generating one:

find([a,b,c], E)                      find(L, a)
├── {E/a}                             ├── {L/[a|_]}
└── find([b,c], E)                    └── find(T', E) : {L/[_|T']}
    ├── {E/b}                             ├── {L/[_, a|_]}
    └── find([c], E)                      └── find(T'', E) : {L/[_, _|T'']}
        ├── {E/c}                             ├── {L/[_, _, a|_]}
        └── find([], E)  → No                 └── ...

I/O notation

When documenting a predicate for a programmer, one uses a notation that is not Prolog syntax to describe the input/output character of each argument:

mark	meaning
`-`	output element
`+`	input element (of any sort)
`@`	input element that should be ground
`?`	input/output element

It is not very clear how to handle multi-modalities. Examples from the library:

member(?E, ?L).
permutation(+LI, -LO).
append(?L1, ?L2, ?L).
is(-O, @Expression).

Exercise: Prefix of a list

Write the fully relational list_prefix(P, L): P is a prefix of the list L (possibly empty, possibly the whole list). It must work with L given and P unknown, and with both given.