Bern Martens

LOPSTR Conference 1998 Conference Paper

Preserving Termination of Tabled Logic Programs While Unfolding

• Michael Leuschel
• Bern Martens
• Konstantinos Sagonas

Abstract We provide a first investigation of the specialisation and transformation of tabled logic programs through unfolding. We show that — surprisingly — unfolding, even determinate, can worsen the termination behaviour in the context of tabling. We therefore establish two criteria which ensure that such mishaps are avoided. We also briefly discuss the influence of some other transformation techniques on the termination and efficiency of tabled logic programs.

LOPSTR Conference 1998 Conference Paper

Termination Analysis for Tabled Logic Programming

• Stefaan Decorte
• Danny De Schreye
• Michael Leuschel
• Bern Martens
• Konstantinos Sagonas

Abstract We provide a theoretical basis for studying the termination of tabled logic programs executed under SLG-resolution using a left-to-right computation rule. To this end, we study the classes of quasi-terminating and LG-terminating programs (for a set of atomic goals S ). These are tabled logic programs where execution of each call from S leads to only a finite number of different (i. e. , non-variant) calls, and a finite number of different calls and computed answer substitutions for them, respectively. We then relate these two classes through a program transformation, and present a characterisation of quasi-termination by means of the notion of quasi-acceptability of tabled programs. The latter provides us with a practical method of proving termination and the method is illustrated on non-trivial examples of tabled logic programs.

LOPSTR Conference 1998 Conference Paper

To Parse or Not To Parse

• Wim Vanhoof
• Bern Martens

Abstract In this paper, we reconsider the problem of specialising the vanilla meta interpreter through fully automatic and completely general partial deduction techniques. In particular, we study how the homeomorphic embedding relation guides specialisation of the interpreter. We focus on the so-called parsing problem, i. e. removing all parsing overhead from the program, and demonstrate that further refinements in the control of general partial deduction are necessary to properly deal with it. In particular, we modify local control on the basis of information imported from the global level. The resulting control strategy, while remaining fully general, leads to excellent specialisation of vanilla like meta programs. Parsing is always specialised, but — appropriately, as we will show — not always completely removed. As a concrete application, we subject an extended vanilla meta interpreter capable of dealing with compositions of programs to our techniques, showing we equal or surpass results obtained through a more ad hoc approach.

LOPSTR Conference 1997 Conference Paper

Conjunctive Partial Deduction in Practice

• Jesper Jørgensen
• Michael Leuschel
• Bern Martens

Abstract Recently, partial deduction of logic programs has been extended to conceptually embed folding. To this end, partial deductions are no longer computed of single atoms, but rather of entire conjunctions; Hence the term “conjunctive partial deduction”. Conjunctive partial deduction aims at achieving unfold/fold-like program transformations such as tupling and deforestation within fully automated partial deduction. However, its merits greatly surpass that limited context: Also other major efficiency gains can be obtained through considerably improved side-ways information propagation. In this paper, we present a first investigation of conjunctive partial deduction in practice. We describe the concrete options used in the implementation(s), look at abstraction in a practical Prolog context, include and discuss an extensive set of benchmark results. ¿ From these, we can conclude that conjunctive partial deduction can indeed pay off in practice, beating its conventional precursor on a number of small to medium size programs. However, controlling it in a perfect way proves far from obvious, and a range of challenging open problems remain as topics for further research.

LOPSTR Conference 1994 Conference Paper

Some Further Issues in Finite Unfolding (Abstract)

• Bern Martens
• Danny De Schreye

TCS Journal 1994 Journal Article

Sound and complete partial deduction with unfolding based on well-founded measures

• Bern Martens
• Danny De Schreye
• Tamás Horváth

We present a procedure for partial deduction of logic programs, based on an automatic unfolding algorithm which guarantees the construction of sensibly and strongly expanded, finite SLD-trees. We prove that the partial deduction procedure terminates for all definite logic programs and queries. We show that the resulting program satisfies important soundness and completeness criteria with respect to the original program, while retaining the essentially desired amount of specialisation.

LOPSTR Conference 1990 Conference Paper

Bottom-Up Specialisation of Logic Programs

• Wim Vanhoof
• Danny De Schreye
• Bern Martens

Abstract Partial deduction is an important transformation technique for logic programs, capable of removing inefficiencies from programs [ 4, 5 ]. As an on-line specialisation technique, it is based on an evaluation mechanism for logic programs. The input to a typical partial deducer is a program and a partially instantiated query. The instantiated part represents the information with respect to which one would like to specialise; the uninstantiated part represents the information not yet known. Therefore, all classical partial deduction techniques use top-down evaluation (or SLD -resolution) to evaluate the program parts that depend on the known input and generate a new program that computes its result using only the remainder of the input. Since the new program has less computations to perform, in general, it will be more efficient.