상세정보

This book represents an attempt to combine concurrent logic programming and constraint logic programming. It is divided into three parts. In the first part, a novel computation mode, called the multi-Pandora model, which is designed on the basis of the Pandora model, is presented. In the second part, the distributed implementation schemes for Parlog, Pandor and multi-Pandor are presented. Finally, the author presents the distributed constraint solvers in the domains of real numbers and Boolean rings which can be incorporated into the schemes presented in Part 2 to handle the "ask-" and "tell"-constraints.

정보제공 :

CONTENTS
Preface = ⅶ
Acknowledgement = ⅹ
INTRODUCTION = 1
Chapter Ⅰ Distributed and Constraint Logic Programming-A Brief History = 3
 1.1 The Logic Programming Paradigm = 4
  1.1.1 Re Origin of Logic Programming = 4
  1.1.2 The Basic Nomenclatures = 4
  1.1.3 Predicate Logic as Programing Language = 4
 1.2 Logic Programming Languages and Their Implementations = 5
  1.2.1 Prolog = 6
  1.2.2 Warren Abstract Machine = 8
  1.2.3 Parallel Execution of prolog = 9
  1.2.4 Committed-Choice Logic Programming Languages = 10
  1.2.5 Implementations of Committed Choice Logic Programming Languages = 15
 1.3 Distributed Logic Programming = 16
  1.3.1 Distributed Implementations of Prolog = 17
  1.3.2 Special Distributed Logic Programming Languages = 17
 1.4 Constraint Logic Programming = 19
  1.4.1 CLP(R) = 19
  1.4.2 CHIP = 19
  1.4.3 Prolog Ⅲ = 20
  1.4.4 CAL = 20
  1.4.5 Concurrent Constraint Programming = 23
 1.5 Structure of the Book = 21
 1.6 The Contributions of this Research = 23
PART ONE = 27
 Chapter Ⅱ Parlog, Pandora and Their Abstract Machines = 29
  2.1 The Parlog Language = 29
   2.1.1 The Syntax = 29
   2.1.2 The Semantics = 29
   2.1.5 Kernel Parlog = 30
  2.2 JAM-A Parlog Abstract Machine = 32
   2.2.1 Data Structures in JAM 32
   2.2.2 The Execution Model in JAM 33
  2.3 The Pandora Language = 36
  2.4 The Pandora Abstract Machine = 38
 Chapter Ⅲ The Multi-Pandora Model and the Multi-Pandora Abstract Machine = 41
  3.1 The Multi-Pandora Model = 42
   3.1.1 Disjointed AND-parallelism and Connected Groups = 42
   3.1.2 The Multi-Pandora Model = 43
  3.2 An Outline of the Design of the Multi-Pandora Abstract Machine = 49
   3.2.1 Data Structures in the Multi-Pandora Abstract Machine = 50
   3.2.2 Detection of Deadlocked Connected Groups during Garbage Collection = 51
  3.3 Deadlock Handling in Multi-Pandora = 67
   3.3.1 Deadlock Handling in Multi-Pandora = 68
   3.3.2 The Implementation of Deadlock Handling = 68
  3.4 Discussions and Conclusions = 70
PART TWO = 71
 Chapter Ⅳ Distributed Implementation of Parlog = 73
  4.1 Distributed Implementation of Parlog-An Overview = 73
   4.1.1 The Design of the Distributed Implementation = 73
   4.1.2 The Weighted Reference Count Technique = 74
  4.2 The Distributed AND-tree Model = 75
   4.2.1 The AND-tree Model : a Starting Point = 75
   4.2.2 The Foster Parents = 77
   4.2.3 Process Migration Using Weighted Reference Count = 78
   4.2.4 Simplification Under Certain Conditions = 83
  4.3 The Distributed Unification Scheme = 84
   4.3.1 The Import Variable Table and the Export Variable Table = 85
   4.3.2 Variable Exportation and Reexportation = 86
   4.3.3 The Distributed Unification Scheme = 90
   4.3.4 Circular Reference Avoidance = 93
   4.3.5 Deep Guard Consideration = 94
  4.4 Distributed Garbage Collection = 95
   4.4.1 Garbage Collection for the Import Variable Table = 96
   4.4.2 Garbage Collection for the Export Variable Tabie = 97
   4.4.3 Garbage Collection for the Foster Parent Table and the Foster Parent Look-up Table 98
  4.5 The Distributed Parlog Language = 98
   4.5.1 The Syntax = 98
   4.5.2 The Semantics = 99
  4.6 Programming in Distributed Parlog = 100
   4.6.1 The Dolev-Klawe-Rodeh Algorithm for Extrema Finding 100
   4.6.2 The Distributed Snapshot Algorithm = 102
   4.6.3 The Dining Philosophers = 104
   4.6.4 The Communication Complexity of Lists as Channels = 105
   4.6.5 Half-Duplex' Channels = 107
  4.7 Comparisons with Related Work = 109
   4.7.1 The Execution Models = 109
   4.7.2 The Distributed Unification Schemes = 110
   4.7.3 The Distributed Garbage Collection Schemes = 114
  4.8 Conclusions = 117
 Chapter Ⅴ Distributed Implementation of pandora = 119
  5.1 An Overview of the Distributed Implementation = 119
   5.1.1 The Concepts of Stage and Computation State = 119
   5.1.2 An Overview of the Implementation = 122
  5.2 Distributed Deadlock Detection in Distributed Pandora = 123
  5.3 Setting up a Choice Point in Distributed Pandora = 126
  5.4 Failure and Backtracking Distributed Pandora = 133
  5.5 Identification of Obsolete Messages = 136
  5.6 Properties and Correctness of the Algorithm = 135
  5.7 The Trailing Mechanism = 141
  5.8 Conclusions = 142
 Chapter Ⅵ Distributed Implementation of Multi-Pandora = 143
  6.1 Issues in Distributed Implementation of Multi-Pandora = 144
   6.1.1 New Problems for Distributed Implementation = 144
   6.1.2 Modifications to the Data Structures = 145
  6.2 An Overview of the Distributed Implementation = 146
  6.3 The Distributed Deadlock Connected Group Detection Algorithm = 148
   6.3.1 An Informal Overview of the Algorithm = 148
   6.3.2 The Algorithm in Five Parts = 151
   6.3.3 The Formats of Messages = 153
   6.3.4 The Algorithm - Part Ⅰ = 154
   6.3.5 The Algorithm - Part Ⅱ = 158
   6.3.6 The Algorithm - Part Ⅲ = 159
   6.3.7 The Algorithm - Part Ⅳ = 161
   6.3.8 The Algorithm - Part Ⅴ = 162
   6.3.9 Some Properties of the Algorithm = 162
  6.4 Setting UP Distributed Choice Points = 163
   6.4.1 The Age and Computation Stale in Distributed Multi-Pandora = 164
   6.4.2 The Distributed Choice Points = 165
  6.5 Backtracking and Failure Recovery = 167
  6.6 Identifying Obsolete Messages = 169
  6.7 Finding the Next Answer Substitution = 169
  6.8 Deadlock Handling in Distributed Multi-Pandora = 171
   6.8.1 Dead lock Handier in Distributed Multi-Pandora = 172
   6.8.2 The Default Deadlock Handler = 172
  6.9 Conclusions = 173
 Chapter Ⅶ Finite Domain Constraints in Distributed Concurrent Logic Programming Languages = 175
  7.1 Finite Domains in Logic Programming = 175
   7.1.1 Finite Domain = 175
   7.1.2 Declaration of Finite Domain Constraints = 176
   7.1.3 Domain Variables and d-Unification = 178
   7.1.4 The FCIR, the LAIR and the PLAIR = 179
  7.2 Implementation of Finite Domain Constraints in Distributed Concurrent Logic Programming Languages = 181
   7.2.1 Implementation of Domain Variables = 181
   7.2.2 Implementation of d-Unification = 182
   7.2.3 Implementation of Distributed d-Unification = 183
   7.2.4 The $deadlocked Register = 187
   7.2.5 Translating a Forward-Checking Constraint into Parlog = 187
   7.2.6 Translating a Looking-Ahead Constrain into Parlog = 191
  7.3 A Comparison with Bahgat's Approach = 193
   7.3.1 Bahgat's Approach to Constraint-Based Reasoning = 193
   7.3.2 A Comparison to th Current Approach = 195
  7.4 Conclusions = 198
PART THREE = 199
 Chapter Ⅷ Distributed Constraint Concurrent Logic Programming = 201
  8.1 Constraints in Concurrent Logic Programming Languages = 202
   8.1.1 'Ask'- Constraints = 202
   8.1.2 'Tell'- Constraints = 203
  8.2 Distributed Constraint Solving = 204
   8.2.1 Motivations = 204
   8.2.2 The Logic Programming Machines and the Constraint Solvers = 205
  8.3 Constraint Variables and Generation of New Constraints = 207
  8.4 Constraint Migration = 208
  8.5 Variable Migration = 209
  8.6 Other Issues = 210
 Chapter Ⅸ Distributed Constraint Solver in the Domain of Real Numbers = 211
  9.1 Definitions = 212
   9.1.1 Ordering and Locality of Constraint Variables = 212
   9.1.2 Ordering and Locality of Constraints = 213
  9.2 Distributed Constraint Solving For Linear Equations = 213
   9.2.1 The Algorithm = 214
   9.2.2 An Example = 215
   9.2.3 Properties and Correctness of the Algorithm = 218
  9.3 Distributed Constraint Solving for Linear Equations and Inequalities = 219
   9.3.1 The s-Variables = 219
   9.3.2 Feasibility of Simultaneous Linear Equation of Nonnegative Variables = 220
   9.3.3 Strict Inequalities and Implicit Equations = 225
   9.3.4 The Distributed Implementation = 229
   9.3.5 Examples = 234
  9.4 Conclusions = 238
 Chapter Ⅹ Distributed Constraint Solver in the Domain of Boolean Rings = 239
  10.1 Boolean Unification = 239
   10.1.1 Boolean Ring = 239
   10.1.2 Boolean Unification Algorithm = 241
  10.2 The Distributed Implementation = 243
  10.3 Properties and Correctness of the Distributed Implementation = 244
  10.4 Examples = 246
  10.5 Conclusions = 249
 Chapter XI Integrating Distributed Constraint Solvers and Distributed Logic Programming Languages = 251
  11.1 Interfacing the Logic Programming Machine and the Constraint Solver = 251
   11.1.1 The Constraint Variables = 251
   11.1.2 Passing New Constraints to the Constraint Solver = 253
  11.2 A Lazy Variable Migration Technique = 254
   11.2.1 The Variable Exportation／Reexportation Scheme Revisited = 255
   11.2.2 A Lazy Variable Migration Technique = 255
   11.2.3 The Three Indices of the s-Variables = 257
  11.3 Implementation of Constraint Guard Calls = 257
   11.3.1 The Suspension Mechanism = 257
   11.3.2 Constraint Guard Call Suspension Mechanism = 258
   11.3.3 Remote Constraint Guard Calls = 259
   11.3.4 Constraint Guards and Metacall = 260
  11.4 Garbage Collection for Constraint Guards = 262
   11.4.1 Local Garbage Collection = 253
   11.4.2 Remote Garbage Collection = 263
  11.5 Trailing and Recovery of Constraints = 263
   11.5.1 The Modification of the Constraint Solvers = 264
   11.5.2 The Trailing Mechanism in Distributed Constraint Pandora = 264
   11.5.3 The Trailing Mechanism in Distributed Constraint Multi-Pandora = 266
  11.6 Conclusions = 266
CONCLUSIONS 267
 Chapter XII Conclusions and Future Work = 269
  12.1 Summary = 269
  12.2 Future Work 270
REFERENCES = 273
References = 275
APPENDICES = 291
 Appendix A A Detailed Trace of a Pandora Program = 293
 Appendix B Proofs of Theorems = 297
 Appendix C The αβγ-bit Algorithm for Detection of Termination of Multi-Processor Execution = 307
 Appendix D The Shafrir-Shapiro Implementation of the Dolev-Klawe-Rodeh Algorithm in Concurrent Prolog = 311
 Appendix E A Distributed Parlog Implementation of the Distributed Snapshots Algorithm = 315
 Appendix F A Distributed Parlog Implementation of the Dining Philosophers Problem = 317
 Appendix G Parlog Codes for the Implementation of the Looking-Ahead Inference Rule = 321