Functional Programming and Parallel Graph Rewriting (International Computer Science Series)

✍ Scribed by M. J. Plasmeijer, Marko Van Eekelen, Rinus Plasmeijer, M. C. J. D. Van Eekelen

• Publisher: Addison-Wesley
• Year: 1993
• Tongue: English
• Leaves: 590
• Category: Library

✦ Synopsis

The descriptive power and semantic elegance of modern functional languages make it possible to develop correct programs relatively quickly. Efficient implementations of functional languages, employing graph rewriting techniques, have only recently become available. This book illustrates the techniques of functional programming in Miranda and Clean, and focuses on the computational model of Graph Rewriting Systems for both sequential and parallel machines.
Highlights of the book include a clear tutorial guide to functional programming in Miranda and Clean, in-depth coverage of implementation on both sequential and parallel machines, and unique focus on Graph Rewriting Systems as a computational model.
The book will be equally valuable for students taking courses in functional programming, and for programmers or systems designers who are keen to explore state-of-the-art programming and implementation techniques.
The Concurrent Clean System, which is available from the authors, offers the opportunity to write both sequential and parallel applications (including window-based systems) in a pure, lazy functional language.

✦ Table of Contents

Preface
Contents
--- Functional Programming
Basic concepts
Why functional programming?
Functions in mathematics
A functional program
The evaluation of a functional program
Functions with guarded equations & patterns
Data structures
Higher order functions and currying
Correctness proof of functional programs
Program examples
Advanced concepts: Miranda
Defining functions
Predefined data structures
The type system
User-defined data structures and their types
The use of functions as basic building blocks
Interactive programs
Top-down functional programming
--- Models of Computation
λ-Calculus
λ-Expressions
Reduction Rules for λ-Expressions
Reduction Sequences & Normal Forms
Properties of the λ-Calculus
Reduction Strategies
Properties of Subclasses of λ-Calculus
λ-Calculus as Basis for Functional Languages
λ-Calculus as Basis for Implementations
Term Rewriting Systems
TRSs
Rewriting with a TRS
Reduction sequences & normal forms
Properties of TRSs
Reduction strategies
Orthogonal TRSs
Priority rewrite systems
TRSs as a basis for functional languages
TRSs as a basis for implementations
Graph Rewriting Systems
Extending TRSs to GRSs
GRSs
Rewriting with a GRS
Reduction sequences and normal forms
Shorthand form
Properties of GRSs
Reduction strategies
Term graph rewriting
Generalized graph rewriting systems
GRSs as a basis for functional languages
GRSs as a basis for implementations
--- Analysis of Functional Programs
Type Assignment Systems
Type Assignment for λ-Calculus
Polymorphism & Recursion
Type Assignment for TRSs
Strictness Analysis
Strictness
Abstract interpretation
Basic domain theory
Strictness analysis using abstract interpretation
Analysing function definitions
Analysing non-flat domains
Abstract reduction
Strictness analysis using abstract reduction
--- Sequential Architectures
Clean
Clean - language for functional graph rewriting
Type System
Strict annotations
Modules
Unique types & destructive updates
IO handling
Translation into Clean
About the desugaring of the language
Simple transformations
List comprehensions
Local function definitions
Translating the desugared language into Clean
The exploitation of sharing
Abstract ABC Machine
About the ABC machine
Machine components and micro-instructions
The machine instructions
Program execution
Translating Clean into ABC code
Basic graph rewriting on the ABC machine
The run-time system
Optimizations
Realizing the ABC Machine
Representing the ABC machine components
Garbage collection
Motorola MC68020 Processor
Representing ABC components on MC68020
Generating MC68020 code
Example of concrete code
Performance
--- Concurrency Issues
Basic Language Concepts
Concurrency and functional programming
Annotations for concurrency
Examples of concurrent functional programs
Discussion
Parallel Graph Rewriting
Annotations to control the reduction order
GRSs with lazy copying
Modelling parallel graph rewriting
Concurrent Clean
Extending Clean to Concurrent Clean
Specifying process structures
Translation into Concurrent Clean
Parallel ABC Machine
About the PABC machine
Interleaved reduction
Parallel reduction
Program execution
Translating Concurrent Clean into PABC code
Realizing the PABC Machine
Representing the PABC machine components
Garbage collection on a distributed machine
The transputer processor
Representing PABC components on transputers
Generating transputer code and performance
Syntax of example programs
Concurrent Clean Syntax & Library
Concurrent Clean Syntax
δ-Rules
IO Library
ABC Machine Specification
ABC Instruction Set
Running ABC Programs
ABC Micro-Instructions
PABC Machine Specification
PABC Instruction Set
Running PABC Programs
New Micro-Instructions
Biblio
Index
Errata