The Implementation of Functional Programming Languages

Describes how to translate a high-level functional language into an intermediate language, called the lambda calculus, and its implementation using lazy graph reduction.

**Tag(s):**
Functional Programming

**Publication date**: 31 Dec 1987

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
n/a

**Views**: 19,851

**Type**: N/A

**Publisher**:
n/a

**License**:
n/a

**Post time**: 01 Dec 2006 02:51:50

The Implementation of Functional Programming Languages

Describes how to translate a high-level functional language into an intermediate language, called the lambda calculus, and its implementation using lazy graph reduction.

Terms and Conditions:

Book Excerpts:

This book is about implementing functional programming languages using lazy graph reduction, and it divides into three parts.

The first part describes how to translate a high-level functional language into an intermediate language, called the lambda calculus, including detailed coverage of pattern-matching and type-checking. The second part begins with a simple implementation of the lambda calculus, based on graph reduction, and then develops a number of refinements and alternatives, such as supercombinators, full laziness and SK combinators. Finally, the third part describes the G-machine, a sophisticated implementation of graph reduction, which provides a dramatic increase in performance over the implementations described earlier.

One of the agreed advantages of functional languages is their semantic simplicity. This simplicity has considerable payoffs in the book. This book repeatedly able to make semi-formal arguments for the correctness of the compilation algorithms, and the whole book has a distinctly mathematical flavor - an unusual feature in a book about implementations.

Most of the material to be presented has appeared in the published literature in some form (though some has not), but mainly in the form of conference proceedings and isolated papers. References to this work appear at the end of each chapter.

Intended Audience:

This book is about implementations, not languages, it will make no attempt to extol the virtues of functional languages or the functional programming style. Instead this book will assume that the reader is familiar with functional programming; those without this familiarity may find it heavy going.

Simon Peyton Jones wrote:My 1987 book is now out of print, but it is now available online in its entirety.

Book Excerpts:

This book is about implementing functional programming languages using lazy graph reduction, and it divides into three parts.

The first part describes how to translate a high-level functional language into an intermediate language, called the lambda calculus, including detailed coverage of pattern-matching and type-checking. The second part begins with a simple implementation of the lambda calculus, based on graph reduction, and then develops a number of refinements and alternatives, such as supercombinators, full laziness and SK combinators. Finally, the third part describes the G-machine, a sophisticated implementation of graph reduction, which provides a dramatic increase in performance over the implementations described earlier.

One of the agreed advantages of functional languages is their semantic simplicity. This simplicity has considerable payoffs in the book. This book repeatedly able to make semi-formal arguments for the correctness of the compilation algorithms, and the whole book has a distinctly mathematical flavor - an unusual feature in a book about implementations.

Most of the material to be presented has appeared in the published literature in some form (though some has not), but mainly in the form of conference proceedings and isolated papers. References to this work appear at the end of each chapter.

Intended Audience:

This book is about implementations, not languages, it will make no attempt to extol the virtues of functional languages or the functional programming style. Instead this book will assume that the reader is familiar with functional programming; those without this familiarity may find it heavy going.

Tweet

About The Author(s)

Principal Researcher at Microsoft Research.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Rexx
Microsoft .NET
Perl
PHP
R
Python
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors