Constructor specialization

ABSTRACT

In the section on “challenging problems” in the proceedings from the first international workshop on partial evaluation and mixed computation [BEJ88] a question is stated: “Can PE be used to generate new specialized data types, in a way analogous to generating specialized functions”. Since then little has been done to address this problem. In [Lau89], new types are indeed generated, but they are all simpler versions of the types in the original program. It is, e.g. not possible to have types with more constructors than the types in the original program. I propose to alleviate this by means of constructor specialization. Constructors are specialized with respect to the static parts of their arguments, just like residual functions. I show how this is done and argue that it makes it possible to get good results from partial evaluation in cases where the traditional methods fail to produce satisfactory results. The discussion is centered around a small subset of Standard ML, but the idea applies equally well to other languages having user defined constructors, e.g. Haskell and Prolog.

REFERENCES

• BEJ88: D. Bj0rner, A.P. Ershov, and N.D. Jones, editors. Partial Evaluation and Mixed Computation. Proceedings o} the IFIP TC2 Workshop, Gammel A vernaes, Denmark, October 1987. Amsterdam: North-Holland, 1988.
• Bon91: A. Bondorf. Compiling laziness by partial evaluation. In S.L. Peyton Jones, G. Hutton, and C. Kehler Holst, editors, Functzonal Programming, Glasgow 1990, pages 9-22, Berlin: Springer-Verlag, 1991.
• Bon93: A. Bondorf. S, milix Manual, System Version 5.0. Technical Report, DIKU, University of Copenhagen, Denmark, 1993.
• Bul88: M.A. Bulyonkov. A theoretical approach to polyvariant mixed computation. In D. Bjcrner, A.P. Ershov, and N.D. Jones, editors, Partial Evaluation and M, xed Computation, pages 51- 64, Amsterdam: North-Holland, 1988.
• DNBDV91: Anne De Niel , Eddy Bevers , Karel De Vlaminck, Program bifurcation for a polymorphically typed functional language, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.142-153, June 17-19, 1991, New Haven, Connecticut, United States
• GJ91: C.K. Goraard and N.D. Jones. A partial evaluator for the untyped lambda-calculus. Journal of Functional Programming, 1(1):21-69, January 1991.
• GR92: M. Gengler and B. Rytz. A polyvariant binding time analysis handling partially known values. In M. Billaud et M., editors, WSA '92, Static Analysis, Bordeaux, France, September 1992. Bigre vols 81-82, 1992, pages 322-330, Rennes: IRISA, 1992.
• 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
• HH91: C.K. ttolst and J. Hughes. Towards bindingtime improvement for free. In S.L. Peyton Jones, G. I-Iutton, and C. Kehler Holst, editors, Functional Programming, Glasgow 1990, pages 83-100, Berlin: Springer-Verlag, 1991.
• HL91: C.K. Holst and J. Launchbury. Hanclwrltln~ cogen to avoid problems with static typing. In Draft Proceedings, Fourth Annual Glasgow Workshop on Functional Programming, Skye, Scotland, pages 210-218, Glasgow University, 1991.
• JSS85: Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, December 1985, Dijon, France
• JSS89: N.D. Jones, P. Sestoft, and H. Sondergaard. Mix: a self-applicable partial evaluator for experiments ia compiler generation. Lisp and Symbolic ('o,aputation, 2(1):9-50, 1989.
• Lau89: J. Launchbury. Projection Factorisations in Partial Evaluation. PhD thesis, Department of Computing, University of Glasgow, November 1989. Revised version in {Lau91a}.
• Lau91a: John Launchbury, Projection factorisations in partial evaluation, Cambridge University Press, New York, NY, 1991
• Lau91b: John Launchbury, A strongly-typed self-applicable partial evaluator, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.145-164, June 1991, Cambridge, Massachusetts, United States
• MB93: T. Mogensen and A. Bondorf. Logimix: a self-applicable partial evaluator for Prolog. In K.-K. Lay and T. Clement, editors, LOPSTR 92. Workshops in Computing, Berlin: Springer- Verlag, January 1993.
• Mog88: T. Mogensen. Partially static structures in a self-applicable partial evaluator. In D. Bj0rner, A.P. Ershov, and N.D. Jones, editors, Partial Evaluation and Mixed Computation, pages 325-347, Amsterdam: North-Holland, 1988.
• Mog89: Torben Æ. Mogensen, Binding Time Analysis for Polymorphically Typed Higher Order Languages, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 2: Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Current Issues in Programming Languages, p.298-312, March 13-17, 1989
• Mog92: T. Mogensen. Self-applicable partial evaluation for pure lambda calculus. In Part, al Evaluation and Semantics-Based Program Manipulat, on, San Francisco, California, June 199P (Technical Report YALEU/DCS/RR.909), pages 116- 121, New Haven, CT: Yale University, 1992.
• Mos93: Christian Mossin, Partial evaluation of general parsers, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.13-21, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154632]
• MTH90: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• Rom90: S. A. Romanenko, Arity raiser and use in program specialization, Proceedings of the third European symposium on programming on ESOP '90, p.341-360, May 1990, Copenhagen, Denmark
• Ses86: Peter. Sestoft, The structure of a self-applicable partial evaluator, on Programs as data objects, p.257-281, April 1986, Copenhagen, Denmark

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Standard ML
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Languages