Chapter 2

Syntax and Data Objects

Prof. N. G. J. Dias
Senior Professor
Department of Computer Systems Engineering,
Faculty of Computing and Technology,
University of Kelaniya,
Kelaniya
Learning outcomes
At the end of this chapter, students should be able to
• Understand syntax and semantics of basic concepts of Prolog,
• Differentiate between simple and structured data objects, and
• Explain the matching technique, i.e., the fundamental operation of objects in
Prolog.

1 May 2025 NGJD@FCT-UoK 2

2.1 Data objects
• Following figure shows a classification of data objects in Prolog.
Data objects

Simple objects Structures

Constants Variables

Atoms Numbers
• Simple objects are either Variables or Constants and a constant is either a Number or
an Atom.

1 May 2025 NGJD@FCT-UoK 3

 • The Prolog system recognizes the type of an object in the program by its
syntactic form.
• This is possible because the syntax of Prolog specifies different forms for each
type of data objects.
• No additional information (such as datatype declaration) has to be
communicated to Prolog in order to recognize the type of an object.

1 May 2025 NGJD@FCT-UoK 4

 2.2 Constants
• Constants are either Atoms or Numbers.
• Atoms can be constructed in three ways:
1. String of letters, digits and the underscore character starting with
lowercase letter.
Examples: ann, anil, x25, x_25, x_AB, x__y, parent_of, has_a_child.
2. String of special characters
Examples: <-->, ==>, … , ::=
When using atoms of this form, some care is necessary because some
strings of special characters already have a predefined meaning.
For example, some strings such as :- and [ ] have a special meaning.
3. String of characters enclosed in single quotes.
Examples: ‘Tom’, ‘America’, ‘X’, ‘Sunil’.
1 May 2025 NGJD@FCT-UoK 5
 This form is useful if we want, for example, to have an atom that starts with a
capital letter.
By enclosing it in quotes we make it distinguishable from variables.
• Numbers used in Prolog include integer numbers and real numbers.
• The syntax of integers is simple, as illustrated by the following examples:
1 1313 0 -97
Not all integer numbers can be represented in a computer, therefore the range of
integers is limited to an interval between some smallest and some largest number
permitted by a particular Prolog implementation.
• The syntax of real numbers is as shown by the following examples:
3.14 -0.0035 100.2 7.15E-9
The last example uses the exponent notation and is equivalent to 0.00000000715.
1 May 2025 NGJD@FCT-UoK 6
• Some care is needed when using real numbers because of numerical errors that
arise due to rounding when doing arithmetic.

1 May 2025 NGJD@FCT-UoK 7

2.3 Variables
• A Variable is a String of letters, digits or underscore character beginning with an
upper case letter or an underscore character.
Examples: X, Result, Tom, ShoppingList, _x23,_23, _A, Object2 are all variables.
• When a variable appears in a clause once only, we do not have to invent a name
for it.
We can use the so-called 'anonymous‘ variable, which is written as a single
underscore character, i.e., the underscore character alone denotes an
anonymous variable.

1 May 2025 NGJD@FCT-UoK 8

• For example, let us consider the following rule:
has_a_child(X) :- parent(X, Y).
This rule says:
for all X, X has a child if X is a parent of some Y.
We are defining the property has_a_child which, as it is mean there, does not
depend on the name of the child.
Thus, this is a proper place in which to use an anonymous variable.
The clause above can thus be rewritten:
has_a_child(X) :- parent(X, _).
• Each time a single underscore character occurs in a clause it represents a new
anonymous variable.

1 May 2025 NGJD@FCT-UoK 9

 For example, we can define that an object is visible it is seen by the camera at some
arbitrary coordinate position (𝑋, 𝑌):
visible(Object) :- see(Object, _, _).
This is equivalent to
visible(Object) :- see(Object, X, Y).
But this is, of course, quite different from:
visible(Object) :- see(Object, X, X).
• If the anonymous variable appears in a question, then its value is not output when
Prolog answers the question.
For example, if we are interested in people who have children, but not in the names
of the children, then we can simply ask:
?- parent( X, _).

1 May 2025 NGJD@FCT-UoK 10

• The lexical scope of variable names is one clause. This means that, for example, if
the name X occurs in two clauses, then it signifies two different variables.
But each occurrence of X within the same clause means the same variable.
• The situation is different for constants: the same atom always means the same
object in any clause - that is, throughout the whole program.

1 May 2025 NGJD@FCT-UoK 11

2.4 Structures
2.4.1 Defining structures
• Structured objects ( or simply structures) are objects that have several components.
For example, the date can be viewed as a structure with three components: day,
month, year.
• The components can be either constants, variables or other structures.
• Although composed of several components, structures are treated in the program
as single objects.
• In order to combine the components into a single object we have to choose a
functor.

1 May 2025 NGJD@FCT-UoK 12

• For example, a suitable functor for our example is date.
Then the date 1st May 2020 can be written as:
date(1, may, 2020).
All the components in this example are constants (two integers and one atom).
• Since, components can also be variables or other structures, any day in May can be
represented by the structure:
date(Day, may, 2020)
Note that Day is a variable and can be instantiated to any object at some later point
in the execution.

1 May 2025 NGJD@FCT-UoK 13

• Now we can formally define a structure as follows:
A structure in Prolog is a functor (a Prolog atom which is a name of a predicate or
operator) followed by a list of arguments separated by commas and enclosed in
round brackets.
• The number of arguments following a functor in a stucture is called the arity of the
functor.
• More examples:
1. parent(pam, bob)
2. sister(X, pat)
3. book(title(‘Art of Prolog’), author(‘Leon Sterling’, ’Ehud Shaprio’) ).
4. Lists in Prolog (See Chapter 3 for more details.):
.(Head,Tail).
1 May 2025 NGJD@FCT-UoK 14
 • This method for data structuring is simple and powerful.
It is one of the reasons why Prolog is so naturally applied to problems that
involve symbolic manipulation.
• Syntactically, all data objects (simple or structured objects) in Prolog are terms.
For example,
may, date(1, may, 2020), X, parent(pam, bob), sister(X, pat), 2020, 37.4
are all terms.

1 May 2025 NGJD@FCT-UoK 15

 2.4.2 Tree structure of structured objects
• All structured objects can be pictured as trees.
• The root of the tree is the functor, and the children of the root are components
(arguments).
• If a component (argument) is also a structure then it is a sub tree of the tree
that corresponds to the whole structured object.
Examples:
1. parent(pam,bob).
parent

pam bob

1 May 2025 NGJD@FCT-UoK 16

 2. book(title(‘Art of Prolog’), author(‘Leon Sterling’, ’Ehud Shaprio’) ).
book

title author

‘Art of Prolog’ ‘Leon Sterling’ ‘Ehud Shaprio’

3. Lists in Prolog: .(Head,Tail).

.
Head Tail

1 May 2025 NGJD@FCT-UoK 17

 4. This example will show how structures can be used to represent some simple
geometric objects.

A point in two-dimensional space is defined by its two coordinates; a line

segment is defined by two points; and a triangle can be defined by three
points.
1 May 2025 NGJD@FCT-UoK 18
 Let us choose the following functors:
point for points,
seg for line segments, and
triangle for triangles.
Then the objects in the above figure can be represented by the following Prolog
terms:
P1 = point(1,1)
P2 = point(2,3)
S = seg( P1, P2) = seg( point(1,1), point(2,3))
T = triangle( point(4,2), point(6,4), point(7,1) ).
The corresponding tree representation of these objects is shown in the following
Figure.
1 May 2025 NGJD@FCT-UoK 19
1 May 2025 NGJD@FCT-UoK 20
 5. Following figure shows the tree structure that corresponds to the arithmetic
expression 𝑎 + 𝑏 ∗ (𝑐 − 5).

According to the syntax of terms introduced so far this can be written, using the
symbols '* ', ‘+' and '-' as functors, as follows:
∗ (+ 𝑎, 𝑏 , − 𝑐, 5 ).
This is of course a legal term in Prolog.

1 May 2025 NGJD@FCT-UoK 21

• In general, the functor at the root of the tree is called the principal functor of the
term.
For example, seg is the principal functor in the term seg( point(1,1), point(2,3)).
Also, triangle is the principal functor in the term
triangle( point(4,2), point(6,4), point(7,1) ).

1 May 2025 NGJD@FCT-UoK 22

 Exercise
Which of the following are syntactically correct Prolog objects? What kinds of
object are they (atom, number, variable, structure)?
(a) Diana
(b) diana
(c) 'Diana'
(d) _diana
(e) 'Diana goes south’
(f) goes(diana, south)
(g) 45
(h) 5( x, Y)
(i) +( north, west)
(j) three( Black( Cats) )
1 May 2025 NGJD@FCT-UoK 23
2.5 Matching
• In the previous section we have seen how terms can be used to represent
complex data objects.
• The most important operation on terms is matching.
• Given two terms, we say that they match if:
(1) they are identical, or
(2) the variables in both terms can be instantiated to objects in such a way that
after the substitution of variables by these objects the terms become
identical.
• Matching is a process that takes as input two terms and checks whether they
match.

1 May 2025 NGJD@FCT-UoK 24

• If the terms do not match we say that this matching fails.
If they do match then the matching succeeds and it also instantiates the variables in
both terms to such values that the terms become identical.
• The request for this matching operation can be communicated to the Prolog system
by the following question, using the operator ‘=':
?_date( D, M, 2019) = date( D1, may, Y1).
The instantiation
D = D1
M = may
Y1 = 2019
makes both terms identical and hence achieves the match.
• There are, however, other instantiations that also make both terms identical (More
details in Part II of this course.).
1 May 2025 NGJD@FCT-UoK 25
• Now we can express the following general rule to decide whether two given terms
match.
• The general rules to decide whether two terms, S and T, match are as follows:
(1) If S and T are constants then S and T match only if they are the same object.
(2) If S is a variable and T is anything, then they match, and S is instantiated to T.
Conversely, if T is a variable then T is instantiated to S.
(3) If S and T are structures then they match only if
(a) S and T have the same principal functor, and
(b) all their corresponding components match.
the resulting instantiation is determined by the matching of the components.

1 May 2025 NGJD@FCT-UoK 26

• The last of these rules can be visualized by considering the tree representation of
the terms: triangle( point(1,1), A, point(2,3)) and triangle( X, point(4,Y), point(2,Z))
given in the following Figure:

- The matching process of the two terms starts at the root (the principal
functors).
As both functors match, the process proceeds to the arguments where
matching of the pairs of corresponding arguments occurs.
1 May 2025 NGJD@FCT-UoK 27
 - So the whole matching process can be thought of as consisting of the following
sequence of (simpler) matching operations:
triangle = triangle,
point(1,1) = X,
A = point(4,Y),
point(2,3) = point(2,Z).
- The whole matching process succeeds because all the matchings in the
sequence succeed.
The resulting instantiation is:
X = point(1,1)
A = point(4,Y)
Z=3

1 May 2025 NGJD@FCT-UoK 28

Exercise
Will the following matching operations succeed or fail? If they succeed, what are
the resulting instantiations of variables?
(a) point( A, B) = point( 1, 2)
(b) point( A, B) = point( X, Y, Z)
(c) plus( 2,2) = 4
(d) +( 2, D) = +( E,2)
(e) triangle( point(-1,0), P2, P3) = triangle( P1, point(1,0), point(0,Y) )
The resulting instantiation defines a family of triangles. How would you describe
this family?

1 May 2025 NGJD@FCT-UoK 29

2.6 A note on Prolog clauses
• In general, a question to the Prolog system is a list of goals separated by commas.
• A list of goals is true if all the goals in the list are true for the same instantiation of
variables.
• A comma between goals thus denotes the conjunction of goals: they all have to be
true.
• But Prolog also accepts the disjunction of goals: any one of the goals in the
disjunction has to be true.
• Disjunction is indicated by a semicolon.
For example,
P:- Q; R.
is read: P is true if Q is true or R is true.
1 May 2025 NGJD@FCT-UoK 30
 The meaning of this clause is thus the same as the meaning of the following two
clauses together:
P :- Q.
P :- R.
The comma binds stronger than the semicolon. So the clause
P:- Q, R; S, T, U.
is understood as
P :- ( Q , R ) ; ( S , T , U ).
and means the same as the clauses:
P :- Q,R.
P :- S,T,U.

1 May 2025 NGJD@FCT-UoK 31

2.7 Remark on the relation between Prolog and Logic
• Prolog is based on clausal form logic - a restricted versions of predicate logic (a
conjunctive normal form in which quantifiers are not explicitly written) and further
restricted to Horn clauses only (clauses that have at most one positive literal).
• A clause is an expression of the form
B1 ∧ B2 ∧ ⋯ ∧ Bn ⟶ A1 ∨ A2 ∨ ⋯ ∨ Am
where (i) n and m are non-negative integers,
(ii) ∧, ∨ and ‘⟶’ represent the logical connectives AND,OR and IMPLIES in
logic respectively,
(iii) A1, A2, … , Am, B1, B2, … , Bn are all compound terms.

1 May 2025 NGJD@FCT-UoK 32

• The notation introduced by Kowalski in 1974 for a clause like above is
A1, A2, … Am ⟵ B1, B2, … , Bn ,
which is written in Prolog as
A1, A2,…, Am :- B1, B2, … , Bn.
The disjunction of conclusions A1, A2, … , Am is called the head of the clause and
the conjunction of the conditions B1, B2, … , Bn is called the body of the clause.

1 May 2025 NGJD@FCT-UoK 33

• It is important to note the following special cases:
1. If 𝑛 = 0 and 𝑚 = 1, then the clause is called a fact, written as A1.
In this case the body is empty.
2. If 𝑛 > 0 and 𝑚 = 0, then the clause is said to be a query or question, written as
a conjunction of goals B1, B2, …, Bn.
In this case the head is empty.
3. If 𝑛 > 0 and 𝑚 = 1, then the clause is said to be a rule and written in Prolog as
A1 :- B1,B2,…,Bn.
4. If 𝑛 = 0 and 𝑚 = 0, the clause is said to be an empty clause and it is denoted
by [].
The empty clause is interpreted as a sentence which is inconsistent. (i.e. always
false).
5. If 𝑛 ≥ 0 and 𝑚 ≤ 1, then such a clause is called a horn clause (a clause that
have at most one conclusion).
1 May 2025 NGJD@FCT-UoK 34
• A Prolog program consists of a finite sequence of statements called horn clauses.

1 May 2025 NGJD@FCT-UoK 35

Summary
• Simple objects in Prolog are atoms, variables and numbers.
• Structured objects, or structures, are used to represent objects that have several
components.
• Structures are constructed by means of functors. Each functor is defined by its
name and arity.
• The type of object is recognized entirely by its syntactic form.
• The lexical scope of variables is one clause. Thus the same variable name in two
clauses means two different variables.
• Structures can be naturally pictured as trees. Prolog can be viewed as a language for
processing trees.
• The matching operation takes two terms and tries to make them identical by
instantiating the variables in both terms.
1 May 2025 NGJD@FCT-UoK 36
• Matching, if it succeeds, results in the most general instantiation of variables.
• A comma between goals means the conjunction of goals. A semicolon between
goals means the disjunction of goals.

1 May 2025 NGJD@FCT-UoK 37