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 numbers and strings and ... are separate.
Declarative nature allows programmer to concentrate on the nature of the problem, rather than the method of solution.
Very clear semantics - defined mathematically
Some pragmatics are required however to produce problem solutions!!

The principles of running Prolog

SWI Prolog

Very widely used, free!
Available from SWI

Create a configuration file ...

On Linux iand OSX, in $HOME/.config/swi-prolog/init.pl
On Windows, in the CSIDL folder CSIDL_APPDATA, typically C:\Documents and Settings\username\Application Data.

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)).
%----Allow code to be listed
:- use_module(library(listing)).
%----Turn on traditional debugging
:- use_module(library(prolog_debug)).
:- use_module(library(edinburgh)).
%----Undefine "not" so it can be used as a user predicate
:- op(0,fy,not).
%----Limit depth and style of printing
:- set_prolog_flag(answer_write_options,
                   [ quoted(true),
                     portray(true),
                     max_depth(100), attributes(portray)
                   ]).

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 several forms, atoms and numbers and strings.
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'
Numbers
- Integers
- Floats
- Rationals are not atomic, SWI is weird
Strings (SWI only)
- Traditionally "quoted strings" were the same as a list of the quoted characters' ASCII values.

Example

geoff
'the cat and the rat'
'ABCD'
123
123.456
"the quick brown fox"

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.
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
_
     
```
In terms of logic, variables are universally quantified.
Variables in Prolog are rather different to those in most other programming 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.
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 predicates

geoff_is_a_lecturer
can_study_adv_ai
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 (BinaryTree)

%------------------------------------------------------------------------------
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).

Facts

Always end with . in a program.
Lower case alphabetic for first letter of predicate symbols.

Examples

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

Rules

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

Examples

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.

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

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

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

Queries

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

A query succeeds if there is any clause whose head unifies with the query, and whose body succeeds. In the absence of variables "unifies" simply means that they must match exactly. This concept will be generalised when variables are introduced.
A clause succeeds if its body succeeds.
- The body of a clause is a conjunctive query.
- The predicates of a conjunctive query are evaluated sequentially.
- A conjunctive query succeeds if all predicates succeeds.
- If a predicate of a conjunctive query fails, then alternative solutions to earlier predicates are tried.
If a clause body fails, alternative subsequent clauses are tried.
If no head unifies with a query, then the query fails.
Queries eventually succeed or fail and the interpreter prints yes or no.

Example : Query on propositional rules (QOnPropRules)

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 (QConjunctiveNo)

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

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 (QBackFail)

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 (QAlternative)

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 (QUnifyRulesVars)

has_enrolled(jane,adv_ai).

hod_permission_to_study(jane,adv_ai).

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

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

-----------------------------------------------------
?- 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 (QUnifyBack2)

has_studied(joe,prerequisite_to(adv_ai)).

hod_permission_to_study(jane,adv_ai).

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

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

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

Example (QUnifyBack6)

is_prerequisite(adv_ai,apt).

is_prerequisite(pascal,adv_ai).

has_studied(fred,apt).

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

--------------------------------------------------------
?- 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.

The flow of data is bidirectional by unification. The unification also allows data to be "pulled apart" as part of the call to a clause.

Example (QUnifyArguments)

hod_permission_to_study(jane,adv_ai).

has_enrolled(jane,adv_ai).

is_prerequisite(pascal,adv_ai).

has_studied(jane,pascal).

has_studied(Student,prerequisite_to(Course)):-
    is_prerequisite(Prerequisite,Course),
    has_studied(Student,Prerequisite).

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

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

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

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

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

Query with negation, without backtracking

Example (QUnifyArgumentsCut)

hod_permission_to_study(jane,adv_ai).

has_enrolled(jane,adv_ai).

is_prerequisite(pascal,adv_ai).

has_studied(jane,pascal).

has_studied(Student,prerequisite_to(Course)):-
    is_prerequisite(Prerequisite,Course),
    has_studied(Student,Prerequisite).

can_study(Anyone,Anything):-
    is_prerequisite(Prerequisite,Anything),
    \+ has_studied(Anyone,Prerequisite),
    !,
    hod_permission_to_study(Anyone,Anything).

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

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

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

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 (QUnifyBack4)

lecturer(olivier,ai).
lecturer(john,pascal).
lecturer(olivier,ai).
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, olivier, geoff, john, nizam, peter, geoff, olivier, john]

Example

lecturer(olivier,ai).
lecturer(john,pascal).
lecturer(olivier,ai).
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(olivier, ai), 
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

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.

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.
%------------------------------------------------------------------------------

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.

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