Some achievements and prospects in partial deduction
ACM Computing SurveysPublished 1 September 1998Open access
Michaël Leuschel, Bob Martens, Danny De Schreye
Citations9
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage.
Abstract
Interpretation ". Danny De Schreye is Senior Research Associate of the Fund for Scientific Research --- Flanders Belgium. Authors' addresses: M. Leuschel, B. Martens and D. De Schreye, Departement Computerwetenschappen, K.U.Leuven, Celestijnenlaan 200A, B-3001 Heverlee, Belgium. E-mail : fmichael,bern,[email protected] Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission and/or a fee. Permissions may be requested from Publicati...
Keywords
Computer Science
The Journal of Logic ProgrammingPartial evaluation in logic programming
388 Citations1991John W. Lloyd, J. C. Shepherdson
A theoretical foundation for partial evaluation in logic programming is given and it is shown that, unless strong conditions are imposed, the authors do not have completeness for the declarative semantics.
ACM Transactions on Programming Languages and SystemsControlling generalization and polyvariance in partial deduction of normal logic programs
92 Citations1998Michaël Leuschel, Bern Martens +1 more
This article elaborate global control for partial deduction, using the concept of a characteristic tree, encapsulating specialization behavior rather than syntactic structure, to guide generalization and polyvariance, and shows how this can be done in a correct and elegant way.
New Generation ComputingThe derivation of an algorithm for program specialisation
74 Citations1991John P. Gallagher, Maurice Bruynooghe
An algorithm, based on abstract interpretation, for source specialisation of logic programs, is developed, more general than partial evaluation, and can perform some source specialisations that cannot be done by partial evaluation; examples are specialisation that use information from infinite computations.
The MIT Press eBooksEnsuring Global Termination of Partial Deduction While Allowing Flexible Polyvariance
70 Citations1995Bern Martens, John P. Gallagher
A quite general framework is formulated where this set of distinct ``partially deduced'' atoms generated during partial deduction is represented as a tree structure and a well-founded order among such structures is defined, thus obtaining a foundation for certified global termination of partial deduction.
New Generation ComputingA general criterion for avoiding infinite unfolding during partial deduction
67 Citations1992Maurice Bruynooghe, Danny De Schreye +1 more
This work formulate formal and practical criteria for controlling the unfolding during the construction of SLD-trees that form the basis of a partial deduction and provides algorithms that allow to use these criteria in a constructive way.
Lirias (KU Leuven)A Conceptual Embedding of Folding into Partial Deduction: Towards a Maximal Integration
60 Citations1996Michaël Leuschel, Danny De Schreye +1 more
This paper provides an extended partial deduction framework in which most of the tupling and deforestation transformations of the fold/unfold approach, as well the current partial deduction transformations, can be achieved.
Lecture notes in computer sciencePartial deduction and driving are equivalent
59 Citations1994Robert Glück, Morten Heine Sørensen
It is argued that both techniques achieve essentially the same transformational effect by unification-based information propagation by giving a translation from a functional language to a definite logic language preserving certain properties.
Lecture notes in computer scienceRedundant argument filtering of logic programs
55 Citations1997Michaël Leuschel, Morten Heine Sørensen
A safe, effective approximation of the notion of a redundant argument is given and several simple and efficient algorithms based on the approximative notion are described, illustrating the practical benefits of this approach.
The Journal of Logic ProgrammingAutomatic finite unfolding using well-founded measures
37 Citations1996Bern Martens, Danny De Schreye
The framework to control unfolding during partial deduction of logic programs is extended to incorporate lexicographical priorities between argument positions in a goal, and it is shown how this can be adapted to cope with datalog-like constant manipulating predicates in a satisfactory way.
Lecture notes in computer scienceConstraint-Based Partial Evaluation of Rewriting-Based Functional Logic Programs
36 Citations1998L. Lafave, John P. Gallagher
Results from the implementation of the partial evaluator in the functional logic language Escher show that the algorithm is also able to perform intermediate list elimination and rename operations and termination and correctness properties.
Lecture notes in computer scienceRegular approximation of computation paths in logic and functional languages
35 Citations1996John P. Gallagher, L. Lafave
A method of approximating trace-terms is described, based on well-established methods for computing regular approximations of terms, applicable to both logic and functional languages, and appears to offer appropriate control information in both formalisms.
Controlling conjunctive partial deduction of definite logic programs
33 Citations1996Robert Glück, J. Jørgensen +2 more
This paper presents a generic algorithm for partial deduction within the framework by Lloyd and Shepherdson, and reene the generic algorithm into a fully automatic concrete one that registers partially deduced conjunctions in a global tree, and proves its termination and correctness.
Lecture notes in computer scienceConjunctive partial deduction in practice
32 Citations1997Jesper Jørgensen, Michaël Leuschel +1 more
Recently, partial deduction of logic programs has been extended to conceptually embed folding, so that partial deductions are no longer computed of single atoms, but rather of entire conjunctions.
Lecture notes in computer scienceLogic program specialisation: How to be more specific
32 Citations1996Michaël Leuschel, Danny De Schreye
This work presents a simple, as well as a more refined integration of conjunctive partial deduction with an abstract interpretation technique known as more specific program construction, where it surpasses the precision of current abstract interpretation techniques.
Lecture notes in computer scienceControlling conjunctive partial deduction
27 Citations1996Robert Glück, Jesper Jørgensen +2 more
Focusing on novel challenges specific to local and global control, a generic algorithm for conjunctive partial deduction is described, refined into a fully automatic concrete algorithm, and proved termination and correctness.
New Generation ComputingConstrained partial deduction and the preservation of characteristic trees
26 Citations1998Michaël Leuschel, Danny De Schreye
This paper presents a terminating partial deduction strategy which, for purely determinate unfolding rules, induces no loss of local specialisation due to the abstraction while ensuring correctness of the specialised programs.
Lecture notes in computer scienceEfficiently generating efficient generating extensions in prolog
26 Citations1996Jesper Jørgensen, Michaël Leuschel
The so called “cogen approach” to program specialisation, writing a compiler generator instead of a specialiser, has been used with considerable success in partial evaluation of both functional and imperative languages.