Skip to main content

Über dieses Buch

Prolog Versus You shows how you can take up the gauntlet of the logic programming language Prolog (PROgramming in LOGic) and use it as an obedient programming and problem solving tool. Logic programming emphasizes that programming is a human activity and consequently that programs should be easy for humans to write, understand and manipulate. In a program knowledge about the problem is stated in a logical language without consideration of the underlying machine language. This book has emerged from undergraduate courses in logic programming. The relation to logic is described and the necessary logic is provided continuously. No previous programming experience is assumed and it can be used by beginners as well as by advanced programmers. The book emphasizes the declarative reading of Prolog programs which greatly facilitates the thinking about the problems and yields programs easy to understand. The book covers logic programs, their execution and data structures; databases and expert systems; program synthesis, program correctness and program transformation as well as an efficient computation of Prolog programs. Each chapter ends with some exercises (with solutions). The book also contains a thorough index, appendices and a chapter on Prolog implementations: DECsystem-10 Prolog, Tricia, Quintus Prolog, MProlog, Turbo Prolog, micro-Prolog and LM-Prolog.



Round 1. Logic Programs

A logic program is a description of an imaginary or real world. In every world there are various objects and the program describes properties of the objects and relations between them. The description, i.e. the program, makes it possible to draw conclusions about the objects in the described world. Objects in the world may be concrete individuals such as persons and numbers, abstract concepts or abstract structures such as lists or trees. Two descriptions of the same world may be entirely different, focusing on different objects and relations, depending on who is looking at the world and the purpose of the observation. Our outlook is mirrored in the description; we include only those objects, properties and relations which we think important.
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman

Round 2. Execution of Logic Programs

The time has come for us to find out how conclusions can be drawn from our world descriptions, i.e. how to execute Prolog programs. The conclusions are verified or refuted by a deduction. The clauses of the program are the premises of the deduction. A deduction consists of a sequence of deduction steps. To create a new step in the sequence we apply an inference rule either on premises or on formulas we have obtained from previous deduction steps. An inference rule states how a formula will follow from certain premises, i.e. an inference rule takes a set of premises and produces a conclusion:
$$ \frac{{P_1 \, \cdots \,P_n }} {S} $$
S is a conclusion inferred from the premises P1,…, P n .
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman

Round 3. Data Structures

In our examples we have met with different types of terms. We have used, for instance, the constants Thor, Odin, and 0 and the variables x, parent, and itinerary. Apart from variables and constants we have used constructed terms or structures. A structure is a collection of terms and corresponds to a structural relation between the terms. We express a structure by a constructor and one or several arguments that are terms. We may denote a pair, for instance, by the constructor Pair and the two constants A and 5 as the two arguments: Pair(A, 5).
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman

Round 4. Databases and Expert Systems

Let us make a visit to the feline world where we can make the following world description:
$$ {\text{Feline}}\left( {\text{x}} \right) \leftarrow {\text{Cat}}\left( {\text{x}} \right) $$
$$ {\text{Feline}}\left( {\text{x}} \right) \leftarrow {\text{Big - cat}}\left( {\text{x}} \right) $$
$$ {\text{Feline}}\left( {\text{x}} \right) \leftarrow {\text{Cheetah}}\left( {\text{x}} \right) $$
$$ {\text{Cat}}\left( {\text{x}} \right) \leftarrow {\text{Domestic\_cat}}\left( {\text{x}} \right) $$
$$ {\text{Cat}}\left( {\text{x}} \right) \leftarrow {\text{Wildcat}}\left( {\text{x}} \right) $$
$$ {\text{Big - cat}}\left( {\text{x}} \right)\, \leftarrow \,{\text{Lion}}\left( {\text{x}} \right) $$
$$ {\text{Big - cat}}\left( {\text{x}} \right)\, \leftarrow \,{\text{Tiger}}\left( {\text{x}} \right) $$
$$ {\text{Cheetah}}\left( {\text{x}} \right)\, \leftarrow \,{\text{Hunting\_leopard}}\left( {\text{x}} \right) $$
$$ {\text{Hunting\_leopard}}\left( {{\text{Juba}}} \right)\, \leftarrow $$
$$ {\text{Tiger}}\left( {{\text{Shere - Khan}}} \right)\, \leftarrow $$
$$ {\text{Tiger}}\left( {{\text{Amur}}} \right)\, \leftarrow $$
$$ {\text{Lion}}\left( {{\text{Leona}}} \right)\, \leftarrow $$
$$ {\text{Domestic\_cat}}\left( {{\text{Tom}}} \right)\, \leftarrow $$
The statements (130) – (142) form an open world. It is possible that not all information is included in our description. We do not know, for instance, if only the relations Cat, Big_cat, and Cheetah together make up Feline. There might be more groups belonging to the felines but not included in our world.
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman

Round 5. Program Methodology

We have seen that programs in Horn form can be written in a simple and declarative way. Prolog programs without extralogical constructions have a direct connection to formulas in first-order predicate logic.
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman

Round 6. Efficient Computation

A definition may be expressed so that there are alternative evaluation possibilities reached by backtracking. We can sometimes conclude in advance that an alternative evaluation will not succeed. If we can control the search so that these fruitless alternatives are never tried, we will achieve a more efficient evaluation.
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman

Round 7. Input and Output

So far we have used the arguments in a question to give input to programs and to get output from programs. But we can also use built-in predicates for controlling the input and output of programs. In this way we can construct our own interface with the program.
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman

Round 8. Prolog Implementations

D.H.D. Warren, L.M. Pereira, and F.C.N. Pereira developed an implementation of Prolog1 at the Department of Artificial Intelligence at the University of Edinburgh in 1977. This implementation is for the DEC-10 under the Tops-10 and Tops-20 operating systems. The Prolog system consists of an interpreter and a compiler, both written in Prolog to a large extent.
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman

Round 9. Sparringpartner

Without Abstract
Anna-Lena Johansson, Agneta Eriksson-Granskog, Anneli Edman


Weitere Informationen