Transcript Prolog Concepts

Prolog Concepts
A declarative language



Most programming languages are imperative—you tell the
computer what to do to solve a problem
Prolog is declarative—you give it the data it needs, and it solves the
problem for you
Consider:

append([], List, List).
append([Head | Tail], List, [Head | More]) :append(Tail, List, More).

This defines what it means append lists




You can use it to append two lists
You can use it to find what to append to a list to get another list
You can use it to find what list to append to to get another list
You can test whether the relation holds between three lists
2
append examples I

3 ?- append([a, b], [c, d], X).
X = [a, b, c, d].

4 ?- append([a, b], X, [a, b, c]).
X = [c].

5 ?- append(X, [c, d], [a, b, c, d]).
X = [a, b]
false.
2
append examples I

6 ?- append(X, Y, [a, b, c]).
X = [], Y = [a, b, c]
X = [a], Y = [b, c]
X = [a, b], Y = [c]
X = [a, b, c], Y = []
false.

7 ?- append([a, b], X, Y).
Y = [a, b|X].

8 ?- append(X, [a, b, c], Y).
X = [], Y = [a, b, c]
X = [_G1989], Y = [_G1989, a, b, c]
X = [_G1989, _G1995], Y = [_G1989, _G1995, a,
b, c]
2
A constraint satisfaction language

Prolog is also one of a number of constraint satisfaction
languages


You tell it the constraints on a problem (e.g. the solution must
be someone who is both female and rich), and it finds a solution
that satisfies those constraints
A “logic puzzle” is nothing more than a set of constraints
(e.g. every man has a different tie)
3
A homoiconic language



Prolog is homoiconic—that is, there is no distinction
between “statements” in the language and the “data”
that the languages processes
When you provide “input” to a Prolog program (e.g. for
an adventure game), you use the same syntax as when
you write the program
We haven’t emphasized homoiconicity in Prolog,
because it is more important in some of the other
languages we will be studying
4
Prolog does backtracking

You don’t have to implement backtracking in Prolog; the
language does it for you

The only other “language” I know of that does this is Regular
Expressions, which are a “sublanguage” of most modern
programming languages
loves(chuck, X)
call
fail
female(X)
rich(X)
exit
redo
5
Prolog uses unification

The basic rules of unification are:




Any value can be unified with itself
A variable can be unified with another variable
A variable can be unified with any value
Two different structures can be unified if their constituents can
be unified



Lists are a particularly important kind of structure
A variable can be unified with a structure containing that same
variable
Unification is reflexive, symmetric, and transitive
6
Unification and pattern matching

Parameter transmission is by unification, not assignment




member(H, [H | T]).
member(H, [_ | T]) :- member(H, T).
Thus, parameters are not restricted to simple variables
Note also the use of the “don’t care” variable, _
Many other languages use pattern matching, which is like
unification, but may be asymmetric:

value match { pattern1 => code1; pattern2 => code2; … }
7
Lists

Lists, not arrays, are the fundamental data structures in
Prolog and nearly all functional languages


Non-empty lists consist of a head (the first element in the list)
and a tail (a list of the remaining elements)
Although the syntax may differ, this way of treating a list is
common among functional languages
8
Predicates as functions

Prolog has no functions, so it cannot be a functional language
 But we can do something similar with predicates

map(_, [], []).
map(P, [H|T], [H2|T2]) :- call(P, H, H2), map(P, T, T2).
filter(_, [], []).
filter(P, [H|T], [H|T2]) :- call(P, H), filter(P, T, T2).
filter(P, [_|T], L) :- filter(P, T, L).
twice(X, Y) :- Y is 2 * X.
even(X) :- X mod 2 =:= 0.

31 ?- map(twice, [1, 2, 3], X).
X = [2, 4, 6] .
32 ?- filter(even, [1, 2, 3, 4], X).
X = [2, 4]
8
Prolog is a theorem prover


Prolog is an implementation of resolution theorem
proving in a programming language
Because it is based on logic, there is very little that is ad
hoc or arbitrary about Prolog
9
Resolution

A clause is a disjunction (“or”) of zero or more literals, some or all of which
may be negated


sinks(X)  dissolves(X, water)  ¬denser(X, water)
Any expression in the predicate calculus can be put into clause form



X  Y can be rewritten as ¬ X  Y
Conjunctions (“ands”) can be rewritten as separate clauses
The existential quantifier  can be replaced by a Skolem function




If the existential quantifier is under control of a universal quantifier, replace it with a
function of the universally quantified variable
Otherwise, just replace with a constant (whose value need not be known)
Universal quantifiers, , can be dropped
Here is the resolution principle:


X  someLiterals
¬ X  someOtherLiterals
---------------------------------------------conclude: someLiterals  someOtherLiterals
Clauses are closed under resolution
From
and
10
The End
11