Implementations of Distributed Prolog
Edited by
Peter Kacsuk, KFKI Research Institute for Measurement and Computing Techniques, Hungary
and
Michael J. Wise, University of Sydney, Australia
Foreword by Doug De Groot, Texas Instruments, USA
Although much needed, standard and commercially successful parallel processing languages are unlikely to emerge until the many complex issues inherent in parallel computation are understood. This is particularly the case for distributed systems, so there is continuing R&D need to search out solutions.
Apart from their use in areas such as Artificial Intelligence, logic programming languages can play the role of parallel processing shells in parallel and distributed systems by allowing programmers to focus on details of algorithms. From this point of view, major issues covered in the book range from scheduling to compilation and from algorithm expression to performance measurements.
For those engaged in developing practical systems for logic programming, this book describes computational models, implementation techniques and language extensions which in novel and explorative ways exploit parallel computers. In particular, this volume is the first to examine implementations of logic programming languages on distributed systems.
Author(s): edited by Peter Kacsuk and Michael Wise
Edition: 1
Publisher: John Wiley & Sons
Year: 1992
Language: English
Pages: 469
City: New York
Tags: Prolog, Parallel Processing, Parallel Programming, Logic Programming
xi - Foreword by Doug DeGroot, March 1992
xviv - List of Contributors
1 - PART I - OR-PARALLEL IMPLEMENTATIONS OF PROLOG
==================================================
3 - /1/ OR-Parallel Logic Computational Models
(S. A. Delgado-Rannauro)
3 - 1. Concepts and methods
6 - 2. The shared binding environment family
16 - 3. The closed binding environment family
20 - 4. Recomputation family
24 - 5. Summary
26 - Acknowledgements
27 - /2/ Parallel Prolog on a Scalable multiprocessor
(S. Raina, D. H. D. Warren and J. Cownie)
27 - 1. Introduction
28 - 2. Parallel Prolog implementations
29 - 3. MIMD multiprocessors
30 - 4. Related work on scalable architectures
31 - 5. The Data Diffusion Machine
32 - 6. A Transputer-based emulation of the DDM
41 - 7. Aurora and Andorra-I on the DDM emulator
43 - 8. Conclusion and future work
44 - Acknowledgements
45 - /3/ OPERA: OR-Parallel Prolog System on Supernode
(J. Briat, M. Favre, C. Geyer and J. Chassin de Kergommeaux)
45 - 1. Introduction
47 - 2. Architecture of the Supernode
48 - 3. The OPERA computational model
54 - 4. Scheduling of work
59 - 5. Implementation and preliminary results
61 - 6. Related work
63 - 7. Conclusion
63 - Acknowledgements
65 - /4/ A Distributed Interpreter for Inherent AND/OR Parallelism
(M. Avvenuti, P. Corsini and G. Frosini)
65 - 1. Introduction
66 - 2. The parallel execution model
72 - 3. Implementing the interpreter
79 - 4. Performing evaluation
83 - 5. A model optimization
85 - 6. Conclusions and future work
86 - Appendix 1: The benchmark program
89 - /5/ Distributed Data Driven Prolog Abstract Machine
(P. Kacsuk)
89 - 1. Introduction
90 - 2. Graph representation of Prolog programs
92 - 3. Parallel execution
97 - 4. General view of the 3DPAM
98 - 5. Machine registers and data structures
101 - 6. Abstract instruction set
112 - 7. Variable binding
115 - 8. Comparison with related research
117 - Conclusions
118 - Acknowledgements
119 - PART II - AND- AND AND/OR-PARALLEL IMPLEMENTATIONS OF PROLOG
==================================================================
121 - /6/ Restricted AND- and AND/OR-Parallel Logic Computational Models
(S. A. Delgado-Rannauro)
121 - 1. Restricted AND-Parallel logic models
132 - 2. AND/OR-Parallel logic models
140 - 3. Summary
141 - Acknowledgements
143 - /7/ An AND-Parallel Distributed Prolog Executor
(A. Verden and H. Glaser)
143 - 1. Introduction
145 - 2. An example execution
146 - 3. Communicating variable bindings
147 - 4. The Execution scheme
151 - 5. Clause level intelligent backtracking
153 - 6. Evaluation of our implementation
156 - 7. Conclusions
157 - Appendix
159 - /8/ The OPAL Machine
(J.S. Conery)
159 - 1. Background: OPAL and the AND/OR model
161 - 2. Modules of an OPAL implementation
165 - 3. Control: processes and continuations
171 - 4. Unification: closed environments
179 - 5. Performance
181 - 6. Acknowledgements
182 - 7. The OM instruction set
187 - /9/ The Reduce-OR Process Model ofr Parallel Logic Programming on Non-Shared Memory Machines
(L. V. Kalé and B. Ramkumar)
187 - Introduction
188 - The Reduce-OR process model
191 - The Binding environment
205 - Compiled execution
207 - Performance
212 - Summary
213 - /10/ An Actor-oriented Computer for Logic and its Applications
(C. Percebois, N. Signès and L. Selle)
213 - 1. Committed-choice languages vs. non-deterministic systems
215 - 2. The COALA goal rewriting system
219 - 3. Implementation of the parallel execution model
223 - 4. Independent AND-Parallelism
227 - 5. SEARCH-Parallelism
228 - 6. The CIAM abstract machine
234 - 7. Preliminary results
235 - Summary and conclusion
235 - Acknowledgements
237 - PART III - COMMITTED CHOICE LANGUAGES
===========================================
239 - /11/ Stream AND-Parallel Logic Computational Models
(S. A. Delgado-Rannauro)
239 - 1. Concepts
241 - 2. CCND Languages
246 - 3. Architectural modesl fro CCND languages
256 - 4. Summary
257 - Acknowledgements
259 - /12/ Logical Occam
(D. Cohen, M. M. Huntbach and G. A. Ringwood)
259 - 1. Introduction
261 - 2. The producer-consumer prototype
267 - 3. Synchronous from asynchronous
272 - 4. The client-server prototype
275 - 5. Semantics
277 - 6. Open worlds
279 - 7. Implementation issues
281 - 8. Meta-interpretation and partial evaluation of Occam
284 - 9. Conclusions
287 - /13/ A Distributed Implementation of Flat Concurrent Prolog on Multi-transputer Environments
(U. Glässer)
287 - 1. Introduction
289 - 2. Concurrent logic programming
293 - 3. Design of an abstract FCP machine
295 - 4. Concepts for a distributed implementation
304 - 5. A multi-transputer implementation of FCP
309 - 6. Conclusions
311 - /14/ Distributed Implementation of KL1 on the Multi-PSI
(K. Nakajima)
311 - 1. Introduction
312 - 2. GHC and KL1
313 - 3. Architecture of the Multi-PSI
316 - 4. Intra-PE processing
319 - 5. Inter-PE processing
327 - 6. Programming environment support
328 - 7. Evaluation
332 - 8. Conclusion
332 - Acknowledgements
333 - PART IV - PROCESS-ORIENTED PROLOG LANGUAGES
=================================================
335 - /15/ Delta Prolog: A Distributed Logic Programming Language and its Implementation on Distributed Memory Multiprocessors
(J. C. Cunha, P. D. Medeiros, M. B. Carvalhosa and L. M- Pereira)
335 - 1. Introduction
335 - 2. The programming model
339 - 3. Operational semantics
352 - 4. Implementing the parallel models
355 - 5. Conclusion and future work
356 Acknowledgements
357 - /16/ CS-Prolog: A Communicating Sequential Prolog
(Sz. Ferenczi and I. Futó)
357 - 1. Introduction
358 - 2. Concepts of CS Prolog
368 - 3. Ensuring distributed completeness
370 - 4. Examples
374 - 5. System simulation in CS-Prolog
375 - 6. Implementation issues
377 - 7. Assessment of CS-Prolog
378 - Acknowledgements
379 - /17/ PMS-Prolog: A Distributed, Coarse-grain-parallel Prolog with Processes, Modules and Streams
(M. J. Wise, D. G. Jones and T. Hintz)
380 - 1. Introduction and desiderata
383 - 2. Assumptions underlying PMS-Prolog
385 - 3. Preliminaries - adding modules to Prolog
386 - 4. Adding processes and streams - an overview
388 - 5. A simple example: the producer-consumer problem
389 - 6. More details on fork, transmit and receive
393 - 7. Two other built-ins
393 - 8. Uniprocessor and multiprocessor PMS-Prolog
399 - 9. Discussion of the longer example
400 - 10. Related work
405 - /18/ PADMAVATI Prolog (X. de Joybert and J. J. Monot)
405 - 1. Introduction
406 - 2. The PADMAVATI machine
407 - 3. Prolog parallelism model
409 - 4. Implementation of parallel aspects
414 - 5. Implementation of sequential aspects
415 - 6. Padmalog through examples
423 - 7. Discussion of performance
423 - 8. Conclusion
427 - Acknowledgements
429 - References
459 - Index (compiled by Paul Nash)
