*Lecturer: Dr M. Richards*
(`mr@cl.cam.ac.uk`)

*No. of lectures:* 12

**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.

**Lectures**

**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.