SLD-Resolution, choice of atom

[Uzaku1991]

Hey,
right now I am learning prolog, my problem is SLD resolution. My script says, that the choice of an atom in the query, for a SLD-resolution-step does not affect the result. I couldnt really wrap my head around it, so I just tried a sample.

I wrote this little "program":

sumList([Number], [OutNumber]):- OutNumber is Number + 1.
sumList([HeadIn|BodyIn], [HeadOut|BodyOut]):-
    sumList(BodyIn, BodyOut),
    HeadOut is HeadIn + 1.
   
sqList([Number], [OutNumber]):- OutNumber is Number * Number.
sqList([HeadIn|BodyIn], [HeadOut|BodyOut]):-
    sqList(BodyIn, BodyOut),
    HeadOut is HeadIn * HeadIn.

For the query:

?- sumList([2,3,4], O1), sqList(O1, O2).

I get the result:

O1 = [3, 4, 5],
O2 = [9, 16, 25]

which is exactly what I expected, but when I try to change the order in the query (because the order does not seem to matter) like this:

?- sqList(O1, O2), sumList([2,3,4], O1).

I get the following error:

ERROR: is/2: Arguments are not sufficiently instantiated
   Exception: (7) sqList(_G412, _G413) ? creep

Could someone explain me, why the error is there, and maybe, why order should not matter (or does it?)

Best regards
Uzaku

[Markus Triska]

Hi Uzaku,

(is)/2 is not a true relation, because it cannot be used in all directions. Therefore, you cannot reason in this way about it, as the algebraic properties you expect from logical relations (in this case: commutativity of conjunction) do not hold for these low-level primitives.

There is a declarative alternative which should be used instead to obtain more general and declarative programs, especially if you are just beginning to learn Prolog: You get the behaviour you expect if you simply use constraints instead of low-level arithmetic predicates. Constraints can be used in all directions as true relations and are therefore much easier to understand.

For constraints over integers, add:

:- use_module(library(clpfd)).

at the beginning of your program, and replace (is)/2 by (#=)/2 throughout.

alsoPleaseConsiderWhatYouFindEasierToRead: mixed_caps_or_underscores_for_predicate_names?

After these changes, the second query also yields a solution:

?- sq_list(O1, O2), sum_list([2,3,4], O1).

O1 = [3, 4, 5],
O2 = [9, 16, 25]

and lets you observe its nontermination when you press SPACE.

In addition, the resulting predicates can also be used in the most general way (i.e., all arguments variables) , which was not possible before.

All the best,
Markus

[Uzaku1991]

Hey,
thanks a lot, but now I'm wondering, why I get a solution at all, when I try to reconstruct the steps, that prolog takes, I would expect it, to be stuck in the recursive call of sqList?
It is the leftmost atom in the query, and the version were there is only one number in the in- and outlists wont be reached, right?

[Markus Triska]

Hi Uzaku,

again a very good question, and which you can again answer with declarative thinking:

Instead of the conjunction, try the more general, single goal:

?- sq_list(X, Y).

and see that it yields one solution after another without being stuck anywhere. Once you understand how this is possible, it will be clear why the conjunction also yields a solution, because the termination properties and meaning of the other predicate can be readily soon from its definition.

This is a good example why you should focus less on the actual steps that Prolog performs, but on declarative properties as you did initially. Focus on a pure, declarative and clear description of what holds, and it will be much easier to reason about what your programs are actually able to do.

All the best!
Markus

[Uzaku1991]

Hey,
I understand, that from your point, I should only focus on the declarative part, since prolog is a declarative language, but the point is, I have troubles with the declarative thinking (I asume, that because I have been programming imperativly for 8 years now). So what I try to do, is REALLY understanding the declarative paradigm by seeing it decomposed into its imperative steps.

So, as far as it looks to me, when I call

?- sq_list(X, Y).

Prolog interprets X and Y as one element list, with anonymous variables? And when that "fails" (because I request another solution) it interprets them as list with 2 anonymous variables? I guess it started with empty lists, but that failed too?
And the reason why the query with sum_list also works, is that it tries this so long, until the Lists have as many variables as the inputlist, that I defined by hand?

[Markus Triska]

Hi Uzaku,

you can easily see the precise steps Prolog performs in the tracer: Try

?- gtrace, sq_list(X, Y).

to see what is going on.

The most interesting and relevant properties cannot be seen from a trace, so beware its limited use.

All the best,
Markus

[Uzaku1991]

Hey,
thanks a lot for your answers. I'm sure I'll be back with other questions :D