Techniques of
PROLOG PROGRAMMING
with implementation of
logical negation and quantified goals
T . V a n Le, Ph.D.
University of Canberra
ULB Darmstadt
M v 16170852 . t c.
New Yc... oronto * Singapore
Contents
Preface vii
Chapter 1 Introduction to Prolog
1.1 What is Prolog? 1
1.2 Prolog versus conventional programming 2
1.3 Prolog programs 3
1.4 Queries 7
1.5 Working with Prolog 8
1.6 Predefined functions and predicates 11
1.7 Summary 13
Solved problems 14
Supplementary problems 17
Chapter 2 Declarative Prolog programming
2.1 Writing a declarative Prolog program 20
2.2 Recursive programming 23
2.3 List processing 30
2.4 List sorting 38
2.5 Data structures 41
2.6 Databases 44
2.6.1 Database as a set of records 45
2.6.2 Database as a set of attributes 46
2.6.3 Database as a collection of record lists 47
2.6.4 Database as a collection of sorted binary trees 48
2.7 Fundamental techniques of declarative Prolog programming 50
Solved problems / 52
Supplementary problems 68
Chapter 3 Procedural Prolog programming
3.1 Procedural reading of Prolog programs 73
3.2 Writing a procedural Prolog program 76
3.3 Program execution: unification and resolution 80
Xlll
XIV CONTENTS
3.4 Parameter passing 85
3.5 Order of goals and clauses 88
3.6 Backtracking 90
3.7 Efficient list sorting 92
3.8 Fundamental techniques of procedural Prolog programming 95
Solved problems 96
Supplementary problems 104
Chapter 4 Control and side-effect features
of Prolog
4.1 Control of program execution 107
4.2 Prevention of backtracking: the cut predicate 108
4.2.1 Correct use of cut 110
4.2.2 Incorrect use of cut 112
4.2.3 The once predicate 115
4.3 Forcing of backtracking: the fail predicate 119
4.4 Negation-as-failure: the not predicate 122
4.4.1 Correct use of not 124
4.4.2 Incorrect use of not 125
4.5 Repetition: the repeat predicate 126
4.6 Input-output predicates 128
4.7 Environment-manipulating predicates 132
4.7.1 File-handling predicates 132
4.7.2 Database-manipulating predicates 134
4.7.3 System predicates 136
Solved problems 141
Supplementary problems 153
Chapter 5 Development of Prolog programs
5.1 Program development 155
5.2 Program style 157
5.3 Programming techniques 166
5.3.1 Generate-and-test 166
5.3.2 Divide-and-conquer 169
5.4 User interaction 172
5.4.1 Menu-driven interaction 172
CONTENTS XV
5.4.2 User-system dialogue 174
5.5 Program validation 177
5.5.1 Proof of a program's correctness 178
5.5.2 Test of a program's correctness 180
Solved problems 184
Supplementary problems 194
Chapter 6 Advanced programming techniques
and data structures
6.1 Nondeterministic programming 196
6.1.1 Nondeterministic thinking 197
6.1.2 Nondeterministic finite automata 198
6.2 Second-order programming 203
6.2.1 Collection of data: the set-predicates 203
6.2.2 Conversion of data: the = . . predicate 209
6.2.3 Inspection of data: the functor and arg predicates 212
6.2.4 Classification of data: type-predicates 213
6.2.5 Definition of new functors: the op predicate 214
6.3 Representation of queues, frames, and arrays 219
6.3.1 Queues 219
6.3.2 Frames 223
6.3.3 Arrays 225
6.4 Advanced tree structures 230
6.4.1 AVL-trees 230
6.4.2 B-trees 239
6.5 An example of program validation 248
Solved problems 258
Supplementary problems 269
Chapter 7 Search techniques
7.1 Search: a problem-solving technique 272
7.1.1 Representation of states 273
7.1.2 Change of states 274
7.2 Search strategies 274
7.3 Depth-first search 281
7.4 Breadth-first search 285
XVI CONTENTS
7.5 Wave search 289
7.6 Inter-wave search 291
7.7 Hill-climbing search 294
7.8 Best-first search 296
7.9 Best-cost search' 298
7.10 Best-path search 300
7.11 Performance of a search procedure 303
7.11.1 The search space 303
7.11.2 The branching factor 304
Solved problems 307
Supplementary problems 336
Chapter 8 Meta-programming in Prolog
8.1 Meta-programs 341
8.2 Meta-programming techniques 343
8.2.1 Inspection of formulas 345
8.2.2 Modification of formulas 350
8.2.3 Generation of new formulas 351
8.2.4 Execution of goals 352
8.3 The problem of the meta-predicate not 355
8.4 LnProlog's negation evaluator 357
8.5 LnProlog's meta-preprocessor 362
8.6 Representation of quantified goals in LnProlog 368
8.7 Simulation of a Prolog interpreter for debugging 371
8.8 A Prolog debugger 381
Solved problems 387
Supplementary problems 395
Chapter 9 Building expert systems in Prolog
/
9.1 What is an expert system? 397
9.2 Components of an expert system 398
9.3 Building an expert system 400
9.4 Representation of uncertainty 404
9.5 Generation of explanations 407
9.6 A meta-interpreter for expert systems 417
9.7 Expert system shells 422
CONTENTS xvn
9.8 ESSLN: An expert system shell with logical negation 423
9.9 Quantified goals in ESSLN 425
9.10 ESSLN's user interface 427
9 # 1 Subtypes in ESSLN 457
Solved problems 462
Supplementary problems 474
Chapter 10 Natural language processing
in Prolog
10.1 Natural language processing 476
10.2 Context-free grammars 477
10.3 Definite clause grammars 480
10.4 Logical representation of sentences 484
10.5 Interpretation of logical formulas 488
10.6 A database query-answering system 493
Solved problems 499
Supplementary problems 510
Chapter 11 System simulation in Prolog
11.1 What is simulation? 512
11.2 Object-oriented simulation models 513
11.3 Prolog simulation models 515
11.4 Realisation of nondeterminism 519
11.5 Multiobject requirement 525
11.6 Implementation of rendez-vous 530
11.7 POSS: A Prolog-based object-oriented simulation system 534
11.8 Simulation programming with POSS 539
Solved problems 543
Supplementary problems / 557
Appendices
A Theory of unification and resolution 561
A.I Unification 561
A.2 SLD-resolution 563
B Pure-Prolog interpreter 567
XVlll CONTENTS
C Prolog predefined functions and predicates 569
D The ASCII character set 576
E Prolog operators precedence . 577
'-' F List of defined procedures 578
G The diskettes 582
Bibliography 585
Index 594
