Categorical combinators, sequential algorithms, and functional programming. 2nd ed. (English) Zbl 0814.68085

Progress in Theoretical Computer Science. Basel: Birkhäuser. XX, 403 p. (1993).
This is a completely revised version of the book published by B. Pitman Publishing Ltd. (1986; Zbl 0643.68002). The author presents an approach to the semantics of sequential programming languages based on the relationship between \(\lambda\)-calculus and category theory, with applications to the design and implementation of programming languages. In the second edition many new results due to various authors (including the author of the book) are added, mostly in the form of exercises. Many new references are included. Among other things, the following new topics are reported: the confluence properties of rewriting systems of categorical combinators, calculi of explicit substitutions, connections of sequential algorithms with linear logic and games, a theory of sequential structures. The additions make the book more comprehensive and up-to-date.


68Q55 Semantics in the theory of computing
03G30 Categorical logic, topoi
03B40 Combinatory logic and lambda calculus
68-02 Research exposition (monographs, survey articles) pertaining to computer science
03B70 Logic in computer science


Zbl 0643.68002