Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2011 | Book

Terms and Relations Read chapter Read first chapter

Introduction to the Theory of Programming Languages

Authors: Gilles Dowek, Jean-Jacques Lévy

Publisher: Springer London

Book Series : Undergraduate Topics in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

The design and implementation of programming languages, from Fortran and Cobol to Caml and Java, has been one of the key developments in the management of ever more complex computerized systems. Introduction to the Theory of Programming Languages gives the reader the means to discover the tools to think, design, and implement these languages. It proposes a unified vision of the different formalisms that permit definition of a programming language: small steps operational semantics, big steps operational semantics, and denotational semantics, emphasising that all seek to define a relation between three objects: a program, an input value, and an output value. These formalisms are illustrated by presenting the semantics of some typical features of programming languages: functions, recursivity, assignments, records, objects, ... showing that the study of programming languages does not consist of studying languages one after another, but is organized around the features that are present in these various languages. The study of these features leads to the development of evaluators, interpreters and compilers, and also type inference algorithms, for small languages.

Table of Contents

Frontmatter
Chapter 1. Terms and Relations
Abstract
For the book to be really self contained, this chapter introduces all the basic notions about inductive definitions and formal languages in general (variables, expressions, substitution, bound and free variables, sorts, …). Then it introduces to three ways to define the semantics of a programming language: denotational semantics, big-step and small-step operational semantics. This chapter start from scratch and gives many examples.
Gilles Dowek, Jean-Jacques Lévy
Chapter 2. The Language PCF
Abstract
This chapter introduces a specific programming language called PCF (and sometimes mini-ML). This language is one of the backbones of the book. It will be evaluated, interpreted, compiled, and extended (with types, references, records and objects) in the rest of the book. This chapter focuses on giving an informal description of the language, defining its small-step and big-step operational semantics and culminates with the implementation of an evaluator for this language.
Gilles Dowek, Jean-Jacques Lévy
Chapter 3. From Evaluation to Interpretation
Abstract
This chapter introduces an essential notion in the implementation of programming languages: that of environment. Then it uses it to transform the evaluator built in the previous chapter into an interpretor. It finally discusses several optimizations: the use of De Bruijn indices and recursive closures.
Gilles Dowek, Jean-Jacques Lévy
Chapter 4. Compilation
Abstract
In this chapter the interpretor is transformed into a compiler. The emphasis is put on the construction of an abstract machine, whose language is the target language of the compilation. This chapter ends with the bootstrapping of this compiler.
Gilles Dowek, Jean-Jacques Lévy
Chapter 5. PCF with Types
Abstract
This chapter opens a new part of the book, dedicated to types. The language PCF is extended by adding types. A type verification algorithm is described and the application to the static detection of errors is discussed in length. This chapter also describes the denotational semantics of PCF with types.
Gilles Dowek, Jean-Jacques Lévy
Chapter 6. Type Inference
Abstract
This chapter continues with types, but with a much more operational orientation. Powerful type inferences type inference algorithms are described, in particular one with polymorphic typing.
Gilles Dowek, Jean-Jacques Lévy
Chapter 7. References and Assignment
Abstract
This chapter opens the last part of the book where PCF is extended with new features. This chapter focuses on references and assignments, and thus shifts from functional to imperative programming. A semantics is given for PCF with references and the interpretor of Chap. 3 is extended.
Gilles Dowek, Jean-Jacques Lévy
Chapter 8. Records and Objects
Abstract
The final chapter of the book is dedicated to object oriented programming languages. An extension of PCF with objects is defined and implemented. But before that, an extension of PCF with records is. Then objects are introduced as records with functional fields.
Gilles Dowek, Jean-Jacques Lévy
Chapter 9. Epilogue
Abstract
The Epilogue discusses the goals of the theory of programming languages: building tools to describe existing languages or to define new ones?
Gilles Dowek, Jean-Jacques Lévy
Backmatter
Metadata
Title
Introduction to the Theory of Programming Languages
Authors
Gilles Dowek
Jean-Jacques Lévy
Copyright Year
2011
Publisher
Springer London
Electronic ISBN
978-0-85729-076-2
Print ISBN
978-0-85729-075-5
DOI
https://doi.org/10.1007/978-0-85729-076-2

Premium Partner

    Image Credits