Prolog for Artificial Intelligence

Lecturer: Dr W.F. Clocksin (wfc@cl.cam.ac.uk)

No. of lectures: 12

This course is a prerequisite for Artificial Intelligence (Part II).

Aims

The aim of this course is to introduce the elements of programming in the language Prolog. A relatively pure subset of Prolog is covered, which excludes assert/retract, but includes the cut. The course consists of tutorials with exercises in graded order of difficulty, followed by case studies demonstrating a variety of applications.

Topics

• Introduction. History, syntax, semantics, getting started running programs.

• Goals. Clauses, procedures, backtracking.

• Data structures and unification. Recursion in data and process. Variables are holes in data structures.

• List processing. Some practical programming examples.

• Mappings. Some principles of structuring problem solving.

• Accumulators. Ways of constructing tail-recursive procedures from specifications.

• Difference structures. Probably the best programming technique ever invented.

• Computing with difference structures. Ways of exploiting the above.

• Modifying backtracking. Ways of specifying control over the default chronological backtracking execution rule.

• Case studies. The remaining lectures are case studies that demonstrate larger programs and use the programming techniques previously introduced. The case studies are chosen from an ever-changing set including formula manipulation, digital circuit analysis, knowledge representation, the Fast Fourier Transform, compiling procedural languages.

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 prepared using the basic programming schemata introduced in the course

Recommended books

Clocksin, W.F. (1997). Clause and Effect: PROLOG Programing for the Working Programmer. Berlin: Springer-Verlag.
Bratko, I. (1986). PROLOG: Programming for Artificial Intelligence. Addison-Wesley.
Shoham, Y. (1994). Artificial Intelligence Techniques in PROLOG. Morgan Kaufmann.