COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
An Architecture for Combinator Graph Reduction - 1st Edition - ISBN: 9780124192409, 9781483270463

An Architecture for Combinator Graph Reduction

1st Edition

0.0 star rating Write a review
Author: Philip John Koopman
eBook ISBN: 9781483270463
Imprint: Academic Press
Published Date: 28th October 1990
Page Count: 172
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


An Architecture for Combinator Graph Reduction examines existing methods of evaluating lazy functional programs using combinator reduction techniques, implementation, and characterization of a means for accomplishing graph reduction on uniprocessors, and analysis of the potential for special-purpose hardware implementations.

Comprised of eight chapters, the book begins by providing a background on functional programming languages and existing implementation technology. Subsequent chapters discuss the TIGRE (Threaded Interpretive Graph Reduction Engine) methodology for implementing combinator graph reduction; the TIGRE abstract machine, which is used to implement the graph reduction methodology; the results of performance measurements of TIGRE on a variety of platforms; architectural metrics for TIGRE executing on the MIPS R2000 processor; and the potential for special-purpose hardware to yield further speed improvements. The final chapter summarizes the results of the research, and suggests areas for further investigation.

Computer engineers, programmers, and computer scientists will find the book interesting.

Table of Contents

List of Tables

List of Illustrations


1. Introduction

1.1. Overview of the Problem Area

1.2. Organization of this Book

2. Background

2.1. Problem Definition

2.1.1. Lazy Functional Programming

2.1.2. Closure Reduction and Graph Reduction

2.1.3. Performance Inefficiencies

2.2. Previous Research

2.2.1. Miranda

2.2.2. Hyperlazy Evaluation

2.2.3. The G-Machine

2.2.4. TIM

2.2.5. NORMA

2.2.6. The Combinatorgraph Reducer

2.2.7. Analysis and Summary

2.3. Approach of this Research

3. Development of the TIGRE Method

3.1. THE Conventional Graph Reduction Method

3.2. Fast Interpretive Execution of Graphs

3.3. Direct Execution of Graphs

4. Implementation of the TIGRE Machine

4.1. THE TIGRE Abstract Machine

4.1.1. Hardware Definition

4.1.2. TIGRE Assembly Language

4.1.3. A TIGRE Compiler

4.2. Mapping of TIGRE onto Various Execution Models

4.2.1. Mapping of TIGRE Onto the C Execution Model

4.2.2. Mapping of TIGRE Assembly Language Onto a VAX

4.2.3. Mapping of TIGRE Assembly Language Onto a MIPS R2000

4.2.4. Translation to Other Architectures

4.3. TIGRE Assembler Definitions of Combinators

4.3.1. Non-Strict Combinatore

4.3.2. Strict Combinatore

4.3.3. List Manipulation Combinators

4.3.4. Supercombinators

4.4. Software Support

4.4.1. Garbage Collection

4.4.2. Other Software Support

5. TIGRE Performance

5.1. TIGRE Performance on Various Platforms

5.1.1. TIGRE Performance for the Turner Set

5.1.2. TIGRE Performance for Supercombinator Compilation

5.2. Comparisons with Other Methods

5.2.1. Miranda

5.2.2. Hyperlazy Evaluation

5.2.3. The G-Machine

5.2.4. TIM

5.2.5. NORMA

5.3. TIGRE versus other Languages

5.3.1. Non-Lazy Language: T Version 3.0

5.3.2. Imperative Language: MIPS R2000 C Compiler

5.4. Analysis of Performance

6. Architectural Metrics

6.1. Cache Behavior

6.1.1. Exhaustive Search of the Cache Design Space

6.1.2. Parametric Analysis

6.1.3. A Desirable Cache Strategy

6.2. Performance of Real Hardware

6.2.1. Simulation Results for a DECstation 3100

6.2.2. Comparison with Actual Measurements

6.3. Dynamic Program Behavior

6.3.1. Heap Memory Use

6.3.2. Stack Memory Use

7. The Potential of Special-Purpose Hardware

7.1. DECstation 3100 as a Baseline

7.2. Improvements in Cache Management

7.2.1. Copy-Back Cache

7.2.2. Increased Block Size

7.2.3. Prefetch on Read Misses

7.3. Improvements in CPU Architecture

7.3.1. Stack Unwinding Support

7.3.2. Stack Access Support

7.3.3. Doubleword Store

7.4. Performance Improvement Possibilities

8. Conclusions

8.1. Contributions of this Research

8.2. Areas for Further Research

Appendix A. A Tutorial on Combinator Graph Reduction

A.1. Functional Programs

A.2. Mapping Functional Programs to Lambda Calculus

A.3. Mapping Lambda Calculus to SK-Combinators

A.4. Mapping SK-Combinator Expressions onto a Graph

A.5. The Turner Set of Combinators

A.6. Supercombinators

A.7. Inherent Parallelism in Combinator Graphs

Appendix B. Selected TIGRE Program Listings










No. of pages:
© Academic Press 1990
28th October 1990
Academic Press
eBook ISBN:

About the Author

Philip John Koopman

Ratings and Reviews