Partial Evaluation and Automatic Program Generation

This book is about partial evaluation, a program optimization technique also known as program specialization. It presents general principles for constructing partial evaluators for a variety of programming languages, with examples of applications.

**Tag(s):**
Compiler Design and Construction

**Publication date**: 01 Jun 1993

**ISBN-10**:
0130202495

**ISBN-13**:
n/a

**Paperback**:
415 pages

**Views**: 19,768

Partial Evaluation and Automatic Program Generation

This book is about partial evaluation, a program optimization technique also known as program specialization. It presents general principles for constructing partial evaluators for a variety of programming languages, with examples of applications.

Book Excerpts:

This book is about partial evaluation, a program optimization technique also known as program specialization. It presents general principles for constructing partial evaluators for a variety of programming languages, and it gives examples of applications and numerous references to the literature.

Partial evaluation works with program texts rather than mathematical functions: a partial evaluator is an algorithm which, when given a program and some of its input data, produces a so-called residual or specialized program. Running the residual program on the remaining input data will yield the same result as running the original program on all of its input data.

The theoretical possibility of partial evaluation was established many years ago in recursive function theory as Kleene's 's-m-n theorem'. This book concerns its practical realization and application.

Partial evaluation gives a remarkable approach to compilation and compiler generation. For example, partial evaluation of an interpreter with respect to a source program yields a target program. Thus compilation can be achieved without a compiler, and a target program can be thought of as a specialized interpreter.

This book contains several examples of such applications, but the main emphasis of the book is on principles and methods for partial evaluation of a variety of programming languages: functional (the lambda calculus and Scheme); imperative (a flowchart language and a subset of C); and logical (Prolog). This book explains the techniques necessary for construction of partial evaluators (for instance, program flow analysis) in sufficient detail to allow their implementation. Many of these techniques are applicable also in other advanced programming tasks.

Intended Audience:

The book should be accessible even to beginning graduate students and thus useful for beginners and researchers in partial evaluation alike. The perspective on partial evaluation and the selection of material reflect the experience of constructing of several partial evaluators. These include the first non-trivial self-applicable partial evaluators for a functional language, an imperative language, the lambda calculus, a Prolog subset and a subset of C.

This book is about partial evaluation, a program optimization technique also known as program specialization. It presents general principles for constructing partial evaluators for a variety of programming languages, and it gives examples of applications and numerous references to the literature.

Partial evaluation works with program texts rather than mathematical functions: a partial evaluator is an algorithm which, when given a program and some of its input data, produces a so-called residual or specialized program. Running the residual program on the remaining input data will yield the same result as running the original program on all of its input data.

The theoretical possibility of partial evaluation was established many years ago in recursive function theory as Kleene's 's-m-n theorem'. This book concerns its practical realization and application.

Partial evaluation gives a remarkable approach to compilation and compiler generation. For example, partial evaluation of an interpreter with respect to a source program yields a target program. Thus compilation can be achieved without a compiler, and a target program can be thought of as a specialized interpreter.

This book contains several examples of such applications, but the main emphasis of the book is on principles and methods for partial evaluation of a variety of programming languages: functional (the lambda calculus and Scheme); imperative (a flowchart language and a subset of C); and logical (Prolog). This book explains the techniques necessary for construction of partial evaluators (for instance, program flow analysis) in sufficient detail to allow their implementation. Many of these techniques are applicable also in other advanced programming tasks.

Intended Audience:

The book should be accessible even to beginning graduate students and thus useful for beginners and researchers in partial evaluation alike. The perspective on partial evaluation and the selection of material reflect the experience of constructing of several partial evaluators. These include the first non-trivial self-applicable partial evaluators for a functional language, an imperative language, the lambda calculus, a Prolog subset and a subset of C.

Tweet

About The Author(s)

No information is available for this author.

No information is available for this author.

No information is available for this author.

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
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors