This book is an introduction to the study of programming languages. The material has evolved from lecture notes used in a programming languages course for juniors, seniors, and graduate students at Johns Hopkins University [21].

The book treats programming language topics from a foundational, but not formal, perspective. It is foundational in that it focuses on core concepts in language design such as functions, records, objects, and types and not directly on applied languages such as C, C++, or Java. We show how the particular core concepts are realized in these modern languages, and so the reader should emerge from this book with a stronger sense of how they are structured.

The book is not formal in the sense that no theorems are proved about programming languages. We do, however, use several techniques that are useful in the formal study of programming languages, including operational semantics and type systems. With these techniques we can define more carefully how programs should behave.

The OCaml Language

The Caml programming language [15] is used throughout the book, and assignments related to the book are best written in Caml. Caml is a modern dialect of ML which has the advantages of being reliable, fast, free, and available on just about any platform through

This book does not provide an introduction to Caml, and we recommend the following resources for learning the basics:

The OCaml manual is complete but terse. Hickey’s book may be your antidote if you want a more descriptive explanation than that provided in the manual.


Complementing the book is the D Development Kit, DDK. It is a set of Caml utilities and interpreters for designing and experimenting with the toy D and DSR languages defined in the book. It is available from the book homepage at, and is documented in Appendix A.

Background Needed

The book assumes familiarity with the basics of Caml, including the module system (but not the objects, the “O” in OCaml). Beyond that there is no absolute prerequisite, but knowledge of C, C++, and Java is helpful because many of the topics in this book are implemented in these languages. The compiler presented in chapter 7 produces C code as its target, and so a very basic knowledge of C will be needed to implement the compiler. More nebulously, a certain “mathematical maturity” greatly helps in understanding the concepts, some of which are deep. for this reason, previous study of mathematics, formal logic and other foundational topics in Computer Science such as automata theory, grammars, and algorithms will be a great help.