wiki:Papers

Doctoral thesis, François-Xavier Josset, 2002

Download PDF

Abstract

After a long hegemony of procedural languages, object-oriented programming is progressively improving as the leading technology for software engineering. The development of such applications remains delicate, as the treated problems may be complex and heterogeneous, and object-oriented programming languages artificially suitable. New tools and new methods that help the development process are proposed regularly, as well as increasingly powerful and open languages.

This thesis is about the specifications and the compilation of CLAIRE, a high-level object-oriented programming language, that offers reflexive objects, extensive types, parametric and polymorphic functions, concrete and abstract sets, production rules and primitives for hypothetical reasoning. This language, more especially dedicated to write hybrid algorithms for combinatorial optimization problems, comes with a complete programming environment reconciling expressivity and efficiency.

As an evolving plateform of development, a new version of CLAIRE is proposed with original collections, with a rich type system that implies a strong, safe and flexible typing, and with the ability to generate readable and maintainable Java programs. Moreover, a tool for static computations of metrics allows to determine the quality of CLAIRE applications, to identify their weaknesses and to visualize the improvements carried out during the different versions. The combination between the new platform and the tool for quality measures ensures a greater control of CLAIRE applications.

Doctoral thesis, François Laburthe, 1998

Download PDF

Abstract

His thesis considers the use of Constraint Programming (CP) in order to solve combinatorial optimization problems. We study and improve CP methods on a panel of important optimization problems (such as resource allocation, scheduling, travel optimization and time-tabling). This leads to CP algorithms which are enriched by redundant propagation rules, propagation algorithms inherited from Operations Research (OR) and customized search trees. We then compare the efficiency of such a Constraint Programming approach against more traditional Operations Research algorithms. This leads to a small roadmap of combinatorial problem solving, (as far as the problems cited above are concerned), matching problems (of varying size and difficulty) with algorithmic solutions (from CP and OR).

This roadmap highlights the relevance of hybrid algorithms for tackling large scale optimization problems. Such hybrid algorithms combine constraint programming with other algorithmic techniques such as local optimization. In order to encourage their development, we propose a high level langage, SaLSA, designed to specify the control flow of complex search procedures. We illustrate its use on various optimization problems, on which it is used to code hybrid search algorithms. Finally, we present an operational semantics from which the prototype implementation has been derived.

Source to Source Optimization and Abstract Interpretation in the CLAIRE Programming Language, Yves CASEAU, François-Xavier JOSSET

Download PDF

Abstract

This paper demonstrates the use of abstract interpretation and code specialization for the translation from a high-level functional programming language into a standard object-oriented target language. We report our experiments with CLAIRE, a high-level programming language for complex algorithms.

This language includes paradigms which are usually associated with declarative languages, such as objects, sets, parametric data structures, iterators, high-order functions, production rules, and search primitives. The originality comes from the tight integration of these concepts. We review here the use of abstract interpretation techniques in the source-to-source CLAIRE optimizer.

Abstract interpretation is used for type inference, for detecting possible side effects or allocations, the possibility of run-time errors, the need for specific type checking, or for computing various complexity metrics. We use these different properties about code fragments to perform various source-to-source optimizations, such as the optimization of method calls, as well as the specialization of set iteration, which is one of the most salient features of CLAIRE. We present a generic specialization scheme based on evaluating the complexity expected for a given call. These different rewriting techniques also allow us to deal efficiently with advanced features such as procedural attachment, defeasible updates (the ability to backtrack) or the management of inverses. The multiple layers of optimization may be seen as a fixed-point computation and advocate the need for simplification rules in the generated code which we call composition polymorphism.

The CLAIRE language was originally designed to develop hybrid algorithms for combinatorial problems.

These problems are complex to model and hard to solve from a computational point of view. Thus, it was necessary to combine expressiveness and efficiency. The source-to-source optimization techniques presented here aim at conciliating these two opposite goals.

Combining Sets, Search and Rules to Better Express Algorithms Yves Caseau, François-Xavier Josset, François Laburthe

Download PDF

Abstract

This paper presents a programming language that includes paradigms that are usually associated with declarative languages, such as sets, rules and search, into an imperative (functional) language. Although these paradigms are separately well-known and available under various programming environments, the originality of the CLAIRE language comes from the tight integration, which yields interesting run-time performances, and from the richness of this combination, which yields new ways to express complex algorithmic patterns with few elegant lines. To achieve the opposite goals of a high abstraction level (conciseness and readability) and run-time performance (CLAIRE is used as a C++ pre-processor), we have developed two kinds of compiler technology. First, a pattern pre-processor handles iterations over both concrete and abstract sets (data types and program fragments), in a completely user-extensible manner. Second, an inference compiler transforms a set of logical rules into a set of functions (demons that are used through procedural attachment).

From a Predicate Logic to an Event-Based Logic for Objects, Yves Caseau

Download PDF

Abstract

This paper presents an extension of the logic rule engine that is included into the CLAIRE system [CJL99] to handle events. We show how the predicate-based logic language that we use to define rule (an extension of Datalog) can be enriched with a few primitives to capture statements about transitions in the object state and external events. The main contribution of the paper is to show that this syntactical extension can be matched with an extension of the relational algebra that CLAIRE uses to compile rule into demons. Wirth very little effort it is possible to maintain a compilation strategy based on differentiation of relational terms [Cas94] that yields state-of-the-art performance.

Last modified 13 years ago Last modified on Oct 4, 2006 4:17:03 PM

Attachments (5)