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.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BD91	Anders Bondorf , Olivier Danvy, Automatic autoprojection of recursive equations with global variable and abstract data types, Science of Computer Programming, v.16 n.2, p.151-195, Sept. 1991  [doi>10.1016/0167-6423(91)90002-F ]
	Bon91a	Anders Bondorf, Automatic autoprojection of higher order recursive equations, Selected papers from the symposium on 3rd European symposium on programming, p.3-34, December 1991
	Bon91b	Anders Bondorf. Similix Manual, system version j.O. DIKU, University of Copenhagen, Denmark, September 1991.
	CD91	Charles Consel , Olivier Danvy, For a better support of static data flow, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.496-519, June 1991, Cambridge, Massachusetts, United States
	Con90a	Charles Consel, Binding time analysis for high order untyped functional languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.264-272, June 27-29, 1990, Nice, France  [doi>10.1145/91556.91668]
	Con90b	Charles Consel. The Schism Manual. Yale University, New Haven, Connecticut, USA, 1990. Version 1.0.
	Dan91	Olivier Danvy, Semantics-directed compilation of nonlinear patterns, Information Processing Letters, v.37 n.6, p.315-322, March 28, 1991  [doi>10.1016/0020-0190(91)90148-B ]
	Dan92	Olivier Danvy, Back to direct style, Symposium proceedings on 4th European symposium on programming, p.130-150, January 1992, Rennes, France
	GJ91a	Carsten K. Gomard and Neil D. Jones. Compiler generation by partial evaluation: a case study. Structured Programming, 12:123-144, 1991.
	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.
	HG91	Carsten Kehler Holst , Darsten Krogh Gomard, Partial evaluation is fuller laziness, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.223-233, June 17-19, 1991, New Haven, Connecticut, United States
	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.
	IEE90	CORPORATE IEEE, Inc. Staff, IEEE Std 1178-1990, IEEE Standard for the Scheme Programming Language, IEEE Standards Office, New York, NY, 1991
	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.
	Jor92	Jesper Jørgensen, Generating a compiler for a lazy language by partial evaluation, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.258-268, January 19-22, 1992, Albuquerque, New Mexico, United States  [doi>10.1145/143165.143220]
	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.
	KS91	Siau Cheng Khoo , R. S. Sundaresh, Compiling inheritance using partial evaluation, ACM SIGPLAN Notices, v.26 n.9, p.211-222, Sept. 1991
	Lau91	John Launchbury, Projection factorisations in partial evaluation, Cambridge University Press, New York, NY, 1991
	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.
	Mog89	Torben }E. Mogensen. Binding Time Aspects of Partial Evaluation. PhD thesis, DIKU, University of Copenhagen, Denmark, March 1989.
	NN88	F. Nielson , R. H. Nielson, Automatic binding time analysis for a typed &lgr;-calculus, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-106, January 10-13, 1988, San Diego, California, United States  [doi>10.1145/73560.73569]
	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.
	Ste78	Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
	WCRS91	Daniel Weise , Roland Conybeare , Erik Ruf , Scott Seligman, Automatic online partial evaluation, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.165-191, June 1991, Cambridge, Massachusetts, United States

• Constructing reality Proceedings of the 11th annual international conference on Systems documentation
  Douglas A. Powell ,  Norman R. Ball ,  Mansel W. Griffiths
  
  
• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  

• ACM SIGPLAN Lisp Pointers
  Volume V ,  Issue 1   Jan. 1992