ICS 2405 Knowledge Based Systems

LESSON 5
Logic programming and prolog

Contents

• Basic introduction to logic

• programming Structure of a Prolog program

• Basic Prolog programming

• Data objects and structures

• Summary

5.1. Introduction
• Logic programming refers to a family of languages and an associated pro-
gramming style based on writing programs as a set of assertions (facts and
inference rules).

• The execution of a logic program is a kind of deduction on the specified facts

and inference rules.

• Prolog is such a logic programming language.

5.2. Prolog
•.6. Prolog is the most widely used language to have been inspired by logic pro-
gramming research. Some features:

•.7. Prolog uses logical variables. These are not the same as variables in other lan-
guages. Programmers can use them as ‘holes’ in data structures that are gradually
filled in as computation proceeds.

•.8. Unification is a built-in term-manipulation method that passes parameters, re-

turns results, selects and constructs data structures.

•.9. Basic control flow model is backtracking.

38
ICS 2405 Knowledge Based Systems

•.10. Program clauses and data have the same form.

•.11. The relational form of procedures makes it possible to define ‘reversible’ pro-
cedures.

•.12. Clauses provide a convenient way to express case analysis and nondetermin-
ism.

•.13. Sometimes it is necessary to use control features that are not part of ‘logic’.

•.14. A Prolog program can also be seen as a relational database containing rules
as well as facts.

5.2.1. Prolog as a ‘declarative’ language

•.15. Clauses are statements about what is true about a problem, instead of instruc-
tions how to accomplish the solution.

•.16. The Prolog system uses the clauses to work out how to accomplish the solu-
tion by searching through the space of possible solutions.

•.17. Not all problems have pure declarative specifications. Sometimes extralogical
statements are needed.

•.18. Example: Concatenate lists a and b

39
ICS 2405 Knowledge Based Systems

5.2.2. Structure of a Prolog program

• Programs consist of procedures.

• Procedures consist of clauses.

• Each clause is a fact or a rule.

– facts for describing object features or relationships, and

– rules for inferring new properties and relationships from other properties
and relationships.

• Programs are executed by posing queries.

•.19. example

• A Fact
• A fact has the format:

– predicatename(arguments)

* Where arguments-ANY TERM

* (CONSTANT,VARIABLE,FUNCTION EXPRESSION)

• For instance:

40
ICS 2405 Knowledge Based Systems

– female(monica).

* expresses the fact that monica is a female

– parent(monica, bob).

* expresses the fact that monica is a parent of bob

• A Rule
• A rule has the following form:
• X :- Y1, Y2, ... ,Yn.

– (Simply HEAD:-BODY. Read as HEAD if BODY)

– which may be read as "X is true if Y1 is true and Y2 is true and ... and
Yn is true"
– X represents the head of the rule and Y1, Y2, ... ,Yn represents the body.

• ":-" is read "if“

• The BODY may be a CONJUNCTION or a DISJUNCTION of

predicates

• For instance:
• mother(X, Y) :- parent(X, Y), female(X).

• means X is mother of Y if X is parent of Y and X is a female.

5.2.3. Querying a Prolog Database

•.4. Once a prolog program is written, the user may ask different questions.

•.5. A question to Prolog is always a sequence of one or more predicates (called

goals) as, for instance:

• ?- parent(X, rachael).

– % Who is Rachael’s parent ?

41
ICS 2405 Knowledge Based Systems

• ?- predecessor(monica, X).

– % Who are Monica’s successors ?

Example 3

42
ICS 2405 Knowledge Based Systems

5.2.4. Prolog Program-Continued

5.2.5. How Prolog answers questions

•.6. If the question consists of a predicate with no variables like, for instance

•.7. ?- parent(bob, pat).% Is Bob a parent of Pat ?

• Prolog tries to demonstrate that this fact logically follows from the facts and
the rules in the program.

– It returns Yes if the proof is successful and

– No otherwise.

43
ICS 2405 Knowledge Based Systems

•.8. Prolog uses the closed world assumption which states that all relevant, true
assertions are explicitly represented or are derivable from those explicitly repre-
sented.

• Based on CWA, any assertion that is neither explicitly represented nor deriv-
able, is considered to be false.

•.9. If the question consists of one or more predicates with variables such as:

• ?- parent(Y, kenny), parent(X, Y).

– % Find X and Y such that Y is a parent of Kenny

– % and X is a grandparent of Kenny

•.10. Prolog will look for all the instances of the variables from the question (X and
Y in the above example) such that the predicates in the question logically follow
from the facts and the rules in the program.

•.11. One says that Prolog tries to satisfy the goals "parent(Y, kenny)" and "par-
ent(X, Y)".

•.12. Prolog returns the found pairs of the values of X and Y, or No if no such pair
is found.

• ?- parent(Y, kenny), parent(X, Y).

• X = bob

• Y = pat

•.13. In all the queries the goals are satisfied by matching the questions with the
facts.

•.14. If a goal cannot be satisfied in such a way, Prolog will try to use the rules
from the program

•.15. Prolog backtracks and tries any applicable rules if one goal fails

44
ICS 2405 Knowledge Based Systems

5.3. Unification
• Two terms unify if substitutions can be made for any variables in the terms
so that the terms are made identical. If no such substitution exists, the terms
do not unify.

• The Unification Algorithm proceeds by recursive descent of the two terms.

– Constants unify if they are identical

– Variables unify with any term, including other variables
– Compound terms unify if their functors and components unify.

5.3.1. Order of Clauses

When writing Prolog programs one should use the following problem solving heuris-
tic:

• try the simplest idea first.

5.3.2. Data objects

• Syntactically, all data objects in Prolog are terms.

• As known from logic, a term could be a constant, a variable, or a function the

arguments of which are terms.

Complete Syntax of Terms

45
ICS 2405 Knowledge Based Systems

5.3.3. Variables
• Variables are strings of letters, digits and underscore characters.

– They start with an upper-case letter or an underscore character.

– e.g. haschild(X) :- parent(X, Y). % X has a child if %there is Y such
that X is the parent of Y

• Each time a single underscore character occurs in a clause it represents a new

anonymous variable.

– haschild(X) :- parent(X, _). % X has a child if % X is the parent of

someone

• If the anonymous variable appears in a question clause then its value is not
output when Prolog answers the question:

• ?- parent(X, _). % Who is a parent ? Or

– X = monica; % Find X such that X is a %parent of someone.

– X = tom;
– X = bob;
– X = pat

• The lexical scope of variable names is one clause.

5.3.4. Compound Terms

•.16. Some atoms have built-in operator declarations so they may be written in a
syntactically convenient form. The meaning is not affected. This example looks
like an arithmetic expression, but might not be. It is just a term.

•.17. Constants are simply compound terms of arity 0.

•.18. owino means the same as owino()

46
ICS 2405 Knowledge Based Systems

5.3.5. Structures
•.19. Structured objects (structures) are objects that have several components.

• The components themselves can, in turn, be structures.

•.20. A structured object corresponds to a function (or functional term) in logic.

• E.g.: date(december, 3, 1983)

•.21. All structured objects in Prolog are trees, represented in the program by terms.

•.22. It should be noted that the functions of Prolog are seen as compound data
structures similar to the records of Pascal: they can be constructed and analyzed.

• They are not functions applied to arguments to denote the corresponding re-
sult.

5.3.6. Lists
•.23. A list is a data structure that is either empty or consists of two parts: a head
and a tail. The tail itself has to be a list.

•.24. The empty list is represented as [].

•.25. A list with Head and Tail is represented as .( Head, Tail)

•.26. Lists are handled in Prolog as a special case of binary trees.

•.27. For improved readability Prolog provides a special notation for lists:

• [ Item1, Item2, ...] or

• [ Head | Tail] or

• [ Item1, Item2, ... | Others]

47
ICS 2405 Knowledge Based Systems

5.3.7. Some operations on lists-Membership

• We define the relation member( X, L), where X is an object and L is a list.

• X is a member of L if either

• X is the head of L, or X is a member of the tail of L.

– member( X, [X | Tail] ).
– member( X, [Head | Tail] ) :-member( X, Tail).

5.3.8. Concatenation
•.28. We define the relation conc( L1, L2, L3) where L1 and L2 are two lists and
L3 is their concatenation.

• conc corresponds to append in LISP.

•.29. conc( [], L, L). % the concatenation of an empty list [] %with a list L is L

•.30. conc([X | L1], L2, [X | L3] ) :- % a non-empty list has the form [X | L1]

•.31. conc( L1, L2, L3). % the concatenation of [X | L1] with a list L2 is % the list
[X | L3],where L3 is the concatenation of L1 and L2

•.32. This program can be used for concatenating given lists:

• ?- conc([a,b,c], [1,2,3], L).

• L = [a,b,c,1,2,3]

•.33. conc could also be used in the inverse direction for decomposing a given list
into two lists:

• ?- conc(U, V, [a,b,c]).

– U = []
– V = [a,b,c];
– U = [a]

48
ICS 2405 Knowledge Based Systems

– V = [b,c];
– U = [a,b]
– V = [c];
– U = [a,b,c]
– V = [];
– no

Add
Adding an item X to the beginning of a list L can be programmed as a relation

• add( X, L, [X | L] ). % X is added %in the front of the list

Delete
• Deleting an item X from a list L can be programmed as a relation

– del ( X, L, L1) where L1 is equal to the list L with the item X removed.
– del( X, [X | Tail], Tail). % if X is the head of the %list then the result of
deletion of X % is the tail of the list.
– del( X, [Y | Tail], [Y | Tail1]) :- % if X is in the tail, then it %should be
deleted from there. del( X, Tail, Tail1)

Sublist
sublist( S, L) :- % S is a sublist of L if conc( L1, L2, L), % L is composed of two
lists, L1 and L2, and conc( S, L3, L2). % L2 is composed of S and some L3.

5.3.9. Operators
Any atom may be designated an operator. The only purpose is for convenience; the
only effect is how the term containing the atom is parsed. Operators are ‘syntactic
sugar’. Operators have three properties: position, precedence and associativity.
Examples of operator properties

49
ICS 2405 Knowledge Based Systems

Revision questions

Example . give an example of a prolog Programs consisting of procedures,clauses.

facts,rules and queries.

Solution:


E XERCISE 8.  ....

50