Suchen und Finden
Mehr zum Inhalt
An Architecture for Combinator Graph Reduction - Architecture for Combinator Graph Reduction
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
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.