Logical operational semantics of Parlog part I: And-Parallelism

Abstract

We provide a complete mathematical semantics for the parallel logic programming language PARLOG.This semantics is abstract but nevertheless simple and supports the intuitive operational understanding of programs. It is based on Gurevich's notion of Evolving Algebras ([8]) and is obtained adapting ideas from the OCCAM formalization in [11] and from the Evolving Algebras semantics of full PROLOG in [1]. The first part gives an explicit formalization of the AND-Parallelism in PARLOG, leaving the (orthogonal) OR-Parallelism abstract. Thereby our description can be easily modified for other parallel logic programming languages, too.

In a sequel to this paper the OR-Parallelism is also made explicit by a natural extension of the PARLOG Algebras developed here and the correctness of this extension will be proved.

Part of this work was done when the first author was guest scientist at the Scientific Center of IBM Germany GmbH in Heidelberg, on sabbatical from University of Pisa, and when the second author from July 1990 till November 1990 worked at the Institut für Logik, Komplexität und Deduktionssysteme of University of Karlsruhe (Germany). The second author has been partially supported by ”Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo” of CNR, under Grant n.90.00671.69.