Cut and side-effects in a data-driven implementation of prolog

A number of data-driven execution models have been proposed for parallel execution of logic programs. LogDf is an abstract data-driven execution model for pure logic programs, which has shown promising performance during simulations. However, the original model lacks support for extra logical featur...

Full description

Saved in:
Bibliographic Details
Published in:New generation computing 1994-06, Vol.12 (3), p.223-250
Main Authors: AUWATANAMONGKOL, S, CIEPIELEWSKI, A, BISWAS, P
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Language theory and syntactical analysis
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A number of data-driven execution models have been proposed for parallel execution of logic programs. LogDf is an abstract data-driven execution model for pure logic programs, which has shown promising performance during simulations. However, the original model lacks support for extra logical features such as cut and side-effects, which are needed to execute Prolog programs. This paper describes a scheme that has been incorporated into the LogDf model to support cut and side-effects. The main component of the scheme is a data structure, called a flat, non-strict S-Stream, which maintains strict ordering of multiple solutions, and, at the same time, allows simultaneous modification by several actors. This ordering corresponds to the order in which solutions would be produced in a sequential system and is necessary to implement cut and side-effects. The correct synchronization and ordering of operations on the cells of an S-Stream is ensured by the use of I-structure memory. The descriptor based token coloring mechanism in the LogDf provides convenient support for maintaining the scope information associated with cuts. An efficient garbage collection strategy is also proposed.
ISSN:0288-3635
1882-7055
DOI:10.1007/BF03037344