Computer LaboratoryComputer Science Syllabus - Prolog

Prolog
Next: Semantics of Programming Languages Up: Michaelmas Term 2006: Part Previous: Logic and Proof   Contents

## Prolog

Lecturer: Mrs K.S. Taylor

No. of lectures: 8

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.