×

zbMATH — the first resource for mathematics

Efficient analysis of concurrent constraint logic programs. (English) Zbl 1418.68052
Lingas, Andrzej (ed.) et al., Automata, languages and programming. 20th international colloquium, ICALP 93, Lund, Sweden, July 5–9, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 700, 633-644 (1993).
Summary: The standard operational semantics of concurrent constraint logic languages is not confluent in the sense that different schedulings of processes may result in different program behaviors. While implementations are free to choose specific scheduling policies, analyses should be correct for all implementations. Moreover, in the presence of parallelism it is usually not possible to determine how processes will actually be scheduled. Efficient program analysis is therefore difficult as all process schedulings must be considered. To overcome this problem we introduce a confluent semantics which closely approximates the standard (non-confluent) semantics. This semantics provides a basis for efficient and accurate program analysis for these languages. To illustrate the usefulness of this approach we sketch analyses based on abstract interpretations of the confluent semantics which determine if a program is suspension and local suspension free.
For the entire collection see [Zbl 0814.00020].

MSC:
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68N17 Logic programming
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68Q55 Semantics in the theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S.D. Brookes and A.W. Roscoe. Deadlock Analysis in Networks of Communicating Processes. \(Distributed Computing\), 4:209-230, 1991. · Zbl 0717.68006
[2] K.M. Chandy and J. Misra. Deadlock Absence Proofs for Networks of Communicating Processes. \(Information Proc. Letters\), 9(4):185, 1979. · Zbl 0456.68030
[3] M. Codish, M. Falaschi, and K. Marriott. Suspension Analyses for Concurrent Logic Programs. \(ACM Transactions on Programming Languages and Systems\), 1993. To appear.
[4] C. Codognet, P. Codognet, and M. Corsini. Abstract Interpretation for Concurrent Logic Languages. In S. Debray and M. Hermenegildo, editors, \(Proc. North American Conf. on Logic Programming'90\), pages 215-232. The MIT Press, Cambridge, Mass., 1990.
[5] P. Cousot and R. Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In \(Proc. Fourth ACM Symp. Principles of Programming Languages\), pages 238-252, 1977.
[6] C.A.R. Hoare. \(Communicating Sequential Processes\). Prentice-Hall, 1985. · Zbl 0637.68007
[7] J.-L. Lassez and M. J. Maher. Closures and Fairness in the Semantics of Programming Logic. \(Theoretical Computer Science\), 29:167-184, 1984. · Zbl 0547.68034
[8] J. W. Lloyd. \(Foundations of Logic Programming\). Springer-Verlag, Berlin, 1987. Second edition. · Zbl 0668.68004
[9] R. Milner. \(Communication and Concurrency\). Prentice-Hall Int. (UK), 1989.
[10] W. Peng and S. Purushothaman. Data flow analysis of communicating finite state machines. \(ACM Transactions on Programming Languages and Systems\), 13(2):399-442, 1991.
[11] V. Saraswat, M. Rinard, and P. Panangaden. Semantic Foundation of Concurrent Constraint Programming. In \(Proc. Eighteenth Annual ACM Symp. on Principles of Programming Languages\), 1991.
[12] V. A. Saraswat. \(Concurrent Constraint Programming Languages\). PhD thesis, Carnegie-Mellon University, January 1989. Also in \(ACM Distinguished Dissertation Series\).
[13] E. Y. Shapiro. The family of concurrent logic programming languages. \(ACM Computing Surveys\), 21(3):412-510, 1989.
[14] R. Yang and H. Aiso. P-Prolog: a parallel language based on exclusive relation. In E. Y. Shapiro, editor, \(Proc. Third Int'l Conf. on Logic Programming\), volume 225 of \(LNCS\), pages 255-269. Springer-Verlag, Berlin, 1986. · Zbl 0595.68010
[15] K. Yelick and J.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.