Architecture for Combinator Graph Reduction (eBook)

Philip John Koopman (Autor)

eBook Download: PDF

2014 | 1. Auflage
172 Seiten
Elsevier Science (Verlag)
9781483270463 (ISBN)

Infos

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.

Inhalt

Front Cover 1
An Architecture for Combinator Graph Reduction 4
Copyright Page 5
Table of Contents 8
List of Tables 12
List of Illustrations 14
Preface 16
Chapter 1. Introduction 18
1.1. OVERVIEW OF THE PROBLEM AREA 18
1.2. ORGANIZATION OF THIS BOOK 20
Chapter 2. Background 22
2.1. PROBLEM DEFINITION 22
2.2. PREVIOUS RESEARCH 26
2.3. APPROACH OF THIS RESEARCH 31
Chapter 3. Development of the TIGRE Method 32
3.1. THE CONVENTIONAL GRAPH REDUCTION METHOD 32
3.2. FAST INTERPRETIVE EXECUTION OF GRAPHS 34
3.3. DIRECT EXECUTION OF GRAPHS 36
Chapter 4. Implementation of the TIGRE Machine 42
4.1. THE TIGRE ABSTRACT MACHINE 42
4.2. MAPPING OF TIGRE ONTO VARIOUS EXECUTION MODELS 48
4.3. TIGRE ASSEMBLER DEFINITIONS OF COMBINATORS 54
4.4. SOFTWARE SUPPORT 62
Chapter 5. TIGRE Performance 66
5.1. TIGRE PERFORMANCE ON VARIOUS PLATFORMS 66
5.2. COMPARISONS WITH OTHER METHODS 71
5.3. TIGRE VERSUS OTHER LANGUAGES 74
5.4. ANALYSIS OF PERFORMANCE 76
Chapter 6. Architectural Metrics 80
6.1. CACHE BEHAVIOR 80
6.2. PERFORMANCE OF REAL HARDWARE 95
6.3. DYNAMIC PROGRAM BEHAVIOR 101
Chapter 7. The Potential of Special-Purpose Hardware 106
7.1. DECSTATION 3100 AS A BASELINE 106
7.2. IMPROVEMENTS IN CACHE MANAGEMENT 107
7.3. IMPROVEMENTS IN CPU ARCHITECTURE 109
7.4. PERFORMANCE IMPROVEMENT POSSIBILITIES 111
Chapter 8. Conclusions 114
8.1. CONTRIBUTIONS OF THIS RESEARCH 114
8.2. AREAS FOR FURTHER RESEARCH 115
Appendix A: A Tutorial on Combinator Graph Reduction 118
A.l. FUNCTIONAL PROGRAMS 118
A.2. MAPPING FUNCTIONAL PROGRAMS TO LAMBDA CALCULUS 119
A.3. MAPPING LAMBDA CALCULUS TO SK-COMBINATORS 120
A.4. MAPPING SK-COMBINATOR EXPRESSIONS ONTO A GRAPH 122
A.5. THE TURNER SET OF COMBINATORS 134
A.6. SUPERCOMBINATORS 137
A.7. INHERENT PARALLELISM IN COMBINATOR GRAPHS 138
Appendix B: Selected TIGRE Program Listings 140
B.l. REDUCE.H 140
B.2. KERNEL.C 143
B.3. TIGRE.S 146
B.4. MIPS.S 153
B.5. HEAP.H 161
B.6. HEAP.C 162
References 166
Index 170

Produkt-Details

• Erscheint lt. Verlag: 12.5.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Informatik ► Weitere Themen ► Hardware
• ISBN-13: 9781483270463 / 9781483270463