Prolog EN -- Laboratory 1 -- 2006-2007 -- info.uvt.ro

• Prolog EN -- 2006-2007 -- info.uvt.ro
  • Prolog EN -- Laboratory 1 -- 2006-2007 -- info.uvt.ro
  • Prolog EN -- Laboratory 2 -- 2006-2007 -- info.uvt.ro
  • Prolog EN -- Laboratory 3 -- 2006-2007 -- info.uvt.ro
  • Prolog EN -- Laboratory 4 -- 2006-2007 -- info.uvt.ro
  • Prolog EN -- Test -- 2006-2007 -- info.uvt.ro

Introduction

• Prolog -- Wikipedia article
• Prolog -- the name of the language -- comes from Programing in logic.

Usage

• symbolic computation
• Artificial intelligence
• Computational linguistics

Concepts

• Horn clauses
• Unification

Syntax

Atoms

• Strings of letters, digits and underscore starting with a lower case-letter. Examples:

john_smith
nil
x25

• Strings of special characters. Examples:

<
<-->
::=

• Strings enclosed in single quotes. Examples:

'John Smith'
'X25'

Numbers

Examples:

78
73.2
-54
-39.7

Variables

Strings of letters, digits and underscore starting with an upper-case letter or an underscore.

Examples:

X
List
_x25
_

Structures

Syntax:

<functor>(<argument-1>, <argument-2>, ..., <argument-n>)

A functor is any atom and represents the name of the structure. The functor has an arity -- the number of arguments.

An argument is any atom, number, or other structure.

Examples:

date(1, may, 2007)
person('John', 'Smith', date(23, october, 1976))

point(1, 1)
segment(point(1, 1), point(1, 3))
triangle(point(1, 1), point(1, 3), point(2, 3))

+(1, *(2, 3))

.(a, .(b, .(c, [])))

Lists

A list is nothing else than a composed structure.

Syntax:

.(<element-1>, .(<element-2>, ... .(<element-n>, []) ... ))

or

[<element-1>, <element-2>, ..., <element-n>]

Examples:

[]
[1, 2, 3]
[a, b, c, d]
[1, b, 3, d]
[[1, 2], [3, 4], d]

Facts

Syntax:

<relation>(<argument-1>, <argument-2>, ..., <argument-n>).

A relation is an atom and represents the name of the relation. Each relation has an arity -- the number of arguments.

An argument is any atom, number, or structure.

Example:

on(switch).
working(switch).
working(bulb).

We can observe that relations have the same syntax as structures.

We read each fact as:

• the switch is on.
• the switch is working.
• the bulb is working.

We also can observe that facts can be seen as predicates that state something about their subjects (the arguments).

Rules

Syntax:

<rule>(<argument-1>, <argument-2>, ..., <argument-n>) :-
    <clause-1>,
    <clause-2>,
    ...
    <clause-n>.

Where clause can be a fact or another rule.

The comma , stands for and.

Example:

on(light) :- working(switch), working(bulb), on(switch).
off(light) :- off(switch).

We read the rules above as:

• The light is on if the switch is working, and the bulb is working, and the switch is on.
• The light is off if the switch is off.

We can observe that:

• Like in the case of facts, rules can be seen as statements (predicates) about some subjects (the arguments).
• We can have both facts and rules with the same name and the same arity.

First example -- Genealogical Tree

Creating and loading the fact file

Create a fact file (ex-1.prolog):

parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

Start GNU prolog:

gprolog

Load the facts file:

consult('ex-1.prolog'). 

Querying the facts

The most simple query:

parent(tom, liz). %=> yes
parent(tom, ann). %=> no

Queries using variables:

parent(tom, C). %=> C = liz
parent(bob, C). %=> C = ann; C = pat
parent(P, C). %=> P = tom, C = liz; P = bob, C = ann; ...
parent(_, C). %=> C = liz; C = ann; C = pat; C = jim
parent(P, _). %=> P = tom; P = bob; P = bob; P = pat
parent(_, _). %=> true; true; true; true

Joined queries:

parent(tom, C), parent(C, GC). %=> no
parent(bob, C), parent(C, GC). %=> C=pat, GC=jim

Unification

• Unification -- Wikipedia article
• Unification is the process in which a variables are instantiated to a values, by trying to make two expressions equivalent.
• The operator that forces unification is =

Example:

X = a. %=> X = a
X = Y. %=> Y = X
a = b. %=> no

X = human(john). %=> X = human(john)
human(Name) = human(john). %=> Name = john
Human = human(Name), Name = john. %=> Human = human(john), Name = john.

Resolution

• Resolution -- Wikipedia article
• Resolution is the process in which a goal (a query) is being satisfied by searching facts, applying rules and unification.
• After each successful resolution, for each solution found, we will get all the variable instances.

Example:

parent(P, C). %=> P = tom, C = liz; P = bob, C = ann; ...

Second example -- Genealogical tree with queries

Adding rules to the fact file

We add some more facts at the end of the fact file:

male(tom).
male(bob).
male(jim).
female(liz).
female(pat).
female(ann).

And we add the following rules at the end of the fact file (after all the facts):

child(C, P) :- parent(P, C).

father(P, C) :- parent(P, C), male(P).
mother(P, C) :- parent(P, C), female(P).

son(C, P) :- child(C, P), male(C).
daughter(C, P) :- child(C, P), female(C).

brother(A, B) :- son(A, P), son(B, P).
sister(A, B) :- daughter(A, P), daughter(B, P).

grandparent(G, C) :- child(P, G), child(C, P).

ancestor(A, C) :- parent(A, C).
ancestor(A, C) :- parent(A, P), ancestor(P, C).

Querying the rules

father(P, C). %=> P = tom, C = liz; P = bob, C = ann; P = bob, C = ann
grandparent(G, C). %=> G = bob, C = jim
sister(A, B). %=> A = liz, B = liz; A = ann, B = ann; A = ann, B = pat; A = pat, B = ann; A = pat, B = pat
ancestor(bob, C). %=> C = ann; C = pat; C = jim

ccraciun@info.uvt.ro