Essentials of Programming Languages

This page for the first edition is no longer being maintained.
Please visit the page for the
second edition.

Title: Essentials of Programming Languages
Authors: Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes
Publishers: MIT Press (trade, ISBN 0-262-06145-7) and McGraw Hill (academic, ISBN 0-07-022443-9)
Format: 536 pages, hardback: $70, soft cover: $34.50
Library: QA76.7.F73
Copyright: 1992 (third printing)

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.

From the preface

The goal of this book is to give students a deep, hands-on understanding of the essential concepts of programming languages, using Scheme as an executable metalanguage. Because Scheme is a wide-spectrum language, it enables us to write both at the very high level needed to produce a concise, comprehensible interpreter and at the much lower level needed to understand how that interpreter might be coded in assembly language, or transformed into a compiler. Because of Scheme's excellent abstraction facilities, we can write substantial language-processing systems that are nevertheless compact enough for students to understand and manipulate with a reasonable amount of effort. This is a hands-on book: everything discussed in the book may be programmed by students.

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:

  1. The first strategy is the use of {interpreters} to explain the run-time behavior of programs in a given language. Interpreters express language design decisions in a manner that is both formal (unambiguous and complete) and executable. Furthermore, our interpreters are generally expressed in a fashion consistent with the principles of denotational semantics; they express key ideas of denotational semantics in a concrete way.
  2. Instead of relying on mere descriptions, using English, diagrams, or some abstract notation, we present each principle using Scheme programs that implement it. The use of Scheme enables the student to understand these programs without drowning in a sea of irrelevant detail. The exercises allow the student to experiment with alternatives in design and implementation.
  3. We emphasize the systematic derivation of low-level implementations from their high-level abstractions. We show how simple algebraic manipulation can be used to derive program properties and correctness-preserving program transformations. In particular, we use these techniques to derive stack-management protocols and to transform an interpreter into a compiler.
  4. Finally, we use data abstraction, expressed as a modular coding style, to separate algorithms from the representation of the underlying quantities. In this way, we can change data representation without changing programs. In the case of interpreters, we use this technique to investigate different implementation strategies.

Through the use of these strategies, we are able to give students several working models, ranging from very high-level (almost formal semantics) to very low-level (almost assembly language), and to demonstrate a clear connection between these models.

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.

Organization

... The first four chapters provide the foundations for a careful study of programming languages. Chapter 1 introduces most of the features of Scheme that are required in later chapters, along with some basic terminology. Readers who have prior experience with Scheme or other Lisp dialects may wish to skim this chapter and refer to it as necessary. Chapter 2 emphasizes the connection between inductive data specification and recursive programming, and introduces several notions related to the scope of variables. A set of exercises is provided to develop facility with recursive programming. Chapter 3 introduces some commonly used syntactic abstractions, including a variant record facility. This leads to a discussion of data abstraction and examples of representational transformations of the sort used in subsequent chapters. Chapter 4 introduces, in the context of the lambda calculus, several rewrite rules that are basic program transformations and provides a brief review of imperative programming.

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.

Usage

This text has been used in various forms to teach students from the sophomore to the graduate level, and in continuing education classes for professional programmers. It also has much to offer the dedicated computer scientist through self-study.

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. ...

chaynes@indiana.edu