An Algorithm of Generalization in Positive Supercompilation
Abstract
This paper presents a termination technique for positive supercompilation, based on notions from term algebra. The technique is not particularily biased towards positive supercompilation, but also works for deforestation and partial evaluation. It appears to be well suited for partial deduction too. The technique guarantees termination, yet it is not overly conservative. Our technique can be viewed as an instance of Martens ' and Gallagher's recent framework for global termination of partial deduction, but it is more general in some important respects, e.g. it uses well-quasi orderings rather than well-founded orderings. Its merits are illustrated on several examples.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
There is an interesting relation between the control techniques presented in the article and current practice in supercompilation.
“Next, there is an interesting relation between the control techniques presented in this article and current practice in supercompilation [Glück and Sørensen 1996;Sørensen and Glück 1995;Turchin 1986;Turchin 1988].”
From Controlling generalization and polyvariance in partial deduction of normal logic programs (1998) · cites this paper as Sørensen and Glück 1995
In Sørensen and Glück [1995], a generalization strategy for positive supercompilation (no negative information propagation while driving) is proposed.
“In the latter, a generalization strategy for positive supercompilation (no negative information propagation while driving) is proposed.”
From Controlling generalization and polyvariance in partial deduction of normal logic programs (1998) · cites this paper as Sørensen and Glück [1995]
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
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
- Sørensen, M. H., & Glück, R.
- ORCID
- Robert Glück
- Venue
- Logic Programming
- Publisher
- The MIT Press
- Published
- 1995
- OpenAlex
- W1598890912
- Cited by
- 145
- References
- 0
- Citations by year
- 2022: 2 · 2021: 4 · 2020: 4 · 2019: 3 · 2018: 7 · 2017: 1 · 2016: 1 · 2015: 2 · 2014: 1 · 2013: 4 · 2012: 15
- FWCI
- 22.16
- Type
- book chapter
- Language
- en
- Open access
- closed
- Locations
- The MIT Press eBooks (publishedVersion)
- Research at the University of Copenhagen (University of Copenhagen) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- termination analysis, term algebras, deforestation, partial evaluation, partial deduction, well-quasi-ordering, program transformation
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
