Functional programming and parallel graph rewriting. (English) Zbl 0788.68023

International Computing Science Series. Amsterdam: Addison-Wesley Publishing Group. XVII, 571 p. $ 48.50 /hc (1993).
This work is a famous textbook for a two-terms study course in functional programming. The first term is an introduction on functional programming models of computation and the implementation of functional languages referring to sequential machines architectures. The second term deals with analysis methods for functional programs, concurrent functional programming and the implementation on parallel architectures.
The book consists of 17 chapters in five parts.
Part 1 (Functional programming) deals with the idea of functional programming as a basis for most functional languages. Here a Miranda oriented advanced language concept is being introduced.
Part 2 (Models of computation) demonstrates three different computation models: Lambda-calculus, term-rewriting-systems and graph-rewriting- systems. These models are compared with respect to their ability for functional languages and their implementation. Graph-rewriting-systems will be used later as a basis for implementation.
Part 3 (Analysis of functional languages) treats the static analysis of functional programs. Here type assignment systems for the Lambda- calculus, term rewriting and strictness analysis are discussed. A methodology for the analysis in rewriting systems (called abstract reduction) is described.
Part 4 (Implementation on sequential architecture) described an implementation method, which uses Miranda as a basis that is then translated into an intermediate language Clean – a language for functional graph rewriting. The clean-program is then translated into a code for an abstract stack-based machine, which finally can be transformed into the code for a real processor. Thus, the implementation consists of two intermediate levels and three translations.
Part 5 (Concurrency issues) shows conceptual and practical possibilities of concurrent evaluation of functional programs. Here the basis is formed by notions in the language Miranda with concurrency. The intermediate language used is Concurrent Clean, a language for parallel graph rewriting. Here used for implementation of an parallel machine model with a loosely coupled architecture. Finally, the implementation is carried out by a concrete parallel target machine which uses transputer processors.
Each chapter also offers interesting exercises. The appendices provide Miranda based syntax of example programs, concurrent Clean syntax and library as well as specifications for abstract sequential and parallel machines.
“This textbook is suited for advanced undergraduate students, for postgraduate students of computer science and for researchers interested in the area of functional programming and the implementation techniques on sequential and parallel architectures”.


68N15 Theory of programming languages
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q42 Grammars and rewriting systems


Haskell; Miranda