JFLP: Volume 1996, Article 3

The Journal of Functional and Logic Programming

Volume 1996

Article 3

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.

Compile-Time Pointer Reversal

Simon Brock

13 September 1996

Abstract

This paper introduces an alternative representation for lambda terms which has the notable property that the search for the leftmost outermost redex is restricted to two steps. This is important in the implementation of a lazy functional programming language, as this search consumes time and space. The representation introduced is similar to that resulting from the implementation technique of reversing pointers in the left spine of a term while traversing it, except that here the pointers in the left spine are reversed before reduction. This paper completely develops this new representation, including rigourous proofs of the correctness as a representation for lambda terms and a number of properties, such as the restriction on the search for the next redex. It is shown that the representation can be used with graphs, hence it can be used as the basis for an implementation of a lazy functional language. An implementation is introduced and its performance is compared with a conventional implementation, showing a notable increase in efficiency.

The following versions of the article are available:

• Preformatted versions of the article (compressed with gzip )
  • DVI (gzip'ped 36 kb); download figures separately
  • PostScript (gzip'ped 158 kb)
• Source materials for custom formatting
  • LaTeX ( JFLP-A96-03.tex , gzip'ped 21 kb)
  • BIBTeX ( JFLP-A96-03.bib , gzip'ped 2 kb)
  • PostScript Figure #1 ( JFLP-A96-03-f1.ps.gz , gzip'ped 10 kb)
  • PostScript Figure #2 ( JFLP-A96-03-f2.ps.gz , gzip'ped 10 kb)
  • PostScript Figure #3 ( JFLP-A96-03-f3.ps.gz , gzip'ped 10 kb)
  • PostScript Figure #4 ( JFLP-A96-03-f4.ps.gz , gzip'ped 10 kb)
  • PostScript Figure #5 ( JFLP-A96-03-f5.ps.gz , gzip'ped 10 kb)
  • PostScript Figure #6 ( JFLP-A96-03-f6.ps.gz , gzip'ped 11 kb)
  • PostScript Figure #7 ( JFLP-A96-03-f7.ps.gz , gzip'ped 10 kb)
  • PostScript Figure #8 ( JFLP-A96-03-f8.ps.gz , gzip'ped 10 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-03,
      author={Simon Brock},
      title={Compile-Time Pointer Reversal},
      journal={Journal of Functional and Logic Programming},
      volume={1996},
      number={3},
      publisher={The MIT Press},
      month={September},
      year={1996}
    }

Main page