Dynamic Slicing for Concurrent Constraint Languages

• Autorzy: Falaschi Moreno , Gabbrielli Maurizio , Olarte Carlos , Palamidessi Catuscia

Identyfikatory

DOI

10.3233/FI-2020-1992

• Języki publikacji: EN

Abstrakty

EN

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 CCP-based 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.

Słowa kluczowe

EN

concurrent constraint programming; CCP; program slicing; debugging

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 177, nr 3/4
• Strony: 331--357
• Opis fizyczny: Bibliogr. 47 poz.

Twórcy

autor

Falaschi Moreno

• Dept. of Information Engineering and Mathematics, Università di Siena, Siena, Italy

autor

Gabbrielli Maurizio

• Dipartimento di Informatica - Scienza e Ingegneria, Università di Bologna, Bologna, Italy

autor

Olarte Carlos

• ECT - Escola de Ciências e Tecnologia, Universidade Federal do Rio Grande do Norte, Natal, Brazil

autor

Palamidessi Catuscia

• INRIA and LIX, École Polytechnique, Palaiseau, France

Bibliografia

• [1] Saraswat VA. Concurrent Constraint Programming. MIT Press, 1993. ISBN 9780262527996.
• [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.
• [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.
• [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.
• [6] Nielsen M, Palamidessi C, Valencia FD. Temporal Concurrent Constraint Programming: Denotation, Logic and Applications. Nord. J. Comput., 2002. 9(1):145-188.
• [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.
• [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 Constraint-Based Process Calculi. In: Koutny M, Ulidowski I (eds.), CONCUR, volume 7454 of Lecture Notes in Computer Science. Springer, 2012 pp. 317-332. doi:http://dx.doi.org/10.1007/978-3-642-32940-1_23.
• [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.
• [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.
• [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.
• [14] Shapiro EY. Algorithmic Program DeBugging. MIT Press, 1983. ISBN 9780262693073.
• [15] Weiser M. Program slicing. IEEE Trans. on Software Engineering, 1984. 10(4):352-357.
• [16] Korel B, Laski J. Dynamic Program Slicing. Inf. Process. Lett., 1988. 29(3):155-163. doi:10.1016/0020-0190(88)90054-3.
• [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.
• [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.
• [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.
• [21] Falaschi M, Gabbrielli M, Olarte C, Palamidessi C. Slicing Concurrent Constraint Programs. In: Hermenegildo MV, López-García P (eds.), Proc. of LOPSTR 2016, volume 10184 of Lecture Notes in Computer Science. Springer, 2017 pp. 76-93. doi:https://doi.org/10.1007/978-3-319-63139-4_5.
• [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.
• [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.
• [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 of Lecture Notes in Computer Science. Springer, 1994 pp. 50-72. doi:http://dx.doi.org/10.1007/BFb0016844.
• [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.
• [28] Ruet P, Fages F. Concurrent Constraint Programming and Non-commutative Logic. In: Nielsen M, Thomas W (eds.), Proceedings of CSL’97, volume 1414 of Lecture Notes in Computer Science. Springer, 1998 pp. 406-423. doi:10.1007/BFb0028028.
• [29] Berry G, Gonthier G. The ESTEREL Synchronous 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.
• [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.
• [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.
• [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.
• [34] Chemillier M. Les Mathématiques 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án 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.
• [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 of Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2019 pp. 148-165. doi:https://doi.org/10.1007/978-3-030-13838-7_9.
• [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.
• [39] Falaschi M, Olarte C, Palamidessi C, Valencia F. Declarative Diagnosis of Temporal Concurrent Constraint Programs. In: Dahl V, Niemelä I (eds.), Proc. of ICLP 2007, volume 4670 of Lecture Notes in Computer Science. Springer, 2007 pp. 271-285. doi:https://doi.org/10.1007/978-3-540-74610-2_19.
• [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.
• [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 of Lecture Notes in Computer Science. Springer, 2015 pp.179-200. doi:https://doi.org/10.1007/978-3-319-27436-2_11.
• [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 of Lecture 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.
• [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.
• [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.
• [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 of Lecture Notes in Computer Science. Springer, 2017 pp. 62-75. doi:https://doi.org/10.1007/978-3-319-51963-0_6.
• [47] Brodo L. On the expressiveness of π-calculus for encoding mobile ambients. Math. Struct. Comput. Sci., 2018. 28(2):202-240. doi:https://doi.org/10.1017/S0960129516000256.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).