×

Dynamic slicing for concurrent constraint languages. (English) Zbl 1497.68098

Summary: Concurrent Constraint Programming (CCP) is a declarative model for concurrency where agents interact by telling and asking constraints (pieces of information) in a shared store. Some previous works have developed (approximated) declarative debuggers for CCP languages. However, the task of debugging concurrent programs remains difficult. In this paper we define a dynamic slicer for CCP (and other language variants) and we show it to be a useful companion tool for the existing debugging techniques. We start with a partial computation (a trace) that shows the presence of bugs. Often, the quantity of information in such a trace is overwhelming, and the user gets easily lost, since she cannot focus on the sources of the bugs. Our slicer allows for marking part of the state of the computation and assists the user to eliminate most of the redundant information in order to highlight the errors. We show that this technique can be tailored to several variants of CCP, such as the timed language ntcc, linear CCP (an extension of CCPbased on linear logic where constraints can be consumed) and some extensions of CCP dealing with epistemic and spatial information. We also develop a prototypical implementation freely available for making experiments.

MSC:

68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Software:

Alcove
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Saraswat VA. Concurrent Constraint Programming. MIT Press, 1993. ISBN 9780262527996. · Zbl 1002.68026
[2] Saraswat VA, Rinard MC, Panangaden P. Semantic Foundations of Concurrent Constraint Programming. In: Wise DS (ed.), POPL ’91: Proceedings of the 18th ACM Symposium on Principles of programming languages. 1991 pp. 333-352. doi:http://doi.acm.org/10.1145/99583.99627.
[3] Olarte C, Rueda C, Valencia FD. Models and emerging trends of concurrent constraint programming. Constraints, 2013.18(4):535-578. doi:https://doi.org/10.1007/s10601-013-9145-3. · Zbl 1317.90283
[4] Bortolussi L, Policriti A. Modeling Biological Systems in Stochastic Concurrent Constraint Programming. Constraints, 2008.13(1-2):66-90. doi:http://dx.doi.org/10.1007/s10601-007-9034-8. · Zbl 1144.92001
[5] Saraswat VA, Jagadeesan R, Gupta V. Timed Default Concurrent Constraint Programming.J. Symb. Comput., 1996.22(5/6):475-520. doi:10.1006/jsco.1996.0064. · Zbl 0876.68041
[6] Nielsen M, Palamidessi C, Valencia FD. Temporal Concurrent Constraint Programming: Denotation, Logic and Applications.Nord. J. Comput., 2002.9(1):145-188. · Zbl 1018.68019
[7] de Boer FS, Gabbrielli M, Meo MC. A Timed Concurrent Constraint Language.Inf. Comput., 2000. 161(1):45-83. doi:http://dx.doi.org/10.1006/inco.1999.2879. · Zbl 1046.68507
[8] Olarte C, Valencia FD.Universal concurrent constraint programming: symbolic semantics and applications to security.In: Wainwright RL, Haddad H (eds.), Proceedings of the 2008 ACM Symposium on Applied Computing (SAC). ACM.ISBN 978-1-59593-753-7, 2008 pp. 145-150.doi: http://doi.acm.org/10.1145/1363686.1363726.
[9] Knight S, Palamidessi C, Panangaden P, Valencia FD. Spatial and Epistemic Modalities in ConstraintBased Process Calculi. In: Koutny M, Ulidowski I (eds.), CONCUR, volume 7454 ofLecture Notes in Computer Science. Springer, 2012 pp. 317-332. doi:http://dx.doi.org/10.1007/978-3-642-32940-1 23. · Zbl 1364.68290
[10] Olarte C, Pimentel E, Nigam V. Subexponential concurrent constraint programming.Theor. Comput. Sci., 2015.606:98-120. doi:10.1016/j.tcs.2015.06.031. · Zbl 1332.68027
[11] Codish M, Falaschi M, Marriott K. Suspension Analyses for Concurrent Logic Programs.ACM Transactions on Programming Languages and Systems, 1994.16(3):649-686. doi:https://doi.org/10.1145/177492. 177656.
[12] Comini M, Titolo L, Villanueva A.Abstract Diagnosis for Timed Concurrent Constraint programs. Theory and Practice of Logic Programming, 2011.11(4-5):487-502.doi:https://doi.org/10.1017/ S1471068411000135. · Zbl 1222.68053
[13] Falaschi M, Olarte C, Palamidessi C. Abstract interpretation of temporal concurrent constraint programs. Theory and Practice of Logic Programming, 2015.15(3):312-357. doi:10.1017/S1471068413000641. · Zbl 1379.68060
[14] Shapiro EY. Algorithmic Program DeBugging. MIT Press, 1983. ISBN 9780262693073. · Zbl 0589.68003
[15] Weiser M. Program slicing.IEEE Trans. on Software Engineering, 1984.10(4):352-357. · Zbl 0552.68004
[16] Korel B, Laski J. Dynamic Program Slicing.Inf. Process. Lett., 1988.29(3):155-163. doi:10.1016/ 0020-0190(88)90054-3. · Zbl 0656.68018
[17] Ochoa C, Silva J, Vidal G. Dynamic Slicing of Lazy Functional Programs Based on Redex Trails.Higher Order Symbol. Comput., 2008.21(1-2):147-192. doi:10.1007/s10990-008-9023-7. · Zbl 1192.68139
[18] Alpuente M, Ballis D, Espert J, Romero D. Backward Trace Slicing for Rewriting Logic Theories. In: Proc. of CADE’11. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-642-22437-9, 2011 pp. 34-48. doi: https://doi.org/10.1007/978-3-642-22438-6 5. · Zbl 1341.68026
[19] Alpuente M, Ballis D, Frechina F, Romero D. Using Conditional Trace Slicing for Improving Maude Programs.Sci. Comput. Program., 2014.80:385-415. doi:10.1016/j.scico.2013.09.018.
[20] Josep S. A Vocabulary of Program Slicing-based Techniques.ACM Comput. Surv., 2012.44(3):12:1- 12:41. doi:https://doi.org/10.1145/2187671.2187674. · Zbl 1293.68081
[21] Falaschi M, Gabbrielli M, Olarte C, Palamidessi C.Slicing Concurrent Constraint Programs.In: Hermenegildo MV, L´opez-Garc´ıa P (eds.), Proc. of LOPSTR 2016, volume 10184 ofLecture Notes in Computer Science. Springer, 2017 pp. 76-93. doi:https://doi.org/10.1007/978-3-319-63139-4 5. · Zbl 1485.68046
[22] de Boer FS, Pierro AD, Palamidessi C. Nondeterminism and Infinite Computations in Constraint Programming.Theoretical Computer Science, 1995.151(1):37-78. doi:http://dx.doi.org/10.1016/0304-3975(95) 00047-Z. · Zbl 0872.68103
[23] Hentenryck PV, Saraswat VA, Deville Y. Design, Implementation, and Evaluation of the Constraint Language cc(FD).J. Log. Program., 1998.37(1-3):139-164. · Zbl 0920.68026
[24] Saraswat VA. The Category of Constraint Systems is Cartesian-Closed. In: Proceedings of the 7th Annual Symposium on Logic in Computer Science (LICS ’92). IEEE Computer Society, 1992 pp. 341-345. doi: 10.1109/LICS.1992.185546.
[25] Smolka G. A Foundation for Higher-order Concurrent Constraint Programming. In: Jouannaud J (ed.), Proceedings of Constraints in Computational Logics, volume 845 ofLecture Notes in Computer Science. Springer, 1994 pp. 50-72. doi:http://dx.doi.org/10.1007/BFb0016844. · Zbl 1495.68044
[26] Girard J. Linear Logic.Theor. Comput. Sci., 1987.50:1-102. doi:http://dx.doi.org/10.1016/0304-3975(87) 90045-4.
[27] Fages F, Ruet P, Soliman S. Linear Concurrent Constraint Programming: Operational and Phase Semantics.Inf. Comput., 2001.165(1):14-41. · Zbl 1003.68065
[28] Ruet P, Fages F. Concurrent Constraint Programming and Non-commutative Logic. In: Nielsen M, Thomas W (eds.), Proceedings of CSL’97, volume 1414 ofLecture Notes in Computer Science. Springer, 1998 pp. 406-423. doi:10.1007/BFb0028028. · Zbl 0908.03033
[29] Berry G, Gonthier G. The ESTERELSynchronous Programming Language: Design, Semantics, Implementation.Science of Computer Programming, 1992.19(2):87-152. doi:https://doi.org/10.1016/ 0167-6423(92)90005-V. · Zbl 0772.68013
[30] Saraswat VA, Jagadeesan R, Gupta V. Foundations of Timed Concurrent Constraint Programming. In: Proceedings of the 9th Annual Symposium on Logic in Computer Science (LICS ’94. IEEE Computer Society, 1994 pp. 71-80. doi:10.1109/LICS.1994.316085. · Zbl 0942.68539
[31] Nielsen M, Palamidessi C, Valencia FD. On the expressive power of temporal concurrent constraint program. languages. In: Proc. of PPDP’02. ACM, 2002 pp. 156-167. doi:10.1145/571157.571173.
[32] Olarte C, Pimentel E. On concurrent behaviors and focusing in linear logic.Theor. Comput. Sci., 2017. 685:46-64. doi:10.1016/j.tcs.2016.08.026. · Zbl 1371.68197
[33] Olarte C, Pimentel E, Rueda C. A concurrent constraint programming interpretation of access permissions. Theory and Practice of Logic Programming, 2018.18(2):252-295. doi:10.1017/S1471068418000017. · Zbl 1478.68056
[34] Chemillier M. Les Math´ematiques Naturelles. Odile Jacob, 2007.
[35] Olarte C, Rueda C, Sarria G, Toro M, Valencia FD. Concurrent Constraints Models of Music Interaction. In: Assayag G, Truchet C (eds.), Constraint Programming in Music, pp. 133-153. Wiley, 2011.
[36] Guzm´an M, Haar S, Perchy S, Rueda C, Valencia FD. Belief, knowledge, lies and other utterances in an algebra for space and extrusion.J. Log. Algebr. Meth. Program., 2017.86(1):107-133. doi:10.1016/j. jlamp.2016.09.001. · Zbl 1353.68203
[37] Falaschi M, Olarte C. An assertion language for slicing Constraint Logic Languages. In: Mesnard F, Stuckey P (eds.), Proceedings of LOPSTR’2018, volume 11408 ofLecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2019 pp. 148-165. doi:https://doi.org/10.1007/978-3-030-13838-7 9. · Zbl 1524.68064
[38] Jaffar J, Maher MJ, Marriott K, Stuckey PJ. The Semantics of Constraint Logic Programs.J. Log. Program., 1998.37(1-3):1-46. doi:https://doi.org/10.1016/S0743-1066(98)10002-X. · Zbl 0920.68068
[39] Falaschi M, Olarte C, Palamidessi C, Valencia F. Declarative Diagnosis of Temporal Concurrent Constraint Programs. In: Dahl V, Niemel¨a I (eds.), Proc. of ICLP 2007, volume 4670 ofLecture Notes in Computer Science. Springer, 2007 pp. 271-285. doi:https://doi.org/10.1007/978-3-540-74610-2 19. · Zbl 1213.68204
[40] Bodei C, Brodo L, Gori R, Levi F, Bernini A, Hermith D. A static analysis for Brane Calculi providing global occurrence counting information.Theoretical Computer Science, 2017.696:11-51. doi:https: //doi.org/10.1016/j.tcs.2017.07.008. · Zbl 1383.92032
[41] Bodei C, Brodo L, Gori R, Hermith D, Levi F. A Global Occurrence Counting Analysis for Brane Calculi. In: Proc. of LOPSTR 2015, volume 9527 ofLecture Notes in Computer Science. Springer, 2015 pp. 179-200. doi:https://doi.org/10.1007/978-3-319-27436-2 11. · Zbl 1417.68118
[42] Bodei C, Brodo L, Focardi R. Static Evidences for Attack Reconstruction. In: Proc. of Programming Languages with Applications to Biology and Security, volume 9465 ofLecture Notes in Computer Science. Springer, 2015 pp. 162-182. doi:http://doi-org-443.webvpn.fjmu.edu.cn/10.1007/978-3-319-25527-9 12. · Zbl 1437.94051
[43] Olarte C, Chiarugi D, Falaschi M, Hermith D. A proof theoretic view of spatial and temporal dependencies in biochemical systems.Theor. Comput. Sci., 2016.641:25-42. doi:https://doi.org/10.1016/j.tcs.2016.03. 029. · Zbl 1344.68140
[44] Chiarugi D, Falaschi M, Hermith D, Olarte C, Torella L. Modelling non-Markovian dynamics in biochemical reactions.BMC Systems Biology, 2015.9(S-3):S8. doi:https://doi.org/10.1186/1752-0509-9-S3-S8. · Zbl 1351.68157
[45] Bernini A, Brodo L, Degano P, Falaschi M, Hermith D. Process calculi for biological processes.Natural Computing, 2018.17(2):345-373. doi:https://doi.org/10.1007/s11047-018-9673-2.
[46] Brodo L, Olarte C. Symbolic Semantics for Multiparty Interactions in the Link-Calculus. In: Steffen B, Baier C, van den Brand M, Eder J, Hinchey M, Margaria T (eds.), Proc. of SOFSEM 2017, volume 10139 ofLecture Notes in Computer Science. Springer, 2017 pp. 62-75. doi:https://doi.org/10.1007/ 978-3-319-51963-0 6. · Zbl 1433.68241
[47] Brodo L.
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.