An Architecture for Combinator Graph Reduction - Architecture for Combinator Graph Reduction

An Architecture for Combinator Graph Reduction - Architecture for Combinator Graph Reduction

von: Philip John Koopman

Elsevier Reference Monographs, 2014

ISBN: 9781483270463 , 172 Seiten

Format: PDF

Kopierschutz: DRM

Windows PC,Mac OSX Apple iPad, Android Tablet PC's

Preis: 29,69 EUR

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