Objectives

This module introduces the list, the most influential data type in artificial intelligence programming. It starts with an introduction to lists in Prolog and how lists are typically processed. The major section looks at list processing operations, splitting them into three groups, classified by the nature of their terminating condition. Some of the examples given in this section work but are not the most efficient method of implementation in practical Prolog, so some examples based on the use of accumulators are given.

These notes are a complete re-writing of a previous version. Their new shape is largely due to a critical study of the old notes by Dorothee Wiegand undertaken as an MSc (Computer Science) project and reported in: Wiegand, Dorothee. (1992) A Prolog teaching aid. Unpublished MSc thesis: School of Computer Science, University of Birmingham, September 1992.
 

The anatomy of lists and their processing

This answers questions such as "why use lists?", "how are lists processed?", "what do Prolog lists look like?" and "how does unification work with lists?".

Termination criteria

It is necessary to know how the processing of a list will be successfully completed so as to be able to write correct list processing procedures. This section introduces three termination criteria which frequently occur as patterns in Prolog programs.

Multiple uses of procedures

With some procedures it is possible to use them in more than one way. For instance, the classic definition of the Prolog append/3 will not only tell you what two lists appended together make, but will also (given one list) tell you which pairs of lists could be appended to make it. This section explores the multiple use of procedures and looks at some of the problems encountered.

Accumulators in Prolog

The previous section included examples designed to illustrate termination. However, the examples given aren't necessarily the ones most frequently used by expert programmers, because there are other versions that are more efficient. These are considerations that have to take into account the way that Prolog is implemented on the underlying hardware. In this sense, the previous versions are not "wrong" but less appropriate. The topic of efficiency in list processing is taken further in discussion on the topic of accumulators.

Determinism and equality in list processing

Prolog's capability of solving non-deterministic problems is one of its strengths, but for the unwary programmer, it can introduce unintended behaviours into a program. Worse still, a lack of careful analysis and description of a problem can lead programs into infinite recursion. This section looks at when list processing procedures should be deterministic, how to make programs more accurate expressions of the designer's intentions and how to test with relationships other than unification.