Wednesday , June 20 2018

Syntax Extensions for a Constrained-Object Language via Dynamic Parser Cooperation*

Ricardo SOTO
Pontificia Universidad Católica de Valparaíso
Av. Brasil 2950, Valparaíso, Chile

Broderick CRAWFORD
Universidad Autónoma de Chile
Pedro de Valdivia 641, Santiago, Chile

Universidad Técnica Federico Santa María
Avenida España 1680, Valparaíso, Chile

Fernando PAREDES
Escuela de Ingeniería Industrial, Universidad Diego Portales
Manuel Rodríguez Sur 415, Santiago, Chile

Abstract: A modern feature of constraint languages is the ability of compiling a model into a set of solver languages. This allows one to model a problem in a single language and to execute it in a set of solver engines. The idea is to facilitate experimentation as well as model sharing. The common architecture to support this task is composed of three layers: an upper layer for the modeling language, a bottom layer for the solver language, and a middle one for performing the mapping process. However, this architecture has an important inconvenience: there is no mechanism for updating the modeling language. This paper addresses this concern by introducing a simple description language for extending the syntax of the modeling language. The goal is to make the architecture adaptable to further upgrades of the solver layer.

Keywords: Constraint Programming, Programming Languages, Modeling Languages.

>>Full text

CITE THIS PAPER AS: Ricardo SOTO, Broderick CRAWFORD, Eric MONFROY, Fernando PAREDES, Syntax Extensions for a Constrained-Object Language via Dynamic Parser Cooperation*, Studies in Informatics and Control, ISSN 1220-1766, vol. 21 (1), pp. 41-48, 2012.

1. Introduction

Constraint programming is a modern programming paradigm devoted to the efficient resolution of Constraint Satisfaction Problems (CSP). A CSP is a formal problem representation that mainly consists of a sequence of variables holding a domain and a set of constraint over such variables. The goal is to find a variable-value assignment that satisfies the whole set of constraints.

In the past years, several programming languages and libraries have been designed for CP, for instance, ECLiPSe [24], ILOG SOLVER [14], and OZ [16]. In these approaches, a host language is used to state control operations, a constraint language is used for modeling the variables and constraints, and a strategy language may be used to tune the solving process.

The expertise required by CP languages led to the development of modeling languages such as OPL [23]. Here, a higher-level of abstraction is provided. There is no need for dealing with operational concerns of the host language. The user states the model and the system solves it by means of a fixed underlying solver.

A recent concern is to separate the modeling language from the underlying solver [12, 7]. To this end, a three-layered architecture is proposed, including a modeling language, a solver, and a middle tool mapping models (with a high level of abstraction) to executable solver code (with a low-level of abstraction). Among others, this architecture gives the possibility to plug-in new solvers and to process a same model with different solvers.

An important inconvenience of this architecture is the lack of a mechanism for updating the modeling language. For instance, if a new functionality such as a new method, predicate or global constraint is added in the solver, the unique way to use it from the modeling layer is to update the grammar of the modeling language and to recompile it by hand. Likewise, the mapping tool needs to be modified. The translation of the new functionality from the modeling language to the solver language must be included.

In this paper, we present a simple description language to extend the syntax of a modeling language in order to make the architecture adaptable to further upgrades of the solvers. In addition we present an interesting parsing system for an efficient handling of this extension process. The extension language has been designed as part of the s-COMMA system [4], a three-layered architecture for modeling constrained objects (objects subject to constraints on their attributes [17]). In this architecture constraint satisfaction and optimization models [21, 22] can be translated to three native solver models: ECLiPSe [24], Gecode/J [20] and RealPaver [11].

The s-COMMA modeling language is built from a combination of a constraint language and an object-oriented framework. In this work, we will focus on extending just the constraint language of s-COMMA. We see no apparent necessity for extending the object-oriented framework.

The outline of this paper is as follows. In Section 2 we give an overview of the s-COMMA language. Section 3 describes the extension language. The parsing system is presented in Section 4. The process of updating the architecture is described in Section 5, followed by the related work and conclusions.


  1. BESSIÈRE, C., E. HEBRARD, B. HNICH, T. WALSH, The Complexity of Global Constraints. In proceedings of AAAI, 2004, pp. 112-117.
  2. CHIBA, S., A Metaobject Protocol for C++. In proceedings of OOPSLA, 1995, pp. 285-299.
  3. CHRISTIANSEN, H., A Survey of Adaptable Grammars. SIGPLAN Notices, vol. 25, no.11, 1990, pp. 35-44.
  4. CHENOUARD, R., L. GRANVILLIERS, R. SOTO, Model-driven Constraint Programming. In proceedings of the 10th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP), ACM Press, 2008, pp. 236-246.
  5. CLINGER, W., J. REES, Macros that Work. In proceedings of the 8th ACM Symposium on Principles of Programming Languages (POPL), 1991, pp. 155-162.
  6. DERSHOWITZ, N., J. JOUANNAUD, Rewrite Systems. In Handbook of Theoretical Computer Science, vol. B: Formal Models and Sematics (B), 1990, pp. 243-320.
  7. FRISCH, A., W. HARVEY, C. JEFFERSON, B. MARTÍNEZ-HERNÁNDEZ, I. MIGUEL, Essence: A Constraint Language for Specifying Combinatorial Problems. Constraints, vol. 13, no. 3, 2008, pp. 268-306.
  8. FRISCH, A., B. HNICH, Z. KIZILTAN, I. MIGUEL, T. WALSH, Global Constraints for Lexicographic Orderings. In proceedings of the 8th International Conference of Principles and Practice of Constraint Programming (CP), vol. 2470 of LNCS, 2002, pp. 93-108.
  9. GAMBINI, I., Quant aux carrés carrelés. PhD thesis, L’Université de la Méditerranée aix-Marseille II, 1999.
  10. GENT, I., B. SMITH, Symmetry Breaking in Constraint Programming. In proceedings of 14th European Conference on Artificial Intelligence (ECAI), 2000, pp. 599-603.
  11. GRANVILLIERS, L., F. BENHAMOU, Algorithm 852: Realpaver: An Interval Solver using Constraint Satisfaction Techniques. ACM Trans. Math. Softw., vol. 32, no. 1, 2006, pp. 138-156.
  12. MARRIOTT, K., N. NETHERCOTE, R. RAFEH, P. J. STUCKEY, M. GARCIA DE LA BANDA, M. WALLACE, The Design of the Zinc Modelling Language. Constraints, vol. 13, no. 3, 2008, pp. 229-267.
  13. PARR, T., K. FISHER, LL(*): The Foundation of the ANTLR Parser Generator. In proceedings of the 32th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), ACM Press, 2011, pp. 425-436.
  14. PUGET, J. F., A C++ Implementation of CLP. In proceedings of SCIS, Singapore, 1994.
  15. RAFEH, R., M. GARCÍA DE LA BANDA, K. MARRIOTT, M. WALLACE, From Zinc to Design Model. In proceedings of 9th International Symposium on Practical Aspects of Declarative Languages (PADL), vol. 4354 of LNCS, 2007, pp. 215-229.
  16. SMOLKA, G., The Oz Programming Model. In Computer Science Today, vol. 1000 of LNCS, 1995, pp. 324-343.
  17. SOTO, R., L. GRANVILLIERS, The Design of COMMA: An Extensible Framework for Mapping Constrained Objects to Native Solver Models. In proceedings of the 19th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE Computer Society, 2007, pp. 243-250.
  18. SOTO, R., L. GRANVILLIERS, Dynamic Parser Cooperation for Extending a Constrained Object-Based Modeling Language. In proceedings of the 21st Workshop on (Constraint) Logic Programming (WLP), Technical Report 434, University of W?rzburg, 2007, pp. 70-78.
  19. SOTO, R., Controlling Search in Constrained-Object Models. In proceedings of the 12th Ibero-American Conference on Artificial Intelligence (IBERAMIA), vol. 6433 of LNAI, 2010, pp. 582-591.
  20. SCHULTE, C., G. TACK, Perfect Derived Propagators. In proceedings of International Conference of Principles and Practice of Constraint Programming (CP), vol. 5202 of LNCS, 2008, pp. 571-575.
  21. TALMACIU, M., E. NECHITA, Some Combinatorial Optimization Problems for Weak-Bisplit Graphs. Studies in Informatics and Control, ICI Publishing House, vol. 19, no. 4, 2010, pp. 427-434.
  22. TANGOUR, F., P. BORNE, Presentation of Some Metaheuristics for the Optimization of Complex Systems. Studies in Informatics and Control, ICI Publishing House, vol. 17, no. 2, 2008, pp. 169-180.
  23. VAN HENTENRYCK, P., The OPL Optimization Programming Language. The MIT Press, 1999.
  24. WALLACE, M., S. NOVELLO, J. SCHIMPF, Eclipse: A Platform for Constraint Logic Programming, Technical Report IC-Parc, Imperial College, 1997.

* A shorter version of this paper was also published in the proceedings of the 21st Workshop on (Constraint) Logic Programming with the title “Dynamic Parser Cooperation for Extending a Constrained Object-Based Modeling Language” [18].