1985 | ReviewPaper | Chapter
The G-machine: A fast, graph-reduction evaluator
Author : Richard B. Kieburtz
Published in: Functional Programming Languages and Computer Architecture
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The G-machine is an abstract architecture for evaluating functional-language programs by programmed graph reduction. Unlike combinator reduction, in which control is derived dynamically from the expression graph itself, control in programmed graph reduction is specified by a sequence of instructions derived by compiling an applicative expression.The G-machine architecture was defined by Thomas Johnsson and Lennart Augustsson (Gothenburg) as the evaluation model for a compiler for a dialect of ML with lazy evaluation rules. This paper describes a sequential evaluator based upon that abstract architecture. It discusses performance issues affecting reduction architectures, then describes the organization of a hardware design to address these issues. The interplay between compilation strategies and the computational engine is exploited in this design.Principal features of the design are (i) hardware support for graph traversal, (ii) a vertically microcoded, pipelined internal architecture, (iii) an instruction fetch and translation unit with very low latency, and (iv) a new memory architecture, one specifically suited to graph reduction and which can be extended to very large memories.