×

zbMATH — the first resource for mathematics

Cadmium: an implementation of ACD term rewriting. (English) Zbl 1185.68137
Garcia de la Banda, Maria (ed.) et al., Logic programming. 24th international conference, ICLP 2008, Udine, Italy, December 9–13 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-89981-5/pbk). Lecture Notes in Computer Science 5366, 531-545 (2008).
Summary: Cadmium is a rule based programming language for compiling solver independent constraint models to various solver dependent back-ends. Cadmium is based on a hybrid between Constraint Handling Rules (CHR) and term rewriting modulo Associativity, Commutativity and a restricted form of Distributivity (ACD) called Conjunctive Context (CC). Experience with using Cadmium in the G12 project shows that CC is a powerful language feature, as local model mapping can depend on some non-local context, such as variable declarations or other constraints. However, CC significantly complicates the Cadmium normalisation algorithm, since the normal form of a term may depend on what context it appears in. In this paper we present an implementation of Cadmium based on classic bottom-up evaluation, but modified to handle CC matching. We evaluate the performance of the new implementation compared to earlier prototype normalisation algorithms. We show that the resulting system is fast enough to run “real-world” Cadmium applications.
For the entire collection see [Zbl 1154.68013].

MSC:
68N15 Theory of programming languages
Software:
Cadmium; G12; Maude; MiniZinc
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baader, F., Nipkow, T.: Term rewriting and all that. Cambridge Univ. Press, Cambridge (1998) · Zbl 0948.68098 · doi:10.1017/CBO9781139172752
[2] Brand, S., Duck, G.J., Puchinger, J., Stuckey, P.J.: Flexible, Rule-based Constraint Model Linearisation. In: Hudak, P., Warren, D.S. (eds.) PADL 2008. LNCS, vol. 4902, pp. 68–83. Springer, Heidelberg (2008) · Zbl 05243237 · doi:10.1007/978-3-540-77442-6_6
[3] Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., Talcott, C.: The Maude 2.0 System. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 76–87. Springer, Heidelberg (2003) · Zbl 1038.68559 · doi:10.1007/3-540-44881-0_7
[4] Duck, G.J., Stuckey, P.J., Brand, S.: ACD Term Rewriting. In: Etalle, S., Truszczyński, M. (eds.) ICLP 2006. LNCS, vol. 4079, pp. 117–131. Springer, Heidelberg (2006) · Zbl 1131.68374 · doi:10.1007/11799573_11
[5] Frühwirth, T.: Theory and practice of constraint handling rules. Journal of Logic Programming 37, 95–138 (1998) · Zbl 0920.68029 · doi:10.1016/S0743-1066(98)10005-5
[6] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: Towards a Standard CP Modelling Language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007) · Zbl 05318838 · doi:10.1007/978-3-540-74970-7_38
[7] Rewriting Engines Competition, http://www.lcc.uma.es/ duran/rewriting_competition/
[8] Eker, S.M.: Associative-Commutative Matching Via Bipartite Graph Matching. Computer Journal 38(5), 381–399 (1995) · Zbl 05478894 · doi:10.1093/comjnl/38.5.381
[9] Schmidt-Schauß, M.: Decidability of Unification in the Theory of One-Sided Distributivity and a Multiplicative Unit. Journal of Symbolic Computation 22(3), 315–344 (1997) · Zbl 0865.68065 · doi:10.1006/jsco.1996.0054
[10] Stuckey, P.J., García de la Banda, M., Maher, M., Marriott, K., Slaney, J., Somogyi, Z., Wallace, M., Walsh, T.: The G12 project: Mapping solver independent models to efficient solutions. In: Gabbrielli, M., Gupta, G. (eds.) ICLP 2005. LNCS, vol. 3668, pp. 9–13. Springer, Heidelberg (2005) · Zbl 1165.68517 · doi:10.1007/11562931_3
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.