Towards efficient partial evaluation

ABSTRACT

In general, a partial evaluator needs to keep track of the tasks that have already been completed or initiated, so that it can recognize when to stop unfolding. In the MIX-style polyvariant specialization algorithm, this is accomplished by a global log. This is a very general technique, so it is not surprising that the algorithm is not particularly efficient. In many special cases a simpler technique would suffice. In this paper, we identify some classes of such special cases by considering the purpose of the global log. We outline how a partial evaluator can take advantage of these special cases and we propose analyses to detect them automatically. We discuss examples to illustrate the effect on specialization and to demonstrate that we can even obtain better residual programs. The work presented here is still in its early stages, and we do not have a full system incorporating the proposed improvements.

REFERENCES

• And92: L.O. Andersen. C program specialization. Technical Report 92/14, DIKU, University of Copenhagen, Denmark, May 1992.
• 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, Science of Computer Programming, v.17 n.1-3, p.3-34, Dec. 1991
• Bon91b: A. Bondorf. Similix manual, system version 4.0. DIKU, University of Copenhagen, Denmark. September, 1991.
• Bon92: Anders Bondorf, Improving binding times without explicit CPS-conversion, ACM SIGPLAN Lisp Pointers, v.V n.1, p.1-10, Jan. 1992
• Bon93: A. Bondorf. Similix manual, system version 5.0. DIKU, University of Copenhagen, Denmark, April 1993.
• 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
• CR91: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• Got74: E. Goto. Monocopy and associative algorithms in an extended Lisp. Technical report, University of Tokyo, Japan, May 1974.
• Hen91: Fritz Henglein, Efficient type inference for higher-order binding-time analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.448-472, June 1991, Cambridge, Massachusetts, United States
• Hol91: Carsten Kehler Holst, Finiteness analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.473-495, June 1991, Cambridge, Massachusetts, United States
• JGS93: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• JM86: Neil D. Jones , Alan Mycroft, Data flow analysis of applicative programs using minimal function graphs, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.296-306, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512672]
• JSS89: N.D. Jones, P. Sestoft, and H. Sendergaard. Mix: A self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation, 2(1):9-50, 1989.
• Plo75: G.D. Plotkin. CaJl-by-name, call-by-value and the )~-calculus. Theoretical Computer Science, 1:125- 159, 1975.
• RW91: Erik Ruf , Daniel Weise, Using types to avoid redundant specialization, ACM SIGPLAN Notices, v.26 n.9, p.321-333, Sept. 1991
• Sch85: 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]
• Sch86: David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986
• Ses86: Peter. Sestoft, The structure of a self-applicable partial evaluator, on Programs as data objects, p.257-281, April 1986, Copenhagen, Denmark
• Ses89: Peter Sestoft, Replacing function parameters by global variables, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.39-53, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99374]
• Ste78: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters; Compilers

General Terms:
Algorithms, Design, Languages