Lazy Functional Languages: Abstract Interpretation and Compilation (Research Monographs in Parallel and Distributed Computing) [Paperback]

Pitman Publishing (Author)

Book Description

Publication Date: August 28, 1991 | ISBN-10: 0262521601 | ISBN-13: 978-0262521604

The class of programming languages commonly known as functional includes Lisp, Scheme, ML, and Miranda TM. This book explores a subclass known as lazy functional languages, beginning with the theoretical issues and continuing through abstract interpretation and offering improved techniques for implementation.Now that advanced compiler technology has made it possible for lazy functional languages to compare favorably in run-time with more traditional languages such as C and Pascal, this monograph tackles problems of implementation such as time and memory overheads and restrictions on parallelism. Specifically, it describes a more efficient implementation model, the evaluation transformer model, that can be used when information is known about how functions use their arguments, develops a semantically sound analysis technique called abstract interpretation, which can determine this information, and shows how to use the information to compile more efficient code for sequential and parallel machines.Geoffrey Burn is Lecturer at Imperial College of Science, Technology, and Medicine, London.Contents: Introduction. Operational and Denotational Semantics of the Typed Lambda Calculus. A Framework for the Abstract Interpretation of Functional Languages. Some Example Abstract Interpretations. Evaluation Transformers. Implementing Functional Languages on Sequential and Parallel Machines. Relationship to Other Work. Epilogue. Appendixes: Additional Proofs. The Spineless G-Machine.

Editorial Reviews

About the Author

This book explores a subclass known as lazy functional languages, beginning with the theoretical issues and continuing through abstract interpretation and offering improved techniques for implementation.

Product Details

• Paperback: 252 pages
• Publisher: The MIT Press (August 28, 1991)
• Language: English
• ISBN-10: 0262521601
• ISBN-13: 978-0262521604
• Product Dimensions: 10.9 x 8.2 x 0.6 inches
• Shipping Weight: 1.3 pounds (View shipping rates and policies)
• Average Customer Review: 4.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #2,818,296 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

2 of 2 people found the following review helpful:

4.0 out of 5 stars Table of Contents, March 16, 2001

By 

"kimbly_b" (Boston, MA USA) - See all my reviews

This review is from: Lazy Functional Languages: Abstract Interpretation and Compilation (Research Monographs in Parallel and Distributed Computing) (Paperback)

Preface
List of figures
1 Introduction
1.1 Functional Programming Languages and Lazy Evaluation
1.2 The Evaluation Transformer Model of Reduction
1.3 An Introduction to Abstract Interpretation
1.4 Outline of Book
2 Operational and Denotational Semantics of the Typed Lambda Calculus
2.1 The Typed Lambda-Calculus
2.2 Sets with Structure
2.3 Interpretations
2.4 A Result Relating the Operational Semantics and Standard Interpretations of AT

2.5 Drawing it Together
3 A Framework for the Abstract Interpretation of Functional Languages
3.1 The Abstract Interpretation of AT
3.2 Abstraction and Concretisation Maps
3.3 Correctness of the Framework
3.4 Drawing it Together
4 Some Example Abstract Interpretations
4.1 An Abstract Interpretation for Evaluation Transformers
4.2 On Defining Abstract Domains
4.3 A Systematic Approach to Deriving Abstract Domains for Lists and Trees
4.4 Drawing it Together
5 Evaluation Transformers
5.1 Safe Changes to the Evaluation Strategy
5.2 Definition of Evaluators
5.3 Determining Evaluation Transformers
5.4 Drawing it Together
6 Implementing Functional Languages on Sequential and Parallel Machines
6.1 Graph Reduction
6.2 The Spineless G-machine
6.3 Relating the Graph Reduction Model to the Typed Lambda Calculus
6.4 Compiling Code for Evaluation Transformers
6.5 Drawing it Together
7 Relationship to Other Work
7.1 Abstract Interpretation
7.2 Polymorphism
7.3 Other Program Analysis Techniques
7.4 Implementation of Lazy Functional Languages
8 Epilogue
A Proofs Omitted in Earlier Chapters
B The Spineless G-Machine
B.1 Compilation Rules
B.2 Initial G-machine state
B.3 An Interpreter for the Spineless G-Machine
Bibliography
Index of Symbols
Index

2 of 2 people found the following review helpful:

5.0 out of 5 stars I enjoyed it., April 19, 1999

By A Customer

This review is from: Lazy Functional Languages: Abstract Interpretation and Compilation (Research Monographs in Parallel and Distributed Computing) (Paperback)

Forced into the world of denotational semantics of functional languages, I found this book actually quite interesting and informative. Using lattice theory to look at the properties of functional evaluation provides for hours of entertaining reading.