×

zbMATH — the first resource for mathematics

Maude: specification and programming in rewriting logic. (English) Zbl 1001.68059
Summary: Maude is a high-level language and a high-performance system supporting executable specification and declarative programming in rewriting logic. Since rewriting logic contains equational logic, Maude also supports equational specification and programming in its sublanguage of functional modules and theories. The underlying equational logic chosen for Maude is membership equational logic, that has sorts, subsorts, operator overloading, and partiality definable by membership and equality conditions. Rewriting logic is reflective, in the sense of being able to express its own metalevel at the object level. Reflection is systematically exploited in Maude endowing the language with powerful metaprogramming capabilities, including both user-definable module operations and declarative strategies to guide the deduction process. This paper explains and illustrates with examples the main concepts of Maude’s language design, including its underlying logic, functional, system and object-oriented modules, as well as parameterized modules, theories, and views. We also explain how Maude supports reflection, metaprogramming and internal strategies. The paper outlines the principles underlying the Maude system implementation, including its semicompilation techniques. We conclude with some remarks about applications, work on a formal environment for Maude, and a mobile language extension of Maude.

MSC:
68Q42 Grammars and rewriting systems
68T27 Logic in artificial intelligence
Software:
OBJ3; Maude; ELAN; CafeOBJ
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Astesiano, E.; Kreowski, H.-J.; Krieg-Brückner, B., Algebraic foundations of systems specification, IFIP state-of-the-art reports, (1999), Springer Berlin · Zbl 0922.00008
[2] Basin, D.; Cavel, M.; Meseguer, J., Rewriting logic as a metalogical framework, (), 55-80 · Zbl 1044.03020
[3] Bergstra, J.; Tucker, J., Characterization of computable data types by means of a finite equational specification method, (), 76-90
[4] P. Borovanský, Le Contrôle de la Réécriture: Étude et Implantation d’un Formalisme de Stratégies. Ph.D. Thesis, Université Henri Poincaré - Nancy I, October 1998.
[5] P. Borovanský, C. Kirchner, H. Kirchner, Controlling rewriting by rewriting, in: J. Meseguer (Ed.), Proc. 1st Int. Workshop on Rewriting Logic and its Applications, WRLA’96, Asilomar, California, September 3-6, 1996, Electronic Notes in Theoretical Computer Science, Vol. 4, Elsevier, Amsterdam, Sept. 1996, pp. 168-188, . · Zbl 0912.68088
[6] P. Borovanský, C. Kirchner, H. Kirchner, Rewriting as a unified specification tool for logic and control: the ELAN language, in: M.P.A. Sellink (Ed.), 2nd Int. Workshop on the Theory and Practice of Algebraic Specifications, Amsterdam, The Netherlands, September 25-26, 1997, Electronic Workshops in Computing. Springer, Berlin, 1998, .
[7] P. Borovanský, C. Kirchner, H. Kirchner, P.-E. Moreau, C. Ringeissen, An overview of ELAN, in: C. Kirchner, H. Kirchner (Eds.), Proc. 2nd Int. Workshop on Rewriting Logic and its Applications, WRLA’98, Pont-à-Mousson, France, September 1-4, 1998, Electronic Notes in Theoretical Computer Science, Vol. 15, Elsevier, Amsterdam, 1998, pp. 329-344, .
[8] P. Borovanský, C. Kirchner, H. Kirchner, P.-E. Moreau, M. Vittek, ELAN: a logical framework based on computational systems, in: J. Meseguer (Ed.), Proc. 1st Int. Workshop on Rewriting Logic and its Applications, WRLA’96, Asilomar, California, September 3-6, 1996, Electronic Notes in Theoretical Computer Science, Vol. 4, Elsevier, Amsterdam, Sept. 1996, pp. 35-50, . · Zbl 0912.68091
[9] Bouhoula, A.; Jouannaud, J.-P.; Meseguer, J., Specification and proof in membership equational logic, Theoret. comput. sci., 236, 35-132, (2000) · Zbl 0938.68057
[10] Burstall, R.; Goguen, J.A., The semantics of clear, a specification language, (), 292-332 · Zbl 0456.68024
[11] G. Carabetta, P. Degano, F. Gadducci, CCS semantics via proved transition systems and rewriting logic, in: C. Kirchner, H. Kirchner (Eds.), Proc. 2nd Int. Workshop on Rewriting Logic and its Applications, WRLA’98, Pont-à-Mousson, France, September 1-4, 1998, Electronic Notes in Theoretical Computer Science, Vol. 15, Elsevier, Amsterdam, 1998, pp. 253-272, . · Zbl 0917.68126
[12] Clavel, M., Reflection in rewriting logic: metalogical foundations and metaprogramming applications, (2002), CSLI Publications Stanford, CA · Zbl 1003.03032
[13] M. Clavel, F. Durán, S. Eker, P. Lincoln, N. Martı́-Oliet, J. Meseguer, Metalevel computation in Maude, in: C. Kirchner, H. Kirchner (Eds.), Proc. 2nd Int. Workshop on Rewriting Logic and its Applications, WRLA’98, Pont-à-Mousson, France, September 1-4, 1998, Electronic Notes in Theoretical Computer Science, Vol. 15, Elsevier, Amsterdam, 1998, pp. 3-24, . · Zbl 0917.68024
[14] M. Clavel, F. Durán, S. Eker, P. Lincoln, N. Martı́-Oliet, J. Meseguer, J.F. Quesada, Maude: specification and programming in rewriting logic, Manual distributed as documentation of the Maude system, Computer Science Laboratory, SRI International, , January 1999.
[15] M. Clavel, F. Durán, S. Eker, P. Lincoln, N. Martı́-Oliet, J. Meseguer, J.F. Quesada, A Maude tutorial, Tutorial distributed as documentation of the Maude system, Computer Science Laboratory, SRI International. Presented at the European Joint Conference on Theory and Practice of Software, ETAPS 2000, Berlin, Germany, March 25, 2000, , March 2000. · Zbl 0962.68108
[16] M. Clavel, F. Durán, S. Eker, P. Lincoln, N. Martı́-Oliet, J. Meseguer, J.F. Quesada, Towards Maude 2.0, in: K. Futatsugi (Ed.), Proc. 3rd Int. Workshop on Rewriting Logic and its Applications, WRLA 2000, Kanazawa, Japan, September 18-20, 2000, Electronic Notes in Theoretical Computer Science, Vol. 36, Elsevier, Amsterdam, 2000, pp. 297-318, .
[17] M. Clavel, F. Durán, S. Eker, J. Meseguer, Building equational proving tools by reflection in rewriting logic, in: Proc. CafeOBJ Symp. ’98, Numazu, Japan, CafeOBJ Project, April 1998, .
[18] Clavel, M.; Durán, F.; Eker, S.; Meseguer, J.; Stehr, M.-O., Maude as a formal meta-tool, (), 1684-1703
[19] M. Clavel, S. Eker, P. Lincoln, J. Meseguer, Principles of Maude, in: J. Meseguer (Ed.), Proc. 1st Int. Workshop on Rewriting Logic and its Applications, WRLA’96, Asilomar, California, September 3-6, 1996, Electronic Notes in Theoretical Computer Science, Vol. 4, Elsevier, Amsterdam, Sept. 1996, pp. 65-89, .
[20] M. Clavel, J. Meseguer, Reflection in conditional rewriting logic, Theoret. Comput. Sci. 2002, this volume. · Zbl 1001.68060
[21] G. Denker, J. Meseguer, C.L. Talcott, Formal specification and analysis of active networks and communication protocols: the Maude experience, in: D. Maughan, G. Koob, S. Saydjari (Eds.), Proc. DARPA Information Survivability Conference and Exposition, DISCEX 2000, Hilton Head Island, South Carolina, January 25-27, 2000, IEEE Computer Society Press, Silver Spring, MD, 2000, pp. 251-265, .
[22] Dershowitz, N.; Jouannaud, J.-P., Rewrite systems, (), 243-320 · Zbl 0900.68283
[23] Diaconescu, R.; Futatsugi, K., Cafeobj report, the language, proof techniques, and methodologies for object-oriented algebraic specification, AMAST series in computing. vol. 6, (1998), World Scientific Singapore
[24] Diaconescu, R.; Futatsugi, K.; Iida, S., Component-based algebraic specification and verification in cafeobj, (), 1644-1663
[25] R. Diaconescu, K. Futatsugi, M. Ishisone, T. Sawada, A.T. Nakagawa, An overview of CafeOBJ, in: C. Kirchner, H. Kirchner (Eds.), Proc. 2nd Int. Workshop on Rewriting Logic and its Applications, WRLA’98, Pont-à-Mousson, France, September 1-4, 1998, Electronic Notes in Theoretical Computer Science, Vol. 15, Elsevier, Amsterdam, 1998, pp. 75-88, .
[26] R. Diaconescu, J. Goguen, P. Stefaneas, Logical support for modularization, in: G. Huet, G. Plotkin, C. Jones (Eds.), Proc. Workshop on Logical Frameworks, Edinburgh, UK, May 1991, Cambridge University Press, Cambridge, May 1991, pp. 83-130.
[27] F. Durán, A Reflective Module Algebra with Applications to the Maude Language, Ph.D. Thesis, Universidad de Málaga, Spain, June 1999, .
[28] Durán, F., The extensibility of Maude’s module algebra, (), 422-437 · Zbl 0983.68522
[29] Durán, F.; Eker, S.; Lincoln, P.; Meseguer, J., Principles of mobile maude, (), 73-85
[30] F. Durán, J. Meseguer, An extensible module algebra for Maude, in: C. Kirchner, H. Kirchner (Eds.), Proc. 2nd Int. Workshop on Rewriting Logic and its Applications, WRLA’98, Pont-à-Mousson, France, September 1-4, 1998, Electronic Notes in Theoretical Computer Science, Vol. 15, Elsevier, Amsterdam, 1998, pp. 185-206, .
[31] F. Durán, J. Meseguer, Parameterized theories and views in Full Maude 2.0, in: K. Futatsugi (Ed.), Proc. 3rd Int. Workshop on Rewriting Logic and its Applications, WRLA 2000, Kanazawa, Japan, September 18-20, 2000, Electronic Notes in Theoretical Computer Science, Vol. 36, Elsevier, Amsterdam, 2000, pp. 319-337, .
[32] S. Eker, Fast matching in combination of regular equational theories, in: J. Meseguer (Ed.), Proc. 1st Int. Workshop on Rewriting Logic and its Applications, WRLA’96, Asilomar, California, September 3-6, 1996, Electronic Notes in Theoretical Computer Science, Vol. 4, Elsevier, Amsterdam, Sept. 1996, pp. 90-108. . · Zbl 0912.68057
[33] S. Eker, Term rewriting with operator evaluation strategy, in: C. Kirchner, H. Kirchner (Eds.), Proc. 2nd Int. Workshop on Rewriting Logic and its Applications, WRLA’98, Pont-à-Mousson, France, September 1-4, 1998, Electronic Notes in Theoretical Computer Science, Vol. 15, Elsevier, Amsterdam, 1998, pp. 45-62. . · Zbl 0917.68113
[34] K. Futatsugi (Ed.), Proc. 3rd Int. Workshop on Rewriting Logic and its Applications, WRLA 2000, Kanazawa, Japan, September 18-20, 2000, Electronic Notes in Theoretical Computer Science, Vol. 36, Elsevier, Amsterdam, 2000, .
[35] F. Gadducci, U. Montanari, Comparing logics for rewriting: rewriting logic, action calculi and tile logic, Theoret. Comput. Sci., 2002, this volume. · Zbl 1001.68056
[36] Goguen, J.A.; Meseguer, J., Order-sorted algebra iequational deduction for multiple inheritance, overloading, exceptions and partial operations, Theoret. comput. sci., 105, 217-273, (1992) · Zbl 0778.68056
[37] Goguen, J.A.; Winkler, T.; Meseguer, J.; Futatsugi, K.; Jouannaud, J.-P., Introducing OBJ, (), 3-167
[38] Jouannaud, J.-P.; Kirchner, H., Completion of a set of rules modulo a set of equations, SIAM J. comput., 15, 1155-1194, (1986) · Zbl 0665.03005
[39] C. Kirchner, H. Kirchner (Eds.), Proc. 2nd Int. Workshop on Rewriting Logic and its Applications, WRLA’98, Pont-à-Mousson, France, September 1-4, 1998, Electronic Notes in Theoretical Computer Science, Vol. 15, Elsevier, Amsterdam, 1998, .
[40] Kirchner, C.; Kirchner, H.; Vittek, M., Designing constraint logic programming languages using computational systems, (), 133-160
[41] N. Martı́-Oliet, J. Meseguer, Rewriting logic as a logical and semantic framework, in: D.Gabbay (Ed.), Handbook of Philosophical Logic, Second Edition, Vol. 9, Kluwer Academic Publishers, Dordrecht, 2002, . · Zbl 0912.68096
[42] J. Meseguer, Rewriting as a unified model of concurrency, Technical Report SRI-CSL-90-02, SRI International, Computer Science Laboratory, February 1990, Revised June 1990. · Zbl 0758.68043
[43] Meseguer, J., Conditional rewriting logic as a unified model of concurrency, Theoret. comput. sci., 96, 1, 73-155, (1992) · Zbl 0758.68043
[44] Meseguer, J., A logical theory of concurrent objects and its realization in the maude language, (), 314-390
[45] Meseguer, J., Solving the inheritance anomaly in concurrent object-oriented programming, (), 220-246
[46] J. Meseguer (Ed.), Proc. 1st Int. Workshop on Rewriting Logic and its Applications, WRLA’96, Asilomar, California, September 3-6, 1996, Electronic Notes in Theoretical Computer Science, Vol. 4, Elsevier, Amsterdam, Sept. 1996, .
[47] Meseguer, J., Rewriting logic as a semantic framework for concurrencya progress report, (), 331-372
[48] Meseguer, J., Membership algebra as a logical framework for equational specification, (), 18-61 · Zbl 0903.08009
[49] Meseguer, J., Research directions in rewriting logic, (), 347-398 · Zbl 0940.68069
[50] Meseguer, J., Rewriting logic and maude: a wide-spectrum semantic framework for object-based distributed systems, (), 89-117 · Zbl 0968.68079
[51] Meseguer, J., Rewriting logic and maude: concepts and applications, (), 1-26 · Zbl 0964.68069
[52] Meseguer, J.; Goguen, J.A., Order-sorted algebra solves the constructor-selector, multiple representation and coercion problems, Inform. comput., 104, 1, 114-158, (1993) · Zbl 0796.68144
[53] Meseguer, J.; Talcott, C.L., A partial order event model for concurrent objects, (), 415-430 · Zbl 0939.68084
[54] Milner, R., Communication and concurrency, (1989), Prentice-Hall Englewood Cliffs, NJ · Zbl 0683.68008
[55] Nipkow, T., Combining matching algorithms: the regular case, J. symbolic comput., 12, 633-653, (1991) · Zbl 0767.68069
[56] P.C. Ölveczky, Specification and Analysis of Real-Time and Hybrid Systems in Rewriting Logic, Ph.D. Thesis, University of Bergen, Norway, 2000, .
[57] P.C. Ölveczky, J. Meseguer, Real-time Maude: a tool for simulating and analyzing real-time and hybrid systems, in: K. Futatsugi (Ed.), Proc. 3rd Int. Workshop on Rewriting Logic and its Applications, WRLA 2000, Kanazawa, Japan, September 18-20, 2000, Electronic Notes in Theoretical Computer Science, Vol. 36, Elsevier, Amsterdam, 2000, pp. 361-383, . · Zbl 0962.68109
[58] P.C. Ölveczky, J. Meseguer, Specification of real-time and hybrid systems in rewriting logic, Theoret. Comput. Sci., 2002, this volume. · Zbl 1001.68061
[59] J.F. Quesada, The SCP parsing algorithm based on syntactic constraints propagation, Ph.D. Thesis, Universidad de Sevilla, Spain, June 1997.
[60] J.F. Quesada, The Maude parser: parsing and meta-parsing β-extended context-free grammars, Tech. Rep. Computer Science Laboratory, SRI International, 2001, in preparation.
[61] Suzuki, T.; Middeldorp, A.; Ida, T., Level-confluence of conditional rewrite systems with extra variables in right-hand sides, (), 179-193
[62] C.L. Talcott, An actor rewriting theory, in: J. Meseguer (Ed.), Proc. 1st Int. Workshop on Rewriting Logic and its Applications, WRLA’96, Asilomar, California, September 3-6, 1996, Electronic Notes in Theoretical Computer Science, Vol. 4, Elsevier, Amsterdam, Sept. 1996, pp. 360-383, .
[63] Talcott, C.L., Interaction semantics for components of distributed systems, (), 154-169
[64] Talcott, C.L., Towards a toolkit for actor system specification, (), 391-406 · Zbl 0983.68134
[65] C.L. Talcott, Actor theories in rewriting logic, Theoret. Comput. Sci., 2002, this volume. · Zbl 1001.68055
[66] A. Verdejo, N. Martı́-Oliet, Executing and verifying CCS in Maude, Tech. Rep. 99-00, Departamento de Sistemas Informáticos y Programación, Universidad Complutense de Madrid, Feb. 2000, . · Zbl 1086.68552
[67] Viry, P., Rewriting: an effective model of concurrency, (), 648-660
[68] P. Viry, Rewriting modulo a rewrite system, Technical Report TR-95-20, Dipartimento di Informatica, Università di Pisa, December 1995, .
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.