Implementing lazy functional languages on stock hardware:

the Spineless Tagless G-machine ?

Version 2.5

Simon L Peyton Jones
Department of Computing Science, University of Glasgow G12 8QQ
[email protected]

March 17, 1993

Abstract

The Spineless Tagless G-machine is an abstract machine designed to support nonstrict 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 recognisably-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.

Version 2.5 of this paper (minus appendix) appears in the Journal of Functional Programming 2(2) (April 1992), pp127-202. The indexing in the published version is one page out throughout, due to a CUP typesetting bug.

Changes in Version 2.0: large new section on comparing the STG machine with other designs (Section 3); profiling material (Section 11); index.

Changes in Version 2.1: proper statement of the initial state of the machine (Section 5.1); reformulation of CAF updates (Section 10.8); new format for state transition rules, separating the guards which govern the applicability of the rules (such that") from the auxiliary definitions (where") | Section 5.

Changes in Version 2.2: introduction of the term lambda-form"; new subsection on lambda lifting (Section 4.5); discussion of copy-vs-share in Section 10.6; allow a variablebinding form of default alternative in algebraic case expressions.

Changes in Version 2.3: more explicit discussion of the translation into the STG language (Section 4.1); some re-ordering of sub-sections in Section 4; an overview of the code generation process at the start of Section 9.

Changes in Version 2.4: new-format profiling in Section 11; new section on black holes, saying how to avoid space leaks without black-holing (Section 9.3.3).

?Previously entitled The Spineless Tagless G-machine: a second attempt".