Laurea in INFORMATICA Laurea in INFORMATICA MAGISTRALE MAGISTRALE

1

Prolog / 1 Prolog / 1

Logic Programming, Syntax Logic Programming, Syntax

Laurea in INFORMATICA Laurea in INFORMATICA

MAGISTRALE MAGISTRALE

Corso di

ARTIFICIAL INTELLIGENCE Stefano Ferilli

Questi lucidi sono stati preparati per uso didattico. Essi contengono materiale originale di proprietà dell'Università degli Studi di Bari e/o figure di proprietà di altri autori, società e organizzazioni di cui e' riportato il riferimento. Tutto o parte del materiale può essere fotocopiato per uso personale o didattico ma non può essere distribuito per uso commerciale. Qualunque altro uso richiede una specifica autorizzazione da parte dell'Università degli Studi di Bari e degli altri autori coinvolti.

Logic Programming

●

Born in the 70s

●

Kowalski

–

Theoretical foundations

●

Procedural vs Declarative interpretation of Horn clauses

–

Horn clause p :- q,r.

●

Declarative interpertations

●

p is true if q and r are

●

From q and r it follows p

●

Procedural interpretations

●

To solve problem p, solve in order subproblems q and r

●

To satisfy p, satisfy in order q and r

–

Allowed implementation on computers of logic programming languages

●

Colmerauer

–

First design and implementation for a logic language (Prolog)

Logic Programming

●

Spread of interest for this new kind of programming

●

From academic to industrial domains

●

Prolog

–

Chosen in 1981 by japanese as the language on which basing the V computer generation, characterized by high parallelism

–

Currently the logic programming language par excellence

●

Exploited in a wide range of application areas of AI and knowledge engineering

Logic Programming

●

Problems described declaratively

●

Sets of logic formulae

●

Procedural interpretation of clauses

●

Theorem proving methods as tools for executing programs

–

Logics = problem representation

–

Deduction = problem solving

●

Aristotle’s syllogism

–

A form of deductive reasoning

●

From a general judgment, reach a particular one

–

Major premise All men are mortals

–

Minor premise Socrates is a man

–

Middle term man ---

–

Conclusion Socrates is a mortal

Logic Programming

●

Classical programming (procedural)

●

More suitable for everyday problems, well-defined

●

Adopts an imperative paradigm

–

Strict sequences of steps (algorithms) must be specified that, given the available data, allow to reach the desired results

Logic Programming

●

Corresponding to Wirth’s famous equation for classic programming

●

Algorithms + Data structures = Programs

–

Data (what) and control (how) inextricably connected

●

Kowalski proposed the following equation

●

Algorithm = Logic + Control

–

Data (what) and control (how) clearly separated

●

Programmer in charge of specifying the logic component only

–Only define the problem, expressing its specifications –Not telling the machine how to solve it

●

System in exclusive charge of control

Logic Programming

●

Procedural languages

●

Programs specify the sequence of operations the computer must carry out to solve the problem

●

Assumptions on which the algorithm is based usually implicit (prescriptive style, how-type)

●

Logic programming

●

Programs describe the knowledge about the problem

–

Involved objects and relationships among them (descriptive style, what-type)

●

Control completely separated from problem description

–

=> any modification may only affect efficiency, not correctness of the results

Example

●

Taking an elevator

●

Procedural language

–

Wait for elevator to arrive at calling floor

–

Open elevator’s door

–

Enter elevator

–

Close elevator’s door

–

Press button corresponding to floor to reach

●

Execution order counts!

●

Declarative language

–

If elevator arrived and door open, then enter the elevator

–

If need to open elevator door, need to wait the elevator to arrive

–

If entered and open door, then close door

–

If entered and closed door, then press button corresponding to the floor to reach

●

Execution order irrelevant!

Logic Programming

●

Need to abandon the process-oriented way of thinking

●

Program is a description of solution, not of the process

●

Built by describing in a formal language the application area

–

Objects that exist in it

●

Concrete or abstract, existing or imaginary

–

Relationships among them and the facts about them

●

Qualities or attributes of a group of objects, linking them each other

Logic Programming

●

Underlying formal language: Horn clauses

●

h :- p1, ..., pn.

–

Knowledge base (program’s assumptions)

●

Facts h. (= h :- .)

●

Rules h :- p1, ..., pn.

●

Program execution by asking the system questions about the objects in the domain and their

relationships

–

Need for an inference procedure (deduction) for the machine to draw conclusions or answers not explicitly reported from a knowledge base

●

Consequence: possibility of incrementally developing the knowledge base

–

Relevant conclusions can be stored in the base for subsequent use

Prolog

●

PROgramming in LOGic

●

Result of research by Colmerauer and Kowalski

●

Logic Programming language

–

Very powerful and flexible

–

Particularly suited to AI and non-numerical programming

–

Most suitable for problems concerning (especially structured) objects and relationships among them

●

Programmer focuses on objects and relationships among them, expressing knowledge about them in the form of facts and rules, for later asking questions

–

Interpreter endowed with an inference mechanism that tries to answer questions by relating them to facts and rules in the knowledge base and trying to carry out deductions

Prolog

●

Fundamental components:

●

Declarations of facts, objects and their relationships

●

Declarations of rules on objects and their relationships

●

Questions about objects and their relationships

●

Used by programmers to interact with the language

●

Facts and Rules -> writing programs

–

Programming = describing the problem domain through facts and rules in the form of Horn clauses

●

Questions -> running programs

Syntax

●

Constant, function, predicate names

●

Start with lowercase letter

–

May contain lowercase/uppercase letters, numbers, _

●

Fancier names enclosed in ‘...’

●

Variable names

●

Start with uppercase letter or _

–

May contain lowercase/uppercase letters, numbers, _

●

_ always a “fresh” variable

●

Function and predicate arguments

●

In parentheses, separated by commas

–

Some Prolog implementations allow infix notation

Clauses

●

Clauses

●

General pattern h :- l_1, ..., l_n.

–

Rules (Definite clauses)

●

Both head and body

●

Should involve variables

–

Facts

●

Only head

–

No :- symbol

●

Should be ground

–

Goals

●

Only body

●

All end with a .

Syntax

●

Examples

●

Constants

–

Parent Carl NO!

–

parent carl OK!

●

Predicate/function names

–

part of son of married with NO!

–

part_of son_of married_with OK!

–

partOf sonOf marriedWith OK!

●

Clauses

–

parent(carlo,stefano). fact

–

son(X,Y) :- parent(X,Y), male(Y). rule

–

:- son(carlo,X). goal

Facts

●

Claims that are always true

●

Unconditional Horn clauses

–

Informally, a fact is a sentence concerning something or someone, which establishes a relationship among its arguments and that may be true or false

–

Prolog implicitly assumes all facts in a KB to be true

●

Thus, responsibility for truth of falseness of facts in the knowledge base is in charge of the programmer

–

Example. The KB

●

red(blood). red(snow).

–

Is valid, and Prolog will assume that both blood and snow fulfil the property expressed by predicate ‘red’

●

Express a (complete) claim

–

Not constrained by a previous check of conditions

●

p :- q,r. p is true provided that q and r are verified

●

p :- . p is true provided that... (no condition) -> simply

●

p.

Facts

●

A relationship is, in general, defined as the set of all its instances

●

A set of claims (facts) built on the same predicate

–

Predicate = name & arity

●

predicates <-> relational database tables

–

Facts -> n-tuples

–

parent(carlo, stefano).

–

parent(alfonso,marcella).

–

parent(anna, stefano).

–

parent(francesco, alfonso).

–

parent(lucia, alfonso).

–

parent(iginia, carlo).

–

parent(alfonso, carlo).

–

parent(iginia, marcella).

–

parent(pietro, francesco).

–

parent(giovanni, anna).

–

parent(immacolata, anna).

parent

carlo stefano

alfonso carlo

anna stefano

francesco alfonso

lucia alfonso

iginia carlo

alfonso marcella

iginia marcella

pietro francesco

giovanni anna

immacolata anna

Facts

●

Interpretation

●

Prolog treats all relationships as syntactic entities

–

Meaning given by the programmer

●

Name, order and role of the arguments

●

Programmer in charge of consistent use

–

Once defined, interpretation cannot be changed

●

Otherwise, meaningless answers

–

Example: parent(x,y). “x is a parent of y”

●

In all atoms built on parent/2, the former argument must be the parent, and the latter the child

●

Swapping them would lead Prolog to misunderstandings (and wrong answers)

●

E.g., parent(stefano,carlo)

“a parent of Stefano is Carlo” NO!

Rules

●

Claims that are true provided that their conditions are satisfied

●

Express general situations by using objects and relationships among them

●

Head = claim to be defined; Body = objectives to be satisfied, in sequence, to make the head true

–

If swapped, completely different meaning!

●

passes_test(X) :- studies(X). !!

●

studies(X) :- passes_test(X). ??

●

Avoid redundancy in the knowledge base

–

child(X,Y) :- parent(Y,X).

Rules

●

Recursion

●

Recursive rules: define a relation in terms of itself

●

Allow to obtain shorter and more general programs

●

Needed for solving complex problems or intrinsically recursive ones

●

Very easily used in Prolog

–

One of its foundational components

Rules

●

Example

●

Ancestors relationship

–

Recursive definition

●

ancestor(X,Y) :- parent(X,Y).

–

A parent is also an ancestor

●

ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

–

The parent of an ancestor is also an ancestor

–

Without recursion, we should have

●

ancestor(X,Y) :- parent(X,Y).

●

ancestor(X,Y) :- parent(X,Z), parent(Z,Y).

●

ancestor(X,Y) :- parent(X,W), parent(W,Z), parent(Z,Y).

●

...

–

Longer, and in any case incomplete!

●

We should go on forever adding more generations

Rules

●

Scope of variables local to the rules they belong to

●

Different rules for the same predicate may use the same variable

–

Consistency of roles must be ensured

●

Example

–

ancestor(A,B) :- parent(A,B).

–

ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

●

In both rules the former argument is the ancestor, and the latter the descendant

●

This is clear from the second rule

●

The same variable, used in different clauses, does not imply any relationship among them

●

Example

–

siblings(Y,X) :- parent(Z,Y), parent(Z,X).

different(Y,Z) –

siblings(X,Y) :- siblings(Y,X).

Examples

●

Use of variables

●

bad(X). everybody is bad (ATTENTION!)

●

lives(X,italy) :- resident(X,rome).

–

If someone resides in Rome, then he lives in Italy

●

needs_washing(X) :- dirty(X), black(X).

–

If something is dirty and black, then it needs washing.

●

needs_washing(X) :- dirty(X), black(_).

–

If something is dirty and there exists something black, then it needs washing.

●

interesting(world) :- nice(_), fun(_).

–

The world is interesting if there is something nice and something fun

●

Not necessarily the same thing!

Knowledge Base

●

A sequence of clauses

●

Possibly partitioned into modules (~namespaces)

–

module:clause

●

Can be updated (adding, removing, changing clauses/relationships) without changing the program that processes them

●

Saved in text file(s)

●

.pl extension

–

Older Prolog versions use .pro

●

To be loaded before use

●

consult/1

–

reconsult/1

●

[ ]

Datalog

●

Correspondence

●

Facts = tables

–

Extensional DB

–

Table = facts built on the same predicate

●

Predicate = table name

●

arguments = n-tuples

●

Rules = views

–

Intensional DB

●

Implements relational algebra operators

●

Selection

●

Projection

●

Join

●

Differences

●

Negation

●

Recursion

Datalog

●

Example

●

Selection

–

stefanos_parent(X,Y) :- parent(X,Y), Y = stefano.

●

stefanos_parent(X,Y) :- parent(X,stefano).

●

Projection

–

parent(X) :- parent(X,Z).

●

parent(X) :- parent(X,_).

●

Join

–

father_in_law(X,Y) :- father(X,Z), married(Z,Y).

–

father_in_law(X,Y) :- father(X,Z), married(Y,Z).

Questions

●

1. load a knowledge base into memory

●

2. query it (execute the program)

●

Query environment

–

?- prompt

●

Says that Prolog is ready to answer questions concerning the currently loaded knowledge base

●

Questions = goals (to prove) or queries (to answer)

–

Variables denote unknown (unbound) objects

●

The system should possibly bind them

●

Answers

–

No/False

–

Yes/True

–

Computed Answer Substitution

●

Variable assignments that make the question true

Questions

●

Examples

–

Single

●

?- parent(carlo,stefano).

–

Yes

●

?- parent(giovanni,carlo).

–

No

–

Multiple

●

?- parent(carlo,stefano), parent(alfonso,carlo).

–

Yes

●

?- parent(carlo,stefano), parent(giovanni,carlo).

–

No

–

Order does not matter

●

?- parent(carlo,stefano), parent(alfonso,carlo).

–

Yes

●

?- parent(carlo,stefano), parent(giovanni,carlo).

–

No

Questions

●

Variables

●

Used to know for which values the query is true

●

If many values are possible

–

Prolog returns the first one and asks if we want to know more

–

When no more are available it answers ‘No’

●

Represent values not known in advance

–

Unbound variables

●

Will be determined by the system

–

Looks for solutions by searching the knowledge base

●

If found, bound to variable

–

Instantiated variable

Questions

●

Examples

●

Single

–

?- parent(X,francesco).

●

X = pietro

–

?- parent(anna,Child).

●

Child = stefano

–

?- parent(Parent,giovanni).

●

No

●

Multiple

–

?- parent(X,marcella).

●

X = alfonso More? y

●

X = iginia More? y

●

No

Questions

●

Answering strategy

●

Question = one or many goals to be satisfied

–

Satisfy a goal = Proving it is true

●

Logically follows from the knowledge base / program

–

If the question involves variables, Prolog tries to find all

specific objects that, replaced to variables, allow to satisfy the goal

●

If it cannot satisfy all goals in the query, it answers ‘No’

–

Example

●

?- parent(immacolata, anna), parent(lucia, alfonso), ancestor(giovanni, stefano).

●

Yes.

●

?- parent(lucia, anna), parent(stefano, mario), ancestor(giovanni, carlo).

●

No.

●

?- parent(giovanni, anna), parent(marcella, alfonso), ancestor(giovanni, stefano).

●

No.

Prolog

●

Mathematical interpretation of programs

●

Prolog takes facts and rules as a set of axioms, and the question as a theorem to be proven

●

And it must prove that the theorem can be logically derived from the axioms

Prolog

●

Control strategy

●

SLD resolution

–

Selection rule driven Linear resolution for Definite clauses

●

If the goal to prove is made up of many goals

●

Prolog tries to satisfy them left-to-right

–

Consider the next as soon as one is proved

–

When one cannot be proven, backtracks to the last choice point

–

If all are satisfied, it answer ‘Yes’ or a computed answer substitution

●

Using the available clauses, each goal is replaced by new goals until all become simple facts

–

If there are alternate paths (many clauses defining the same relationship), Prolog chooses them top-down

●

Based on their specification in the knowledge base

–

If a failure is obtained (no more clauses having the same

head as the goal to be proven) the goal fails and Prolog goes back to the most recent choice point (backtracking) to look for an alternate path

ancestor(X, Y) :- parent(X, Y).

ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

:- parent(pietro, Z), ancestor(Z, stefano). parent(pietro, francesco).

:- ancestor(francesco, stefano). ancestor(X, Y) :- parent(X, Y).

ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

:- parent(francesco, Z), ancestor(Z, stefano). parent(francesco, alfonso).

:- ancestor(alfonso, stefano). ancestor(X, Y) :- parent(X, Y).

ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

:- parent(alfonso, Z), ancestor(Z, stefano). parent(alfonso, marcella).

:- ancestor(marcella, stefano). ancestor(X, Y) :- parent(X, Y).

ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

parent(alfonso, carlo).

:- ancestor(carlo, stefano). ancestor(X, Y) :- parent(X, Y).

:- parent(carlo, stefano).

parent(carlo, stefano).

Yes.

Prolog

●

Obtaining many answers to a goal

●

Prolog forces backtracking on the situation on which it returned the last answer

–

Example: ?- ancestor(pietro,stefano).

●

(expected answer: Yes)

Lists

●

Only data structure available in Prolog

●

Non-typed data -> may simulate all other structures

–

[] empty list

–

E & L recursion (L list) a & [b,c,d] = [a,b,c,d]

●

Formalism

●

Delimiters [ ]

●

Separator ,

●

Pattern

●

[Head|Tail]

–

Head = single item(s)

–

Tail = list of remaining items

Examples

●

[a,b,c] = [H|T] -> H = a, T = [b,c]

●

[b,c] = [H|T] -> H = b, T = [c]

●

[c] = [H|T] -> H = c, T = []

●

[] = [H|T] -> false

●

●

[a, 2, X, p(a,Y), [3.2, Z, b], a]

●

book(ferilli, “document processing”, 2011, 109.50)

●

[ferilli, “document processing”, 2011, 109.50]

Collecting Answers in Lists

●

setof/3

●

No duplicates

●

Fails if empty set!

●

Binds variables at first unification!

–

Example

●

?- setof(X, parent(X,marcella), Z).

●

Z = [alfonso,marcella]

●

bagof/3, findall/3

●

Duplicates

Writing Knowledge Bases

●

Plain text file

●

.pl (or .pro) extension

●

Clauses

●

Grouped by predicate

–

May raise warnings otherwise

●

Indentation!

●

Comments

●

% line comment

●

/* ... */ multiple line comment

Interpreter

●

As most AI languages, Prolog is interpreted

●

Starting interpreter from operating system

–

sicstus

–

(yap)

–

swipl

●

Prompt

–

?-

●

Ready to take commands = queries to the knowledge base

●

Terminating interpreter

–

halt/0

Running Programs

●

Load knowledge base

●

consult(filename).

–

If in working directory, filename without extension sufficient

–

If in other directory

●

(Absolute or relative) path + filename in ‘...’

●

Run procedure = Ask query

●

Atom built on any predicate defined in the knowledge base

●

Outcome

●

no/false

●

yes/true

–

or Computed Answer Substitution

Debug

●

Setting breakpoint

●

spy/1

–

Argument: predicate

–

Cannot set on specific execution

●

Enabling

●

trace/0

●

Disabling

●

notrace/0

●

Control

●

(s)kip

–

On call

●

(r)edo

–

On exit / fail

●

(l)eap

–

To next spied predicate

●

(a)bort

●

(h)elp

Control Predicates

●

true/0

●

Always true

●

fail/0

●

Always false

●

!/0 “cut”

●

always true

●

“freezes” partial computed answer substitution

●

call/1

●

call(X) or simply X

Comparisons

●

Unification

●

=

●

Exact equality

●

==

–

Including variables

●

Non-unification

●

\=

●

Inequality

●

\==

●

<

●

>

●

=<

●

>=

Negation as Failure

●

Definition

●

not(Goal) :- call(Goal),

!, fail.

●

not(_).

●

Predefined predicate

●

\+

Collecting Outcomes

●

Arguments:

Items to be collected, Goal, Collection

●

setof/3

–

Removes duplicates

–

Fails if empty set

–

Locks variables

●

Existential quantification ^

●

bagof/3

–

Similar to setof/3, preserves duplicates and order

●

findall/3

–

Similar to bagof/3, does not lock variables

Suggested Readings

●

Clocksin W.F., Mellish C. “Programming in

Prolog – Using the ISO Standard” 5 ^th Ed.,

Springer, 2013