Wt 7 Pilftti"W

✓ •n cnwrzt "rx+.waa r t. a

Iv

Pro log
programming
for artificial
intelligence
Third edition
 Pro log
INTERNATIONA L CO MPUTER SCIENCE SERIES

Consulting Editor
A.D. McGettrick University of Strathclyde

programming
Concurrent Systems: An Integrated Approach to Operating Systems, Database and
Distributed Systems (2nd edn) Bacon, J.
Programming Language Essentials Bal, H.E. and Grune, D.
Programming in Ada 95 Barnes, J.
Java Gently (3rd edn) Bishop, J.
for a rt if i c i a I
I
Java Gently for Engineers and Scientists Bishop, J. and Bishop, N.
Software Design Budgen, D.

intelligence
Concurrent Programming Burns, A. and Davies, G.

I
Database Systems: A Practical Approach to Design Implementation and Management
Connolly, T. and Begg, C.
Distributed Systems: Concepts and Design (2nd edn) Coulouris, G., Dollimore, J. and
Kindberg, T. Third edition
Fortran 90 Programming Ellis, T.M.R., Phillips, U?. and Lahey, T.M.
Program Verification Francez, N.
Introduction to Programming using SML Hansen, M. and Rische/, H. IVAN BRATKO
Parallel Processing: The Transputer and its Applications Hull, M.E.C., Crookes, D. and
Sweeney, P.J. Faculty of Computer and Information Science,
Introductory Logic and Sets for Computer Scientists (2nd edn) Nissanke, N. lJubl1ana University
and
Human-Computer Interaction Preece, J. et al.
J. Stefan Institute
Algorithms - A Functional Programming Approach Rabhi, F.A.
Foundations of Computing: System Development with Set Theory and Logic
Scheurer, T.
Java from the Beginning Skansholm, J.
Ada from the Beginning (2nd edn) Skansholm, J.
Object-Oriented Programming in Eiffel (2nd edn) Thomas, P. and Weedon, R.
Miranda: The Craft of Functional Programming Thompson, S.
Haskell: The Craft of Functional Programming (2nd edn) Thompson, S.
Discrete Mathematics for Computer Scientists (2nd edn) Truss, J.K.
Compiler Design Wilhelm, R. and Maurer, D. ...,•. Addison-Wesley
Discover Delphi: Programming Principles Explained Wil/iams, S.
Comparative Programming Languages (2nd edn) Wilson, L.B. and Clark, R.G. An imprint of Pearson Education
Harlow, England - London • New York - Reading, Mass<1chusetts - San Francisco - Toronto - Don Mills, Ontario . Sydney
Software Development with Z Wordsworth, J.B. Tokyo · Singapore - Hong Kong • Seoul • Taipei - Cape Town - Madrid - Mexico City - Amsterdam - Munich - Paris - Milan
Pearson Education Li1nited
Edinburgh Gate
Harlow
Essex CMZO 2JE
England .,
and Associated Companies throughout the world _/) 5119. 0 [ dedicate the third edition of this book
to my mother, the kindest person I know
Visit us on tile World Wide Web at: and to my father, who, during world war II
-...vww.pearsoneduc.corn escaped from a concentration camp by
digging an underground tunnel, which he
First edition 1986 described in his novel, The Telescope
Second edition 1990

This edition C Pearson Education Limited 200l

The right of Ivan Bratko to be identified as author of

this Work has been asserted by him in accordance with
the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced. stored

in a retrieval system, or transmitted in any form or by any means. electronic,
mechanical, photocopying, recording or otherwise, without either the prior
written permission of the publisher or a licence permitting restricted copying
in the United Kingdom issued by tbe Copyright Licensing .-\gencv Ltd,
90 Tottenham Court Road, London W 1 P OLP.

The programs in this book have been included for their instructional value.
They have been tested with care but are not guaranteed for any particular
purpose. The publisher does not offer any warranties or representations
nor does it accept any liabilities with respect to the programs.

ISBN 0201-40375-7

Rritislz Lilmzry Catalogui11g-in-Pu/,iication Data

A catalogue record for this book can be obtained from the British Library

Library o( Congress Catalogi11g-in-Publication Data

Bratko, Ivan 1946-
Prolog programming for artificial intelligence / Ivan Bratko. -- 3rd eel.
p. cm. -- (International computer science series)
Includes bibliographical references and index.
ISBN 0-201-40375-7
l. Artifical intelligence--Data processing. 2. Prolog (Computer program language)
I. Title. II. Series.
Q336.B74 2001
006.3 '0285'5133--clcZl 00-026973

10 9 8 7 6 54 3 2
0504 03 02 01

Typeset by 43 in 9/12.Spt Stone Serif

Printed in Great Britain by Henry Ling Ltd, at the Dorset Press, Dorchester, Dorset
 Contents
Foreword xiii
Preface xvii

PART I The Prolog Language

1 Introduction to Prolog 3
.......... ............ ...............

1.1 Defining relations by facts 3

1.2 Defining relations by rules 8
1.3 Recursive rules 14
1.4 How Prolog answers questions 18
1.5 Declarative and procedural meaning of programs 23

2 Syntax and Meaning of Prolog Programs 25

.•..••..............•......•................ .....•.............

2.1 Data objects 26

2.2 Matching 33
2.3 Declarative meaning of Prolog programs 38
2.4 Procedural meaning 41
2.5 Example: monkey and banana 46
2.6 Order of clauses and goals 50
2.7 The relation between Prolog and logic 57

3 Lists, Operators, Arithmetic 61

. . . . . . . . . . . . . . ........ ........
3.1 Representation of lists 61
3.2 Some operations on lists 64
3.3 Operator notation 74
3.4 Arithmetic 80

4 Using Structures: Example Programs 88

····· ································ ·········· · · · · · ···················· ················
4.1 Retrieving structured information from a database 88

Vii
viii Contents Contents ix

4.2 Doing data abstraction 92 9 Operations on Data Structures 197

. . . . . . . . . . . . . ........
4.3 Simulating a non-deterministic automaton 94 9.1 Sorting lists 197
4.4 Travel agent 98 9.2 Representing sets by binary trees 202
4.5 The eight queens problem 103 9.3 Insertion and deletion in a binary dictionary 208
9.4 Displaying trees 213
5 Controlling Backtracking 114 9.5 Graphs 215
.......•....•••.... .......••.....••.••• •••••.•••..

5.1 Preventing backtracking 114

5.2 Examples using cut 119 10 Advanced Tree Representations 224
5.3 Negation as failure 124
10.1 The 2-3 dictionary 224
5.4 Problems with cut and negation 127
10.2 AVL-tree: an approximately balanced tree 231

6 Input and Output 132

.... ········ . . . . . . . . . . . . . . . . . . . . . . . . . • . . . . . . . . .
6.1 Communication with files 132 PART II Prolog in Artificial Intelligence 237
··············································· · · · ·············································· ··········································
6.2 Processing files of terms 135
6.3 Manipulating characters 140 11 Basic Problem-Solving Strategies 239
6.4 Constructing and decomposing atoms 141
6.5 Reading programs 144 11.1 Introductory concepts and examples 239
11.2 Depth-first search and iterative deepening 244
7 More Built-in Predicates 147 11.3 Breadth-first search 250
······· · · ············ ············ ············

I
11.4 Analysis of basic search techniques 255
7.1 Testing the type of terms 147
7 .2 Constructing and decomposing terms: = . . , functor, arg, name 155
12 Best-First Heuristic Search 260
7.3 Various kinds of equality and comparison 160 ·······························
7.4 Database manipulation 161 12.1 Best-first search 260
7.5 Control facilities 166 12.2 Best-first search applied to the eight puzzle 270
7.6 bagof, setof, and finda/1 167 12.3 Best-first search applied to scheduling 274
12.4 Space-saving techniques for best-first search 280
8 Programming Style and Technique 171
··········································································
13 Problem Decomposition and AND/OR Graphs 292
8.1 General principles of good programming 171 .....................................................................
8.2 How to think about Prolog programs 173 13.1 AND/OR graph representation of problems 292
8.3 Programming style 176 13.2 Examples of AND/OR representation 296
8.4 Debugging 179 13.3 Basic AND/OR search procedures 300
8.5 Improving efficiency 181 13.4 Best-first AND/OR search 305
x Contents Contents xr

14 Constraint Logic Programming 319 18 Machine Learning 442

' •......•••.•......•. . ..•••. ' .............. ······ ................ . ···········•····

14.1 Constraint satisfaction and logic programming 319 18.1 Introduction 442
14.2 CLP over real numbers: CLP(R) 324 18.2 The problem of learning concepts from examples 443
14.3 Scheduling with CLP 329 18.3 Learning relational descriptions: a detailed example 448
14.4 A simulation program with constraints 336 18.4 Learning simple if-then rules 454
14.5 CLP over finite domains: CLP(FD) 341 18.5 Induction of decision trees 462
18.6 Learning from noisy data and tree pruning 469
18.7 Success of learning 476
15 Knowledge Representation and Expert Systems 347
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ······················· · · · · · · · · · · · · · · · · · · · · · · ··· · ·· ·· ·· ·
15.1 Functions and structure of an expert system 347 19 Inductive Logic Programming 484
. . . . . . . . . . . . . . . . . · · · · · . . • . . . . . • " .. · · · · ·
15.2 Representing knowledge with if-then rules 349 19.1 Introduction 484
15.3 Forward and backward chaining in rule-based systems 352 19.2 Constructing Prolog programs from examples 487
15.4 Generating explanation 358 19.3 Program HYPER 500
15.5 Introducing uncertainty 360
15.6 Belief networks 363 20 Qualitative Reasoning 520
15.7 Semantic networks and frames 372
20.1 Common sense, qualitative reasoning and naive physics 520
20.2 Qualitative reasoning about static systems 525
16 An Expert System Shell 383 20.3 Qualitative reasoning about dynamic systems 529
· · · · · ·· · ········ ················ · · · · · · · · · · · · · · · · · · · · · · · · · · ······
20.4 A qualitative simulation program 536
16.1 Knowledge representation format 383
20.5 Discussion of the qualitative simulation program 547
16.2 Designing the inference engine 388
16.3 Implementation 392
21 Language Processing with Grammar Rules 555
16.4 Concluding remarks 410 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ····················
21.1 Grammar rules in Prolog 555
21.2 Handling meaning 563
17 Planning 413 21.3 Defining the meaning of natural language 568
· · ·· · · · · · · · · · · · · · · · · · · · · · · · · ·
17.1 Representing actions 413
22 Game Playing 581
17.2 Deriving plans by means-ends analysis 418 · · · · · · · · · · · · · · · · · · · · · · · · · · ············· ················
17.3 Protecting goals 422 22.1 Two-person, perfect-information games 581
17.4 Procedural aspects and breadth-first regime 424 22.2 The minimax principle 583
17.5 Goal regression 427 22.3 The alpha-beta algorithm: an efficient implementation of
17.6 Combining means-ends planning with best-first heuristic 430 minimax 586
17.7 Uninstantiated actions and partial-order planning 434 22.4 Minimax-based programs: refinements and limitations 590
 , '!!lfl.."'' ·" ·�::":a·er,"�J.�J.tt'&.���.:m-��r��;t'Z�!tt?.t"!f!'!".�-it:sfatt��"l"1xr:i:il"'o::·y

xii Contents
!
I

22.5 Pattern knowledge and the mechanism of 'advice' 592

1
22.6 A chess endgame program in Advice Language O 596
From Patrick Winston s Foreword
23 Meta-Programming 612
23.1 Meta-programs and meta-interpreters 612
to the Second Edition
23.2 Prolog meta-interpreters 613
23.3 Explanation-based generalization 618
I can never forget my excitement when I saw my ftrst Prolog-style program in action.
23.4 Object-oriented programming 624
It was part of Terry Winograd's famous Shrdlu system, whose blocks-world problem
23.5 Pattern-directed programming 631 solver arranged for a simulated robot arm to move blocks around a screen, solving
23.6 A simple theorem prover as a pattern-directed program 638 intricate problems in respome to human-specified goals.
Winograd's blocks-world problem solver was written in Microplanner, a language
which we now recognize as a sort of Prolog. Nevertheless, in spite of the defects of
Appendix A: Some Differences Between Prolog Implementations 647 Microplanner, the blocks-world problem solver was organiud explicitly around
goals, because a Prolog-style language encourages programmers to think in terms of
goals. The goal-oriented procedures for grasping, clearing, getting rid of, moving,
Appendix B: Some Frequently Used Predicates 649
and ungrasping made it possible for a clear, tramparent, concise program to seem
amazingly intelligent.
Solutions to Selected Exercises 652 Winograd's blocks-world problem solver permanently ct1anged the way l think
about programs. ! even rewrote the blocks-world problem solver in Lisp for my Lisp
textbook because that program unalterably impressed me with the power of the
Index 671 goal-oriented philosophy of programming and the fun of writing goal-oriented
programs.
But learning about goal-oriented programming through Lisp programs is like
reading Shakespeare in a language other than English. Some of the beauty comes
through, but not as powerfully as in the original. Similarly, the best way to learn
about goal-oriented programming is to read and write goal-oriented programs in
Prolog, for goal-oriented programming is what Prolog is all about.
In broader terms, the evolution of computer languages is an evolution away from
low-level languages, in which the programmer speciftes how something is to be
clone, toward high-level languages, in which the programmer speciftes simply what
is to be done. With the development of Fortran, for example, programmers were no
longer forced to speak to the computer in the procrustian low-level language of
addresses and registers. Instead, Fortran programmers could speak in their own
language, or nearly so, using a notation that made only moderate concessions to the
one-dimensional, SO-column world.
Fortran and nearly all other languages are still how-type languages, however. In
my view, modem Lisp is the champion of these languages, for Lisp in its Common
Lisp form is enormously expressive, but how to do something is still what the Lisp
programmer is allowed to be expressive about. Prolog, on the other hand, is a
language that clearly breaks away from the how-type languages, encouraging the

xiii
xiv Foreword Foreword xv

programmer to dnuiiJc si tuatiorrs and problems, not the deta iled means by which precedent knowledge, the transition from novice to skilled programmer is already
the problems arc to be solved. under way.
Consequently, ,in introduction to Prolog is important for all students of Of course, a beneficial side effect of good programming examples is that they
Computer Scicr1cc, for thc:rc is no better way to see wllat the notion of what-type expose a bit of interesting science as well as a lot about programming itself. The
programming h ,ill ;ibr,ut. science behind the examples in this book is Artificial Intelligence. The reader lea rns
In particula r, the chapters of this book clearly ill u strate the difference between about such problem-solving ideas as problem reduction, forward and backward
how-type and what-typ(' thinking. In the first chapter, for example, the difference is chaining, 'how' and 'why' questioning, and various search techniques.
illustrated thro ugh prr,hkms dealing with family relations. The Prolog programmer fn fact, one of the great features of Prolog is that it is simple enough for students
straightforwardly dv,crd>es the grandfather concept in explicit, natural terms: a in introductory Artificial Intelligence subjects to learn to use immediately. I expect
grandfather is a Lit lier of a parent. Here is the Prolog notation: that many instructors will use this book as pa rt of their artificial intelligence subjects
grandfather( X, /) :- father( X, ), paren so that their students can see abstract ideas immediately reduced to concrete,
Y t( Y, Z).
motivating form.
Once Prolog know, wh,:t a grandfather is, it is easy to ask a question: who are Among l'rolog texts, I -expect this book to be particularly popular, not only
Patrick's gran dL11 lil'r\ for example. Here again is the Prolog notation, along with a because of its examples, but also because of a n umber of other fea tures:
typical answer: • Careful summaries appea r throughout.
?- grandfather( X, p.>trkk). • N umerous exercises reinforce all concepts.
X = jarnes; • Structure selectors introduce the notion of da ta abstraction.
X = earl • Explicit discussions of programming style and techniq ue occupy an entire
chapter.
It is Prolog's joi, tu figure out how to solve the problem by combing through a
database of known lather and parent relations. The programmer specifies only what • There is honest attention to the problems to be fa ced in Prolog programming, as
is known and wil;11 q11estion is to be solved. The programmer is more concerned well as the joys.
with knowledge· ,111d il'ss concerned with algorithms that exploit the knowledge. Features like this make this a well done, enjoyable. and instructive book.
Given tha t it i, i111port;1nt to learn Prolog, the next question is how. 1 believe that I keep the frrst edition of this textbook in my libra ry on the outstanding­
learning a progra1111n ing language is like learning a natural language in many ways. textbooks shelf, programming languages section, for as a textbook it exhibited all
For example, a rl'fertnce m a nual is helpful in learning a programming langu age, just the strengths that set the outstanding textbooks apart from the others, including
as a dictiona y
r i, hl'ipful in learning a natural language. But no one learns a natural clear and direct writing, copious examples, careful summaries, and numerous
language with 011ly ,1 dic tionary, for the words are only part of what must be learned. exercises. And as a programming la nguage textbook, I especially liked its attention
The student of ,1 11;1tur;l1 langua ge must learn the conventions that govern how the to data abstraction, emphasis on programming style, and honest treatment of
words are put lq,ally together, and later, the student should learn the art of those Prolog's problems as well as Prolog's advantages.
who put the words together with style.
Similarly, no orw learns a programming language from only a reference manual,
for a reference n1,11111;J! says little or nothing about the way the primitives of the
langua ge are put to use by those who use the language well. For this, a textbook is
required, and the bes t textbooks offer copious examples, for good examples are
distilled experie11n'. ,ind it is principally through experience that we learn.
In this book, the 1·1rs t example on the first page, and the remaining pages
is
constitute an exan1plc cornu copia, pouring forth Prolog programs written by a
passionate Prolog programmer who is dedicated to the Prolog point of view. By
carefully studying these examples, the reader acquires not only the mechanics of the
language, but ;il .\o a personal collection of precedents, ready to be taken apart,
adap ted, and re,tsSt.'mble
d together into new programs. With this acquisition of

;;;:S.��->>":'
-:.i'f..qB• ,?:,:.J;;,.'.'f, .;,,;::;r.::::;,�,t;-:,_,,11t;,-sJ¥�,J(,;.;'..;¥.(.�����ff'"f?-tR"._Je;��:'"',: �-�- -><-•·-- ,...-,.
Preface
Prolog

Prolog is a programming language centred around a small set of basic mechanisms,

including pattern matching, tree-based data structuring and automatic back­
tracking. This small set constitutes a surprisingly powerful and flexible
programming framework. Prolog is especially well suited for problems that involve
objects - in particular, structured objects - and relations between them. For
example, it is an easy exercise in Prolog to express spatial relationships between
objects, such as the blue sphere is behind the green one. ft is also easy to state a more
general rule: if object Xis closer to the observer than object Y, and Y is closer than Z,
then Xmust be closer than Z. Prolog can now reason about the spatial relationships
and their consistency with respect to tr,e general rule. Features like this make Prolog
a powerful language for artificial intelligence (Al) and non-numerical programming
in general. There are well-known examples of symbolic computation whose
implementation in other standard languages took tens of pages of indigestible code.
When the same algorithms were implemented in Prolog, the result was a crystal­
clear program easily fitting on one page.

Development of Prolog
Prolog stands for programming in logic- an idea that emerged in the early 1970s to use
logic as a programming language. The early developers of this idea included Robert
Kowalski at Edinburgh (on the theoretical side), Maarten van Emden at Edinburgh
(experimental demonstration) and Alain Colmerauer at Marseilles (implementa­
tion). David D.I--l. Warren's efficient implementation at Edinburgh in the mid-1970s
greatly contributed to the popularity of Prolog. A more recent development is
constraint logic programming (CLP), usually implemented as part of a Prolog system.
CLP extends Prolog with constraint processing, which has proved in practice to be
an exceptionally flexible tool for problems like scheduling and logistic planning. In
1996 the official ISO standard for Prolog was published.

Historical controversies about Prolog

There are some controversial views that historically accompanied Prolog. Prolog fast
gained popularity in Europe as a practical programming tool. In Japan, Prolog was
placed at the centre of the development of the fifth-generation computers. On the

xvii
xviii Preface Preface xix

other hand, in the United States l'rolog was generally accepted with some delay, due Differences between the second and third edition
to several historical factors. One of these was an early ,\merican experience with the
All the material has been revised and updated. There are new chapters on:
Microplanner language, also akin to the idea of logic programming, but inefficiently
implemented. Some reservations also came in reaction to the early 'orthodox • constraint logic programming (CLP);
school' of logic programming, which insisted on the use of pure logic that should • inductive logic programming;
not be marred by adding practical facilities not related to logic. This led to some • qualitative reasoning.
widespread misunderstandings about Prolog in the past. For example, some believed
that only backward chaining reasoning can be programmed in Prolog. The truth is Other major changes are:
that Prolog is a general programming language and any algorithm can be
• addition of belief networks (Bayes networks) in the chapter on knowledge
programmed in it. The impractical 'orthodox school's' position was modified
by Prolog practitioners who adopted a more pragmatic view, benefiting from representation and expert systems;
combining the new, declarative approach with the traditional, procedural one. • addition of memory-efficient programs for best-first search (!DA*, RBFS) in the
chapter on heuristic search;

Learning Prolog
• major updates in the chapter on machine learning;
• additional techniques for improving program efficiency in the chapter on
Since l'rolog has its roots in mathematical logic it is often introduced through logic. programming style and technique.
However, such a mathematically intensive introduction is not very useful if the aim
is to teach Prolog as a practical programming tool. Therefore this book is not Throughout, more attention is paid to the differences between Prolog implementa­
concerned with the mathematical aspects, but concentrates on the art of making the tions with specific references to the Prolog standard when appropriate (see also
few basic mechanisms of Prolog solve interesting problems. Whereas conventional Appendix A).
languages are procedurally oriented, Prolog introduces the descriptive, or declarative,
view. This greatly alters the way of thinking about problems and makes learning to Audience for the book
program in Prolog an exciting intellectual challenge. \-[any believe that every
student of computer science should learn something about Prolog at some point This book is for students of Prolog and Al. It can be used in a Prolog course or in an
because Prolog enforces a different problem-solving paradigm complementary to Al course in which the principles of AI are brought to life through Prolog. The reader
other programming languages. is assumed to have a basic general knowledge of computers, but no knowledge of AI
is necessary. No particular programming experience is required; in fact, plentiful
experience and devotion to conventional procedural programming - for example in
Contents of the book C or Pascal - might even be an impediment to the fresh way of thinking Prolog
Part l of the book introduces the Prolog language and shows how Prolog programs requires.
are developed. Techniques to handle important data structures, such as trees and
graphs, are also included because of their general importance. In Part II, Prolog is The book uses standard syntax
applied to a number of areas of Al, including problem solving and heuristic search,
programming with constraints, knowledge representation and expert systems, Among several Prolog dialects, the Edinburgh syntax, also known as DEC-10 syntax,
planning, machine learning, qualitative reasoning, language processing and game is the most widespread, and is the basis of the ISO standard for Prolog. It is also used
playing. Al techniques are introduced and developed in depth towards their in this book. For compatibility with the various Prolog implementations, this book
implementation in Prolog, resulting in complete programs. These can be used as only uses a relatively small subset of the built-in features that are shared by many
building blocks for sophisticated applications. The concluding chapter, on meta­ Prologs.
programming, shows bow Prolog can be used to implement other languages and
programming paradigms, including object-oriented programming, pattern-directed How to read the book
programming and writing interpreters for Prolog in Prolog. Throughout, the
emphasis is on the clarity of programs; efficiency tricks that rely on implementa­ In Part I, the natural reading order corresponds to the order in the book. However,
tion-dependent features are avoided. the part of Section 2.4 that describes the procedural meaning of Prolog in a more

£_t;;f:;
:
-,,;:-.-: t-,,(,t,·,:5;:;:-��;:;:;,};fii;{f;j:-;:4t�,!i�;i!f:Y:S-';'.;cr..f.,♦¥'%-l�f����/f����:;.:;ilt�--:.'
 - -,;:;q;:;,ii.!&!iia a&� ,s,;;;;: & . ;;;;:;::::

xx Preface
Preface XXI

t the Prolog development team at Edinburgh, for their programming advice and
numerous discussions. The book greatly benefited from comments and suggestions
2
to the previous editions by Andrew 1vlcGettrick and Patrick H. Winston. Other
t people who read parts of the manuscript and contributed significant comments
3 include: Damjan Bojadziev, Rod Bristow, Peter Clark, Frans Coenen, David C.
t Dodson, Saso Dzeroski, Bogdan Filipic, Wan Fokkink, Matjaz Garns, Peter G.
4 (Selectively) Greenfield, "tv!arko Grobelnik, Chris Hinde, Igor Kononenko, Matevz Kovacic,
t Eduardo Morales, Igor Mozetic, Timothy B. Niblett, Dusan Peterc, Uros Pompe,
Robert Rodosek, Agata Saje, Claude Sammut, Cem Say, Ashwin Srinivasan, Dorian
5

t Sue, Peter Tancig, Tanja Urbancic, Mark Wallace, William Walley, Simon Weilguny,
Blaz Zupan and Darko Zupanic. Special thanks to Cem Say for testing many
6
t programs and his gift of finding hidden errors. Several readers helped by pointing
out errors in the previous editions, most notably G. Oulsnam and Iztok Tvrdy. I
7
would also like to thank Karen Mosman, Julie Knight and Karen Sutherland of
t Pearson Education for their work in the process of making this book. Simon
8 � 9 � IO Plumtree and Debra Myson-Etherington provided much support in the previous
t editions. Most of the artwork was clone by Darko Simersek. Finally, this book would
ll not be possible without the stimulating creativity of the international logic

t
12.l
t
14
t
I5
t
17
i
18 20
t
21
t
22
t
23
programming community.
The publisher wishes to thank Plenum Publishing Corporation for their permis­
sion to reproduce material similar to that in Chapter 10 of Human and Maclzine
.....�
12.2 ·I 13
t t Problem Solving (1989), K. Gilhooly (eel).
16 19
Ivan Bratko
Figure P.1 Precedence constraints among the chapters. January 2000
formalized way can be skipped. Chapter 4 presents programming examples that can
be rl':id (or skipped) selectively. Chapter 10 on advanced tree representations can be
skipped.
Par t II allows more flexible reading strategies as most of the chapters are intended
to bt· mutually independent. However, some topics will still naturally be covered
beforl' others, such as basic search strategies (Chapter 11). Figure P.l summarizes the
natural precedence constraints among the chapters.

Program code and course materials

Sour,·e code for all the programs in the book and relevant course materials are
accessible fro;:n the companion web site (,vww-.booksites.net/bratko).

Acknowledgements
Dorn1ld Michie was responsible for first inducing my interest in Prolog. I am grateful
to Liwrence Byrd, Fernando Pereira and David... H.D. Warren, once members of
part

The Prolog Language

Introduction to Prolog 3

2 Syntax and Meaning of Prolog Programs 25

3 Lists, Operators, Arithmetic 61
4 Using Structures: Example Programs 88
5 Controlling Backtracking 114
6 Input and Output 132
7 More Built-in predicates 147
8 Programming Style and Technique 171
9 Operations on Data Structures 197

10 Advanced Tree Representations 224

chapter 1

Introduction to Prolog
1.1 Defining relations by facts 3
1.2 Defining relations by rules 8
1.3 Recursive rules 14
1.4 How Prolog answers questions 18
1.5 Declarative and procedural meaning of programs 23

This chapter reviews basic mechanisms of Prolog through an example program.

Although the treatment is largely informal many important concepts are introduced
such as: Prolog clauses, facts, rules and procedures. Prolog's built-in backtracking
mechanism and the distinction between declarative and procedural meanings of a
program are discussed.

1.1 Defining relations by facts

Prolog is a programming language for symbolic, non-numeric computation. It is
specially well suited for solving problems that involve objects and relations between
objects. Figure 1.1 shows an example: a family relation. The fact that Torn is a parent
of Bob can be written in Prolog as:
parent( tom, bob).
Here we choose parent as the name of a relation; tom and bob are its arguments. For
reasons that will become clear later we write names like tom with an initial lower­
case letter. The whole family tree of Figure 1.1 is defined by the following Prolog
program:
parent( pam, bob).
parent( tom, bob).

3
4 Introduction to Prolog Defining relations by facts 5

because the program does not mention anything about Liz being a parent of Pat. It
also answers 'no' to the question:
?- parent( tom, ben).
because the program has not even heard of the name Ben.
More interesting questions can also be asked. For example: Who is Liz's parent?
?- parent( X, liz).
Prolog's answer will not be just 'yes' or 'no' this time. Prolog will tell us what is the

8
value of X such that the above statement is true. So the answer is:
X = tom

The question Who are Bob's children? can be communicated to Prolog as:
?- parent( bob, X).

This time there is more than just one possible answer. Prolog first answers with one
solution:
Figure 1.1 A family tree. X = ann
We may now request another solution (by typing a semicolon), and Prolog will find:
parent( tom, liz).
parent( bob, ann). X =pat
parent( bob, pat).
If we request more solutions again, Prolog will answer 'no' because all the solutions
parent( pat, jim).
have been exhausted.
This program consists of six clauses. Each of these clauses declares one fact about the Our program can be asked an even broader question: Who is a parent of whom'
parent relation. For example, parent( tom, bob) is a particular instance of the parent Another formulation of this question is:
relation. Such an instance is also called a relationship. ln general, a relation is defined Find X and Y such that X is a parent of Y.
as the set of all its instances.
When this program has been communicated to the Prolog system, Prolog can be This is expressed in Prolog by:
posed some questions about the parent relation. For example: Is Bob a parent of Pat? ?- parent( X, Y).
This question can be communicated to the Prolog system by typing into the
terminal: Prolog now finds all the parent-child pairs one after another. The solutions will be
displayed one at a time as long as we tell Prolog we want more solutions, until all the
?- parent( bob, pat).
solutions have been found. The answers are output as:
Having found this as an asserted fact in the program, Prolog will answer: X=pam
Y = bob;
yes
X= tom
A further query can be: Y = bob;
?- parent( liz, pat). X= tom
Y = liz;
Prolog answers:

no We can stop the stream of solutions by typing a return instead of a semicolon.

6 Introduction to Prolog Defining relations by facts 7

parent
0t \ X == bob
Y =pat
Yet another question could be: Do Ann and Pat have a common parent? This can be
) grandparent expressed again in two steps:
�
paren

03!
/ (l) Who is a parent, X, of Ann?
(2) Is (this same) X a parent of Pat?
The corresponding question to Prolog is then:
Figure 1.2 The grandparent relation expressed as a composition of two parent relations.
?- parent( X, arm), parent( X, pat).

Our example program can be asked still more complicated questions like: Who is The answer is:
a grandparent of Jim? As our program does not directly know the grandparent X = bob
relation this query has to be broken down into two steps, as illustrated by Figure 1.2.
Our example program has helped to illustrate some important points:
(1) Who is a parent of Jim? Assume that this is some Y.
• It is easy in Prolog to define a relation, such as the parent relation, by stating the
(2) Who is a parent of Y'/ Assume that this is some X.
n-tuples of objects that satisfy the relation.
Such a composed query is written in Prolog as a sequence of two simple ones: • The user can easily query the Prolog system about relations defined in the
?- parent( Y, jirn), parent( X, Y). program.
• A Prolog program consists of clauses. Each clause terminates with a full stop.
The answer will be:
• The arguments of relations can (among other things) be: concrete objects, or
X =bob constants (such as tom and arm), or general objects such as X and Y. Objects of
Y =pat
the first kind in our program are called atoms. Objects of the second kind are
Our composed query can be read: Find such X and Y that satisfy the following two called variables.
requirements: • Questions to the system consist of one or more goals. A sequence of goals, such
parent( Y, jirn) and parent( X, Y) as:

If we change the order of the two requirements the logical meaning remains the parent( X, ann), parent( X, pat)
same: means the conjunction of the goals:
parent( X, Y) and parent( Y, jirn)
X is a parent of Ann, and
We can indeed do this in our Prolog program, and the query: X is a parent of Pat.
?- parent( X, Y), parent( Y, jim). The word 'goals' is used because Prolog accepts questions as goals that are to be
satisfied.
will produce the same result.
In a similar way we can ask: Who are Tom's grandchildren? • An answer to a question can be either positive or negative, depending on
whether the corresponding goal can be satisfied or not. In the case of a positive
?- parent( tom, X), parent( X, Y). answer we say that the corresponding goal was satisfiable and that the goal
Prolog's answers are: succeeded. Otherwise the goal was unsatisfiable and it failed.
• If several answers satisfy the question then Prolog will find as many of them as
X =bob
Y =ann; desired by the user.
8 Introduction to Prolog Defining relations by rules 9

Exercises parent relation; that is, by simply providing a list of simple facts about the offspring
relation, each fact mentioning one pair of people such that one is an offspring of the
1.1 Assuming the parent relation as defined in this section (see Figure 1.1), what will be other. For example:
Prolog's answers to the following questions? offspring( liz, torn).
(a) ? parent( jim, X). However, the offspring relation can be defined much more elegantly by making use
(b) ?- parent( X, jim). of the fact that it is the inverse of parent, and that parent has already been defined.
(c) ? parent( pam, X), parent( X, pat). This alternative way can be based on the following logical statement:
(d) ?- parent( pam, X), parent( X, Y), parent( Y, jim). For all Xand Y,
Y is an offspring of Xif
1.2 Formulate in Prolog the following questions about the parent relation: Xis a parent of Y.
(a) Who is Pat's parent? This formulation is already close to the formalism of Prolog. The corresponding
(b) Does Liz have a child? Prolog clause which has the same meaning is:
(c) Who is Pat's grandparent? offspring( Y, X) :- parent( X, Y).
This clause can also be read as:
For all Xand Y,
1.2 if Xis a parent of Y then
Y is an offspring of X.
Our example program can be easily extended in many interesting ways. Let us first
add the information on the sex of the people that occur in the parent relation. This Prolog clauses such as:
can be done by simply adding the following facts to our program: offspring( Y, X) :- parent( X, Y).
female( pam). are called rules. There is an important difference between facts and rules. A fact like:
male( torn).
male( bob). parent( tom, liz).
female( liz).
female( pat). is something that is always, unconditionally, true. On the other hand, rules specify
female( a1111). things that are true if some condition is satisfied. Therefore we say that rules have:
rnale(jim). • a condition part (the right-hand side of the rule) and
The relations introduced here are male and female. These relations are unary (or one­ • a conclusion part (the left-hand side of the rule).
place) relations. A binary relation like parent defines a relation between pairs of
objects; on the other hand, unary relations can be used to declare simple yes/no The conclusion part is also called the hee1d of a clause and the condition part the body
of a clause. For example:
properties of objects. The first unary clause above can be react: Pam is a female. We
could convey the same information declared in the two unary relations with one offspring( Y, X) :- parent( X, Y).
binary relation, sex, instead. An alternative piece of program would then be: � �
head body
sex( pam, feminine).
sex( tom, masculine). If the condition parent( X, Y) is true then a logical consequence of this is
sex( bob, masculine). offspring( Y, X).
How rules are actually used by Prolog is illustrated by the following example. Let
As our next extension to the program let us introduce the offspring relation as us ask our program whether Liz is an offspring of Tom:
the inverse of the parent relation. We could define offspring in a similar way as the ?- offspring( liz, tom).
10 Introduction to Prolog

There is no fact about offsprings in the program, therefore the only way to consider
this question is to apply the rule about offsprings. The rnle is general in the sense
that it is applicable to any objects X and Y; therefore it can also be applied to such
particular objects as liz and tom. To apply the rule to liz and tom, Y has to be '"""�)J ""''''"'
f
parent
emale

'; mother
Defining relations by rules

9
0i \
parent
1
11

'
G grandparent
I
substituted with liz, and X with tom. We say that the variables X and Y become
instantiated to: parent /
X=tom and Y=liz

After the instantiation we have obtained a special case of our general rule. The
special case is: Figure 1.3 Definition graphs for the relations offspring, mother and grandparent in terms
of other relations.
offspring( liz, tom) :- parent( tom. liz).

The condition part has become:

with the name of the relation. The relations that are being defined are represented
parent( tom, liz) by dashed arcs. So each diagram should be understood as follows: if the relations
shown by solid arcs hold, then the relation shown by a clashed arc also holds.
Now Prolog tries to find out whether the condition part is true. So the initial goal: The grandparent relation can be, according to Figure 1.3, immediately written in
offspring( liz, tom) Prolog as:
grandparent( X, Z) :- parent( X, Y), parent( Y, Z).
has been replaced with the subgoal:
At this point it will be useful to make a comment on the layout of our programs.
parent( tom, liz)
Prolog gives us almost full freedom in choosing the layout of the program. So we can
This (new) goal happens to be trivial as it can be found as a fact in our program. This insert spaces and new lines as it best suits our taste. ln general we want to make our
means that the conclusion part of the rule is also true, ancl Prolog will answer the programs look nice and tidy, ancl, above all, easy to read. To this end we will often
question with yes. choose to write the head of a clause and each goal of the body on a separate line.
Let us now acid more family relations to our example program. The specification When doing this, we will indent goals in order to make the difference between the
of the mother relation can be based on the following logical statement: head and the goals more visible. For example, the grandparent rule would be,
according to this convention, written as follows:
For all Xand Y,
Xis the mother of Y if grandparent( X, Z)
parent( X, Y),
Xis a parent of Y and
parent( Y, Z).
Xis a female.
Figure 1.4 illustrates the sister relation:
This is translated into Prolog as the following rule:
mother( X, Y) :- parent( X, Y), female( X).

A comma between two conditions indicates the conjunction of the conditions,

z
meaning that both conditions have to be true.
parent
Relations such as parent, offspring ancl mother can be illustrated by diagrams such
as those in Figure 1.3. These diagrams conform to the following conventions. Nodes
in the graphs correspond to objects - that is, arguments of relations. Arcs between female ( X
nodes correspond to binary (or two-place) relations. The arcs are oriented so as to sister
point from the first argument of the relation to the second argument. Unary
relations are indicated in the diagrams by simply marking the corresponding objects Figure 1.4 Defining the sister relation.
12 Introduction to Prolog Defining relations by rules 13

For any X and Y, Some important points of this section are:

X is a sister of Y if
• Prolog programs can be extended by simply adding new clauses.
(1) both X and Y have the same parent, and
(2) X is a female. • Prolog clauses are of three types: facts, rules and questions.
The graph in Figure 1.4 can be translated into Prolog as: • Facts declare things that are always, unconditionally true.
sister( X, Y) :­ • Rules declare things that are true depending on a given condition.
parent( Z, X), • By means of questions the user can ask the program what things are true.
parent( Z, Y),
female( X). • Prolog clauses consist of the head and the body. The body is a list of goals
separated by commas. Commas are understood as conjunctions.
Notice the way in which the requirement 'both X and Y have the same parent' has
been expressed. The following logical formulation was used: some Z must be a • Facts are clauses that have a head and the empty body. Questions only have the
parent of X, and this same Z must be a parent of Y..>..n alternative, but less elegant body. Rules have the head and the (non-empty) body.
way would be to say: Zl is a parent of X, and Z2 is a parent of Y, and Zl is equal to Z2. • In the course of computation, a variable can be substituted by another object.
We can now ask: We say that a variable becomes instantiated.
?- sister( arrn, pat). • Variables are assumed to be universally quantified and are read as 'for all'.
The answer will be 'yes', as expected (see Figure 1.1). Therefore we might conclude Alternative readings are, however, possible for variables that appear only in the
that the sister relation, as defined, works correctly. There is, however, a rather subtle body. For example:
flaw in our program, which is revealed if we ask the question Who is Pat's sister1: hasachild( X) :- parent( X, Y).
?- sister( X, pat).
can be read in two ways:
Prolog will find two answers, one of which may come as a surprise:
(a) For al! X and Y,
X = ann;
if X ls a parent of Y then
X = pat X has a child.
So, Pat is a sister to herself?! This is probably not what we had in mind when (b) For all X,
defining the sister relation. However, according to our rule about sisters Prolog's X has a child if
answer is perfectly logical. Our rule about sisters does not mention that X and Y there is some Y such that X is a parent of Y.
must not be the same if X is to be a sister of Y. As this is not required Prolog
(rightfully) assumes that X and Y can be the same, and will as a consequence find
that any female who has a parent is a sister of herself. Exercises
To correct our rule about sisters we have to add that X and Y must be different. We
will see in later chapters how this can be done in several ways, but for the moment 1 .3 Translate the following statements into Prolog rules:
we will assume that a relation different is already known to Prolog, and that:
different( X, Y) (a) Everybody who has a child is happy (introduce a one-argument relation happy).
(b) For all X, if X has a child who has a sister then X has two children (introduce
is satisfied if and only if X and Y are not equal. An improved rule for the sister
new relation hastwochildren).
relation can then be:
sister( X, Y) :­ 1.4 Define the relation grandchild using the parent relation. Hint: It will be similar to the
parent( Z, X), grandparent relation (see Figure 1.3).
parent( Z, Y),
female( X), 1.5 Define the relation aunt( X, Y) in terms of the relations parent and sister. As an aid
different( X, Y). you can first draw a diagram in the style of Figure 1.3 for the aunt relation.

--
14 Introduction to Prolog Recursive rules 15

0 0
1.3 Recursive rules
parent
t
0)
\ parent t \
CR
1\ 1\
rr/
Let us add one more relation to our family program, the predecessor relation. This
predeces.sor I

t
relation will be defined in terms of the parent relation. The whole definition can be
expressed with two rules. The first rule will define the direct (immediate) predeces­ parent 1 pmP�) predecessor
sors and the second rule the indirect predecessors. We say that some Xis an indirect
predecessor of some Z if there is a parentship chain of people between X and Z, as (if predecessor

illustrated in Figure 1.5. In our example of Figure 1.1, Tom is a direct predecessor of
Liz and an indirect predecessor of Pat.
The first rule is simple and can be formulated as: ""'"'<lf/
For all X and Z,
Xis a predecessor of Z if
Xis a parent of Z.
ctJ
This is straightforwardly translated into Prolog as: Figure 1.6 Predecessor-successor pairs at various distances.

predecessor( X, Z) predecessor( X, Z)
parent( X, Z). parent( X, Yl),
parent( Yl, Y2),
The second rule, on the other hand, is more complicated because the chain of parent( Y2, Z).
parents may present some problems. One attempt to define indirect predecessors
predecessor( X, Z)
could be as shown in Figure 1.6 ..-'\ccording to this, the predecessor relation would be parent( X, Yl),
defined by a set of clauses as follows: parent( YI, Y2),
parent( Y2, Y3),
predecessor( X, Z) parent( Y3, Z).
parent( X, Z).
predecessor( X, Z)
parent( X, Y), This program is lengthy and, more importantly, it only works to some extent. It
parent( Y, Z). would only discover predecessors to a certain depth in a family tree because the
length of the chain of people between the predecessor and the successor would be

0+ > predecessor
0+ \ limited according to the length of our predecessor clauses.
There is, however, an elegant and correct formulation of the predecessor relation: it

9\
parent parent will be correct in the sense that it will work for predecessors at any depth. The key idea

(a) (if I
is to define the predecessor relation in terms of itself. Figure 1.7 illustrates the idea:
For all X and Z,
parent ) predecessor

'"'"9(D/
Xis a predecessor of Z if
there is a Y such that
(1) Xis a parent of Y and
(2) Y is a predecessor of Z.
(b) A Prolog clause with the above meaning is:
predecessor( X, Z) :-
Figure 1.5 Examples of the predecessor relation: (a) Xis a direct predecessor of Z; parent( X, Y),
(b) X is an indirect predecessor of Z. predecessor( Y, Z).
16 Introduction to Prolog Recursive rules 17

parent
0! \ X = pat;
X=jim
Prolog's answers are, of course, correct and they logically follow from our definition
y) \\ of the predecessor and the parent relation. There is, however, a rather important
I question: How did Prolog actually use the program to find these answers?
\ An informal explanation of how Prolog does this is given in the next section. But
\
I first let us put together all the pieces of our family program, which was extended
I gradually by adding new facts and rules. The final form of the program is shown
1 predecessor
I in Figure 1.8. Looking at Figure 1.8, two further points are in order here: the
predecessor I ( )
I
I
I % Pamis a parent of Bob
I parent(pam, bob).
I parent( tom, bob).

' i/
parent( torn, liz).
parent( bob, ann).

0
parent( bob, pat).
parent( pat , jirn).
female( pam). 0,1, Pamis female
Figure 1.7 Recursive formulation of the predecessor relation. male( torn). 'Yr, Tom is male
male(bob).
We have thus constructed a complete program for the predecessor relation, which female( liz) .
female( ann).
consists of two rules: one for direct predecessors and one for indirect predecessors.
female( pat).
Both rules are rewritten together here: male(jim).
predecessor( X, Z) offspring( Y, X) '¼, Y is an offspring of X if
parent( X, Z). parent( X, Y). % Xis a parent of Y
predecessor( X, Z) mother( X, Y) :­ % X is the mother of Y if
parent( X, Y), parent( X, Y), % Xis a parent of Y and
predecessor( Y, Z). female(X). % Xis female
The key to this formulation was the use of predecessor itself in its definition. Such a grandparent( X, Z) '½,Xis a grandparent of Zif
definition may look surprising in view of the question: When defining something, parent( X, Y), % X is a parent of Y and
parent( Y, Z). % Yis a parent of Z
can we use this same thing that has not yet been completely defined? Such
definitions are, in general, called recursive definitions. Logically, they are perfectly sister( X, Y) :­ % Xis a sister of Y if
correct and understandable, which is also intuitively obvious if we look at Figure 1. 7. parent( Z, X),
parent( Z, Y) , % X and Y have the same parent and
But will the Prolog system be able to use recursive rules? It turns out that Prolog can female( X), % Xis female and
indeed very easily use recursive definitions. Recursive programming is, in fact, one different( X, Y). % X and Y are different
of the fundamental principles of programming in Prolog. It is not possible to solve
predecessor( X, Z) % Rule prl: X is a predecessor of Z
tasks of any significant complexity in Prolog without the use of recursion. parent( X, Z).
Going back to our program, we can ask Prolog: Who are Pam's successors? That is:
predecessor(X, Z) % Rule pr2: X is a predecessor of Z
Who is a person that has Pam as his or her predecessor?
parent( X, Y),
?- predecessor( pam, X). predecessor( Y, Z).
X = bob;
X = ann; Figure 1.8 The family program.
 r

18 Introduction to Prolog How Prolog answers questions 19

first will introduce the term 'procedure', the second will be about comments in variables, Prolog also has to find what are the particular objects (in place of variables)
programs. for which the goals are satisfied. The particular instantiation of variables to these
The program in Figure 1.8 defines several relations - parent, male, female, objects is displayed to the user. lf Prolog cannot demonstrate for some instantiation
predecessor, etc. The predecessor relation, for example, is defined by two clauses. of variables that the goals logically follow from the program, then Prolog's answer to
We say that these two clauses are about the predecessor relation. Sometimes it is the question will be 'no'.
convenient to consider the whole set of clauses about the same relation. Such a set of An appropriate view of the interpretation of a Prolog program in mathematical
clauses is callee! a procedure. terms is then as follows: Prolog accepts facts and rules as a set of axioms, and the
In Figure 1.8, the two rules about the predecessor relation have been distinguished user's question as a conjectured theorem; then it tries to prove this theorem - that is, to
by the names'prl' and'pr2', added as comments to the program. These names will be demonstrate that it can be logically derived from the axioms.
used later as references to these mies. Comments are, in general, ignored by the We will illustrate this view by a classical example. Let the axioms be:
Prolog system. They only serve as a further clarification to the person who reads
All men are fallible.
the program. Comments are distinguished in Prolog from the rest of the program by
being enclosed in special brackets'/,' and',/'. Thus comments in Prolog look like Socrates is a man.
this: A theorem that logically follows from these two axioms is:
/, This is a comment ,/ Socrates is fallible.
Another method, more practical for short comments, uses the percent character'%'. The first axiom above can be rewritten as:
Everything between '%' and the encl of the line is interpreted as a comment:
For all X, if X is a man then X is fallible.
%, This is also a comment
Accordingly, the example can be translated into Prolog as follows:

Exercise fallible( X) :- man( X). '¼i All men are fallible

man( socrates). ryo Socrates is a rr1an
1.6 Consider the following alternative definition of the predecessor relation: ?- fallible( socrates). % Socrates is fallible?
predecessor( X, Z) yes
parent( X, Z).
A more complicated example from the family program of Figure 1.8 is:
predecessor( X, Z)
parent( Y, Z), ?- predecessor( tom, pat).
predecessor( X, Y).
We know that parent( bob, pat) is a fact. Using this fact and rule prl we can conclude
Does this also seem to be a correct definition of predecessors? Can you modify the predecessor( bob, pat). This is a derived fact: it cannot be found explicitly in our
diagram of Figure 1.7 so that it would correspond to this new definition? program, but it can be derived from facts and rules in the program. An inference
step, such as this, can be written in a more compact form as:
parent( bob, pat) => predecessor( bob, pat)
1.4 �?.'!!.P..'.?.l?.�--�-�?.�.�:.?.. g.�.�?.!!.?.0.?........................................................................... This can be read: from parent( bob, pat) it follows that predecessor( bob, pat), by rule
prl. Further, we know that parent( tom, bob) is a fact. Using this fact and the derived
This section gives an informal explanation of how Prolog answers questions. A fact predecessor( bob, pat) we can conclude predecessor( tom, pat), by rule pr2. We
question to Prolog is always a sequence of one or more goals. To answer a question, have thus shown that our goal statement predecessor( tom, pat) is true. This whole
Prolog tries to satisfy all the goals. What does it mean to satisfy a goal? To satisfy a inference process of two steps can be written as:
goal means to demonstrate that the goal is tme, assuming that the relations in
the program are true. In other words, to satisfy a goal means to demonstrate that the parent( bob, pat) => predecessor( bob, pat)
goal logically follows from the facts and rules in the program. If the question contains parent( tom, bob) and predecessor( bob, pat) => predecessor( tom, pat)
20 Introduction to Prolog How Prolog answers questions 21

vVe have thus shown what can be a sequence of steps that satisfy a goal - that is, predecessor( torn, pat)
make it dear that the goal is trne. Let us call this a proof sequence. We have not,
however, shown how the Prolog system actually finds such a proof sequence.
Prolog finds the proof sequence in the inverse order to that which we have just hy rule pr! by rule pr2
used. Instead of starting with simple facts given in the program, Prolog starts with
the goals and, using rules, substitutes the current goals with new goals, until new parent( torn, pat) parent( tom, Y)
predecessor( Y, pat)
goals happen to be simple facts. Given the question:
no
?- predecessor( tom, pat).
Figure 1.10 Execution trace continued from Figure 1 .9.
Prolog will try to satisfy this goal. In order to do so it will try to find a clause in the
program from which the above goal could immediately follow. Obviously, the only
clauses relevant to this encl are prl and pr2. These are the rules about the predecessor
As before, the variables X and Z become instantiated as:
relation. We say that the heads oi these rules match the goal.
The two clauses, prl and pr2, represent two alternative ways for Prolog to proceed. X = tom, Z = pat
Prolog first tries that clause which appears first in the program:
But Y is not instantiated yet. The top goal predecessor( tom, pat) is replaced by two
predecessor( X, Z) :- parent( X, Z.). goals:
Since the goal is predecessor( tom, pat), the variables in the rule must be instantiated parent( tom, Y),
as follows: predecessor( Y, pat)

X = tom, Z = pat This executional step is shown in Figure 1.10, which is an extension to the situation
we had in Figure 1.9.
The original goal predecessor( tom, pat) is then replaced by a new goal: Being now faced with two goals, Prolog tries to satisfy them in the order in which
parent( tom, pat) they are written. The first one is easy as it matches one oi the facts in the program.
The matching forces Y to become instantiated to bob. Thus the first goal has been
This step of using a rule to transform a goal into another goal, as above, is satisfied, and the remaining goal has become:
graphically illustrated in Figure 1.9. There is no clause in the program whose head
matches the goal parent( tom, pat), therefore this goal fails. Now Prolog backtracks predecessor( bob, pat)
to the original goal in order to try an alternative way to derive the top goal To satisfy this goal the rule prl is used again. Note that this (second) application of
predecessor( tom, pat). The rule pr2 is thus tried: the same rule has nothing to do with its previous application. Therefore, Prolog uses
predecessor( X, Z) :­ a new set of variables in the rule each time the rule is applied. To indicate this we
parent( X, Y), shall rename the variables in rule pr 1 for this application as follows:
predecessor( Y, Z). predecessor( X', Z')
parent( X', Z').
predecessor( tom,pat) The head has to match our current goal predecessor( bob, pat). Therefore:
X' = bob, Z' = pat
by rule pr/
The current goal is replaced by:
parent( tom.pat) parent( bob, pat)

This goal is immediately satisfied because it appears in the program as a fact. This
Figure 1.9 The first step of the execution. The top goal is true if the bottom goal is true. completes the execution trace, which is graphically shown in Figure 1. 11.
22 Introduction to Prolog Declarative and procedural meaning of programs 23

predecessor( tom, pat) 1.5 Declarative and procedural

··········································· meaning of programs
····················································································· ··········
I n our examples s o far i t has always been possible to understand the results o f the
by rule pr/ by rule pr2 program without exactly knowing how the system actually found the results. It
parent( tom, Y) therefore makes sense to distinguish between two levels of meaning of Prolog
parent( tom, pat) predecessor( Y, pat) programs; namely,
no
• the declarative meaning and
Y = bob 11 by fact parent( tom, bob)
• the procedural meaning.
predecessor( bob, pat)
The declarative meaning is concerned only with the relations defined by the
program. The declarative meaning thus determines what will be the output of
by rule pr! the program. On the other hand, the procedural meaning also determines how this
output is obtained; that is, how the relations are actually evaluated by the Prolog
parent( bob, pat) system.
yes The ability of Prolog to work out many procedural details on its own is considered
to be one of its specific advantages. It encourages the programmer to consider the
Figure 1.11 The complete execution trace to satisfy the goal predecessor( tom, pat). The declarative meaning of programs relatively independently of their procedural
right-hand branch proves the goal is satisfiable. meaning. Since the results of the program are, in principle, determined by its
declarative meaning, this should be (in principle) sufficient for writing programs.
This is of practical importance because the declarative aspects of programs are
The graphical illustration of the execution trace in Figure 1. 11 has the form of a
usually easier to understand than the procedural details. To take full advantage of
tree. The nodes of the tree correspond to goals, or to lists of goals that are to be
this, the programmer should concentrate mainly on the declarative meaning and,
satisfied. The arcs between the nodes correspond to the application of (alternative)
whenever possible, avoid being distracted by the executional details. These should
program clauses that transform the goals at one node into the goals at another node.
be left to the greatest possible extent to the Prolog system itself.
The top goal is satisfied when a path is found from the root node (top goal) to a leaf
This declarative approach indeed often makes programming in Prolog easier than
node labelled 'yes'. A leaf is labelled 'yes' if it is a simple fact. The execution of Prolog
in typical procedurally oriented programming languages such as C or Pascal.
programs is the searching for such paths. During the search Prolog may enter an
Unfortunately, however, the declarative approach is not always sufficient. It will
unsuccessful branch. When Prolog discovers that a branch fails it automatically
later become clear that, especially in large programs, the procedural aspects cannot
backtracks to the previous node and tries to apply an alternative clause at that node.
be completely ignored by the programmer for practical reasons of executional
efficiency. Nevertheless, the declarative style of thinking about Prolog programs
should be encouraged and the procedural aspects ignored to the extent that is
Exercise permitted by practical constraints.

1. 7 Try to understand how Prolog derives answers to the following questions, using
the program of Figure 1.8. Try to draw the corresponding derivation diagrams in the
style of Figures 1.9 to 1.11. Will any backtracking occur at particular questions? Summary
························································································································ ·················
(a) ?- parent( pam, bob). • Prolog programming consists of defining relations and querying about relations.
(b) ?- mother( pam, bob). • A program consists of clauses. These are of three types: facts, mies and questions.
(c) ?- grandparent( pam, ann)- • A relation can be specified by facts, simply stating the n-tuples of objects that
(d) ?- grandparent( bob, jim). satisfy the relation, or by stating mies about the relation.
24 Introduction to Prolog

• A proced11re is a set of clauses about the same relation.

• Querying about relations, by means of q11esHons, resembles querying a database. chapter 2
Prolog's answer to a question consists of a set of objects that satisfy the question.
• In Prolog, to establish whether an object satisfies a query is often a complicated
process that involves logical inference, exploring among alternatives and
possibly backtracking. All this is done automatically by the Prolog system and is, Syntax and Meaning of
Prolog Programs
in principle, hidden from the user.
• Two types of meaning of Prolog programs are distinguished: declarative and
procedural. The declarative view is advantageous from the programming point
of view. I\evertheless, the procedural details often have to be considered by the 2.1 Data objects 26
programmer as well.
• The following concepts have been introduced in this chapter: 2.2 Matching 33
clause, fact, rule, question 2.3 Declarative meaning of Prolog programs 38
the head of a clause, the body of a clause
recursive rule, recursive definition 2.4 Procedural meaning 41
procedure
atom, variable 2.5 Example: monkey and banana 46
instantiation of a variable
2.6 Order of clauses and goals 50
goal
goal is satisfiable, goal succeeds 2.7 The relation between Prolog and logic 57
goal is unsatisfiable, goal fails
backtracking
declarative meaning, procedural meaning

References
This chapter gives a systematic treatment of the syntax and semantics of basic
Various implementations of Prolog use different syntactic conventions. However, most of them concepts of Prolog, and introduces structured data objects. The topics included are:
follow the tradition of the so-called Edinburgh syntax (also called DEC-10 syntax, established • simple data objects (atoms, numbers, variables)
by the historically influential implementation of Prolog for the DEC-10 computer; Pereira et al.
1978; Bowen 1981). The Edinburgh syntax also forms the basis of the ISO international • structured objects
standard for Prolog ISO/IEC 13211-1 (Deransart d al. 1996). Major Prolog implementations • matching as the fundamental operation on objects
now largely comply with the standard. In this book we use a subset of the standard syntax, with • declarative (or non-procedural) meaning of a program
some small and insignificant differences. In rare cases of such differences, there is a note to this
effect at an appropriate place. • procedural meaning of a program
• relation between the declarative and procedural meanings of a program
Bowen, D.L. (1981) DECsystem-JO Prolog User's Manual. University of Edinburgh: Department of • altering the procedural meaning by reordering clauses and goals.
Artificial Intelligence.
Deransart, P., Ed-Bdali, A. and Ceroni, L. (1996) Prolog: The Standard. Berlin: Springer-Verlag. Most of these topics have already been reviewed in Chapter 1. Here the treatment
Pereira, L.M., Pereira, F. and Warren, D.H.D. (1978) User's Guide to DECsystem-JO Prolog. will become more formal and detailed.
University of Edinburgh: Department of Artificial Intelligence.

25
'
26 Syntax and Meaning of Prolog Programs Data objects n
data objects
2.1 Data objects
····················································.. ············--······································································
Figure 2.1 shows a classification of data objects in Prolog. The Prolog system
/
simple objects
�
structures
recognizes the type of an object in the program by its syntactic form. This is possible
because the syntax of Prolog specifies different forms for each type of data object. /
constants
�
variables
We have already seen a method for distinguishing between atoms and variables in
1
�·' Chapter 1: variables start with upper-case letters whereas atoms start with lower-case
letters. No additional information (such as data-type declaration) has to be com­ atoms
/ �
numbers
municated to Prolog in order to recognize the type of an object.
N Figure 2.1 Data objects in Prolog.
'":
2.1.1 Atoms and numbers
(3) Strings of characters enclosed in single quotes. This is useful if we want, fo1
In Chapter 1 we have seen some simple examples of atoms and variables. In general,
example, to have an atom that starts with a capital letter. By enclosing it in
however, they can take more complicated forms - that is, strings of the following
quotes we make it distinguishable from variables:
characters:
'Torn'
;j • upper-case letters A, B, ..., Z 'Sonth_America'
• lower-case letters a, b, ... , z 'Sarah Jones'
• digits 0, 1, 2, ... , 9 Numbers used in Prolog include integer numbers and real numbers. The syntax ot
• special characters such as + - * / < > = : . & integers is simple, as illustrated by the following examples:
Atoms can be constructed in three ways:
1313 0 -97
(1) Strings of letters, digits and the underscore character, '_', starting with a lower­
case letter: Not all integer numbers can be represented in a computer, therefore the range ol
integers is limited to an interval between some smallest and some largest number
anna
� permitted by a particular Prolog implementation.
.,; nil
x25 We will assume the simple syntax of real numbers, as shown by the following
'1 x_25 examples:

I
x_ZSAB
x_ 3.14 -0.0035 100.2
x___y
Real numbers are not very heavily used in typical Prolog programming. The reason
alpha_beta_procedure
for this is that Prolog is primarily a language for symbolic, non-numeric computa­
} miss_Jones

I!
sarah_jones tion. [n symbolic computation, integers are often used, for example, to count the
number of items in a list; but there is typically less need for real numbers.
(2) Strings of special characters: Apart from this lack of necessity to use real numbers in typical Prolog applica­
<---> tions, there is another reason for avoiding real numbers. In general, we want to keep
======> the meaning of programs as neat as possible. The introduction of real numbers
somewhat impairs this neatness because of numerical errors that arise due to
rounding when doing arithmetic. For example, the evaluation of the expression

I
10000 + 0.0001 - 10000
When using atoms of this form, some care is necessary because some strings of
special characters already have a predefined meaning; an example is ':-' . may result in 0 instead of the correct result 0.0001.

,!
28 Syntax and Meaning of Prolog Programs Data objects 29

2.1.2 Variables 2.1.3 Structures

Variables are strings of letters, digits and underscore characters. They start with an Structured objects (or simply structures) are objects that have several components.
upper-case letter or an underscore character: The components themselves can,in turn,be structures. For example,the date can be
viewed as a structure with three components: day, month, year. Although composed
X
of several components, structures are treated in the program as single objects. In
Result
Object2 order to combine the components into a single object we have to choose a functor. A
Participant_list suitable functor for our example is date. Then the date 1 May 200 I can be written as:
ShoppingList elate( 1, may, 2001)
x23
_23 (see Figure 2.2).
When a variable appears in a clause once only, we do not have to invent a name All the components in this example are constants (two integers ancl one atom).
for it. We can use the so-called 'anonymous' variable, which is written as a single Components can also be variables or other structures. Any day in May can be
underscore character. For example, let us consider the following rule: represented by the structure:

hasachild( X) :- parent( X,Y). date( Day, may, 2001)

This rule says: for all X, X has a child if X is a parent of some Y. We are defining the Note that Day is a variable and can be instantiated to any object at some later point
property hasachild which, as it is meant here, does not depend on the name of in the execution.
the child. Thus, this is a proper place in which to use an anonymous variable. The This method for data structuring is simple and powerful. It is one of the reasons
clause above can thus be rewritten: why Prolog is so naturally applied to problems that involve symbolic manipulation.
Syntactically, all data objects in Prolog are terms. For example,
hasachilcl(X) :- parent( X,_).
may
Each time a single underscore character occurs in a clause it represents a new
anonymous variable. For example, we can say that there is somebody who has a and
child if there are two objects such that one is a parent of the other: date( 1,may,2001)
somebody _has_chilcl :- parent(_,_). are terms.
This is equivalent to: All structured objects can be pictured as trees (see Figure 2.2 for an example). The
root of the tree is the functor, and the offsprings of the root are the components. If a
somebody _has_chilcl :- parent( X, Y).
component is also a structure then it is a subtree of the tree that corresponds to the
But this is, of course, quite different from: whole structured object.
Our next example will show how structures can be used to represent some simple
somebocly_has_chilcl :- parent( X,X).
geometric objects (see Figure 2.3). A point in two-dimensional space is defined by its
If the anonymous variable appears in a question clause then its value is not output
when Prolog answers the question. If we are interested in people who have children,

I \II
date date( 1, may, 2001)

/I�
but not in the names of the children, then we can simply ask:
?- parent( X,_).
The lexical scope of variable names is one clause. This means that, for example, if may 2001 functor arguments
the name XlS occurs in two clauses, then it signifies two different variables. But (a) ( b)
each occurrence of XIS within the same clause means the same variable. The
situation is different for constants: the same atom always means the same object in Figure 2.2 Date is an example of a structured object: (a) as it is represented as a tree; (b) as it
any clause - that is, throughout the whole program. is written in Prolog.
 ?''\
30 Syntax and Meaning of Prolog Programs Data objects 31

l
5
(6.4)

;-, : , �
4
/"g�

I\ I\
point point

/' T·�
2 r
2 3
(7.1)
Fl =(1.l)
2 3 4 5 6 7 8

Figure 2.3 Some simple geometric ob1ects.

I\ /\ I\
point point point

two coordinates; a line segment is defined by two points; and a triangle can be
defined by three points. Let us choose the following functors: 4 2 6 4

point for points,

Figure 2.4 Tree representation of the objects in Figure 2.3.
seg for line segments, and
triangle for triangles.
As already explained, all structllfed objects in Prolog are trees, represented in the
Then the objects in Figure 2.3 can be represented as follows: program by terms. We will study two more examples to illustrate how naturally
Pl = point(l, 1) complicated data objects can be represented by Prolog terms. Figure 2.5 shows the
P2 = point(2,3) tree structure that corresponds to the arithmetic expression:
S = seg( Pl, P2) = seg( point(l , 1), point(2 ,3))
T = triangle( point('cl,2), point(6,4), point(7,l)) (a+/J)*(c--5)
According to the syntax of terms introduced so far this can be written, using the
The corresponding tree representation of these objects is shown in Figure 2.4. In
symbols '* ', '+' and ' -' as functors, as follows:
general, the functor at the root of the tree is called the principal functor of the term.
If in the same program we also had points in three-dimensional space then we ,(+(a, b), -( c, 5))
could use another functor, point3, say, for their representation:
This is, of course, a legal l'rolog term; but this is not the form that we would
point3( X, Y, Z) normally iike to have. We would normally prefer the usual, infix notation as used
in mathematics. In fact, Prolog also allows us to use the infix notation so that
We can, however, use the same name, point, for points in both two and three
the symbols '* ', '+' and ' -' are written as infix operators. Details of how the
dimensions, and write for example:
programmer can define his or her own operators will be discussed in Chapter 3.
point( X l, Yl) and point( X, Y, Z)

/ �-
l( -
If the same name appears in the program in two different roles, as is the case for
point above, the Prolog system will recognize the difference by the number of
arguments, and will interpret this name as two functors: one of them with two +
arguments and the other one with three arguments. This is so because each functor
is defined by two things:
a
/� /� b
(1) the name, whose syntax is that of atoms;
(2) the arity- that is, the number of arguments. Figure 2.5 A tree structure that corresponds to the arithmetic expression (a+ b) * (c - 5).
32 Syntax and Meaning of Prolog Programs Matching 33

rI r2 seq seq( rl, r2)

/\
-� par( rl, r2)
par( rl, par( r2, r3) )
(:1) par( rl, seq( par( r2, r3), r4) )
rI r2

rl Exercises

-0
par

/\
rI r2
2 .1 Which of the following are syntactically correct Prolog objects? What kinds of object
are they (atom, number, variable, structure)?
(t,)
(a) Diana
(b) diana
rl par (c) 'Diana'

r2 /\
rl par
(d) _diana
(e) 'Diana goes south'

(c)
r)
/\ r2 r3
(f) goes( diana, south)
(g) 45
(h) 5( X, Y)
(i) +( north, west)
rl par ( j) three( Black( Cats) )

/\
rl seq
2.2 Suggest a representation for rectangles, squares and circles as structured Prolog
objects. Use an approach similar to that in Figure 2.4. For example, a rectangle can

/\
be represented by four points (or maybe three points only). Write some example
terms that represent some concrete objects of these types using the suggested
representation.
par r4

/\
(d)

r2 r3 2.2 �.�.t_c_�!.�.9.............................................. ........................................................................

Figure 2.6 Some simple electric circuits and their tree representations: (a) sequential
composition of resistors r1 and r2; (b) parallel composition of two resistors; In the previous section we have seen how terms can be used to represent complex
(c) parallel composition of three resistors; (d) parallel composition of rl and data objects. The most important operation on terms is matching. Matching alone
another circuit. can produce some interesting computation.
Given two terms, we say that they match if:
(1) they are identical, or
As the last example we consider some simple electric circuits shown in Figure 2.6.
(2) the variables in both terms can be instantiated to objects in such a way that
The right-hand side of the figure shows the tree representation of these circuits. The
after the substitution of variables by these objects the terms become identical.
atoms rl, r2, r3 and r4 are the names of the resistors. The functors par and seq denote
the parallel and the sequential compositions of resistors respectively. The corres­ For example, the terms date( D, M, 2001) and date( Dl, may, Yl) match. One instan­
ponding Prolog terms are: tiation that makes both terms identical is:
34 Syntax and Meaning of Prolog Programs
Matching 35

• D is instantiated to Dl To satisfy the first goal, Prolog instantiates the variables as follows:
• M is instantiated to may D= Dl
• Yl is instantiated to 2001 M= may
Yl= 2001
This instantiation is more compactly written in the familiar form in which Prolog
outputs results: After having satisfied the second goal, the instantiation becomes more specific as
follows:
D= Dl
D=15
M=may
Yl=200l Dl=15
M= may
On the other hand, the terms date( D, M, 2001) and date( Dl, Ml, 1444) do not YI=2001
match, nor do the terms date( X, Y, Z) and point( X, Y, Z). Y=2001
,vfutching is a process that takes as input two terms and checks whether they This example also shows that variables, during the execution of consecutive goals,
match. If the terms do not match we say that this process fails. If they do match then typically become instantiated to increasingly more specific values.
the process succeeds and it also instantiates the variables in both terms to such values The general rules to decide whether two terms, Sanc! T, match are as follows:
that the terms become identical.
Let us consider again the matching of the two dates. The request for this
operation can be communicated to the Prolog system by the following question, (1) If Sand T are constants then Sand T match only if they are the same object.
using the operator'=': (2) If Sis a variable and T is anything, then they match, and Sis instantiated to
T. Conversely, if T is a variable then T is instantiated to S.
'!- date( D, M, 2001) = date( Dl, may, Yl).
(3) If Sand T are structures then they match only if
We have already mentioned the instantiation D= Dl, M = may, Yl = 2001, which (a) Sand T have the same principal functor, and
achieves the match. There are, however, other instantiations that also make both
(b) all their corresponding components match.
terms identical. Two of them are as follows:
The resulting instantiation is determined by the matching of the com­
D=l
Dl=1 ponents.
M= may
Yl= 2001 The last of these rules can be visualized by considering the tree representation of
D=third terms, as in the example of Figure 2.7. The matching process starts at the root (the
Dl=thircl principal functors). As both functors match, the process proceeds to the arguments
M=may where matching of the pairs of corresponding arguments occurs. So the whole
Yl= 2001 matching process can be thought of as consisting of the following sequence of
These two instantiations are said to be less general than the first one because they (simpler) matching operations:
constrain the values of the variables D and Dl more strongly than necessary. For triangle=triangle,
making both terms in our example identical, it is only important that D and D l have point(l.l)= X..
the same value, although this value can be anything. Matching in Prolog always A= point(4,Y),
results in the most general instantiation. This is the instantiation that commits the point(2,3)= point(2,Z).
variables to the least possible extent, thus leaving the greatest possible freedom for The whole matching process succeeds because all the matchings in the sequence
further instantiations if further matching is required. As an example consider the succeed. The resulting instantiation is:
following question:
X=point(l,l}
?- date( D, M, 2001)= elate( Dl, may, Yl), A=point(4,Y)
elate( D, M, 2001)= elate( 15, M, Y). Z=3
36 Syntax and Meaning of Prolog Programs Matching 37

/I�
triangle

point(X.Yl)

I\
point A point

I\ 2 3
point( X. Y) point( XI. Yl

triangle point( X. Yl

/I �

/\ /\
X point point
Figure 2.8 Illustration of vertical and horizontal line segments.

-1 y z A more general question to the program is: Are there any vertical segments that
start at the point (2,3)?
Figure 2.7 Matching triangle( point(l, 1), A, point(2,3) ) = triangle( X, point(4, Y),
point(2,Z) ). ?- vertical( seg( point(Z,3), P)).
P = point(Z, Y)
The following example will illustrate how matching alone can be used for
interesting computation. Let us return to the simple geometric objects of Figure This answer means: Yes, any segment that ends at any point (2, Y), which means
2A, and define a piece of program for recognizing horizontal and vertical line anywhere on the vertical line x = 2. It should be noted that Prolog's actual answer
segments. 'Vertical' is a property of segments, so it can be formalized in Prolog as a would probably not look as neat as above, but (depending on the Prolog
unary relation. Figure 2.8 helps to formulate this relation. A segment is vertical if the implementation used) something like this:
x-coordinates of its encl-points are equal, otherwise there is no other restriction on
P = point(Z,_136)
the segment. The property 'horizontal' is similarly formulated, with only x and y
interchanged. The following program, consisting of two facts, does the job: This is, however, only a cosmetic difference. Here _136 is a variable that has not been
vertical( seg( point(X,Y), point(X,Y l))). instantiated. _136 is a legal variable name that the system has constructed during the
execution. The system has to generate new names in order to rename the user's
horizontal( seg( point(X,Y), point(Xl,Y))).
variables in the program. This is necessary for two reasons: first, because the same
The following conversation is possible with this program: name in different clauses signifies different variables, and second, in successive
applications of the same clause, its 'copy' with a new set of variables is used each
?- vertical( seg( point(l,l), point(l,2))).
time.
yes Another interesting question to our program is: Is there a segment that is both
?- vertical( seg( point(l,l), point(Z,Y)) ). vertical and horizontal?
no ?- vertical( S), horizontal( S).
?- horizontal( seg( point(l, 1), point(Z,Y))). S = seg( point(X,Y), point(X,Y))
Y=l
This answer by Prolog says: Yes, any segment that is degenerated to a point has the
The first question was answered 'yes' because the goal in the question matched one of property of being vertical and horizontal at the same time. The answer was, again,
the facts in the program. For the second question no match was possible. In the third derived simply by matching. As before, some internally generated names may
question, Y was forced to become 1 by matching the fact about horizontal segments. appear in the answer, instead of the variable names X and Y.
 Declarative meaning of Prolog programs 39

Thus the difference between the declarative readings and the procedural ones is
that the latter do not only define the logical relations between the head of the clause
111 the following matching operations succeed or fail? If they succeed, what are the and the goals in the body, but also the order in which the goals are processed.
resulting instantiations of variables? Let us now formalize the declarative meaning.
The declarative meaning of programs determines whether a given goal is true,
(a) point( A, B) = point( 1, 2) and if so, for what values of variables it is true. To precisely define the declarative
(b) point( A, B) = point( X, Y, Z) meaning we need to introduce the concept of instance of a clause. An instance of a
(c) plus( 2, 2) = 4 clause C is the clause C with each of its variables substituted by some term. A variant
of a clause C is such an instance of the clause C where each variable is substituted by
(cl) +( 2, D) = +( E, 2) another variable. For example, consider the clause:
(e) triangle( point(-1,0), P2, P3) = triangle( Pl, point(l,O), point(O,Y) ) hasachild( X) :- parent( X, Y).
The resulting instantiation defines a family of triangles. How would you Two variants of this clause are:
describe this family?
hasachild( A) :- parent( A, B).
2.4 Using the representation for line segments as described in this section, write a term hasachild( Xl) :- parent( Xl, X2).
that represents any vertical line segment at x = 5. Instances of this clause are:
2.5 Assume that a rectangle is represented by the term rectangle( Pl, P2, 1'3, P4) where hasachild( peter) :- parent( peter, Z).
hasachild( barry) :- parent( barry, small(caroline) ).
the P's are the vertices of the rectangle positively ordered. Define the relation:
Given a program and a goal G, the declarative meaning says:
regular( R)

which is true if R is a rectangle whose sides are vertical and horizontal. A goal G is true (that is, satisfiable, or logically follows from the program) if and
only if:

2.3 . (1) there is a clause C in the program such that

�.�.�!�.r�.�!''..�...��.��.i�9..?.'..?'..?!?9.. P.'..?9.' .�.�.s....................................................... (2) there is a clause instance I of C such that

(a) the head of I is identical to G, and
We have already seen in Chapter 1 that Prolog programs can be understood in two
ways: declaratively and procedurally. In this and the next section we will consider a (b) all the goals in the body of I are true.
more formal definition of the declarative and procedural meanings of programs in
basic Prolog. But first let us look at the difference between these two meanings again. This definition extends to Prolog questions as follows. In general, a question to
Consider a clause: the Prolog system is a list of goals separated by commas. A list of goals is true if all the
goals in the list are true for the same instantiation of variables. The values of
P :- Q, R.
the variables result from the most general instantiation.
where P, Q and R have the syntax of terms. Some alternative declarative readings of A comma between goals thus denotes the conjunction of goals: they all have to be
this clause are: true. But Prolog also accepts the disjunction of goals: any one of the goals in a
disjunction has to be true. Disjunction is indicated by a semicolon. For example,
P is true if Q and R are true.
p :- Q; R.
From Q and R follows P.
is read: P is true if Q is true or R is true. The meaning of this clause is thus the same as
Two alternative procedural readings of this clause are: the meaning of the following two clauses together:
To solve problem P, first solve the subproblem Q and the11 the subproblem R. p Q.
To satisfy P, first satisfy Q and then R. p :- R.
40 Syntax and Meaning of Prolog Programs Procedural meaning 41

The comma binds stronger than the semicolon. So the clause: 2.8 Rewrite the following program without using the semicolon notation.
P :- Q, R; S, T, U. translate( Number, Word) :­
is understood as: Number= 1, Word= one;
Number= 2, Word= two;
P :- ( Q, R); ( S, T, U). Number= 3, Word= three.
and means the same as the clauses:
p Q, R.
P :- S, T, U.

2.4 Procedural meaning

Exercises ····················· · ·· · · · ···· · · · · · · · ·· · · · · · · · · · · · · · · ········ · · · · · · ········· · · · · · · · · · ·· · · · · · · · · · · · · · · ···················· ················

The procedural meaning specifies /zow Prolog answers questlons. To answer a

2.6 Consider the following program: question means to try to satisfy a list of goals. They can be satisfied lf the variables
f( l, one). that occur in the goals can be instantiated in such a way that the goals logically
f( s(l), two). follow from the program. Thus the procedural meaning of Prolog is a procedure for
executing a list of goals with respect to a given program. To 'execute goals' means:
f( s(s(l)), three).
try to satisfy them.
f( s(s(s(X))), NJ :- Let us call this procedure execute. As shown in Figure 2.9, the inputs to and the
f( X, N).
outputs from this procedure are:
How will Prolog answer the following questions? Whenever several answers are
posslble, give at least two. input: a program and a goal list
output: a success/failure indicator and an instantiation of variables
(a) ?- f( s(l), .-\).
The meaning of the two output results is as follows:
(b) ?- f( s(s(l)), two).
(c) ?- f( s(s(s(s(s(s(l)))))), C). (1) The success/failure indicator is 'yes' if the goals are satisfiable and 'no'
(d) ?- f( D, three).
otherwise. We say that 'yes' signals a successful termination and 'no' a failure.
(2) An instantiation of variables is only produced in the case of a successful
2.7 The following program says that two people are relatives if
termination; in the case of failure there is no instantiation.
(a) one is a predecessor of the other, or
In Chapter 1, we have in effect already discussed informally what procedure
(b) they have a common predecessor, or
execute does, under the heading 'How Prolog answers questions'. What follows in
(c) they have a common successor: the rest of this section is just a more formal and systematic descriptlon of this
relatives( X, Y) :­
predecessor( X, Y).
program
relatives( X, Y) :­
predecessor( Y, X).
relatives( X, Y) :­ % X and Y have a common predecessor
predecessor( Z, X),
predecessor( Z, Y). ,,_ success/failure indicator
goolli"t
relatives( X, Y) :­ % X and Y have a common successor
instantiation of variable,
predecessor( X, Z),
predecessor( Y, Z).
Can you shorten this program by using the semicolon notation? Figure 2.9 Input/output view of the procedure that executes a list of goals.
42 Syntax and Meaning of Protog Programs Procedural meaning 43

process, and can be skipped without seriously affecting the understanding of the rest PROGRAM
of the book.
big( bear). % Clause 1
Particular operations in the goal execution process are illustrated by the example big( elephant). % Clause 2
in Figure 2.10. It may be helpful to study Figure 2.10 before reading the following small( cat). % Clause 3
general description.
brown( bear). % Clause 4
To execute a list of goats: % Clause S
black( cat).
gray( elephant). % Clause 6
Gl, G2, ..., Gm
dark( Z) :- % Clause 7: Anything black is dark
the procedure execute does the following: black( Z).
dark( Z) :­ % Clause 8: Anything brown is dark
brown( Z).
• If the goal list is empty then terminate with success.
• If the goal list is not empty then continue ,�ith (the following) operation
QUESTION

called 'SCANNING'. ?- dark( X), big( X). ')-b Who is dark and big?
• SCANNING: Scan through the clauses in the program from top to bottom EXECUTlON TRACE
until the first clause, C, is found such that the head of C matches the first goal (1) Initial goal list: dark( X), big( X).
G 1. If there is no such clause then terminate with failure. (2) Scan the program from top to bottom looking for a clause whose head matches the first goal
If there is such a clause C of the form dark( X). Clause 7 found:
dark( Z) :- black( Z).
H :- Bl, ..., Bn.
Replace the first goal by the instantlated body of clause 7, giving a new goal list:
then rename the variables in C to obtain a variant C' of C, such that C' and
black( X), big( X)
the list G 1, ..., Gm have no common variables. Let C' be
(3) Scan the program to find a match with black( X). Clause 5 found: black( cat).This clause has no
H' :- Bl', ... , Bn'. body, so the goal list, properly instantiated, shrinks to:
Match G 1 and H'; let the resulting instantiation of variables be S. big( cat)
In the goal list G 1, G2, . .., Gm, replace Gl with the list Bl', ... , Bn', (4) Scan the program for the goal big( cat).No clause found. Therefore backtrack to step (3) and undo
obtaining a new goal list tile instantiation X = cat. Now the goal list is again:
Bl', ... , Bn', G2, ..., Gm black( X), big( X)
(Note that if C is a fact then n = 0 and the new goal list is shorter than the Continue scanning the program below clause 5. No clause found. Therefore backtrack to step (2) and
continue scanning below clause 7. Clause 8 is found:
original one; such shrinking of the goal list may eventually lead to the empty
list and thereby a successful termination.) dark( Z) :- brown( Z).
Substitute the variables in this new goal list with new values as specified in Replace the first goal in the goal list by brown( X), giving:
the instantiation S, obtaining another goal list brown( X), big( X)
Bl", ... , Bn", G2', ..., Gm' (5) Scan the program to match brown( X), finding brown( bear). This claLtse has no body, so the goal
list shrinks to:
• Execute (recursively with this same procedure) this new goal list. If the
big( bear)
execution of this new goal list terminates with success then terminate
(6) Scan the program and find clause big( bear). It has no body so the goal list shrinks to empty. This
the execution of the original goal list also with success. If the execution indicates successful termination, and the corresponding variable instantiation is:
of the new goal list is not successful then abandon this new goal list and go
X = bear
back to SCANNING through the program. Continue the scanning with the
clause that immediately follows the clause C (C is the clause that was last
Figure 2.10 An example to illustrate the procedural meaning of Prolog: a sample trace of the procedure
used) and try to find a successful terminati0n using some other clause.
execute.
 Procedural meaning 45
44 Syntax and Meaning of Prolog Programs

This procedure is more compactly written in a Pascal-like notation in Figure procedure execute (Program, Goa/List, Success);
2.11. Input arguments:
Several additional remarks are in order here regarding the procedure execute as Program: list of clauses
presented. First, it was not explicitly described how the final resulting instantiation Goa/List: list of goals
of variables is produced. It is the instantiation S which led to a successful Output argLiment:
Success: truth value; Success will become true if Goa/List is true with respect to Program
termination, and was possibly further refined by additional instantiations that were
Local variables:
done in the nested recursive calls to execute. Goal: goal
Whenever a recursive call to execute fails, the execution returns to SCANNING, OtilerGoals: list of goals
continuing at the program clause C that had been last used before. As the Satisfied: truth value
application of the clause C did not lead to a successful termination Prolog has to MatchOK: truth value
try an alternative clause to proceed. What effectively happens is that Prolog Instant: instantiation of variables
abandons this whole part of the unsuccessful execution and backtracks to the point H, H', Bl,Bl', ... , B11, 811': goals
(clause C) where this failed branch of the execution was started. When the Auxiliary functions:
empty(L): returns true if L is the empty list
procedure backtracks to a certain point, all the variable instantiations that were
head(L): returns the first element of list L
done after that point are undone. This ensures that Prolog systematically examines tail(L): returns the rest of L
all the possible alternative paths of execution until one is found that eventually append(Ll,l2): appends list L2 at the end of list LI
succeeds, or until all of them have been shown to fail. match(Tl,T2,1'vfatcilOK,Jnstant): tries to match terms Tl and T2; if
We have already seen that even after a successful termination the user can force succeeds then MatchOK is true and Instant is the corresponding instantiation of variables
the system to backtrack to search for more solutions. In our description of execute substitute(I11stant,Coals): substitutes variables in Coals according to instantiation Instant
this detail was left out. begin
Of course, in actual implementations of Prolog, several other refinements have to if mzpty(Goallist) then Success :c, true
be added to execute. One of them is to reduce the amount of scanning through the else
program clauses to improve efficiency. So a practical Prolog implementation will not begin
scan through all the clauses of the program, but will only consider the clauses about Coal := lzead(Goa/List);
the relation in the current goal. OtherCoals := tai/(Goallist);
Satisfied := false;
while not Satisfied and "more clauses in program" do
begin
Let next clause in Program be
H :-Bl, ... ,Bn.
Construct a variant of this clause
H' :-Bl', ... ,Bn'.
match(Goal,H',Matc/1OK,Irzstarzt);
onsider the program in Figure 2.10 and simulate, in the style of Figure 2.10, if MatchOK then
olog's execution of the question: begin
NewGoals := append([B1',... ,En'], OtherCoals);
7- big( X), dark( X). NewGoczls := substitute(Instarzt,NewCoals);
exernte(Program,NewCoals,Satisf7ed)
1pare your execution trace with that of Figure 2.10 when the question was end
1tially the same, but with the goals in the order: end;
Success := Satisfied
'.lark( X), big( X) . end
end;
:h of the two cases does Prolog have to do more work before the answer is
Figure 2.11 Executing Prolog goals.
46 Syntax and Meaning of Prolog Programs Example: monkey and banana 47

2.5 Example: monkey and banana

··········································································································································
Second, what are the allowed moves that change the world from one state to
another? There are four types of moves:
The monkey and banana problem is used as a simple example of problem solving.
(1) grasp banana,
Our Prolog program for this problem will show how the mechanisms of matching
and backtracking can be used in such exercises. We will develop the program in the (2) climb box,
non-procedural way, and then study its procedural behaviour in detail. The program (3) push box,
will be compact and illustrative.
(4) walk around.
We will use the following variation of the problem. There is a monkey at the door
into a room. In the middle of the room a banana is hanging from the ceiling. The Not all moves are possible in every possible state of the world. For example, the
monkey is hungry and wants to get the banana, but he cannot stretch high enough move 'grasp' is only possible if the monkey is standing on the box directly
from the floor. At the window of the room there is a box the monkey may use. The under the banana (which is in the middle of the room) and does not have the
monkey can perform the following actions: walk on the floor.. climb the box, push banana yet. Such rules can be formalized in Prolog as a three-place relation named
the box around (if it is already at the box) and grasp the banana if standing on the move:
box directly under the banana. Can the monkey get the banana?
One important task in programming is that of finding a representation of the move( Statel, Move, StateZ)
problem in terms of the programming language used. In our case we can think of
The three arguments of the relation specify a move thus:
the 'monkey world' as always being in some state that can change in time. The
current state is determined by the positions of the objects. For example, the initial Statel ------ StateZ
state of the world is determined by: Move

(1) Monkey is at door. Statel is the state before the move, Move is the move executed and StateZ is the state
(2) Monkey is on floor. after the move.
The move 'grasp', with its necessary precondition on the state before the move,
(3) Box is at window.
can be defined by the clause:
(4) Monkey does not have banana.
move( state( middle, onbox, middle, hasnot), % Before move
It is convenient to combine all of these four pieces of information into one structured grasp, %Move
object. Let us choose the word 'state' as the functor to hold the four components state( midclle, onbox, micldle, has) ). % After move
together. Figure 2.12 shows the initial state represented as a structured object.
Our problem can be viewed as a one-person game. Let us now formalize the rules This fact says that after the move the monkey has the banana, and he has remained
of the game. First, the goal of the game is a situation in which the monkey has the on the box in the middle of the room.
In a similar way we can express the fact that the monkey on the floor can walk
banana; that is, any state in which the last component is 'has':
from any horizontal position Posl to any position PosZ. The monkey can do this
state(_, _, _, has) regardless of the position of the box and whether it has the banana or not. All
this can be defined by the following Prolog fact:
state

//\�
move( state( Posl, onfloor, Box, Has),
walk( Posl, PosZ), %, Walk from Pos l to Pos2
state( PosZ, onfloor, Box, Has) ).

atdoor on floor atwindow hasnot Note that this clause says many things, including, for example:

Figure 2.12 The initial state of the monkey world represented as a structured object. The four • the move executed was 'walk from some position Posl to some position
components are: horizontal position of monkey, vertical position of monkey, PosZ';
position of box, monkey has or has not banana. • the monkey is on the floor before and after the move;
48 Syntax and Meaning of Prolog Prograrr.s Example: monkey and banana 49

• the box is at some point Box which remained the same after the move; %, move( Statel, Move, State2): making Move in Sta tel results in State2;
• the 'has banana' status Has remains the same after the move. % a state is represented by a term:
% state( MonkeyHorizontal, MonkeyVertical, BoxPosition, l·lasBanana)
The clause actually specifies a whole set of possible moves because it is applicable to move( state( miclclle, onbox, middle, hasnot), % Before move
any situation that matches the specified state before the move. Such a specification grasp, % Grasp banana
is therefore sometimes also called a move schema. Using Prolog variables, such state( middle, onbox, middle, has) ). 91, After move
schemas can be easily programmed in Prolog. move( state( P, onfloor, P, H),
The other two types of moves, 'push' and 'climb', can be similarly specified. climb, % Climb box
The main kind of question that our program will have to answer is: Can the state( P, onbox, P, H) ).
monkey in some initial state State get the banana? This can be formulated as a move( state( Pl, onfloor, Pl, H),
predicate push( Pl, P2), % Push box from P 1 to P2
state( P2, onfloor, P2, H) ).
canget( State)
move( state( Pl, onfloor, B, H),
where the argument State is a state of the monkey world. The program for canget can walk( Pl, P2), % Walk from r 1 to rz
be based on two observations: state( P2, onfloor, B, I-1) ).

(1) For any state in which the monkey already has the banana, the predicate canget '¼, canget( State): monkey can get banana in State
must certainly be true; no move is needed in this case. This corresponds to the canget( state(_,_,_, has) ). %, can 1: Monkey already has it
Prolog fact: canget( State 1) :- % can 2: Do some work to get it
move( State 1, Move, State2), '¼, Do something
canget( state(_,_,_, has) ).
canget( State2). % Get it now
(2) In other cases one or more moves are necessary. The monkey can get the
banana in any state Statel if there is some move \love from Statel to some state Figure 2.14 A program for the monkey and banana problem.
State2, such that the monkey can then get the banana in state State2 (in zero or
more moves). This principle is illustrated in Figure 2.13. A Prolog clause that
corresponds to this rule is: to the program:
canget( State 1) :- ?- canget( state( atdoor, onfloor, atwindow, hasnot) ).
move( State 1, Move, State2),
canget( State2). Prolog's answer is 'yes'. The process carried out by Prolog to reach this answer
This completes our program, which is shown in Figure 2.14. proceeds, according to the procedural semantics of Prolog, through a sequence of
The formulation of canget is recursive and is similar to that of the predecessor goal lists. [t involves some search for the right moves among the possible alternative
relation of Chapter 1 (compare Figures 2.13 and 1.7). This principle is used in Prolog moves. At some point this search will take a wrong move leading to a dead branch.
again and again. At this stage, backtracking will help it to recover. Figure 2.15 illustrates this search
We have developed our monkey and banana program in the non-procedural way. process.
Let us now study its procedural behaviour by considering the following question To answer the question Prolog had to backtrack once only. A right sequence of
moves was found almost straight away. The reason for this efficiency of the program
was the order in which the clauses about the move relation occurred in the
Move Statem program. The order in our case (luckily) turned out to be quite suitable. However,
State l
... � less lucky orderings are possible. According to the mies of the game, the monkey
� could just as easily try to walk here or there without ever touching the box, or
canget canget has aimlessly push the box around. A more thorough investigation will reveal, as shown
in the following section, that the ordering of clauses is, in the case of our program,
Figure 2.13 Recursive formulation of canget. in fact critical.
 ''?' 7LT:S:Y <+ 4r"""'-�°"'· , A"°< ¼-.;zT;v. "' �',,< >� :,,•:,� ·�S..cA<;.J7T"'C��"7'� ..p

50 Syntax and Meaning of Prolog Programs Order of clauses and goals 51

Using the clause above, the goal p is replaced by the same goal p; this will be in turn
state( atdoor, onfloor, atwindow, hasnot)
replaced by p, etc. In such a case Prolog will enter an infinite loop not noticing that
no progress is being made.
walk( atdoor. P2) This example is a simple way of getting Prolog to loop indefinitely. However,
similar looping could have occurred in some of our previous example programs if we
changed the order of clauses, or the order of goals in the clauses. It will be instructive
state( P2, onfloor, atwindow, hasnot) to consider some examples.
In the monkey and banana program, the clauses about the move relation were
/
push( P2, P2') ordered thus: grasp, climb, push, walk ( perhaps 'unclimb' should be added for
climb/ //backtrack
/ P2 = atwindow completeness). These clauses say that grasping is possible, climbing is possible, etc.
According to the procedural semantics of Prolog, the order of clauses indicates that
the monkey prefers grasping to climbing, climbing to pushing, etc. This order of
state( atwindow, onbox, atwinJow, hasnot) state( P2', onfloor, P2', hasnol) preferences in fact helps the monkey to solve the problem. But what could happen if
the order was different? Let us assume that the 'walk ' clause appears first. The
No move
possible: climb execution of our original goal of the previous section
?- canget( state( atdoor, on floor, atwindow, hasnot) ).
state( P2', onbox, P2', hasnut) would this time produce the following trace. The first four goal lists (with variables
appropriately renamed) are the same as before:
grasp
P2' = middle canget( state( atdoor, onfloor, atwindow, hasuot))
(1)
The second clause of canget ('can2') is applied, producing:
state( middle, onbox, middle, has)
(2) move( state( atdoor, onfloor, atwindow, hasnot), M', S2'),
canget( S2')
Figure 2.15 The monkey's search for the banana, The search starts at the top node and
proceeds downwards, as indicated, Alternative moves are tried in the left-to-right By the move walk( atdoor, PZ') we get:
order, Backtracking occurred once only,
(3) canget( state( P2', onfloor, atwindow, hasnot))

Using the clause 'can2' again the goal list becomes:

(4) move( state( P2', onfloor, atwindow, hasnot), M", S2"),

2.6 canget(S2")

Now the difference occurs. The first clause whose head matches the first goal above
is now 'walk' (ancl not 'climb' as before). The instantiation is
2,6.1 Danger of indefinite looping
S2" = state( PZ", onfloor, atwindow, hasnot)
Consider the following clause:
Therefore the goal list becomes:
p :- p. canget( state( P2", onfloor, atwindow, hasnot) )
(5)
This says that 'p is true if p is true'. This is declaratively perfectly correct, but
procedurally is quite useless. In fact, such a clause can cause problems to Prolog. Applying the clause 'can2' we obtain:
Consider the question: (6) move( state( P2", onfloor, atwindow, hasnot), M"', S2"' ),
?- p. canget( S2"' )
52 Syntax and Meaning of Prolog Programs Order of clauses and goals 53

Again, 'walk' is now tried first, producing: (1) the order of clauses in the program, and
(7) canget( state( P2"', onfloor, atwindow, hasnot) ) (2) the order of goals in the bodies of clauses.

Let us now compare the goals (3), (5) and (7). They are the same apart from one The predecessor procedure consists of two clauses, and one of them has two goals in
variable; this variable is, in turn, P', P1' and P"'. As we know, the success of a goal does the body. There are, therefore, four variations of this program, all with the same
not depend on particular names of variables in the goal. This means that from goal declarative meaning. The four variations are obtained by:
list (3) the execution trace shows no progress. We can see, in fact, that the same
(1) swapping both clauses, and
two clauses, 'can2' and 'walk', are used repetitively. The monkey walks around
without e\·er trying to use the box. As there is no progress made this will (2) swapping the goals for each order of clauses.
(theoreticallv) go on for ever: Prolog will not realize that there is no point in
The corresponding four procedures, called predl, pred2, precl3 and pred4, are showrr
continuing along this line.
in Figure 2.16.
This example shows Prolog trying to solve a problem in such a way that a solution
is ne\·er reached, although a solution exists. Such situations are not unusual in
Prolog programming. Infinite loops are, also, not unusual in other programming
languages. What is unusual in comparison with other languages is that a Prolog % Four versions of the predecessor program
program may be declaratively correct, but at the same time be procedurally incorrect % The original version
in that it is not able to produce an answer to a question. In such cases Prolog may not predl( X, Z) :-
be :1b!e to satisfy a goal because it tries to reach an answer by choosing a wrong path. parent( X, ZJ.
..\ nJturJl question to ask at this point is: Can we not make some more substantial predl( X, Z) :­
change to our program so as to drastically prevent anv danger of looping? Or shall parent( X, Y),
me al11·a\·s ha\·e to rely just on a suitable ordering of clauses and goals? As it turns out predl( Y, Z).
programs. especiallv large ones, 'A"Ould be too fragile if they just had to rely on some
'¾, Variation a: swap clauses of the original version
suitable ordering. There are several other methods that preclude infinite loops, and
these are much more general and robust than the ordering method itself. These pred2( X, Z) :-
techniques will be used regularly later in the book, especially in those chapters that parent( X, Y),
pred2( Y, Z).
deal 11ith path finding, problem solving and search.
prec12( X, Z) :-
parent( X, Z).
2.6.2 Program variations through reordering of clauses and goals % Variation b: swap goals in second clause of the original version
pred3( X, Z) :-
..\lreJd\· in the example programs of Chapter 1 there was a latent danger of parent( X, Z).
producing a cycling behaviour. Our program to specify the predecessor relation in pred3( X, Z) :-
Chapter 1 was: pred3( X, Y),
parent( Y, Z).
predecessor( Parent, Child)
parent( Parent, Child). % Variation c: swap goals and clauses of the original version
pre<leces.sor( Predecessor, Successor) pred4( X, Z) :-
parent( Predecessor, Child), pred4( X, Y),
predecessor( Child, Successor). parent( Y, Z).
Let us analvze some variations of this program. All the variations will clearly have pred4( X, Z) :-
parent( X, Z).
the same declarative meaning, but not the same procedural meaning. According to
the declarative semantics of Prolog we can, without affecting the declarative
meaning, change: Figure 2.16 Four versions of the predecessor program.
54 Syntax and Meaning of Prolog Programs Order of clauses and goals 55

This question again brings the system into an infinite sequence of recursive calls.
There are important differences in the behaviour of these four declaratively
equivalent procedures. To demonstrate these, consider the parent relation as shown Thus prec!3 also cannot be considered procedurally correct.
in Figure 1.1 of Chapter l. Now, what happens if we ask whether Tom is a
predecessor of Pat using the four variations of the predecessor relation: 2.6.3 Combining declarative and procedural views
?- predl( tom, pat).
The foregoing section has shown that the order of goals and clauses does matter.
yes
Furthermore, there are programs that are declaratively correct.. but do not work in
?- pred2( tom, pat). practice. Such discrepancies between the declarative and procedural meaning may
yes pred2( X, Z) :­
parent( X, Y), pred21 lorn, pall
?- pred3( torn, pat).
prec!2( Y, Z).
yes pred2( X. Z) :­
parent( X, Z). parenll tom. y· I
?- pred4( torn, pat). pred21 y'. pall
In the la:;t case Prolog cannot find the answer. This is manifested on the terminal by l, y· = hoh
a Prolog message such as 'More core needed' or 'Stack overflow'. pred21 hoh. pall
Figure 1.11 in Chapter 1 showed the trace of preen (in Chapter 1 called
predecessor) produced for the above question. Figure 2.17 shows the corresponding
traces for pred2, prec!3 and pred4. Figure 2. l 7(c) clearly shows that pred4 is hopeless,
and Figure 2. l 7(a) indicates that pred2 is rather inefficient compared to predl: pred2
does much more searching and backtracking in the family tree. yes
This comparison should remind us of a general practical heuristic in problem
solving: it is usually best to try the simplest idea first. In our case, all the versions of
the predecessor relation are based on two ideas:

(1) the simpler idea is to check whether the two arguments of the predecessor
relation satisfy the parent relation; no no
(2) the more complicated idea is to find somebodv 'between' both people (some-
pred2( pat, pat)
body who is related to them by the parent and predecessor relations).
4)'
Of the four variations of the predecessor relation, precll does simplest things first. On l'
the contrary, pred4 always tries complicated things first. prec!2 and pred3 are in parent( pat, pat)
between the two extremes. Even without a detailed study of the execution traces, no
predl should be preferred merely on the grounds of the mle 'try simple things first'.
This rule will be in general a useful guide in programming.
Our four variations of the predecessor procedure can be further compared by
considering the question: What types of questions can particular variations answer,
parent(jim, y'")
and what types can they not answer? It turns out that predl and precl2 are both able pred2( y"", pat) parent(jim, pat)
to reach an answer for any type of question about predecessors; pred4 can never no no
(a)
reach an answer; and pred3 sometimes can and sometimes cannot. One example in
which pred3 fails is: Figure 2.17 The behaviour of three formulations of the predecessor relation on the question:
Is Tom a predecessor of Pat?
?- pred3( liz, jim).
56 Syntax and Meaning of Prolog Programs
The relation between Prolog and logic 57
pred3( X, Z) :- ·
pred3(tom, pat)
parent( X, Z).· appear annoying. One may argue: Why not simply forget about the declarative
pred3( X, Z) :- · meaning? This argument can be brought to an extreme with a clause such as:
pred3( X, Y),
parent( Y, Z). predecessor( X, Z) :- predecessor( X, Z).
pred3( tom, y'J
parent( tom, pat) parent( y', pat) which is declaratively correct, but is completely useless as a working program.
no The reason why we should not forget about the declarative meaning is that
progress in programming technology is achieved by moving away from procedural
parent( tom, Y') details toward declarative aspects, which are normally easier to formulate and
parent( y', pat) understand. The system itself, not the programmer, should carry the burden of

jl y' = bob
filling in the procedural details. Prolog does help toward this encl, although, as we
have seen in this section, it only helps partially: sometimes it does work out the
procedural details itself properly, and sornettmes it does not. The philosophy
parent( bob, pat) adopted by many is tt1at it is better to have at least some declarative meaning rather
yes than none ('none' is the case in most other programming languages). The practical
(h)
aspect of this view is that it is often rather easy to get a working program once we
have a program that is declaratively correct. Consequently, a useful practical
approach that often works is to concentrate on the declarative aspects of the
problem, then test the resulting program, and if it fails procedurally try to rearrange
the clauses and goals into a suitable order.
pred4( X, Z) :­ pred-i( torn, pat)
pred4( X, Y),
parent( Y, Z).
pred4( X, Z) :­
2.7 The relation between Prolog and logic
parent( X, Z).
pred4(tom, Y) Prolog is related to mathematical logic, so its syntax and meaning can be specified
parent( y', pat)
most concisely with references to logic. Prolog is indeed often defined that way.
However, such an introduction to Prolog assumes that the reader is familiar with
certain concepts of mathematical logic. These concepts are, on the other hand,
pred4( tom, Y")
certainly not necessary for understanding and using Prolog as a programming tool,
parent( y'', v') which is the aim of this book. For the reader who is especially interested in the
parent( y', pat) relation between l'rolog and logic, the following are some basic links to mathemat­
ical logic, together with some appropriate references.
Prolog's syntax is that of the fzrst-order predicate logic formulas written in the so­
called clause form (a conjunctive normal form in which quantifiers are not explicitly
pred4( tom, y"') written), and further restricted to Horn clauses only (clauses that have at most one
parent( y'", Y")
parent( y", Y'J positive literal). Clocksin and Mellish (1987) give a Prolog program that transforms a
parent( y', pat) first-order predicate calculus formula into the clause form. The procedural meaning
of Prolog is based on the resolution principle for mechanical theorem proving
introduced by Robinson in his classic paper (1965). Prolog uses a special strategy
(c) for resolution theorem proving called SLD. An introduction to the first-order
predicate calculus and resolution-based theorem proving can be found in several
Figure 2.17 contd general books on artificial intelligence (Genesereth and Nilsson 1987; Ginsberg
1993; Poole eta/. 1998; Russell and Norvig 1995; see also Flach 1994). Mathematical
58 Syntax and Meaning of Prolog Programs References 59

questions regarding the properties of Prolog's procedural meaning with respect to • Matching, if it succeeds, results in the most general instantiation of variables.
logic are analyzed by Lloyd (1991). • The declarative semantics of Prolog defines whether a goal is true with respect to a
Matching in Prolog corresponds to what is called 1111ifzcatio11 in logic. However, we given program, and if it is true, for what instantiation of variables it is true.
avoid the word unification because matching, for efficiency reasons in most Prolog • A comma between goals means the conjunction of goals. A semicolon between
systems, is implemented in a way that does not exactly correspond to unification
goals means the disjunction of goals.
(see Exercise 2.10). But from the practical point of view this approximation to
unification is quite adequate. Proper unification requires the so-called ocrnrs check:
• The procedural semantics of Prolog is a procedure for satisfying a list of goals in
does a given variable occur in a given term? The occurs check would make matching the context of a given program. The procedure outputs the truth or falsity of the
inefficient. goal list and the corresponding instantiations of variables. The procedure
automatically backtracks to examine alternatives.
• The declarative meaning of programs in 'pure Prolog' does not depend on the
Exercise order of clauses and the order of goals in clauses.
• The procedural meaning does depend on the order of goals and clauses. Thus the
2.10 What happens if we ask Prolog: order can affect the efficiency of the program; an unsuitable order may even lead
?- X = f( X). to infinite recursive calls.

Should this request for matching succeed or fail? According to the definition of
• Given a declaratively correct program, changing the order of clauses and goals
can improve the program's efficiency while retaining its declarative correctness.
unification in logic this should fail, but what happens according to om definition of
Reordering is one method of preventing indefinite looping.
matching in Section 2.27 Try to explain why many Prolog implementations answer
the question above with: • There are other more general techniques, apart from reordering, to prevent
indefinite looping and thereby make programs procedurally robust.
X = f(f(f(f(f(f(f(f(f(f(f(f(f(f( ...
• Concepts discussed in this chapter are:
data objects: atom, number, variable, structure
term
?.�r:'.:.r.1�_rY....................................................... .... ······ ················· ································ . functor, arity of a functor
principal functor of a term
So far we have covered a kind of basic Prolog, also called 'pure Prolog'. lt is 'pure' matching of terms
because it corresponds closely to formal logic. Extensions whose aim is to tailor the most general instantiation
language toward some practical needs will be covered later in the book (Chapters 3, declarative semantics
5, 6, 7). Important points of this chapter are: instance of a clause, variant of a clause
• procedural semantics
Simple objects in Prolog are atoms, variables and numbers. Structured objects, or
executing goals
structures, are used to represent objects that have several components.
• Structures are constructed by means of (zmctors. Each functor is defined by its
name and arity.
References
• The type of object is recognized entirely by its syntactic form.
• The lexical scope of variables is one clause. Thus the same variable name in two Clocksin, W.F. and Mellish, C.S. (1987) Programming in Prolog, second edition. Berlin: Springer­
clauses means two different variables. Verlag.
Flach, P. (1994) Simply Logical: Intelligent Reasoning by Example. Chichester, UK: Wiley.
• Structures can be naturally pictured as trees. Prolog can be viewed as a language Genesereth, M.R. and Nilsson, N.J. (1987) Logical Foundation o(Artif,cial Intelligence. Palo Alto,
for processing trees. CA: Morgan Kaufmann.
• The matching operation takes two terms and tries to make them identical by Ginsberg, M. (1993) Essentials o(Artificial Intelligence. San Francisco, CA: Morgan Kaufmann.
instantiating the variables in both terms. Lloyd, J.W. (1991) Foundations o(Logic Programming, second edition. Berlin: Springer-Verlag.
 60 Syntax and Meaning of Prolog Programs

Robinson, A.J. (1965) A machine-oriented logic basec! on the resolution principle. JAC!vf 12: chapter 3
23-41.
Poole, D., Mackworth, A. and Gaebel, R. (1998) Computational Intelligence: A Logical Approach.

Lists, Operators, Arithmetic

Oxford University Press.
Russell, S. and Norvig, P. (1995) Artificial Intelligence: A Modem Approach. Englewood Cliffs, NJ:
Prentice flail.

3.1 Representation of lists 61

3.2 Some operations on lists 64
3.3 Operator notation 74
3.4 Arithmetic 80

In this chapter we will study a special notation for lists, one of the simplest and most
useful structures, and some programs for typical operations on lists. We will also
look at simple arithmetic and the operator notation, which often improves the
readability of programs. Basic Prolog of Chapter 2, extended with these three
additions, becomes a convenient framework for writing interesting programs.

3.1 Representation of lists

· · · · · · ·········· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·· · · · · · · · · · · · · ·· · · · · · · · · · · · · · · · · ·· · · · · · · ·········

The list is a simple data structure widely used in non-numeric programming. A list is
a sequence of any number of items, such as ann, tennis, tom, skiing. Such a list can be
written in Prolog as:
[ ann, tennis, tom, skiing]
This is, however, only the external appearance of lists. As we have already seen in
Chapter 2, all structured objects in Prolog are trees. Lists are no exception to this.
How can a list be represented as a standard Prolog object? We have to consider
two cases: the list is either empty or non-empty. In the first case, the list is simply
written as a Prolog atom,[]. In the second case, the list can be viewed as consisting
of two things:
%]

(1) the first item, called the head of the list;

(2) the remaining part of the list, called the tail.

61
62 Lists, Operators, Arithmetic
Representation of lists 63

For our example list,

only a cosmetic improvement and that our lists will be internally represented as
[ ann, tennis, tom, skiing] binary trees. When such terms are output they will be automatically converted into
the head is arrn and the tail is the list: their neater form. Thus the following conversation with Prolog is possible:

[ tennis, tom, skiing] ?- Listl = [a,b,c],

List2 = .(a, .(b, .(c, [ ]) ) ).
In general, the head can be anything (any Prolog object, for example, a tree or a Listl = [a,b,c]
variable); tl1e tail has to be a list. The head and the tail are then combined into List2 =[a,b,c]
a structure by a special functor,
?- Hobbies! =.(tennis, .(music, [ ]) ) ,
.(Head, Tail) Hobbies2 =[ skiing, food],
L =[ ann, Hobbies 1, tom, Hobbies2].
Since Tail is in tum a list, it is either empty or it has its own head and tail. Therefore,
I-lobbiesl = [ tennis, music]
to represent lists of any length no additional principle is needed. Our example list is
Hobbies2 =[ skiing, food]
then represented as the term: L = ( ann, [tennis,music), torn, [skiing,fooc!J ]
.(arrn, .(tennis, .(tom, .(skiing, ( ] ) ) ) ) This example also reminds us that the elements of a list can be objects of any kind;
Figure 3.1 shows the corresponding tree structure. Note that the empty list appears in particular they can also be lists.
in our term. This is because the one but last tail is a single item list: It is often practical to treat the whole tail as a single object. For example, let:
( skiing] L = [a,b,c]

This list has the empty list as its tail: Then we could write:
Tail= [b,c] and L =.(a, Tail)
[ skiing] =.(skiing, ( J )
To express this in the square bracket notation for lists . Prolog provides another
This example shows how the general principle for structuring data objects in notational extension, the vertical bar, which separates the head and the tail:
Prolog also applies to lists of any length. As our example also shows, the straight­
forward notation with dots and possibly deep nesting of subterms in the taii part can L = ( a I Tail]
produce rather confusing expressions. This is the reason why Prolog provides the The vertical bar notation is in fact more general: we can list any number of elements
neater notation for lists, so that they can be written as sequences of items enclosed followed by' I' and the list of remaining items. Thus alternative ways of writing the
in square brackets. A programmer can use both notations, but the square bracket above list are:
notation is, of course, normally preferred. We will be aware, however, that this is [a,b,c] = [a I (b,c] ] = [a,b I (c] ] = [a,b,c I [11
To summarize:

ann
/� • A list is a data structure that is either empty or consists of two parts: a /zeacl and a
tail. The tail itself has to be a list.
/ �
• Lists are handled in Prolog as a special case of binary trees. For improved
tennis
readability Prolog provides a special notation for lists, th us accepting lists
/ � written as:
tom
[ Iteml, Item2, ... ]
/ �
or
skiing []
[ Head I Tail]
or
Figure 3.1 Tree representation of the list [ ann, tennis, tom, skiing].
[ Item 1, Jtem2, ... I Others]
 Some operations on lists 65
64 Lists, Operators, Arithmetic

�.°..f!l�.. �.P.�'.-�.�.i.?.�5. ..°.�.. !!��?. . ... . . . . . . . . . . . . ... . . ...... . . . . . . . . . . . . ... .

3.2 3.2.2 Concatenation
For concatenating lists we will define the relation:
Lists can be used to represent sets, although there is a difference: the order of
elements in a set does not matter while the order of items in a list does; also, the cone( Ll, L2, L3)
same object can occur repeatedly in a list. Still, the most common operations on lists Here L1 and L2 are two lists, and L3 is their concatenation. For example,
are similar to those on sets. Among them are:
cone( [a,b], [c,d], [a,b,c,d])
• checking whether some object is an element of a list, which corresponds to is true, but
checking for the set membership;
cone( [a,b], [c,d], [a,b,a,c,d])
• concatenation of two lists, obtaining a third list, which may correspond to the
union of sets; is false. In the definition of cone we will have again two cases, depending on the first
• argument, L1:
adding a new object to a list, or deleting some object from it.
(1) [f the first argument is the empty list then the second and the third arguments
In the remainder of this section we give programs for these ancl some other must be the same list (call it L); this is expressed by the following f'rolog fact:
operations on lists.
cone( [ ], L , L ).
(2) If the first argument of cone is a non-empty list then it has a head and a tail and
3.2.1 Membership must look like this:
[XI Ll]
Let us implement the membership relation as:
Figure 3.2 illustrates the concatenation of [X I L1] and some list L2. The result
member( X, L) of the concatenation is the list [X I L3] where L3 is the concatenation of L1 and
where Xis an object anc! Lis a list. The goal member( x, I.) is true if Xoccurs in L. For L2. In Prolog this is written as:
example, cone( [X I Ll], L2, [X I L3]) :­
cone( L l, L2, L3).
member( b, [a,b,c])
This program can now be used for concatenating given lists, for example:
is true,
?- cone( [a,b,c], [1,2,3], L).
member( b, [a,[b,c]])
L = [a,b,c,1,23
, ]
is not true, bLtt

=
[XI Lll
member( [b,c], [a,[b,cl])
is true. The program for the membership relation can be based on the following
observation: Ix· 1�.::···· Ji···-····-11·:---.L2-·· ·1
X is a member of L if either:
(1) Xis the head of L, or
(2) X is a member of the tail of L.
rx r"'
-,
-- :-•--"•-=-�
�=·-···,,. ��"'""t:::r:"""
L3

3
-- : --·
·r:::::r'.C:1& ',::::,....,,- -·
·:1.
,.,,,,..,,_

This can be ½'Titten in two clauses; the first is a simple fact and the second is a rule:
[XI L3]
member( X, [X I Tail]).
member( X, [Head I Tail]) Figure 3.2 Concatenation of lists.
member( X, Tail).
66 Lists, Operators, Arithmetic Some operations on lists 67

?- cone( [a,[b,cl,d], [a,[ ],bj, L). memberl( X, L) :­

L= [a, [b,c], ct, a,[ ], b] cone( Ll, [X [ L2], L).

Although the cone program looks rather simple it can be used flexibly in many other This clause says: Xis a member of list Lif Lcan be decomposed into two lists so that
ways. For example, we can use cone in the inverse direction for decomposing a given the second one has X as its head. Of course, memberl defines the same relation as
list into two lists, as follows: member. We have just used a different name to distinguish between the two
implementations. Note that the above clause can be written using anonymous
?- cone( Ll, L2, [a,b,c] ).
variables as:
L1 = (]
L2= [a,b,c]; mernberl( X, L)
L1 = [a] cone( __ , [X I_), L).
L2 = [b,cJ;
ft is interesting to compare both implementations of the membership relation,
Ll = [a,b]
L2= [c]; member and memberl. member has a rather straightforward procedural meaning,
which is as follows:
LI= [a,b,c]
L2 = []; To check whether some Xis a member of some list L:
no ( I) first check whether the head of Lis equal to X, and then
(2) check whether Xis a member of the tail of L.
It is possible to decompose the list [a,b,c] in four ways, all of which were found by
our program through backtracking. On the other hand, the declarative reading of memberl is straightforward, but its
We can also use our program to look for a certain pattern in a list. For example, procedural meaning is not so obvious. An interesting exercise is to tind how
we can find the months that precede and the months that follow a given month, as member! zictually computes something. An example execution trzice will give some
in the following goal: idea: let us consider the question:
?- cone( Before, [may I After],
[jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec] ). ?- member!( b, [a,b,cJ ).

Before= [jan,fcb,mar,apr] Figure 3.3 shows the execution trace. From the trace we can infer that member!
After= [jun,jul,aug,sep,oct,nov,dec]. behaves similc1rly to member. It scans the list, element by element, until the item in
Further we can find the immediate predecessor and the immediate successor of May question is found or the list is exhausted.
by asking:
?- cone(_ , [Monthl,may,Month2 [ _],
[jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec] ). Exercises
Monthl= apr
Month2= jun 3.1 (a) Write a goal, using cone, to delete the last three elements from a list Lproducing
another list Ll. Hint: Lis the concatenation of Ll and a three-element list.
Further still, we can, for example, delete from some list, Ll, everything that follows
(b) Write a goal to delete the first three elements and the last three elements from a
three successive occurrences of z in Ll together with the three z's. For example:
list L producing list L2.
?- Ll= [a,b,z,z,c,z,z,z,d,e],
cone( L2, [z,z,z I _], LI). 3.2 Define the relation
Ll = [a,b,z,z,c,z,z,z,d,e]
L2= [a,b,z,z,c] last( Item, List)

We have already programmed the membership relation. Using cone, however, the so that Item is the last element of a list List. Write two versions: (a) using the cone
membership relation could be elegantly programmed by the clause: relation, (b) without cone.
 Lists, Operators, Arithmetic Some operations on lists 69
68

I membcrl(b,[a,b,c])l 3 .2 .4 Deleting an item

Deleting an item, X, from a list, L, can be programmed as a relation
clel( X, L, Ll)
I conc(Ll, [biL2],[a,b,c]) I where Ll is equal to the list L with the item X removed. The de! relation can be
I\ '\ defmed similarly to the membership relation. We have, again, two cases:
1st clause of :one 2nd clause c fconc (1) If X is the head of the list then the result after the deletion is the tail of the list.
(2) If X is in the tail then it is deleted from there.
Matching: de!( X, [XI Tail], Tail).
Matching: Ll=[XIL
del( X, [YI Tail], [YI Tail l])
LI=[ l [blL2I=I.: clel( X, Tail, Tail1).
[biL2]=[a, ), CI [a,b,c]=[X LJ'j
This forces: Like member, de! is also non-deterministic. If there are several occurrences of X in
Ji1il hecause b #a
X=a,LJ'= [b,cl the list then clel will be able to delete any one of them by backtracking. Of course,
each alternative execution will only delete one occurrence of X, leaving the others
I conc(LI',[blL2].[b.c]J - untouched. For example:

no ) ?- clcl( a, [a,b,a,a], L).

1st clause of cone L = [b,a,a1;
Matching:
L = [a,b,aj;
LI'=[ l
[b!L2i=[b, c] L = [a,b,aJ;
This forces: no
L2=[c]
clel will fail if the list does not contain the item to be deleted.
yes de! can also be used in the inverse direction, to add an item to a list by inserting
the new item anywhere in the list. For example, if we want to insert a at any place
Figure 3.3 Procedure memberl finds an item in a given list by sequentially searching the list. in the list [1,2,3] then we can do this by asking the question: What is L such that after
deleting a from L we obtain (1,2,3]?
?- del( a, L, (1,2,3] ).
3.2.3 Adding an item L=[a,1,2,3];
L=[l,a,2,3];
To add an item to a list, it is easiest to put the new item in front of the list so that it
becomes the new head. If X is the new item and the list to which X is added is L then L= [1,2,a,3];
the resulting list is simply: L = (1,2,3,a];

[XI L] no

So we actually need no procedure for adding a new element in front of the list. In general, the operation of inserting X at any place in some list List giving BiggerList
Nevertheless, if we want to define such a procedure explicitly, it can be written as can be defined by the clause:
the fact: insert( X, List, BiggerList)
add( X, L, [X I L] ). clel{ X, BiggerList, List).

i
,,$�fg'.,i:f:fif}.:.;t;(J;�";�¼,U.;,},
' 'l ?i.rffJ�q��'", · ·r-;::1'".~"
70 Lists, Operators, Arithmetic Some operations on lists 71

In memherl we elegantly implemented the membership relation by using cone . Of course, the sublist procedure can be used flexibly in several ways. Although it was
We can also use de! to test for membership. The idea is simple: some Xis a member designed to check if some list occurs as a sublist within another list it can also be
of List if Xcan be deleted from List : used, for example, to find all sublists of a given list:

memher2( X, List) ?- sublist( S, [a,b,c]).

clel( X, List,_). s = [] ;
s = fa];
3.2.5 Sublist s = [a,bJ;
S = [a,b,c];
Let us now consider the sublist relation. This relation has two arguments, a list L and
s = (];
a list S such that S occurs within Las its sublist. So,
S = [bj;
sublist( [c,d,e], [a,b,c,cl ,e,tl)
is true, but
sublist( [c,e], [a,b,c,cl,e,f])
3.2.6 Permutations
is not. The Prolog program for sublist can be based on the same idea as mcmberl,
only this time the relation is more general (see Figure 3.4). Accordingly, the relation Sometimes lt is useful to generate permutations of a given list. To this end, we will
can be formulated as: define the permutation relation with two arguments. The arguments are two lists
S is a sublist of L if: such that one is a permutation of the other. The intention is to generate permuta­
( 1) L can be decomposed into two lists, L1 and L2, and tions of a list through backtracking using the pe r mutation procedure, as in the
(2) L2 can be decomposed into two lists, S and some L3. following example:

As we have seen before, the cone relation can be used for decomposing lists. So the ?- permutation( [a,b,c], P).
above formulation can be expressed in Prolog as: P = [a,b,c];
sublist( S, L) :- P = [a,c,bJ;
cone( Ll, L2 , L), I'= [b,a,c];
cone( S, L3, L2).

L The program for permut ation can be, agam, based on the consideration of two cases,

ltx·11_- .. -.',Lz ____ -_J

depending on the first list:
Li J member( X, L)
__ _______ (1) If the first list is empty then the second list must also be empty.
(2) If the first list is not empty then it has the form [X I L], and a permutation of
[XI L21
such a list can be constructed as shown in Figure 3.5: first permute L obtaining
L
L1 and then insert Xat any position into LL

t::?:C�J C--� 11 [:�:�.::-:I sublist( S, L) Two Prolog clauses that correspond to these two cases are:
permutation( [ ], []).
L2 permutation( [X I L ], P)
permutation( L , Ll),
Figure 3.4 The member and sublist relations. insert( X, Ll , P).
72 Lists, Operators, Arithmetic
Some operations on lists 73

X ,, Exercises

i
=,;;.

3J Define two predicates

permute L
evenlength( List) and oelellength( List)

so that they are true if their argument is a list of even or odd length respectively. For
r -··•····--·U ... _ . _ ... :j L1 is a permutation ofL example, the list [a,b,c,d] is 'evenlength' and [a,b,c] is 'oddlength',
insert X obtaining a permutation of [ X I L ] 3.4 Detine the relation

Figure 3.5 One way of constructing a permutation of the list [X I L]. reverse( List, ReverseelList)

that reverses lists. For example, reverse( [a,b,c,c!], [d,c,b,a] ).

One alternative to this program would be to delete an element, X, from the first list,
permute the rest of it obtaining a list P, and then add X in front of P. The 3.5 Define the predicate palindrome( List). A list is a palindrome if it reads the same in
corresponding program is: the forward and in the backward direction. For example, [m,a,d,a,m).

permutation2( [ ], [ ] ). 3.6 Define the relation

perrnutation2( L, [X I PJ ) shift( List 1, List2)
del( X, L, Ll),
permutation2( Ll, I'). so that List2 is Listi 'shifted rotationally' by one element to the left. For example,
It is instructive to do some experiments with our permutation programs. Its ?- shift( [1,2,3,4,5), Ll),
normal use would be something like this: shift( Ll, LZ).
?- permutation( [red,blue,greenj, P). produces:
This would result in all six permutations, as intended: Ll = [2,3,4,5,1]
P = [ red, blue, green]; L2 = (3,4,5, 1,2]
P = [ reel, green, blue]; 3.7 Define the relation
P = [ blue, red, green];
translate( Listl, List2)
P = [ blue, green, reel);
P = [ green, reel, blue]; to translate a list of numbers between O and 9 to a list of the corresponding words.
For example:
P = [ green, blue, reel];
no translate( (3,5,1,31, [three,five,one,threej )

Another attempt to use permutation is: Use the following as an auxiliary relation:

?- permutation( L, [a,b,c] ). means( 0, zero). means( 1, one). means( 2, two).

Our first version, permutation, will now instantiate L successfully to all six permuta­ JS Define the relation
tions. If the user then requests more solutions, the program would never answer 'no'
subset( Set, Subset)
because it would get into an infinite loop trying to find another permutation when
there is none. Our second version, permutation2, will in this case find only the first where Set and Subset are two lists representing two sets. We would like to be able to
(identical) permutation and then immediately get into an infinite loop. Thus, some use this relation not only to check for the subset relation, but also to generate all
care is necessary when using these permutation programs. possible subsets of a given set. For example:
74 Lists, Operators, Arithmetic Operator notation 75

/�
?- subset( [a,b,c], S).
S = [a,b,c];

/�
S = [a,b]; * *
S = [a,c];
S = [a];
/ �

S = [b,c];
Figure 3.6 Tree representation of the expressio1 2,a + b,c.
S = [b];

Since we would normally prefer to have such expressions written in the usual, infix
3.9 Defir1e the relation
style with operators, Prolog caters for this notational convenience. Prolog will
cliviclelist( Li t, Listl, List2)
0
therefore accept our expression written simply as:
so that the elements of List are partitioned between Listl and List2, and List! and List2 2*a + b,c
are of approximately the same length. For example, cliviclelist( [a,b,c,cl,e], [a,c,e], [b,d] ). This will be, however, only the external representation of this object, which will
3.10 Rewrite the monkey and banana program of Chapter 2 as the relation be automatically converted intv the usual form of Prolog terms. Such a term will be
output for the user, again, in its external, infix form.
canget( State, Actions)
Thus operators in Prolog are merely a notational extension. If we write a+ b,
to answer not just 'yes' or 'no', but to produce a sequence of monkey's actions Prolog will handle it exactly as if it had been written +(a,b). In order that Prolog
represented as a list of moves. For example: properly understands expressions such as a - b,c, Prolog has to know that * binds
stronger than+. We say that -c has higher precedence than,. So the precedence of
Actions= [ walk(door,winc!ow), push(winclow,mic!c!le), climb, grasp]
operators decides what is the correct interpretation of expressions. For example, the
3.11 Define the relation expression a+ b,c can be, in principle, understood either as
flatten( List, FlatList) +( a, ,(b,c))
where List can be a list of lists, and FlatList is List 'flattened' so that the elements of or as
List's sublists (or sub-sublists) are reorganized as one plain list. For example: ,( +(a,b), c)
?- flatten( [a,b,[c,cl],[ ],[[[ell],t], L ). The general rule is that the operator with the highest precedence is the principal
L = [a,b,c,cl,e,f] functor of the term. If expressions containing + and , are to be understood
according to our normal conventions, then + has to have a higher precedence than
*· Then the expression a+ !J,c means the same as a + (b,c). If another interpretation
is intended, then it has to be explicitly indicated by parentheses - for example,
3.3 Operator notation
···· • • ······························································································································· ····· (a+ b)*c.
A programmer can define his or her own operators. So, for example, we can detine
In mathematics we are used to writing expressions like the atoms has and supports as intix operators and then write in the program facts
2•a + b•c like:

where + and * are operators, and 2, a, b, are arguments. In particular, + and * are peter has information.
floor supports table.
said to be infix operators because they appear between the two arguments. Such
expressions can be represented as trees, as in Figure 3.6, and can be written as Prolog These facts are exactly equivalent to:
terms with + and * as functors:
has( peter, information).
+( ,(2,a), ,(b,c) ) supports( floor, table).
76 Lists, Operators, Arithmetic Operator notation 77

A programmer can define new operators by inserting into the program special
kinds of clauses, sometimes called directives, which act as operator definitions. An
operator definition must appear in the program before any expression containing
that operator. For our example, the operator has can be properly defined by the
directive:
:- op( 600, xfx, has).
This tells Prolog that we want to use 'has' as an operator, whose precedence is 600 precedence 500 precedence 500
and its type is 'xfx', which is a kind of infix operator. The form of the specifier 'xfx'
suggests that the operator, denoted by 'f', is between the two arguments denoted Figure 3.7 Two interpretations of the expres,ion a - b - c assuming that' - ' has
by 'x'. precedence 500. If' - ' is of type yfx, then interpretation 2 is invalid because
Notice that operator definitions do not specif\• any operation or action. In the precedence of b - c is not less than the precedence of' -'.
principle, 110 uperntion 011 data is associated wit/; cm operator (except in very special
cases). Operators are normally used, as functors, only to combine objects into
structures and not to invoke actions on data, although the word 'operator' appears is normally understood as (a - b) - c, and not as a (b - c). To achieve the normal
to suggest an action. interpretation the operator ' - ' has to be defined as yfx. Figure 3. 7 shows why the
Operator names are atoms. An operator's precedence must be in some range second interpretation is then ruled out.
which depends on the implementation. We will assume that the range is between As another example consider the prefix operator not. If not is defined as fy then
1 and 1200. the expression
There are three groups of operator types which are indicated by type specifiers not not p
such as xfx. The three groups are:
is legal; but if not is defined as fx then this expression is illegal because the argument
(l) infix operators of three types:
to the first not is not p, which has the same precedence as not itself. [n this case the
xfx xfy yfx expression has to be written with parentheses:
(2) prefix operators of two types: not( not p)
fx fy
For convenience, some operators are predefined in the Prolog system so that they
(3) postfix operators of two types: can be readily used, and no definition is needed for them. What these operators are
xf yf and what their precedences are depends on the implementation of Prolog. We
will assume that this set of 'standard' operators is as if defined by the clauses in
The specifiers are chosen so as to reflect the structure of the expression where 'f'
Figure 3.8. The operators in this figure are a subset of those defined in the Prolog
represents the operator and 'x' and 'y' represent arguments. An 'f' appearing between
standard, plus the operator not. As Figure 3.8 also shows, several operators can be
the arguments indicates that the operator is infix. The prefix and postfix specifiers
declared by one clause if they all have the same precedence and if they are all of the
have only one argument, which follows or precedes the operator respectively.
same type. In this case the operators' names are written as a list.
There is a difference between 'x' and 'y'. To explain this we need to introduce the
The use of operators can greatly improve the readability of programs. As an
notion of the precedence o(argumerzt. If an argument is enclosed in parentheses or it is
example let us assume that we are writing a program for manipulating Boolean
an unstructured object then its precedence is O; if an argument is a structure then its
expressions. In such a program we may want to state, for example, one of de
precedence is equal to the precedence of its principal functor. 'x' represents an
Morgan's equivalence theorems, which can in mathematics be written as:
argument whose precedence must be strictly lower than that of the operator. 'y'
represents an argument whose precedence is lower or equal to that of the operator. ~(A & B) <=> ~Av ~B
These rules help to disambiguate expressions with several operators of the same
precedence. For example, the expression One way to state this in Prolog is by the clause:

a-b-c equivalence( not( and( A, B)), or( not( A), not( B) ) ).

 \�\:�«:.&� v ;;z;;;;z;:;z;:;J �¼. rn�se&.<i

78 Lists, Operators, Arithmetic Operator notation 79

<===>
op( 1200, xfx, [:-,-->l ).

/
op( 1200, fx [:-, ?-] ).
op( 1100,xfy, ';' ).
op( 1050, xfy, -> ). �

/�
op( 1000, xfy, ',' ).
op( 900, fy, [not,'\+')).
op( 700, xfx, [=, \=,==, \==,=-- l ).
&
/�
op( 700, xfx, [is,=:=,=\=,<,=<,> ,>=,@<,@=<,@>,@>=)).
op( 500, yfx, [+ ,- ) ).
op( 400, yfx, [ ,, /, //, mod]). A B A ll
op( 200, xfx, ,,).
op( 200, xfy, A).
Figure 3.9 Interpretation of the term ~(A & B) <===>~Av~B.
op( 200, fy, - ).

• The type of an operator depends on two things: (1) the position of the operator
Figure 3.8 A set of predefined operators. with respect to the arguments, and (2) the precedence of the arguments
compared to the precedence of the operator itself. In a specifier like xfy, x
However, it is in general a good programming practice to try to retain as much indicates an argument whose precedence is strictly lower than that of the
resemblance as possible between the original problem notation and the notation operator; y indicates an argument whose precedence is less than or equal to
used in the program. In our example, this can be achieved almost completely by that of the operator.
using operators. A suitable set of operators for our purpose can be defined as:
op( 800, xfx,<===>). Exercises
op( 700, xfy, v).
op( 600, xfy, &). 3.12 Assuming the operator definitions
op( 500, fy, ~).
op( 300, xfx, plays).
Now the de Morgan's theorem can be written as the fact: op( 200, xfy, and).
~(A & B) <===>~Av ~B.
then the following two terms are syntactically legal objects:
According to our specification of operators above, this term is understood as shown Terml = jimmy plays football and squash
in Figure 3.9. Term2 = susan plays tennis and basketball and volleyball
To summarize:
How are these terms understood by Prolog? What are their principal functors and
• The readability of programs can be often improved by using the operator what is their structure?
notation. Operators can be infix, prefix or postfix.
3.13 Suggest an appropriate definition of operators ('was', 'of', 'the') to be able to write
• In principle, no operation on data is associated with an operator except in clauses like
special cases. Operator definitions do not define any action, they only introduce
new notation. Operators, as functors, only hold together components of diana was the secretary of the department.
structures. and then ask Prolog:
• A programmer can define his or her own operators. Each operator is defined by
?- Who was the secretary of the department.
its name, precedence and type.
'Who = diana
• The precedence is an integer within some range, usually between l and 1200.
The operator with the highest precedence in the expression is the principal ?- diana was What.
functor of the expression. Operators with lowest precedence bind strongest. What = the secretary of the department
80 Lists, Operators, Arithmetic Arithmetic 81

3.14 Consider the program: will be necessary. The following question is a naive attempt to request arithmetic
computation:
t( O+l, H-0).
t( X+-0+1, X-<l+O). ?- X=l + 2.
t( X+l+l, Z) :- Prolog will 'quietly' answer
t( X+l, XI),
t( Xl+l, Z). X=1+2

How will this program answer the following questions if'+' is an infix operator of and not X = 3 as we might possibly expect. The reason is simple: the expression
type yfx (as usual): 1 + 2 merely denotes a Prolog term where + is the functor and 1 and 2 are its
arguments. There is nothing in the above goal to force Prolog to actually activate
(a) ?- t( O+ 1, A). the addition operation. A special predefined operator, is, is provided to circumvent
(b) ?- t( O+l-;-1, B). this problem. The is operator will force evaluation. So the right wc1y to invoke
(c) ?- t( l�0-0 1-rl+l, C). arithmetic is:
(d) ?- t( D, l+l+l+O). ?- Xis 1 +2.
3.15 In the previous section, relations involving lists were written as: Now the answer will be:
member( Element, List), X =3
cone( List 1, List2, List3),
del( Element, List, Newl.ist), ... The addition here was carried out by a special procedure that is associated with the
operator is. We call such procedures built-in procedures.
Suppose that we would prefer to write these relations as:
Different implementations of Prolog may use somewhat different notations for
Element in List, arithmetics. For example, the '/' operator may denote integer division or real
concatenating List! and List2 gives List3, division. In this book, '/' denotes real division, the operator // denotes integer
deleting Element from List gives Newl.ist, ... division, and mod denotes the remainder. Accordingly, the question:
Define 'in', 'concatenating', 'and', etc. as operators to make this possible. Also, ?- X is 5/2,
redefine the corresponding procedures. Yis 5//2,
Z is 5 mod 2.
is answered by:
3.4 Arithmetic X 2.5
Y=2
Some of the predefined operators can be used for basic arithmetic operations. These Z =l
are:
The left argument of the is operator is a simple object. The right argument is an
+ addition arithmetic expression composed of arithmetic operators, numbers and variables.
subtraction Since the is operator will force the evaluation, all the variables in the expression
multiplication must already be instantiated to numbers at the time of execution of this goal. The
division precedence of the predefined arithmetic operators (see Figure 3.8) is such that the
** power associativity of arguments with operators is the same as normally in mathematics.
II integer division Parentheses can be used to indicate different associations. Note that +, -, *,/ and div
mod modulo, the remainder of integer division are defined as yfx, which means that evaluation is carried out from left to right. For
example,
Notice that this is an exceptional case in which an operator may in fact invoke
an operation. But even in such cases an additional indication to perform arithmetic Xis 5-2-l
 , ,,;;;;_i�� ¥� =__,»

w
,,;;!;,"

82 Lists, Operators, Arithmetic Arithmetic 83

is interpreted as: Let us further illustrate the use of arithmetic operations by two simple examples.
The first is computing the greatest common divisor; the second.. counting the items
Xis (5 - 2) - I
in a list.
Prolog implementations usually also provide standard functions such as sin(X), Given two positive integers, X and Y, their greatest common divisor, D, can be
cos(X), atan(X), log(X), exp(X), etc. These functions can appear to the right of found according to three cases:
operator is. (1) If X and Y are equal then D is equal to X.
Arithmetic is also involved when comparing numerical values. We can, for
(2) If X < Y then D is equal to the greatest common divisor of X and the difference
example, test whether the product of 277 and 37 is greater than 10000 by the goal:
y - X.
?- 277, 37 > 10000. (3) If Y < X then do the same as in case (2) with X and Y interchanged.
yes
It can be easily shown by an example that these three rules actually work. Choosing,
Note that, similarly to is, the'>' operator also forces the evaluation. for example, X == 20 and Y == 25, the above rules would give D == 5 after a sequence
Suppose that we have in the program a relation born that relates the names of of subtractions.
people with their birth years. Then we can retrieve the names of people born These rules can be formulated into a Prolog program by defining a three­
between 1980 and 1990 inclusive with the following question: argument relation, say:

?- born( Name, Year), gcd( X, Y, D)

Year >= 1980,
The three rules are then expressed as three clauses, as follows:
Year �, < 1990.
gcd( X, X, X).
The comparison operators are as follows:
gcd( X, Y, D) :-
X > y X is greater than Y X < Y,
X < y X is less than Y Yl is Y - X,
X >= y X is greater than or equal to Y gcd( X, Yl, D).
X =< y X is less than or equal to Y gcd( X, Y, D) :­
X =:= y the values of X and Y are equal y < X,
X =\= y the values of X and Y are not equal gcd( Y, X, D).

Notice the difference between the matching operator'=' and'==:=='; for example, in Of course, the last goal in the third clause could be equivalently replaced by the two
the goals X = Y and X =: = Y. The first goal will cause the matching of the objects X goals:
and Y, and will, if X and Y match, possibly instantiate some variables in X and Y. Xl is X - Y,
There will be no evaluation. On the other hand, X =: = Y causes the arithmetic gcd( Xl, Y, D)
evaluation and cannot cause any instantiation of variables. These differences are
Our next example involves counting, which usually requires some arithmetic. An
illustrated by the following examples:
example of such a task is to establish the length of a list; that is, we have to count the
?- 1 + 2 =: = 2 + 1. items in the list. Let us define the procedure:
yes length( List, N)
?- 1 + 2 = 2 + 1. which will count the elements in a list List and instantiate N to their number. As was
no the case with our previous relations involving lists, it is useful to consider two cases:

?- 1 +A= B + 2. (1) If the list is empty then its length is 0.

A=2 (2) If the list is not empty then List = [Head I Tail]; then its length is equal to 1 plus
B=l the length of the tail Tail.
3-1 Lrs:s, O�'s?r2:2:S, .4rithrnetic Arithmetic 85

These two cases correspond to the following program: ?- length!( (a,b,c], N), Length is N.
N = l+(l+(l+O))
kn:;th\ [ ], 0). Length= 3
k�th\ [_ I Tail], NJ
kngth( Tail, Nl), Finally we note that the predicate length is often provided as a built-in predicate.
\ is 1 - '.'il. To summarize:

\,1 J,•�1iication of length can be: • Built-in procedures can be used for doing arithmetic.
• Arithmetic operations have to be explicitly requested by the built-in procedure
> kn:;th( [a,b,[c,d],e], N).
is. There are built-in procedures associated with the predefmed operators +, -, *,
-f
\ C
/, div and mod.
\,•:,, :hJt in the second clause of length, the two goals of the body cannot be • At the time that evaluation is carried out, all arguments must be already
,,,.1c·:·eJ. The reason for this is that Nl has to be instantiated before the goal: instantiated to numbers.
'\ c, 1 - '\'] • The values of arithmetic expressions can be compared by operators such as<,=<,
etc. These operators force the evaluation of their arguments.
,·.,:1 ·:-,:,processed.With the built-in procedure is, a relation has been introduced that
:, •<>iti,•e to the order of processing and therefore the procedural considerations
:'.2,·,· :,,,:c1me vital.
l: :s interesting to see what happens if we try to program the length relation Exercises
"::''..'Ut the use of is. Such an attempt can be:
3.16 Define the relation
c(Cl:,:th 1 ( [ ], 0).
max( X, Y, Max)
k'.,:;th ll [_ I Tail], N)
1 en�h 1( Tail, Nl),
so that Max is the greater of two numbers X and Y.
'\' = 1-Nl.
3.17 Define the predicate
\,._---,., the goal
maxlist( List, Max)
:- kngthl( [a,b,[c,d],e], N).
so that Max is the greatest number in the list of numbers List.
-.,::: :1rL-.iuce the answer:
3.18 Define the predicate
'\ = 1-\1-(l+(l+0))).
sumlist( List, Sum)
:·::e 1J..iition was never explicitly forced and was therefore not carried out at all. But
so that Sum is the sum of a given list of numbers List.
::: :.,ugthl we can, unlike in length, swap the goals in the second clause:
:eugthl\ [_ I Tail], N)
3.19 Define the predicate
'\' = 1 - Nl, ordered( List)
kngthl( Tail, Nl).
which is true if List is &,1 ordered list of numbers. For example,
:"::::- wrsion of lengthl will produce the same result as the original version. It can
ordered( (1,5,6,6,9,12] ).
i...--..· o,: written shorter, as follows,
:engthl( [_ I Tail], l + N)
3.20 Define the predicate
lengthl( Tail, N). subsum( Set, Sum, SubSet)
:el producing the same result. We can, however, use lengthl to find the number of so that Set is a list of numbers, SubSet is a subset of these numbers, and the sum of
e:e'll.e1.1ts in a list as follows: the numbers in SubSet is Sum. For example:
86 Lists, Operators, Arithmetic Summary 87

?- subsum( [1,2,5,3,2), 5, Sub). • The operator notation allows the programmer to tailor the syntax of programs
Suh= [1,2,2]; toward particular needs. Using operators the readability of programs can be
greatly improved.
Sub= [2,3];
• New operators are defined by the directive op, stating the name of an operator,
Sub= (5];
its type and precedence.
• In principle, there is no operation associated with an operator; operators are
3.21 Define the procedure merely a syntactic device providing an alternative syntax for terms.
between( Nl, NZ, X) • Arithmetic is done by built-in procedures. Evaluation of an arithmetic expres­
sion is forced by the procedure is and by the comparison predicates <, = <, etc.
which, for two given integers Nl and N2, generates through backtracking all the
integers X that satisfy the constraint Nl §; X §; N2.
• Concepts introduced in this chapter are:
list, head of list, tail of list
3.22 Define the operators 'if', 'then', 'else' and':=' so that the following becomes a legal list notation
term: operators, operator notation
if X > Y then Z := X else Z := Y infix, prefix and suffix operators
precedence of an operator
Choose the precedences so that 'if' will be the principal functor. Then define the
arithmetic built-in procedures
relation 'if' as a small interpreter for a kind of 'if-then-else' statement of the form
if Val1 > Val2 then Var:= Val3 else Var:= Val4
where Vall, Val2, Val3 and Val4 are numbers (or variables instantiated to numbers)
and Var is a variable. The meaning of the 'if' relation should be: if the value of Vall is
greater than the value of Val2 then Var is instantiated to Val3, otherwise to Val4.
Here is an example of the use of this interpreter:
?- X= 2, Y= 3,
Val2 is 2.,x,
Val4 is 4,X,
if Y > Val2 then Z := Y else Z := Val4,
if Z > 5 then W : = 1 else W := 0.
X= 2
y =3
Z =8
W= 1
Val2= 4
Val4 = 8

Summary
······· ·················-················································································································
• The list is a frequently used structure. It is either empty or consists of a head and
a tail which is a list as well. Prolog provides a special notation for lists.
• Common operations on lists, programmed in this chapter, are: list membership,
concatenation, adding an item, deleting an item, sublist.
 Retrieving structured information from a database 89

chapter 4
family

pers,�J�.

Using Structures: Example Programs

---
to�c�:: -works a,([5::�nplo.ed perso� � ·
//\__ I\
7 may 1960 bbc 152011
/I� . //�
9 ITU!) 1961 pat fox date unernploJed
/�
person [I
4.1 Retrieving structured information from a database 88 //\ may 1983
II�
jim fox date unemployed
4.2 Doing data abstraction 92
/!�
5 may !98J
4.3 Simulating a non-deterministic automaton 94
1-4 Travel agent 98 Figure 4.1 Structuring information about the family.

t_S The eight queens problem 103

family(
person( tom, fox, date(7,may,1960), works(bbc,15200) ),
person( arm, fox, clate(9,may,1961), unemployed),
[ person( pat, fox, clate(S,may,1983), unemployed),
person( jim, fox, date(S,may, 1983), unemployed) ] ).

Data structures, with matching, backtracking and arithmetic, are a powerful Our database would then be comprised of a sequence of facts like this describing all
programming tool. In this chapter we will develop the skill of using this tool families that are of interest to our program.
through programming examples: retrieving structured information from a database, Prolog is, in fact, a very suitable language for retrieving the desired information
simulating a non-deterministic automaton, travel planning, and eight queens on from such a database. One nice thing about Prolog is that we can refer to objects
the chessboard. We will also see how the principle of data abstraction can be carried without actually specifying all the components of these objects. We can merely
out in Prolog. The programming examples in this chapter can be read selectively. indicate the stnicture of objects that we are interested in, and leave the particular
components in the structures unspecified or only partially specified. Figure 4.2
shows some examples. So we can refer to all Armstrong families by:

4.1 Retrieving structured information from a database

······································•·························································································
family( person(_, armstrong,_,_), _, _)

The underscore characters denote different anonymous variables; we do not care

This exercise develops techniques of representing and manipulating structured data about their values. Further, we can refer to all families with three children by the
objects. It also illustrates Prolog as a natural database query language. term:
A database can be naturally represented in Prolog as a set of facts. For example, a
family(_,_,[_,_,_])
database about families can be represented so that each family is described by one
clause. Figure 4.1 shows how the information about each family can be structured. To find all married women that have at least three children we can pose the
Each family has three components: husband, wife and children. As the number of question:
children varies from family to family the children are represented by a list that is
?- family(_, person( Name, Surname,_,_),[_,_, -1 _] ).
capable of accommodating any number of items. Each person is, in turn, repres­
ented by a structure of four components: name, surname, date of birth, job. The job The point of these examples is that we can specify objects of interest not by
information is 'unemployed', or it specifies the working organization and salary. The their content, but by their structure. We only indicate their structure and leave their
family of Figure 4.1 can be stored in the database by the clause: arguments as unspecified slots.

38
90 Using Structures: Example Programs Retrieving str�ctured information from a database 91

(b) famiil clateofbirth(pe rson(_,_, Date,_), Date).

/I�
1· �
sala ry(person( _,_,_, wo rks(_, S)), $). % Salary of working person

(;,) person/1"� sala ry(person(_,_,_,unemployed),0). 'ro Salary of unemployed

1·�
/.!.�
_ _
We can use these utilities, for example, in the following queries to the database:

1·� 11
• Find the names of all the people in the database:

?- exists(pe rson( Name , Surname ,_,_)).

• Find all children born in 2000:

?- child( X),

�!,.,
( c) farnil� dateotbirth( X ,date(_,_, 2000))-

-<r!ia� /�1·�
Find all employed wives:

>�
?- wife( person( Name , Surname,_, works(_,_)))-
Nsme •
• Find the names of unemployed people who were born before 1973:

?- exists(person( Name, Surname,date(_ ,_, Year),unemployed)),

Yea r< 1973.
• Find people born before 1960 whose salary is less than 8000:

Figure 4.2 Specifying objects by their structural properties: (a) any Armstrong family; (b) any ?- exists( Person),
family with exactly three children; (c) any family with at least three children. ctateotlJirth( Person , elate(_,_ , Yea r)),
Structure (c) makes provision for retrieving the wife's name through the Year< 1960 ,
instantiation of the variables Name and Surname. salary( Person , Sala ry),
Salary< 8000.

• Find the names of families with at least three children:

We can provide a set of procedures that can serve as a utility to make the
interaction with the database more comfortable. Such utility procedures could be ?- family(person(_, Name,_,_),_, L,_, -1 _] ).
part of the user interface. Some useful utility procedures for our database are:
To calculate the total income of a family it is useful to define the sum of salaries of
husband( X) :­ % X is a husband a list of people as a two-argument relation:
family( X , _,_).
total( List_of_people, Sum_of_their_salaries)
wife( X) :­ % X is a wife
family(_, X , _). This relation can be programmed as:

child( X) :- % X is a child total( [],0). % Empty list ofpeople

family(_,_, Children), total( [Person I List], Sum)
member( X , Child ren). % X in list Children sala ry( Person , S), o/o S: sala ry of first person
exists( Person) :­ total( List , Rest), o/o Rest: sum of sala ries of others
% Any person in the database
husband( Person) Sum is S + Rest .

The total income of families can then be found by the question:

wife( Person)
?- family( Husband , Wife, Child ren),
child( Person). total( [Husband , Wife I Child ren], Income).
92 Using Structures: Example Programs Doing data abstraction 93

Let the length relation count the number of elements of a list, as defined in Section Let us now define some relations through which the user can access particular
3.4. Then we can specify all families that have an income per family member of less components of a family without knowing the details of Figure 4.l. Such relations
than 2000 by: can be called selectors as they select particular components. The name of such a
selector relation wiil be the name of the component to be selected. The relation will
?- family( Husband, Wife, Children),
total( [Husband, Wife I Children], Income), have two arguments: first, the object that contains the component, ancl second, the
length( [Husband, Wife I Chilc!ren], N), % :si: size of family component itself:
lncome/N < 2000.
selector_relation( Object, Component_selectec!)

Here are some selectors for the family structure:

Exercises
husband( family( Husband,_,_), Husband).
4.1 \Vrite queries to find the following from the family database: wife( family(_, Wife,_), Wife).
children( family(_,_, Chilc!List), Chilc!List).
(a) names of families without children;
(b) all employed children; We can also define selectors for particular children:
(c) names of families with employed wives and unemployed husbands; firstchilcl( Family, First) :-
(cl) all the children whose parents differ in age by at least 15 years. children( Family,[First I _] ).
4.2 Define the relation seconclchild( Family, Second) :-
children( Family,[_, Second I I).
twins( Chile!! , Chilcl2)
to find twins in the family database.
We can generalize this to selecting the Nth child:
nthchilcl( N, Family, Chile!) :-
children( Family, Chilc!List),
4.2 n th_member( N, Chilc!List, Chile!). % Nth element of a list

Another interesting object is a person. Some related selectors according to

Data abstraction can be viewed as a process of organizing various pieces of informa­
Figure 4.1 are:
tion into natural units (possibly hierarchically), thus structuring the information
into some conceptually meaningful form. Each such unit of information should be firstname( person( Name,_,_,_), Name).
easily accessible in the program. Ideally, all the details of implementing such a surname( person(_, Surname,_,_), Surname).
structure should be invisible to the user of the structure - the programmer can then
just concentrate on objects and relations between them. The point of the process is born( person(_,_, Date,_), Date).
to make the use of information possible without the programmer having to think How can we benefit from selector relations? Having defined them, we can now
about the details of how the information is actually represented. forget about the particular way that structured information is represented. To create
Let us discuss one way of carrying out this principle in Prolog. Consider our and manipulate this information, we just have to know the names of the selector
family example of the previous section again. Each family is a collection of pieces of relations and use these in the rest of the program. In the case of complicated
information. These pieces are all clustered into natural units such as a person or a representations, this is easier than always referring to the representation explicitly.
family, so they can be treated as single objects. Assume again that the family In our family example in particular, the user does not have to know that the
information is structured as in Figure 4.1. In the previous section, each family was children are represented as a list. For example, assume that we want to say that Tom
represented by a Prolog clause. Here, a family will be represented as a structured Fox and Jim Fox belong to the same family and that Jim is the second child of Tom.
object, for example: Using the selector relations above, we can define two persons, call them Personl and
FoxFamily = family( person( tom, fox,_,_),_,_) Person2, and the family. The following list of goals does this:
��rrraootWttt'::::®:Ottt'.IM( rx '. 11 )?)' ""' t:rt ifittWWXtXI i'C 'CM fiftfti¥Wif1 · 111' 1f oote Vi,J •
IC�

94 Using Structures: Example Programs Simulating a non-deterministic automaton 95

firstname( Person 1, torn), surname( Person 1, fox), % Person 1 is Tom Fox

firstnarne( Person2, jim), surname( Person2, fox), % Person2 is Jim Fox
husband( Family, Person 1),
secondchild( Family, Person2) a

As a result, the variables Person l, Person2 and Family are instantiated as:
Personl = person( tom, fox._,_)
a� / ,:x;
Person2 =person( jim, fox,_,_)
Family= family{ person( tom, fox,_,_),_, [_,person( jim, fox) I_ 1)
null
The use of selector relations also makes programs easier to modify. Imagine that
we would like to improve the efficiency of a program by changing the representation s4
�
b @, s�
,,,
of data. All we have to do is to change the defmitions of the selector relations, and
the rest of the program will work unchanged with the new representation.
Figure 4.3 An example of a non-deterministic finite automaton.

Exercise move is said to be silent because it occurs without any reading of input, and the
observer, viewing the automaton as a black box, will not be able to notice that any
4.3 Complete the definition of nthchild by defining the relation transition has occurred.
nth_member( N, List, X) The state s3 is double circled, which indicates that it is a final state. The
automaton is said to accept the input string if there is a transition path in the graph
which is true if X is the Nth member of List. such that

(1) it starts with the initial state,

(2) it ends with a final state, and
4.3 ?.i.�-�-l-�-�-i-�9- �---�-?-��?-��-���-i-�_i_s�i �--?.�-�-?��-t?.�---················································ (3) the arc labels along the path correspond to the complete input string.
It is entirely up to the automaton to decide which of the possible moves to
This exercise shows how an abstract mathematical construct can be translated into execute at any time. In particular, the automaton may choose to make or not
Prolog. In addition, our resulting program will turn out to be much more flexible
to make a silent move, if it is available in the current state. But abstract non­
than initially intended.
deterministic machines of this kind have a magic property: if there is a choice then
A non-deterministic finite automaton is an abstract machine that reads as input a
they always choose a 'right' move; that is, a move that leads to the acceptance of the
string of symbols and decides whether to accept or to reject the input string. An
input string, if such a move exists. The automaton in Figure 4.3 will, for example,
automaton has a number of states and it is always in one of the states. It can change accept the strings ab and aabaab, but it will reject the strings abb and abba. It is easy
its state by moving from the current state to another state. The internal structure of to see that this automaton accepts any string that terminates with ab, and rejects all
the automaton can be represented by a transition graph such as that in Figure 4.3. In others.
this example, 51, s2, 53 and 54 are the states of the automaton. Starting from the In Prolog, an automaton can be specified by three relations:
initial state (s 1 in our example), the automaton moves from state to state while
reading the input string. Transitions depend on the current input symbol, as (1) a unary relation final which defines the final states of the automaton;
indicated by the arc labels in the transition graph. (2) a three-argument relation trans which defines the state transitions so that
A transition occurs each time an input symbol is read. Note that transitions can
trans( S 1, X, S2)
be non-deterministic. In Figure 4.3, if the automaton is in state s 1 and the current
input symbol is a then it can transit into s 1 or s2.Some arcs are labelled null denoting means that a transition from a state Sl to S2 is possible when the current input
the 'null symbol'. These arcs correspond to 'silent moves' of the automaton. Such a symbol X is read;
 Simulating a non-deterministic automaton 97
96 Using Structures: Example Programs

first symbol rest of string

(3) a binary relation
silent( SJ, S2)
meaning that a silent move is possible from S l to S2.
�-----''
V X -v ,_ -�
(a)
For the automaton in Figure 4.3 these three relations are:
final( s3).
trans( sl, a, s1).

� ------ a
trans( sl, a, s2). string
trans( sl, b. sl).
trans( s2, b, s3).
trans( s3, b, 54). V null � V ' ' , ____ .,.. ;rry
silent( s2, s4). (b)
silent( s3, s1).
We will represent input strings as Prolog lists. So the string cwb will be represented
Figure 4.4 Accepting a string (a) by reading its first symbol X; (b) by making a silent move.
by [a. a,b]. Given the description of the automaton, the simulator will process a given
input string and decide whether the string is accepted or rejected. By definition, the
non-deterministic automaton accepts a given string if (starting from an initial state),
The program can be asked, for example, about the acceptance of the string aaab by:
after having read the whole input string, the automaton can (possibly) be in its final
state. The simulator is programmed as a binary relation, accepts, which defines the ?- accepts( sl, [a,a,a,b] ).
acceptance of a string from a given state. So
yes
accepts( State, String)
As we have already seen, Prolog programs are often able to solve more general
is true if the automaton, starting from the state State as initial state, accepts the problems than problems for which they were originally developed. In our case, we
string String. The accepts relation can be defined by three clauses. They correspond can also ask the simulator which state om automaton can be in initially so that it
to the following three cases: will accept the string ab:
( 1) The empty string, [ L is accepted from a state State if Sta te is a final state. ?- accepts( S, [a,b] ).
(2) A non-empty string is accepted from State if reading the first symbol in the S =sl;
string can bring the automaton into some state State 1, and the rest of the string
S = s3
is accepted from State 1. Figure 4.4(a) illustrates.
(3) A string is accepted from State if the automaton can make a silent move Amusingly, we can also ask: What are all the strings of length 3 that are accepted
from State to Sta tel and then accept the (whole) input string from Statel. from state s 1 ?
Figure 4.4(b) illustrates. ?- accepts( sl, [X l,X2,X3] ).
These rules can be translated into Prolog as: Xl = a
X2 =a
accepts( State, [ ] ) :­ % Accept empty string
X3 =b;
final( State).
accepts( State, [X I Rest] ) Xl =b
% Accept by reading first symbol
trans( State, X, Statel), X2 = a
accepts( State 1, Rest). X3 =b;

accepts( Sta te, String) :­ % Accept by making silent move no

silent( State, Statel), If we prefer the acceptable input strings to be typed out as lists then we can
accepts( State 1, String). formulate the question as:
 98 Using Structures: Example Programs Travel agent 99

?- String=[_,_,_ J, accepts( sl, String)_ • I have to visit Milan, Ljubljana and Zurich, starting from London on Tuesday
String=[a,a,b]; and returning to London on Friday_ In what sequence should I visit these cities
String=[b,a,b]; so that I have no more than one flight each day of the tour?
no The program will be centred around a database holding the flight information_ This
will be represented as a three-argument relation:
We can make further experiments asking even more general questions, such as:
From what states will the automaton accept input strings of length 7? timetable( Placel, Place2, ListOfF!ights)
Further experimentation could involve modifications in the structure of the where ListOfFlights is a list of structured items of the form:
automaton by changing the relations final, trans and silent_ The automaton in Figure
4_3 does not contain any cyclic 'silent path' (a path that consists only of silent DepartureTime / Arriva!Time / FlightNumber / ListOfl)ays
moves)_ If in Figure 4_3 a new transition Here the operator '/' only holds together the components of the structure, and of
silent( sl, s3) course does not mean arithmetic division_ Listomays is either a list of weekdays or
the atom allclays_ One clause of the timetable relation can be, for example:
is added then a'silent cycle' is created_ But our simulator may now get into trouble_
timetable( lonclon, eclinburgh,
For example, the question
[ 9:40 / 10:50 / ba4 733 / allclays.
?- accepts( sl, [a])- 19:40 / 20:50 / ba4833 / [mo,tu,we,th,fr,su) 1 )-

would induce the simulator to cycle in state s1 indefinitely, all the time hoping to The times are represented as structured objects with two components, hours and
find some way to the final state_ minutes, combined by the operator':'_
The main problem is to find exact routes between two given cities on a given day
of the week_ This will be programmed as a four-argument relation:
Exercises route( Placel, Place2, Day, Route)

4_4 Here Route is a sequence of flights that satisfies the following criteria:
Why could cycling not occur in the simulation of the original automaton in
Figure 4-3, when there was no'silent cycle' in the transition graph? (1) the start point of the route is Placel;
4_5 Cycling in the execution of accepts can be prevented, for example, by counting the (2) the end point is Place2;
number of moves made so far. The simulator would then be requested to search only (3) all the flights are on the same day of the week, Day;
for paths of some limited length_ Modify the accepts relation this way_ Hint: Add a (4) all the flights in Route are in the timetable relation;
third argument: the maximum number of moves allowed:
(5 ) there is enough time for transfer between flights_
accepts( State, String, MaxMoves)
The route is represented as a list of struchued objects of the form:
From / To / FlightNumber I Departure_time

4_4
!:.?.�-�_\ _
�_9_��-�--------·------------------------------------··-------------------·-------------------·---------------------------
We will also use the following auxiliary predicates:

(1) flight( Place 1, Place2, Day, FlightNum, DepTime, ArrTime)

[n this section we will construct a program that gives advice on planning air travel.
The program will be a rather simple advisor, yet it will be able to answer some useful This says that there is a flight, FlightNum, between Placel and Place2 on the day
questions, such as: of the week Day with the specified departure and arrival times_
• What days of the week is there a direct evening flight from Ljubljana to London? (2) cleptime( Route, Time)
• How can I get from Ljubljana to Edinburgh on Thursday? Departure time of Route is Time_
100 Using Structures Example Programs Travel agent 101

(3 ) transfer( Time1, Time2)

'X, A FLIGHT ROUTE PLANNER
There is at least 40 minutes between Timel and Time2, which should be :- op( SO, xfy, :).
sufficient for transfer between two t1ights. 'K, route( Place 1, Place2, Day, Route):
'¾, Route is a sequence of flights on Day, starting at Place 1, ending at Place2
The problem of finding a route is reminiscent of the simulation of the non­
route( Pl, P2, Day, [ Pl / P2 / Fnum / Deptime ]) :- % Direct flight
deterministic automaton of the previous section. The similarities of both problems
flight( Pl, P2, Day, Fnum, Deptime, _).
are as follows:
route( Pl, P2, Day, [ (Pl/P3/Fnuml/Depl) I RestRoute]) % Indirect connection
• The states of the automaton correspond to the cities. route( 1'3, P2, Day, RestRoute),
flight( Pl, P3, Day, Fnuml, Depl, Arrl),
• A transition between two states corresponds to a t1ight between two cities. deptime( RestRoute, Dep2), 1r, Departure time of Route
0

• transfer( Arrl, Oep2). % Enough time for transfer

The transition relation of the automaton corresponds to the timetable relation.
flight( Placel, Place2, Day, Fnum, Deptirne, Arrtime)
• The automaton simulator finds a path in the transition graph between the initial
timetable( Place1, Place2, Flightlist),
state and a final state; the travel planner finds a route between the start city and member( Deptime / Arrtime / Fnum / Day!ist , Flightlist),
the end city of the tour. flyday( Day, Daylist).
flyday( Day, Daylist) :­
Not surprisingly, therefore, the route relation can be defined similarly to the accepts
member( Day, Daylist).
relation, with the exception that here we have no 'silent moves'. We have two
cases: flyday( Day, alldays) :-
member( Day, [mo,tu ,we,th,fr,sa,su]).
(1) Direct flight connection: if there is a direct flight between places Place l and deptime( [ Pl / P2 / Fnum / Oep I _], Dep).
Place2 then the route consists of this flight only: transfer( Hoursl:Minsl, Hours2:Mins2) :-
60, (Hours2 - Hoursl) + Mins2 - Minsl >= 40.
route( Place 1, Place2, Day, [ Placel / Place2 / Fnum / Dep ])
flight( Place 1, Place2, Day, Fnum, Dep, Arr). member( X, [X I L]).
member( X, [Y I L]) :-
(2) Indirect flight connection: the route between places Pl and PZ consists of the member( X, L).
first flight, from Pl to some intermediate place P3, followed by a route between
'¼, A FLIGHT DATABASE
P3 to PZ. In addition, there must be enough time between the arrival of the first
timetable( edinburgh, london,
flight and the departure of the second t1ight for transfer.
[ 9:40 / 10:50 / ba4733 / al!days,
route( Pl, P2, Day, [Pl / P3 / Fnuml / Depl I RestRoute]) 13:40 / 14:50 / ba4773 / alldays,
route( P3, P2, Day, RestRoute), 19:40 / 20:50 / ba4833 / [mo,tu,we,th,fr,su]]).
flight( Pl, P3, Day, Fnuml, Depl, Arrl), timetable( london, edinburgh,
deptime( RestRoute, Dep2), [ 9:40 / 10:50 / ba4732 / al!days,
transfer( Arrl, Dep2). 11:40 / 12:50 / ba4752 / a!ldays,
18:40 / 19:50 / ba4822 / [1110,tu ,we,th,fr]]).
The auxiliary relations flight, transfer and deptime are easily programmed and are timetable( london, ljubljana,
included in the complete travel planning program in Figure 4.5. Also included is an [ 13:20 / 16:20 / jp212 / [mo,tu,we,fr,su],
example timetable database. 16:30 / 19:30 / ba473 / [mo,we,th,sa]) ).
Our route planner is extremely simple and may examine paths that obviously timetable( london, zurich,
lead nowhere. Yet it will suffice if the flight database is not large. A really large [ 9:10 / 11:45 / ba614 / a!ldays,
database would require more intelligent planning to cope with the large number of 14:45 / 17:20 / sr805 / a!ldays ] ).
potential candidate paths.
Some example questions to the program are as follows: Figure 4.5 A flight route planner and an imaginary flight timetable.
102 Using Structures: Example Programs The eight queens problem 103

?- permutation( (milan, ljubljana, zurich], (Cityl, City2, City3J ),

Figure 4.5 contd flight( lonclon, City!, tu, FNl, _, _),
flight( Cityl, City2, we, FN2, _, _),
timetable( lonclon, milan, flight( City2, City3, th, FN3, _, _),
[ 8:30 / 11:20 / bas IO / allclays, flight( City3, lonclon, fr, FN4, _, _).
11:00 / 13:50 / az459 / allclays ]).
Cityl = milan
timetable( ljubljana, Zurich, City2 = zurich
[ 11:30 / 12:40 I jp322 / [tu,th]] ). City3= ljubljana
timetable( ljubljana, london, FNl = baSIO
[ 11:10 / 12:20 / jp211 / (mo,tu,we,fr,su], FN2= sr621
20:30 / 21:30 / ba472 / [mo,we,th,sa]]). FN3 = jp323
FN4 = jp211
timetable( milan, london,
[ 9:10 / 10:00 / az458 / alldays, Finally let us note that this program is susceptible to indefinite loops, which
12:20 / 13:10 / baSll / allclays ]). happens for example if we ask it to find a route not in the timetable:
timetable( milan, zurich,
[ 9:25 / 10:15 / sr621 / alldays,
?- route ( moscow, edinburgh, mo. R).
12:45 / 13:35 / sr623 / alldays ] ). It is better therefore to keep questions safe by limiting the length of the route. We
timetable( zurich, ljubljana, can use the usual trick with cone:
[ 13:30 / 14:40 / jp323 / [tu,th]J ).
?- cone( R, __ ,[_,_,_,__ ]),route( moscow, eclinburgh, mo, R).
timetable( zurich, london,
[ 9:00 I 9:40 / ba613 / [mo,tu,we,th.fr,sa], no
16:10 / 16:55 / sr806 / [mo,tu,we,th,fr,su]]). The cone goal limits the list R to length 4 and also forces the search to consider
timetable( zurich, milan , shortest routes first.
[ 7:55 / 8:45 / sr620 / alldays ] ).

• What days of the week is there a direct evening flight from Ljubljana to London?
4.5 The eight queens problem
?- flight( ljubljana, london, Day,_, DeptHour: _, _), DeptHour >= 18. The problem here is to place eight queens on the empty chessboard in such a way
that no queen attacks any other queen. The solution will be programmed as a unary
Day= mo;
Day= we; predicate
solution( Pos)
• How crn I get from Ljubljana to Edinburgh on Thursday? which is true if and only if Pos represents a position with eight queens that do not
attack each other. It will be interesting to compare various ideas for programming
?- route( ljubljana, edinburgh, th, R).
this problem. Therefore we will present three programs based on somewhat different
R = [ ljubljana / zurich / jp322 / 11:30, zurich / london / sr806 / 16:10, representations of the problem.
london / edinburgh / ba4822 / 18:40]
• How can I visit Milan, Ljubljana and Zurich, starting from London on Tuesday
and returning to London on Friday, with no more than one flight each day of 4.5.1 Program 1
the tour? This question is somewhat trickier. It can be formulated by using the
permutation relation, programmed in Chapter 3. We are asking for a permuta­ First we have to choose a representation of the board position. One natural choice is
tion of the cities Milan, Ljubljana and Zurich such that the corresponding t1ights to represent the position by a list of eight items, each of them corresponding to one
are possible on successive days: queen. Each item in the list will specify a square of the board on which the
104 Using Structures: Example Programs The eight queens problem 105

8 •
7 • Case 2 The list of queens is non-empty: then it looks like this:

6I • [ X/Y I Others]
' •
4 • In case 2, the first queen is at some square X/Y and the other queens are at squares

• specified by the list Others. If this is to be a solution then the following conditions

• must hold:

• (1) There must be no attack between the queens in the list Others; that is, Others
123 -15678 itself must also be a solution.

Figure 4.6 A solution to the eight queens problem This position can be specified by the list (2) X and Y must be integers between 1 and 8.
[1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1]. (3) A queen at square X/Y must not attack any of the queens in the list Others.
To program the first condition we can simply use the solution relation itself. The
corresponding queen is sitting. Further, each square can be specified by a pair of second condition can be specified as follows: Y will have to be a member of the list of
coordinates (X and Y) on the board, where each coordinate is an integer between integers between 1 and 8 - that is, [1,2,3,4,5,6,7,8]. On the other hand, we do not
1 and 8. In the program we can write such a pair as: have to worry about X since the solution list will have to miltch the template in
X/Y which the X-coordinates are already specified. So X will be guaranteed to have a
proper value between 1 and 8. We can implement the third condition as another
where, of course, the '/' operator is not meant to indicate division, but simply relation, noattack. All this can then be written in Prolog as follows:
combines both coordinates together into a square. Figure 4.6 shows one solution of
the eight queens problem and its list representation. solution( [X/Y I Others]) :­
solution( Others),
Having chosen this representation, the problem is to find such a list of the form:
member( Y, [1,2,3,4,5,6,7,81 ),
[ X 1/Yl, X2/Y2, X3/Y3, ... , X8/Y8] noattack( X/Y, Others).

which satisfies the no-attack requirement. Our procedure solution will have to search It now remains to define the noattack relation:
for a proper instantiation of the variables Xl, Yl, xz, Y2, ..., XS, Y8. As we know that noattack( Q , Qlist)
all the queens will have to be in different columns to prevent vertical attacks, we can
Again, this can be broken down into two cases:
immediately constrain the choice and so make the search task easier. We can thus
fix the X-coordinates so that the solution list will fit the following, more specific (1) If the list Qlist is empty then the relation is certainly true because there is no
template: queen to be attacked.

[ 1/Yl, 2/YZ, 3/Y3, ... , 8/Y8 J (2) If Qlist is not empty then it has the form [ Q1 I Qlistl I and two conditions must
be satisfied:
We are interested in the solution on a board of size 8 by 8. However, in (a) the queen at Q must not attack the queen at Ql, and
programming, the key to the solution is often in considering a more general
(b) the queen at Q must not attack any of the queens in Qlistl.
problem. Paradoxically, it is often the case that the solution for the more general
problem is easier to formulate than that for the more specific, original problem. The To specify that a queen at some square does not attack another square is easy: the
original problem is then simply solved as a special case of the more general problem. two squares must not be in the same row, the same column or the same diagonal.
The creative part of the problem is to find the correct generalization of the Our solution template guarantees that all the queens are in different columns, so it
original problem. In our case, a good idea is to generalize the number of queens (the only remains to specify explicitly that:
number of columns in the list) from 8 to any number, including zero. The solution
• the Y-coordinates of the queens are different, and
relation can then be formulated by considering two cases:
• they are not in the same diagonal, either upward or downward; that is, the
Case 1 The list of queens is empty: the empty list is certainly a solution because distance between the squares in the X-direction must not be equal to that in
there is no attack. the Y-direction.
 ,.. ·." ...., ,.,,, vW�W.�ritf"tvt.:,�ti't.1..\.�.fr :(�· ,:;0/
' . .:::t::,'.Y\ �.:::<:0 }/"J;·>;'J:·:

106 Using Structures: Example Programs The eight queens problem 707

'¾, solution( BoardPosition) if BoardPosition is a list of non-attacking queens 4.5.2 Program 2

solution([) ).
In the board representation of program 1, each solution had the form
solution([X/Y I Others] ) % First queen at X/Y, other queens at Others
solution(Others), [ 1/Yl, 2/Y2, 3/Y3, ... , 8/Y8]
member(Y, [l,2,3,4,5,6,7,8] ), because the queens were simply placed in consecutive columns. No information is
noattack(X/Y, Others). % First queen does not attack others lost if the X-coordinates were omitted. So a more economical representation of the
noattack(_, (1 ). % Nothing to attack board position can be used, retaining only the Y-coordinates of the queens:
noattack( X/Y, [Xl/Yl I Others] )
[ Yl, Y2, Y3, ..., Y8]
Y = \ = Yl, % Different Y-coordinates
YI - Y = \ = Xl - X, %, Different diagonals To prevent the horizontal attacks, no two queens can be in the same row. This
Yl - Y = \ = X- X l, imposes a constraint on the Y-coordinates. The queens have to occupy all the rows
noattack(X/Y, Others). 1, 2, ... , 8. The choice that remains is the order of these eight numbers. Each
member( Item, [Item I Rest] ). solution is therefore represented by a permutation of the list
member(Item, [First I Rest] ) [1,2,3,4,5,6,7,8]
member(Item, Rest).
Such a permutation, S, is a solution if all the queens are safe. So we can write:
% A solution template
solution( S) :-
template([l/Yl,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8] ). permutation([1,2,3,4,5,6,7,8], S),
safe( S).
Figure 4.7 Program 1 for the eight queens probiem We have already programmed the permutation relation in Chapter 3, but the safe
relation remains to be specified. We can split its definition into two cases:

Figure 4.7 shows the complete program. To alleviate its use a template list has been (1) S is the empty list: this is certainly safe as there is nothing to be attacked.
added. This list can be retrieved in a question for generating solutions. So we can (2) S is a non-empty list of the form [Queen I Others]. This is safe if the list Others is
now ask: safe, and Queen does not attack any queen in the list Others.
?- template(S), solution( S). In Prolog, this is:
and the program will generate solutions as follows: safe([ ] ).

S = [ 1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1]; safe([Queen I Others])
safe(Others),
S = [ 1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1]; noattack(Queen, Others).
S = [ 1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1]; The noattack relation here is slightly trickier. The difficulty is that the queens'
positions are only defined by their Y-coordinates, and the X-coordinates are not
explicitly present. This problem can be circumvented by a small generalization of
the noattack relation, as illustrated in Figure 4.8. The goal
Exercise noattack(Queen,Others)

4.6 is meant to ensure that Queen does not attack Others when the X-distance between
When searching for a solution, the program of Figure 4.7 explores alternative values
Queen and Others is equal to 1. What is needed is the generalization of the
for the Y-coordinates of the queens. At which place in the program is the order of
X-distance between Queen and Others. So we add this distance as the third argument
alternatives defined? How can we easily modify the program to change the order?
of the noattack relation:
Experiment with different orders with the view of studying the time efficiency of the
program. noattack(Queen, Others, Xdist)
iC8 Using Structures: Example Programs The eight queens problem 109

(a)
I .
-I-
\
(b)

I
I• /c, solution( Queens) if Queens is a list of ¥-coordinates of eight non-attacking queens
0

solution( Queens) :-
I • I I •I permutation( (1,2,3,4,5,6,7, 8], Queens),
•
'--._

•V Others safe( Queens).

.
-'--
Queen
permutation([], [J ).
I • )
(-/ permutation([Head I Tail], PermList)
permutation( Tail, PermTail),
H I I
de!( Head, PermList, PermTail). % Insert Head in permuted Tail
X-dist = l X-dist = 3
% de!( Item, List, NewList): deleting Item from List gives NewList
de!( Item,[Item I List], List).
Figure 4.8 (a) X-distance between Queen and Others is 1. (b) X-distance between Queen
and Others is 3. de!( Item,[First I List],[First I Listl] )
de!( Item, List, Listl).
% safe( Queens) if Queens is a list of ¥-coordinates of non-attacking queens
Accordingly, the noattack goal in the safe relation has to be modified to
safe([] ).
noattack( Queen, Others, 1) safe( (Queen I Others] )
safe( Others),
The noattack relation can now be formulated according to two cases, depending on noattack( Queen, Others, 1).
the list Others: if Others is empty then there is no target and certainly no attack; if
noattack( _,[], _).
Others is non-empty then Queen must not attack the first queen in Others (which is
Xdist columns from Queen) and also the tail of Others at Xdist + 1. This leads to the noattack( Y,[Yl I Y list], Xdist)
Yl - Y =\= Xdist,
program shown in Figure 4.9.
Y Yl=\=Xdist,
Distl is Xdist + 1,
noattack( Y, Y list, Distl).
4.5.3 Program 3
Figure 4.9 Program 2 for the eight queens problem.
Our third program for the eight queens problem will be based on the following
reasoning. Each queen has to be placed on some square; that is, into some column,
some row, some upward diagonal and some downward diagonal. To make sure that The domains for all four dimensions are:
all the queens are safe, each queen must be placed in a different column, a different
row, a different upward and a different downward diagonal. It is thus natural to Dx= (1,2,3,4,5,6,7,8]
consider a richer representation with four coordinates: Dy= [1, 2, 3,4, 5,6,7,8]

x columns Du=[-7,-6,-5,-4,-3,-2,-l,0,l,2,3,4,5,6,7]
y rows Dv = [2,3,4,5,6,7,8,9,10,1 1, 1 2,1 3, 14,1 5,16]
u upward diagonals
v downward diagonals The eight queens problem can now be stated as follows: select eight 4-tuples
(X,Y,U,V) from the domains (X from Dx, Y from Dy, etc.), never using the same
The coordinates are not independent: given x and y, u and v are determined (Figure element twice from any of the domains. Of course, once X and Y are chosen, U and
4.10 illustrates). For example, as: V are determined. The solution can then be, roughly speaking, as follows: given all
four domains, select the position of the first queen, delete the corresponding items
ll=X-y from the four domains, and then use the rest of the domains for placing the rest
V=x+y of the queens. A program based on this idea is shown in Figure 4.11. The board

Mr�;J;i(�'/!,::;.J;•;;���$f�����-��".,, ;, -, ;:;' ..,.... ,,.. 2 '"' -�,,;�&<•!:: ·

110 Using Structures: Example Programs The eight queens problem 111

11 = .r- j' position is, again, represented by a list of Y-coordinates. The key relation in this
-7 -2 +7 program is
sol( Ylist, Ox,Dy,Di1, Dv)

which instantiates the Y-coordinates (in Ylist) of the queens, assuming that they are
placed in consecutive columns taken from Dx. All Y-coordinates and the corres­
ponding U and V-coordinates are taken from the lists Dy, Du and Dv. The top

�l I I J;f I I I I
procedure, solution, can be invoked by the question:
?- solution( S).
This will cause the invocation of sol with the complete domains that correspond to
the problem space of eight queens.
7 The sol procedure is general in the sense that it can be used for solving the
-k I I 'i, I I I l'
N-queens problem (on a chessboard of size N by N). It is only necessary to properly
2. 3 4 5 '6. 7 8 X set up the domains Dx, Dy, etc.
It is practical to mechanize the generation of the domains. For that we need a
procedure
2 6 16
gen( N1, N2, List)
v=x+y
which will, for two given integers Nl and N2, produce the list:
Figure 4.10 The relation between columns, rows, upward and downward diagonals. The List= [ Nl, Nl + 1, Nl + 2, .. ., NZ - 1, NZ]
indicated square has coordinates: x = 2, y = 4, u = 2 - 4 = -2, v = 2 + 4 = 6.
Such a procedure is:

'1/c, solution( Ylist) if Ylist is a list of Y-coordinates of eight non-attacking queens gen( N, N, (N] ).

solution( Ylist) :- gen( Nl, NZ, [Nl I List] )

sol( Ylist, Nl < NZ,
'¾, Y-coordinates of queens
[l,2,3 4,5,6,7,8], Mis Nl + 1,
%Domain for X-coordinates
gen( M, N2, List).
[ 1,2,3,4,5,6, 7,8], %Domain for Ycoordinates
-
[-7,-6,-5,-4,-3,-2,-1,0,l,2,3,-l,5,6,7], % Upward diagonals The top level relation, solution, has to be accordingly generalized to
[2,3,4,5,6,7,8,9,10,11,12, 13,14,15,16] ). '1/oDownward diagonals
solution( N, 5)
sol( [ ],[),Dy, Du, Dv).
sol( [YI Ylist), [XI Dxl),Dy, Du, Dv) where N is the size of the board and S is a solution represented as a list of
del( Y,Dy,Dyl), % Choose a Y-coordinate Y-coordinates of N queens. The generalized solution relation is:
U is X-Y, % Corresponding upward diagonal solution( N, S) :­
de!( U,Du,Dul), % Remove it gen( 1, N,Dxy), %Dxy - domain for X and Y
V is X+Y, % Corresponding downward diagonal Nul is 1 - N, Nu2 is N - 1,
del( V,Dv,Dvl), % Remove it gen( Nul, Nu2,Du),
sol( Ylist,Dxl,Dyl,Dul,Dvl). % Use remaining values Nv2 is N + N,
del( Item, [Item I List), List). gen( 2, Nv2,Dv),
sol( S,Dxy,Dxy,Du,Dv).
de!( Item, [First I List], [FirstI Listl])
de!( Item, List, Listl). For example, a solution to the 12-queens problem would be generated by:
?- solution( 12, S).
..
Figure 4.11 Program 3 for the eight queens problem . S = [1,3,5,8,10,12,6,11,2,7,9,4]
112 Using Structures: Example Programs Summary 113

4.5.4 Concluding remarks Summary

···················--·················································································--···························----···
The three solutions to the eight queens problem show how the same problem can be The examples of this chapter illustrate some strong points and characteristic features
approached in different ways. We also varied the representation of data. Sometimes of Prolog programming:
the representation was more economical, sometimes it was more explicit and
partially redundant. The drawback of the more economical representation is that • A database can be naturally represented as a set of Prolog facts.
some information always has to be recomputed when it is required. • Prolog's mechanisms of querying and matching can be flexibly used for retriev­
At several points, the key step toward the solution was to generalize the problem. ing structured information from a database. In addition, utility procedures can
Paradoxically, by considering a more general problem, the solution became easier to be easily defined to further alleviate the interaction with a particular database.
formulate. This generalization principle is a kind of standard technique that can • Data abstraction can be viewed as a programming technique that makes the use
often be applied. of complex data structures easier, and contributes to the clarity of programs. It is
Of the three programs, the third one illustrates best how to approach general easy in Prolog to carry out the essential principles of data abstraction.
problems of constructing under constraints a structure from a given set of elements. • Abstract mathematical constructs, such as automata, can often be readily
A natural question is: Which of the three programs is most efficient? In this
translated into executable Prolog definitions.
respect, program 2 is far inferior while the other two programs are similar. The reason
• As in the case of eight queens, the same problem can be approached in different
is that permutation-based program 2 constructs complete permutations while the
other two programs are able to recognize and reject unsafe permutations when ways by varying the representation of the problem. Often, introducing redund­
they are only partially constructed. Program 3 avoids some of the arithmetic ancy into the representation saves computation. This entails trading space for
computation that is essentially captured in the redundant board representation this time.
program uses. • Often, the key step toward a solution is to generalize the problem. Paradoxically,
by considering a more general problem the solution may become easier to
formulate.
Exercise
4. 7 Let the squares of the chessboard be represented by pairs of their coordinates of the
form X/Y, where both X and Y are between l and 8.

(a) Define the relation jump( Square 1, Square2) according to the knight jump on the
chessboard. Assume that Squarel is always instantiated to a square while Square2
can be uninstantiated. For example:

? jump( 1/1, S).

S = 3/2;

S = 2/3;

no

(b) Define the relation knightpath( Path) where Path is a list of squares that represent
a legal path of a knight on the empty chessboard.
(c) Using this knightpath relation, write a question to find any knight's path of
length 4 moves from square 2/1 to the opposite edge of the board (Y = 8) that
goes through square 5/4 after the second move.
 Preventing backtracking 115

y
chapter 5
4

Controlling Backtracking 2 -----.0

3 6 X
5.1 Preventing backtracking 114
Figure 5.1 A double-step function.
5.2 Examples using cut 119
5.3 Negation as failure 124 This can be written in Prolog as a binary relation:
f( X, Y)
5.4 Problems with cut and negation 127
as follows:
f( X, 0) :- X<3. /r, Rule 1
0

f( X, 2) 3 =<X, X<6. % Rule 2

f( X, 4) 6 =<X. % Rule 3
We have already seen that a programmer can control the execution of a program This program, of course, assumes that before f( X, Y) is executed X is already
through the ordering of clauses and goals. In this chapter we will look at another instantiated to a number, as this is required by the comparison operators.
control facility, callee! 'cut', for preventing backtracking. The cut also extends the vVe will make two experiments with this program. Each experiment will reveal
expressive power of Prolog ancl enables the definition of a kine! of negation, called some source of inefficiency in the program, and we will remove each source in turn
'negation as failure' and associated with the 'closed world assumption'. by using the cut mechanism.

5.1 Preventing backtracking

·······················································································································...................
5.1.1 Experiment 1
Prolog will automatically backtrack if this is necessary for satisfying a goal. Let us analyze what happens when the following question is posed:
Automatic backtracking is a useful programming concept because it relieves the ?- f( 1. Y), 2<Y.
programmer of the burden of programming backtracking explicitly. On the other
hand, uncontrolled backtracking may cause inefficiency in a program. Therefore we When executing the first goal, f( 1, Y), Y becomes instantiated to 0. So the second
sometimes want to control, or to prevent, backtracking. We can do this in Prolog by goal becomes
using the 'cut' facility. 2<0
Let us first study the behaviour of a simple example program whose execution
involves some unnecessary backtracking. We will identify those points at which the which fails, and so does the whole goal list. This is straightforward, but before
backtracking is useless and leacls to inefficiency. admitting that the goal list is not satisfiable, Prolog tries, through backtracking, two
Consider the double-step function shown in Figure 5.1. The relation between X useless alternatives. The detailed trace is shown in Figure 5.2.
and Y can be specified by three rules: The three rules about the f relation are mutually exclusive so that one of them at
most will succeed. Therefore we, not Prolog, know that as soon as one rule succeeds
Rule 1: if X < 3 then Y = 0 there is no point in trying to use the others, as they are bound to fail. In the example
Rule 2: if 3 � X ancl X < 6 then Y = 2 of Figure 5.2, rule 1 has become known to succeed at the point indicated by 'CUT'.
Rule 3: if 6 � X then Y = 4 In order to prevent futile backtracking at this point we have to tell Prolog explicitly

114
116 Controlling Backtracking Preventing backtracking 117

5.1 .2 Experiment 2
f(l,Y)
2< y
Let us now perform a second experiment with the second version of our program.
I; Suppose we ask:
rule\ ruk3 ?- f( 7, Y).

.- I � �: I
r =V // Y= Y=�
Y=4
1<3 3;;,I
1<6 Let us analyze what has happened. All three rules were tried before the answer was

-
2<0 2<2 obtained. This produced the following sequence of goals:
,
no
Try rule 1: 7 < 3 fails, backtrack and try rule 2 (cut was not reached)
CUT Try rnle 2: 3;;; 7 succeeds, but then 7 < 6 fails, backtrack and try rule 3 (cut was not
reached)
2<0 Try rule 3: 6 ;;; 7 succeeds

This trace reveals another source of inefficiency. First it is established that X < 3 is
no not true (7 < 3 fails). The next goal is 3 =< X ( 3 = < 7 succeeds). But we know that
Figure 5.2 .!'\t the point marked 'CUT' we already know that the rules 2 and 3 are bound to once the first test has failed the second test is bound to succeed as it is the negation
fail. of the first. Therefore the second test is redundant and the corresponding goal can
be omitted. The same is true about the goal 6 =< X in rule 3. This leads to the
not to backtrack. We can do this by using the cut mechanism. The 'cut' is written as! following, more economical formulation of the three rules:
and is inserted between goals as a kind of pseudo-goal. Our program, rewritten with if X < 3 then Y = 0,
cuts, is: otherwise if X < 6 then Y = 2,
f( X, 0) X < 3, 1• otherwise Y = 4.
f( X, 2) 3 =< X, X < 6, !. We can now omit the conditions in the program that are guaranteed to be true
f( X, 4) 6 =< X. whenever they are executed. This leads to the third version of the program:
The ! symbol will now prevent backtracking at the points at which it appears in the f( X, 0) X < 3, !.
program. If we now ask: f( X, 2) X < 6, !.
?- f( l, Y), 2 < Y. f( X, 4).
Prolog will produce the same left-hand branch as in Figure 5.2. This branch will fail This program produces the same results as our original version, but is more efficient
at the goal 2 < 0. Now Prolog will try to backtrack, but not beyond the point marked! than both previous versions. But what happens if we now remove the cuts? The
in the program. The alternative branches that correspond to 'rule 2' and 'rule 3' will program becomes:
not be generated.
f( X, 0) X < 3.
The new program, equipped with cuts, is in general more efficient than the
original version without cuts. When the execution fails, the new program will in f( X, 2) X < 6.
general recognize this sooner than the original program. f( X, 4).
To conclude, we have improved the efficiency by adding cuts. If the cuts are now This may produce multiple solutions, some of which are not correct. For
removed in this example, the program will still produce the same result; it will
example:
perhaps only spend more time. In our case, by introducing the cut we only changed
the procedural meaning of the program; that is, the results of the program were not ?- f( 1, Y).
affected_ We will see later that using a cut may affect the results as well. y =0 ;
118 Controlling Backtracking Examples using cut 119

y= 2;
Y= 4; ,/�
B�C-< -- D
----.. --
no

It is important to notice that, in contrast to the second version of the program, this
time the cuts do not only affect the procedural behaviour, but also change the
/
p -'-+-
-<-- Q- -
I.
�-...:-
- T -U
-<--R-► S -<- -<--
�
_____ _
-- -
--
-- - - -
- -
-- - V
results of the program.
A more precise meaning of the cut mechanism is as follows:
Figure 5.3 The effect of the cut on the execution. Starting with A, the solid arrows indicate
the sequence of calls; the dashed arrows indicate backtracking. There is 'one way
Let us call the 'parent goal' the goal that matched the head of the clause traffic' between R and s.
containing the cut. When the cut is encountered as a goal it succeeds immedi­
ately, but it commits the system to all choices made between the time the 'parent Therefore the cut will only affect the execution of the goal C. On the other hand, it
goal' was invoked and the time the cut was encountered. All the remaining will be 'invisible' from goal A. So automatic backtracking within the goal list B, C, D
alternatives between the parent goal and the cut are discarded. will remain active regardless of the cut within the clause used for satisfying C.

To clarify this definition consider a clause of the form:

1-1 :- Bl, B2, ... , Bm, !, ..., Bn. 5.2 Examples using cut
··········································································································································
Let us assume that this clause was invoked by a goal G that matched H. Then G is the
parent goal. At the moment that the cut is encountered, the system has already
found some solution of the goals Bl, ..., Brn. When the cut is executed, this
5.2.1 Computing maximum
(current) solution of HI, ..., Bm becomes frozen and all possible remaining altern­
The procedure for finding the larger of two numbers can be programmed as a
atives are discarded. Also, the goal G now becomes committed to this clause: any
relation
attempt to match G with the head of some other clause is precluded.
Let us apply these rules to the following example: max( X, Y, Max)
C P, Q, R, !, S, T, U. where Max= Xif Xis greater than or equal to Y, and Max is Y if Xis less than Y. This
C V. corresponds to the following two clauses:
A B, C, D. max( X, Y, X) X >= Y.
?- A. max( X, Y, Y) X <Y.
Here A, B, C, D, P, etc. have the syntax of terms. The cut will affect the execution of These two rules are mutually exclusive. If the first one succeeds then the second one
the goal C as illustrated by Figure 5.3. Backtracking will be possible within the goal will fail. If the first one fails then the second must succeed. Therefore a more
list P, Q, R; however, as soon as the cut is reached, all alternative solutions of the economical formulation, with 'otherwise', is possible:
goal list P, Q, R are suppressed. The alternative clause about C,
If X ?c Y then Max = X,
C :- V.
otherwise Max = Y.
will also be discarded. However, backtracking will still be possible within the goal
This is written in Prolog using a cut as:
list S, T, U. The 'parent goal' of the clause containing the cut is the goal C in the
clause: max( X, Y, X) :- X > = Y, L
A B, C, D_ max( X, Y, Y).
120 Controlling Backtrack"ing Examples using cut 121

It should be noted that the use of this procedure requires care. [t is safe if in the goal where X is the item to be added, L is the list to which Xis to be added and Ll is the
max(X, Y,Max) the argument Max is not instantiated. The following example of resulting new list. Our rule for adding can be formulated as:
incorrect use illustrates the problem:
If X is a member of list L then Ll = L,
?- max( 3, 1, 1). otherwise L1 is equal to L with X inserted.
yes It is easiest to insert X in front of L so that X becomes the head of Ll. This is then
The following reformulation of max overcomes this limitation: programmed as follows:
max( X, Y, Max) :- add( X, L, L) :- member( X, L), !.
X >= Y, !, Max= X add{ X, L, [XI L] ).
Max= Y. The behaviour of this procedure is illustrated by the following example:
?- add( a, [b,c], L).
5.2.2 Single-solution membership I.= [a,b,c]
?- add( X, (b,c], L).
We have been using the relation
L = (b,c]
member( X, I.) X=b
for establishing whether X is in list L. The program was: ?- add{ a, [b,c,X], L).
member( X, [XI L] ). L = [b,c,a]
X=a
member( X, [YI L] ) :- member( X, L).
Similar to the foregoing example with max, add( X, Ll, L2) is intended to be called
This is non-deterministic: if X occurs several times then any occurrence can be
with L2 uninstantiated. Otherwise the result may be unexpected: for example
found. Let us now change member into a deterministic procedure which will find
add( a, [a], [a,a] ) succeeds.
only the first occurrence. The change is simple: we only have to prevent back­
This example is instructive because we cannot easily program the 'non-duplicate
tracking as soon as X is found, which happens when the first clause succeeds. The
add' without the use of cut or another construct derived from the cut. If we omit the
modified program is:
cut in the foregoing program then the add relation will also add duplicate items. For
member( X, [X I L] ) !. example:
member( X, [YI L] ) member( X, L). ?- add( a, [a,b,c], L).
This program will generate just one solution. For example: L= [a,b,c];
?- member( X, [a,b,c] ). L= [a,a,b,c]
X = a; So the cut is necessary here to specify the intended relation, and not only to improve
no efficiency. The next example also illustrates this point.

5.2.3 Adding an element to a list without duplication 5.2.4 Classification into categories
Often we want to add an item Xto a list L so that Xis added only if Xis not yet in L. Assume we have a database of results of tennis games played by members of a
If X is already in L then L remains the same because we do not want to have club. The pairings were not arranged in any systematic way, so each player just
redundant duplicates in L. The add relation has three arguments: played some other players. The results are in the program represented as facts
add{ X, L, Ll) like:
 Examples using cut 123
122 Controlling Backtracking

beat( tom, jim). class( X, sportsman)

beat( ann, tom). beat(_, X).
beat( pat, jim).
Notice that the cut in the clause for winner is not necessary. Care is needed when
We want to define a relation using such procedures containing cuts. Here is what can happen:

class( Player, Category) ?- class( tom, C).

C = fighter; 0
;,, As intended
that ranks the players into categories. We have just three categories:
no
winner: every player who won all his or her games is a winner
?- class( tom, sportsman).
fighter: any player that won some games and lost some
yes % Not as intended
sportsman: any player who lost all his or her games
The call of class is safe if the second argument is not instantiated. Otherwise we may
For example, if all the results available are just those above then Ann and Pat are
get an unintended result.
winners, Tom is a fighter and Jim is a sportsman.
It is easy to specify the rule for a fighter:

X is a fighter if Exercises
there is some Y such that X beat Y and
there is some Z such that Z beat X. 5.1 Let a program be:
p( 1).
Now a rule for a winner:
p( 2) :- !.
X is a winner if
p( 3).
X beat some Y and
X was not beaten by anybody. Write all Prolog's answers to the following questions:

This formulation contains 'not' which cannot be directly expressed with our present (a) ?- p( X).
Prolog facilities. So the formulation of winner appears trickier. The same problem (bJ ?- p( X), p( Y).
occurs with sportsman. The problem can be circumvented by combining the (c) ?- p( X), !, p( Y).
definition of winner with that of fighter, and using the 'otherwise' connective. Such
zero and
a formulation is: 5.2 The following relation classifies numbers into three classes: positive,
negative:
If X beat somebody and X was beaten by somebody
class( Number, positive) Number> 0.
then X is a fighter,
otherwise if X beat somebody class( 0, zero).
then X is a winner, class( Number, negative) Number< 0.
otherwise if X got beaten by somebody Define this procedure in a more efficient way using cuts.
then X is a sportsman.

This formulation can be readily translated into Prolog. The mutual exclusion of the
5.3 Define the procedure

three alternative categories is indicated by the cuts: split( Numbers, Positives, Negatives)

class( X, fighter) which splits a list of numbers into two lists: positive ones (including z.ero) and
beat( X, _), negative ones. For example:
beat(_, X), !.
split( [3,-1,0,5,-2], [3,0, 5], [-1,-2])
class( X, winner)
beat( X, _), !. Propose two versions: one with a cut and one without.
124 Controlling Backtracking Negation as failure 125

5.3 Negation as failure We again use the cut and fail combination:
······················· ····································· .. ................ ............ . ......................... ··············· different( X, X) :- !, fail.
'Mary likes all animals but snakes'. How can we say this in Prolog? ft is easy to different( X, Y).
express one part of this statement: Mary likes any X if X is an animal. This is in
Prolog: This can also be written as one clause:
different( X, Y)
likes( mary, X) :- animal( X).
X = Y, !, fail
But we have to exclude snakes. This can be done by using a different formulation:
true.
If X is a snake then 'Mary likes X' is not true, true is a goal that always succeeds.
otherwise if X is an animal then Mary likes X. These examples indicate that it would be useful to have a unary predicate 'not'
That something is not true can be said in Prolog by using a special goal, fail, which such that
always fails, thus forcing the parent goal to fail. The abow formulation is translated not( Goal)
into f'rolog, using fail, as follows:
is true if Goal is not true. We will now define the not relation as follows:
likes( mary, X) :­
s,1ake( X), 1, fail. If Goal succeeds then not( Goal) fails,
otherwise not( Goal) succeeds.
likes( mary, X)
animal( X). This definition can be written in Prolog as:

The frrst rule here will take care of snakes: if X is a snake then the cut will prevent not( P ) :-
P, 1, fail
backtracking (thus excluding the second rule) and fail will cause the failure. These
two clauses can be written more compactly as one clause: true.
likes( nrnry, X) :­ Henceforth, we will assume that not is a built-in Prolog procedure that behaves as
snake( X), !, fail defined here. We will also assume that not is defined as a prefix operator, so that we
animal( X). can also write the goal
not( snake(X) )
We can use the same idea to define the relation
as:
different( X, Y)
not snake( X)
which is true if X and Y are different. We have to be more precise, however, because
Some Prolog implementations, in fact, support this notation. If not, then we can
'different' can be understood in several ways:
always defme not ourselves. Alternatively, not Goal is written as \+ Goal. This more
• X and Y are not literally the same; mysterious notation is also recommended in the Prolog standard for the following
• reason. not defined as failure, as here, does not exactly correspond to negation in
X and Y do not match;
mathematical logic. This difference can cause unexpected behaviour if not is used
• the values of arithmetic expressions X and Y are not equal. without care. This will be discussed later in the chapter.
Nevertheless, not is a useful facility and can often be used advantageously in place
Let us choose here that X and Y are different if they do not match. The key to saying
of cut. Our two examples can be rewritten with not as:
this in Prolog is:
likes( mary, X) :-
If X and Y match then different( X, Y) fails, animal( X),
otherwise different( X, Y) succeeds. not snake( X).
126 Controlling Backtracking Problems with cut and negation 127

5.5 Define the set subtraction relation

solution( [ ]).
set_difference( Setl, Set2, SetDifference)
solution( [X/Y I Others])
solution( Others), where all the three sets are represented as lists. For example:
member( Y, [1,2,3,4,5,6,7,8] ), % Usual member predicate
not attacks( X/Y, Others). set_difference( [a,b,c,d], [b,d,e,f], [a,c] )
attacks( X/Y, Others) :­ 5.6 Define the predicate
member( Xl/Yl, Others),
( Yl =Y; unifiable( Listl, Term, List2)
YlisY+Xl-X;
YlisY - Xl + X ). where List2 is the list of all the members of Listl that match Term, but are not
instantiated by this matching. For example:

Figure 5.4 Another eight queens program. ?- unifiable( [X, b, t(Y)], t(a), List).
List = [X, t(Y)]

different( X,Y) Note that X and Y have to remain uninstantiated although the matching with t( a)
not( X =Y). does cause their instantiation. Hint: Use not( Terml = Tenn2). If Terml = Term2
succeeds then not( Terml = Term2) fails and the resulting instantiation is undone!
This certainly looks better than our original formulations. It is more natural and is
easier to read.
Our tennis classification program of the previous section can also be rewritten,
using not, in a way that is closer to the initial definition of the three categories: 5.4
class( X, fighter)
beat( X, _), Using the cut facility we get something, but not for nothing. The advantages and
beat(_, X). disadvantages of using cut were illustrated by examples in the previous sections. Let
us summarize, first the advantages:
class( X, winner)
beat( X, _), With cut we can often improve the efficiency of the program. The idea is to
(1)
not beat( _, X).
explicitly tell Prolog: do not try other alternatives because they are bound
class( X, sportsman) to fail.
beat(_, X},
not beat( X, _). (2) Using cut we can specify mutually exclusive rules; so we can express rules of
the form:
As another example of the use of not let us reconsider program 1 for the eight
queens problem of the previous chapter (Figure 4.7). We specified the no_attack if condition P then conclusion Q,
relation between a queen and other queens. This relation can be formulated also otherwise conclusion R
as the negation of the attack relation. Figure 5.-l shows a program modified In this way, cut enhances the expressive power of the language.
accordingly.
The reservations against the use of cut stem from the fact that we can lose the
valuable correspondence between the declarative and procedural meaning of
Exercises programs. If there is no cut in the program we can change the order of clauses and
goals, and this will only affect the efficiency or termination of the program, not
5.4 Given two lists, Candidates and RuledOut, write a sequence of goals (using member the declarative meaning. On the other hand, in programs with cuts, a change in the
and not) that will through backtracking find all the items in Candidates that are not order of clauses may affect the declarative meaning. This means that we can get
in RuledOut. different results. The following example illustrates:
123 Controiling Backtracking Problems with cut and negation 129

p a, b. ?- not human( mary).

p :- C. Prolog will probably answer 'yes'. But this should not be understood as Prolog saying
The declarative meaning of this program is: p is true if and only if a and b are both 'Mary is not human'. What Prolog really means to say is: 'There is not enough
true or c is true. This can be written as a logic formula: information in the program to prove that Mary is human'. This arises because when
processing a not goal, Prolog does not try to prove this goal directly. [nstead, it tries
p <=> (a & b) V c to prove the opposite, and if the opposite cannot be proved then Prolog assumes
We can change the order of the two clauses and the declarative meaning remains the that the not goal succeeds.
same. Let us now insert a cut: Such reasoning is basecl on the so-called closed world assumption. Accorcling to this
assumption the world is closed in the sense that everything that exists is stated in the
p a,!, b.
program or can be derived from the program. Accordingly then, if something is not
p C. in the program (or cannot be derived from it) then it is not true and consequently its
The declarative meaning is now: negation is true. This deserves special care because we do not normally assume that
'the world is closed'. When we do not explicitly enter the clause
p <=> (a & b) v (~a & c)
human( mary).
ff we swap the clauses,
into our program, we do not mean to imply that Mary is not human.
p :- C. To further study the special care that not requires, consider the following example
p a,!, b. about restaurants:
then the meaning becomes: good_standard( jeanluis).
p <=> c I/ (a & b) expensive( jeanluis).
good_standard( francesco).
The important point is that when we use the cut facility we have to pay more
attention to the procedural aspects. Unfortunatelv, this additional difficulty reasonable( Restaurant) :-
not expensive( Restaurant).
increases the probability of a programming error.
In our examples in the previous sections we have seen that sometimes the removal [f we ask:
of a cut from the program can change the decbrative meaning of the program. But
?- good_standard( X), reasonable( X).
there were also cases in which the cut had no effect on the declarative meaning. The
use of cuts of the latter type is less delicate, and therefore cuts of this kind are Prolog will answer:
sometimes called 'green cuts'. From the point of view of readability of programs,
X = francesco
green cuts are 'innocent' and their use is quite acceptable. When reading a program,
green cuts can simply be ignored. If we ask apparently the same question
On the contrary, cuts that do affect the declarative meaning are called 'red cuts'.
?- reasonable( X), good_standard( X).
Red cuts are the ones that make programs hard to understand, and they should be
used with special care. then Prolog will answer:
Cut is often used in combination with a special goal, fail. In particular, we defined
no
the negation of a goal (not) as the failure of the goal. The negation, so defined, is just
a special, more restricted way of using cut. For reasons of clarity we will prefer to use The reader is invited to trace the program to understand why we get different
not instead of the cut-fail combination (whenever possible), because the negation is answers. The key difference between both questions is that the variable X is, in the
intuitively clearer than the cut-fail combination. first case, already instantiated when reasonable( X) is executed, whereas X is not yet
It should be noted that not may also cause problems, and so should also be used instan_tiated in the second case. The general hint is: not Goal works safely if the
with care. The problem is that not, as defined here, does not correspond exactly to variables in Goal are instantiated at the time not Goal is called. Otherwise we may get
negation in mathematics. If we ask Prolog: unexpected results due to reasons explained in the sequel.
130 Controlling Backtracking References 131

The problem with uninstantiated negated goals arises from unfortunate change • not defined through failure does not exactly correspond to negation in
of the quantification of variables in negation as failure. In the usual interpretation in mathematical logic. Therefore, the use of not also requires special care.
Prolog, the question:
?- expensive( X).
References
means: Does there exist X such that expensive( X) is true? If yes, what is X? So X is
existentially quantified. Accordingly Prolog answers X = jeanluis. But the question: The distinction between 'green cuts' and 'red cuts' was proposed by van Emden (1982). Le
?- not expensive( X). (1993) proposes a different negation for Prolog which is mathematically advantageous, but
computationally more expensive.
is not interpreted as: Does there exist X such that not expensive( X)? The expected
answer would be X = francesco. But Prolog answers 'no' because negation as failure Le, T.V. (1993) Tec/111iques o(Prolog Progranuning. John Wiley & Sons.
changes the quantification to universal. The question not expensive( X) is interpreted van Emden, M. ( 1982) Reel and green cuts. Logic Programming Newsletter: 2.
as:
not( exists X such that expensive( X))
This is equivalent to:
For all X: not expensive( X)
We have discussed problems with cut, which also indirectly occur in not, in
detail. The intention has been to warn users about the necessary care, not to
definitely discourage the use of cut. Cut is useful and often necessary. Ancl after all,
the kind of complications that are incurred by cut in Prolog commonly occur when
programming in other languages as well.

Summary
• The cut facility prevents backtracking. [t is used both to improve the efficiency
of programs and to enhance the expressive power of the language.
• Efficiency is improved by explicitly telling Prolog (with cut) not to explore
alternatives that we know are bound to fail.
• Cut makes it possible to formulate mutually exclusive conclusions through rules
of the form:
i( Condition then Conclusionl otherwise Conclusion2
• Cut makes it possible to introduce negation as (ailure: not Goal is defined through
the failure of Goal.
• Two special goals are sometimes useful: true always succeeds, fail always fails.
• There are also some reservations against cut: inserting a cut may destroy the
correspondence between the declarative and procedural meaning of a program.
Therefore, it is part of good programming style to use cut with care and not to
use it without reason.
 Communication with files 133

chapter 6 User
terminal

Input and Output

user user

· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ··
Output
6.1 Communication with files 132 �pW { fikl file 3 }
streams streams
file2 file 4
6.2 Processing files of terms 135
6.3 Manipulating characters 140 Figure 6.1 Communication between a Prolog program and several files .

6.4 Constructing and decomposing atoms 141

Built-in predicates aimed at these extensions depend on the implementation of
6.5 Reading programs 144
Prolog. We will study here a simple and handy repertoire of such predicates, which is
part of many Prolog implementations. However, the implementation manual
should be consulted for details and specificities. Many l'rolog implementations
provide various additional facilities not covered here. Such extra facilities handle
windows, provide graphics primitives for drawing on the screen, input information
from the mouse, and so on.
In this chapter we will investigate some built-in facilities for reading data from We will first consider the question of directing input and output to files, and then
computer files and for outputting data to files. These procedures can also be used for how data can be input and output in different forms.
formatting data objects in the program to achieve a desired output representation of Figure 6.1 shows a general situation in which a Prolog program communicates
these objects. We will also look at facilities for reading programs and for construct­ with several files. The program can, in principle, react data from several input files,
ing and decomposing atoms. also called input streams, and output data to several output files, also called output
streams. Data coming from the user's terminal is treated as just another input stream.
Data output to the terminal is, analogously, treated as another output stream. Both
of these 'pseudo-files' are referred to by the name user. The names of other files can
6.1 Communication with files be chosen by the programmer according to the rules for naming files in the
computer system used.
The method of communication between the user and the program that we have At any time during the execution of a Prolog program, only two files are 'active':
been using up to now consists of user questions to the program and program one for input and one for output. These two files are called the current input stream
answers in terms of instantiations of variables. This method of communication is and the current output stream respectively. At the beginning of execution these two
simple and suffices to get the information in and out. However, it is often not quite streams correspond to the user's terminal. The current input stream can be changed
sufficient because it is too rigid. Extensions to this basic communication method are to another file, Filename, by the goal:
needed in the following areas:
see( Filename)
• input of data in forms other than questions - for example, in the form of English
sentences, Such a goal succeeds (unless there is something wrong with Filename) and
• output of information in any format desired, and
causes, as a side effect, that input is switched from the previous input stream to
Filename. So a typical example of using the see predicate is the following
• input from and output to any computer file or device and not just the user sequence of goals, which reads something from filel and then switches back to the
terminal. terminal:
132
-----------------------------------··-···�--· · ·-·

134 Input and Output Processing files of terms 135

input/output request of this type would transfer a whole term from the current
see( file!),
read_from_file( Information), input stream or to the current output stream respectively. Predicates for transfer of
see( user), terms are read and write. Of course, in this case, the information in the file has to be
in a form that is consistent with the syntax of terms.
What kind of file organization is chosen will, of course, depend on the problem.
The current output stream can be changed by a goal of the form: Whenever the problem speciflcation will allow the information to be naturally
tell( Filename) squeezed into the syntax of terms, we will prefer to use a file of terms. It will then be
possible to transfer a whole meaningful piece of information with a single request.
A sequence of goals to output some information to file3, and then redirect On the other hand, there are problems whose nature dictates some other organiza­
succeeding output back to the terminal, is: tion of files. An example is the processing of natural language s1entences, say, to
generate a dialogue in English between the system and the user. In such cases, files
tell( file3), will have to be viewed as sequences of characters that cannot be parsed into terms.
write_on_file( Information),
tell( user),
6.2 Processing fil��..?�.��.rri:1�........................................... ...........................................
The goal
seen
closes the current input file. The goal
6.2.1 read and write
told The built-in predicate read is used for reading terms from the current input stream.
The goal
closes the current output file.
We will assume here that files can only be processed sequentially although many read( X)
Prolog implementations also handle files with random access. Sequential files
will cause the next term, T, to be read, and this term will be matched with X. lf Xis a
behave in the same way as the terminal. Each request to read something from an
variable then, as a result, X will become instantiated to T. If matching does not
input file will cause reading at the current position in the current input stream. After
succeed then the goal read( X) fails. The predicate reacl is deterministic, so in the case
the reading, the current position will be, of course, mo\·ed to the next unreaci item.
of failure there will be no backtracking to input another term. Each term in the
So the next request for reading will start reading at this new current position. If a
input file must be followed by a full stop and a space or carriage-return.
request for reading is made at the end of a file, then the information returned by
If read( X) is executed when the end of the current input file has been reached
such a request is the atom end_of_file.
then X will become instantiated to the atom end_of_file.
Writing is similar; each request to output information will append this informa­
The built-in predicate write outputs a term. So the goal
tion at the end of the current output stream. It is not possible to move backward and
to overwrite part of the file. write( X)
We will here only consider 'text-files' - that is, files of characters. Characters are will output the term X on the current output file. X will be output in the same
letters, digits and special characters. Some of them are said to be non-printable standard syntactic form in which Prolog normally displays values of variables. A
because when they are output on the terminal they do not appear on the screen. useful feature of Prolog is that the write procedure 'knows' to display any term no
They may, however, have other effects, such as spacing between columns and lines. matter how complicated it may be.
There are two main ways in which files can be viewed in Prolog, depending on Typically, there are additional built-in predicates for formatting the output. They
the form of information. One way is to consider the character as the basic element insert spaces and new lines into the output stream. The goal
of the file. Accordingly, one input or output request will cause a single character to
be read or written. We assume the built-in predicates for this are get, getO and put. tab( N)
The other way of viewing a file is to consider bigger units of information as basic causes N spaces to be output. The predicate nl (which has no arguments) causes the
building blocks of the file. Such a natu,al bigger unit is the Prolog term. So each start of a new line at output.
136 Input and Output Processing files of terms 137

The following examples will illustrate the use of these procedures. The numbers 2, 5 and 12 were typed in by the user on the terminal; the other
Let us assume that we have a procedure that computes the cube of a number: numbers were output by the program. Note that each number entered by the user
had to be followed by a full stop, which signals the end of a term.
cube( N, C) :- It may appear that the above cube procedure could be simplified. However, the
C is N, N * N. following attempt to simplify is not correct:
Suppose we want to use this for calculating the cubes of a sequence of numbers. We cube :-
could do this by a sequence of questions: read( stop), !.
?- cube( 2, X). cube :­
read( N),
X=8 C is N, N" N,
write( C),
?- cube( 5, Y). cube.
Y = 125
The reason why this is wrong can be seen easily if we trace the program with input
?- cube( 12, Z). data 5, say. The goal read( stop) will fail when the number is read, and this number
Z = 1728 will be lost for ever. The next read goal will input the next term. On the other hand,
it could happen that the stop signal is read by the goal read( N), which would then
For each number, we had to type in the corresponding goal. Let us now modify this cause a request to multiply non-numeric data.
program so that the cube procedure will read the data itself. Now the program will The cube procedure conducts interaction between the user and the program. In
keep reading data and outputting their cubes until the atom stop is read: such cases it is usually desirable that the program, before reading new data from the
terminal, signals to the user that it is ready to accept the information, and perhaps
cube :- also says what kind of information it is expecting. This is usually done by sending a
read( X),
process( X). 'prompt' signal to the user before reading. Our cube procedure would be accordingly
modified, for example, as follows:
process( stop) !.
cube :-
process( N) :- write( 'Next item, please: '),
C is N • N * N, read( X),
write( C), process( X).
cube.
process( stop) !.
This is an example of a program whose declarative meaning is awkward to
process( N) :-
formulate. However, its procedural meaning is straightforward: to execute cube, first C is N * N * N,
read X and then process it; if X = stop then everything has been clone, otherwise write( 'Cube of'), write( N), write( ' is '),
write the cube of X and recursively call the cube procedure to process further data. A write( C), nl,
table of the cubes of numbers can be produced using this new procedure as follows: cube.

?- cube. A conversation with this new version of cube would then be, for example, as follows:
2.
8 ?-cube.
5. Next item, please: 5.
125 Cube of 5 is 125
12. Next item, please: 12.
1728 Cube of 12 is 1728
stop. Next item, please: stop.
yes yes

'�;/;-:�;�b#/�.{t�- 'f�t$;i>'\i{J�S,1.;k...Z.,.;r;,��j�"i'f1if�����1)!:�4!"���i'jl'��lfi)e��,, '

138 Input and Output Processing files of terms 139

Depending on the implementation, an extra request (like ttyflush, say) after writing The bars procedure can be defined as follows:
the prompt might be necessary in order to force the prompt to actually appear
on the screen before reading. bars( [l ).
In the following sections we will look at some typical examples of operations that bars( (NI L])
involve reading and writing. stars( N), nl,
bars( L).
stars( N) :-
6.2.2 Displaying lists N > 0,
write(,),
Besides the standard Prolog format for lists, there are se\·eral other natural forms for Nl is N - l,
displaying lists which have advantages in some situations. The following procedure stars( Nl).

writelist( L) stars( N) :­
N =<0.
outputs a list L so that each element of L is written on a separate line:
writelist( [ ] ).
writelist( [XI L]) 6.2.3 Processing a file of terms
write( X), nl,
writelist( L). A typical sequence of goals to process a whole file, F, would look something like this:
If we have a list of lists, one natural output form is to write the elements of each list in ..., see( F), processfile, see( user), ...
one line. To this end, we will define the procedure writelistZ. An example of its use is:
Here processfile is a procedure to read and process each term in F, one after another,
?- writelist2( [ [a,b,c], (d,e,f], [g ,h,i] ] ).
until the end of the file is encountered. A typical schema for processfile is:
abc
def processfile :-
g hi read( Term), % Assuming Term not a variable
process( Term).
A procedure that accomplishes this is:
process( end_of_file) !. % All done
writelistZ( [] ).
process( Term)
writelist2( [LI LL]) treat( Term), % Process current item
doline( L), nl, processfile. % Process rest of file
writelist2( LL).
doline( [ J ). Here treat( Term) represents whatever is to be done with each term. An example
would be a procedure to display on the terminal each term together with its
doline( [XI LJ )
write( X), tab( 1), consecutive number. Let us call this procedure showfile. It has to have an additional
doline( L). argument to count the terms read:

A list of integer numbers can be sometimes conveniently shown as a bar graph. showfile( N) :-·
The following procedure, bars, will display a list in this form, assuming that the read( Term),
numbers in the list are sufficiently small. An example of using bars is: show( Term, N).
show( end_of_file, _) !.
?- bars( (3,4,6,5] ).
**"' show( Term, N) :-
**** write( N), tab( 2), write( Term), nl,
****** Nl is N + 1,
***** sho½file( Nl).
140 Input and Output Constructing and decomposing atoms 141

Exercises sentence processed by squeeze ends with a full stop and that words are separated
simply by one or more blanks, but no other character. An acceptable input is
6.1 Let f be a file of terms. Define a procedure then:

findtcrm( Tenn) The robot tried to pour wine out of the bottle.

that displays on the terminal the first term inf that matches Term. The goal squeeze would output this in the form:

6.2 Let f be a file of terms. Write a procedure The robot tried to pour wine out of the bottle.

findallterms( Term) The squeeze procedure will have a similar structure to the procedures for
processing files in the previous section. First it will read the first character, output
that displays on the terminal all the terms inf that match Tem1. Make sure that Term this character, and then complete the processing depending on this character. There
is not instantiated in the process (which could prevent its match with terms that are three alternatives that correspond to the following cases: the character is either a
occur later in the file).
full stop, a blank or a letter. The mutual exclusion of the three alternatives is
achieved in the program by cuts:
squeeze :­
6.3 Manipulating characters
··· ······ · · ······· ······· ······ ··········••··· ·················································· ······· ·························· •········
getO(C),
put(C),
A character is written on the current output stream with the goal dorest(C).
dorest( 46) [. % 46 is ASCII for full stop, all done
put(C)
dorest( 32) [, % 32 is ASCH for blank
where C is the ASCII code (a number between O and 127) of the character to be get(C), % Skip other blanks
OLttput. For example, the question put(C),
dorest( C).
7- put( 65), put( 66), put( 67).
dorest( Letter)
would cause the following output: squeeze.
ABC

65 is the ASCII code of 'A', 66 of 'B', 67 of 'C'. Exercise

A single character can be read from the current input stream by the goal
getO(C) 6.3 Generalize the squeeze procedure to handle commas as well. All blanks immediately
preceding a comma are to be removed, and we want to have one blank after each
This causes the current character to be read from the input stream, and the variable comma.
C becomes instantiated to the ASCII code of this character. A variation of the
predicate getO is get, which is used for reading non-blank characters. So the goal
get(C)
6.4 Constructing and decomposing atoms
will cause the skipping over of all non-printable characters (blanks in particular)
from the current input position in the input stream up to the first printable It is often desirable to have information, read as a sequence of characters, repres­
character. This character is then also read and C is instantiated to its ASCII code. ented in the program as an atom. There is a built-in predicate, name, which can be
As an example of using predicates that transfer single characters let us define a used to this end. name relates atoms and their ASCII encodings. Thus,
procedure, squeeze, to do the following: read a sentence from the current input
name(A, L)
stream, and output the same sentence reformatted so that multiple blanks between
words are replaced by single blanks. For simplicity we will assume that any input is true if L is the list of ASCII codes of the characters in A. For example,
142 Input and Output Constructing and decomposing atoms 143

name( zx232, (122, 120,50,51,50] )

/,
is true. There are two typical uses of name: Procedure getsentence reads in a sentence and combines the words into a list of atoms.
For example
(1) given an atom, break it down into single characters;
getsentence( Worc!Iist)
(2) given a list of characters, combine them into an atom.
produces
An example of the first kind of application would be a program that deals with Wordlist= [ 'Mary', was, pleased, to, see, the, robot, failj
orders, taxis and drivers. These would be, in the program, represented by atoms
if the input sentence is:
such as:
Mary was pleased to see the robot fail.
orderl, order2, driver 1, driver2, taxial, taxilux
•I
The following predicate: getsentence( Wordlist)
taxi( X) getO( Char),
getrest( Char, Wordlist).
tests whether an atom X represents a taxi: getrest( 46, [] ) :- !. '¾, End of sentence: 46 = ASCII for'.'
taxi( X) :- getrest( 32, Wordlist) :- !, % 32= ASCII for blank
name( X, Xlist), getsentence( Wordlist). % Skip the blank
name( taxi, Tlist), getrest( Letter, [Word I Wordlist] )
cone( Tlist, _, Xlist). 1i, Is word 'taxi' prefix of X?
0
getietters( Letter, Letters, Nextchar), % Read letters of current word
name( Word, Letters),
Predicates order and driver can be defined analogously.
getrest( Nextchar, Wordlist).
The next example illustrates the use of combining characters into atoms. We will
define a predicate: getletters( 46, [], 46) !. % End of word: 46 = full stop
getietters( 32, [ ], 32) !. % End of word: 32= blank
getsentence( Wordlist)
getletters( Let, [Let I Letters], Nextchar)
that reads a free-form natural language sentence and instantiates Worctlist to some getO( Char),
internal representation of the sentence. A natural choice for the internal representa­ getletters( Char, Letters, Nextchar).
tion, which would enable further processing of the sentence, is this: each word
of the input sentence is represented as a Prolog atom; the whole sentence is Figure 6.2 A procedure to transform a sentence into a list of atoms.
represented as a list of atoms. For example, if the current input stream is:

Mary was pleased to see the robot fail. (3) Char is a letter: first read the word, Word, which begins with Char, and then use
getsentence to read the rest of the sentence, producing Wordlist. The cumulative
then the goal getsentence( Sentence) will cause the instantiation:
result is the list (Word I Wordlist].
Sentence= [ 'Mary', was, pleased, to, see, the, robot, fail]
The procedure that reads the characters of one word is:
For simplicity, we will assume that each sentence terminates with a full stop and getletters( Letter, Letters, Nextchar)
that there are no punctuation symbols within the sentence.
The program is shown in Figure 6.2. The procedure getsentence first reads the The three arguments are:
current input character, Char, and then supplies this character to the procedure
(1) Letter is the current letter (already read) of the word being read.
getrest to complete the job. getrest has to react properly according to three cases:
(2) Letters is the list of letters (starting with Letter) up to the end of the word.
(1) Char is the full stop: then everything has been read. (3) Nextchar is the input character that immediately follows the word read.
(2) Char is the blank: ignore it, getsentence from rest of input. Nextchar must be a non-letter character.
144 Input and Output Summary 145

We conclude this example with a comment on the possible use of the getsentence will be that all the clauses in file program3 are read and loaded into the memory. So
procedure. It can be used in a program to process text in natural language. Sentences they wilt be used by Prolog when answering further questions from the user.
represented as lists of words are in a form that is suitable for further processing in Another file may be 'consulted' at some later time during the same session. Basically,
Prolog. A simple example is to look for certain keywords in input sentences. A much the effect is again that the clauses from this new file are added into the memory.
more difficult task would be to understand the sentence; that is, to extract from the However, details depend on the implementation and other circumstances. If the
sentence its meaning, represented in some chosen formalism. This is an important new file contains clauses about a procedure defined in the previously consulted
research area of Artificial Intelligence, and is introduced in Chapter 21. file, then the new clauses may be simply added at the end of the current set of
clauses, or the previous definition of this procedure may be entirely replaced by the
new one.
Exercises Several files may be consulted by the same consult goal, for example:
?- consult( [ program3, program4, queens]).
6.4 Define the relation
Such a question can also be written more simply as:
starts( Atom, Character)
?- [ program3, prograrn4, queens].
to check whether Atom starts with Character.
Consulted programs are used by a Prolog interpreter. If a Prolog implementation also
6.5 Define the procedure plural that will convert nouns into their plural form. For features a compiler, then programs can be loaded in a compiled form. This enables
example: more efficient execution with a typlcal speed-up factor of 5 or 10 between the
?- plural( table, X). interpreted and compiled code. Programs are loaded into memory in the compiled
form by the built-in predicate compile, for example:
X = tables
?- compile( program3).
6.6 Write the procedure
or
search( KeyWord, Sentence)
?- compile( [ program4, queens, program6]).
that will, each time it is called, find a sentence in the current input file that contains
the given Keyword. Sentence should be in its original form, represented as a sequence Compiled programs are more efficiently executed, but interpreted programs are
of characters or as an atom (procedure getsentence of this section can be accordingly easier to debug because they can be inspected and traced by Prolog's debugging
modified). facilities. Therefore an interpreter is typically used in the program development
phase, and a compiler is used with the final program.
It should be noted, again, that the details of consulting and compiling files
depend on the implementation of Prolog. Usually a Prolog implementation also
6.5 Reading programs
········································· ·································································································
allows the user to enter and edit the program interactively.

We can communicate our programs to the Prolog system by means of built-in

predicates that consult or compile files with programs. The details of 'consulting' and
compiling files depend on the implementation of Prolog. Here we look at some basic Summary
..........................................................................................................................................
facilities that are available in many Prologs.
We tell Prolog to read a program from a file F with a goal of the form consult( F), • Input and output (other than that associated with querying the program) is done
for example: using built-in procedures. This chapter introduced a simple and practical
repertoire of such procedures that can be found in many Prolog implementa­
?- consult( program3). tions.
Depending on the implementation, the file name program3 will possibly have to • This repertoire assumes that files are sequential. There is the current input stream
have an extension indicating that it is a Prolog program file. The effect of this goal and the current output stream. The user terminal is treated as a file called user.
146 Input and Output

•
chapter 7
Switching between streams is done by:
see( File) File becomes the current input stream
tell( File) File becomes the current output stream
seen close the current input stream

•
told close the current output stream
Files are read and written in two ways: More Built-in Predicates
as sequences of characters
as sequences of terms 7.1 Testing the type of terms 147
Built-in procedures for reading and writing characters and terms are: 7.2 Constructing and decomposing terms:= .. , functor, arg, name 155
read( Term) input next term
write( Term) output Term 7.3 Various kinds of equality and comparison 160
put( CharCode) output character with the given ASC!l code
7.4 Database manipulation 161
get0( CharCode) input next character
get( CharCode) input next 'printable' character 7.5 Control facilities 166
• Two procedures help formatting:
7.6 bagof, setof and finda/1 167
nl output new line
tab( N) output N blanks
• The procedure name( Atom, CodeList) decomposes and constructs atoms.
CodeList is the list of ASCII codes of the characters in Atom.
• Many Prolog implementations provide additional facilities to handle non­
sequential files, windows, provide graphics primitives, input information from In this chapter we will examine some more built-in predicates for advanced Prolog
the mouse, etc. programming. These features enable the programming of operations that are not
possible using only the features introduced so far. One set of such predicates
manipulate terms: testing whether some variable has been instantiated to an
Reference. to Prolog standard integer, taking terms apart, constructing new terms, etc. Another useful set of
procedures manipulates the 'database': they add new clauses to the program or
For some of the predicates mentioned in this chapter, ISO standard for Prolog (Deransart et al. remove existing ones.
1996) recommends different names from those used in most Prolog implementations. The built-in predicates largely depend on the implementation of Prolog.
However, the predicates are conceptually the same, so compatibility is only a matter of However, the predicates discussed in this chapter are provided by many Prolog
renaming. The concerned predicates in this chapter are: see(Filename), tell(Filename), implementations. Various implementations may provide additional features.
get(Code), put(Code), name(Atom.CodeList). The corresponding predicate names in the
standard are: set_input(Filename), set_output(Filename), get_code(Code), put_code(Code),
atom_codes(Atom,CodeList).
7.1 Testing the type of terms
Deransart, P., Ed-Bdali, A. and Ceroni, L. (1996) Prolog: Tile Standard. Berlin: Springer-Verlag.

7 .1.1 Predicates var, nonvar, atom, integer, float, number, atomic,

compound
Terms may be of different types: variable, integer, atom, etc. If a term is a variable
then it can be, at some point during the execution of the program, instantiated or

147
148 More Built-in Predicates Testing the type of terms 149

uninstantiated. Further, if it is instantiated, its value can be an atom, a structure, etc. ?- atomic( 3.14).
It is sometimes useful to know what the type of this value is. For example, we may yes
want to add the values of two variables, X and Y, by:
?- atom( ==> ).
Z is X + Y
yes
Before this goal is executed, X and Y have to be instantiated to numbers. If we are ?- atom( p(l) ).
not sure that X and Y will indeed be instantiated to numbers at this point then we
should check this in the program before arithmetic is done. no
To this end we can use the built-in predicate number. number( X) is true if X is a ?- compound ( 2 + X)
number or if it is a variable whose value is a number. We say that X must 'currently yes
stand for' a number. The goal of adding X and Y can then be protected by the
following test on X and Y: We will illustrate the need for atom by an example. We would like to count how
many times a given atom occurs in a given list of objects. To this purpose we will
..., number( X), number( Y), Z is X + Y, ...
define a procedure:
If X and Y are not both numbers then no arithmetic will be attempted. So the
count( A, L, N)
number goals 'guard' the goal Z is X + Y before meaningless execution.
Built-in predicates of this sort are: var, nonvar, atom, integer, float, number, atomic, where A is the atom, L is the list and N is the number of occurrences. The first
compound. Their meaning is as follows: attempt to define count could be:
var( X) succeeds if X is currently an uninstantiated variable count(_,[], 0).
nonvar( X) succeeds if X is not a variable, or X is an already instantiated count( A,[A I L], N) !,
variable count( A, L, Nl), % Nl = number of occurrences in tail
atom( X) is true if X currently stands for an atom N is Nl + 1.
integer( X) is true if X currently stands for an integer count( A, [_ I L], N)
float( X) is true if X currently stands for a real number count( A, L, N).
number( X) is true if X currently stands for a number
atomic( X) is true if X currently stands for a number or an atom Now let us try to use this procedure on some examples:
compound( X) is true if X currently stands for a compound term (a structure) ?- count( a, [a,b,a,a], N).
The following example questions to Prolog illustrate the use of these built-in N=3
predicates:
?- count( a,[a,b,X,Y], Na).
?- var( Z), Z = 2. Na=3
Z=2
?- Z = 2, var( Z). ?- count( b,[a,b,X,Y], Nb).
no
Nb=3
?- integer( Z), Z = 2.
no
?- L=[a, b, X, Y], count( a, L, Na), count( b, L, Nb).
?- Z=2, integer( Z), nonvar( Z).
Na=3
Z=2 Nb= 1
X=a
?- atom( 3.14). y=a
no
150 More Built-in Predicates Testing the type of terms 151

In the last example, X and Y both became instantiated to a and therefore we only got Numberl = [D ll . 0 1 2, ..., D,,...].
Nb= 1; but this is not what we had in mind. We are interested in the number of real Number2 = [Dzt.Dzz .....Dz,.... ]
Number3 = [D:n, D32 ..... D3, ...J
occurrences of the given atom, and not in the number of terms that match this atom.
According to this more precise definition of the count relation we have to check rry
\ ��:� �: ll (
��7 from
ig ht
ere carry
( t}O
whether the head of the list is an atom. The modified program is as follows: � �
�
II C Cl ll

I
count(_, [ I, 0).
count( A, [B I L], N)
atom( B), A = B, !, % Bis atom A?
Number!
+ Numbcr2
I D,,.

D 2, ....................]
count( A, L, Nl), 1<, Count in tail
0

N is N1 + 1 ::-: Nurnbt::r3 D;, I

l
count( A, L, N). % Otherwise just count the tail
Figure 7.1 Digit by digit summation. The relations at the indicated ith digit position are
The following, more complex programming exercise in solving cryptarithmetic D 3, =(Cl+ D 1 , + D2,)mod 10; C =(Cl+ D 1 , + D 2,) div 10.
puzzles makes use of the nonvar predicate.

The task is to find SLtch an instantiation of the variables D, 0, N, etc., for which the
7.1.2 A cryptarithmetic puzzle using nonvar sum is valid. When the sum relation has been programmed, the puzzle can be stated
to Prolog by the question:
A popular example of a cryptarithmetic puzzle is ?- sum( [D,O,N,A,L,D], [G,E,R,A,L,D], [R,O,B,E,R,T] ).
DONALD To define the sum relation on lists of digits, we have to implement the actual rules
+GERALD for doing summation in the ciecimal number system. The summation is clone digit
ROBERT by digit, starting with the right-most digits, continuing toward the left, always
taking into account the carry digit from the right. It is also necessary to maintain a
The problem here is to assign decimal digits to the letters D, 0, N, etc., so that the set of available digits; that is, digits that have not yet been used for instantiating
above sum is valid. All letters have to be assigned different digits, otherwise trivial variables already encountered. So, in general, besides the three numbers Nl, NZ and
solutions are possible - for example, all letters equal zero. N, some additional information is involved, as illustrated in Figure 7.1:
We will define a relation
• carry digit before the summation of the numbers;
sum( Nl, NZ, N)
• carry digit after the summation;
where Nl, NZ and N represent the three numbers of a given cryptarithmetic puzzle. • set of digits available before the summation;
The goal surn( Nl, NZ, N) is true if there is an assignment of digits to letters such that • remaining digits, not used in the summation.
N1 +NZ= N.
The first step toward a solution is to decide how to represent the numbersNl, NZ To formulate the sum relation we will use, once again, the principle of generalization
andN in the program. One way of doing this is to represent each number as a list of of the problem: we will introduce an auxiliary, more general relation, suml. suml has
decimal digits. For example, the number 225 would be represented by the list [2,2,5]. some extra arguments, which correspond to the foregoing additional information:
As these digits are not known in advance, an uninstantiated variable will stand for suml( Nl, NZ, N, Cl, C, Digitsl, Digits)
each digit. Using this representation, the problem can be depicted as:
Nl, NZ ancl N are our three numbers, as in the sum relation, Cl is carry from
[D,O,N,A,L, DJ
+ [ G, E, R, A, L, D] the right (before summation of Nl and NZ), and C is carry to the left (after the
[R, O,B, E, R, T] summation). The following example illustrates:
152 More Built-in Predicates Testing the type of terms 153

?- suml( [H,EJ, [6,E], [U,S], l, 1, [l,3,4,7,8,9], Digits). Translating this case into Prolog we have:
I-!�, 8
E =3 suml( [DlINl], [D2IN2], [DI NJ, Cl , C, Digs 1, Digs)
S =7 sum 1( Nl, N2, N, Cl, C2, Digs 1, Digs2),
U =4 digitsum( Dl, D2, C2, D, C, Digs2, Digs).
Digits= [1,9]
It only remains to define the digitsum relation in Prolog. There is one subtle detail
This corresponds to the following summation: that involves the use of the metalogical predicate nonvar. D1, D2 and D have to be
decimal digits. If any of them is not yet instantiated then it has to become
� 1
instantiated to one of the digits in the list DigsZ. This digit has to be deleted from
8 3
the set of available digits. If D1, D2 or D is already instantiated then, of course, none
6 3
4 7
'¾., Solving cryptarithmetic puzzles
As Figure 7.1 shows, Cl and C have to be O if Nl, NZ and N are to satisfy the sum
relation. Digitsl is the list of available digits for instantiating the variables in Nl, NZ sum( Nl, N2, N) :- % Numbers represented as lists of digits
and N; Digits is the list of digits that were not used in the instantiation of these sum l( Nl, N2, N,
variables. Since we allow the use of any decimal digit in satisfying the sum relation, 0, 0, % Carries from right and to left both 0
[0,1,2,3,4,5,6,7,8,9], _). % All digits available
the definition of sum in terms of suml is as follows:
suml( [], [l, [], C, C, Digits, Digits).
sum( Nl, N2, N) :-
suml( [DlINl], [D2INZ], [DINJ, Cl, C, Digsl, Digs)
suml( Nl, N2, N, 0, 0, [0,1,2,3,4,5,6,7,8,9], _ ).
suml( Nl, N2, N, Cl, C2., Digsl, Digs2),
The burden of the problem has now shifted to the suml relation. This relation is, digitsum( Dl, D2, C2, D, C, Digs2, Digs).
however, general enough that it can be defined recursively. We will assume, without digitsum( Dl, D2, Cl, D, C, Digsl, Digs)
loss of generality, that the three lists representing the three numbers are of equal del_var( Dl, Digsl, Digs2), % Select an available digit for D 1
length. Our example problem, of course, satisfies this constraint; if not, a 'shorter' de!_var( D2, Digs2, Digs3), % Select an available digit for D2
del_var( D, Digs3, Digs), % Select an available digit for D
number can be prefixed by zeros.
S is Dl + D2 + Cl,
The definition of suml can be divided into two cases:
D is S mod 1 0, % Remainder
(1) The three numbers are represented by empty lists. Then:
C is SII 10. '¾, Integer division
del_var( A, L, L) :-
suml( [], [], [], C, C, Digs, Digs). nonvar( A), !. % A already instantiated
(2) All three numbers have some left-most digit and the remaining digits on their del_var( A, [A! L], L). o;,, Delete the head
right. So they are of the form: del_var( A, [B I L], [BILl] )
del_var( A, L, Ll). 1,, Delete from tail
0
[DlINll, [D2IN2], [DIN]
% Some puzzles
In this case two conditions must be satisfied:
puzzlel( [D,O,N,A,L,D],
(a) The three numbers Nl, NZ and N have to satisfy the suml relation, giving [G,E,R,A,L,D],
some carry digit, CZ, to the left, and leaving some unused subset of [R,O,B,E,R,T] ).
decimal digits, Digs2. puz.2le2( [0,S,E,N,D],
(b) The left-most digits D1, D2 and D, and the carry digit CZ have to satisfy the [0,M,O,R,E],
[M,O,N,E,Y] ).
relation indicated in Figure 7. l: CZ, D1 and D2 are added giving D and
a carry to the left. This condition will be formulated in our program as a
relation digitsum. Figure 7.2 A program for cryptarithmetic puzzles.
154 More Built-in Predicates Constructing and decomposing terms: - .. , functor, arg, name 155

of the available digits will be spent. This is realized in the program as a non­ to store a new element into a list. Assume that all of the elements that can be stored
deterministic deletion of an item from a list. If this item is non-variable then are non-variables. List contains all the stored elements followed by a tail that is not
nothing is deleted (no instantiation occurs). This is programmed as: instantiated and can thus accommodate new elements. For example, let the existing
elements stored be a, b and c. Then
clel_var( Item, List, List) :­
nonvar(Item), !. % Item already instantiated List=[a, b, c I Tail]
clel_var( Item, [Item I List], List). 0
/c, Delete the head where Tail is a variable. The goal
del_var( Item, [A I List], [A I Listlj) adcl_to_tail( d, List)
de!_var(Item, List, Listl). % Delete Item from tail
will cause the instantiation
A complete program for cryptarithmetic puzzles is shown in Figure 7.2. The Tail= [cl I t'-iewTail] and List=[a, b, c, cl I NewTail]
program also includes the definition of two puzzles. The question to Prolog about
DONALD, GERALD and ROBERT, using this program, would be: Thus the structure can, in effect, grow by accepting new items. Define also the
corresponding membership relation.
?- puzzlel(NJ, NZ, N), sum(Nl, NZ, N).

Sometimes this puzzle is made easier by providing part of the solution as an

additional constraint that D be equal 5. The puzzle in this form could be com­
municated to Prolog using sum!:
7.2 Constructing and decomposing terms: = .. , functor, arg, name
···· ········· · ····················································································································· ·······
'/-- suml( [5,0,N,A,L,5], There are three built-in predicates for decomposing terms ancl constructing new
[G,E,R,A,L,5], terms: functor, arg and'=..'. We will first look at=.. , which is written as an inftx
[R,O,R,E,R,T], operator and reads as 'univ'. The goal
0, 0, [0,1,2,3,4,6,7,8,91, _ ).
Terrn=.. L
It is interesting that in both cases there is only one solution. That is, there is only is true if L is a list that contains the principal functor of Term, followed by its
one way of assigning digits to letters. arguments. The following examples illustrate:
?- f(a, b)=.. L.
Exercises L=[f, a, b]
?- T=.. [rectangle, 3, SJ.
7.1 Write a procedure simplify to symbolically simplify summation expressions with T=rectangle(3, S)
numbers and symbols (lower-case letters). Let the procedure rearrange the expres­
sions so that all the symbols precede numbers. These are examples of its use: ?- Z=.. [p, X, f(X,Y)].
Z = p( X, f(X,Y) )
?- simplify(1+1 + a, E).
Why would we want to decompose a term into its components - its functor and
E=a+2
its arguments? Why construct a new term from a given functor and arguments? The
?- simplify( 1 +a+4 + 2 + b + c, E). following example illustrates the need for this.
E=a+b+c+7 Let us consider a program that manipulates geometric figures. Figures are squares,
rectangles, triangles, circles, etc. They can, in the program, be represented as terms
?- simplify( 3 + x + x, E). such that the functor indicates the type of figure, and the arguments specify the size
E= 2•x+ 3 of the figure, as follows:

7.2 Define the procedure: square(Side)

triangle(Side!, Side2, Side3)
add_to_tail(Item, List) circle(R)
 Constructing and decomposing terms: - .. , functor, arg, name 157
156 More Built-in Predicates

as follows: if all occurrences of Subterm in Term are substituted by Subterml then we

One operation on such figures can be enlargement. We can implement this as a
get Terml. For example:
three-argument relation
?- substitute( sin(x), 2,sin(x),f(sin(x)), t, F).
enlarge( Fig, Factor, Figl)
F = 2,t.f(t)
where Fig and Figl are geometric figures of the same type (same functor), and the
By 'occurrence' of Subterm in Term we will mean something in Term that matches
parameters of Figl are those of Fig multiplicatively enlarged by Factor. For simplicity,
Subterm. We will look for occurrences from top to bottom. So the goal
we will assume that all the parameters of Fig are already known; that is, instantiated
to numbers, and so is Factor . One way of programming the enlarge relation is: ?- substitute( a+b, f( a, A+B), v, F).

enlarge( square(A), F, square(Al) ) will produce

r\l is f,A. F = f( a, v+v)
F = f( a, v)
enlarge( circle(R), F, circle{Rl) ) A=a and not A=a+b
Rl is f,Rl. B=b B=a+b
enlarge( rectangle(A,B), F, rectangle{Al,Bl) ) In defining the substitute relation we have to consider the following decisions
Al is hA, Bl is F,B.
depending on the case:
If Subterm = Term then Tennl= Subterml;
This works, but it is awkward when there are many different figure types. We have to otherwise if Term is 'atomic' (not a structure)
foresee all types that may possibly occur.Thus, we need an extra clause for each type then Terml= Term (nothing to be substituted),
although each clause says essentially the same thing: take the parameters of the otherwise the substitution is to be carried out on the arguments of Term.
original figure, multiply all the parameters by the factor, and make a figure of
These rules can be converted into a Prolog program, shown in Figure 7.3.
the same type with new parameters.
One (unsuccessful) attempt to handle, at least, all one-parameter figures with one
clause could be: % substitute( Subterm, Term, Subterml, Terml):
% if all occurrences of Subterm in Term are substituted with Subterm 1 then we get Terml.
enlarge( Type(Par), F, Type(Parl))
Parl is hPar.
01<, Case l: Substitute whole term
substitute( Term, Term, Term 1, Term 1) !.
However, this is normally not allowed in Prolog because the functor has to be an
atom; so the variable Type would not be accepted syntactically as a functor. The % Case 2: Nothing to substitute if Term atomic
correct method is to use the predicate '= .. '. Then the enlarge procedure can be substitute(_, Term,_, Term)
stated completely generally, for any type of object, as follows: atomic( Term), !.
enlarge( Fig, F, Figl) :- % Case 3: Do substitution on arguments
Fig= .. [Type I Parameters],
substitute( Sub, Term, Sub 1, Terml)
multiplylist( Parameters, F, Parametersl), 'Yt, Get arguments
Term=..[FI Args],
Figl=..[TypeI Parametersl]. % Perform substitution on them
substlist( Sub, Args, Sub 1, Argsl),
multiplyli st( [ ),_, [] ). Tennl=-.[FI Argsl].
multiplylist( [XI L], F, [XlI Ll] ) substlist(_, [],_, [] ).
Xl is hX. multiplylist( L, F, Ll). substlist( Sub, [Tenn I Terms], Sub 1, [Terml I Tennsl] )
substitute( Sub, Term, Subl, Tennl),
Our next example of using the '= ..' predicate comes from symbolic manipula­
substlist( Sub, Terms, Sub 1, Termsl).
tion of formulas where a frequent operation is to substitute some subexpression by
another expression. We will define the relation
Figure 7 .3 A procedure for substituting a subterm of a term by another subterm.
substitute( Subtenn , Tenn , Subtennl, Tennl)
 Constructing and decomposing terms: = .. , functor, arg, name 159
158 More Built-in Predicates

the functor predicate. The goal

Terms that are constructed by the '= .. ' predicate can, of course, be also used as The last example shows a special application of
al' term whose principal functor is date with
goals. The advantage of this is that the program itself can, during execution, functor( D, date, 3) generates a 'gener
arguments are uninstantiated
generate and execute goals of forms that were not necessarily foreseen at the time three arguments. The term is general in that the three
example:
of writing the program. A sequence of goals illustrating this effect would be variables whose names are generated by Prolog. For
something like the following:
D=date( _5, _6, _7)
obtain( Functor), example above by the three arg
compute(Arglist), These three variables are then instantiated in the
Goal = .. [Functor I Arglist], goals.
predicate name for constructing/
Goal Related to this set of built-in predicates is the
We will repeat its meaning here for
decomposing atoms, introduced in Chapter 6.
Here, obtain and compute are some user-defined procedures for getting the
completeness.
components of the goal to be constructed. The goal is then constructed by '= .. ',
and invoked for execution by simply stating its name, Goal. name(A, L)
cters in atom A.
Some implementations of Prolog may require that all the goals, as they appear in is true if L is the list of ASCII codes of the chara
the program, are syntactically either atoms or structures with an atom as the
principal functor. Thus a variable, regardless of its eventual instantiation, in such a
case may not be syntactically acceptable as a goal. This problem is circumvented by Exercises
another built-in predicate, call, whose argument is the goal to be executed.
is true if Term does not contain any
.-\ccordingly, the above example would be rewritten as: 7.3 Define the predicate ground( Term) so that it
uninstantiated variables.
produces the 'outer-most' substitution
Goal= .. [Functor I Arglist], 7.4 The substitute procedure of this section only
dure so that all possible alternative
call( Goal) when there are alternatives. Modify the proce
gh backt rackin g. For example:
Sometimes we may want to extract from a term just its principal functor or one of its substitutions are produced throu
arguments. We can, of course, use the '= .. ' relation. But it can be neater, and also ?- substih1te( a+b, f(A+B), new, NewTenn).
more efficient, to use one of the other two built-in procedures for manipulating A=a
terms: functor and arg. Their meaning is as follows: a goal B=b
functor( Term, F, N) NewTerm=f( new);
A= a+b
is true if F is the principal functor of Term and N is the arity of F. A goal
B= a+b
arg( :--;_ Term, A) -> NewTerm= f( new+new)
is true if A is the Nth argument in Term, assuming that arguments are numbered Our original version only finds the first answer.
from left to right starting with 1. The following examples illustrate:
7.5 Define the relation
?- functor( t( f(X), X, t), Fun,Arity).
subsumes( Term 1, Tenn2)
Fun=t
.-\.rity=3 so that Term! is more general than Term2. For example:

'· arg( 2, f( X, t(a), t(b)), Y). ?- subsumes( X, c).

Y=t(a) yes
?- functor( D, date, 3), ?- subsumes( g(X), g(t(Y)) ).
arg( 1, D, 29),
yes
arg( 2, D, june),
arg( 3, D, 1982). ?- subsumes( f(X,X), f(a,b) ).
D = date( 29, june, 1982) no
160 More Built-in Predicates Database manipulation 161

7.3 Y.?.:.i ?.��..�!0.?.�. ?.'...�g·�a· ·��t.Y..�.0.?..�.?.f!lP�.'.i �?.0..................................... .

from Section 7.1. This time let N be the number of literal occurrences of the term
Term in a list List:

When do we consider two terms to be equa!7 Until now we have introduced three count(_,[], 0).
kinds of equality in Prolog. The first was based on matching, written as: count(Term, [Head I L ), N)
X= Y Tenn== Head, !,
count(Tenn, L, Nl),
This is true if X and Y match. Another type of equality was written as: N is NI+ 1
X is E
count(Term, L, N).
This is true if X matches the value of the arithmetic expression E. We also had: We have already seen predicates that compare terms arithmetically, for example
El=:= E2 X+2 < 5. Another set of built-in predicates compare terms alphabetically and thus
define an ordering relation on terms. For example, the goal
This is true if the values of the arithmetic expressions El and E2 are equal. In
contrast, when the values of two arithmetic expressions are not equal, we write: X@<Y
El=\=E2 is read: term X precedes term Y. The precedence between simple terms is determined
by alphabetical or numerical ordering. The precedence between structures is
Sometimes we are interested in a stricter kind of equality: the literal equality of two
determined by the precedence of their principal functors. If the principal functors
terms. This kind of equality is implemented as another built-in predicate written as
are equal, then the precedence between the top-most, left-most functors in the
an infix operator'==':
subterms in X and Y decides. Examples are:
Tl== T2
?- paul@< peter.
This is true if terms Tl and T2 are identical; that is, they have exactly the same yes
structure and all the corresponding components are the same. In particular, the
names of the variables also have to be the same. The complementary relation is 'not ?- f(2)@< f(3).
identical', written as: yes
Tl\==T2 ?- g(2)@< f(3).
Here are some examples: 110

?- f( a, b)== f( a, b). ?- g(2)@>= f(3).

yes yes
?- f( a, b)== f( a, X). ?- f( a, g(b), c)@< f( a, h(a), a).
no yes
?- f( a, X)== f( a, Y). All the built-in predicates in this family are@<, @=<,@> , @>= with their obvious
no meanings.
?- X\==Y.
yes
?- t( X, f(a,Y) )== t( X, f(a,Y) ). 7.4 Database manipulation
··········································································································································
yes
According to the relational model of databases, a database is a specification of a set
As an example, let us redefine the relation
of relations. A Prolog program can be viewed as such a database: the specification of
count( Tenn, List, N) relations is partly explicit (facts) and partly implicit (rules). Some built-in predicates
162 More Built-in Predicates Database manipulation 163

make it possible to update this database during the execution of the program. This is ?- disgusting.
done by adding (during execution) new clauses to the program or by deleting yes
existing clauses. Predicates that serve these purposes are assert, asserta, assertz and
?- retract( fog).
retract.
A goal yes

assert( C) ?- disgusting.
no
always succeeds and, as its side effect, causes a clause C to be 'asserted' -- that is,
added to the database. A goal ?- assert( sunshine).
yes
retract( C)
?- funny.
does the opposite: it deletes a clause that matches C. The following conversation
yes
with Prolog illustrates:
?- retract( raining).
?- crisis.
yes
no
?- nice.
?- assert( crisis).
yes
yes
Clauses of any form can be asserted or retracted. However, depending on the
?- crisis.
implementation of Prolog, it may be required that predicates manipulated through
yes assert/retract be declared as dynamic, using the directive dynamic( Predicatelndicator).
?- retract( crisis). Predicates that are only brought in by assert, and not by consult, are automatically
assumed as dynamic.
yes
The next example illustrates that retract is also non-deterministic: a whole set of
?- crisis. clauses can, through backtracking, be removed by a single retract goal. Let us assume
no that we have the following facts in the 'consulted' program:

Clauses thus asserted act exactly as part of the 'original' program. The following fast( ann).
slow( tom).
example shows the use of assert and retract as one method of handling changing
slow( pat).
situations. Let us assume that we have the following program about weather:
We can add a rule to this program, as follows:
nice
sunshine, not raining. ?- assert(
funny :- ( faster(X, Y)
sunshine, raining. fast(X), slow(Y) ) ).

disgusting :­ yes
raining, fog. ?- faster( A, B).
raining. A= ann
fog. B= tom

The following conversation with this program will gradually update the database: ?- retract( slow(X) ).
X= tom;
?- nice. X= pat;
no no
 Database manipulation 165
164 More Built-in Predicates

Y, compute Z
?- faster( arrn, _). of integers between O and 9 as follows: generate a pair of integers X and
of th product table, and then force the
no is X•Y, assert the three numbers as one lin e e
backtrac king, another pair of integ ers to be
failure. The failur e will cause, through
Notice that when a rule is asserted, the syntax requires that the rule (as an argument line tabulate d, tc. Th following proc edur e maketable
found and so anoth e r e e

to assert) be enclosed in par entheses. implements this idea:

When ass erting a claus e, we may want to specify the position at which the new
rnaketable :-
clause is inserted to the database. The pr edicates asserta and assertz enable us to
L = [0,1,2,3, 4,5,6,7,8,9],
control th e position of insertion. The goal member( X, L), % Choose first factor
member( Y, L), % Choose second factor
asserta( C)
Z is X,Y,
aclcls Cat th e beginning of the database. The goal assert( product(X,Y,Z) ),
fail.
assertz( C)
The question
adds Cat the end of the database. We will assume that assert is equivalent to assertz,
as usual in Prolog implementations. The following example illustrates these effects: ?- maketable.

?- assert( p(b) ), assertz( p(c) ), assert( p(d) ), asserta( p(a) ). will, of course, not succeed, but it will, as a side effect, add the whole product table
to the database. After that we can ask, for example, what pairs give the product 8:
yes
?- product( A, B, 8).
?- p( X).
X =a; A=l
X=b; B = 8;
X= c; A=2
X=d B=4;

There is a relation between consult and assertz. Consulting a file can be defined in
terms of assertz as follows: to consult a file, read each term (clause) in th e file and A remark on the style of programming should be made at this stage. The
assert it at the encl of the database. foregoing examples illustrate some obviously useful applications of assert and
One useful application of asserta is to store alr eady computed answers to retract. However, their use requires special care. Excessiv e and careless use of these
questions. For example, let th ere be a predicate facilities cannot be r ecommended as good programming style. By asserting and
retracting we, in fact, modify the program. Therefore relations that hold at some
solve( Problem, Solution)
point will not be true at some other time. At different times the same questions
defined in th e program. W e may now ask som e question and r equest that the answer receive differ ent answers. A lot of asserting and retracting may thus obscure the
be r emembered for futur e questions. m eaning of the program. The resulting behaviour of the program may becom e
difficult to understand, difficult to explain and to trust.
?- solve( problem1, Solution),
asserta( solve( problem1, Solution) ).
If the first goal above succeeds then the answer (Solution) is stored and used, as any Exercises
other clause, in answering further questions. The advantage of such a 'memoization'
of answers is that a further quest ion that matches the asserted fact will normally be
7.6 (a) Write a Prolog question to remove the whole product table from the database.
answered much quicker than the first one. The result now will be simply retrieved as
a fact, and not computed through a possibly time-consuming process. This tech­ (b) Modify the question so that it only removes those entries where the product is 0.
nique of storing derived solutions is also called 'caching'.
7. 7 Define the relation
An extension of this idea is to use asserting for generating all solutions in the
form of a table of facts. For example, we can generate a table of products of all pairs copy_tem1( Term, Copy)
166 More Built-in Predicates bagof, setof and finda/1 167

7.6 �.�9?.(..��.�?.'...��.�..(!.0.�?.!!.........................................................................................
which will produce a copy of Tenn so that Copy is Term with all its variables
renamed. This can be easily programmed by using asserta and retract. In some
Prologs copy_term is provided as a built-in predicate.
We can generate, by backtracking, all the objects, one by one, that satisfy some goal.
Each time a new solution is generated, the previous one disappears and is not
accessible any more. However, sometimes we would prefer to have all the generated
objects available together - for example, collected into a list. The built-in predicates
7.5 Control facilities bagof, setof and findall serve this purpose.
The goal
So far we have ccvered most of the extra control facilities except repeat. For
completeness the complete set is presented here. bagof( X, !', L)
• mt, written as'!', prevents backtracking. It was introduced in Chapter 5. A useful will produce the list L of all the objects X such that a goal P is satisfied. Of course,
predicate is once( P) defined in terms of cut as: this usually makes sense only .if X and P have some common variables. For example,
let us have these facts in the program:
once( P) :- P, !.
age( peter, 7).
once( P) produces one solution only. The cut, nested in once, does not prevent
age( ann, 5).
backtracking in other goals. age( pat, 8).
• fail is a goal that always fails. age( tom, S).
• true is a goal that always succeeds. Then we can obtain the list of all the children of age 5 by the goal:
• not( !') is negation as failure that behaves exactly as if defined as:
?• bagof( Child, age( Child, 5), List).
not( P) :- P,!, fail; true. List=[ ann, tom]
Some problems with cut and not were discussed in detail in Chapter 5. If, in the above goal, we leave the age unspecified, then we get, through back­
• call( P) invokes a goal P. It succeeds if P succeeds. tracking, three lists of children, corresponding to the three age values:
• repeat is a goal that always succeeds. Its special property is that it is non­ ?- bagof( Child, age( Child, Age), List).
deterministic; therefore, each time it is reached by backtracking it generates
another alternative execution branch. repeat behaves as if defined by: Age= 7
List= [ peter];
repeat. Age= 5
repeat :- repeat. List= [ arrn, tom];
A typical way of using repeat is illustrated by the following procedure dosquares Age= 8
which reads a sequence of numbers and outputs their squares. The sequence is List= [ pat];
concluded wi.th the atom stop, which serves as a signal for the procedure to no
terminate.
We may prefer to have all of the children in one list regardless of their age. This can
dosquares
be achieved by explicitly stating in the call of bagof that we do not care about the
repeat,
read( X), value of Age as long as such a value exists. This is stated as:
( X=stop,!
?- bagof( Child, Age A age( Child, Age), List).
Y is X•X, write(Y), List= [ peter, ann, pat, tom]
fail
). Syntactically, 'A' is a predefined infix operator of type xfy.
168 More Built-in Predicates Summary 169

If there is no solution for P in the goal bagof( X, P, L), then the bagof goal simply
findall( X, Goal, Xlist)
fails. If the same object X is found repeatedly, then all of its occurrences will appear % Find a solution
call( Goal),
in L, which leads to duplicate items in L. assertz( queue(X) ), % Assert it
The predicate setof is similar to bagof. The goal fail; % Try to find more solutions
assertz( queue(bottom) ), % Mark end of solutions
setof( X, P, L)
collect( Xlist). % Collect the solutions
will again produce a list L of objects X that satisfy P. Only this time the list L will be " .. collect( L) :-
ordered, and duplicate items, if there are any, will be eliminated. The ordering of the retract( queue(X) ), !, % Retract next solution
objects is according to built-in predicate@<, which defines the precedence among ( X== bottom,!, L= [] % End of solutions?
terms. For example:
L = [X I Rest], collect( Rest) ). % Otherwise collect the rest
?- setof( Child, Age A age( Child, Age), ChildList),
setof( Age, Child A age( Child, Age), AgeList).
ChildList= [ ann, pat, peter, tom] Figure 7.4 An implementation of the fmdall relation.
AgeList= [ S, 7, 8]

There is no restriction on the kind of objects that are collected. So we can, for
example, construct the list of children ordered by their age, by collecting pairs of the
form Age/Child:
?- setof( Age/Child, age( Child, Age), List). 7.8 Use bagof to define the relation powerset( Set, Subsets) to compute the set of all
List= [ 5/ann, 5/tom, 7/peter, 8/pat] subsets of a given set (all sets represented as lists).

Another predicate of this family, similar to bagof, is findall. 7.9 Use bagof to define the relation
findall( X, P, L)
copy_term( Term, Copy)
produces, again, a list of objects that satisfy P. The difference with respect to bagof is
that all of the objects X are collected regardless of (possibly) different solutions for such that Copy is Term with all its variables renamed.
variables in P that are not shared with X. This difference is shown in the following
example:
?- findall( Child, age( Child, Age), List). Summary
·· ·· · ·· · ·· · ·· · ··· ··· ···· · ····· ·· ···· · ··· ··················· · ··· · · · ··············· · ········· · · · ·········· · · ···· · ···························
List= [ peter, ann, pat, tom]
• A Prolog implementation normally provides a set of built-in procedures to
If there is no object X that satisfies P then findall will succeed with L = [ J.
accomplish several useful operations that are not possible in pure Prolog. In this
If findall is not available as a built-in predicate in the implementation used then it
chapter, such a set of predicates available in many Prolog implementations was
can be easily programmed as follows. All solutions for P are generated by forced
introduced.
backtracking. Each solution is, when generated, immediately asserted into the
database so that it is not lost when the next solution is found. After all the solutions • The type of a term can be tested by the following predicates:
have been generated and asserted, they have to be collected into a list and retracted var( X) X is a (non-instantiated) variable
from the database. This whole process can be imagined as all the solutions generated nonvar( X) X is not a variable
forming a queue. Each newly generated solution is, by assertion, added to the end of atom( X) X is an atom
this queue. When the solutions are collected the queue dissolves. Note, in addition, integer( X) X is an integer
that the end of this queue has to be marked, for example, by the atom 'bottom' float( X) X is a real number
(which, of course, should be different from any solution that is possibly expected). atomic( X) X is either an atom or a number
An implementation of findall along these lines is shown as Figure 7.4. compound( X) X is a structure
170 More Built-in Predicates

chapter 8
• Terms can be constructed or decomposed:
Term = .. [ Functor I ArgumentList]
functor( Term, Functor, Arity)
arg( N, Term, Argument)

•
name( Atom, CharacterCodes)
Terms can be compared:
Programming Style and Technique
X=Y X and Y match
X== y X and Y are identical 8.1 General principles of good programming 171
X \== y X and Y are not identical
8.2 How to think about Pro log programs 173
X =: =Y X and Y are arithmetically equal
X= \=Y X and Y are not arithmetically equal 8.3 Programming style 176
X <Y arithmetic value of X is less than Y (related: = <, >, > =)
X @<Y term X precedes term Y (related:@=<,@>,@>=) 8.4 Debugging 179
• A Prolog program can be viewed as a relational database that can be updated by
8.5 Improving efficiency 181
the following procedures:
assert( Clause) add Clause to the program
asserta( Clause) add at the beginning
assertz( Clause) add at the end
retract( Clause) remove a clause that matches Clause
• All the objects that satisfy a given condition can be collected into a list by the In this chapter we will review some general principles of good programming and
predicates: discuss the following questions in particular: How to think about Prolog programs?
bagof( X, P, L) Lis the list of all X that satisfy condition P vVhat are elements of good programming style in Prolog7 How to debug Prolog
setof( X, P, L) L is the sorted list of all X that satisfy condition P programs? How to make Prolog programs more efficient?
findall( X, P, L) similar to bagof
• repeat is a control facility that generates an unlimited number of alternatives for
backtracking.
8.1 General principles of good programming
What is a good program? Answering this question is not trivial as there are several
criteria for judging how good a program is. Generally accepted criteria include the
following:
• Correctness Above all, a good program should be correct. That is, it should do
what it is supposed to do. This may seem a trivial, self-explanatory requirement.
However, in the case of complex programs, correctness is often not attained. A
common mistake when writing programs is to neglect this obvious criterion and
pay more attention to other criteria, such as efficiency or external glamour of the
program.
• User-friendliness A good program should be easy to use and interact with.
• Ef{lciency A good program should not needlessly waste computer time and
memory space.

171
 How to think about Prolog programs 173
172 Programming Style and Technique

• Rene/ability A good program should be easy to read and easy to understand. It and to data structures. In the initial stages we normally work with more abstract,
should not be more complicated than necessary. Clever programming tricks that bulky units of information whose structure is refined later.
obscure the meaning of the program should be avoided. The general organiza­ Such a strategy of top-clown stepwise refinement has the following advantages:
tion of the program and its layout help its readability.
• it allows for formulation of rough solutions in terms that are most relevant to
• Modifiability A good program should be easy to modify and to extend. the problem;
Transparency and modular organization of the program help modifiability.
• • in terms of such powerful concepts, the solution should be succinct and simple,
Robustness A good program should be robust. It should not crash immediately and therefore likely to be correct;
when the user enters some incorrect or unexpected data. The program should,
in the case of such errors, stay 'alive' and behave reasonably (should report • each refinement step should be small enough so that it is intellectually manage­
errors). able; if so, the transformation of a solution into a new, more detailed
representation is likely to be correct, and so is the resulting solution at the next
• Docwnentation A good program should be properlv documented. The minimal level of detail.
documentation is the program's listing including sufficient program comments.
In the case of Prolog we may talk about the stepwise refinement of relations. If the
The importance of particular criteria depends on the problem and on the
problem suggests thinking in algorithmic terms, then we can also talk about
circumstances in which the program is written, and on the environment in which
refinement of algorit!zms, adopting the procedural point of view in Prolog.
it is used. There is no doubt that correctness has the highest priority. The issues of
In order to properly refine a solution at some level of detail, and to introduce
readability, user-friendliness, modifiability, robustness and documentation are
useful concepts at the next lower level, we need ideas. Therefore programming is
usually given, at least, as much priority as the issue of efficiency.
creative, especially so for beginners. With experience, programming gradually
There are some general guidelines for practically achieving the above criteria.
becomes less of an art and more of a craft. But, nevertheless, a major question is:
One important rule is to first think about the problem to be solved, and only then to
How do we get ideas? i\,fost ideas come from experience, from similar problems
start writing the actual code in the programming language used. Once we have
whose solutions we know. If we do not know a direct programming solution,
developed a good understanding of the problem and the solution is well thought
another similar problem could be helpful. Another source of ideas is everyday life.
through, the actual coding will be fast and easy, and there is a good chance that we
For example, if the problem is to write a program to sort a list of items we may get an
will soon get a correct program.
idea from considering the question: How would I myself sort a set of exam papers
A common mistake is to start writing the code even before the full definition of
according to the alphabetical order of students?
the problem has been understood. A fundamental reason why early coding is bad
General principles of good programming outlined in this section basically apply
practice is that the thinking about the problem and the ideas for a solution should
to Prolog as well. We will discuss some details with particular reference to Prolog in
be done in terms that are most relevant to the problem. These terms are usually far
the following sections.
from the syntax of the programming language used, and they may include natural
language statements and pictorial representation of ideas.
Such a formulation of the solution will have to be transformed into the
programming language, but this transformation process may not be easy. A good
approach is to use the principle of stepwise refinement. The initial formulation of 8.2 How to think about Prolog programs
· · · ·· · · · · · · · · · · · · · ·· ····· · · ·· ·················· ·· · · · · · · · ···· · · · · · · · · ················ ·· · · · · · · · · · · · · ··· · · · · · · · ······· · · · · · · · · · ········· ·· · · ·
the solution is referred to as the 'top-level solution', and the final program as the
'bottom-level solution'. One characteristic feature of Prolog is that it allows for both the procedural and
According to the principle of stepwise refinement, the final program is developed declarative way of thinking about programs. The two approaches have been
through a sequence of transformations, or 'refinements', of the solution. We start discussed in detail in Chapter 2, and illustrated by examples throughout the text.
with the first, top-level solution and then proceed through a sequence of solutions; Which approach will be more efficient and practical depends on_ the problem.
these are all equivalent, but each solution in the sequence is expressed in more Declarative solutions are usually easier to develop, but may lead to an inefficient
detail. In each refinement step, concepts used in previous formulations are program.
elaborated to greater detail and their representation gets closer to the programming During the process of developing a solution we have to find ideas for reducing
language. It should be realized that refinement applies both to procedure definitions problems to one or more easier subproblems. An important question is: How do we
174 Programming Style and Technique How to think about Prolog programs 175

find proper subproblems? There are several general principles that often work in One reason why recursion so naturally applies to defining relations in Prolog is
Prolog programming. These will be discussed in the following sections. that data objects themselves often have recursive strncture. Lists and trees are such
objects. A list is either empty (boundary case) or has a head and a tail that is itself a
list (general case). A binary tree is either empty (boundary case) or it has a root and
8.2.1 Use of recursion two subtrees that are themselves binary trees (general case). Therefore, to process a
whole non-empty tree, we must do something with the root, and process the
The principle here is to split the problem into cases belonging to two groups: subtrees.
(1) trivial, or 'boundary' cases;
(2) 'general' cases where the solution is constructed from solutions of (simpler) 8.2.2 Generalization
versions of the original problem itself.
[n Prolog we use this technique all the time. Let us look at one more example: It is often a good idea to generalize the original problem, so that the solution to the
processing a list of items so that each item is transformed by the same transforma­ generalized problem can be formulated recursively. The original problem is then
tion rule. Let this procedure be solved as a special case of its more general version. Generalization of a relation
typically involves the introduction of one or more extra arguments. A major
maplist( List, F, NewList) problem, which may require deeper insight into the problem, is how to find the
where List is an original list, Fis a transformation rnle (a binary relation) and NewList right generalization.
is the list of all transformed items. The problem of transforming List can be split into As an example let us revisit the eight queens problem. The original problem was
two cases: to place eight queens on the chessboard so that they do not attack each other. Let us
call the corresponding relation:
(l) Boundary case: List = [ ]
eightqueens( Pos)
if List = [] then NewList = [ ] , regardless of F
This is true if Pos is a position with eight non-attacking queens. A good idea in this
(2) General case: List = [X I Tail] case is to generalize the number of queens from eight to N. The number of queens
To transform a list of the form [X I Tail], do: now becomes the additional argument:
transform the item X by rnle F obtaining NewX, and nqueens( Pos, N)
transform the list Tail obtaining NewTail;
the whole transformed list is [NewX I NewTailj. The advantage of this generalization is that there is an immediate recursive
formulation of the nqueens relation:
In Prolog:
maplist( [ ], _, [ l ). (1) Boundary case: N = 0
map!ist( [X I Tail], F, [NewX I NewTail] ) To safely place zero queens is trivial.
G = .. [F, X, NewX],
call( G), (2) General case: N > 0
maplist( Tail, F, NewTail).
To safely place N queens on the board, satisfy the following:
Suppose we have a list of numbers and want to compute the list of their squares.
maplist can be used for this as follows: • achieve a safe configuration of (N - 1) queens; and
square( X, Y) • add the remaining queen so that she does not attack any other queen.
Y is X•X.
Once the generalized problem has been solved, the original problem is easy:
?- maplist( (2, 6, 5], square, Squares).
Squares = [ 4, 36, 25] eightqueens( Pos) :- nqueens( Pos, 8).
176 Programming Style and Technique Programming style 177

8.2.3 Using pictures • The layout of programs is important. Spacing, blank lines and indentation
should be consistently used for the sake of readability. Clauses about the same
When searching for ideas about a problem, it is often useful to introduce some procedure should be clustered together; there should be blank lines between
graphical representation of the problem. A picture may help us to perceive some clauses (unless, perhaps, there are numerous facts about the same relation); each
essential relations in the problem. Then we just have to describe what we see in the goal can be placed on a separate line. Prolog programs sometimes resemble
picture in the programming language. poems for the aesthetic appeal of ideas and form.
The use of pictorial representations is often useful in problem solving in general; • Stylistic conventions of this kind may vary from program to program as they
it seems, however, that it works with Prolog particularly well. The following depend on the problem and personal taste. lt is important, however, that the
arguments explain why: same conventions are used consistently throughout the whole program.
(1) Prolog is particularly suitable for problems that involve objects and relations • The cut operator should be used with care. Cut should not be used if it can be
between objects. Often, such problems can be naturally illustrated by graphs in easily avoided. It is better to use, where possible, 'green cuts' rather than 'red
which nodes correspond to objects and arcs correspond to relations. cuts'. As discussed in Chapter 5, a cut is callee! 'green' if it can be removed
(2) Structured data objects in Prolog are naturally pictured as trees. without altering the declarative meaning of the clause. The use of 'red cuts'
should be restricted to clearly defined constructs such as not or the selection
(3) The declarative meaning of Prolog facilitates the translation of pictorial
between alternatives. An example of the latter construct is:
representations into Prolog because, in principle, the order in which the
picture is described does not matter. We just put what we see into the program if Condition then Goall else Goal2
in any order. (For practical reasons of the program's efficiency this order will
possibly have to be polished later.) This translates into Prolog, using cut, as:
Condition, !, % Condition true?
Goall <){, If yes then Goal I
8.3 Programming style
·· · ··· ··· ··· ·· ·········· · · · · · · ······· ··· Goal2 % Otherwise Goal2
• The not procedure can also lead to surprising behaviour, as it is related to cut. We
The purpose of conforming to some stylistic conventions is:
have to be well aware of how not is defined in Prolog. However, if there is a
• to reduce the clanger of programming errors; and dilemma between not and cut, the former is perhaps better than some obscure
• to produce programs that are readable and easy to understand, easy to debug and construct with cut.
to modify. • Program modification by assert and retract can grossly degrade the transparency
of the program's behaviour. In particular, the same program will answer the
We will review here some ingredients of good programming style in Prolog: some
same question differently at different times. In such cases, if we want to
general rules of good style, tabular organization of long procedures and commenting.
reproduce the same behaviour we have to make sure that the whole previous
state, which was modified by assertions and retractions, is completely restored.
8.3.1 Some rules of good style • The use of a semicolon may obscure the meaning of a clause. The readability can
sometimes be improved by splitting the clause containing the semicolon into
• Program clauses should be short. Their body should typically contain no more more clauses; but this will, possibly, be at the expense of the length of the
than a few goals. program and its efficiency.
• Procedures should be short because long procedures are hard to understand. To illustrate some points of this section consider the relation
However, long procedures are acceptable if they have some uniform structure
merge( Listl, List2, List3)
(this will be discussed later in this section).
• Mnemonic names for procedures and variables should be used. Names should where Listl and List2 are ordered lists that merge into List3. For example:
indicate the meaning of relations and the role of data objects. merge( [2,4,7], [l,3,4,8], [1,2,3,4,4,7,8))
178 Programming Style and Technique Debugging 179

The following is an implementation of merge in bad style: Undercommenting is a usual fault, but a program can also be overcommented.
merge( Listl, List2, List3) :- Explanation of details that are obvious from the program code itself is only a
Listl = [ ], !, List3 = List2; % First list empty needless burden to the program.
List2 = ( ], !, List3 = Listl; % Second list empty Long passages of comments should precede the code they refer to, while short
Listl = (X I Restl ], comments should be interspersed with the code itself. Information that should, in
List2 = (Y I Rest2], general, be included in comments comprises the following:
( X <Y, !,
Z= X, % Z is head of List3 • What the program does, how it is used (for example, what goal is to be invoked
merge( Restl, List2, Rest3); and what are the expected results), examples of using the program.
Z= Y,
• What are top-level predicates?
merge( Listl, Rest2, Rest3) ),
List3 = [Z I Rest3]. • How are main concepts (objects) represented?
Here is a better version which avoids semicolons: • Execution time and memory requirements of the program.
• What are the program's limitations?
merge( [ ], List, List)
!. % Prevent redundant solutions • Are there any special system-dependent features used?
merge( List, [ ], List). • What is the meaning of the predicates in the program? What are their
merge( [X I Restl], [Y I Rest2], [X I Rest3]) arguments? Which arguments are 'input' and which are 'output', if known?
X <Y, !, (Input arguments have fully specified values, without uninstantiated variables,
merge( Rest 1, [YI Rest2], Rest3). when the predicate is called.)
merge( Listl, [Y I Rest2], (Y I Rest3] ) • Algorithmic and implementation details.
merge( Listl, Rest2, Rest3). • The following conventions are often used when describing predicates. Refer­
ences to a predicate are made by stating the predicate's name and its arity,
written as:
8.3.2 Tabular organization of long procedures
PredicateName / Arity
Long procedures are acceptable if they have some uniform stmcture. Typically, such For example, merge( Listl, List2, List3) would be referred to as merge/3. The
a form is a set of facts when a relation is effectively defined in the tabular form. input/output modes of the arguments are indicated by prefixing arguments'
Advantages of such an organization of a long procedure are: names by'+' (input) or'-' (output). For example, merge( +Listl, +List2, -List3)
• Its structure is easily understood. indicates that the first two arguments of merge are input, and the third one is
• lncrementability: it can be refined by simply adding new facts.
output.

• It is easy to check and correct or modify (by simply replacing some fact
independently of other facts).
8.4 �.e.�.�9.g.i.�9............................................. .................. ················································
8.3.3 Commenting When a program does not do what it is expected to do the main problem is to locate
the error(s). It is easier to locate an error in a part of the program (or a module) than
Program comments should explain in the first place what the program is about in the program as a whole. Therefore, a good principle of debugging is to start by
and how to use it, and only then the details of the solution method used and testing smaller units of the program, and when these can be trusted, to test bigger
other programming details. The main purpose of comments is to enable the user to modules or the whole program.
use the program, to understand it and to possibly modify it. Comments should Debugging in Prolog is facilitated by two things: first, Prolog is an interactive
describe, in the shortest form possible, everything that is essential to these ends. language so any part of the program can be directly invoked by a proper question to
180 Programming Style and Technique Improving efficiency 181

the Prolog system; second, Prolog implementations usually provide special debug­
ging aids. As a result of these two features, debugging of Prolog programs can, in
8.5 Improving efficiency
··········· ···········································-······················· ··································· · · ·················· · ····
general, be done more efficiently than in most other programming languages.
There are several aspects of efficiency, including the most common ones, execution
The basis for debugging aids is tracing. 'Tracing a goal' means that the informa­
time and space requirements of a program. Another aspect is the time needed by the
tion regarding the goal's satisfaction is displayed during execution. This information
programmer to develop the program.
includes:
The traditional computer architecture is not particularly suitable for the Prolog
• Entry information: the predicate name and the values of arguments when the style of program execution - that is, satisfying a list of goals. Therefore, the
goal is invoked. limitations of time and space may be experienced earlier in Prolog than in many
• Exit information: in the case of success, the values of arguments that satisfy the
other programming languages. Whether this will cause difficulties in a practical
application depends on the problem. The issue of time efficiency is practically
goal; otherwise an indication of failure. meaningless if a Prolog program that is run a few times per clay takes 1 second of
• Re-entry information: invocation of the same goal caused by backtracking. CPU time and a corresponding program in some other language, say Fortran, takes
0.1 seconds. The difference in efficiency will perhaps matter if the two programs take
Between entry and exit, the trace information for all the subgoals of this goal can be 50 minutes and 5 minutes respectively.
obtained. So we can trace the execution of our question all the way down to the On the other hand, in many areas of application Prolog will greatly reduce the
lowest level goals until facts are encountered. Such detailed tracing may turn out to program development time. Prolog programs will, in general, be easier to write, to
be impractical due to the excessive amount of tracing information; therefore, the understand and to debug than in traditional languages. Problems that gravitate
user can specify selective tracing. There are two selection mechanisms: first, suppress toward the 'Prolog domain' involve symbolic, non-numeric processing, structured
tracing information beyond a certain level; second, trace only some specified subset data objects and relations between them. In particular, Prolog has been successfully
of predicates, and not all of them. applied in areas such as symbolic solving of equations, planning, databases, general
Such debugging aids are activated by system-dependent built-in predicates. A problem solving, prototyping, implementation of programming languages, discrete
typical subset of such predicates is as follows: and qualitative simulation, architectural design, machine learning, natural language
trace
understanding, expert systems, and other areas of artificial intelligence. On the
other hand, numerical mathematics is an area for which Prolog is not a natural
triggers exhaustive tracing of goals that follow. candidate.
With respect to the execution efficiency, executing a compiled program is
notrace generally more efficient than interpreting the program. Therefore, if the Prolog
system contains both an interpreter and a compiler, then the compiler should be
stops further tracing.
used if efficiency is critical.
spy( P) If a program suffers from inefficiency then it can often be radically improved by
improving the algorithm itself. However, to do this, the procedural aspects of the
specifies that a predicate P be traced. This is used when we are particularly interested program have to be studied. A simple way of improving the executional efficiency is
in the named predicate and want to avoid tracing information from other goals to find a better ordering of clauses of procedures, and of goals in the bodies of
(either above or below the level of a call of P). Several predicates can be simul­ procedures. Another relatively simple method is to provide guidance to the Prolog
taneously active for 'spying'. system by means of cuts.
Ideas for improving the efficiency of a program usually come from a deeper
nospy( P)
understanding of the problem. A more efficient algorithm can, in general, result
stops 'spying' P. from improvements of two kinds:
Tracing beyond a certain depth can be suppressed by special commands during • Improving search efficiency by avoiding unnecessary backtracking and stopping
execution. There may be several other debugging commands available, such as the execution of useless alternatives as soon as possible.
returning to a previous point of execution. After such a return we can, for example, • Using more suitable data structures to represent objects in the program, so that
repeat the execution at a greater detail of tracing. operations on objects can be implemented more efficiently.
 '�,;_,_,�'o\4dfuiui%/4>S· ------------

Improving efficiency 183

182 Programming Style and Technique

ngb( austria, [czech_republic, gem1any, hungary, italy, liechtenstein,

We will study both kinds of improvements by looking at examples. Yet another
slovakia, slovenia, switzerland) ).
technique of improving efficiency will be illustrated by an example. This technique,
called caching, is based on asserting into the database intermediate results that are
likely to be needed again in the future computation. Instead of repeating the Let a solution be represent ed as a list of pairs of the form
computation, such results are simply retrieved as already known facts.
Country/Colour
which specifies a colour for each country in a given map. For the given map, the
8.5.1 Improving the efficiency of an eight queens program names of countries are fixed in advance, and the problem is to find the values for
the colours. Thus, for Europe, the problem is to find a proper instantiation of
As a simple example of improving the search efficiency let us revisit the eight queens variables Cl, C2, C3, etc. in the list:
problem (see Figure 4. 7). In this program, the Y-coordinates of the queens are found
by successively trying, for each queen, the integers between 1 and 8. This was [ albania/Cl, andorra/C2, austria/C3, ... )
programmed as the goal: Now let us detine the predicate
member( Y, [l,2,3,4,5,6,7,8])
colours( Country _colour_list)
The way that member works is that Y = I is tried first, and then Y = 2, Y = 3, etc. As
which is true if the Country_colour_list satisfies the map colouring constraint with
the queens are placed one after another in adjacent columns on the board, it is
respect to a given ngb relation. Let the four colours be yellow, blue, red and green.
obvious that this order of trials is not the most appropriate. The reason for this
The condition that no two neighbouring countries are of the same colour can be
is that the queens in adjacent columns will attack each other if they are not placed
formulated in Prolog as follows:
at least two squares apart in the vertical direction. According to this observation, a
simple attempt to improve the efficiency is to rearrange the candidate coordinate colours( [ )).
values. For example: colours( [Country/Colour I Rest))
member( Y, [l,5,2,6,3,7,4,8)) colours( Rest),
member( Colour, [yellow, blue, red, green] ),
This minor change will reduce the time needed to find the first solution by a factor not( member( Countryl/Colour, Rest), neighbour( Country, Country!) ).
of 3 or 4. neighbour( Country, Country!) :-
In the next example, a similarly simple idea of reordering will convert a ngb( Country, Neighbours),
practically unacceptable time complexity into a trivial one. member( Country 1, Neighbours).
Here, member( X,I.) is, as usual, the list membership relation. This will work well for
simple maps, with a small number of countries. Europe might be problematic,
8.5.2 Improving the efficiency in a map colouring program
however. Assuming that the built-in predicate setof is available, one attemp t to
colour Europe could be as follows. First, let us define an auxiliary relation:
The map colouring problem is to assign each country in a given map one of
four given colours in such a way that no two neighbouring countries are painted country( C) :- ngb( C, _ ).
with the same colour. There is a theorem which guarantees that this is always
possible. Then the question for colouring Europe can be formulated as:
Let us assume that a map is specified by the neighbour relation ?- setof( Cntry/Colour, country( Cntry), CountryColourList),
ngb( Country, Neighbours) colours( CountryColourList).
for Europe in which
where Neighbours is the list of countries bordering on Country. So the map of Europe, The setof goal will construct a template country/colour list
variable s stand for colours. Then the colours goal is supposed
with 30 countries, would be specified (in alphabetical order) as: uninstantiated
probabl y fail because of
ngb( albania, [greece, macedonia, yugoslavia] ). to instantiate the colours. However, this attempt will
ngb( andorra, [france, spain] ). inefficiency.
 Improving efficiency 185
184 Programming Style and Technique

A detailed study of the way Prolog tries to satisfy the colours goal reveals the 8.5.3 Improving efficiency of list concatenation by difference lists
source of inefficiency. Countries in the country/colour list are arranged in alphabet­
ical order, and this has nothing to do with their geographical arrangement. The In our programs so far, the concatenation of lists has been programmed as:
order in which the countries are assigned colours corresponds to the order in the list cone([ ], L, L).
(starting at the end), which is in our case independent of the ngb relation. So the
cone( [X I LI], L2, [X I L3] )
colouring process starts at some end of the map, continues at some other end, etc.,
cone( L 1, L2, L3).
moving around more or less randomly. This may easily lead to a situation in which a
country that is to be coloured is surrounded by many other countries, already This is inefficient when the first list is long. The following example explains why:
painted with all four available colours. Then backtracking is necessary, which leads ?- cone( [a,b,c], [cl,e], L).
to inefficiency.
This produces the following sequence of goals:
It is clear, then, that the efficiency depends on the order in which the countries
are coloured. Intuition suggests a simple colouring strategy that should be better cone([a,b,c], [d,e], L)
than random: start with some country that has many neighbours, and then proceed cone([b,c], [d,e], L') where L = [a I L']
cone([cl, [d,ej, L") where L' = [b I L"]
to the neighbours, then to the neighbours of neighbours, etc. For Europe, then,
cone( [ ], [d,e], L"') where L'' = [c I L'")
Germany (having most neighbours) is a good candidate to start with. Of course, where L"' = [d,e]
true
when the template country/colour list is constructed, Germany has to be put at the
until the
end of the list and other countries have to be added at the front of the list. In this From this it is clear that the program in effect scans all of the first list,
way the colouring algorithm, which starts at the rear end, will commence with empty list is encountered.
append
Germany and proceed from there from neighbour to neighbour. But could we not simply skip the whole of the first list in a single step and
we need
Such a country/colour template dramatically improves the efficiency with respect the second list, instead of gradually working down the first list? To do this,
of lists.
to the original, alphabetical order, and possible colourings for the map of Europe to know where the end of a list is; that is, we need another representation
called difference lists. So a list is represented by a
will be now prodttced without difficulty. One solution is the data structure
We can construct a properly ordered list of countries manually, but we do not pair of lists. For example, the list
have to. The following procedure, makelist, does it. It starts the construction with [a,b,c]
some specified country (Germany in our case) and collects the countries into a list
can be represented by the two lists:
called Closed. Each country is first put into another list, called Open, before it is
transferred to Closed. Each time that a country is transferred from Open to Closed, its LI = [a,b,c,d,e]
neighbours are added to Open. 1.2 = [c!,el
s the
Such a pair of lists, which we will for brevity choose to write as Ll-L2, represent
course only works under the condition that
makelist( List) :- 'difference' between Ll and L2. This of
collect([gemiany], [ ], List). that the same list can be represent ed by several 'differenc e
L2 is a suffix of Ll. Note
pairs'. So the list [a,b,c] can be represented, for example, by
collect([ ], Closed, Closed). % No more candidates for Closed
[a,b,c] -[)
collect([X I Open], Closed, List)
or
member( X, Closed), !, % X has already been collected?
collect( Open, Closed, List). % Discard X [a,b,c,d,e] - [d,e]
or
collect([X I Open], Closed, List)
ngb(X, Ngbs), % Find X's neighbours [a,b,c,d,e IT] - [d,e IT]
cone( Ngbs, Open, Openl), % Put them to Open l
collect( Open 1, [X I Closed], List). % Collect the Rest or
[a,b,c IT] -T
The cone relation is, as usual, the list concatenation relation. where T is any list. The empty list is represented by any pair of the form L-L.
186 Programming Style and Technique Improving efficiency 187

L.,., ,. ...,H..
Al Zl A2 ZZ p( ... ) :-

LI
.s.�-•-cC••·-=t, --··
-=,.
L2
.I
... , !,
p( ... ).
% The cut ensures no backtracking
% Tail-recursive call
In the cases of such tail-recursive procedures, no information is needed upon the
LJ return from a call. Therefore such recursion can be carried out simply as iteration in
which a next cycle in the loop does not require additional memory. A Prolog system
Figure 8.1 Concatenation of lists represented by difference pairs. Ll is represented by Al-Zl, will typically notice such an opportunity of saving memory and realize tail recursion
L2 by A2-Z2, and the result L3 by Al-Z2 when Zl = AZ must be true. as iteration. This is called tail recursion optimization, or last call optimization.
When memory efficiency is critical, tail-recursive formulations of procedures
help. Often it is indeed possible to re-formulate a recursive procedure into a tail­
As the second member of the pair indicates the end of the list, the end is directly recursive one. Let us consider the predicate for computing the sum of a list of
accessible. This can be used for an efficient implementation of concatenation. The numbers:
method is illustrated in Figure 8.1. The corresponding concatenation relation
translates into Prolog as the fact: sumlist( List, Sum)

concat( Al · Zl, Zl - Z2, A 1 - Z2). Here is a simple first definition:

sum list( [], 0).
Let us use concat to concatenate the lists [a,b,c], represented by the pair [a,b,c I Tl 1-
Tl, and the list [d,e], represented by [cl,e j T2]-T2: sumlist( [ First I Rest], Sum)
sumlist( Rest, Sum0),
?- concat( [a,b,c I Tl] -Tl, [cl,e I T2] -T2, L). Sum is X + SmnO.
The concatenation is done just by matching this goal with the clause about concat, This is not tail recursive, so the summation over a very long list will require many
giving: recursive calls and therefore a lot of memory. However, we know that in a typical
Tl= [d,e I T2] procedural language such summation can be carried out as a simple iterative loop.
L = [a,b,c,d,e j T2] · T2 How can we make sumlist tail recursive and enable Prolog too to carry it out as
iteration? Unfortunately we cannot simply swap the goals in the body of the second
Due to its efficiency, this difference lists technique for list concatenation is very clause, because the is goal can only be executed after Sumo has been computed. But
popular, although it cannot be used as flexibly as our usual cone procedure. the following is a common trick that does it:
sumlist( List, Sum) :-
sum list( List, 0, Sum). '1/c, Call auxiliary predicate
8.5.4 Last call optimization and accumulators
1t, sumlist( List, PartialSum, TotalSum):
0

% TotalSum = PartialSum + sum over List

Recursive calls normally take up memory space, which is only freed after the return
from the call. A large number of nested recursive calls may lead to shortage of sumlist( [ ], Sum, Sum). % Total sum = partial sum
memory. In special cases, however, it is possible to execute nested recursive calls sumlist( [ First j Rest ], PartialSurn, TotalSurn)
without requiring extra memory. In such a case a recursive procedure has a special NewPartialSum is Partia!Surn + First,
form, called tail recursion. A tail-recursive procedure only has one recursive call, and sumlist( Rest, NewPartia!Sum, TotalSum).
this call appears as the last goal of the last clause in the procedure. In addition, the This is now tail recursive and Prolog can benefit from last call optimization.
goals preceding the recursive call must be deterministic, so that no backtracking The technique of making our sumlist procedure tail recursive as above is
occurs after this last call. We can force this determinism by placing a cut just before frequently used. To define our target predicate sumlist/2, we introduced an auxiliary
the recursive call. Typically a tail-recursive procedure looks like this: predicate sumlist/3. The additional argument, Partia!Sum, enabled a tail-recursive
p( ... ) % No recursive call in the body of this clause formulation. Such extra arguments are common and they are called accumulators.
p( ... ) % No recursive call in the body of this clause The final result is gradually accumulated in such an accumulator during successive
recursion calls.
 Improving efficiency 189
188 Programming Style and Technique

In other languages, a typical example statement that involves direct access to an

Here is another famous example of tail-recursion formulation through intro­
element of an array is:
ducing an accumulator argument:
reverse( List, ReversedList) A[60]: = 1
ReversectList has the same elements as List, but in the reverse order. The following is a This initializes the value of the 60th element of array A to 1. We can achieve
first, straightforward attempt: analogous effect in Prolog by the goal:
reverse( [ I, []). arg( 60, A, 1)
reverse( [X I Rest], Reversed)
This directly accesses the 60th component of the compound term A, which as the
reverse( Rest, RevRest),
cone( RevRest, [X], Reversed). % Append X at end result gets instantiated to:

This is not tail recursive. Apart from that, it is also very inefficient because of the A= f( _, ..., _, 1, _, ..., _) 'X, 60th component equal 1
goal cone( RevRest, [XJ, Reversed), which requires time proportional to the length of The point is that time needed to access the Nth component of a structure does not
RevRest. Therefore, to reverse a list of length 11, the procedure above will require time
depend on N. Another typical example statement from other programming
proportional to 112 . But, of course, a list can be reversed in linear time. Therefore, due languages is:
to its inefficiency, the procedure above is also known as 'naive reverse'. A much
more efficient version below introduces an accumulator: X := A[60]
reverse( List, Reversed) :- This translates into our simulated array in Prolog as:
reverse( List, [], Reversed).
arg( 60, A, X)
'1/rJ reverse( List, PartReversecl, Reversed):
% Reversed is obtained by adding the elements of List in reverse order This is much more efficient than having a list of 100 elements and accessing the
% to PartReversed
60th element by nested recursion down the list. However, the updating of the value
reverse( [], Reversed, Reversed). of an element in a simulated array is awkward. Once the values in an array have been
reverse( [X I Rest], PartReversed, Tota!Reversed) initialized, they can be changed, for example:
reverse( Rest, [X I PartReversecl], Tota!Reversed). % Adel X to accumulator
A[60] : = A[60]+ 1
This is efficient (time is linear in the length of list) and tail recursive.
A straightforward way to simulate such update of a single value in an array in
Prolog would be as follows: build a whole new structure with 100 components using
8.5.5 Simulating arrays with arg functor, insert the new value at the appropriate place in the structure, and fill all the
other components by the corresponding components of the previous structure. All
The list structure is the easiest representation for sets in Prolog. However, accessing this is awkward and very inefficient. One idea to improve this is to provide
an item in a list is done by scanning the list. This takes time proportional to the uninstantiated 'holes' in the components of the structure, so that future values of
length of the list. For long lists this is very inefficient. Tree structures, discussed in array elements can be accommodated in these holes. So we can, for example, store
Chapters 9 and 10, offer much more efficient access. However, often it is possible to successive update values in a list in which the rest of the list is an uninstantiated
access an element of a structure through the element's index. In such cases, array variable - a 'hole' for future values. As an example consider the following updates of
structures, provided in other programming languages, are the most effective because the value of variable X in a procedural language:
they enable direct access to a required element.
There is no array facility in Prolog, but arrays can be simulated to some extent by X := 1; X := 2; X := 3
using the built-in predicates arg and functor. Here is an example. The goal:
These updates can be simulated in Prolog with the 'holes' technique as follows:
functor( A, f, 100)
X= [ 1 I Restl] % Corresponds to X:= 1, Restl is hole for future values
makes a structure with 100 elements: Restl = [ 2 I Rest2] % Corresponds to X : = 2, Rest 2 is hole for future values
Rest2= [ 3 I Rest3] % Corresponds to X := 3
A= f( _, _, _, ...)
190 Programming Style and Technique Improving efficiency 191

At this point X =[ 1, 2, 3 I Rest3]. Obviously the whole history of the values of X is As an example consider a program to compute the Nth Fibonacci number for a
maintained, and the current value is the one just preceding the 'hole'. If there are given N. The Fibonacci sequence is:
many successive updates, the 'current' value gets nested deep, and the technique
becomes inefficient again. A further idea, to overcome this source of inefficiency, is 1, 1, 2, 3, 5, 8, 13, . . .
to throw away the previous values at the moment when a list gets too long, and start Each number in the sequence, except for the first two, is the sum of the previous two
again with a list consisting of just a head and an uninstantiated tail. numbers. We will define a predicate
ln spite of these potential complications, in many cases the simulation of arrays
i
f b( N, F)
with arg is simple and works well. One such example is our solution 3 for the eight
queens problem in Chapter 4 (Figure 4.11). This program places a next queen into to compute, for a given N, the Nth Fibonacci number, F. We count the numbers in
a currently free column (X-coordinate), row (Y-coordinate), upward diagonal the sequence starting with N = 1. The following fib program deals first with the first
(U-coordinate) and downward diagonal (V-coordinate). The sets of currently free two Fibonacci numbers as two special cases, and then specifies the general rule about
coordinates are maintained, and when a new queen is placed the corresponding the Fibonacci sequence:
occupied coordinates are deleted from these sets. The deletion of U and V fib( 1, 1). % 1st Fibonacci number
coordinates in Figure 4.11 involves scanning the corresponding lists, which is
fib( 2, 1). 'Yo 2nd Fibonacci number
inefficent. Efficiency can easily be improved by simulated arrays. So the set of all
15 upward diagonals can be represented by the following term with 15 components: fib( N, F) :- % Nth Fib. number. N > 2
N > 2,
Du= u( _, _, _ , _, _ , _, _, _ , _ , _, _, _, _, _, _) Nlis N - 1, fib( Nl. Fl),
N2 is N - 2, fib( N2, FZ),
Consider placing a queen at the square (X,YJ = (1,1). This square iies on the 8th Fis F 1 + FZ. '¼, Nth number is the sum of its two predecessors
upward diagonal. The fact that this diagonal is now occupied can be marked
This program tends to redo parts of the computation. This is easily seen if we trace
by instantiating the 8th component of Ou to l (that is, the corresponding
the execution of the following goal:
X-coordinate):
?- fib( 6, F).
arg( 8, Ou, 1)
Figure 8.2 illustrates the essence of this computational process. For example, the
Now Du becomes: third Fibonacci number, ((3), is needed in three places and the same computation is
repeated each time.
Du::::::: u( _, _, _, _, _ 1, _, _, _, _, _, _, _)
This can be easily avoided by remembering each newly computed Fibonacci
1 _, _,

If later a queen is attempted to be placed at (X,Y) = (3,3), also lying on the 8th number. The idea is to use the built-in procedure asserta and to add these
diagonal, this would require: (intermediate) results as facts to the database. These facts have to precede other
clauses about fib to prevent the use of the general rule in cases where the result is
arg( 8, Du, 3) % Here X = 3 already known. The modified procedure, fibZ, differs from fib only in this assertion:
This will fail because the 8th component of Du is already l. So the program will not fib2( 1, 1). % 1st Fibonacci number
allow another queen to be placed on the same diagonal. This implementation of the fib2( 2, 1). % 2nd Fibonacci number
sets of upward and downward diagonals leads to a considerably more efficient i
f b2( N, F) :- % Nth Fib. number, N > 2
program than the one in Figure 4.11. N > 2,
Nlis N - 1, fib2( Nl, Fl),
N2is N - 2, fib2( NZ, F2),
8.5.6 Improving efficiency by asserting derived facts Fis Fl + F2,
asserta( fib2( N, F) ). % Remember Nth number
Sometimes during computation the same goal has to be satisfied again and again. As This program will try to answer any fib2 goal by first looking at stored facts about
Prolog has no special mechanism to discover such situations whole computation this relation, and only then resort to the general rule. As a result, when a goal
sequences are repeated. fib2( N, F) is executed all Fibonacci numbers, up to the Nth number, will get
 Improving efficiency 193
192 Programming Style and Technique

[{6)

I
[(6)

+
I +
/ ----
1/5�-[(.J)
l
f/4)

I
l/5!

I +
I
+ + J, retrievecl

/� /� f/21 !).JI
/ �
f/31

I
f/3)

I I
f/3)

I
[(./)

+
I +
I + + 2, retrieved

/� /� [/1) [{2)
/� IW
/�
1/2)

I I
[/31 1(2) [(3)

I
/12)

+
I I I I I +
/�I ( I)
/�
f/2) f/2) I)/)

I I I I
Figure 8.2 Computation of the 6th Fibonacci number by procedure fib. Figure 8.3 Computation of the 6th Fibonacci number by procedure fib2, which remembers
previous results. This saves some computation in comparison with fib, see
Figure 8.2.
tabulated. Figure 8.3 illustrates the computation of the 6th Fibonacci number by
fib2. A comparison with Figure 8.2 shows the saving in the computational complex­
ity. For greater N, the savings would be much more substantial.
Asserting intermediate results, also callee! caching, is a stanclarcl technique for

... Q
avoiding repeated computations. It should be noted, however, that in the case of
Fibonacci numbers we can preferably avoid repeated computation by using another

0
algorithm, rather than by asserting intermediate results. This other algorithm will
lead to a program that is more difficult to unclerstancl, but more efficient to execute.
The idea this time is not to define the Nth Fibonacci number simply as the sum of its

-­
two predecessors and leave the recursive calls to unfold the whole computation
'clownwarcls' to the two initial Fibonacci numbers. Instead, we can work 'upwards',
starting with the initial two numbers, and compute the numbers in the sequence one
Starting Transition from Final
by one in the forward direction. We have to stop when we have computed the Nth configuration M configuration.
configuration.
number. Most of the work in such a program is done by the procedure: here \1 = 2 toM + I here M = N
forwardfib( M, N, Fl, F2, F) is
Figure 8.4 Relations in the Fibonacci sequence. A 'configuration', depicted by a large circle,
Here, Fl and F2 are the (M - l)st and Mth Fibonacci numbers, and F is the Nth defined by three things: an index M and two consecutive Fibonacci numbers
Fibonacci number. Figure 8.4 helps to understand the forwardfib relation. According f(M - 1) and f(M).
 ,i£.f::5,g ••aJlt:m!'-�r�flits.tm"5Bl't�t-�'.�}&\'lt�t!:�}:::·�(t,'

194 Programming Style and Technique Summary 195

to this figure, forwardfib finds a sequence of transformations to reach a final 8J Define the relation
configuration (when M = N) from a given starting configuration. When forwardfib reverse( List, ReversedList)
is invoked, all the arguments except F have to be instantiated, and M has to be less
than or equal to N. The program is: where both lists are represented by difference pairs.

fib3(N, F) :- 8.4 Rewrite the collect procedure of Section 8.5.2 using difference pair representation for
forwardfib( 2, N, 1, 1, F). % The first two Fib. numbers are 1 lists so that the concatenation can be clone more efficiently.
forwardfib( M, N, Fl, F2, F2) 8.5 The following procedure computes the maximum value in a list of numbers:
M>=N. % Nth Fibonacci number reached
max( [X], X).
forwardfib(M, N, Fl, F2, F)
M<N, % Nth number not yet reached max( [XI Rest], \fox)
NextM is M + 1, max( Rest, MaxRest),
NextF2 is Fl + F2, ( Max Rest>= X, !, Max= Max Rest
forwardfib(NextM, N, F2, NextF2, F).
Max�, X ).
Notice that forwarclfib is tail recursive, and M, Fl and F2 are accumulator arguments.
Transform this into a tail-recursive procedure. Hint: Introduce accumulator argu­
ment MaxSoFar.
Exercises 8.6 Rewrite program 3 for eight queens (Figure 4.11) using simulated array with arg to
represent the sets of free diagonals, as discussed in Sectlon 8.5.S. Measure the
8.1 Procedures subl, sub2 and sub3, shown below, all implement the sublist relation. improvement in efficiency.
subl is a more procedural definition whereas sub2 and sub3 are written in a more
declarative style. Study the behaviour, with reference to efficiency, of these three 8.7 Implement the updating of the value of an element of an array simulated by functor
and arg, using 'holes' for future values along the lines discussed in Section 5.5.S.
procedures on some sample lists. Two of them behave nearly equivalently and have
similar efficiency. Which two? Why is the remaining one less efficient?
subl( List, Sublist) :­
prefix( List, Sublist). Summary · ··· ·
· · · · · · · · · · ····· · · · · · · ···· · ·· · ···· ···· · · ·············· ·· ··········· · ··· · · ··· ··· · ·· · ·· · · · · ·· · · · · · · · · · · · · · · ·· · •""" " ' " " """""""" ' " " " " ' ' ' ' "
subl( [_I Tail], Sublist) • There are several criteria for evaluating programs:
subl( Tail, Sublist). % Sublist is sublist of Tail
correctness
prefix(_ , [] ).
user-friendliness
prefix( [XI Listl], [XI List2]) efficiency
prefix(Listl, List2).
readability
sub2( List, Sublist) :- modifiability
cone( Listl, List2, List), robustness
cone( List3, Sublist, Listl). documentation
sub3( List, Sublist) :- program
• The principle of stepwise refinement is a good way of organizing the
cone( Listl, List2, List), to relations, algorithm s and
cone(Sublist,_, List2). development process. Stepwise refinement applies
data structures.