Prolog

Aims

The aim of this course is to introduce programming in the Prolog language. Prolog encourages a different programming style to Java or ML and particular focus is placed on programming to solve real problems that are suited to this style. Practical experimentation with the language is strongly encouraged.

Lectures

• Introduction to Prolog. The structure of a Prolog program and how to use the Prolog interpreter. Unification. Some simple programs.
• Arithmetic and lists. Prolog’s support for evaluating arithmetic expressions and lists. The space complexity of program evaluation discussed with reference to last-call optimisation.
• Backtracking, cut, and negation. The cut operator for controlling backtracking. Negation as failure and its uses.
• Search and cut. Prolog’s search method for solving problems. Graph searching exploiting Prolog’s built-in search mechanisms.
• Difference structures. Difference lists: introduction and application to example programs.
• Building on Prolog. How particular limitations of Prolog programs can be addressed by techniques such as Constraint Logic Programming (CLP) and tabled resolution.

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 or 4th ed.).
Sterling, L. and Shapiro, E. (1994). The art of Prolog. MIT Press (2nd ed.).

Further reading:

O’Keefe, R. (1990). The craft of Prolog. MIT Press. [This book is beyond the scope of this course, but it is very instructive. If you understand its contents, you’re more than prepared for the examination.]