Transcription
Prolog Programming in Depth(AUTHORS’ MANUSCRIPT)Michael A. CovingtonDonald NuteAndré VellinoArtificial Intelligence ProgramsThe University of GeorgiaAthens, Georgia 30602–7415 U.S.A.September 1995Authors’ manuscript693 ppid September 9, 1995Prolog Programming in Depth
ContentsI The Prolog Language1Introducing Prolog1.1The Idea of Prolog : : : : : : : : : : : :1.2How Prolog Works : : : : : : : : : : : :1.3Varieties of Prolog : : : : : : : : : : : :1.4A Practical Knowledge Base : : : : : : :1.5Unification and Variable Instantiation :1.6Backtracking : : : : : : : : : : : : : : :1.7Prolog Syntax : : : : : : : : : : : : : : :1.8Defining Relations : : : : : : : : : : : :1.9Conjoined 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 : : : : : : : : : :9: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :1124491014161819202224252728301Authors’ manuscript693 ppid September 9, 1995Prolog Programming in Depth
2234Constructing Prolog Programs2.1Declarative and Procedural Semantics : : :2.2Output: write, nl, display : : : : : : : : :2.3Computing versus Printing : : : : : : : : :2.4Forcing Backtracking with fail : : : : : : :2.5Predicates as Subroutines : : : : : : : : : :2.6Input of Terms: read : : : : : : : : : : : : :2.7Manipulating the Knowledge Base : : : : :2.8Static and Dynamic Predicates : : : : : : :2.9More 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, put2.13 Constructing Menus : : : : : : : : : : : : :2.14 A Simple Expert System : : : : : : : : : : :Data Structures and Computation3.1Arithmetic : : : : : : : : : : : : : : :3.2Constructing Expressions : : : : : :3.3Practical Calculations : : : : : : : :3.4Testing for Instantiation : : : : : : :3.5Lists : : : : : : : : : : : : : : : : : :3.6Storing Data in Lists : : : : : : : : :3.7Recursion : : : : : : : : : : : : : : :3.8Counting List Elements : : : : : : :3.9Concatenating (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 Atom3.14 Structures : : : : : : : : : : : : : : :3.15 The “Occurs Check” : : : : : : : : :3.16 Constructing Goals at Runtime : : :3.17 Data Storage Strategies : : : : : : : :3.18 Bibliographical Notes : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : :Expressing Procedural Algorithms4.1Procedural Prolog : : : : : : : : : : : : : : : :4.2Conditional Execution : : : : : : : : : : : : : :4.3The “Cut” Operator (!) : : : : : : : : : : : : :4.4Red Cuts and Green Cuts : : : : : : : : : : : :4.5Where Not to Put Cuts : : : : : : : : : : : : : :4.6Making a Goal Deterministic Without Cuts : :4.7The “If–Then–Else” Structure (- ) : : : : : : : :4.8Making a Goal Always Succeed or Always Fail4.9Repetition Through Backtracking : : : : : : : :4.10 Recursion : : : : : : : : : : : : : : : : : : : : :Authors’ manuscript693 ppid September 9, 1995: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : 5777879818385858789919192949697989999101103Prolog Programming in Depth
34.114.124.134.144.154.164.17More About Recursive Loops : : : : : :Organizing Recursive Code : : : : : : :Why Tail Recursion is Special : : : : : :Indexing : : : : : : : : : : : : : : : : : :Modularity, Name Conflicts, and Stubs :How to Document Prolog Predicates : :Supplement: Some Hand Computations4.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 Formats5.1The Problem of Free–Form Input : : : : : : : : :5.2Converting Strings to Atoms and Numbers : : :5.3Combining Our Code with Yours : : : : : : : : :5.4Validating User Input : : : : : : : : : : : : : : :5.5Constructing Menus : : : : : : : : : : : : : : : :5.6Reading Files with get byte : : : : : : : : : : : :5.7File Handles (Stream Identifiers) : : : : : : : : :5.8Fixed–Length Fields : : : : : : : : : : : : : : : :5.9Now 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” Solution5.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 : : : : : : : : : : : : : : :77.17.27.37.47.57.67.7Authors’ manuscriptAdvanced TechniquesStructures as Trees : : : : : : : : : : : :Lists as Structures : : : : : : : : : : : :How to Search or Process Any StructureInternal Representation of Data : : : : :Simulating Arrays in Prolog : : : : : : :Difference Lists : : : : : : : : : : : : : :Quicksort : : : : : : : : : : : : : : : : :693 ppid September 9, 1995: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : 165167170172173173175176177181182183Prolog Programming in Depth
47.87.97.107.117.127.137.14Efficiency of Sorting Algorithms : : : : : : : :Mergesort : : : : : : : : : : : : : : : : : : : : :Binary Trees : : : : : : : : : : : : : : : : : : : :Treesort : : : : : : : : : : : : : : : : : : : : : :Customized Arithmetic: A Replacement for isSolving Equations Numerically : : : : : : : : :Bibliographical Notes : : : : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :II Artificial Intelligence Applications89205Artificial Intelligence and the Search for SolutionsArtificial Intelligence, Puzzles, and Prolog : : : : : :Through the Maze : : : : : : : : : : : : : : : : : : :8.2.1 Listing of MAZE.PL : : : : : : : : : : : : : : :8.2.2 Listing of MAZE1.PL (connectivity table) : : :8.3Missionaries and Cannibals : : : : : : : : : : : : : :8.3.1 Listing of CANNIBAL.PL : : : : : : : : : : : :8.4The Triangle Puzzle : : : : : : : : : : : : : : : : : :8.4.1 Listing of TRIANGLE.PL : : : : : : : : : : : :8.5Coloring a Map : : : : : : : : : : : : : : : : : : : : :8.5.1 Listing of MAP.PL : : : : : : : : : : : : : : : :8.5.2 Listing of SAMERICA.PL (data for MAP.PL) : :8.6Examining Molecules : : : : : : : : : : : : : : : : :8.6.1 Listing of CHEM.PL : : : : : : : : : : : : : : :8.7Exhaustive Search, Intelligent Search, and Heuristics8.7.1 Listing of FLIGHT.PL : : : : : : : : : : : : : :8.8Scheduling : : : : : : : : : : : : : : : : : : : : : : :8.8.1 Listing of SCHEDULE.PL : : : : : : : : : : : :8.9Forward 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 : : : : : : : : : : : : : : : : : :8.18.2A Simple Expert System ShellExpert systems : : : : : : : : : : : : : : : : : : : :Expert consultants and expert consulting systems :Parts of an expert consulting system : : : : : : : :Expert system shells : : : : : : : : : : : : : : : : :Extending the power of Prolog : : : : : : : : : : :9.5.1 Listing of XSHELL.PL : : : : : : : : : : : : :9.6XSHELL: the main program : : : : : : : : : : : : :9.7Asking about properties in XSHELL : : : : : : : :9.8Asking about parameters in XSHELL : : : : : : : :9.9XSHELL’s explanatatory facility : : : : : : : : : : :9.19.29.39.49.5Authors’ manuscript693 ppid September 9, 1995187189191194197198201: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : 285288Prolog Programming in Depth
59.109.119.129.139.141011CICHLID: a sample XSHELL knowledge base9.10.1 Listing of CICHLID.PL : : : : : : : : : :A consultation with CICHLID : : : : : : : : :PAINT: a sample XSHELL knowledge base :9.12.1 Listing of PAINT.PL : : : : : : : : : : :Developing XSHELL knowledge bases : : : :Bibliographical notes : : : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :An Expert System Shell With Uncertainty10.1 Uncertainty, probability, and confidence : : : : : : :10.2 Representing and computing confidence or certainty10.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 : : : : : : : : : : : : : : : : : :Defeasible Prolog11.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 responses11.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 : : : : : : : : : : : : :Authors’ manuscript693 ppid September 9, 1995: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : :: : : : : : : : : : : : 373386387388389389390391392392396397Prolog Programming in Depth
611.2111.2211.2311.2412ATemporal persistence : : : : : : : : : : : : :The Election Example : : : : : : : : : : : :d-Prolog and the Closed World AssumptionBIBLIOGRAPHICAL NOTES : : : : : : : :Natural Language Processing12.1 Prolog and Human Languages12.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) Notation12.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 : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :Summary of ISO PrologA.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 : : : : : : :Authors’ manuscript693 ppid September 9, 1995: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : :: : : : : : : : : : : 463465465465466466467467467467467467Prolog Programming in Depth
7A.5A.6Flags : : : : : : : : : : : : : : : : : : : :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 baseA.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 ImplementationsIntroduction : : : : : : : : : : : : : : : : : : : : : :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.3Variation 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.4Control Constructs : : : : : : : : : : : : : : : : : :B.4.1 Negation : : : : : : : : : : : : : : : : : : : :B.4.2 Scope of cuts : : : : : : : : : : : : : : : : : :B.4.3 If–then–else : : : : : : : : : : : : : : : : : : :B.1B.2Authors’ manuscript693 ppid September 9, 1995: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : :: : : : : : : : : 488488488488489489489489490490490490491Prolog Programming in Depth
8B.5B.6B.7B.8Authors’ manuscriptB.4.4 Tail recursion and backtrack points : : : : : : : :B.4.5 Alternatives created by asserting : : : : : : : : :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 : : : : : : : : : : : : : : : : :Arithmetic : : : : : : : : : : : : : : : : : : : : : : : : :B.6.1 Evaluable functors : : : : : : : : : : : : : : : : :B.6.2 Where expressions are evaluated : : : : : : : : :B.6.3 Expressions created at runtime in Quintus PrologInput 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 : : : : : : : : : : : : : : : : : :Definite Clause Grammars : : : : : : : : : : : : : : : :B.8.1 Terminal nodes : : : : : : : : : : : : : : : : : : :B.8.2 Commas on the left : : : : : : : : : : : : : : : : :B.8.3 phrase : : : : : : : : : : : : : : : : : : : : : : : :693 ppid September 9, 1995: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : :: : : : : : : 94495495495496496497497Prolog Programming in Depth
PrefaceProlog is an up-and-coming computer language. It has taken its place alongside Lispin artificial intelligence research, and industry has adopted it widely for knowledgebased systems.In this book, we emphasize practical Prolog programming, not just theory. Wepresent several ready-to-run expert system shells, as well as routines for sorting,searching, natural language processing, and even numerical equation solving.We also emphasize interoperability with other software. For example, Chapter5 presents techniques for reading Lotus spreadsheets and other special file formatsfrom within a Prolog program.There is now an official ISO standard for the Prolog language, and this bookfollows it while retaining compatibility with earlier implementations. We summarize the ISO Prolog standard in Appendix A. It is essentially what has been called“Edinburgh” Prolog. Our programs have been tested under Quintus Prolog, ArityProlog, ALS Prolog, LPA Prolog, and a number of other commercial implementations, as well as freeware Prologs from ESL and SWI. (We do not cover Turbo [PDC]Prolog, nor Colmerauer’s Prolog II and III, which are distinctly different languages.)An earlier version of this book was published by Scott, Foresman in 1987. Sincethen, we have used the book in our own courses every year, and the present versionreflects numerous refinements based on actual classroom experience. We want tothank all our students and colleagues who made suggestions, especially Don Potter,Harold Dale, Judy Guinan, Stephen McSweeney, Xun Shao, Joerg Zeppen, JoergGrau, Jason Prickett, Ron Rouhani, Ningyu Chen, and Feng Chen.9Authors’ manuscript693 ppid September 9, 1995Prolog Programming in Depth
10When necessary, Chapter 7 can be skipped since the remainder of the book doesnot rely on them. Those who are not preparing for work in the software industry maytake Chapter 5 somewhat lightly. A Prolog course for experienced AI programmersshould cover Chapters 1-7 and 12 but may skip Chapters 8-11, which cover basic AItopics.The programs and data files from this book are available on diskette from thepublisher and by anonymous FTP from ai.uga.edu. From the same FTP site you canalso obtain freeware Prolog compilers and demonstrations of commercial products.We are always interested in hearing from readers who have questions or suggestions for improvement.Athens, GeorgiaSeptember 1995Authors’ manuscript693 ppid September 9, 1995Prolog Programming in Depth
Part IThe Prolog Language11Authors’ manuscript693 ppid September 9, 1995Prolog Programming in Depth
Authors’ manuscript693 ppid September 9, 1995Prolog Programming in Depth
Chapter 1Introducing Prolog1.1. THE IDEA OF PROLOGUntil recently, programming a computer meant giving it a list of things to do, stepby step, in order to solve a problem. In Prolog, this is no longer the case. A Prologprogram can consist of a set of facts together with a set of conditions that the solutionmust satisfy; the computer can figure out for itself how to deduce the solution fromthe facts given.This is called LOGIC PROGRAMMING. Prolog is based on formal logic in the sameway that FORTRAN, BASIC, and similar languages are based on arithmetic andsimple algebra. Prolog solves problems by applying techniques originally developedto prove theorems in logic.Prolog is a very versatile language. We want to emphasize throughout thisbook that Prolog can implement all kinds of algorithms, not just those for which it wasspecially designed. Using Prolog does not tie you to any specific algorithm, flow ofcontrol, or file format. That is, Prolog is no less powerful than Pascal, C, or C ;in many respects it is more powerful. Whether Prolog is the best language for yourpurposes will depend on the kind of job you want it to do, and we will do our bestto equip you to judge for yourself.Prolog was invented by Alain Colmerauer and his colleagues at the Universityof Aix-Marseille, in Marseilles, France, in 1972. The name stands for programmingin logic. Today Prolog is used mainly for artificial intelligence applications, especially automated reasoning systems. Prolog was the language chosen for the FifthGeneration Project, the billion-dollar program initiated by the Japanese government1Authors’ manuscript693 ppid September 9, 1995Prolog Programming in Depth
2Introducing PrologChap. 1in 1982 to create a new generation of knowledge–based computers. Commercially,Prolog is often used in expert systems, automated helpdesks, intelligent databases,and natural language processing programs.Prolog has much in common with Lisp, the language traditionally used forartificial intelligence research. Both languages make it easy to perform complexcomputations on complex data, and both have the power to express algorithms elegantly. Both Lisp and Prolog allocate memory dynamically, so that the programmerdoes not have to declare the size of data structures before creating them. And bothlanguages allow the program to examine and modify itself, so that a program can“learn” from information obtained at run time.The main difference is that Prolog has an automated reasoning procedure —an INFERENCE ENGINE — built into it, while Lisp does not. As a result, programs thatperform logical reasoning are much easier to write in Prolog than in Lisp. If the built–in inference engine is not suitable for a particular problem, the Prolog programmercan usually use part of the built–in mechanism while rewriting the rest. In Lisp, onthe other hand, if an inference engine is needed, the programmer must supply it.Is Prolog “object–oriented”? Not exactly. Prolog is a different, newer, and moreversatile solution to the pr
Authors' manuscript 693 ppid September 9, 1995 Prolog Programming in Depth Contents I The Prolog Language 9 1 Introducing Prolog 1 1.1 The Idea of Prolog: 1 1.2 How Prolog Works: 2 1.3 Varieties of Prolog: 4 1.4 A Practical Knowledge Base: 4 1.5 Unification and Variable Instantiation: 9 1.6 Backtracking: 10 1.7 Prolog Syntax: 14 1.8 .
