zbMATH — the first resource for mathematics

Abstracting synchronization in concurrent constraint programming. (English) Zbl 0924.68045
Summary: Because of synchronization based on blocking ask, some of the most important techniques for data-flow analysis of (sequential) constraint logic programs (clp) are no longer applicable to cc languages. In particular, the generalized approach to the semantics, intended to factorize the (standard) semantics so as to make explicit the domain-dependent features (i.e., operators and semantic objects that may be influenced by abstraction) becomes useless for relevant applications. In the case of clp programs, abstract interpretation of a program P is obtained by evaluating an abstract program \(\alpha(P)\) into an instance of clp itself, provided with a suitable abstract constraint system. In cc programs, a correct characterization of suspended computations can only be obtained by replacing ask constraints with stronger constraints, which is not the case in abstract interpretation, where abstraction is usually a weakening of constraints. A possible solution to this problem is based on a more abstract (nonstandard) semantics: the success semantics, which models nonsuspended computations only. With a program transformation (NoSynch) that simply ignores synchronization, we obtain a clplike program that allows us to apply standard techniques for data-flow analysis. For suspension-free programs, the success semantics is equivalent to the standard semantics, thus justifying the use of suspension analysis to generate sound approximations. A second transformation (Angel) is introduced, applying a different abstraction of synchronization in possibly suspending programs. The resulting abstraction is adequate to suspension analysis. Applicability and accuracy of these solutions are investigated.

68N17 Logic programming
Full Text: Link