JFLP: Volume 1996, Article 4

The Journal of Functional and Logic Programming

Volume 1996

Article 4

Published by The MIT Press . Copyright 1996 Massachusetts Institute of Technology.

Your institution may already be a subscriber to JFLP. If not, please subscribe for legitimate access to all journal articles.

Better Consumers for Program Specializations

Wei-Ngan Chin and Siau-Cheng Khoo

13 November 1996

Abstract

It is well known that not all programs are susceptible to automatic program specialization. Traditionally, complicated analyses are performed before actual specialization, in order to uncover as much of the useful program properties as possible. This is particularly the case for automatic program transformers that specialize function calls with arguments containing only constructors and variables.

We describe a novel approach for achieving better program specialization by preprocessing a program before subjecting it to actual specialization. The preprocessing phase involves simple syntactic analyses and program transformation, which is based on the well-understood fold/unfold strategy with generalization on terms. We ensure the termination of the transformation used in this phase, and outline a proof of its total correctness. Our approach greatly simplifies the task of program specialization in the later stage. Compared to other existing semantics-based approaches, our syntax-based method is considerably simpler, yet still widely applicable.

Our approach is formulated for nonstrict first-order programs. It can help obtain programs that are more susceptible to a variety of program specializers, including partial evaluation, deforestation, and the elimination of repeated pattern testing.

The following versions of the article are available:

• Preformatted versions of the article (compressed with gzip )
  • DVI (gzip'ped 64 kb)
  • PostScript (gzip'ped 122 kb)
• Source materials for custom formatting
  • LaTeX ( JFLP-A96-04.tex , gzip'ped 36 kb)
  • BIBTeX ( JFLP-A96-04.bib , gzip'ped 2 kb)
  • Parameter settings for custom formatting ( cjropts.tex , 117 bytes)

You can find this article also on the ftp-server of The MIT Press (access may be faster from some sites).

Self citation

    @article{jflp96-04,
      author={Wei-Ngan Chin and Siau-Cheng Khoo},
      title={Better Consumers for Program Specializations},
      journal={Journal of Functional and Logic Programming},
      volume={1996},
      number={4},
      publisher={The MIT Press},
      month={November},
      year={1996}
    }

Main page