Information Technology Reference
In-Depth Information
4
Writing Prolog Programs
The previous chapter looked at what it takes for a Prolog program to be grammatically
correct and how it is then used to establish queries. But there is more to a language
than just getting the grammar right. There is an old saying in computer science,
abbreviated as GIGO: garbage in, garbage out. This means that if the program given
to Prolog is grammatically correct but garbage, Prolog will use it to answer queries
without complaining, but the answers will also be garbage.
This chapter looks at what it takes to write Prolog programs that are not garbage.
The first section examines what it means for a program to be fully correct. Section 2
introduces a new program in a blocks world and studies how it was written. This
leads to a discussion of recursion in section 3, and to its companion, mathematical
induction, in section 4. Section 5 considers the issue of programs that run forever
(see section 2.5.1), and how to avoid writing them. Section 6 looks at a more complex
predicate as it appears in the blocks-world program. Finally, section 7 introduces the
issue of program efficiency.
4.1 The truth in Prolog
How do we know whether a grammatically correct program will do what it is
supposed to? In Prolog, the answer is perhaps clearer than in other programming
languages. A Prolog program is a knowledge base made up of clauses. Each of those
clauses is an encoding of an atomic or conditional sentence. To answer the question,
we need to consider the
truth
of these sentences.
4.1.1 The truth, and nothing but
Let us go back to the family example of figure 3.1, which used the predicate
child
.
As far as Prolog is concerned, that name does not mean anything; it could have been
boojum
. But the writers of the program had a definite idea in mind when they wrote
child(john,sue)
and that idea is expressed by the English sentence “John is a child
