Transcript Introduction to declarative programmming and Prolog

Declarative
Programming
Introduction
Autumn 2014
Lecture times
Regular lectures on Wednesdays 16:30-18:05, room 12
16 lectures
The lectures at the following dates will be rescheduled
(dates/times to be agreed, but likely to some time in
November/December):
10.09.
17.10.
Some other changes are possible (but hopefully, not too
many).
Web page(s)
http://susurs.mii.lu.lv/juris/courses/dp2014.html
Is expected to contain:
• short summaries of lectures
• power point presentations (when present)
• problems for programming assignments/project
• your grades
• other relevant information (exam dates,
changes in lecture times etc)
Course material also available as e-course:
https://estudijas.lu.lv/login/index.php
Contact information
Juris Vīksna
Room 421, Rainis boulevard 29
email: [email protected]
phone: +371-67213716
Consultations:
• "official" consultation times: Thursdays (???) 16:30-18:00,
Rainis bouleverd 29, room 421;
• by individual arrangements.
In "official" times I will be usually (but probably not always)
available without an appointment, so just in case I recommend
to check in advance.
Programming languages
Imperative
Functional
Logical
C++
Pascal
Java
...
Lisp
ML
Haskell
...
Prolog
Imperative
Declarative
Declarative vs imperative languages
[Adapted from U.Nilsson]
Declarative vs imperative languages
[Adapted from U.Nilsson]
Imperative languages
Program is a list of explicit steps of computation
list procedure cat(list a, list b)
{
list t = list u = copylist(a);
while (t.tail != nil) t = t.tail;
t.tail = b;
return u;
}
Functional languages
Program is a composition of functions
cat(a,b)
if b = nil then a
else cons(head(a), cat(tail(a),b))
Logical languages
Program is a list of facts that are known to be true and
a query, which has to be proved or disproved
u (S(u)  z (R(z)  P(u,z)))
y (S(y) & w (Q(w)  P(y,w)))
y (Q(y)  R(y))
Can this really be done (at least efficiently)?
Depends...
cat([], Z, Z).
cat([H|T], L, [H|Z]) :- cat(T, L, Z).
Propositional logic (propositional calculus)
Infinite set of variables:
Finite set of operators:
Finite set of auxiliary symbols:
A,B,C,D,...
,,,,
(,)
Set of rules that defines syntactically correct formulas, e.g.:
(AB)(AB)
Interpretation of formulas:
We assign truth values 0 and 1 to each of variables in a
formula. The truth value of formula is computed using
rules such as:
A = 1
AB = 1


A=0
A = 1 and B = 1
Propositional logic (propositional calculus)
Propositional logic (propositional calculus)
Predicate logic (first-order)
Infinite set of constants:
Infinite set of variables:
Infinite set of function symbols:
Infinite set of relation symbols:
Finite set of operators:
Finite set of auxiliary symbols:
c1,c2,...
x1,x2,...
f1,f2,...
r1,r2,...
,,,,,,
(,),”,”,
Set of rules that defines syntactically correct formulas, e.g.:
(x)(r(x)c) (y)q(c,y)
(x)(y)r(x,y,c)
r(x,y,c) “might” mean e.g.:
“for given c and for any x there exists y such that x+y=c”
Predicate logic (first-order)
How to assign truth values to predicate logic formulas?
Again we use notion of interpretation, however now it gets
more complicated.
interpretation domain D
c1
r(c2,c2) = 1 or 0 (true or false)
c2
f(c3) = c2
c3
Thus, interpretation defines:
- domain D
- “semantics” of functional and relational symbols.
Given interpretation we can assign truth values to
formulas!
Predicate logic (first-order)
Predicate logic (first-order)
Predicate logic (first-order)
Motivation
 logic programming is quite important and useful
concept in computer science
 kind of fun!
 there are problems for which PROLOG may be a
natural choice of programming language
Requirements
 4-6 short programming assignments
(half of them must be submitted before
the exam session, in order to be allowed
to proceed, others are optional)
0 – 50%
 1 programming project (optional)
0 – 30%
 Exam (open book, optional)
–20 – 20% (?)
Academic honesty
You are expected to submit only your own work!
Sanctions:
Receiving a zero on the assignment (in no circumstances
a resubmission will be allowed)
No admission to the exam and no grade for the course
Textbooks
Ivan Bratko
PROLOG programming for
artificial intelligence
Pearson Range Extension Paul
2011 (4th ed)
Textbooks
Leon Sterling,
Ehud Shapiro
The art of Prolog
MIT Press 1994 (2nd ed)
Textbooks
Richard A. O’Keefe
The craft of Prolog
MIT Press 1990
(reprint 2009)
Textbooks
W.F. Clocksin,
C.S.Mellish
Programming in Prolog
Springer Verlag 2003
(4th/5th ed)
(5th ed looks like just a reprint
of 4th ed from 2003)
Textbooks
This one can be downloaded
from the internet:
http://www.ida.liu.se/~ulfni/lpp/
Ulf Nilsson and Jan Maluszynski
Logic, Programming and
Prolog (2ed)
Previously published by
John Wiley & Sons Ltd.
Textbooks
Also available from the internet:
http://bookboon.com/en/textbooks/it-programming/applications-of-prolog
http://bookboon.com/en/textbooks/it-programming/prolog-techniques-applications-of-prolog
Attila Csenki
Applications of Prolog
Prolog Techniques
Textbooks
L.C.Paulson
ML for working programmer
Cambridge University Press, 1996
Prolog compilers/interpreters
SWI Prolog
http://www.swi-prolog.org/
Prolog compilers/interpreters
SWI Prolog Editor
http://lakk.bildung.hessen.de/netzwerk/faecher/informatik
/swiprolog/indexe.html
An integrated environment that allows editing
and running of Prolog programs + provides some
debugging functionality.
Http link also from SWI Prolog site.
Prolog compilers/interpreters
SICSTUS Prolog http://www.sics.se/isl/sicstuswww/site/index.html
Prolog compilers/interpreters
[Adapted from wikipedia.org]
Workplan
 PROLOG syntax
 formal (its quite simple...)
4
 special keywords and their semantics
(also there is not that much...)
 Computational model of PROLOG programs
1
 PROLOG interpreters - how to use them
1
 Program examples
 PROLOGish (often AI related)
7
 general (for training - to try to write thing that are hard in PROLOG)
 Functional programming
2
Prolog – short history
1961
Resolution method for predicate calculus (John Robinson)
1965
ABSYS (Aberdeen System), ABSET (Aberdeen Set Language)
(Michael Foster, Ted Ellock)
1971
SYSTEMQ (Colmerauer, Kowalski), eventually it become
Prolog
1974
1st FORTRAN compiler for Prolog (David Warren)
Was generally considered to be a very promising language up to
early 1990s
Prolog is a ‘declarative’ language

Clauses are statements about what is true about a
problem, instead of instructions how to accomplish
the solution.

The PROLOG system uses the clauses to work out
how to accomplish the solution by searching through
the space of possible solutions.

Not all problems have pure declarative
specifications. Sometimes extralogical statements
are needed.
What a program looks like
% At the Zoo %
elephant(george).
elephant(mary).
panda(chi_chi).
panda(ming_ming).
dangerous(X) :- big_teeth(X).
dangerous(X) :- venomous(X).
guess(X, tiger) :- stripey(X), big_teeth(X), isaCat(X).
guess(X, koala) :- arboreal(X), sleepy(X).
guess(X, zebra) :- stripey(X), isaHorse(X).
Example: Concatenate lists a and b
In an imperative language:
list procedure cat(list a, list b)
{
list t = list u = copylist(a);
while (t.tail != nil) t = t.tail;
t.tail = b;
return u;
}
In a functional language:
cat(a,b)
if b = nil then a
else cons(head(a),cat(tail(a),b))
In a declarative language
cat([], Z, Z).
cat([H|T], L, [H|Z]) :- cat(T, L, Z).
Prolog “pseudocodes”
Prolog program
“Hand computation”
“Pseudocode”
[Adapted from A.Csenki]