Introduction to the theory of programming languages. (Q1960263)

The book is devoted to the methods of defining semantics of programming languages, understood as the relation between the program and its input and output. The first chapter defines basic concepts, in particular the fixed point theorem, as well as three formalisms -- denotational semantics, big-step operational semantics and small-step operational semantics. In the following, the introduced concepts and methods are applied to the functional programming language Programming Computable Functions (PCF), originally formulated by Dana Scott. Chapter 2 describes the syntax of the language and the principles of its operational semantics. Chapters 3 and 4 are devoted to the creation of an interpreter and/or a compiler for PCF based on the definition of its semantics. Chapters 5 and 6 elaborate the exposition by adding types to PCF and formulating its denotational semantics and type inference. The next two chapters further extend the language with references, assignment statements, records and objects. All the chapters are supplemented by exercises. Chapter 9 contains a suitable summary of the exposition. This is a very good textbook from the Springer series Undergraduate Topics in Computer Science; it was first published in French in 2005 [Introduction à la théorie des langages de programmation. Palaiseau: Les Éditions de l'École Polytechnique (2006; Zbl 1193.68067)].