Parallel Execution of Logic Programs
Published on 31. January 1987
Book
Hardback
160 pages
978-0-89838-194-8 (ISBN)
Description
This book is an updated version of my Ph.D. dissertation, The AND/OR Process Model for Parallel Interpretation of Logic Programs. The three years since that paper was finished (or so I thought then) have seen quite a bit of work in the area of parallel execution models and programming languages for logic programs. A quick glance at the bibliography here shows roughly 50 papers on these topics, 40 of which were published after 1983. The main difference between the book and the dissertation is the updated survey of related work. One of the appendices in the dissertation was an overview of a Prolog implementation of an interpreter based on the AND/OR Process Model, a simulator I used to get some preliminary measurements of parallelism in logic programs. In the last three years I have been involved with three other implementations. One was written in C and is now being installed on a small multiprocessor at the University of Oregon. Most of the programming of this interpreter was done by Nitin More under my direction for his M.S. project.
The other two, one written in Multilisp and the other in Modula-2, are more limited, intended to test ideas about implementing specific aspects of the model. Instead of an appendix describing one interpreter, this book has more detail about implementation included in Chapters 5 through 7, based on a combination of ideas from the four interpreters.
The other two, one written in Multilisp and the other in Modula-2, are more limited, intended to test ideas about implementing specific aspects of the model. Instead of an appendix describing one interpreter, this book has more detail about implementation included in Chapters 5 through 7, based on a combination of ideas from the four interpreters.
More details
Series
Language
English
Place of publication
United States
Target group
College/higher education
Professional and scholarly
Illustrations
biography
Dimensions
Height: 240 mm
Width: 160 mm
Weight
440 gr
ISBN-13
978-0-89838-194-8 (9780898381948)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
John S. Conery
Parallel Execution of Logic Programs
Book
11/2011
Springer
€53.49
Shipment within 15-20 days
Content
1 Introduction.- 2 Logic Programming.- 2.1 Syntax.- 2.2 Semantics.- 2.3 Control.- 2.4 Prolog.- 2.4.1 Evaluable Predicates and Arithmetic.- 2.4.2 Higher Order Functions.- 2.4.3 The Cut Symbol.- 2.5 Alternate Control Strategies.- 2.5.1 Selection by Number of Solutions.- 2.5.2 Selection by Number of Uninstantiated Variables.- 2.5.3 Intelligent Backtracking.- 2.5.4 Coroutines.- 2.6 Chapter Summary.- 3 Parallelism in Logic Programs.- 3.1 Models for OR Parallelism.- 3.1.1 Pure OR Parallelism.- 3.1.2 OR Processes.- 3.1.3 Distributed Search.- 3.1.4 Summary.- 3.2 Models for AND Parallelism.- 3.2.1 Stream Parallel Models.- 3.2.2 AND Processes.- 3.2.3 AND Parallelism in the Goal Tree.- 3.2.4 Summary.- 3.3 Low Level Parallelism.- 3.4 Chapter Summary.- 4 The AND/OR Process Model.- 4.1 Oracle.- 4.2 Messages.- 4.3 OR Processes.- 4.4 AND Processes.- 4.5 Interpreter.- 4.6 Programming Language.- 4.7 Chapter Summary.- 5 Parallel OR Processes.- 5.1 Operating Modes.- 5.2 Execution.- 5.3 Example.- 5.4 Chapter Summary.- 6 Parallel AND Processes.- 6.1 Ordering of Literals.- 6.1.1 Dataflow Graphs.- 6.1.2 The Ordering Algorithm.- 6.1.3 Examples.- 6.2 Forward Execution.- 6.2.1 Forward Execution Algorithm.- 6.2.2 Solution of a Deterministic Function.- 6.3 Backward Execution.- 6.3.1 Generating Tuples of Terms.- 6.3.2 Definitions for Backward Execution.- 6.3.3 The Backward Execution Algorithm.- 6.4 Detailed Example.- 6.4.1 Ordering.- 6.4.2 Forward Execution.- 6.4.3 Backward Execution.- 6.4.4 Additional Solutions.- 6.5 Discussion.- 6.5.1 Relative Order of Incoming Messages.- 6.5.2 Definition of Candidate Set.- 6.5.3 Result Cache.- 6.5.4 Infinite Domains.- 6.5.5 Multisets of Results.- 6.6 Chapter Summary.- 7 Implementation.- 7.1 Overview of the Interpreter.- 7.2 Parallel AND Processes.- 7.3 Process Allocation.- 7.4 Growth Control.- 7.4.1 Conditional Expressions.- 7.4.2 Process Priorities.- 7.4.3 Message Protocols.- 7.4.4 Secondary Memory.- 7.5 Summary.