Introduction

History

First described by A. Colmerauer of Uni. d'Aix-Marseille in 1972, developed by R. Kowalski (Uni. Edinburgh) from 1974.
There is a core pure Prolog (see Lloyd), which has been extended in many ways. ISO Prolog is a standard extension.
Much development at Uni of Melbourne by Lee Naish and John Lloyd.
Various "black boxes" that implement large portions of Prolog code have been developed (formalised by Jaffar at Monash). Arithmetic is an example of this.

Relationship to other languages

A non-sequential programming language
Declarative - program defines what the problem is, rather than how to solve it.
Symbolic
Based on 1st order logic

The simplicity of Prolog relative to other languages

Very little syntax
Theoretically no data types, but integers are separate.
Very clear semantics - defined mathematically
Why use Prolog
Declarative nature allows programmer to concentrate on the nature of the problem, rather than the method of solution.
Some pragmatics are required however to produce problem solutions!!

The principles of running Prolog

Eclipse Prolog

Fast, no friendly user interface
Available from ECLiPSe

Create a configuration file .eclipserc in your home directory, containing the following ...

%----Silently fail on undefined predicates (like an ATP system)
:-set_event_handler(68,fail/0).
%----Load some useful libraries
:-use_module(library(iso)).
:-use_module(library(numbervars)).  
%----Undefine "not" so it can be used as a user predicate
:-op(0,fy,not).  
%----Use occur check
:-set_flag(occur_check,on).

SWI Prolog

Slower, friendly user interface
Available from SWI

Create a configuration file .plrc in your Prolog working directory or your home directory, containing the following ...

%----Silently fail on undefined predicates (like an ATP system)
:- set_prolog_flag(unknown,fail).
%----Use unification with occurs check
:- set_prolog_flag(occurs_check,true).
%----Use the lists library
:- use_module(library(lists)).

Loading the program (compile/consult)
Interactive queries

The Core of the Language

Terms

In Prolog all data objects are called terms

Atomic terms

Come in two forms, atoms and integers.
Atoms (this is a misnomer as in logic predicates are called atoms and atoms are called constants. However, we'll stick to the Prolog convention.)
- Strings of alphanumerics and _, starting with a lower case alphabetic.
- Strings enclosed in 'single quotes'
Integers are numeric

Example

geoff
'the cat and the rat'
'ABCD'
123

Function terms

Functions have the form <functor>(<term>{,<term>})
Functor starts with a lower case alphabetic.

Example

prerequisite_to(adv_ai)
grade_attained_in(prerequisite_to(adv_ai),pass)

The number of arguments is the arity of the function. When referring to a functor, it is written with its arity in the format <functor>/<arity>. This is also true for atoms, whose arity is 0.
Note that this is a recursive definition.
The view of functions as trees
Operators
- Some functors are used in infix notation, e.g. 5+4
- Operators do not cause the associated function to be carried out.

Variables

Uppercase or _ for start of variables
Example
```
Who
What
_special
_
     
```
Variables in Prolog are rather different to those in most other languages. Further discussion and use is deferred until later.

Predicates

A predicate (called an atom in logic) has the form <predicate symbol>(<term>{,<term>}).

The predicate symbol starts with a lower case alphabetic
A degenerate form of predicate is a proposition, which has no arguments, i.e., <predicate symbol>.
The number of arguments is the arity of the predicate. When referring to a predicate, it is written with its arity in the format <predicate symbol>/<arity>. This is also true for propositions, whose arity is 0.

Example of propositional predicates

geoff_is_a_lecturer
can_study_adv_ai

Example of predicates

lecturer(geoff,adv_ai)
lecturer(olivier,prerequisite_to(adv_ai))
has_studied(Everyone,cp1200)

Prolog programs

Programs are made up of Horn clauses, which in turn are made up of predicates. The closest imperative structure is a 'Boolean function'.

Example: Binary tree program

%------------------------------------------------------------------------------
make_tree(Tree):-
    read(Word),
    insert(Word,Tree).    %----Note recursion for looping
%------------------------------------------------------------------------------
insert(exit,_).

insert(Word,Tree):-
    insert_word(Word,Tree),
    make_tree(Tree).
%------------------------------------------------------------------------------
insert_word(Word,node(Word,_,_)).

insert_word(Word,node(NodeWord,Smaller,_)):-
    ordered(Word,NodeWord),
    insert_word(Word,Smaller).

insert_word(Word,node(NodeWord,_,Larger)):-
    ordered(NodeWord,Word),
    insert_word(Word,Larger).
%------------------------------------------------------------------------------
ordered(Big,Small):-
    Big @> Small.
%------------------------------------------------------------------------------

The heading of a clause is a single predicate (also known as the consequent).
The body of a clause is a sequence of 0 or more predicates, separated by commas (also known as the antecedent). These are 'calls', called queries in Prolog, to other clauses.
If there are predicate(s) in the body, the body is separated from the head with :-.
Clauses with 0 body predicates are facts and those with 1 or more body predicates are rules
Facts may be considered to be rules with the predicate true as the tail.
Whenever a clause is used, new copies of its variables are created (so they are local), typically by adding a numeric suffix.

Propositional facts

<proposition>.
Always end with . in a program.
Lower case alphabetic for first letter of predicate symbols.
Example
```
geoff_is_a_lecturer.
     
```

Facts with no variable arguments.

<predicate symbol>(<arguments>).
Always end with . in a program.

Example

lecturer(geoff,adv_ai).
lecturer(olivier,prerequisite_to(adv_ai)).

Propositional rules

Always end with . in a program.
Head seperated from body by :- (if)
Body predicates are separated by , (and)

Example

can_study_adv_ai:-
    has_studied_ai.

can_study_adv_ai:-
    hod_says_so.

will_study_adv_ai:-
    can_study_adv_ai,
    enrolled_in_adv_ai.

Rules with no variables

As for propositional rules, but with arguments

Example

can_study(geoff,adv_ai):-
    has_studied(geoff,prerequisite_to(adv_ai)).

can_study(geoff,adv_ai):-
    hod_permission_to_study(geoff,adv_ai).

will_study(geoff,adv_ai):-
    can_study(geoff,adv_ai),
    enrolled(geoff,adv_ai).

Queries

Queries, in the form of a clause body, are entered at the ?- prompt, and end with a .

A single query succeeds if there is a clause whos head unifies with the query, and which succeeds. In the absence of variables "unifies" simply means that they must match exactly. This concept will be generalised when variables are introduced.
A conjunctive query succeeds if each element succeeds (an empty conjunction succeeds immediately). The members of a conjunctive query are evaluated sequentially, and evaluation is stopped as soon as a failed member is encountered.
A clause succeeds if its body succeeds. Note that bodies are the same as conjunctive queries.
Queries will eventually succeed or fail and the interpreter will print yes or no appropriately.
If no head unifies with a query, then the query fails.

Example : Queries on propositional facts.

geoff_is_a_lecturer.

----------------------------------------------------
?- geoff_is_a_lecturer.
yes

?- alan_is_a_lecturer.
no

Example : Query on propositional rules

has_studied_ai.

has_brains_to_pass_adv_ai.

enrolled_in_adv_ai.

can_study_adv_ai:-
    has_studied_ai.

will_study_adv_ai:-
    can_study_adv_ai,
    enrolled_in_adv_ai.

--------------------------------------------------------
?- will_study_adv_ai.
yes

Example : Conjunctive queries

has_studied_ai.

has_brains_to_pass_adv_ai.

enrolled_in_adv_ai.

can_study_adv_ai:-
    has_studied_ai.

will_study_adv_ai:-
    can_study_adv_ai,
    enrolled_in_adv_ai.

--------------------------------------------------------
?- will_study_adv_ai,has_brains_to_pass_adv_ai.
yes

Example : Conjunctive queries

has_studied_ai.

has_brains_to_pass_adv_ai.

can_study_adv_ai:-
    has_studied_ai.

will_study_adv_ai:-
    can_study_adv_ai,
    enrolled_in_adv_ai.

--------------------------------------------------------
?- will_study_adv_ai,has_brains_to_pass_adv_ai.
no

Example : Query on rules with no variables

has_studied(geoff,prerequisite_to(adv_ai)).

can_study(geoff,adv_ai):-
    has_studied(geoff,prerequisite_to( adv_ai)).

--------------------------------------------------------
?- can_study(geoff,adv_ai).
yes

Backtracking

There may be more than one version of a clause. The first version (in source code order) is used when the clause is queried. If the first version fails, then the second is tried, and so on. The query fails if none of the versions succeed. This may lead to alternatives further back being tried, and so on. This process is called backtracking.

Example : Query with backtracking on failure

hod_says_so.

can_study_adv_ai:-
    has_studied_ai.

can_study_adv_ai:-
    hod_says_so.

--------------------------------------------------------
?- can_study_adv_ai.
yes

As well as finding a solution, backtracking can also find alternative solutions. After a solution is given, the user can ask for alternatives to be found. The next alternative of the last call that succeeded, is used. If it does not have any alternatives, then calls further back are tried successively. A ; is used to get alternative answers.

Example - Query with alternatives

has_studied_ai.

has_studied_ai.

hod_says_so.

enrolled_in_adv_ai.

has_brains_to_pass_adv_ai.

can_study_adv_ai:-
    has_studied_ai.
can_study_adv_ai:-
    hod_says_so.

will_study_adv_ai:-
    can_study_adv_ai,
    enrolled_in_adv_ai.

--------------------------------------------------------
?- will_study_adv_ai, has_brains_to_pass_adv_ai.
yes ? ;
yes ? ;
yes

Variables

The only way to introduce variables is in a formal or actual argument list. Variables are local to their clause, and each time a clause is used a new set of variables are allocated. The new variables are typically appended with a unique number to make them distinct and local. Clauses with variables

Variables in clauses are universally quantified

Example

has_studied(Everyone,cp1200).

can_study(Anyone,Anything):-
    has_studied(Anyone,prerequisite_to(Anything)).

can_study(Anyone,Anything):-
    hod_permission_to_study(Anyone,Anything).

Variables can be in one of two states - bound (have value) or unbound (no value). Variables are initially unbound. Bound variables cannot have their values reset. However bound variables can become unbound. The binding of variables occurs in a proccess called unification. Two values/variables unify iff

They are identical, or
They are both "functions" with the same functor, and their arguments pairwise unify, or
One is a variable, in which case the the other value/variable is bound to the first. When two variables unify and one is bound to the other, the result is similar to the passing of reference parameters, and any change made to one is made to the other. The variables are said to share.

When a clause is queried, the actual and formal arguments must pairwise unify.

Query with unification

Example

lecturer(geoff,ai).

-------------------------------------------------------
?- lecturer(geoff,ai).
yes

?- lecturer(prof,ai).
no

?- lecturer(geoff,networks).
no

As well as answering yes or no, the bindings of any variables in the original query are printed by the interpreter.

Variables in queries are existentially quantified.

Example

lecturer(geoff,ai).

--------------------------------------------------------
?- lecturer(geoff,What).
yes
What = ai

?- lecturer(Who,ai).
yes
Who = geoff

?- lecturer(Who,What).
yes
Who = geoff
What = ai

?- lecturer(Same,Same).
no

Example

has_studied(Everyone,programming).

-----------------------------------------------------
?- has_studied(geoff, programming).
yes

?- has_studied(geoff,Anything).
yes
Anything = programming

?- has_studied(Anyone, programming).
yes
Anyone = Everyone_1234

Example

will_study(Student,Course):-
    can_study(Student,Course),
    has_enrolled(Student,Course).

can_study(Anyone,Anything):-
    hod_permission_to_study(Anyone,Anything).

hod_permission_to_study(jane,adv_ai).

has_enrolled(jane,adv_ai).

-----------------------------------------------------
?- can_study(jane,Something).
yes
Something = adv_ai

?- will_study(Anyone,Anything).
yes
Anyone = jane
Anything = adv_ai

When another version of a clause is used in backtracking, any variable bindings done in the use of the previous version are undone.

Query with variables and backtracking on failure

Example

lecturer(olivier,ai).
lecturer(geoff,ai).

rides_motorcycle(geoff).

-----------------------------------------------------------
?- lecturer(Anyone,ai),rides_motorcycle(Anyone).
yes
Anyone = geoff

Example

has_studied(joe,prerequisite_to(adv_ai)).

hod_permission_to_study(jane,adv_ai).

can_study(Student,Course):-
    has_studied(Student,prerequisite_to(Course)).

can_study(Student,Course):-
    hod_permission_to_study(Student,Course).

--------------------------------------------------------
?- can_study(jane,Anything).
yes
Anything = adv_ai

Query with variables and backtracking on success

Example

lecturer(olivier,ai).
lecturer(geoff,ai).
lecturer(geoff,projects).

--------------------------------------------------------
?- lecturer(geoff,Anything).
yes
Anything = ai     ? ;
yes
Anything = projects

Example

lecturer(olivier,ai).
lecturer(john,pascal).
lecturer(geoff,ai).
lecturer(john,programming).
lecturer(nizam,networks).
lecturer(peter,graphics).
lecturer(geoff,projects).
lecturer(olivier,ppl).
lecturer(john,graphics).

--------------------------------------------------------
?- lecturer(Anyone,Subject),lecturer(Anyone,Another_subject).
yes
Anyone = olivier
Subject = ai 
Another_subject = ai    ? ;
yes
Anyone = olivier
Subject = ai 
Another_subject = ppl    ? ;
yes ...

Example

has_studied(joe, prerequisite_to(adv_ai)).

hod_permission_to_study(jane,adv_ai).

has_enrolled(jane,adv_ai).

has_brains_to_pass(adv_ai,joe).

can_study(Student,Course):-
    has_studied(Student,prerequisite_to(Course)).
can_study(Student,Course):-
    hod_permission_to_study(Student,Course).

--------------------------------------------------------
?- can_study(Anyone,adv_ai).
yes
Anyone = joe ;
yes
Anyone = jane

Example

has_studied(fred,apt).
has_studied(Anyone,Prerequisite):-
    is_prerequisite(Prerequisite,Anything),
    has_studied(Anyone,Anything).

is_prerequisite(adv_ai,apt).
is_prerequisite(pascal,adv_ai).

--------------------------------------------------------
?- has_studied(fred,Course).
yes
Course = apt,        ? ;
yes
Course = adv_ai,    ? ;
yes
Course = pascal

Consider what happens if the tail is reordered Consider what happens if the tail is re-ordered and the has_studied clauses are swapped! Notice the tree like nature of the search for alternative solutions.

Collecting Successes

There are meta-predicates for collecting all solutions, the simplest of which is findall. findall takes three arguments: the variable or term to collect, the query, and a variable in which a list of the collected results are placed.

Example

lecturer(olivier,ai).
lecturer(john,pascal).
lecturer(geoff,ai).
lecturer(john,programming).
lecturer(nizam,networks).
lecturer(peter,graphics).
lecturer(geoff,projects).
lecturer(olivier,ppl).
lecturer(john,graphics).

--------------------------------------------------------
?- findall(Lecturer,lecturer(Lecturer,_),AllLecturers).
yes
Lecturer = Lecturer
AllLecturers = [olivier, john, geoff, john, nizam, peter, geoff, olivier, john]

Example

lecturer(olivier,ai).
lecturer(john,pascal).
lecturer(geoff,ai).
lecturer(john,programming).
lecturer(nizam,networks).
lecturer(peter,graphics).
lecturer(geoff,projects).
lecturer(olivier,ppl).
lecturer(john,graphics).

--------------------------------------------------------
?- findall(whowhat(Lecturer,Subject),lecturer(Lecturer,Subject),AllLecturers).
yes
Lecturer = Lecturer
Subject = Subject
AllLecturers = [whowhat(olivier, ai), whowhat(john, pascal), whowhat(geoff, ai),
 whowhat(john, programming), whowhat(nizam, networks), whowhat(peter, graphics),
 whowhat(geoff, projects), whowhat(olivier, ppl), whowhat(john, graphics)]

Output

A side effect that always succeeds

put(<integer>) outputs the character with that ASCII code.
nl outputs a new line
tab(<integer>) tabs N spaces
write(<term>) writes out the term.

Input

A side effect that always succeeds

get0(<ASCII value>) succeeds if <ASCII value> unifies with the ASCII value of next character on the input stream, removing that character from the stream.
get(<ASCII value>) is like get0, but ignores characters with ASCII code < 32.
skip(<ASCII value>) skips over characters on the input stream until a character with an ASCII value which unifies with the argument is found. It is not available for reading.
read(<term>) reads a term from the input stream and attempts to unify it with the argument. Input must be terminated with a ., which is not part of the term.

Comments

/*----This is a comment */
%----This is a comment

Example to Run

%------------------------------------------------------------------------------
make_tree(Tree):-
    read(Word),
    insert(Word,Tree).    %----Note recursion for looping
%------------------------------------------------------------------------------
insert(exit,_).

insert(Word,Tree):-
    insert_word(Word,Tree),
    make_tree(Tree).
%------------------------------------------------------------------------------
insert_word(Word,node(Word,_,_)).

insert_word(Word,node(NodeWord,Smaller,_)):-
    ordered(Word,NodeWord),
    insert_word(Word,Smaller).

insert_word(Word,node(NodeWord,_,Larger)):-
    ordered(NodeWord,Word),
    insert_word(Word,Larger).
%------------------------------------------------------------------------------
ordered(Big,Small):-
    Big @> Small.
%------------------------------------------------------------------------------

Tutorial

Write a program that stores information about your family, and will answer queries about relationships. Information about individual people must be stored as facts containing the persons name, sex and parents' names, e.g.

person(geoff,male,bob,margaret).

Here are the queries you should be able to answer ...

?- father(Person,Father).
?- mother(Person,Mother).
?- parent(Person,Parent). Algorithm : Either a mother or father
?- offspring(Person,Offspring). Algorithm : The inverse of parent.
?- son(Person,Son). Algorithm : A son is a male offspring.
?- daughter(Person,Daughter). Algorithm : A daughter is a female offspring.
?- sibling(Person,Sibling). Algorithm : Siblings have the same parents.
?- brother(Person,Brother). Algorithm : A brother is a male sibling.
?- sister(Person,Sister). Algorithm : A sister is a female sibling.
?- aunt(Person,Aunt). Algorithm : An aunt is a parent's sister.
?- uncle(Person,Uncle). Algorithm : An uncle is a parent's brother.
?- nephew(Person,Nephew). Algorithm : A nephew is a sibling's son.
?- niece(Person,Niece). Algorithm : A niece is a sibling's daughter.
?- descendant(Person,Descendant). Algorithm : A descendant is an offspring or a descendant's offspring.
?- ancestor(Person,Ancestor). Algorithm : The inverse of descendant.
?- relation(Person,Relation). Algorithm : Descendants of most distant ancestor.

Answer

Programming Technique

Programming style

C&M pg 176, Bratko Chapter 8

Layout

Procedures (clauses for a given predicate symbol and arity) should be grouped.
Tail predicates should be one per line. If there is only one it may be on the same line as the head.
Procedures should be clearly separated.
Style must be consistent.
Distinct modules should be separated into distinct files.

Commenting

The entry level procedures should be documented as such at the top of the program.
Procedures should be commented as to their overall purpose
Clauses should be commented to indicate their specific purpose within the procedure.

Clauses

Should be short
Should use meaningful names
Recursive procedures should have boundary conditions first and catch all conditions last
Cuts and nots should be used with great care, and be well commented.
Do not use ; for or. Rather write extra clauses.
There is seldom a need for =. Simply use the same variable.
Beware of falling foul of the lack of occurs check in most Prologs.

Predicates

Arguments in predicates should be ordered with "input" arguments first, subsidiary data next, and output arguments last.

Debugging

trace turns on tracing
notrace turns off tracing
spy <predicate> places a spy point on the predicate.
nospy <predicate> removes a spy point from the predicate.
nodebug removes all spy points.
debugging lists what spy points are set.

CALL, EXIT, REDO, FAIL

Tutorial

Use the debugging facilities to follow the execution of your programs.