Prerequisite courses: Foundations of Computer Science, Algorithms I and Logic & Proof
Aims
The aim of this course is to introduce programming in the Prolog
language. The cut operator and assert/retract are included
to allow real uses of the language to be understood and to make the
language an option to use in a Part II project. The course includes
case studies of familiar algorithms in the declarative idiom.
Lectures
Syntax and Unification. Prolog's slim syntax is described.
Unification is described with examples to show how pattern matching
is achieved.
Lists, terms and arithmetic. The Prolog syntax is used to
create lists and terms, and to perform simple arithmetic.
Graphs. Classic graph algorithms are presented in the
declarative Prolog style.
Trees. Classic tree algorithms are presented in the
declarative Prolog style.
Non-determinism. The backtracking mechanism for finding
alternative solutions is described and illustrated, with techniques
to modify the default behaviour.
Negation as failure. The reasons why Prolog saying ``No''
differs from ``false'' are discussed and illustrated.
Difference structures. Difference lists are described and
students participate in a re-write of programs from classical lists
to difference lists.
Using difference structures. Copying trees is used as an
example to show the optimisations possible for large programs when
the difference structure technique is used.
Objectives
At the end of the course students should
be able to write programs in Prolog using techniques such as
accumulators and difference structures.
know how to model the backtracking behaviour of program
execution.
appreciate the unique perspective Prolog gives to problem
solving and algorithm design.
understand how larger programs can be created using the basic
programming techniques used in this course.
Recommended reading
* Bratko, I. (2001). PROLOG programming for artificial intelligence. Addison-Wesley (3rd ed).
