An Architecture for Combinator Graph Reduction

List of TablesList of IllustrationsPreface1. Introduction 1.1. Overview of the Problem Area 1.2. Organization of this Book2. 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 Research3. Development of the TIGRE Method 3.1. THE Conventional Graph Reduction Method 3.2. Fast Interpretive Execution of Graphs 3.3. Direct Execution of Graphs4. 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 Support5. 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 Performance6. 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 Use7. 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 Possibilities8. Conclusions 8.1. Contributions of this Research 8.2. Areas for Further ResearchAppendix 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 GraphsAppendix B. Selected TIGRE Program Listings B.1. REDUCE.H B.2. KERNEL.C B.3. TIGRE.S B.4. MIPS.S B.5. HEAP.H B.6. HEAP.CReferencesIndex