Compilers and staging transformations

ABSTRACT

Computations can generally be separated into stages, which are distinguished from one another by either frequency of execution or availability of data. <i>Precomputation</i> and <i>frequency reduction</i> involve moving computation among a collection of stages so that work is done as early as possible (so less time is required in later steps) and as infrequently as possible (to reduce overall time).We present, by means of examples, several general transformation techniques for carrying out precomputation transformations. We illustrate the techniques by deriving fragments of simple compilers from interpreters, including an example of Prolog compilation, but the techniques are applicable in a broad range of circumstances. Our aim is to demonstrate how perspicuous accounts of precomputation and frequency reduction can be given for a wide range of applications using a small number of relatively straightforward techniques.Related work in partial evaluation, semantically directed compilation, and compiler optimization is discussed.

REFERENCES

• 1: Andrew W. Appel, Semantics-directed code generation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.315-324, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318661]
• 2: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 3: {Darlington81} Darlington, J., <i>The design of efficient data representations.</i> Department of Computing and Control, Imperial College London, 1981.
• 4: {Darlington82} Darlington, J., <i>The structured description of algorithm derivations.</i> International Symposium on Algorithmic Languages, Amsterdam, North Holland, 1982.
• 5: {Emanuelson80} Emanuelson, P., <i>Performance enhancement in a well-structured pattern matcher through partial evaluation.</i> Ph. D. thesis, Link&ouml;ping University, 1980.
• 6: {Ershov78} Ershov, A., <i>On the partial computation principle.</i> Information Processing Letters, Vol. 6, No. 2, pp. 38--41, April 1977.
• 7: {Ershov78} Ershov, A., <i>On the essence of compilation.</i> In: <b>Formal Descriptions of Programming Concepts.</b> Neuhold, E. J., ed., North-Holland, 1978.
• 8: {Ershov82} Ershov, A., <i>Mixed computation: potential applications and problems for study.</i> Theoretical Computer Science No. 18, pp. 41--67, 1982.
• 9: Daniel P. Friedman , Mitchell Wand, Reification: Reflection without metaphysics, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.348-355, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802051]
• 10: {Futamura71} Futamura, Y., <i>Partial evaluation of computation process---an approach to a compiler-compiler.</i> Systems. Computers. Controls Vol. 2, No. 5, pp. 721--728, 1971.
• 11: {Jones83} Jones, N. D. and A. Mycroft, <i>Stepwise development of operational and denotational semantics for prolog.</i> Draft version, DIKU, University of Copenhagen, April 1983.
• 12: {Jones85} Jones, N. D., P. Sestoft and H. S&oslash;ndergaard. <i>An experiment in partial evaluation: the generation of a compiler generator.</i> DIKU Report 85/1, University of Copenhagen, 1985.
• 13: {Kahn84} Kahn, K. and M. Carlsson, <i>The compilation of prolog programs without the use of a prolog compiler.</i> International Conference on Fifth Generation Computer Systems, ICOT, pp. 348--355, 1984.
• 14: H. Jan Komorowski, Partial evaluation as a means for inferencing data structures in an applicative language: a theory and implementation in the case of prolog, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.255-267, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582181]
• 15: Shahrzade Mazaher , Daniel M. Berry, Deriving a compiler from an operational semantics written in VDL, Computer Languages, v.10 n.2, p.147-164, 1985 [doi>10.1016/0096-0551(85)90004-9]
• 16: {Mosses79} Mosses, P., <i>SIS - semantics implementation system, reference manual and users guide.</i> DAIMI MD-30, &Aring;rhus University, 1979.
• 17: {Nillson84} Nillson, J. F., <i>Formal vienna-definition-method models of prolog.</i> In: <b>Implementations of Prolog.</b> Campbell, J. A. ed., Ellis Horwood, 1984
• 18: Lawrence Paulson, A semantics-directed compiler generator, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.224-233, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582178]
• 19: Peter Pepper, Program Transformation and Programming Environments, Springer-Verlag New York, Inc., Secaucus, NJ, 1984
• 20: John C. Reynolds, Definitional interpreters for higher-order programming languages, Proceedings of the ACM annual conference, p.717-740, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805852]
• 21: Jim des Rivières , Brian Cantwell Smith, The implementation of procedurally reflective languages, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.331-347, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802050]
• 22: William Louis Scherlis, Expression procedures and program derivation, 1980
• 23: William L. Scherlis, Program improvement by internal specialization, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.41-49, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567536]
• 24: {Scherlis83} Scherlis, W. L. and D. Scott, <i>First steps towards inferential programming.</i> IFIP Congress 83, North-Holland, 1983.
• 25: {Scherlis85} Scherlis, W. L., <i>Adapting abstract data types.</i> Carnegie-Mellon University, 1985.
• 26: David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
• 27: {Schmidt85b} Schmidt, D. A., <i>Tuning architectures to semantic definitions.</i> Iowa State University, 1985.
• 28: William M. Waite, Optimization, Compiler Construction, An Advanced Course, 2nd ed., p.549-602, January 1976
• 29: Mitchell Wand, Deriving Target Code as a Representation of Continuation Semantics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.496-517, July 1982 [doi>10.1145/357172.357179]
• 30: Mitchell Wand, Semantics-directed machine architecture, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.234-241, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582179]
• 31: David S. Wile, Program developments: formal explanations of implementations, Communications of the ACM, v.26 n.11, p.902-911, Nov. 1983 [doi>10.1145/182.358443]