The Journal of Functional and Logic Programming

Your institution may already be a subscriber to JFLP. If not, please subscribe for legitimate access to all journal articles.

This is a special issue of selected papers from the Joint International Symposium PLILP/ALP'98

Editorial by Catuscia Palamidessi.
[ps | pdf]

Detecting Unsolvable Queries for Definite Logic Programs by Maurice Bruynooghe, Henk Vandecasteele, D. Andre de Waal, and Marc Denecker.
[ps | pdf]

In solving a query, the SLD proof procedure for definite programs sometimes searches an infinite space for a nonexisting solution, for example, querying a planner for an unreachable goal state. Such programs motivate the development of methods to prove the absence of a solution. Considering the definite program and the query <- Q as clauses of a first-order theory, one can apply model generators that search for a finite interpretation in which the program clauses as well as the clause false <- Q are true. This paper develops a new approach that exploits the fact that all clauses are definite. It is based on a goal-directed abductive search in the space of finite preinterpretations for a preinterpretation such that Q is false in the least model of the program based on it. Several methods for efficiently searching the space of preinterpretations are presented. Experimental results confirm that our approach finds solutions with less search than with the use of a first-order model generator.

Explicit Substitutions for Objects and Functions by Delia Kesner and Pablo E. Martinez Lopez.
[ps | pdf]

This paper proposes an implementation of objects and functions via a calculus with explicit substitutions that is confluent and preserves strong normalization. The source calculus corresponds to the combination of the sigma calculus of Abadi and Cardelli and the lambda calculus, and the target calculus corresponds to an extension of the former calculus with explicit substitutions. The interesting feature of our calculus is that substitutions are separated and treated accordingly into two different kinds: those used to encode ordinary substitutions and those encoding invoke substitutions. When working with explicit substitutions, this differentiation is essential to the encoding of lambda calculus into sigma calculus in a conservative way, following the style proposed by Abadi and Cardelli.

Complexity Analysis of Late Binding in Dynamic Object-Oriented Languages by Enrico Pontelli, Desh Ranjan, and Gopal Gupta.
[ps | pdf]

We study the algorithmic complexity of supporting late binding in dynamic object-oriented programming languages. Dynamic object-oriented languages (such as most prototype-based languages and systems like CLOS) allow creation of new class definitions at run time. Late binding means that procedure-call name resolution, that is, mapping of procedure calls to method definitions, is done at run time, rather than compile time. Late binding is an essential feature of object-oriented programming and is present in most object-oriented languages, for example, Java, CLOS, Smalltalk, C++ (virtual functions). Name resolution for late binding is easily solved for static languages such as Java and C++; for dynamic languages, however, it is a complex problem. We propose an abstraction of the late binding problem for dynamic object-oriented languages in terms of operations on dynamic trees, and we prove a time lower bound of Omega(lg N) per operation, where N is the number of nodes in the tree. This result shows that efficient solutions - that is, solutions incurring a constant time-overhead per operation - of this problem are, in general, not possible. We also propose new data structures and algorithms for solving the late binding problem for dynamic object-oriented languages very efficiently, with a worst-case time complexity of O(sqrt^3(N)) per operation. This result is an improvement over frequently used approaches that have a complexity of Omega(N) per operation.

CAT: The Copying Approach to Tabling by Bart Demoen and Konstantinos Sagonas.
[ps | pdf]

The SLGWAM is an abstract machine that can be characterized as a sharing approach to implementing tabling: The execution environments of suspended computations are interspersed in the WAM stacks. Stacks are frozen using a set of freeze registers, and the WAM trail mechanism is extended so that the suspended computations can be resumed. This technique has a reasonably small execution overhead, but it is not easy to implement on top of an existing Prolog system. It is also quite difficult to understand.

We propose a new technique for the implementation of tabling: the copying approach to tabling. CAT does not impose any overhead to the execution of Prolog code and can be introduced into an existing Prolog system orthogonally. Also, CAT is easier to understand.

We have implemented CAT in the XSB system by taking out SLGWAM and adding CAT. We describe the additions needed for adopting CAT in a WAM implementation. We show a case in which CAT performs arbitrarily worse than SLGWAM, but on the other hand we present empirical evidence that CAT is competitive and often faster than the SLGWAM.

We also briefly discuss issues related to memory management and to the scheduling.

Bottom-up Partial Deduction of Logic Programs by Wim Vanhoof, Danny De Schreye, and Bern Martens.
[ps | pdf]

In this paper, we develop a solid theoretical foundation for a bottom-up program transformation, capable of specialising a logic program with respect to a set of unit clauses. Extending a well-known operator, we define a bottom-up partial deduction operator and prove correctness of the transformation with respect to the S-semantics. We also show how, within this framework, a concrete control strategy can be designed. The transformation can be used as a stand-alone specialisation technique, useful when a program needs to be specialised with respect to its internal structure (e.g., a library of predicates with respect to an abstract data type) instead of a single goal. Moreover, the bottom-up transformation can be usefully combined with a more traditional top-down partial deduction strategy.

Main page