Prolog Programming in Depth

Description

This book covers the Prolog programming language thoroughly with an emphasis on building practical application software, not just theory. Working through this book, readers build several types of expert systems, as well as natural language processing software and utilities to read foreign file formats. This is the first book to cover ISO Standard Prolog, but the programs are compatible with earlier dialects of the language. Program files are available by FTP from The University of Georgia. Cover Title Page Table of Contents Preface Part I The Programming Language 1 Introducing Prolog 1.1 The Idea of Prolog 1.2 How Prolog Works 1.3 Varieties of Prolog 1.4 A Practical Knowledge Base 1.5 Unification and Variable Instantiation 1.6 Backtracking 1.7 Prolog Syntax 1.8 Defining Relations 1.9 Conjoined Goals (“And”) 1.10 Disjoint Goals (“Or”) 1.11 Negative Goals (“Not”) 1.12 Testing for Equality 1.13 Anonymous Variables 1.14 Avoiding Endless Computations 1.15 Using the Debugger to Trace Execution 1.16 Styles of Encoding Knowledge 1.17 Bibliographical Notes 2 Constructing Prolog Programs 2.1 Declarative and Procedural Semantics 2.2 Output: write, nl, display 2.3 Computing versus Printing 2.4 Forcing Backtracking with fail 2.5 Predicates as Subroutines 2.6 Input of Terms: read 2.7 Manipulating the Knowledge Base 2.8 Static and Dynamic Predicates 2.9 More about consult and reconsult 2.10 File Handling: see, seen, tell, told 2.11 A Program that “Learns” 2.12 Character Input and Output: get, get0, put 2.13 Constructing Menus 2.14 A Simple Expert System 3 Data Structures and Computation 3.1 Arithmetic 3.2 Constructing Expressions 3.3 Practical Calculations 3.4 Testing for Instantiation 3.5 Lists 3.6 Storing Data in Lists 3.7 Recursion 3.8 Counting List Elements 3.9 Concatenating (Appending) Lists 3.10 Reversing a List Recursively 3.11 A Faster Way to Reverse Lists 3.12 Character Strings 3.13 Inputting a Line as a String or Atom 3.14 Structures 3.15 The “Occurs Check” 3.16 Constructing Goals at Runtime 3.17 Data Storage Strategies 3.18 Bibliographical Notes 4 Expressing Procedural Algorithms 4.1 Procedural Prolog 4.2 Conditional Execution 4.3 The “Cut” Operator (!) 4.4 Red Cuts and Green Cuts 4.5 Where Not to Put Cuts 4.6 Making a Goal Deterministic Without Cuts 4.7 The “If–Then–Else” Structure (->) 4.8 Making a Goal Always Succeed or Always Fail 4.9 Repetition Through Backtracking 4.10 Recursion 4.11 More About Recursive Loops 4.12 Organizing Recursive Code 4.13 Why Tail Recursion is Special 4.14 Indexing 4.15 Modularity, Name Conflicts, and Stubs 4.16 How to Document Prolog Predicates 4.17 Supplement: Some Hand Computations 4.17.1 Recursion 4.17.2 Saving backtrack points 4.17.3 Backtracking 4.17.4 Cuts 4.17.5 An unexpected loop 4.18 Bibliographical Notes 5 Reading Data in Foreign Formats 5.1 The Problem of Free–Form Input 5.2 Converting Strings to Atoms and Numbers 5.3 Combining Our Code with Yours 5.4 Validating User Input 5.5 Constructing Menus 5.6 Reading Files with get byte 5.7 File Handles (Stream Identifiers) 5.8 Fixed–Length Fields 5.9 Now What Do You Do With the Data? 5.10 Comma–Delimited Fields 5.11 Binary Numbers 5.12 Grand Finale: Reading a Lotus Spreadsheet 5.13 Language and Metalanguage 5.14 Collecting Alternative Solutions into a List 5.15 Using bagof and setof 5.16 Finding the Smallest, Largest, or “Best” Solution 5.17 Intensional and Extensional Queries 5.18 Operator Definitions 5.19 Giving Meaning to Operators 5.20 Prolog in Prolog 5.21 Extending the Inference Engine 5.22 Personalizing the User Interface 5.23 Bibliographical Notes 7 Advanced Techniques 7.1 Structures as Trees 7.2 Lists as Structures 7.3 How to Search or Process Any Structure 7.4 Internal Representation of Data 7.5 Simulating Arrays in Prolog 7.6 Difference Lists 7.7 Quicksort 7.8 Efficiency of Sorting Algorithms 7.9 Mergesort 7.10 Binary Trees 7.11 Treesort 7.12 Customized Arithmetic: A Replacement for is 7.13 Solving Equations Numerically 7.14 Bibliographical Notes II Artificial Intelligence Applications 8 Artificial Intelligence and the Search for Solutions 8.1 Artificial Intelligence, Puzzles, and Prolog 8.2 Through the Maze 8.2.1 Listing of MAZE.PL 8.2.2 Listing of MAZE1.PL (connectivity table) 8.3 Missionaries and Cannibals 8.3.1 Listing of CANNIBAL.PL 8.4 The Triangle Puzzle 8.4.1 Listing of TRIANGLE.PL 8.5 Coloring a Map 8.5.1 Listing of MAP.PL 8.5.2 Listing of SAMERICA.PL (data for MAP.PL) 8.6 Examining Molecules 8.6.1 Listing of CHEM.PL 8.7 Exhaustive Search, Intelligent Search, and Heuristics 8.7.1 Listing of FLIGHT.PL 8.8 Scheduling 8.8.1 Listing of SCHEDULE.PL 8.9 Forward Chaining and Production Rule Systems 8.10 A Simple Forward Chainer 8.11 Production Rules in Prolog 8.11.1 Listing of FCHAIN.PL 8.11.2 Listing of CARTONS.PL 8.12 Bibliographical notes 9 A Simple Expert System Shell 9.1 Expert systems 9.2 Expert consultants and expert consulting systems 9.3 Parts of an expert consulting system 9.4 Expert system shells 9.5 Extending the power of Prolog 9.5.1 Listing of XSHELL.PL 9.6 XSHELL: the main program 9.7 Asking about properties in XSHELL 9.8 Asking about parameters in XSHELL 9.9 XSHELL’s explanatatory facility 9.10 CICHLID: a sample XSHELL knowledge base 9.10.1 Listing of CICHLID.PL 9.11 A consultation with CICHLID 9.12 PAINT: a sample XSHELL knowledge base 9.12.1 Listing of PAINT.PL 9.13 Developing XSHELL knowledge bases 9.14 Bibliographical notes 10 An Expert System Shell With Uncertainty 10.1 Uncertainty, probability, and confidence 10.2 Representing and computing confidence or certainty 10.3 Confidence rules 10.4 The CONMAN inference engine 10.5 Getting information from the user 10.6 The CONMAN explanatory facilities 10.7 The main program 10.7.1 Listing of CONMAN.PL 10.8 CONMAN knowledge bases 10.8.1 Listing of MDC.PL 10.8.2 Listing of PET.PL 10.9 No confidence in ‘confidence’ 10.10 Bibliographical notes 11 Defeasible Prolog 11.1 Nonmonotonic reasoning and Prolog 11.2 New syntax for defeasible reasoning 11.3 Strict rules 11.4 Incompatible conclusions 11.5 Superiority of rules 11.6 Specificity 11.6.1 Listing of DPROLOG.PL 11.7 Defining strict derivability in Prolog 11.8 d-Prolog: preliminaries 11.9 Using defeasible rules 11.10 Preemption of defeaters 11.10.1Listing of DPUTILS.PL 11.11 Defeasible queries and exhaustive responses 11.12 Listing defeasible predicates 11.13 Consulting and reconsulting d-Prolog files 11.14 The d-Prolog Dictionary 11.15 Rescinding predicates and knowledge bases 11.16 Finding contradictions 11.17 A special explanatory facility 11.18 A suite of examples 11.18.1Listing of KBASES.DPL 11.19 Some feathered and non-feathered friends 11.20 Inheritance reasoning 11.21 Temporal persistence 11.22 The Election Example 11.23 d-Prolog and the Closed World Assumption 11.24 BIBLIOGRAPHICAL NOTES 12 Natural Language Processing 12.1 Prolog and Human Languages 12.2 Levels of Linguistic Analysis 12.3 Tokenization 12.4 Template Systems 12.5 Generative Grammars 12.6 A Simple Parser 12.7 Grammar Rule (DCG) Notation 12.8 Grammatical Features 12.9 Morphology 12.10 Constructing the Parse Tree 12.11 Unbounded Movements 12.12 Semantic Interpretation 12.13 Constructing Representations 12.14 Dummy Entities 12.15 Bibliographical Notes A Summary of ISO Prolog A.1 Syntax of Terms A.1.1 Comments and Whitespace A.1.2 Variables A.1.3 Atoms (Constants) A.1.4 Numbers A.1.5 Character Strings A.1.6 Structures A.1.7 Operators A.1.8 Commas A.1.9 Parentheses A.2 Program Structure A.2.1 Programs A.2.2 Directives A.3 Control Structures A.3.1 Conjunction, disjunction, fail, and true A.3.2 Cuts A.3.3 If–then–else A.3.4 Variable goals, call A.3.5 repeat A.3.6 once A.3.7 Negation A.4 Error Handling A.4.1 catch and throw A.4.2 Errors detected by the system A.5 Flags A.6 Arithmetic A.6.1 Where expressions are evaluated A.6.2 Functors allowed in expressions A.7 Input and Output A.7.1 Overview A.7.2 Opening a stream A.7.3 Closing a stream A.7.4 Stream properties A.7.5 Reading and writing characters A.7.6 Reading terms A.7.7 Writing terms A.7.8 Other input–output predicates A.8 Other Built–In Predicates A.8.1 Unification A.8.2 Comparison A.8.3 Type tests A.8.4 Creating and decomposing terms A.8.5 Manipulating the knowledge base A.8.6 Finding all solutions to a query A.8.7 Terminating execution A.9 Modules A.9.1 Preventing name conflicts A.9.2 Example of a module A.9.3 Module syntax A.9.4 Metapredicates A.9.5 Explicit module qualifiers A.9.6 Additional built–in predicates A.9.7 A word of caution B Some Differences Between Prolog Implementations B.1 Introduction B.2 Which Predicates are Built–In? B.2.1 Failure as the symptom B.2.2 Minimum set of built–in predicates B.2.3 The Quintus library B.3 Variation In Behavior of Built–In Predicates B.3.1 abolish and retractall B.3.2 name: numeric arguments B.3.3 functor: numeric arguments B.3.4 op, operators, and current op B.3.5 findall, setof, and bagof B.3.6 listing B.4 Control Constructs B.4.1 Negation B.4.2 Scope of cuts B.4.3 If–then–else B.4.4 Tail recursion and backtrack points B.4.5 Alternatives created by asserting B.5 Syntax and Program Layout B.5.1 Syntax selection B.5.2 Comments B.5.3 Whitespace B.5.4 Backslashes B.5.5 Directives B.5.6 consult and reconsult B.5.7 Embedded queries B.6 Arithmetic B.6.1 Evaluable functors B.6.2 Where expressions are evaluated B.6.3 Expressions created at runtime in Quintus Prolog B.7 Input and Output B.7.1 Keyboard buffering B.7.2 Flushing output B.7.3 get and get0 B.7.4 File handling B.7.5 Formatted output B.8 Definite Clause Grammars B.8.1 Terminal nodes B.8.2 Commas on the left B.8.3 phrase