A formal specification of PARLOG
Egon Börger, Elvinia Riccobene · 1993
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 ([20]) and is obtained adapting ideas from the description of full (Sequential) Standard PROLOG in [5] and the specification of imperative parallel computation phenomena of OCCAM developed in [24]. We develope a complete specification of the core of PARLOG which governs the computation of goals by user defined predicates. The built-in predicates can be described as for Standard PROLOG (see [4]-[6]) and are therefore omitted here. We give an explicit formalization of the two kinds of parallelism occurring in PARLOG: the AND-Parallelism and the (orthogonal) OR-Parallelism. Our description uses an abstract notion of PARLOG terms and PARLOG substitutions which is unburdened by representation details and implementation constraints.