G. L. Burn
S. L. Peyton Jones
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.
- 1.Augustsson, L., Compiling Lazy Functional Languages, Part II PhD Thesis, Department of Computer Sciences, Chalmers University of Technology, 1!}87.Google Scholar
- 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.Google ScholarDigital Library
- 3.Fairbaim, J., and Wray, S.C., Code Generation Techniques for Functional Languages, Proceedings 1986 ACM Conference on Lisp and Functional Programming, 4-6 August, 1987, Cambridge, Massachusetts, USA, pp. 94-104. Google ScholarDigital Library
- 4.Fairbaim, J., and Wray, S., TIM: A Simple, Lazy Abstract Machine To Execute Supercombinators, in: Kahn, G., (ed.), Proceedings of the Third International Conference on Functional Languages and Computer Architecture, Portland, Oregon, USA, 14-16 September, 1987, Springer-Verlag LNCS 274, pp. 34-45. Google Scholar
- 5.Goldberg, B., Detecting Sharing of Partial Applications in Functional Languages, in Kahn, G., (ed.) Proceedings of the Third International Conference on Functional Programming Languages and Computer Architecture, Portland, Oregon, USA, 14-16 Sept., 1987, Springer Verlag LNCS vol. 274, pp. 408-425. Google ScholarDigital Library
- 6.Hankin, C.L., Bum, G.L., and Peyton Jones, S.L., A Safe Approach to Parallel Combinator Reduction (Extended Abstract), Proceedings ESOP 86 (European Symposium on Programming), Saarbmcken, Federal Republic of Germany, March 1986, Robinet, B., and Wilhelm, R. (eds.), Springer-Verlag LNCS 213, pp. 99-110. Google ScholarDigital Library
- 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.Google Scholar
- 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.)Google Scholar
- 9.Johnsson, T., Lambda Lifting: Transforming Programs to Reeursive Equations, in :Proceedings of IFIP International Conference on Ft~nctional Prograrruning Languages and Computer Architect~e, Nancy, France, 16-19 September, 1985, Jouannaud, J.-P. (ed.), Springer-Verlag LNCS 201, pp. 190-203. Google ScholarDigital Library
- 10.lohnsson, T., Compiling Lazy Functional Languages, PhD Thesis, Department of Computer Sciences, Chalmers University of Technology, 1987.Google Scholar
- 11.Mycroft, A., Abstract Interpretation and Optimising Transformations for Applicative Programs, PhD. Thesis, University of Edinburgh, 1981.Google Scholar
- 12.Peyton Jones, S.L., The Implementation of Functional Programming Languages, Prentiee-HaU International Series in Computer Science, 1987. Google ScholarDigital Library
- 13.Peyton Jones, S.L., The tag is dead - long live the packet, Distributed on the fp mailboard, 22nd October, 1987.Google Scholar
- 14.Turner, D.A., A New Implementation Technique for Applicative Languages, Software Practice and Experience 9, 1979, pp. 31-49.Google ScholarCross Ref
- 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.)Google Scholar
Index Terms
- The spineless G-machine
Recommendations
The spineless tagless G-machine
FPCA '89: Proceedings of the fourth international conference on Functional programming languages and computer architectureThe spineless tagless G-machine, naturally
ICFP '98: Proceedings of the third ACM SIGPLAN international conference on Functional programmingThe application of natural semantic specifications of lazy evaluation to areas such as usage analysis, formal profiling and abstract machine construction has shown it to be a useful formalism. This paper introduces several variants and extensions of ...
Compiling Lazy Functional Programs Based on the Spineless Tagless G-Machine for the Java Virtual Machine
FLOPS '01: Proceedings of the 5th International Symposium on Functional and Logic ProgrammingA systematic method of compiling lazy functional programs based on the Spineless Tagless G-machine (STGM) is presented for the Java Virtual Machine (JVM). A new specification of the STGM, which consists of a compiler and a reduction machine, is ...
Comments