CICLOPS on Wednesday

Detailed program
Wednesday July 31st, 2002
See also the unified by-slot program


All sessions take place in auditorium 10.

Session 1: LP and Program Analysis

Chair: Ricardo Lopes

11:30-12:00  Tom Schrijvers, K.U. Leuven, Belgium
Combining an improvement to PARMA trailing with analysis in HAL
Trailing of bindings in the PARMA variable representation is expensive in time and space. Two schemes are presented that lower its cost: the first is a technique that halves the space cost of trailing in PARMA. It can be used with conditional and unconditional trailing. It is illustrated and evaluated in the context of dProlog and in the Mercury backend of HAL. The second scheme combines a variant of a previously developed trailing analysis with the first technique. Empirical evidence shows the usefulness of these schemes and that the combination is more effective than each scheme apart.

12:00-12:30  Michel Ferreira, U Porto, Portugal
Luis Damas, U Porto, Portugal
WAM local analysis
The abstract interpretation framework has been used mainly in the global analysis of programs. Most often also, this interpretation is applied to the source Prolog program. In this paper we present an abstract interpretation of more local nature, and applied to the intermediate code (WAM). The purpose of obtaining a more efficient specialized version of the program remains the same as in global analysis approaches. Our specialization is multiple, meaning that we generate a different version for each entry pattern detected by analysis. This poly-variant unfolding of predicates allows the local (predicate level) analysis to propagate inter-procedurally relevant information. Besides time and complexity reduction of local versus global analysis, our approach is suited for goal-independent specialization, and for the partial selection of predicates to specialize. The evaluation of this more general specialization of programs in a full compiler shows that it is an alternative to global and goal-dependent methods.

Session 2: (C)LP and OO

Chair: Christian Schulte

14:00-14:30  Rémi Douence, Ecole des Mines de Nantes, France
Narendra Jussien, Ecole des Mines de Nantes, France
Non-intrusive constraint solver enhancements
Using conflict sets (or nogoods) and explanations within constraint programming has been proved very effective. However, most constraint solvers do not provide this feature. This statement could have been made for many other improvements. Indeed, one of the main reasons of that fact is that many improvements in constraint programming are intrusive: their integration requires a general modification of the solvers' implementation and/or architecture. The core part of constraint solvers is often quite simple, however, it represents only a small part of the implementation. The main part of the code is devoted to specific constraint handling, global constraints, search techniques, API, etc. Modifying this code requires a real development effort that may become overly costly. Constraint solvers need non intrusive approaches. Actually, solvers should not be modified at all and only a general information about implementation should be needed to integrate improvements. In this paper, we present a technique used in software engineering to reach that aim: aspect oriented programming. As an example, the non intrusive integration of conflict set generation and use is presented and some insights of what could be done are provided.

14:30-15:00  Angel Pineda, Techn. U of Madrid, Spain
Francisco Bueno, Techn. U of Madrid, Spain
The O'Ciao approach to OO LP
There have been quite a number of proposals for the integration of Object Oriented Programming features into Logic Programming, resulting in much support theory and several languages. However, none of these proposals seem to have made it into the mainstream. Perhaps one of the reasons for this is that the resulting languages depart too much from the standard logic programming languages to entice the average Prolog programmer. Another reason may be that most of what can be done with object-oriented programming can already be done in Prolog through the meta- and higher-order programming facilities that the language includes, albeit sometimes in a more cumbersome way. In light of this, in this paper we propose an alternative solution which is driven by two main objectives. The first one is to explicitly include at the language level only those characteristics of object-oriented programming which are cumbersome to implement in standard Prolog systems. The second one is to do this in such a way that there is a minimum impact on the syntax and complexity of the language, i.e., to introduce the minimum number of new constructs and concepts. Finally, we would also like the implementation to be as straightforward as possible, ideally based on simple source to source expansions.

15:00-15:30  Manuel Carro, Techn. U of Madrid, Spain
Manuel Hermenegildo, Techn. U of Madrid, Spain
A simple approach to distributed objects in Prolog
We present the design of a distributed object systems for Prolog, based on adding remote execution and distribution capabilities to a previously existing object system. Remote execution brings RPC into a Prolog system, and its semantics are easy to express in terms of well-known Prolog builtins. The final distributed object design features state mobility and a user-transparent network behavior. We sketch an implementation which provides distributed garbage collection and some degree of resilience to network failures. We provide a preliminary study of the overhead of the communication mechanism for some test cases.

Session 3: LP and its implementation guts

Chair: Kostis Sagonas

16:00-16:30  Hia-Feng Guo, State U of New York-Stony Brook, USA
Gopal Gupta, U Texas-Dallas, USA
Cuts in tabled logic programming
Tabled logic programming (LP) systems alter the operational semantics of Prolog since they employ dynamic computation rules that are different from SLD resolution. This also requires changes to the operational semantics of cuts in tabled LP systems. In this paper we explore the incorporation of cuts in tabled logic programming systems, in particular, those based on our dynamic reordering of alternatives (DRA) technique. We present a reasonable operational semantics to cuts for DRA based systems and describe its implementation in the TALS tabled Prolog system. We also address the issues and problems that arise in handling cuts faced by other tabled Prolog systems. We argue that DRA based systems have an operational semantics closer to Prolog's, and therefore support cuts easily.

16:30-17:00  Luis F. Castro, State U of New York-Stony Brook, USA
Vitor S. Costa, U Wisconsin-Madison, USA
Ricardo Lopes, U Porto, Portugal
On the cache performance of Prolog systems
One critical issue in the design of declarative languages is their memory performance, both in terms of total memory usage and locality in memory accesses. Early studies of Prolog programs have shown the language to have excellent characteristics in this regard. In this work we study the memory performance of two modern Prolog systems through detailed instruction-level simulation. Our work aims at addressing several important questions in the implementation of logic programming systems. Through comparative analysis, we can study to what extent memory performance depends on the WAM design and on actual implementation. We study how deterministic and non-deterministic programs fare comparatively regarding locality. And we evaluate examples of larger Prolog applications that do rely extensively on built-ins. One issue of great importance we address in this work is the impact of garbage collection. We study the cache impact of running the garbage collector, and how it affects system efficiency. Our results show that garbage collection can both be very helpful to system performance, or damage cache-performance significantly, and explain why.