Anders Bondorf
ABSTRACT
A major obstacle in partial evaluation (program specialization) is the need for binding time improvements. By reorganizing a source program, the residual programs obtained by specializing the source program may be improved: more computations can be done statically, that is, at specialization time.
One well-known effective reorganization is (manual or automatic) conversion into continuation passing style (cps). This conversion allows data consumers to be propagated through frozen expressions to the data producers. In this paper we show how such improvements can be obtained without affecting the source program: by writing the program specializer itself in cps; traditionally, specialization has been formulated in direct style.
The advantages of avoiding cps-converting source programs are: (1) no cps-conversion phase is needed; (2) the generated residual programs are not in cps; (3) since no source level continuations are added, there is no overhead of manipulating closure representations in the generating extensions (e.g. compilers) obtained by self-application; (4) manual “binding time debugging” is easier since binding time analysis is done on a non-converted program.
We have implemented a cps-based program specializer; it is integrated in the partial evaluator Similix 4.0.
Using a cps-specializer, partially static data structures can be handled safely in a straightforward way. The difficulty is to ensure automatically that residual expressions that become part of a partially static data structure are neither duplicated nor discarded. This is achieved by binding such residual expressions in automatically inserted frozen let-expressions; cps is needed to propagate operations on the partially static data structure through these frozen let-expressions. Based on this idea, we have implemented an extension of Similix 4.0 that handles partially static data structures.
- BD91.Anders Bondorf and Olivier Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. Science o/ Computer Programming, 16:151-195, 1991. Google Scholar
Digital Library
- Bon91a.Anders Bondorf. Automatic autoprojection of higher order recursive equations. Science of Computer Programming, 17 (Selected papers of ESOP '90, the 3rd European Symposium on Programming, LNCS 432)(1-3):3-34, December 1991. Google ScholarDigital Library
- Bon91b.Anders Bondorf. Similix Manual, system version j.O. DIKU, University of Copenhagen, Denmark, September 1991.Google Scholar
- CD91.Charles Consel and Olivier Danvy. For a better support of static data flow. in John Hughes, editor, Conference on Functional Programming and Computer Architecture, Cambridge, Massachusetts. Lecture Notes in Computer Science 523, pages 495-519, Springer-Verlag, August 1991. Google ScholarDigital Library
- Con90a.Charles Consel. Binding time analysis for higher order untyped functional languages. In 1990 A CM Conference on Lisp and Functional Languages. Nice, France, pages 264-272, June 1990. Google ScholarDigital Library
- Con90b.Charles Consel. The Schism Manual. Yale University, New Haven, Connecticut, USA, 1990. Version 1.0.Google Scholar
- Dan91.Olivier Danvy. Semantics-directed compilation of nonlinear patterns. Information Processing Letters, 37(6):315-322, 1991. Google ScholarDigital Library
- Dan92.Olivier Danvy. Back to direct style. In Bernd Krieg-Briickner, editor, ESOP'92, gth European Symposium on Programming, Rennes, France. Lecture Notes in Computer Science 582, pages 130-150, Springer-Verlag, February 1992. Google ScholarDigital Library
- GJ91a.Carsten K. Gomard and Neil D. Jones. Compiler generation by partial evaluation: a case study. Structured Programming, 12:123-144, 1991.Google Scholar
- GJ91b.Carsten K. Gomard and Neil D. Jones. A partial evaluator for the untyped lambda-calculus. Journal of Functional Programming, 1(1):21-69, January 1991.Google ScholarCross Ref
- HG91.Carsten Kehler Hoist and Carsten K. Gomard. Partial evaluation is fuller laziness. In Symposium on Partial Evaluatgon and Semantics- Based Program Manipulation, Yale Universzty, New Haven, Connecticut. SIGPLAN Notices, volume 26, 9, pages 223-233, ACM Press, June 1991. Google ScholarDigital Library
- HH90.Carsten Kehler Hoist and John Hughes. Towards binding-time improvement for free. in Simon L. Pcytoxt Jones, Graham Hutton, and Carsten K ehler Hoist, editors, Functional Programming, Glasgow 1990. Workshops in Computing, pages 83-100, Springer-Verlag, August 1990.Google Scholar
- IEE90.IEEE standard for the Scheme programming language. May 1990. IEEE Std 1178-1990. Google ScholarDigital Library
- Jor90.Jesper Jorgensen. Generating a pattern matching compiler by partial evaluation. In Simon L. Peyton Jones, Graham Hutton, and Carsten Kehler Hoist, editors, Functional Programming, Glasgow 1990. Workshops in Computing, pages 177-195, Springer-Verlag, August 1990.Google Scholar
- Jor92.Jesper JOrgensen. Generating a compiler for a lazy language by partial evaluation. In Nineteenth Annual A CM SIGACT-S}CPLAN Symposium on Principles of Programming Languages. Albuquerque, New Mexico, January 1992. Google ScholarDigital Library
- JSS89.Neil D. Jones, Peter Sestoft, and Harald Sendergaard. MIX: a self-applicable partial evahator for experiments in compiler generation. LISP and Symbolic Computation, 2(1):9-50, 1989.Google ScholarCross Ref
- KS91.Siau Cheng Khoo and R.S. Sundaresh. Compiling inheritance using partial evaluation. In Symposium on Partial Evaluation and Semantics- Based Program Manipulation, Yale University, New Haven, Connecticut. SIGPLAN Notices, volume 26, 9, pages 211-222, ACM Press, June 1991. Google ScholarDigital Library
- Lau91.John Launchbury. Projection Factorisations in Partial Evaluation. Distinguished Dissertations in Computer Science, Cambridge University Press, 1991. Google ScholarDigital Library
- Mog88.Torben _/E. M ogensen. Partially static structures in a self-applicable partial evaluator. In Dines Bjgtrner, Andrei P. Ershov, and Nell D. Jones, editors, Partial Evaluation and Mixed Computation, pages 325-347, North-Holland, 1988.Google Scholar
- Mog89.Torben }E. Mogensen. Binding Time Aspects of Partial Evaluation. PhD thesis, DIKU, University of Copenhagen, Denmark, March 1989.Google Scholar
- NN88.Hanne R. Nielson and Flemming Nielson. Automatic binding time analysis for a typed ,X- calculus. In Fifteenth Annual A CM SIGACT- SIGPLAN Symposium on Principles o/ Programming Languages. San Diego, California, pages 98-106, 1988. Google ScholarDigital Library
- Ses88.Peter Sestoft. Automatic call unfolding in a partial evahator. In Dines Bjorner, Andrei P. Ershov, and Neil D. Jones, editors, Partial Evaluation and Mixed Computation, pages 485-506, North-Holland, 1988.Google Scholar
- Ste78.Guy L. Steele Jr. RABBIT: A Compiler /or SCHEME. Technical Report AI-TR-474, MIT, Cambridge, Massachusetts, Cambridge, Massachusetts, May 1978. Google ScholarDigital Library
- WCRS91.Daniel Weiss, Roland Gonybeare, Erik Ruf, and Scott Seligman. Automatic online partial evaluation, tn John Hughes, editor, Conference on Functional Programming and Computer Architecture, Cambridge, Massachusetts. Lecture Notes in Computer Science 523, pages 165-191, Springer-Verlag, August 1991. Google ScholarDigital Library
Index Terms
- Improving binding times without explicit CPS-conversion
Recommendations
Improving binding times without explicit CPS-conversion
A major obstacle in partial evaluation (program specialization) is the need for binding time improvements. By reorganizing a source program, the residual programs obtained by specializing the source program may be improved: more computations can be ...
Invalid Pointer Dereferences Detection for CPS Software Based on Extended Pointer Structures
SERE-C '12: Proceedings of the 2012 IEEE Sixth International Conference on Software Security and Reliability CompanionInvalid pointer dereferences, such as null pointer dereferences, dangling pointer dereferences and double frees, are a prevalent source of software bugs in CPS software, due to flexible dereferencing pointers along various pointer fields. Existing tools ...
Comments