Concept questions about complex terms in Prolog

Question

I've just started learning Prolog at college and I have a concept question for which I don't find any concrete answer:

I want to interiorize the "philosophy" of this language, so I want to understand very precisely what a complex term is (or compound term). By now, I've read that a complex term is a functor and it's arity. And I can build a Knowledge Base using complex terms like this:

love(john, sarah).

Let's say that now, I can enter any possible string pair as the argument of "love" and it will be false unless the string pair is "john, sarah". Right, so a "question" of a functor and it's arguments, is something that is true or false depending in if I have said that specifically in my knowledge base or if Prolog can infer it from the info he has using rules, unification, etc.

Right, since here, I understand that a complex term says that a relationship between n entities is true or false. What I don't understand is this:

vertical(line(point(X,Y),point(X,Z))).

I understand what point(X, Y). does. It is saying that any entity is related to any other entity through "point". What I don't understand is how point(X, Y) can be the argument of line! Until now, a complex term was just saying if the entities were related or not. I could understand that it is a "traditional function" which returns true or false if the entities are related. But how can that be the argument of line? "line" in theory, has 2 arguments (entities) and it will say if they are related or not. Now, the arguments' values are true or false?

I could understand that "point(X,Y)" is creating an object "point". So the argument of line is a "point entity". But that is not what I've read about complex terms so far, so I would love a technical definition which explains that nested cases.

(I'm sorry if I've used wrong terms or definitions, I'm new in Prolog)

Thanks!

Answer 1

This is a good question in that it is a fundamental confusion point for Prolog many Prolog beginners having come from a background of imperative languages. My advice when learning Prolog is usually, "Forget (almost) everything you have learned about programming and start from the fundamentals".

Prolog is built on terms which can have zero or more arguments. foo is a term with no arguments. foo(A, B) is a term with two arguments. foo(bar(X), bah(Y,Z)) is a complex term with two arguments (referred to as foo/2), and its arguments consist of terms bar/1 (having one argument) and bah/2 (having two arguments).

Even a predicate clause is a term of the form Head :- Body or in canonical form, ':-'(Head, Body). When that kind of term is asserted in a Prolog program (declared statically in the file, or even dynamically asserted), Prolog recognizes it as a predicate because Prolog assigns special meaning to some term functors, and :- in this case is for predicate clause definition. But without that context, ':-'(A, B) is still "just a term".

In Prolog, outside of the predefined terms (such as :-, operators, etc) the semantics of a term that the programmer defines depends simply upon what the programmer decides and the context (query? asserted? part of another term?) in which it is used in their program.

I understand what point(X, Y). does. It is saying that any entity is related to any other entity through "point".

In Prolog, point(X, Y) is a term with two arguments (point/2) that has no semantic meaning (doesn't "do" anything) except as the programmer decides and then as they use it in the program. If I enter point(X, Y) at the Prolog prompt like so:

?- point(1, 2).

Prolog sees this as a query and attempts to find facts or rules that match point(1, 2) and allow it to succeed. If, however, I entered:

?- foo(point(1, 2)).

Prolog just sees a query on foo/1 looking for facts or rules that match foo(_) and point(1, 2) is "just a term" without further interpretation unless there's a predicate clause that puts it in a context which does so. For example, if for foo/1 I only had one fact foo(a). in my database and no rules for foo/1, foo(point(1, 2)). would fail because Prolog would try to match the term a (a term with zero arguments) with the term point(1, 2Y) (a term with 2 arguments) and would fail, and there would be no other choices to try. If I had a clause for foo/1 that looked something like this:

foo(X) :-
    X = point(A,B),
    ...   % do some things involving A and B

Then the query foo(point(1,2)) would match the head of this clause by unifying X with point(1,2), then the first line of this clause would unify point(1, 2) = point(A, B) and unify A = 1 and B = 2, etc. point/2 in this context is not called or executed in any way.

Let's suppose I had the following foo/1 clause:

foo(X) :-
    call(X),
    ...

Now if I query, foo(point(1, 2))., foo/1 will attempt to call point(1, 2) (execute it as a query) and Prolog will attempt to find facts or rules that match point(1, 2).

What I don't understand is how point(X, Y) can be the argument of line!

Remember, it's just a term. It has no semantics unless used in a specific context. Until you exercise the term in a certain way in Prolog, there's no meaning except in the mind of the programmer. The programmer can decide to define a term line(A, B) which represents a line from point A to point B. If we have a term we like to define a point on two coordinates, point(X, Y), we can also say line(point(X1, Y1), point(X2, Y2)). By programmer convention, this means, I have a line from point at (X1, Y1) to point at (X2, Y2).

Until now, a complex term was just saying if the entities were related or not.

I'm not sure why you say "until now". The user decides what that relationship is, and how to organize the (complex) term to represent that relationship. When we say, line(point(X1, Y1), point(X2, Y2)) that can (at the discretion of the programmer) represent a line from point (X1, Y1) to (X2, Y2).

I could understand that it is a "traditional function" which returns true or false if the entities are related.

This is not true. The term does not form a "traditional function" that returns true or false. It is just a term and doesn't return anything. In Prolog, as I mentioned, the behavior of a term does depend upon context. A term can be a query which means it is called, and Prolog will try to determine (through previously asserted facts and rules/predicates) that it is provable or true. In that case, it is matching facts or rules to the top level term functor name. So if you actually queried line(point(X1, Y1), point(X2, Y2)), Prolog would look for facts or rules matching line(_, _) and go from there. It would then succeed or fail depending upon whether it could match facts, or successfully complete a rule.

But how can that be the argument of line? "line" in theory, has 2 arguments (entities) and it will say if they are related or not.

line(point(X,Y), point(X,Z)) is a term that, by convention of the programmer, represents a line from point (X, Y) to point (X, Z).

Now, the arguments' values are true or false?

No, the arguments don't have any value at all. They are just terms or structures that define something the programmer has chosen to represent.

I could understand that "point(X,Y)" is creating an object "point".

It doesn't create an object. It is just a term that represents a point at abscissa X and ordinate Y.

So the argument of line is a "point entity".

line/2 has two arguments which represent the two distinct points that define a line (by convention of the programmer). If it's expressed as line(P1, P2) then the "form" of the points is not specified (the programmer could choose to represent a point with a list, such as [X, Y], or as in this case, a user-defined term, point(X, Y)).

But that is not what I've read about complex terms so far, so I would love a technical definition which explains that nested cases.

What have you read about complex terms so far? In order to help with that, we'd need to know what you read that seems confusing to you.

---

You haven't shown any code for context, so let's make up some context to help understand this. I will choose to define a point to look like point(X, Y), and a line to look like line(P1, P2) where P1 and P2 are points. Thus, I can also represent a line as line(point(X1, Y1), point(X2, Y2)). This is my choice as a programmer.

How might I define a valid point in Prolog? I can define it with the term point(X, Y). But what are X and Y? How can they be defined? I might enforce that they be numbers. So here is a rule for a valid point:

valid_point(P) :-
    P = point(X, Y),   % a Point looks like point(X, Y)
    number(X),
    number(Y).

In Prolog I can simplify this a bit since I can use a complex term for the head of a clause:

valid_point(point(X, Y)) :-
    number(X),
    number(Y).

So valid_point(point(X, Y)) only succeeds if X and Y are both numbers. If you were to ask Prolog if (point(3, 5.2) is a valid point (query valid_point(point(3, 5.2))., it would succeed (say "true"). If you were to ask Prolog if point(a, 3) is a point (query valid_point(point(a, 3))., it would fail (say "false").

Let's now define a line. A line is defined by any two points, so we can represent it as the term line(P1, P2) where P1 and P2 are valid points that are not identical. We can therefore define a valid line as follows. I'm going to show this verbosely to see how terms can be unified and used:

valid_line(Line) :-
    Line = line(P1, P2),
    P1 = point(X1, Y1),    % P1 is a valid point
    valid_point(P1),    
    P2 = point(X2, Y2),    % P2 is a valid point
    valid_point(P2),
    ( X1 =\= X2 ; Y1 =\= Y2 ).

Again, Prolog lets me use compound terms to simplify this further:

valid_line(line(point(X1, Y1), point(X2, Y2))) :-
    valid_point(point(X1, Y1)),
    valid_point(point(X2, Y2),
    ( X1 =\= X2 ; Y1 =\= Y2 ).

This rule says that point(X1, Y1) and point(X2, Y2) form a valid line if they are valid points, and either X1 and X2 are not equal, or Y1 and Y2 are not equal.

Let's move on to a higher level rule. A line is vertical if the line is valid and its points have the same abscissa. We can create a rule, vertical_line which succeeds if the line argument is vertical and fails otherwise:

vertical_line(line(point(X1, Y1), point(X2, Y2)) :-
    valid_line(line(point(X1, Y1), point(X2, Y2)),
    X1 = X2.

We can abbreviate this by unifying the abscissas in the head of the clause:

vertical_line(line(point(X, Y1), point(X, Y2))) :-
    valid_line(line(point(X, Y1), point(X, Y2)).

In all of the above examples, I've separated my rule names from my data structre names. So I have valid_line/1 as a rule, but line/2 representing a structure for a line. There's no reason they have to be separated, but it can help avoid confusion if they are. Even if they are the same, whether Prolog executes it as a query will depend upon context. For example, I could define a rule point/2 that succeeds only if the arguments are numbers:

point(X, Y) :-
    number(X),
    number(Y).

Then I can query:

?- point(1, 3).
true

?- point(a, 7).
false.

However, if I then define line/2:

line(P1, P2) :-
    P1 = point(X1, Y1),
    P2 = point(X2, Y2),
    ( X1 =\= X2 ; Y1 =\= Y2 ).

This will not enforce a valid point (does not call point/2) when doing the unification P1 = point(X1, Y1). This is because predicates in Prolog are not functions and do not behave that way. If I were to query, line(point(a, 3), point(c, d)) it would probably generate an error since I'm trying to compare the coordinates numerically with (=\=)/2. The expression P1 = point(X1, Y1) is really the term '='(P1, point(X1, Y1)) in Prolog. Just as I mentioned above, when Prolog does a call, it is on the top level term, which is, in this case '=', and the point(X1, Y1) is "just a term" and not called in this context. I could call point/2 though as follows:

line(P1, P2) :-
    P1 = point(X1, Y1),
    call(P1),
    P2 = point(X2, Y2),
    call(P2),
    ( X1 =\= X2 ; Y1 =\= Y2 ).

And then Prolog will more elegantly check the validity of the point (per the point/2 predicate I defined). But I don't think this is as clear as defining the valid_... predicates separately.

Answer 2

I understand that a complex term says that a relationship between n entities is true or false [...] "line" in theory, has 2 arguments (entities) and it will say if they are related or not.

Your interpretation of "complex terms" is, unfortunately, wrong. Prolog uses such terms to represent both "programs" and "data", so the interpretation of a term depends on the context it appears in and how it is used.

Consider your first example:

love(john, sarah).

From the period at the end (and from the fact that you mentioned this in the context of knowledge bases), we know that this must appear as a top-level construct in a Prolog file. Such terms define clauses of predicates. These are the "programs": This term defines (one clause of) a predicate love/2 (the /2 is the usual Prolog notation for a term's arity, i.e., number of arguments). We can use this as a "program" by "calling" it:

?- love(X, Y).
X = john,
Y = sarah.

In this "program" context, we can really say that love/2 is a relation between two terms.

But in your second example, the line term does not appear at the top level. It is nested inside a vertical/1 term:

vertical(line(point(X,Y),point(X,Z))).

This means the "program" being defined is vertical/1, a one-place relation on terms. (It's more natural to call it just "a set of terms". In this example, "the set of vertical lines is the set of all lines on which two points have the same X coordinate".) line/2 is not being defined as a relation; it is simply uninterpreted data. We can call vertical/1:

?- vertical(T).
T = line(point(_G921, _G922), point(_G921, _G925)).

But not line/2:

?- line(P1, P2).
ERROR: toplevel: Undefined procedure: line/2 (DWIM could not correct goal)

Summary: Only "top-level" terms define predicates, and only these terms can necessarily be interpreted as relations. Other terms occurring in the program are only the "data" that relations talk about.