Program transformation for efficient derivation of multiple solutions in concurrent logic languages

Candidate: Markantonatos,Nikolaos

Abstract

Concurrent logic languages provide a flexible and powerful vehicle for expressing parallel programs using explicit processes. However, their drastic departure from conventional logic programming with respect to completeness renders them unsuitable for a variety of useful applications involving search. A multiple solution extension to concurrent logic languages appears to successfully obtain the effect of backtracking in a parallel environment, but has been impeded by inefficiency problems. Moreover, the multiple solution subset introduces a new language which is incoherent with the single solution base language. We propose a multiple solution subset definition that adheres to the base language both syntactically and semantically. Subsequently, we advocate a source-to-source transformational approach for the efficient implementation of the subset. Multiple solution programs are converted at compile-time into equivalent single solution programs that derive all possible solutions into a single list. Alternative solutions are obtained in an eager or lazy fashion as specified by the program. A number of multiple solution program classes that are transformable into efficient single solution programs are identified and the corresponding transformation procedures are presented and further illustrated using a variety of examples. The techniques employed for the various transformations include partial evaluation, abstract interpretation, continuation-based transformation, layered stream transformation and loop fusion. As a result of such a static transformational methodology, a broad range of multiple solution programs enjoy efficient execution. We believe that our approach forms a definite step towards an efficient multiple solution subset for concurrent logic languages.