Hostname: page-component-8448b6f56d-m8qmq Total loading time: 0 Render date: 2024-04-23T08:27:23.091Z Has data issue: false hasContentIssue false
  • English
  • Français

Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Simon L. Peyton Jones
Simon L. Peyton Jones
Affiliation:
Department of Computing Science, University of GlasgowG12 8QQ, UKsimonpj@dcs.glasgow.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The Spineless Tagless G-machine is an abstract machine designed to support non-strict higher-order functional languages. This presentation of the machine falls into three parts. Firstly, we give a general discussion of the design issues involved in implementing non-strict functional languages. Next, we present the STG language, an austere but recognizably-functional language, which as well as a denotational meaning has a well-defined operational semantics. The STG language is the ‘abstract machine code’ for the Spineless Tagless G-machine. Lastly, we discuss the mapping of the STG language onto stock hardware. The success of an abstract machine model depends largely on how efficient this mapping can be made, though this topic is often relegated to a short section. Instead, we give a detailed discussion of the design issues and the choices we have made. Our principal target is the C language, treating the C compiler as a portable assembler.

Type
Articles
Information
Journal of Functional Programming , Volume 2 , Issue 2 , April 1992 , pp. 127 - 202
Copyright
Copyright © Cambridge University Press 1992

References

Alverson, R., Callahan, D., Cummings, B., Koblenz, B., Porterfield, A. and Smith, B. 1990. The Tera computer system. In Proceedings of the International Conference on Supercomputing, Amsterdam, the Netherlands.Google Scholar
Appel, A.W. 1987. Garbage collection can be faster than stack allocation. Info. Proc. Lett, 25: 275–279.CrossRefGoogle Scholar
Appel, A.W. 1992. Compiling with continuations, Cambridge University Press.Google Scholar
Appel, A.W. 1989. Simple generational garbage collection and fast allocation Software – Practice and Experience, 19: 171–183.CrossRefGoogle Scholar
Appel, A.W. and Jim, T. 1989. Continuation-passing, closure-passing style. In Proceedings of the ACM Conference on Principles of Programming Languages, pp. 293–302. ACM.Google Scholar
Ariola, Z.M. and Arvind. 1991. A syntactic approach to program transformations. In Symposium on Partial Evaluation and Semantics-Based Program Manipulation, Yale, CT.Google Scholar
Augustsson, L. 1987. Compiling Lazy Functional Languages, Part II. PhD thesis, Chalmers University, Sweden.Google Scholar
Augustsson, L. and Johnsson, T. 1989. Parallel graph reduction with the 〈v,G〉-machine. In Proceedings of the IFIP Conference on Functional Programming Langauges and Computer Architecture, London.Google Scholar
Baker, H. 1978. List processing in real time on a serial computer. Communications of the ACM, 21: 280–294.CrossRefGoogle Scholar
Bartlett, J.F. 1989. SCHEME to C: a portable Scheme-to-C compiler, DEC WRL RR 89/1.Google Scholar
Bloss, A., Hudak, P. and Young, J. 1988. Code optimizations for lazy evaluation. Lisp and Symbolic Computation, 1: 147–164.CrossRefGoogle Scholar
Burn, G., Peyton Jones, S.L. and Robson, J. 1988. The Spineless G-machine. In Proceedings of the Conference on Lisp and Functional Programming, pp. 244–258. ACM.Google Scholar
Consel, C. and Danvy, O. 1991. For a better support of static data flow. In J., Hughes (editor), Functional Programming Langauges and Computer Architecture, Boston, MA. In volume 523 of Lecture Notes in Computer Science, Springer-Verlag, pp. 496–519.CrossRefGoogle Scholar
Cooper, E.C. and Morrisett, J.G. 1990. Adding threads to Standard ML. CMU-CS-90-186, Carnege Mellon University.Google Scholar
Davie, A.J.T., and McNally, D.J. 1989. CASE – a lazy version of an SECD machine with a flat environment. In Proc IEEE TENCON, Bombay, India.Google Scholar
Fairbairn, J. and Wray, S. 1987. TIM – a simply lazy abstract machine to execute supercombinators. In G., Kahn (editor), Proceedings of the IFIP Conference on Functional Programming Languages and Computer Architecture, Portland, OR. In volume 274 of Lecture Notes in Computer Science, Springer-Verlag, pp. 34–45.CrossRefGoogle Scholar
Field, A.J. and Harrison, P.G. 1988. In Functional Programming Addison Wesley.Google Scholar
Fradet, P. and Le Metayer, D. 1991. Compilation of functional languages by program transformation. ACM Trans. Programming Languages and Systems, 13 (01).CrossRefGoogle Scholar
Hammond, K., Peyton Jones, S.L. and Wadler, P.L. 1992. A new input-output model for purely-functional languages, University of Glasgow (02).Google Scholar
Henderson, P. 1980. Functional programming: application and implementation Prentice Hall.Google Scholar
Hieb, R., Dybvig, R.K. and Bruggeman, C. 1990. Representing control in the presence of first-class continuations. In Proc. Conference on Programming Language Design and Implementation (PLDI 90) (06).Google Scholar
Hudak, P., Jones, S.L. Peyton, Wadler, P.L., Boutel, B., Fairbairn, J., Fasel, J., Guzman, M., Hammond, K., Hughes, J., Johnsson, T., Kieburtz, R., Nikhil, R.S., Partain, W and Peterson, J. 1992. Report on the functional programming language Haskell, Version 1.2. SIGPLAN Notices.CrossRefGoogle Scholar
Hughes, J. 1989. Why functional programming matters. The Computer Journal, 32: 98–107 (04).CrossRefGoogle Scholar
Ingerman, P.Z. 1961. Thunks. Communications of the ACM, 4:55–58.CrossRefGoogle Scholar
Ireland, E. 1992. The Lazy Functional Abstract Machine. In Proc. 15th Australian Computer Science Conference, Hobart. World Scientific Publishing.Google Scholar
Johnsson, T. 1985. Lambda lifting: transforming programs to recursive equations. In Jouannaud, (editor), Proc. IFIP Conference on Functional Programming and Computer Architecture. In volume 201 of Lecture Notes in Computer Science, Springer-Verlag, pp. 190–205.Google Scholar
Johnsson, T. 1987. Compiling Lazy Functional Languages. PhD thesis, Chalmers University, Göteborg, Sweden.Google Scholar
Johnsson, T. 1984. Efficient compilation of lazy evaluation. In Proc. SIGPLAN Symposium on Compiler Construction, Montreal, Canada (06).Google Scholar
Jones, R. 1991. Tail Recursion Without Space Leaks, Department of Computer Science, University of Kent (03).Google Scholar
Kelsey, R. 1989. Compilation by Program Transformation. YALEU/DCS/RR-702, PhD thesis, Department of Computer Science, Yale University (05).Google Scholar
Kieburtz, R.B. 1987. A RISC architecture for symbolic computation. In Proc. ASPLOS II (10).Google Scholar
Kieburtz, R.B. and Agapiev, B. 1988. Optimizing the evaluation of suspensions. In Proc. Workshop on Implementation of Lazy Functional Languages, Aspenas (09).Google Scholar
Kingdon, H., Lester, D. and Burn, G.L. 1991. The HDG-machine: a highly distributed graph reducer for a transputer network. Computer Journal, 34:290–302.CrossRefGoogle Scholar
Koopman, P.W.M. 1990. Functional Programs as Executable Specifications. PhD thesis, University of Nijmegen.Google Scholar
Kranz, D.A. 1988. ORBIT – An Optimising Compiler for Scheme. PhD thesis, Department of Computer Science, Yale University.Google Scholar
Landin, P.J. 1965. A correspondence between Algol 60 and Church's lambda calculus, Communications of the ACM, 8:158–165 (03).CrossRefGoogle Scholar
Lester, D. 1989. Combinator Graph Reduction: A Congruence and its Applications. PhD Thesis, Programming Research Group, Oxford.Google Scholar
Meijer, E. 1988. Generalised expression evaluation. In Proc. Workshop on Implementation of Lazy Functional Languages, Aspenas (09).Google Scholar
Miranda, E. 1991. How to do machine-independent fast threaded code. Queen Mary and West-field College, London (04).Google Scholar
Peyton Jones, S.L. 1987. The implementation of functional programming languages, Prentice Hall.Google Scholar
Peyton Jones, S.L. 1988. FLIC – a functional language intermediate code. SIGPLAN Notices, 23.Google Scholar
Peyton Jones, S.L., Clack, C. and Salkild, J. High-performance parallel graph reduction. In Odijk, E., Rem, M. and Syre, J.-C (editors) Proc. Parallel Architectures and Languages Europe (PARLE). In volume 365 of Lecture Notes in Computer Science, Springer-Verlag, pp. 193–206.CrossRefGoogle Scholar
Peyton Jones, S.L. and Launchbury, J. 1991. Unboxed values as first class citizens. In Hughes, J. (editor), Functional Programming Languages and Computer Architecture, Boston.Google Scholar
Peyton Jones, S.L. and Lester, D. 1991. A modular fully-lazy lambda lifter in HASKELL. Software – Practice and Experience, 21 (05).Google Scholar
Peyton Jones, S.L. and Lester, D.R. 1992. Implementing functional languages: a tutorial. Prentice Hall.Google Scholar
Peyton Jones, S.L. and Salkind, J. 1989. The Spineless Tagless G-machine. In MacQueen, D. (editor), Functional Programming Languages and Computer Architecture. Addison Wesley.Google Scholar
Runciman, C. and Wakeling, D. 1992. Heap profiling of lazy functional programs. Department of Computer Science, University of York.Google Scholar
Sansom, P. 1991. Combining copying and compacting garbage collection. In Proc. Fourth Annual Glasgow Workshop on Functional Programming, Springer-Verlag Workshops in Computer Science.Google Scholar
Scheevel, M. 1986. NORMA – a graph reduction processor. In Proc. ACM Conference on Lisp and Functional Programming.Google Scholar
Smetsers, S., Nocker, E., van Groningen, J. and Plasmeier, R. 1991. Generating efficient code for lazy functional languages. In Functional Programming Languages and Computer Architecture, J., Boston, Hughes, (editor).Google Scholar
Stallman, R.M. 1992. Using and porting Gnu CC, Version 2.0. Free Software Foundation Inc.Google Scholar
Steele, G.L. 1978. Rabbit: a compiler for Scheme. AI-TR-474, MIT Lab for Computer Science.Google Scholar
Stoye, W., Clarke, T. and Norman, A. 1984. Some practical methods for rapid combinator reduction. In Proc. 1984 ACM Symposium on Lisp and Functional Programming, 159–166 (08).CrossRefGoogle Scholar
Tarditi, D., Archarya, A. and Lee, P. 1991. No assemby required: compiling Standard ML to C. School of Computer Science, Carnegie Mellon University (03).Google Scholar
Tolmach, A.P. and Appel, A.W. 1990. Debugging Standard ML without reverse engineering. In Proc. ACM Conference on Lisp and Functional Programming, Nice (06). ACM.Google Scholar
Turner, D.A. 1979. A new implementation technique for applicative languages, Software – Practice and Experience, 9:31–49.CrossRefGoogle Scholar
Wadler, P. 1987. Efficient compilation of pattern matching. In Peyton Jones, S.L. (editor), The implementation of functional programming languages, Prentice Hall, 78–103.Google Scholar
Wilson, P.R., Lam, M.S. and Moher, T.G. 1992. Caching considerations for generational garbage collection. Department of Computer Science, University of Texas (01).CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.