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