The spineless G-machine

ABSTRACT

Recent developments in functional language implementations have resulted in the G-machine, a programmed graph-reduction machine. Taking this as a basis, we introduce an optimised method of performing graph reduction, which does not need to build the spine of the expression being reduced. This Spineless G-machine only updates shared expressions, and then only when they have been reduced to weak head normal form. It is thus more efficient than the standard method of performing graph reduction. We begin by outlining the philosophy and key features of the Spineless G-machine, and comparing it with the standard G-machine. Simulation results for the two machines are then presented and discussed. The Spineless G-machine is also compared with Tim, giving a series of transformations by which they can be interconverted. These open up a wide design space for abstract graph reduction machines, which was previously unknown. A full specification of the spineless machine is given in the appendix, together with compilation rules for a simple functional language.

REFERENCES

• 1: Augustsson, L., Compiling Lazy Functional Languages, Part II PhD Thesis, Department of Computer Sciences, Chalmers University of Technology, 1!}87.
• 2: Bum, G.L., Hankin, C.L., and Abramsky, S., Strictness Analysis for Higher-Order Functions, Science of Computer Programming, 7, November 1986, pp.249-278.
• 3: Jon Fairbairn , Stuart C. Wray, Code generation techniques for functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.94-104, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319853]
• 4: John Fairbairn , Stuart Wray, TIM: A simple, lazy abstract machine to execute supercombinators, Proc. of a conference on Functional programming languages and computer architecture, p.34-45, October 1987, Portland, Oregon, United States
• 5: Benjamin Goldberg, Detecting sharing of partial applications in functional languages, Proc. of a conference on Functional programming languages and computer architecture, p.408-425, October 1987, Portland, Oregon, United States
• 6: C L Hankin , G L Burn , S L Peyton Jones, A safe approach to parallel combinator reduction, Proc. of the European symposium on programming on ESOP 86, p.99-110, March 1986, Saarbru:9Aicken, Germany
• 7: Hudak, P., and Young, J., A Set-Theoretic Characterisation of Function Strictness in the Lambda Calculus, Research Report YALEU/DCS/RR-391, Department of Computer Science, Yale University, 1985, Also presented at the Workshop on Abstract Interpretation, University of Kent at Canterbury, August, 1985.
• 8: Hughes, J., The Design and Implementation of Programming Languages, PhD Thesis, Oxford University, 1983. (Published as Oxford University Computing Laboratory, Progranuning Research Group, Technical Monograph PRG-40, September, 1984.)
• 9: Thomas Johnsson, Lambda lifting: transforming programs to recursive equations, Proc. of a conference on Functional programming languages and computer architecture, p.190-203, January 1985, Nancy, France
• 10: lohnsson, T., Compiling Lazy Functional Languages, PhD Thesis, Department of Computer Sciences, Chalmers University of Technology, 1987.
• 11: Mycroft, A., Abstract Interpretation and Optimising Transformations for Applicative Programs, PhD. Thesis, University of Edinburgh, 1981.
• 12: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 13: Peyton Jones, S.L., The tag is dead - long live the packet, Distributed on the fp mailboard, 22nd October, 1987.
• 14: Turner, D.A., A New Implementation Technique for Applicative Languages, Software Practice and Experience 9, 1979, pp. 31-49.
• 15: Wadler, P., Strictness Analysis on Non-Flat Domains (by Abstract Interpretation over Finite Domains), in Abramsky, S., and Ha.nkirh C., (eds), Abstract .Interpretation of Declarative Languages, Ellis Horwood, 1987. (Originally distributed on the FP mailboard November, 1985.)

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

General Terms:
Algorithms, Design, Languages, Performance