An ongoing project for the authors is maintaining an FTP directory containing errata, source code, compatibility files, a draft of an additional chapter on types available for comment, and other materials related to the text.
The email distribution list eopl-teachers@cs.indiana.edu provides a discussion forum for users of this text, with an archive of correspondence. Email eopl-teachers-request@cs.indiana.edu if you would like to be added to or deleted from this list. The following web material is related to this text. Let us know if you have material that might be added to this list.
Many texts are descriptive in nature and may be of use to the casual reader. Not this one. Our approach is analytic. Though we make little use of mathematical notation, our Scheme programs often play the same role. As with analytic texts in any discipline, this book requires careful reading with attention to detail. Before the material is mastered, it will frequently require rereading and reflection. Deep concepts are only absorbed with active participation. Their power must be experienced, not passively viewed.
Though we believe Scheme is an excellent metalanguage, this book is about the essentials of programming languages in general, not Scheme in particular. To emphasize this, we have given the interpreted language developed in this book a syntax very different from that of Scheme. This interpreted language is designed only for our pedagogic purposes and is not intended for other use. It is composed of a number of pieces, introduced throughout the text, which are not necessarily designed to form a coherent whole. Indeed, as we build new interpreters we often use the same concrete syntax with different semantics.
Beyond the use of Scheme, we use four major strategies:
Such depth must come at the expense of breadth. We make no attempt to survey existing languages, though we occasionally point out the design choices used in common languages. Although our approach is largely motivated by the developments in programming language semantics over the last 20 years, we do not address a number of important research areas, such as type checking and inference, logic programming, parallelism, and verification. We believe, however, that a command of the essentials will allow the student to study these topics. For example, an understanding of the mechanics of logic programming certainly requires understanding of continuations, dynamic binding, and the distinction between a variable's name, its binding, and the value of its binding.
The next three chapters show how these foundations may be used to describe the semantics of programming languages. Chapter 5 introduces interpreters as mechanisms for explaining the run-time behavior of languages and develops an interpreter for a simple, lexically scoped language with first-class procedures and variable assignment. This interpreter is the basis for most of the material in the remainder of the book. The chapter goes on to explore static and dynamic scoping and the implementation of recursion. Chapter 6 explores some parameter-passing mechanisms. Chapter 7 presents varieties of object-oriented facilities. These include several characterizations of inheritance and meta-classes. These two chapters can be studied in either order.
Chapters 8-10 show how the use of continuation-passing style enables us to transform our high-level interpreters into a flowchart-like form. Chapter 8 introduces continuation-passing style as a technique for expressing recursion by iteration. Using algebraic techniques, chapter 9 transforms our interpreter into continuation-passing style, and applies the techniques of chapter 3 to develop data structure representations of continuations. Data abstraction techniques then allow us to explore alternative representation strategies for the data manipulated by our interpreters. This includes the ability to make continuations accessible to the programmer as first-class objects of computation. In chapter 10 we complete the task of transforming our interpreter to a set of data structures manipulated by a finite-state controller. This gives us an interpreter that can be implemented in any low-level language. We then show how these data structures can be represented in a single stack with static and dynamic links. This development provides a solid understanding of stack-based language architectures, and also illustrates the power of algebraic reasoning techniques.
Finally, chapters 11 and 12 apply our techniques to the development of scanners, parsers, and compilers. Chapter 11 introduces lexical scanning and parsing techniques. Program transformations clarify the relationship between recursive descent and table-driven parsers. We show in chapter 12 how to start with a high-level functional specification of a language and, by choosing suitable representations of our data abstractions, derive both a virtual machine and a compiler that translates the high-level language to code for the virtual machine.
Chapters 5 through 10 are the heart of this book. The derivation of a sequence of interpreters ranging from very high- to very low-level does more than provide a solid, hands-on understanding of programming language semantics and a disciplined approach to language implementation. It also teaches an approach to programming that starts with a high-level operational specification, which also serves as a rapid prototype, and ends with what is effectively assembly language. We believe the programming transformation techniques used in this process should be in the toolbox of every computer scientist.
We assume the reader has at least one year of programming experience, including experience with a high-level language and assembly language and an introduction to data structures. Previous exposure to Lisp or Scheme is helpful but not required. This course might be followed by one in compiler construction or formal semantics of programming languages. ...