ESPRIT (the European strategic programme for research and development in information technology) is directed toward collaborative research and development efforts among industry, academia, and research centers in the member states. This book represents some ideas of a team of researchers who worked on an ESPRIT project involving the complexity of, the parallel execution of, and analysis techniques for functional programs. The scope of the book is much broader than this, however, and in fact it gives a good overview of both the theoretical and the practical aspects of functional programming.
The eight chapters fit together well, in spite of their distinct authors. The first two chapters are introductory. Chapter 1, “About Programming Environments,” describes the process of developing large software programs, programming environments (illustrated by the Cedar system), specifications, and desired properties of a functional programming environment. Chapter 2, “Aspects of Functional Programming,” surveys properties of functional languages, briefly describes LISP and ML and implementation techniques for functional languages, introduces notions of semantics, and defines the reference language used in the rest of the book.
Chapter 3, “Program Analysis by Abstract Interpretation,” briefly describes sources of inefficiency of functional languages and methods for solving these problems in order to motivate the discussion of abstract interpretation. The abstract interpretation method is then applied in chapter 4, “Compile-time Garbage Collection by Sharing Analysis,” to optimize the implementation of functional language memory management.
In chapter 5, “Analysis of Functional Programs by Program Transformation,” program transformations are introduced and applied to time complexity, potential parallelism, and program memory complexity analyses. Chapter6, “From Lambda Calculus to Machine Code by Program Transformation,” presents a method for transforming lambda expressions into expressions defined in terms of combinators.
Chapter 7, “On Input and Output in Functional Languages,” discusses how streams can be exploited to achieve interactive computations; presents a text editor as an example; examines programming styles and the use of higher-order functions; and considers networks, parallelism, nondeterminism, and functional implementation of an operating system. Chapter 8, “For Imperative Programmers,” investigates the relationship between the functional and imperative paradigms; considers denotational semantics as a method for translating imperative to functional languages; compares the two paradigms from the point of view of program development and correctness proofs; and discusses how history-sensitive computations can be expressed in a purely functional way. References are given at the end of each chapter, but none is more recent than 1989, undoubtedly due to publication delay.
This book covers the whole range of issues in functional languages, from the practical to the theoretical. The authors argue convincingly in favor of their thesis that functional languages could form the “basis of a broad spectrum language which could be used in all stages of the software development process” and that the problems of inefficiency can be overcome by “exploiting inherent qualities of functional languages and powerful program manipulation methods.”
The lucid discussion and historical remarks throughout make interesting reading, not only for researchers in the field, but also for the novice. The book’s usefulness as a reference would have been enhanced if an index had been provided.
