C

omponents

4

 for

R

ule-

B

ased

C

onstraint

P

rogramming

 

Problem and Motivation

State of the Art

Goal and Expected Results

Methodology

Current Status

References

Problem and Motivation

In this project, we will pioneer the investigation of the synergy between two hitherto unrelated areas of computer science: Rule-Based Constraint Programming (RBCP) (1) and Component-Based Software Engineering (CBSE) (3). These two areas bring complementary principles to the general issue of software reuse for Automated Reasoning (AR).

One the one hand, RBPC brings the idea of developing AR services for practical applications by reusing one generic inference engine to apply logical rules to conditionally rewrite constraints. Those rules can declaratively represent knowledge specific to one application domain. But they can also represent domain-independent algorithm and/or control heuristics for a general AR task class. They thus provide a way to declaratively program not only the domain knowledge base of an intelligent system but also most part of the inference engine to process this base.

One the other hand, CBSE brings the idea of developing any software in two largely orthogonal steps. The first, design for reuse step identifies services recurrently needed in a variety of contexts and encapsulate them into components that clearly separate the hidden services' realizations from their public specifications as a provided interface. Other components can use the services provided by this interfaces by connecting to their associated ports. This offers them the possibility to outsource by design part of their own provided services' realizations. This part must be publicly specified as required interfaces with associated ports. The second, design with reuse step of CBSE can then assemble at low-cost a variety of complex services by just connecting component ports with matching required and provided interfaces.

These CBSE concepts of components, interfaces, ports and assembly are currently only supported by imperative programming platforms (whether object-oriented or not) such as .Net or EJB. They are not supported by RBPC platforms, making constraint solving rule bases monolithic. We propose to investigate how these CBSE concepts can be adapted to the RBPC language CHRÚ (Constraint Handling Rules with Disjunctive bodies (1), a simple yet powerful extension of CHR (12)) and implemented in the adaptive CHRÚ engine CHROME (CHR Online Model-driven Engine) currently under development at CIn-UFPE.

The extension of CHRÚ with components, interfaces and ports will allow:

1.       Defining reusable units of various intermediate granularities, such as rule subsets, between the individual rule and the entire rule base, leveraging previous work in modules (29, 28) and type systems (25) for RBCP;

2.       Deploying these units in a distributed way as web services for seamless integration with other software or on a computer grid for efficient parallel constraint solving;

3.       Separating the rule-based realization of a service from its specification;

4.       Transparently substituting the rule-based realization of a service by a procedural realization and vice-versa without affecting its clients;

5.       Following a thorough CBSE methodology such as KobrA (3) to develop agents, robots, decision support systems and other applications with embedded AR by assembling components, some realizing their interfaces in procedural languages such as Java, C# or C++, notably GUI and persistent data API, and others realizing their interfaces as CHRÚ, notably general ontologies, domain specific knowledge bases, general purpose inference methods (e.g., rational tree unification (13)), and more domain customized ones (e.g., arithmetic constraint propagation maintaining bounds consistency (21)).

6.       Observing the overall process organization and resolution performance according to the methodology defined in (8).

CHRÚ components thus promise to make constraint solvers faster to prototype and easier to customize, reuse, combine and integrate into larger software. In fact, it should bring these benefits beyond constraint solving, to the wide array of AR tasks that have been recently reformulated as particular cases of constraint programming. These include deduction (31), abduction (1), default reasoning (1), inheritance (2), belief revision (17), belief update (27) and planning (27) whether using propositional (31), first-order relational (31) or object-oriented (2) representations with either logical (10), plausibilistic (17) or probabilistic (5) semantics. Each of these reformulations could be itself automated as two CHRÚ components: one that encapsulates rules to rewrite an input AR problem Rp into a corresponding equivalent RBCP problem Cp, and another one that encapsulates rules to reversely rewrite the RBCP solution Cs of Cp into the corresponding equivalent output AR solution Rs to Rp.

CHROME is extending Wolf's Justification-Based Truth-Maintenance (JTMS) for CHR-based adaptive constraint solving and CHR solving explanation generation (32) to the case of CHRÚ. As a sub-topic, we propose to investigate how maintenance of the justification of each constraint in the store will need to be extended when this store is no longer global but distributed among multiple CHRÚ components. We also aim to study how the distribution of the constraint store and rule base among various components can be best conveyed in the visual trace of a solving task performed by a CHRÚ component assembly. The long term topic of our project is thus the introduction of components to the most practical and challenging variety of RBCP: adaptive solving that integrates constraint simplification, propagation and search, and provides an insightful visual solving trace to ease debugging and evolution of constraint programs.

Both the INRIA Rocquencourt team and the CIn-UFPE team share a common interest and previous research in RBCP and CHRÚ. However, they bring complementary expertise to different aspects of the issues to investigate in the proposed project. The INRIA Rocquencourt team specific expertise fields in constraint programming are theoretical foundations (10), trace generation and visualization (8), (9) (11) (19), as well as modules (15), (16) and type systems (5), two precursors of software components. The CIn-UFPE specific expertise fields are model-driven engineering (4), software architecture (24), component-based modeling (23) and object-oriented implementation (28) of RBCP engines.

State of the Art

Constraint Programming (CP) is the leading technology to automate and optimize tasks such as resource allocation, scheduling, routing, placement, configuration, and design verification and diagnosis in the most diverse industries (29). The key to the success of CP platforms is their combination of flexible declarative specification of constraint solving tasks in subsets of first-order logic together with their realization by efficient built-in solving methods. The declarative input specification allows one to quickly try various logically equivalent formulations of the same task and choose the one that lends itself best to efficient solving by the methods built in the platform. Conventional CP platforms implement those methods procedurally in the operations of imperative libraries. RBCP pushes the declarative envelope one step further, by using first-order logic rules not only to specify solving tasks, but also solving methods. It thus allows one to quickly define and integrate various methods that are customized to the particular task at hand. This often brings sizable efficient gains for many instances of the task.

CHRÚ is a versatile RBCP language that can serve as a unifying basis to represent constraint solving, deduction, default reasoning, abduction (1), belief revision (17), belief update and planning (27) tasks and methods. It extends CHR that has proven successful in over 100 applications (31).

A CHRÚ program is a set of:

·          Constraint simplification rules of the form S1 ,..., Sa <=> G1 ,.., Gb | (B11,..., Bc1) ;...; (B1d ,..., Bed).  and

·          Constraint propagation rules of the form P1 ,..., Pf ==> G1 ,.., Gg | (B11 ,..., Bh1) ;...; (B1i ,..., Bji).

·          where the Sks, Gls, Bmns and Pos are first-order atoms representing constraints;

·          the Sks and Pos are called heads, the Gls guards and the Bmns bodies.

Operationally, firing a rule alters the content of a Provided Constraint Store (PCS) and a Required Constraint Store (RCS) (In the CHR literature, what we call here Provided constraint is called User-Defined constraint and what we call Required constraint is called Built-In constraint). The PCS stores constraints that match a rule head and/or body, while the RCS stores constraints that match a rule guard and/or body. Firing any rule adds to the stores the constraints of one selected alternative body set. Those that also appear as head in other rules go to the PCS, while those that also appear as guard in other rules go to the RCS. In addition, firing a simplification rule deletes the constraints that matched its head from the PCS.

The condition for firing a rule is that:

·          all its heads match some constraint in the PCS, and

·          the conjunction of its guards with the variable equations resulting from these matches logically entails the RCS.

A CHRÚ engine takes as input a constraint solving task as a set of constraints that initializes the PCS. It then forward chains the CHRÚ, avoiding applying twice the same rule to the same constraints, until either:

·          it reaches a fixed point for PCS È RCS which is then returned as the solving solution, or

·          the RCS simplifies to false.

In this second case, the engine backtracks to some body set choice in a disjunctive rule, resets the stores to their content prior to that choice, chooses an untried body set of that rule and resumes forward chaining. When all the body sets of the disjunctive rule have already been tried and failed, the engine further backtracks to a body set choice from another disjunctive rule fired earlier. CHRÚ is Turing-complete but not self-contained. The required constraint solver and the entailment prover that determines the firing condition of the rules must be implemented in a host platform such as Java, Prolog or Haskell. The CHRÚ engine acting as a client interleaves its processing with that of the host platform acting as a server. We envision a CHRÚ component assembly as a generalization of this single client-server relationship into an arbitrary graph of such relationships connecting CHRÚ components through matching ports and interfaces.

Components are the leading cost-cutting software reuse technology. A component encapsulates the realization of a service set and makes them accessible from outside through a provided interface with its access port. It may delegate part of this realization to external components by specifying them as required interfaces, each one with its access port. Applications and larger component realizations can be quickly assembled from smaller components by connecting the required port of client components to the provided port of server components which matching associated interfaces. In this regard, type systems (25) provide a first way to ensure some level of consistency in the assembly. Furthermore, each operation of a component's provided and required interfaces can be specified in detail using pre and post conditions. By providing detail service specifications while completely hiding their realizations, components with matching specifications but distinct realizations can be plugged out and in without affecting the rest of the assembly. A component can possess a publicly visible state lifecycle: only a subset of its provided interface operations can be called in a given state and these calls can in turn alter this state. Each component in an assembly can follow its own independent thread, using its ports as asynchronous communication channels with the other components. The KobrA method (3) (14) prescribes how to leverage UML to develop component-based artifacts throughout the entire software lifecycle from requirements, to design and testing.  The .Net and J2EE platforms provide sophisticated component assembly implementation, deployment facilities.

Previous work at INRIA (19) has shown that it was possible to adapt a predefined constraint solving model on the top of CHR, making possible to implement a generic tracer for CHR producing a generic trace in the style of Gentra4CP as defined in (9). This allows usage of various existing visualization tools, such as CLPGUI (11) among others, to observe, analyze and better understand constraint solving in CHR based on its underlying reasoning model. The generic trace format needs to be extended in two ways: one to cover the search introduced by the disjunctive bodies of CHRÚ , and another to cover solving distribution among the CHRÚ  component assembly. The tracer driver approach described in (8) emphasizes the client server view of tracing and should be adapted to component-based CHR solving where each component is able to broadcast its own trace.

Goals and Expected Results

We envision a CHRÚ component assembly as a generalization of the single client-server relationship between current monolithic CHRÚ bases and their host platform, into an arbitrary graph of client-server relationships where multiple CHRÚ components are connected through matching ports and interfaces. Each component would encapsulate CHRÚ whose heads are the constraints it provides as server through its provided interface and port. As opposed to the current monolithic CHRÚ bases which delegate solving of all constraints that appear in their guards to a single non-CP platform, a CHRÚ component C would delegate solving these required constraints among various other components, each one with its provided port connected to the matching required port of C. Some of these server components would encapsulate other CHRÚ whose heads are some of the constraints that appear as guards in C, while other would encapsulate a non-CP host platform program.

 Our goal is to elaborate this vision by studying some of the following open issues:

1.       A minimal syntactic extension of  CHRÚ to support components and modules (15),(16);

2.       An approach to upgrade with CHRÚ components CHROME's adaptive entailment verification method to check the firing of every matched rule; this should involve specifying a generic transformation to reformulate the task of determining entailment between two atom conjunctions as a constraint simplification task;

3.       An approach to upgrade with CHRÚ components CHROME's CHRÚ to Java compiler;

4.       An approach to upgrade with CHRÚ components CHROME's constraint justification representation that supports adaptation, reasoning trace generation and conflict-directed backjumping (7) to efficiently search the alternative body sets of disjunctive rules;

5.       An approach to visualize reasoning traces resulting from the interaction between CHRÚ components and a modular tracer compatible with the Gentra4CP format (9);

6.       In what circumstances can the confluence and termination properties of a CHRÚ component assembly be derived from the confluence and termination properties   of its parts?

Another result of this project will be to demonstrate how to leverage the concept of component to seamlessly integrate procedural and declarative modules in large software. In addition, the delegation of required constraint solving to underlying CHRÚ as opposed to a non-CP platform, shall allow to study two intriguing fundamental questions: (a) what is the minimal set of required constraints that must ultimately be delegated to a non-CP platform at the bottom of the CHRÚ component hierarchy and (b) could this set be in fact empty, suggesting the feasibility of a purely constraint programming platform?

CHRÚ simplification rules extend conditional term rewrite rules (20) with disjunctive right-hand sides and Constraint Logic Programming (CLP) (13) rules with guards and multiple heads. CHRÚ propagation rules extend production rules (25) with disjunctive right-hand sides and CLP rules with integrity constraints. The component model that we intend to propose for CHRÚ would thus also constitute a component model for conditional term rewrite rule languages, CLP, Prolog (since CLP is a proper extension of Prolog) and production rule languages. Since term rewriting, logic programming and production rules are the three major rule-based programming and knowledge representation paradigms, the expected results of this project will go well-beyond constraint programming and provide a unifying, sound basis to incorporate components to rule-based systems in general. Such result would in turn be very useful to a variety of computer science topics including distribution and integration of active, deductive and constraint databases, and the current efforts to incorporate rules in semantic web languages.

Methodology

We will conduct our study incrementally starting with the smallest possible core of CHR components with neither disjunctive rules, nor adaptation, nor reasoning trace visualization. In the following three steps, we will study the orthogonal extensions of core CHR components with each of these three aspects. In the last fifth step we will study the integration of these three aspects in an adaptive engine for CHRÚ components with a user-friendly trace visualization interface. The theoretical study of confluence and termination properties of CHRÚ component assembly will be carried out as sixth parallel step. These issues will be investigated and our proposed solutions validated through the development of two CHRÚ components assembly case studies. Each one will solve a task that involves constraints among variables from different domains and require the integration of very different solving methods.

For the main five practical issues we will use a model-driven engineering approach (26) starting by elaborating a Platform Independent Model (PIM) in UML and OCL following KobrA-2 (4), an upgrade of KobrA leveraging the power of the latest standard modeling languages published by the Object Management Group (22).

KobrA-2 prescribes specifying component:

·          Requirements by a set of provided and required interfaces with pre-conditions, post-conditions or body expressions for each operation in the Object Constraint Language (OCL (30)  a textual functional object-oriented language part of the UML standard to detail models with arbitrary logical and procedural constraints among arbitrary model elements); these interfaces must be accompanied by a class diagram that defines the non-primitive type of each input and output parameter for each of their operations;

·          Design by an encapsulated recursive assembly of embedded KobrA-2 components, complemented by an additional class diagram where each operation behavior is in turn specified by either an OCL expression or one or several embedded activity diagrams;

·          Tests by adding to each component a testing interface that gives access to the component internal states for glass box testing (whereas the provided service interface hides such internal states) and embedded tester components to connect to the testing interfaces of its server components to run tests (14).

If we can find additional collaborators during the course of the project, they will then construct from the PIM a Platform Specific Model (PSM) geared towards a Java implementation. From this PSM they will then produce such an implementation and test it on the two validation case studies.

Current Status

The project just received funding from INRIA and FACEPE through the end of 2008. It shall kick-off in May 2007.

It currently involves:

·          Dr. François Fages and Dr. Pierre Deransart from the CONTRAINTES group at INRIA Rocquencourt, France;

·          Prof. Jacques Robin and MSc. student Cleyton Rodrigues at CIn-UFPE, Recife, Brazil.

·          Prof. Luis Menezes of  Escola Politécnica, Universidade de Permanbuco, Caruaru, Brazil

References

(1) Abdennadher, S. 2001. Rule-based Constraint Programming: Theory and Practice. Habilitationsschrift, Institut für Informatik, Ludwig-Maximilians-Universität München.

(2) Ait-Kaci, H., Nasr, R. 1986. LOGIN: A Logic Programming Language with Built-in Inheritance. In Journal of Logic Programming, 3:185--215.

(3) Atkinson, C., Bayer, J., Bunse, C., Kamsties, E., Laitenberger, O., Laqua, R., Muthig, D., Paech, B., Wust, J. and Zettel, J. Component-based Product Line Engineering with UML. Addison-Wesley, 2002.

(4) Atkinson, C., Bendraou, R., Blanc. X, Robin, J., Stoll, D. and Vitorino, J. Upgrading a Model-Driven Component-Based Software Process to Leverage the Latest OMG Standard Languages. In preparation.

(5) Coquery E., Fages F. 2006. A Type system for CHR. Selected papers from ERCIM/Colognet Workshop on Constraint Solving and Constraint Logic Programming CSCLP'05. Recent Advances in Constraints. Springer-Verlag LNAI 3978.

(6) Costa, V.S., Page, D., Qazi, M., Cussens, J. 2003. CLP(BN): Constraint Logic Programming for Probabilistic Knowledge. In Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence. Acapulco, Mexico.

(7) Dechter, R. 2003. Constraint Processing. Morgan-Kaufmann.

(8)  Deransart P., 2006. On using Tracer Driver for External Dynamic Process Observation, Workshop on Logic-based Methods in Programming Environments, Seattle, August 16.

(9) Deransart P., Fekete, J.-D.  2006. Trace Format for Constraint Programming repository  (Tra4CP) (http://contraintes.inria.fr/OADymPPaC/Net/tra4cp/www/index.html ).

(10) Fages F., Ruet P., Soliman S. 2001.  Linear concurrent constraint programming: operational and phase semantics. Journal of Information and Computation 165(1) pp.14-41.

(11) Fages F., Soliman S., Coolen R. 2004. CLPGUI: a Generic Graphical User Interface for Constraint Logic Programming. Journal of Constraints 9(4).

(12) Frühwirth, T. 1994. Theory and Practice of Constraint Handling Rules. In Journal of Logic Progamming. 19(20).

(13) Frühwirth, T., Abdennadher, S. 2003. Essentials of Constraint Programming.  Springer-Verlag,

(14) Gross, H.B. 2004. Component-Based Software Testing with UML. Springer.

(15) Haemmerlé  R.,  Fages F. 2006. Modules for Prolog Revisited. 22nd International Conference on Logic Programming ICLP'06. Seattle, USA. Springer Verlag, LNCS 4079, pp. 41-55.

(16) Haemmerlé  R.,  Fages F. , Soliman S. 2006. On internalizing modules as agents in Linear logic concurrent constraint languages. INRIA Research Report 5981.

(17) Jin, Y., Thielscher, M. 2006. Iterated Belief Revision, Revised. In Artificial Intelligence. (to appear).

(18) Kakas, A.C., Kowalski, R.A. and Toni, F. 1998. The Role of Abduction in Logic Programming. In Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 5. Oxford University Press.

(19)  Kalla S., 2002. Trace générique pour CHR sur domaines finis, Mémoire DEA, INRIA-Rocquencourt.

(20) Kaplan, S. 1984. Conditional Rewrite Rules. Theoretical Computer Science 33.

(21) Marriott, K. and Stuckey, P. 1998. Programming with Constraint: An Introduction. MIT Press.

(22) The Object Management Group. http://www.omg.org. OMG's MetaObject Facility. http://www.omg.org/mof/.

(23) Robin J., Vitorino, J. 2006. ORCAS: Towards a CHR-Based Model-Driven Framework of Reusable Reasoning Components. In Proceedings of the 20th Workshop on (Constraint) Logic Programming (WLP'06).Vienna, Austria.

(24) Robin, J., Vitorino, J., Wolf, A. Constraint Programming Architectures: Review and a New Proposal. Submitted to the 11th Brazilian Symposium on Programming Languages (SBLP'07), 2007, Natal, RN, Brazil.

(25) Russell, S. and Norvig, 2003. P. Artificial Intelligence: A Modern Approach (2nd Ed.). Prentice-Hall.

(26) Stahl, T., Völter, M. 2006. Model-Driven Software Development: Technology, Engineering, Management. Wiley.

(27) Thielscher, M. 2002, Programming of Reasoning and Planning Agent with FLUX. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), Toulouse, France.

(28) Vitorino, J., Robin, J., Frühwirth, T. Towards a Model Transformation Based Compiler for Disjunctive Constraint Handling Rules. Submitted to the 9th International Conference on Enterprise Information System, Madeira, Portugal.

(29) Wallace, M. 1996. Practical Applications of Constraint Programming. Constraints Journal 1(1). Kluwer.

(30) Warmer J., Kleppe A. 2003. The Object Constraint Language ( 2nd Ed.): Getting Your Models Ready for MDA, Addison-Wesley.

(31) WebCHR: http://www.cs.kuleuven.be/~dtai/projects/CHR/.

(32) Wolf, A., Gruenhagen, T., Geske, U. 2000. On Incremental Adaptation of CHR Derivations. In Journal of Applied Artificial Intelligence 14(4). Special Issue on Constraint Handling Rules.

© Jacques Robin, Pierre Deransart and François Fages 2006-2007. Last Updated: 06/03/2007