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

• 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
• ISSN: 0288-3635; 1882-7055
• DOI: 10.1007/BF03037344

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.