Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-27T20:25:39.873Z Has data issue: false hasContentIssue false
  • English
  • Français

Symbolic Specialization of Rewriting Logic Theories with Presto

Published online by Cambridge University Press:  11 February 2022

MARÍA ALPUENTE Open the ORCID record for MARÍA ALPUENTE [Opens in a new window] ,
SANTIAGO ESCOBAR ,
JULIA SAPIÑA Open the ORCID record for JULIA SAPIÑA [Opens in a new window]  and
DEMIS BALLIS
MARÍA ALPUENTE
Affiliation:
VRAIN (Valencian Research Institute for Artificial Intelligence), Universitat Politècnica de València (e-mails: [email protected], [email protected], [email protected])
SANTIAGO ESCOBAR
Affiliation:
VRAIN (Valencian Research Institute for Artificial Intelligence), Universitat Politècnica de València (e-mails: [email protected], [email protected], [email protected])
JULIA SAPIÑA
Affiliation:
VRAIN (Valencian Research Institute for Artificial Intelligence), Universitat Politècnica de València (e-mails: [email protected], [email protected], [email protected])
DEMIS BALLIS
Affiliation:
DMIF, University of Udine (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper introduces $\tt{{Presto}}$ , a symbolic partial evaluator for Maude’s rewriting logic theories that can improve system analysis and verification. In $\tt{{Presto}}$ , the automated optimization of a conditional rewrite theory $\mathcal{R}$ (whose rules define the concurrent transitions of a system) is achieved by partially evaluating, with respect to the rules of $\mathcal{R}$ , an underlying, companion equational logic theory $\mathcal{E}$ that specifies the algebraic structure of the system states of $\mathcal{R}$ . This can be particularly useful for specializing an overly general equational theory $\mathcal{E}$ whose operators may obey complex combinations of associativity, commutativity, and/or identity axioms, when being plugged into a host rewrite theory $\mathcal{R}$ as happens, for instance, in protocol analysis, where sophisticated equational theories for cryptography are used. $\tt{{Presto}}$ implements different unfolding operators that are based on folding variant narrowing (the symbolic engine of Maude’s equational theories). When combined with an appropriate abstraction algorithm, they allow the specialization to be adapted to the theory termination behavior and bring significant improvement while ensuring strong correctness and termination of the specialization. We demonstrate the effectiveness of $\tt{{Presto}}$ in several examples of protocol analysis where it achieves a significant speed-up. Actually, the transformation provided by $\tt{{Presto}}$ may cut down an infinite folding variant narrowing space to a finite one, and moreover, some of the costly algebraic axioms and rule conditions may be eliminated as well. As far as we know, this is the first partial evaluator for Maude that respects the semantics of functional, logic, concurrent, and object-oriented computations.

Keywords

multi-paradigm declarative programmingpartial evaluationrewriting logicnarrowing
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 22 , Issue 3 , May 2022 , pp. 444 - 495
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This research was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215, grant RTI2018-094403-B-C32 funded by MCIN/AEI/10.13039/501100011033 and by ”ERDF A way of making Europe”, and by Generalitat Valenciana under grant PROMETEO/2019/098. Julia Sapiña has been supported by the Generalitat Valenciana APOSTD/2019/127 grant.

References

Aguirre, L., Martí-Oliet, N., Palomino, M., and Pita, I. (2014). Conditional Narrowing Modulo in Rewriting Logic and Maude. In Proceedings of the 10th International Workshop on Rewriting Logic and its Applications (WRLA 2014), volume 8663 of Lecture Notes in Computer Science, pages 80–96. Springer.CrossRefGoogle Scholar
Albert, E., Alpuente, M., Falaschi, M., and Vidal, G. (1998). Indy User’s Manual. Technical Report DSIC-II/12/98, Department of Computer Systems and Computation, Universitat Politècnica de València.Google Scholar
Albert, E., Alpuente, M., Hanus, M., and Vidal, G. (1999). A Partial Evaluation Framework for Curry Programs. In Proceedings of the 6th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR 1999), volume 1705 of Lecture Notes in Computer Science, pages 376–395. Springer.CrossRefGoogle Scholar
Albert, E., Gallagher, J. P., Gómez-Zamalloa, M., and Puebla, G. (2009). Type-based Homeomorphic Embedding for Online Termination. Information Processing Letters, 109(15):879–886.CrossRefGoogle Scholar
Albert, E., Hanus, M., and Vidal, G. (2002). A Practical Partial Evaluation Scheme for Multi-Paradigm Declarative Languages. Journal of Functional and Logic Programming, 2002:1–34.Google Scholar
Alpuente, M., Ballis, D., Cuenca-Ortega, A., Escobar, S., and Meseguer, J. (2019a). ACUOS2: A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance. In Proceedings of the 16th European Conference on Logics in Artificial Intelligence (JELIA 2019), volume 11468 of Lecture Notes in Computer Science, pages 171–181. Springer.CrossRefGoogle Scholar
Alpuente, M., Ballis, D., Escobar, S., Meseguer, J., and Sapiña, J. (2021a). Optimizing Maude Programs via Program Specialization. In Gallagher, J. P., Giacobazzi, R. , and López-Garca, P., editors, Festschrift volume in honor of Manuel Hermenegildo (submitted, invited contribution). Elsevier Science. Available at: http://elp.webs.upv.es/papers/ABEMS20-Festschrift.pdf.Google Scholar
Alpuente, M., Ballis, D., Escobar, S., and Sapiña, J. (2019b). Symbolic Analysis of Maude Theories with Narval. Theory and Practice of Logic Programming, 19(5–6):874–890.CrossRefGoogle Scholar
Alpuente, M., Ballis, D., Escobar, S., and Sapiña, J. (2022). Optimization of Rewrite Theories by Equational Partial Evaluation. Journal of Logical and Algebraic Methods in Programming, 124.Google Scholar
Alpuente, M., Ballis, D., Frechina, F., and Romero, D. (2012). Backward Trace Slicing for Conditional Rewrite Theories. In Proceedings of the 18th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR 2012), volume 7180 of Lecture Notes in Computer Science, pages 62–76. Springer.CrossRefGoogle Scholar
Alpuente, M., Ballis, D., Frechina, F., and Sapiña, J. (2016). Debugging Maude Programs via Runtime Assertion Checking and Trace Slicing. Journal of Logical and Algebraic Methods in Programming, 85:707–736.CrossRefGoogle Scholar
Alpuente, M., Ballis, D., and Romero, D. (2014a). A Rewriting Logic Approach to the Formal Specification and Verification of Web Applications. Science of Computer Programming, 81:79–107.CrossRefGoogle Scholar
Alpuente, M., Ballis, D., and Sapiña, J. (2019c). Static Correction of Maude Programs with Assertions. Journal of Systems and Software, 153:64–85.CrossRefGoogle Scholar
Alpuente, M., Ballis, D., and Sapiña, J. (2020a). Efficient Safety Enforcement for Maude Programs via Program Specialization in the ÁTAME system. Mathematics in Computer Science, 14(3):591–606.CrossRefGoogle Scholar
Alpuente, M., Comini, M., Escobar, S., Iborra, J., and Falaschi, M. (2010). A Compact Fixpoint Semantics for Term Rewriting Systems. Theoretical Computer Science, 411(37):3348–3371.CrossRefGoogle Scholar
Alpuente, M., Cuenca-Ortega, A., Escobar, S., and Meseguer, J. (2020b). A Partial Evaluation Framework for Order-Sorted Equational Programs modulo Axioms. Journal of Logical and Algebraic Methods in Programming, 110:1–36.CrossRefGoogle Scholar
Alpuente, M., Cuenca-Ortega, A., Escobar, S., and Meseguer, J. (2020c). Order-sorted Homeomorphic Embedding modulo Combinations of Associativity and/or Commutativity Axioms. Fundamenta Informaticae, 177(3–4):297–329.CrossRefGoogle Scholar
Alpuente, M., Escobar, S., Espert, J., and Meseguer, J. (2014b). A Modular Order-Sorted Equational Generalization Algorithm. Information and Computation, 235:98–136.CrossRefGoogle Scholar
Alpuente, M., Escobar, S., and Iborra, J. (2009a). Termination of Narrowing Revisited. Theoretical Computer Science, 410(46):4608–4625.CrossRefGoogle Scholar
Alpuente, M., Escobar, S., Meseguer, J., and Ojeda, P. (2008). A Modular Equational Generalization Algorithm. In Proceedings of the 18th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2008), volume 5438 of Lecture Notes in Computer Science, pages 24–39. Springer.Google Scholar
Alpuente, M., Escobar, S., Meseguer, J., and Ojeda, P. (2009b). Order-Sorted Generalization. Electronic Notes in Theoretical Computer Science, 246:27–38.CrossRefGoogle Scholar
Alpuente, M., Escobar, S., Meseguer, J., and Sapiña, J. (2021b). Order-sorted Equational Generalization Algorithm Revisited. Annals of Mathematics and Artificial Intelligence.CrossRefGoogle Scholar
Alpuente, M., Falaschi, M., Julián, P., and Vidal, G. (1997). Specialization of Lazy Functional Logic Programs. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 1997), pages 151–162. Association for Computing Machinery.CrossRefGoogle Scholar
Alpuente, M., Falaschi, M., and Vidal, G. (1998a). A Unifying View of Functional and Logic Program Specialization. ACM Computing Surveys, 30(3es):9es.CrossRefGoogle Scholar
Alpuente, M., Falaschi, M., and Vidal, G. (1998b). Partial Evaluation of Functional Logic Programs. ACM Transactions on Programming Languages and Systems, 20(4):768–844.CrossRefGoogle Scholar
Alpuente, M., Lucas, S., Hanus, M., and Vidal, G. (2005). Specialization of Functional Logic Programs based on Needed Narrowing. Theory and Practice of Logic Programming, 5(3):273–303.CrossRefGoogle Scholar
Bae, K., Escobar, S., and Meseguer, J. (2013). Abstract Logical Model Checking of Infinite-State Systems Using Narrowing. In Proceedings of the 24th International Conference on Rewriting Techniques and Applications (RTA 2013), volume 21 of Leibniz International Proceedings in Informatics (LIPIcs), pages 81–96. Schloss Dagstuhl - Leibniz-Zentrum fÜr Informatik.Google Scholar
Bae, K. and Meseguer, J. (2015). Model Checking Linear Temporal Logic of Rewriting Formulas under Localized Fairness. Science of Computer Programming, 99:193–234.CrossRefGoogle Scholar
Bouchard, C., Gero, K. A., Lynch, C., and Narendran, P. (2013). On Forward Closure and the Finite Variant Property. In Proceedings of the 9th International Symposium on Frontiers of Combining Systems (FroCos 2013), volume 8152 of Lecture Notes in Computer Science, pages 327–342. Springer.CrossRefGoogle Scholar
Burstall, R. M. and Darlington, J. (1977). A Transformation System for Developing Recursive Programs. Journal of the ACM, 24(1):44–67.CrossRefGoogle Scholar
Cadar, C. and Sen, K. (2013). Symbolic Execution for Software Testing: Three Decades Later. Communications of the ACM, 56(2):82–90.CrossRefGoogle Scholar
Clavel, M., Durán, F., Eker, S., Escobar, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., Rubio, R., and Talcott, C. (2020). Maude Manual (Version 3.0). Technical report, SRI International Computer Science Laboratory. Available at: http://maude.cs.uiuc.edu.Google Scholar
Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., and Talcott, C. (2007). All About Maude: A High-Performance Logical Framework. Springer.Google Scholar
Cook, W. R. and Lämmel, R. (2011). Tutorial on Online Partial Evaluation. In Proceedings of the IFIP Working Conference on Domain-Specific Languages (DSL 2011), volume 66 of Electronic Proceedings in Theoretical Computer Science, pages 168–180. Open Publishing Association.CrossRefGoogle Scholar
Cousot, P. and Cousot, R. (1977). Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proceedings of the 4th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 1977), pages 238–252. Association for Computing Machinery.CrossRefGoogle Scholar
De Schreye, D., GlÜck, R., Jørgensen, J., Leuschel, M., Martens, B., and SØrensen, M. H. (1999). Conjunctive Partial Deduction: Foundations, Control, Algorithms, and Experiments. The Journal of Logic Programming, 41(2-3):231–277.CrossRefGoogle Scholar
de Waal, D. A. and Gallagher, J. P. (1994). The Applicability of Logic Program Analysis and Transformation to Theorem Proving. In Proceedings of the 12th International Conference on Automated Deduction (CADE 1994), volume 814 of Lecture Notes in Computer Science, pages 207–221. Springer.CrossRefGoogle Scholar
Durán, F., Eker, S., Escobar, S., Martí-Oliet, N., Meseguer, J., Rubio, R., and Talcott, C. (2020a). Programming and Symbolic Computation in Maude. Journal of Logical and Algebraic Methods in Programming, 110.Google Scholar
Durán, F., Lucas, S., and Meseguer, J. (2008). MTT: The Maude Termination Tool (System Description). In Proceedings of the 4th International Joint Conference on Automated Reasoning (IJCAR 2008), volume 5195 of Lecture Notes in Computer Science, pages 313–319. Springer.CrossRefGoogle Scholar
Durán, F., Meseguer, J., and Rocha, C. (2020b). Ground Confluence of Order-Sorted Conditional Specifications Modulo Axioms. Journal of Logical and Algebraic Methods in Programming, 111:100513.CrossRefGoogle Scholar
Escobar, S. (2014). Functional Logic Programming in Maude. In Specification, Algebra, and Software - Essays Dedicated to Kokichi Futatsugi (SAS 2014), volume 8373 of Lecture Notes in Computer Science, pages 315–336. Springer.CrossRefGoogle Scholar
Escobar, S., Meadows, C., and Meseguer, J. (2009). Maude-NPA: Cryptographic Protocol Analysis Modulo Equational Properties. In Foundations of Security Analysis and Design V (FOSAD 2007/2008/2009 Tutorial Lectures), volume 5705 of Lecture Notes in Computer Science, pages 1–50. Springer.CrossRefGoogle Scholar
Escobar, S. and Meseguer, J. (2007). Symbolic Model Checking of Infinite-State Systems Using Narrowing. In Proceedings of the 18th International Conference on Term Rewriting and Applications (RTA 2007), volume 4533 of Lecture Notes in Computer Science, pages 153–168. Springer.CrossRefGoogle Scholar
Escobar, S., Sasse, R., and Meseguer, J. (2012). Folding Variant Narrowing and Optimal Variant Termination. The Journal of Logic and Algebraic Programming, 81(7–8):898–928.CrossRefGoogle Scholar
Fay, M. (1979). First Order Unification in an Equational Theory. In Proceedings of the 4th International Conference on Automated Deduction (CADE 1979), pages 161–167. Academic Press, Inc.Google Scholar
Gallagher, J. P. (1993). Tutorial on Specialisation of Logic Programs. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 1993), pages 88–98. Association for Computing Machinery.CrossRefGoogle Scholar
Gallagher, J. P. and Bruynooghe, M. (1990). The Derivation of an Algorithm for Program Specialisation. In Proceedings of the 7th International Conference on Logic Programming (ICLP 1990), pages 732–746. The MIT Press.Google Scholar
Garavel, H., Tabikh, M., and Arrada, I. (2018). Benchmarking Implementations of Term Rewriting and Pattern Matching in Algebraic, Functional, and Object-Oriented Languages - The 4th Rewrite Engines Competition. In Proceedings of the 12th International Workshop on Rewriting Logic and its Applications (WRLA 2018), volume 11152 of Lecture Notes in Computer Science, pages 1–25. Springer.Google Scholar
Hanus, M. (1994). The Integration of Functions into Logic Programming: From Theory to Practice. The Journal of Logic Programming, 19/20:583–628.Google Scholar
Hanus, M. (1997). Integration of Declarative Paradigms: Benefits and Challenges. ACM SIGPLAN Notices, 32(1):77–79.CrossRefGoogle Scholar
Hanus, M. and Peemöller, B. (2014). A Partial Evaluator for Curry. In Proceedings of the 28th International Workshop on (Constraint) Logic Programming (WLP 2014), volume 1335, pages 155–171. CEUR-WS.org.Google Scholar
Jones, N. D., Gomard, C. K., and Sestoft, P. (1993). Partial Evaluation and Automatic Program Generation. Prentice-Hall.Google Scholar
Jørgensen, J., Leuschel, M., and Martens, B. (1996). Conjunctive Partial Deduction in Practice. In Proceedings of the 6th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 1996), volume 1207 of Lecture Notes in Computer Science, pages 59–82. Springer.Google Scholar
Leuschel, M. (1998). On the Power of Homeomorphic Embedding for Online Termination. In Proceedings of the 5th International Symposium on Static Analysis (SAS 1998), volume 1503 of Lecture Notes in Computer Science, pages 230–245. Springer.CrossRefGoogle Scholar
Leuschel, M., Elphick, D., Varea, M., Craig, S.-J., and Fontaine, M. (2006). The ECCE and LOGEN Partial Evaluators and their Web Interfaces. In Proceedings of the 16th ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 2006), pages 88–94. Association for Computing Machinery.CrossRefGoogle Scholar
Leuschel, M. and Gruner, S. (2001). Abstract Conjunctive Partial Deduction Using Regular Types and Its Application to Model Checking. In Proceedings of the 11th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2001), volume 2372 of Lecture Notes in Computer Science, pages 91–110. Springer.Google Scholar
Leuschel, M. and Lehmann, H. (2000). Solving Coverability Problems of Petri nets by Partial Deduction. In Proceedings of the 2nd ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2000), pages 268–279. Association for Computing Machinery.CrossRefGoogle Scholar
Lloyd, J. W. and Shepherdson, J. C. (1991). Partial Evaluation in Logic Programming. The Journal of Logic Programming, 11(3-4):217–242.CrossRefGoogle Scholar
Lucas, S. and Meseguer, J. (2016). Normal Forms and Normal Theories in Conditional Rewriting. Journal of Logical and Algebraic Methods in Programming, 85:67–97.CrossRefGoogle Scholar
Martens, B. and Gallagher, J. P. (1995). Ensuring Global Termination of Partial Deduction while Allowing Flexible Polyvariance. In Proceedings of the 12th International Conference on Logic Programming (ICLP 1995), pages 597–611. The MIT Press.Google Scholar
Martí-Oliet, N. and Meseguer, J. (2002). Rewriting Logic: Roadmap and Bibliography. Theoretical Computer Science, 285(2):121–154.CrossRefGoogle Scholar
Meadows, C. (1996). The NRL Protocol Analyzer: An Overview. The Journal of Logic Programming, 26(2):113–131.CrossRefGoogle Scholar
Meier, S., Schmidt, B., Cremers, C., and Basin, D. A. (2013). The TAMARIN Prover for the Symbolic Analysis of Security Protocols. In Proceedings of the 25th International Conference on Computer Aided Verification (CAV 2013), volume 8044 of Lecture Notes in Computer Science, pages 696–701. Springer.CrossRefGoogle Scholar
Meseguer, J. (1992a). Conditional Rewriting Logic as a Unified Model of Concurrency. Theoretical Computer Science, 96(1):73–155.CrossRefGoogle Scholar
Meseguer, J. (1992b). Multiparadigm Logic Programming. In Proceedings of the 3rd International Conference on Algebraic and Logic Programming (ALP 1992), volume 632 of Lecture Notes in Computer Science, pages 158–200. Springer.CrossRefGoogle Scholar
Meseguer, J. (2015). Variant-Based Satisfiability in Initial Algebras. In Proceedings of the 4th International Workshop for Safety-Critical Systems (FTSCS 2015), volume 596 of Communications in Computer and Information Science, pages 3–34. Springer.Google Scholar
Meseguer, J. (2020). Generalized Rewrite Theories, Coherence Completion, and Symbolic Methods. Journal of Logical and Algebraic Methods in Programming, 110.Google Scholar
Meseguer, J. (2021). Symbolic Computation in Maude: Some Tapas. In Proceedings of the 30th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2020), volume 12561 of Lecture Notes in Computer Science, pages 3–36. Springer.CrossRefGoogle Scholar
Meseguer, J., Palomino, M., and Martí-Oliet, N. (2008). Equational Abstractions. Theoretical Computer Science, 403(2–3):239–264.CrossRefGoogle Scholar
Meseguer, J. and Thati, P. (2007). Symbolic Reachability Analysis Using Narrowing and its Application to Verification of Cryptographic Protocols. Higher-Order and Symbolic Computation, 20(1–2):123–160.CrossRefGoogle Scholar
Ölveczky, P. C. and Meseguer, J. (2008). The Real-Time Maude Tool. In Proceedings of the 14th International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS 2008), volume 4963 of Lecture Notes in Computer Science, pages 332–336. Springer.CrossRefGoogle Scholar
Peemæller, B. (2017). Normalization and Partial Evaluation of Functional Logic Programs. PhD thesis, University of Kiel, Germany.Google Scholar
Plotkin, G. D. (1970). A Note on Inductive Generalization. Machine Intelligence, 5:153–163.Google Scholar
Rosu, G. (2017). K: A Semantic Framework for Programming Languages and Formal Analysis Tools. In Dependable Software Systems Engineering, volume 50 of NATO Science for Peace and Security Series - D: Information and Communication Security, pages 186–206. IOS Press.Google Scholar
Rodrguez, A., Durán, F., Rutle, A., and Kristensen, L. M. (2019). Executing Multilevel Domain-Specific Models in Maude. Journal of Object Technology, 18(2):4:1–21.Google Scholar
Serbanuta, T.-F. and Rosu, G. (2006). Computationally Equivalent Elimination of Conditions. In Proceedings of the 17th International Conference on Rewriting Techniques and Applications (RTA 2006), volume 4098 of Lecture Notes in Computer Science, pages 19–34. Springer.Google Scholar
Slagle, J. R. (1974). Automated Theorem-Proving for Theories with Simplifiers, Commutativity, and Associativity. Journal of the ACM, 21(4):622–642.CrossRefGoogle Scholar
Sørensen, M. H., Glück, R., and Jones, N. D. (1994). Towards Unifying Partial Evaluation, Deforestation, Supercompilation, and GPC. In Proceedings of the 5th European Symposium on Programming (ESOP 1994), volume 788 of Lecture Notes in Computer Science, pages 485–500. Springer.CrossRefGoogle Scholar
Viry, P. (2002). Equational Rules for Rewriting Logic. Theoretical Computer Science, 285(2):487–517.CrossRefGoogle Scholar