×

A positive supercompiler. (English) Zbl 0870.68040

Summary: We introduce a positive supercompiler, a version of Turchin’s supercompiler maintaining only positive information during transformation, and using folding without generalization. The positive supercompiler can also be regarded as a variant of Wadler’s deforestation maintaining an increased amount of information. We compare our algorithm to deforestation and, in less detail, to partial evaluation, Turchin’s supercompiler, generalized partial computation (GPC), and partial deduction by classifying these transformers by the amount of information they maintain during transformation. This factor is significant, as a differentiating example reveals: positive supercompilation, Turchin’s supercompiler, GPC and partial deduction can specialize a general pattern matcher with respect to a fixed pattern to obtain an efficient matcher very similar to the Knuth-Morris-Pratt algorithm. Deforestation and traditional partial evaluation achieve this effect only after a non-trivial hand rewriting of the general matcher.

MSC:

68N20 Theory of compilers and interpreters
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wadler, ACM Symposium on Lisp and Functional Programming 1984 pp 282– (1984)
[2] Futamura, Partial Evaluation and Mixed Computation pp 133– (1988)
[3] DOI: 10.1145/357153.357154 · Zbl 0479.68014 · doi:10.1145/357153.357154
[4] DOI: 10.1145/199448.199507 · doi:10.1145/199448.199507
[5] Sørensen, Turchin’s supercompiler revisited. An operational theory of positive information propagation (1994)
[6] Andersen, ACM Workshop on Partial Evaluation and Semantics-Based Program Manipulation pp 1– (1992)
[7] Smith, Symposium on Partial Evaluation and Semantics-Based Program Manipulation pp 62– (1991)
[8] Sestoft, Partial Evaluation and Mixed Computation pp 485– (1988)
[9] Seidl, Lecture Notes in Computer Science (1996)
[10] Sands, Lecture Notes in Computer Science 915 pp 681– (1995)
[11] DOI: 10.1145/199448.199485 · doi:10.1145/199448.199485
[12] Proietti, Programming Language Implementation and Logic Programming pp 347– (1991) · doi:10.1007/3-540-54444-5_111
[13] Nielsen, Lecture Notes in Computer Science 983 pp 296– (1995)
[14] DOI: 10.1145/5956.5957 · Zbl 0598.68016 · doi:10.1145/5956.5957
[15] Consel, Lecture Notes in Computer Science 523 pp 495– (1991)
[16] DOI: 10.1145/800068.802134 · doi:10.1145/800068.802134
[17] Turchin, Lecture Notes in Computer Science 94 pp 441– (1980)
[18] DOI: 10.1016/0020-0190(89)90113-0 · doi:10.1016/0020-0190(89)90113-0
[19] DOI: 10.1145/141471.141494 · doi:10.1145/141471.141494
[20] DOI: 10.1145/954063.954069 · doi:10.1145/954063.954069
[21] DOI: 10.1145/321992.321996 · Zbl 0343.68014 · doi:10.1145/321992.321996
[22] Takano, Symposium on Partial Evaluation and Semantics-Based Program Manipulation pp 1– (1991)
[23] Bird, Introduction to Functional Programming (1988)
[24] Sørensen, Logic Programming: Proceedings of the 1995 International Symposium pp 465– (1995)
[25] DOI: 10.1007/BF00264249 · Zbl 0551.68017 · doi:10.1007/BF00264249
[26] Sørensen, Programming Languages and Systems pp 485– (1994)
[27] Augustsson, Lecture Notes in Computer Science 201 pp 368– (1985)
[28] Sørensen, Lecture Notes in Computer Science 787 pp 335– (1994)
[29] DOI: 10.1016/0743-1066(91)90027-M · Zbl 0741.68030 · doi:10.1016/0743-1066(91)90027-M
[30] Launchbury, 20th ACM Symposium on Principles of Programming Languages pp 144– (1993)
[31] DOI: 10.1137/0206024 · Zbl 0372.68005 · doi:10.1137/0206024
[32] Komorowski, Lecture Notes in Computer Science 649 pp 49– (1992)
[33] Jones, Lecture Notes in Computer Science 792 pp 206– (1994)
[34] Jones, Partial Evaluation and Automatic Program Generation (1993)
[35] Jones, Partial Evaluation and Mixed Computation pp 225– (1988)
[36] DOI: 10.1145/96877.96953 · doi:10.1145/96877.96953
[37] Glück, Lecture Notes in Computer Science 844 pp 165– (1994)
[38] Glück, Lecture Notes in Computer Science 864 pp 432– (1994)
[39] Glück, Lecture Notes in Computer Science 724 pp 112– (1993)
[40] DOI: 10.1016/0304-3975(90)90147-A · Zbl 0701.68013 · doi:10.1016/0304-3975(90)90147-A
[41] Futamura, International Conference on Fifth Generation Computer Systems pp 1– (1988)
[42] Wadler, The Implementation of Functional Programming Languages (1987)
[43] Turchin, Partial Evaluation and Mixed Computation pp 341– (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.