The concept of a supercompiler
Open accessAbstract
A supercompiler is a program transformer of a certain type. It traces the possible generalized histories of computation by the original program, and compiles an equivalent program, reducing in the process the redundancy that could be present in the original program. The nature of the redundancy that can be eliminated by supercompilation may be various, e.g., some variables might have predefined values (as in partial evaluation), or the structure of control transfer could be made more efficient (as in lazy evaluation), or it could simply be the fact that the same variable is used more than once. The general principles of supercompilation are described and compared with the usual approach to program transformation as a stepwise application of a number of equivalence rules. It is argued that the language Refal serves the needs of supercompilation best. Refal is formally defined and compared with Prolog and other languages. Examples are given of the operation of a Refal supercompiler implemented at CCNY on an IBM/370.
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?
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 Turchin 1986
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: 23
- BECKMAN L., 1974, A partial evaluator and its use as a programming tool. Arti{, InteU., 7, 319
- 10.1145/321992.321996 · DOI
- ERSHOV A.P., 1977, North-Holland, 391
- ERSHOV A. P., 1982, Potential applications and problems for future studies, Theor. Comput. Sci., 18, 41, 10.1016/0304-3975(82)90111-6 · DOI
- FRIEDMAN D. P., 1967, Automata, Languages and Programming, Michaelson and Millner, Eds
- FUTAMURA Y, 1971, Partial evaluation of computation process--an approach to a compiler-compiler, Syst. Comput. Control, 2, 5
- FUTAMURA Y., 1983, Proceedings RIMS Symposium on Software Science and Engineering, LNCS 147, 1
- HENDERSON P., 1976, Proceedings 3rd Symposium on POPL, 95
- JONES N., 1980, Semantics- Driven Compiler Generation, LNCS 94, 10.1007/3-540-10250-7 · DOI
- JONES N. D., 1985, International Conference on Rewriting Techniques and Applications
- JONES N., 1983, Univ. of Copenhagen
- LOMBARDI L.A., 1967, Advances in Computers, 8
- NILLSON N.J, 1983, Artificial intelligence prepares for 2001, AI Mag., 4, 7
- O'SHEA T., 1984, New York
- 10.1145/356914.356917 · DOI
- REDDY U. Narrowing as the operational semantics of functional languages. Submitted to the Symposium on Logic Programming (Boston 1985). REDDY U. Narrowing as the operational semantics of functional languages. Submitted to the Symposium on Logic Programming (Boston 1985).
- 1977, TsNIPIASS
- TURC N, V, 1972, Trudy Vsesoyuzn. Simpos. "Teoria Yazykov i metody progr," Alushta-Kiev
- 10.1145/954063.954069 · DOI
- TURCHIN V. F, 1980, The language Refal, the theory of compilation, and metasystem analysis, Courant Institute Rep., 20
- TURCH N, V, 1980, Semantics-Driven Compiler Generation, LNCS 94
- TURCHIN V. F., 1982, ACM Symposium on LISP and Functional Programming, 47
- VUILLEMIN J, 1974, Correct and optimal implementation of recursion in a simple programming language, J. Comput. Syst. Stud., 9, 3
Cited by
Sorted by citations
Occam's razor in metacomputation: the notion of a perfect process tree
Glück, R., & Klimov, A. V. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-57264-3_34 · Cited by 106 · see citing works
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
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
- Turchin, V. F.
- Affiliations
- City College of New York (US)
- Corresponding author
- Turchin, Valentin F.
- Venue
- ACM Transactions on Programming Languages and Systems
- Published
- 1986-06
- Volume
- 8
- Issue
- 3
- Pages
- 292-325
- ISSN
- 0164-0925 (ISSN-L)
- 1558-4593
- OpenAlex
- W2020024606
- Cited by
- 363
- References
- 0
- Citations by year
- 2026: 2 · 2025: 4 · 2024: 5 · 2023: 1 · 2022: 7 · 2021: 9 · 2020: 6 · 2019: 3 · 2018: 13 · 2017: 3 · 2016: 7 · 2015: 13 · 2014: 4 · 2013: 8 · 2012: 20
- FWCI
- 4.79
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Transactions on Programming Languages and Systems (publishedVersion)
- Funders
- National Science Foundation (8007565)
- Topics
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- supercompilation, program transformation, partial evaluation, lazy evaluation, equivalence rules, program equivalence
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
