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.
2.4 Loading programs, editing programs
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.
2.12 Set of answers
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.
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