Abstract
Multiple program specialization can stage a computation into several computation phases. This paper presents an effective solution for multiple program specialization by generalizing conventional off-line partial evaluation and integrating the “cogen approach” with a multi-level binding-time analysis. This novel “multi-cogen approach” solves two fundamental problems of self-applicable partial evaluation: the generation-time problem and the generator-size problem. The multilevel program generator has been implemented for a higher-order subset of Scheme. Experimental results show a remarkable reduction of generation time and generator size compared to previous attempts of multiple self-application.
Supported by an Erwin-Schrödinger-Fellowship of the Austrian Science Foundation (FWF) under grant J0780 & J0964.
Preview
Unable to display preview. Download preview PDF.
References
Lars Ole Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. (DIKU report 94/19).
Anders Bondorf and Olivier Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. Science of Computer Programming, 16:151–195, 1991.
Anders Bondorf and Dirk Dussart. Improving cps-based partial evaluation: writing cogen by hand. In ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 1–9, Orlando, Florida, 1994.
Lennart Beckman, Anders Haraldson, Östen Oskarsson, and Erik Sandewall. A partial evaluator and its use as a programming tool. Artificial Intelligence, 7:319–357, 1976.
Anders Bondorf and Jesper Jørgensen. Efficient analyses for realistic off-line partial evaluation. Journal of Functional Programming, special issue on partial evaluation, 11:315–346, 1993.
Anders Bondorf. Automatic autoprojection of higher order recursive equations. Science of Computer Programming, 17(1–3):3–34, December 1991. Revision of paper in ESOP'90, LNCS 432, May 1990.
Lars Birkedal and Morten Welinder. Partial evaluation of Standard ML. DIKU Report 93/22, DIKU, Department of Computer Science, University of Copenhagen, 1993.
Lars Birkedal and Morten Welinder. Hand-writing program generator generators. In M. Hermenegildo and J. Penjam, editors, Programming Language Implementation and Logic Programming. Proceedings, volume 844 of LNCS, pages 198–214, Madrid, Spain, 1994. Springer-Verlag.
Felice Cardone and Mario Coppo. Type inference with recursive types: Syntax and semantics. Information and Computation, 92:48–80, 1991.
Charles Consel and Olivier Danvy. From interpreting to compiling binding times. In N. D. Jones, editor, ESOP '90, volume 432 of LNCS, pages 88–105, Copenhagen, Denmark, 1990. Springer-Verlag.
Andrei P. Ershov. On the essence of compilation. In E.J. Neuhold, editor, Formal Description of Programming Concepts, pages 391–420. North-Holland, 1978.
Robert Glück and Jesper Jørgensen. Generating transformers for deforestation and supercompilation. In B. Le Charlier, editor, Static Analysis. Proceedings, volume 864 of LNCS, pages 432–448, Namur, Belgium, 1994. Springer-Verlag.
Robert Glück and Jesper Jørgensen. Constraint-based multi-level bindingtime analysis of higher-order languages. Unpublished, 1995.
Robert Glück. Towards multiple self-application. In Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 309–320, New Haven, Connecticut, 1991. ACM Press.
Robert Glück. On the generation of specializers. Journal of Functional Programming, 4(4):499–514, 1994.
John Hatcliff. Mechanically verifying the correctness of an off-line partial evaluator. In PLILP'95, LNCS. Springer-Verlag, 1995.
Fritz Henglein. Efficient type inference for higher-order binding-time analysis. In John Hughes, editor, Conference on Functional Programming and Computer Architecture, Cambridge, Massachusetts. LNCS 523, pages 448–472. Springer-Verlag, August 1991.
Carsten Kehler Holst and John Launchbury. Handwriting cogen to avoid problems with static typing. Working paper, 1992.
Carsten Kehler Holst. Syntactic currying: yet another approach to partial evaluation. Technical report, DIKU, Department of Computer Science, University of Copenhagen, 1989.
Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993.
Torben A. E. Mogensen. Partially static structures in a self-applicable partial evaluator. In Dines Bjørner, Andrei P. Ershov, and Neil D. Jones, editors, Partial Evaluation and Mixed Computation, pages 325–347. North-Holland, 1988.
Flemming Nielson and Hanne R. Nielson. Two-Level Functional Languages, volume 34 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, 1992.
Sergei A. Romanenko. A compiler generator produced by a self-applicable specializer can have a surprisingly natural and understandable structure. In Dines Bjørner, Andrei P. Ershov, and Neil D. Jones, editors, Partial Evaluation and Mixed Computation, pages 445–463. North-Holland, 1988.
Peter Sestoft. Automatic call unfolding in a partial evaluator. In Dines Bjørner, Andrei P. Ershov, and Neil D. Jones, editors, Partial Evaluation and Mixed Computation, pages 485–506. North-Holland, 1988.
Morten Heine Sørensen, Robert Glück, and Neil D. Jones. Towards unifying partial evaluation, deforestation, supercompilation, and GPC. In Donald Sannella, editor, Programming Languages and Systems — ESOP '94. Proceedings, volume 788 of LNCS, pages 485–500, Edinburgh, Scotland, 1994. Springer-Verlag.
Valentin F. Turchin. Refal-5, Programming Guide and Reference Manual. New England Publishing Co., Holyoke, Massachusetts, 1989.
Mitchell Wand. Specifying the correctness of binding-time analysis. Journal of Functional Programming, 3(3):365–387, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Glück, R., Jørgensen, J. (1995). Efficient multi-level generating extensions for program specialization. In: Hermenegildo, M., Swierstra, S.D. (eds) Programming Languages: Implementations, Logics and Programs. PLILP 1995. Lecture Notes in Computer Science, vol 982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026825
Download citation
DOI: https://doi.org/10.1007/BFb0026825
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60359-7
Online ISBN: 978-3-540-45048-1
eBook Packages: Springer Book Archive