PROBLEM SOLVING AND SEARCH
Lecture 1
Imperative (programs as recipes)
function sum(list : List) : Nat
i = 0
while (i < list.lenght)
sum = sum + list[i]
i++
return sum
Functional (programs as functions e.g. Haskell)
sum [] = 0
sum (x : xs) = x + sum xs
Declarative (programs as ‘problems’ e.g. Prolog)
sum([], 0).
sum([Head | Tail, Result):-
sum(Tail, S),
Result is Head + S.
● Imperative programming: specify how to compute
● Declarative programming: specify what to compute
The origins of Prolog (PROgrammation en LOGique):
● Invented in the 1970s by Alain Colmerauer and a team of researchers in France – using
a natural language like French to reason and communicate directly with a computer
● Originally intended for natural language processing – clear and concise programs
● Prolog and Lisp are the two main AI programming languages today
● There are different interpreters, we will use SWI-Prolog
bigger(elephant, horse).
bigger(horse, donkey).
bigger(donkey, dog).
bigger(donkey, monkey).
,?- bigger(donkey, dog).
true
?- bigger(monkey, elephant).
false
?- bigger(elephant, monkey).
false
bigger(X, Y) :- bigger(X, Z), bigger(Z, Y).
?- bigger(elephant, monkey).
true
?- bigger(X, donkey).
X = horse ;
X = elephant ;
false
?- bigger(donkey, X), bigger (X, monkey).
X = dog
?- bigger(donkey, X), bigger(Y, monkey).
X = dog
Prolog terms are either:
● Variables
● Atomic terms: numbers and atoms
● Compound terms
Variables start with a capital letter or the underscore: X, Elephant, _G177, MyVariable, _
Anonymous variable: _
Atoms start with a lowercase letter or are enclosed in single quotes: elephant, xYZ, a_123,
‘Hello?’
Compound terms consist of a functor (an atom) and a number of arguments (terms) enclosed in
brackets: bigger(horse, X)
f(g(Alpha, _), 7)
‘female’(dog)
Ground terms are terms without variables
Facts are compound terms (or atoms), followed by a full stop
, Facts are used to define something as being unconditionally true
bigger(elephant, horse).
parent(john, mary).
Rules consist of a head and a body separated by ‘:-’
The head of a rule (a compound term or an atom) is true if all goals in the body (each a
compound term or an atom) can be proved to be true
grandfather(X, Y) :-
father(X, Z),
parent(Z, Y).
Facts and rules are used to define predicates
Facts and rules are also called clauses
A program is a list of clauses
● Compose your programs in a text editor
A query consists of one or several compound terms (or atoms), separated by commas and
followed by a full stop
● Type your queries in the Prolog prompt and expect a response
● ?- bigger(horse, X), bigger(X, dog).
X = donkey
true
Built-in predicates:
● Compiling a program file:
?- consult(‘big-animals.pl’).
true
● Writing something (a term) on the screen:
?- write (‘Hello!’), nl, write(‘Goodbye!’)
Hello!
Goodbye!
true
Two terms match if they are identical or can be made identical by substituting their variables
with suitable ground terms
We can explicitly ask Prolog whether two given terms match by using the built-in
equality-predicate:
?- born(mary, yorkshire) = born(mary, X).
X = yorkshire
true
Lecture 1
Imperative (programs as recipes)
function sum(list : List) : Nat
i = 0
while (i < list.lenght)
sum = sum + list[i]
i++
return sum
Functional (programs as functions e.g. Haskell)
sum [] = 0
sum (x : xs) = x + sum xs
Declarative (programs as ‘problems’ e.g. Prolog)
sum([], 0).
sum([Head | Tail, Result):-
sum(Tail, S),
Result is Head + S.
● Imperative programming: specify how to compute
● Declarative programming: specify what to compute
The origins of Prolog (PROgrammation en LOGique):
● Invented in the 1970s by Alain Colmerauer and a team of researchers in France – using
a natural language like French to reason and communicate directly with a computer
● Originally intended for natural language processing – clear and concise programs
● Prolog and Lisp are the two main AI programming languages today
● There are different interpreters, we will use SWI-Prolog
bigger(elephant, horse).
bigger(horse, donkey).
bigger(donkey, dog).
bigger(donkey, monkey).
,?- bigger(donkey, dog).
true
?- bigger(monkey, elephant).
false
?- bigger(elephant, monkey).
false
bigger(X, Y) :- bigger(X, Z), bigger(Z, Y).
?- bigger(elephant, monkey).
true
?- bigger(X, donkey).
X = horse ;
X = elephant ;
false
?- bigger(donkey, X), bigger (X, monkey).
X = dog
?- bigger(donkey, X), bigger(Y, monkey).
X = dog
Prolog terms are either:
● Variables
● Atomic terms: numbers and atoms
● Compound terms
Variables start with a capital letter or the underscore: X, Elephant, _G177, MyVariable, _
Anonymous variable: _
Atoms start with a lowercase letter or are enclosed in single quotes: elephant, xYZ, a_123,
‘Hello?’
Compound terms consist of a functor (an atom) and a number of arguments (terms) enclosed in
brackets: bigger(horse, X)
f(g(Alpha, _), 7)
‘female’(dog)
Ground terms are terms without variables
Facts are compound terms (or atoms), followed by a full stop
, Facts are used to define something as being unconditionally true
bigger(elephant, horse).
parent(john, mary).
Rules consist of a head and a body separated by ‘:-’
The head of a rule (a compound term or an atom) is true if all goals in the body (each a
compound term or an atom) can be proved to be true
grandfather(X, Y) :-
father(X, Z),
parent(Z, Y).
Facts and rules are used to define predicates
Facts and rules are also called clauses
A program is a list of clauses
● Compose your programs in a text editor
A query consists of one or several compound terms (or atoms), separated by commas and
followed by a full stop
● Type your queries in the Prolog prompt and expect a response
● ?- bigger(horse, X), bigger(X, dog).
X = donkey
true
Built-in predicates:
● Compiling a program file:
?- consult(‘big-animals.pl’).
true
● Writing something (a term) on the screen:
?- write (‘Hello!’), nl, write(‘Goodbye!’)
Hello!
Goodbye!
true
Two terms match if they are identical or can be made identical by substituting their variables
with suitable ground terms
We can explicitly ask Prolog whether two given terms match by using the built-in
equality-predicate:
?- born(mary, yorkshire) = born(mary, X).
X = yorkshire
true
