An Architecture for Combinator Graph Reduction

Philip John Koopman

• Publisher: Academic Press
• Year: 2014
• ISBN:
  9781483270463
• Topic: Computer Science
• Subtopic: Hardware
• Index: Computer Science

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

• Front Cover
• An Architecture for Combinator Graph Reduction
• Copyright Page
• Table of Contents
• List of Tables
• List of Illustrations
• Preface
• Chapter 1. Introduction
• Chapter 2. Background
• Chapter 3. Development of the TIGRE Method
• Chapter 4. Implementation of the TIGRE Machine
• Chapter 5. TIGRE Performance
• Chapter 6. Architectural Metrics
• Chapter 7. The Potential of Special-Purpose Hardware
• Chapter 8. Conclusions
• Appendix A: A Tutorial on Combinator Graph Reduction
• Appendix B: Selected TIGRE Program Listings
• References
• Index