2. Sample Prolog Programs

In this chapter we provide several sample Prolog programs. The programs are given in a progression from fairly simple programs to more complex programs. The key goals of the presentation are to show several important methods of knowledge representation in Prolog and the declarative programming methodology of Prolog.

2.1 Map colorings

This section uses a famous mathematical problem -- that of coloring planar maps -- to motivate logical representations of facts and rules in Prolog. The prolog program developed provides a representation for adjacent regions in a map, and shows a way to represent colorings, and a definition of when the colorings in conflict; that is, when two adjacent regions have the same coloring. The section introduces the concept of a semantic program clause tree -- to motivate the issue of semantics for logic-based programming.

2.2 Two factorial definitions

This section introduces the student to computations of mathematical functions using Prolog. Various built-in arithmetic operators are discussed. Also discussed is the concept of a Prolog derivation tree, and how derivation trees are related to tracings of Prolog.

2.3 Towers of Hanoi puzzle

This famous puzzle is formulated in Prolog. The discussion concerns both the declarative and the procedural meanings of the program. The program write puzzle solutions to the screen.

Examples show various ways to load programs into Prolog, and an example of a program calling a system editor is given. The reader is encouraged to read sections 3.1 an 3.2 on How Prolog Works before continuing with section 2.5

2.5 Negation as failure

The section gives an introduction to Prolog's negation-as-failure feature, with some simple examples. Further examples show some of the difficulties that can be encountered for programs with negation as failure.

2.6 Tree data and relations

This section shows Prolog operator definitions for a simple tree structure. Tree processing relations are defined and corresponding goals are studied.

2.7 Prolog lists

This section contains some of the most useful Prolog list accessing and processing relations. Prolog's primary dynamic structure is the list, and this structure will be used repeatedly in later sections.

2.8 Change for a dollar

A simple change maker program is studied. The important observation here is how a Prolog predicate like 'member' can be used to generate choices, the choices are checked to see whether they solve the problem, and then backtracking on 'member' generates additional choices. This fundamental generate and test strategy is very natural in Prolog.

2.9 Map coloring redux

We take another look at the map coloring problem introduced in Section 2.1. This time, the data representing region adjacency is stored in a list, colors are supplied in a list, and the program generates colorings which are then checked for correctness.

2.10 Simple I/O

This section discusses opening and closing files, reading and writing of Prolog data.

2.11 Chess queens challenge puzzle.

This familiar puzzle is formulate in Prolog using a permutation generation program from Section 2.7. Backtracking on permutations produces all solutions.

Prolog's 'setof' and 'bagof' predicates are presented. An implementation of 'bagof' using 'assert' and 'retract' is given.

2.13 Truth table maker

This section designs a recursive evaluator for infix Boolean expressions, and a program which prints a truth table for a Boolean expression. The variables are extracted from the expression and the truth assignments are automatically generated.

2.14 DFA parser

A generic DFA parser is designed. Particular DFAs are represented as Prolog data.

2.15 Graph structures and paths

This section designs a path generator for graphs represented using a static Prolog representation. This section serves as an introduction to and motivation for the next section, where dynamic search grows the search graph as it works.

2.16 Search

The previous section discussed path generation in a static graph. This section develops a general Prolog framework for graph searching, where the search graph is constructed as the search proceeds. This can be the basis for some of the more sophisticated graph searching techniques in A.I.

2.17 Animal identification game

This is a toy program for animal identification that has appeared in several references in some form or another. We take the opportunity to give a unique formulation using Prolog clauses as the rule database. The implementation of verification of askable goals (questions) is especially clean. This example is a good motivation for expert systems, which are studied in Chapter 6.

2.18 Clauses as data

This section develops a Prolog program analysis tool. The program analyses a Prolog program to determine which procedures (predicates) use, or call, which other procedures in the program. The program to be analyzed is loaded dynamically and its clauses are processed as first-class data.

2.19 Actions and plans

An interesting prototype for action specifications and plan generation is presented, using the toy blocks world. This important subject is continued and expanded in Chapter 7.

Prolog Tutorial Contents