Tutorial on specialisation of logic programs
Open accessAbstract
In this tutorial the specialisation of declarative logic programs is presented. The main correctness results are given, and the outline of a basic algorithm for partial evaluation of a logic program with respect to a goal. The practical considerations of gaining efficiency (and not losing any) are discussed. A renaming scheme for performing structure specialisation is then described, and illustrated on a well-known string matching example. The basic algorithm is enhanced by incorporating abstract interpretation. A two-phase specialisation is then described and illustrated, in which partial evaluation is followed by the detection and removal of useless clauses. This is shown for the specialisation of a proof procedure for first order logic. The specialisation of meta programs is very important in logic programming, and the ground representation for object programs has to be handled. Some techniques for doing this are described. Comparisons are made in the tutorial to similar work in other programming languages, and the similarities and differences between them and logic program specialisation is discussed.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
From an operational point of view, Gallagher's meta-interpreter lifts the ground representation to the non-ground one for resolution.
“From an operational point of view, this meta-interpreter lifts the ground representation to the non-ground one for resolution”
From Creating specialised integrity checks through partial evaluation of meta-interpreters (1998) · cites this paper as [30]
In §6.2.1 (page unavailable), Gallagher describes an interpreter for programs represented as ground terms and says that all three arguments of its demo predicate are ground. The discussion of ground and non-ground representations also says that operations such as unification must be coded explicitly for the ground representation. This is contrary to the claim that the interpreter lifts the representation to a non-ground one for resolution. (LLM, conf=0.83)
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measuredGallagher presented a declarative meta-interpreter for the ground representation in [29,30].
“This was first exemplified by Gallagher in [29,30], where a (declarative) meta-interpreter for the ground representation is presented.”
From Creating specialised integrity checks through partial evaluation of meta-interpreters (1998) · cites this paper as [30]
It is possible to combine the ground and non-ground representations.
“Sometimes however, it is possible to combine both approaches.”
From Creating specialised integrity checks through partial evaluation of meta-interpreters (1998) · cites this paper as [30]
Section 6.1 describes ground and non-ground representations as two approaches, while Section 6.2 discusses specializing programs that use the ground representation. Neither passage says the representations can be combined; searches for combining or mixing them found no such statement in our copy. Page numbers were not available. (LLM, conf=0.70)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 4
- K, Benkerimi and J.W, Lloyd. A partial evaluation procedure for logic programs. In S.K. Debray and M. Hermenegildo, editors, Proceedings of the North American Conference on Logtc Programming, Austin, pages 343-358, MIT Press, 1990.
- D. Chan and M. Wallace. A treatment of negation during partial evaluation. In H. Abramson and M.H. Rogers, editors, Mets-Programmingin Logic Program- ming, MIT Press, 1989.
- C. Changand.R.C.-T Lee. Symbolic Logic and Mechcm- ical Theorem Proving. Academic Press, 1973.
- P.M. Hill and J.W. Lloyd. AnaJysis of meta-pro- grams. In H. Abramson and M.H. Rogers, editors, Mets-Prograrnming in Logic Programming, MIT Press, 1989.
Cited by
Sorted by citations
Controlling generalization and polyvariance in partial deduction of normal logic programs
Leuschel, M., Martens, B., & De Schreye, D. (1998) · ACM Transactions on Programming Languages and Systems · doi:10.1145/271510.271525 · Cited by 88 · see citing works
Narrowing-driven partial evaluation of functional logic programs
Alpuente, M., Falaschi, M., & Vidal, G. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61055-3_28 · Cited by 40 · see citing works
Creating specialised integrity checks through partial evaluation of meta-interpreters
Leuschel, M., & De Schreye, D. (1998) · The Journal of Logic Programming · doi:10.1016/s0743-1066(97)10012-7 · Cited by 29 · see citing works
Efficiently generating efficient generating extensions in prolog
Jørgensen, J., & Leuschel, M. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61580-6_12 · Cited by 26 · see citing works
- Authors
- Gallagher, J. P.
- Affiliations
- University of Bristol (GB)
- Corresponding author
- Gallagher, J. P.
- ORCID
- Gallagher, J. P.
- Venue
- Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation - PEPM '93
- Publisher
- ACM Press
- Published
- 1993
- Pages
- 88-98
- OpenAlex
- W2048831705
- Cited by
- 171
- References
- 0
- Citations by year
- 2024: 2 · 2022: 1 · 2021: 3 · 2019: 4 · 2018: 3 · 2016: 3 · 2014: 6 · 2013: 3 · 2012: 4
- FWCI
- 6.09
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM) (publishedVersion)
- Funders
- European Commission
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Database Systems and Queries
- Keywords
- partial evaluation, abstract interpretation, meta-programs, string matching, program efficiency
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
