×

A confluent calculus for concurrent constraint programming. (English) Zbl 0902.68034

Summary: Confluence is an important and desirable property as it allows the program to be understood by considering any desired scheduling rule, rather than having to consider all possible schedulings. Unfortunately, the usual operational semantics for concurrent constraint programs is not confluent as different process schedulings give rise to different sets of possible outcomes. We show that it is possible to give a natural confluent calculus for concurrent constraint programs, if the syntactic domain is extended by a blind choice operator and a special constant standing for a discarded branch. This has application to program analysis.

MSC:

68N99 Theory of software
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barendregt, H. P., The Lambda Calculus: its Syntax and Semantics, (Studies in Logic and the Foundations of Mathematics, Vol. 103 (1984), North-Holland: North-Holland Amsterdam) · Zbl 0467.03010
[2] Codish, M.; Falaschi, M.; Marriott, K., Suspension analyses for concurrent logic programs, ACM Trans. Programming Languages Systems, 16, 649-686 (1994)
[3] Codish, M.; Falaschi, M.; Marriott, K.; Winsborough, W., Efficient analysis of concurrent constraint logic programs, (Proc. 20th Internat. Coll. on Automata, Languages, and Programming. Proc. 20th Internat. Coll. on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 700 (1993), Springer: Springer Berlin), 633-644 · Zbl 1418.68052
[4] Codognet, C.; Codognet, P., Guarded constructive disjunction: angel or demon?, (Proc Internat. Conf. on Principles and practice of Constraint Programming, CP’95. Proc Internat. Conf. on Principles and practice of Constraint Programming, CP’95, Marseille, France. Proc Internat. Conf. on Principles and practice of Constraint Programming, CP’95. Proc Internat. Conf. on Principles and practice of Constraint Programming, CP’95, Marseille, France, Lecture Notes in Computer Science, Vol. 976 (1995), Springer: Springer Berlin), 345-361
[5] Codognet, C.; Codognet, P.; Corsini, M., Abstract interpretation for concurrent logic languages, (Proc. North American Conf. on Logic Programming (1990)), 215-232
[6] Falaschi, M.; Gabbrielli, M.; Marriott, K.; Palamidessi, C., Compositional analysis for concurrent constraint programming, (Proc. 8th IEEE Symp. on Logic in Computer Science (1993)), 210-221
[7] Falaschi, M.; Gabbrielli, M.; Marriott, K.; Palamidessi, C., Confluence and concurrent constraint programming, (Alagar, V. S.; Nivat, M., Proc. 4th Internat. Conf. on Algebraic Methodology and Software Technology (AMAST’95). Proc. 4th Internat. Conf. on Algebraic Methodology and Software Technology (AMAST’95), Montreal, Canada. Proc. 4th Internat. Conf. on Algebraic Methodology and Software Technology (AMAST’95). Proc. 4th Internat. Conf. on Algebraic Methodology and Software Technology (AMAST’95), Montreal, Canada, Lecture Notes in Computer Science, Vol. 936 (1995), Springer: Springer Berlin), 531-545 · Zbl 1496.68104
[8] Henkin, L.; Monk, J. D.; Tarski, A., Cylindric Algebras, (Studies in Logic and the Foundations of Mathematics, Vol. 64 (1971), North-Holland: North-Holland Amsterdam) · Zbl 0121.25402
[9] Huet, G., Confluent reductions: Abstract properties and applications to term rewriting systems, J. ACM, 27, 797-821 (1980) · Zbl 0458.68007
[10] lop, Jan Willem, Combinatory reduction systems, (Mathematical Centre Tracts. Mathematical Centre Tracts, Ph.D. Thesis, Vol. 127 (1980), Mathematisch Centrum: Mathematisch Centrum Kruislaan 413, 1098 SJ Amsterdam)
[11] Lloyd, J. W., Foundations of Logic Programming (1987), Springer: Springer Berlin · Zbl 0547.68005
[12] Maher, M., Logic semantics for a class of committed-choice programs, (Proc. 4th Internat. Conf. on Logic Programming (1987)), 858-876
[13] Marriott, K.; Falaschi, M.; Gabbrielli, M.; Palamidessi, C., A simple semantics for logic programming languages with delay, (Kotagiri, R., Proc. 18th Australian Computer Science Conf., Australian Computer Science Comm., 17 (1995)), 356-363
[14] Montanari, U.; Rossi, F.; Saraswat, V., CC programs with both in- and non-determinism: A concurrent semantics, (Proc. 2nd Internat. Workshop on Principles and Practice of Constraint Programming (PPCP’94). Proc. 2nd Internat. Workshop on Principles and Practice of Constraint Programming (PPCP’94), Lecture Notes in Computer Science, Vol. 874 (1994), Springer: Springer Berlin), 151-161
[15] Niehren, J., Funktionale Berechnung in einem uniform nebenläufigen Kalkül mit logischen Variablen, (Ph.D. Thesis (1994), Universität des Saarlandes) · Zbl 0931.03050
[16] Niehren, J.; Smolka, G., A confluent relational calculus for higher-order programming with constraints, (Jouannaud, J.-P., Proc. 1st Internat. Conf. on Constraints in Computational Logics. Proc. 1st Internat. Conf. on Constraints in Computational Logics, München, Germany. Proc. 1st Internat. Conf. on Constraints in Computational Logics. Proc. 1st Internat. Conf. on Constraints in Computational Logics, München, Germany, Lecture Notes in Computer Science, Vol. 845 (1994), Springer: Springer Berlin), 89-104 · Zbl 1495.68043
[17] Nyström, S.-O., Oracles and confluence — A fixpoint semantics for concurrent constraint programming, (Tech. Report 115 (1995), Computer Science Department, Uppsala University)
[18] Plotkin, G. D., Call-by-name, call-by-value, and the \(λ\)-calculus, Theoret. Comput. Sci., 1, 125-159 (1975) · Zbl 0325.68006
[19] Saraswat, V. A.; Rinard, M., Concurrent constraint programming, (Proc. 17th Ann. ACM Symp. on Principles of Programming Languages. Proc. 17th Ann. ACM Symp. on Principles of Programming Languages, San Francisco, CA (1990)), 232-245
[20] Saraswat, V.; Rinard, M.; Panangaden, P., The semantic foundations of concurrent constraint programming, (Conf. Record of the 18th Ann. ACM Symp. on Principles of Programming Languages. Conf. Record of the 18th Ann. ACM Symp. on Principles of Programming Languages, Orlando, Florida (1991), ACM Press: ACM Press New York), 333-352
[21] Zaffanella, E.; Levi, G.; Giacobazzi, R., Abstracting synchronization in concurrent constraint programming, (Proc. 5th Internat. Symp. on Programming Language Implementation and Logic Programming. Proc. 5th Internat. Symp. on Programming Language Implementation and Logic Programming, Lecture Notes in Computer Science, Vol. 844 (1994), Springer: Springer Berlin) · Zbl 0924.68045
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.