Publisher's Synopsis
This book is a thoroughly revised edition of a monograph that presents an approach to the design and implementation of sequential programming languages based on the relationship between lambda-calculus and category theory.;The foundations of a new "categorical" combinatory logic are laid down. Compilation and evaluation techniques are investigated. A simple abstract machine, called the Categorical Abstract Machine, is presented: it has served as the core of the implementation of the language CAML, of the ML family, developed at INRIA-Roquencourt and Ecole Normale Superieure, and first released in 1987.;The main characteristics of this approach are conceptual simplicity and compactness, with bearings on portability, efficiency, and correctness proofs.;A mathematical semantics of sequentiality is proposed, in which "sequential algorithms" rather than functions are used to interpret procedures. The theoretical investigation has led to the development of a programming language, CDSO, in which basic and functional types are not differentiated. The evaluation framework is a demand-driven data flow network. The model of sequential algorithms is fully abstract with respect to this language: two procedures have the same denotation if and only if they have the same behaviour. Background on full abstraction is given.;The new edition covers new results, and introduces new connections, as suggested by the following non-exhaustive fist of keywords: confluence properties of categorical combinators, explicit substitutions, control operations, linear logic, geometry of interaction, strong stability.
