Prolog Programming in Depth - Michael A. Covington, Donald Nute, Andre Vellino [September 1995].pdf - Prolog Programming in Depth - Kowalski2015

Prolog Programming in Depth

(AUTHORS’ MANUSCRIPT)

Michael A. Covington

Donald Nute

Andre Vellino

Artiﬁcial Intelligence Programs

The University of Georgia

Athens, Georgia 30602–7415 U.S.A.

September 1995

Authors’ manuscript

693 ppid September 9, 1995

Prolog Programming in Depth

Contents

I The Prolog Language

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.6 Backtracking : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10

1.7 Prolog Syntax : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14

1.8 Deﬁning Relations : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16

1.9 Conjoined Goals (“And”) : : : : : : : : : : : : : : : : : : : : : : : : 18

1.10 Disjoint Goals (“Or”) : : : : : : : : : : : : : : : : : : : : : : : : : : : 19

1.11 Negative Goals (“Not”) : : : : : : : : : : : : : : : : : : : : : : : : : 20

1.12 Testing for Equality : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22

1.13 Anonymous Variables : : : : : : : : : : : : : : : : : : : : : : : : : : 24

1.14 Avoiding Endless Computations : : : : : : : : : : : : : : : : : : : : 25

1.15 Using the Debugger to Trace Execution : : : : : : : : : : : : : : : : : 27

1.16 Styles of Encoding Knowledge : : : : : : : : : : : : : : : : : : : : : 28

1.17 Bibliographical Notes : : : : : : : : : : : : : : : : : : : : : : : : : : 30

Uniﬁcation and Variable Instantiation : : : : : : : : : : : : : : : : :

Authors’ manuscript

693 ppid September 9, 1995

Prolog Programming in Depth

1.5

Constructing Prolog Programs 31

2.1 Declarative and Procedural Semantics : : : : : : : : : : : : : : : : : 31

2.2 Output: write , nl , display : : : : : : : : : : : : : : : : : : : : : : : 32

2.3 Computing versus Printing : : : : : : : : : : : : : : : : : : : : : : : 34

2.4 Forcing Backtracking with fail : : : : : : : : : : : : : : : : : : : : : 34

2.5 Predicates as Subroutines : : : : : : : : : : : : : : : : : : : : : : : : 37

2.6 Input of Terms: read : : : : : : : : : : : : : : : : : : : : : : : : : : : 38

2.7 Manipulating the Knowledge Base : : : : : : : : : : : : : : : : : : : 40

2.8 Static and Dynamic Predicates : : : : : : : : : : : : : : : : : : : : : 42

2.9 More about consult and reconsult : : : : : : : : : : : : : : : : : : 43

2.10 File Handling: see , seen , tell , told : : : : : : : : : : : : : : : : : : 45

2.11 A Program that “Learns” : : : : : : : : : : : : : : : : : : : : : : : : 46

2.12 Character Input and Output: get , get0 , put : : : : : : : : : : : : : : 48

2.13 Constructing Menus : : : : : : : : : : : : : : : : : : : : : : : : : : : 51

2.14 A Simple Expert System : : : : : : : : : : : : : : : : : : : : : : : : : 54

Data Structures and Computation 61

3.1 Arithmetic : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 61

3.2 Constructing Expressions : : : : : : : : : : : : : : : : : : : : : : : : 63

3.3 Practical Calculations : : : : : : : : : : : : : : : : : : : : : : : : : : 65

3.4 Testing for Instantiation : : : : : : : : : : : : : : : : : : : : : : : : : 67

3.5 Lists : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 69

3.6 Storing Data in Lists : : : : : : : : : : : : : : : : : : : : : : : : : : : 71

3.7 Recursion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 72

3.8 Counting List Elements : : : : : : : : : : : : : : : : : : : : : : : : : 74

3.9 Concatenating (Appending) Lists : : : : : : : : : : : : : : : : : : : : 75

3.10 Reversing a List Recursively : : : : : : : : : : : : : : : : : : : : : : : 77

3.11 A Faster Way to Reverse Lists : : : : : : : : : : : : : : : : : : : : : : 78

3.12 Character Strings : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 79

3.13 Inputting a Line as a String or Atom : : : : : : : : : : : : : : : : : : 81

3.14 Structures : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 83

3.15 The “Occurs Check” : : : : : : : : : : : : : : : : : : : : : : : : : : : 85

3.16 Constructing Goals at Runtime : : : : : : : : : : : : : : : : : : : : : 85

3.17 Data Storage Strategies : : : : : : : : : : : : : : : : : : : : : : : : : : 87

3.18 Bibliographical Notes : : : : : : : : : : : : : : : : : : : : : : : : : : 89

Expressing Procedural Algorithms 91

4.1 Procedural Prolog : : : : : : : : : : : : : : : : : : : : : : : : : : : : 91

4.2 Conditional Execution : : : : : : : : : : : : : : : : : : : : : : : : : : 92

4.3 The “Cut” Operator ( ! ) : : : : : : : : : : : : : : : : : : : : : : : : : 94

4.4 Red Cuts and Green Cuts : : : : : : : : : : : : : : : : : : : : : : : : 96

4.5 Where Not to Put Cuts : : : : : : : : : : : : : : : : : : : : : : : : : : 97

4.6 Making a Goal Deterministic Without Cuts : : : : : : : : : : : : : : 98

4.7 The “If–Then–Else” Structure ( -> ) : : : : : : : : : : : : : : : : : : : : 99

4.8 Making a Goal Always Succeed or Always Fail : : : : : : : : : : : : 99

4.9 Repetition Through Backtracking : : : : : : : : : : : : : : : : : : : : 101

4.10 Recursion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 103

Authors’ manuscript

693 ppid September 9, 1995

Prolog Programming in Depth

4.11 More About Recursive Loops : : : : : : : : : : : : : : : : : : : : : : 104

4.12 Organizing Recursive Code : : : : : : : : : : : : : : : : : : : : : : : 107

4.13 Why Tail Recursion is Special : : : : : : : : : : : : : : : : : : : : : : 108

4.14 Indexing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 111

4.15 Modularity, Name Conﬂicts, and Stubs : : : : : : : : : : : : : : : : : 113

4.16 How to Document Prolog Predicates : : : : : : : : : : : : : : : : : : 114

4.17 Supplement: Some Hand Computations : : : : : : : : : : : : : : : : 116

4.17.1 Recursion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 116

4.17.2 Saving backtrack points : : : : : : : : : : : : : : : : : : : : : : 117

4.17.3 Backtracking : : : : : : : : : : : : : : : : : : : : : : : : : : : : 118

4.17.4 Cuts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 120

4.17.5 An unexpected loop : : : : : : : : : : : : : : : : : : : : : : : : 122

4.18 Bibliographical Notes : : : : : : : : : : : : : : : : : : : : : : : : : : 127

Reading Data in Foreign Formats 129

5.1 The Problem of Free–Form Input : : : : : : : : : : : : : : : : : : : : 129

5.2 Converting Strings to Atoms and Numbers : : : : : : : : : : : : : : 129

5.3 Combining Our Code with Yours : : : : : : : : : : : : : : : : : : : : 133

5.4 Validating User Input : : : : : : : : : : : : : : : : : : : : : : : : : : 134

5.5 Constructing Menus : : : : : : : : : : : : : : : : : : : : : : : : : : : 135

5.6 Reading Files with get byte : : : : : : : : : : : : : : : : : : : : : : : 136

5.7 File Handles (Stream Identiﬁers) : : : : : : : : : : : : : : : : : : : : 139

5.8 Fixed–Length Fields : : : : : : : : : : : : : : : : : : : : : : : : : : : 140

5.9 Now What Do You Do With the Data? : : : : : : : : : : : : : : : : : 143

5.10 Comma–Delimited Fields : : : : : : : : : : : : : : : : : : : : : : : : 143

5.11 Binary Numbers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 144

5.12 Grand Finale: Reading a Lotus Spreadsheet : : : : : : : : : : : : : : : 148

5.13 Language and Metalanguage : : : : : : : : : : : : : : : : : : : : : : 153

5.14 Collecting Alternative Solutions into a List : : : : : : : : : : : : : : : 153

5.15 Using bagof and setof : : : : : : : : : : : : : : : : : : : : : : : : : 155

5.16 Finding the Smallest, Largest, or “Best” Solution : : : : : : : : : : : 157

5.17 Intensional and Extensional Queries : : : : : : : : : : : : : : : : : : 159

5.18 Operator Deﬁnitions : : : : : : : : : : : : : : : : : : : : : : : : : : : 160

5.19 Giving Meaning to Operators : : : : : : : : : : : : : : : : : : : : : : 163

5.20 Prolog in Prolog : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 165

5.21 Extending the Inference Engine : : : : : : : : : : : : : : : : : : : : : 167

5.22 Personalizing the User Interface : : : : : : : : : : : : : : : : : : : : : 170

5.23 Bibliographical Notes : : : : : : : : : : : : : : : : : : : : : : : : : : 172

Advanced Techniques

173

7.1

Structures as Trees : : : : : : : : : : : : : : : : : : : : : : : : : : : : 173

7.2

Lists as Structures : : : : : : : : : : : : : : : : : : : : : : : : : : : : 175

7.3

How to Search or Process Any Structure : : : : : : : : : : : : : : : : 176

7.4

Internal Representation of Data : : : : : : : : : : : : : : : : : : : : : 177

7.5

Simulating Arrays in Prolog : : : : : : : : : : : : : : : : : : : : : : : 181

7.6

Difference Lists : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 182

7.7

Quicksort : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 183

Authors’ manuscript

693 ppid September 9, 1995

Prolog Programming in Depth

7.8 Efﬁciency of Sorting Algorithms : : : : : : : : : : : : : : : : : : : : 187

7.9 Mergesort : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 189

7.10 Binary Trees : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 191

7.11 Treesort : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 194

7.12 Customized Arithmetic: A Replacement for is : : : : : : : : : : : : 197

7.13 Solving Equations Numerically : : : : : : : : : : : : : : : : : : : : : 198

7.14 Bibliographical Notes : : : : : : : : : : : : : : : : : : : : : : : : : : 201

II Artiﬁcial Intelligence Applications

205

Artiﬁcial Intelligence and the Search for Solutions 209

8.1 Artiﬁcial Intelligence, Puzzles, and Prolog : : : : : : : : : : : : : : : 209

8.2 Through the Maze : : : : : : : : : : : : : : : : : : : : : : : : : : : : 213

8.2.1 Listing of MAZE.PL : : : : : : : : : : : : : : : : : : : : : : : : 215

8.2.2 Listing of MAZE1.PL (connectivity table) : : : : : : : : : : : : 216

8.3 Missionaries and Cannibals : : : : : : : : : : : : : : : : : : : : : : : 216

8.3.1 Listing of CANNIBAL.PL : : : : : : : : : : : : : : : : : : : : : 219

8.4 The Triangle Puzzle : : : : : : : : : : : : : : : : : : : : : : : : : : : 221

8.4.1 Listing of TRIANGLE.PL : : : : : : : : : : : : : : : : : : : : : 223

8.5 Coloring a Map : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 226

8.5.1 Listing of MAP.PL : : : : : : : : : : : : : : : : : : : : : : : : : 228

8.5.2 Listing of SAMERICA.PL (data for MAP.PL) : : : : : : : : : : : 229

8.6 Examining Molecules : : : : : : : : : : : : : : : : : : : : : : : : : : 229

8.6.1 Listing of CHEM.PL : : : : : : : : : : : : : : : : : : : : : : : : 233

8.7 Exhaustive Search, Intelligent Search, and Heuristics : : : : : : : : : 236

8.7.1 Listing of FLIGHT.PL : : : : : : : : : : : : : : : : : : : : : : : 243

8.8 Scheduling : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 245

8.8.1 Listing of SCHEDULE.PL : : : : : : : : : : : : : : : : : : : : : 251

8.9 Forward Chaining and Production Rule Systems : : : : : : : : : : : 255

8.10 A Simple Forward Chainer : : : : : : : : : : : : : : : : : : : : : : : 257

8.11 Production Rules in Prolog : : : : : : : : : : : : : : : : : : : : : : : 258

8.11.1 Listing of FCHAIN.PL : : : : : : : : : : : : : : : : : : : : : : : 261

8.11.2 Listing of CARTONS.PL : : : : : : : : : : : : : : : : : : : : : : 263

8.12 Bibliographical notes : : : : : : : : : : : : : : : : : : : : : : : : : : : 265

A Simple Expert System Shell

267

9.1

Expert systems : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 267

9.2

Expert consultants and expert consulting systems : : : : : : : : : : : 268

9.3

Parts of an expert consulting system : : : : : : : : : : : : : : : : : : 269

9.4

Expert system shells : : : : : : : : : : : : : : : : : : : : : : : : : : : 269

9.5

Extending the power of Prolog : : : : : : : : : : : : : : : : : : : : : 271

9.5.1 Listing of XSHELL.PL : : : : : : : : : : : : : : : : : : : : : : : 272

9.6

XSHELL: the main program : : : : : : : : : : : : : : : : : : : : : : : 281

9.7

Asking about properties in XSHELL : : : : : : : : : : : : : : : : : : 283

9.8

Asking about parameters in XSHELL : : : : : : : : : : : : : : : : : : 285

9.9

XSHELL’s explanatatory facility : : : : : : : : : : : : : : : : : : : : : 288

Authors’ manuscript

693 ppid September 9, 1995

Prolog Programming in Depth

Prolog Programming in Depth - Michael A. Covington, Donald Nute, Andre Vellino [September 1995].pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: