Programming Languages: Concepts and Constructs / Edition 2

by Ravi Sethi, Tom Stone

Overview

Programming Languages: Concepts and Constructs, Second Edition retains the "character" of the original, emphasizing concepts and how they work together. This classic book has been thoroughly revised to provide readable coverage of the major programming paradigms. Dr. Sethi's treatment of the core concepts of imperative programming in languages like Pascal and C flows smoothly into object-oriented programming in C++ and Smalltalk. The charm of functional languages is illustrated by programs in standard ML and the Scheme dialect of Lisp. Logic programming is introduced using Prolog.

Novices, who have been introduced to programming in some language, will learn from this book how related concepts work together while designers and implementers willp be exposed to the major programming paradigms.

Example programs from the book are available as source code. These are available by anonymous ftp at ftp://ftp.aw.com/cseng/authors/sethi/pl2e.

0201590654B04062001

Product Details

ISBN-13:	9780201590654
Publisher:	Addison-Wesley
Publication date:	12/28/1995
Series:	Computer Science Series
Edition description:	2nd ed
Pages:	640
Product dimensions:	7.30(w) x 9.00(h) x 1.30(d)

About the Author

About Ravi Sethi

Ravi Sethi, director of Computing Science Research, has been at AT&T Bell Laboratories in Murray Hill, New Jersey since 1976. He has held teaching positions at Pennsylvania State university and the University of Arizona, and has taught at Princeton University and Rutgers. Dr. Sethi is co-author of the "dragon book", Compilers: Principles, Techniques and Tools and has written numerous articles. His books have been translated in Japanese, German, French, Italian, Spanish, and Korean.

Read an Excerpt

PREFACE:

This book is designed for junior/senior level courses on programming languages. A minimal pre-requisite is an introductory programming course. With supplementary readings, the book can also be used for graduate courses.

What's New in this Edition?

Changes on the language scene and feedback from the use of the book have prompted a thorough revision. Instructors liked the emphasis on concepts, but asked that the concepts be illustrated using fewer languages. Meanwhile, Modula-2 has faded, and C++ has taken off as a language for production programming. Candidates for functional languages now include Standard ML, Haskell, and Miranda.

The new outline has 15 chapters, three more than the first edition. The role of the three new chapters is as follows:

• Data types like arrays, records, and pointers have a new chapter.
• Functional programming is introduced using ML in a new chapter.
• Language summaries appear in a final chapter.

Language description and syntax are now treated early, in Chapter 2.

Organization of this Book

The emphasis is on concepts and how they work together, rather than on language features. Related concepts are therefore covered together, to allow meaningful examples and programming exercises along the way. Just enough of a language is introduced, as needed, for the examples and exercises. Language summaries appear in Chapter 15.

Part I: Introduction

Chapter 1 traces the role and development of programming languages. It introduces the programming paradigms in this book. They include imperative,object-oriented, functional, and logic programming.

Syntax description is treated in Chapter 2, so it can be applied in the rest of the book. The examples in the chapter deal with expressions, since methods for describing the syntax of expressions carry over to the rest of a language.

Part II: Imperative Programming

The imperative family is treated in Chapters 3-5. The term ''imperative'' comes from command or action; the computation model is that of a sequence of actions on an underlying machine.

Chapter 3 deals with control flow. Structured constructs like while statements organize the flow of control so that the unit of programming is a structured statement, instead of an individual assignment. Students in a course that emphasizes imperative programming are usually familiar with Pascal, so this chapter goes beyond assignments and structured statements to consider programming with invariants. The examples deal with basic values, like integers, and arrays.

Chapter 4 deals with data in imperative languages. Data representation facilities such as arrays, records, and pointers, have been stable since Pascal and C appeared. The treatment of these facilities anticipates their use to represent objects in Chapters 6 and 7.

Chapter 5 rounds out the discussion of the core of imperative languages, embodied in a language like Pascal or C. Among the topics are the distinction between the source text of a procedure and its activations, parameter passing, scope rules, and storage allocation.

This book illustrates imperative programming using Pascal, where possible. Pascal suffices as a vehicle for Chapters 3-5. C is an alternative.

Part III: Object-Oriented Programming

As programs get larger, the natural unit of programming is a grouping of data and operations. The progression of concepts for such groupings can be described in terms of modules, user-defined types (for example, stacks), and classes (as in object-oriented programming).

Chapter 6 begins with of programming with procedures, modules, and classes. These constructs serve distinct needs and can be used in combination with each other: procedures are needed to implement operations in a module or class; modules can be used to statically partition the source text of a program with classes. Some versions of Pascal support modules; they can be used for the first half of Chapter 6 as well. C++, an extension of C, is introduced in Chapter 6.

The model of computation in Chapter 7 is that of independent objects. The objects interact by sending messages to each other. The first third of the chapter introduces object-oriented programming in general, using a running example that has similar implementations in C++ and Smalltalk. The rest of the chapter has independent coverage of C++ and Smalltalk, so either one can be used to explore object-oriented programming. Based on feedback from instructors, this edition covers C++ before Smalltalk, inverting the order in the previous edition. Object-oriented programming is illustrated using both C++ and Smalltalk, since the two represent different approaches.

All of the concepts in Chapters 3 - 7 can be illustrated using C++. Students can be introduced directly to C++, without going through C.

Part IV: Functional Programming

Functional programming is worth studying as a programming style in its own right; as a setting for studying concepts such as types; and as a technique for language description. The emphasis in Chapter 8 is on concepts, in Chapters 9 and 10 on programming style, and in Chapter 13 on language description. The computational model is based on an expression interpreter; an expression consists of a function applied to subexpressions.

The emphasis in Chapter 8 is on concepts. The simplicity of functional languages makes them convenient for introducing concepts such as values, types, names, and functions. The simplicity results from the emphasis on expressions and values, independent of the underlying machine. The chapter treads ground common to functional languages, using ML as the working language.

The fundamental difference between ML and Lisp is that ML is typed; the influence of types permeates the language. Chapter 9 uses ML to illustrate the use of functions and datatypes. As first-class citizens, functions have the same status as any other values in functional programming. This first-class status permits the creation of powerful operations on collections of data.

Functional programming originated with Lisp. Programs and data are both represented by lists in Lisp; the name is a contraction of ''List Processor.'' The uniform use of lists makes Lisp eminently extensible. Chapter 10 explores the use of lists, using the Scheme dialect of Lisp.

See also Chapter 13, which contains an interpreter for a small subset of Scheme, and Chapter 14, which covers the lambda calculus.

Part V: Other Paradigms

Logic programming goes hand in hand with Prolog, in Chapter 11. Logic programming deals with relations rather than functions. Where it fits, programs are concise, consisting of facts and rules. The languages uses the facts and rules to deduce responses to queries.

Concurrent programming is illustrated using Ada, in Chapter 12. An alternative approach would have been to cover concurrent programming after object-oriented programming. Processes can be formed by giving each object its own thread of computation. The present organization puts functional programming before concurrent programming.

Part VI: Language Description

The methods for language description in Chapter 13 are aimed at specialists. The methods range from attributes used for language translation, to logical rules for used type inference, to interpreters used for clarifying subtle language questions.

A language can be described by writing a definitional interpreter for it, so called because its purpose is to define the interpreted language; efficiency is not a concern. McCarthy's & original definitional interpreter for Lisp in Lisp remains important for language description, so language description is illustrated using the Scheme dialect of Lisp. Chapter 13 develops an interpreter for a small subset of Scheme.

The lambda calculus is the intellectual ancestor of functional languages. The small syntax of the lambda calculus has also led to its use as a vehicle for studying languages. Variants of the lambda calculus are introduced in Chapter 14. The chapter progresses from the pure untyped lambda calculus to typed lambda calculi.

Chapter 15 contains brief summaries of the languages in this book.

Acknowledgments From the First Edition

A graduate seminar at Rutgers University gave me both the opportunity and the incentive to collect material on programming languages. I'd like to thank Alex Borgida, Martin Carroll, Fritz Henglein, Naftaly Minsky, Bob Paige, and Barbara Ryder for keeping the seminar lively.

An undergraduate course at Harvard University used an early draft of this book. Written comments by the students in the course were very helpful.

The organization of this book has benefited greatly from the comments and especially the criticism of the then anonymous reviewers contacted by Addison-Wesley. They are Tom Cheatham, Harvard University, John Crenshaw, Western Kentucky University, Paul Hilfinger, University of California, Berkeley, Barry Kurtz, New Mexico State University, Robert Noonan, College of William and Mary, Ron Olsson, University of California, Davis, William Pervin, University of Texas at Dallas, Paul Reynolds, University of Virginia, David Schmidt, Kansas State University, and Laurie Werth, University of Texas at Austin.

For all their technical help, I am grateful to Al Aho, Jon Bentley, Gerard Berry, Eric Cooper, Bruce Duba, Tom Duncan, Rich Drechsler, Peggy Ellis, Charlie Fischer, Dan Friedman, Georges Gonthier, Bob Harper, Mike Harrison, Bruce Hillyer, Brian Kernighan, Kim King, Chandra Kintala, Dave MacQueen, Dianne Maki, Doug McIlroy, John Mitchell, Mike O'Donnell, Dennis Ritchie, Bjarne Stroustrup, Chris Van Wyk, and Carl Woolf.

This book on programming languages was produced with the help of a number of little languages. The diagrams were drawn using Brian Kernighan's Pic language; the grey-tones in the diagrams rely on the work of Rich Drechsler. The tables were laid out using Mike Lesk's Tbl program. Eqn, Lorinda Cherry and Brian Kernighan's language for typesetting mathematics, handled the pseudo-code as well. The Troff program was originally written by the late Joe Ossanna and is kept vital by Brian Kernighan. Page layout would have suffered without a new Troff macro package and post-processor by Brian Kernighan and Chris Van Wyk. The indexing programs were supplied by Jon Bentley and Brian Kernighan. Cross references were managed using scripts written with the help of Al Aho for managing the text of the ''dragon'' book.

Finally, I'd like to thank AT&T Bell Laboratories for its support. I have learnt more from my colleagues here than they might suspect. Whenever a question occurred, someone in the building always seemed to have the answer.

Acknowledgments

I really appreciate the comments I have received on the first edition. The experience of instructors and the frank opinions of reviewers have guided the revision.

Debbie Lafferty of Addison-Wesley has been the voice on the phone through the months, coordinating reviews and credits, and generally keeping the project on track. I now know that the reviewers include Bill Appelbe, Michael Barnett, Manuel E. Bermudez, Ray Ford, Aditya P. Mathur, L. A. Oldroyd, and Hamilton Richards -- thanks.

For technical help and discussions, I am grateful to Jon Bentley, Lorinda Cherry, Brian Kernighan, Dave MacQueen, Jon Riecke, and Rich Wolf. My colleagues at AT&T Bell Laboratories have been greatly supportive.

A lot has happened while I have been immersed in the Book, including a death, a birth, a move, a fire. Dianne Maki has helped me navigate through it all.

RS

0201590654P04062001

Table of Contents

I. INTRODUCTION.

1. The Role of Programming Languages.

Toward Higher-Level Languages.

Problems of Scale.

Programming Paradigms.

Language Implementation: Bridging the Gap.

Exercises.

Bibliographic Notes.

2. Language Description: Syntactic Structure.

Expression Notations.

Abstract Syntax Trees.

Lexical Syntax.

Context-Free Grammars.

Grammars for Expressions.

Variants of Grammars.

Exercises.

Bibliographic Notes.

II. IMPERATIVE PROGRAMMING.

3. Statements: Structured Programming.

The Need for Structured Programming.

Syntax-Directed Control Flow.

Design Considerations: Syntax.

Handling Special Cases in Loops.

Programming with Invariants.

Proof Rules for Partial Correctness.

Control flow in C.

Exercises.

Bibliographic Notes.

4. Types: Data Representation.

The Role of Types.

Basic Types.

Arrays: Sequences of Elements.

Records: Named Fields.

Unions and Variant Records.

Sets.

Pointers: Efficiency and Dynamic Allocation.

Two String Tables.

Types and Error Checking.

Exercises.

Bibliographic Notes.

5. Procedure Activations.

Introduction to Procedures.

Parameter-Passing Methods.

Scope Rules for Names.

Nested Scopes in the Source Text.

Activation Records.

Lexical Scope: Procedures as in C.

Lexical Scope: Nested Procedures and Pascal.

Exercises.

Bibliographic Notes.

III. OBJECT-ORIENTED PROGRAMMING.

6. Groupings of Data and Operations.

Constructs for Program Structuring.

Information Hiding.

Program Design with Modules.

Modules and Defined Types.

Class Declarations in C++.

Dynamic Allocation in C++.

Templates: Parameterized Types.

Implementation of Objects in C++.

Exercises.

Bibliographic Notes.

7. Object-Oriented Programming.

What is an Object?

Object-Oriented Thinking.

Inheritance.

Object-Oriented Programming in C++.

An Extended C++ Example.

Derived Classes and Information Hiding.

Objects in Smalltalk.

Smalltalk Objects have a Self.

Exercises.

Bibliographic Notes.

IV. FUNCTIONAL PROGRAMMING.

8. Elements of Functional Programming.

A Little Language of Expressions.

Types: Values and Operations.

Function Declarations.

Approaches to Expression Evaluation.

Lexical Scope.

Type Checking.

Exercises.

Bibliographic Notes.

9. Functional Programming in a Typed Language.

Exploring a List.

Function Declaration by Cases.

Functions as First-Class Values.

ML: Implicit Types.

Data Types.

Exception Handling in ML.

Little Quilt in Standard ML.

Exercises.

Bibliographic Notes.

10. Functional Programming with Lists.

Scheme, a Dialect of Lisp.

The Structure of Lists.

List Manipulation.

A Motivating Example: Differentiation.

Simplification of Expressions.

Storage Allocation for Lists.

Exercises.

Bibliographic Notes.

V. OTHER PARADIGMS.

11. Logic Programming.

Computing with Relations.

Introduction to Prolog.

Data Structures in Prolog.

Programming Techniques.

Control in Prolog.

Cuts.

Exercises.

Bibliographic Notes.

12. An Introduction to Concurrent Programming.

Parallelism in Hardware.

Streams: Implicit Synchronization.

Concurrency as Interleaving.

Liveness Properties.

Safe Access to Shared Data.

Concurrency in Ada.

Synchronized Access to Shared Variables.

Exercises.

Bibliographic Notes.

VI. LANGUAGE DESCRIPTION.

13. Semantic Methods.

Synthesized Attributes.

Attribute Grammars.

Natural Semantics.

Denotational Semantics.

A Calculator in Scheme.

Lexically Scoped Lambda Expressions.

An Interpreter.

An Extension: Recursive Functions.

Exercises.

Bibliographic Notes.

14. Static Types and the Lambda Calculus.

Equality of Pure Lambda Terms.

Substitution Revisited.

Computation with Pure Lambda Terms.

Programming Constructs as Lambda-Terms.

The Typed Lambda Calculus.

Polymorphic Types.

Exercises.

Bibliographic Notes.

15. A Look at Some Languages.

Pascal: A Teaching Language.

C: Systems Programming.

C++: A Range of Programming Styles.

Smalltalk, the Language.

Standard ML.

Scheme, a Dialect of Lisp.

Prolog.

Bibliography.

Credits.

Index. 0201590654T04062001

Preface

This book is designed for junior/senior level courses on programming languages. A minimal pre-requisite is an introductory programming course. With supplementary readings, the book can also be used for graduate courses.

What's New in this Edition?

Changes on the language scene and feedback from the use of the book have prompted a thorough revision. Instructors liked the emphasis on concepts, but asked that the concepts be illustrated using fewer languages. Meanwhile, Modula-2 has faded, and C++ has taken off as a language for production programming. Candidates for functional languages now include Standard ML, Haskell, and Miranda.

The new outline has 15 chapters, three more than the first edition. The role of the three new chapters is as follows:

• Data types like arrays, records, and pointers have a new chapter.
• Functional programming is introduced using ML in a new chapter.
• Language summaries appear in a final chapter.

Language description and syntax are now treated early, in Chapter 2.

Organization of this Book

The emphasis is on concepts and how they work together, rather than on language features. Related concepts are therefore covered together, to allow meaningful examples and programming exercises along the way. Just enough of a language is introduced, as needed, for the examples and exercises. Language summaries appear in Chapter 15.

Part I: Introduction

Chapter 1 traces the role and development of programming languages. It introduces the programming paradigms in this book. They include imperative, object-oriented, functional, and logic programming.

Syntax description is treated in Chapter 2, so it can be applied in the rest of the book. The examples in the chapter deal with expressions, since methods for describing the syntax of expressions carry over to the rest of a language.

Part II: Imperative Programming

The imperative family is treated in Chapters 3-5. The term ''imperative'' comes from command or action; the computation model is that of a sequence of actions on an underlying machine.

Chapter 3 deals with control flow. Structured constructs like while statements organize the flow of control so that the unit of programming is a structured statement, instead of an individual assignment. Students in a course that emphasizes imperative programming are usually familiar with Pascal, so this chapter goes beyond assignments and structured statements to consider programming with invariants. The examples deal with basic values, like integers, and arrays.

Chapter 4 deals with data in imperative languages. Data representation facilities such as arrays, records, and pointers, have been stable since Pascal and C appeared. The treatment of these facilities anticipates their use to represent objects in Chapters 6 and 7.

Chapter 5 rounds out the discussion of the core of imperative languages, embodied in a language like Pascal or C. Among the topics are the distinction between the source text of a procedure and its activations, parameter passing, scope rules, and storage allocation.

This book illustrates imperative programming using Pascal, where possible. Pascal suffices as a vehicle for Chapters 3-5. C is an alternative.

Part III: Object-Oriented Programming

As programs get larger, the natural unit of programming is a grouping of data and operations. The progression of concepts for such groupings can be described in terms of modules, user-defined types (for example, stacks), and classes (as in object-oriented programming).

Chapter 6 begins with of programming with procedures, modules, and classes. These constructs serve distinct needs and can be used in combination with each other: procedures are needed to implement operations in a module or class; modules can be used to statically partition the source text of a program with classes. Some versions of Pascal support modules; they can be used for the first half of Chapter 6 as well. C++, an extension of C, is introduced in Chapter 6.

The model of computation in Chapter 7 is that of independent objects. The objects interact by sending messages to each other. The first third of the chapter introduces object-oriented programming in general, using a running example that has similar implementations in C++ and Smalltalk. The rest of the chapter has independent coverage of C++ and Smalltalk, so either one can be used to explore object-oriented programming. Based on feedback from instructors, this edition covers C++ before Smalltalk, inverting the order in the previous edition. Object-oriented programming is illustrated using both C++ and Smalltalk, since the two represent different approaches.

All of the concepts in Chapters 3 - 7 can be illustrated using C++. Students can be introduced directly to C++, without going through C.

Part IV: Functional Programming

Functional programming is worth studying as a programming style in its own right; as a setting for studying concepts such as types; and as a technique for language description. The emphasis in Chapter 8 is on concepts, in Chapters 9 and 10 on programming style, and in Chapter 13 on language description. The computational model is based on an expression interpreter; an expression consists of a function applied to subexpressions.

The emphasis in Chapter 8 is on concepts. The simplicity of functional languages makes them convenient for introducing concepts such as values, types, names, and functions. The simplicity results from the emphasis on expressions and values, independent of the underlying machine. The chapter treads ground common to functional languages, using ML as the working language.

The fundamental difference between ML and Lisp is that ML is typed; the influence of types permeates the language. Chapter 9 uses ML to illustrate the use of functions and datatypes. As first-class citizens, functions have the same status as any other values in functional programming. This first-class status permits the creation of powerful operations on collections of data.

Functional programming originated with Lisp. Programs and data are both represented by lists in Lisp; the name is a contraction of ''List Processor.'' The uniform use of lists makes Lisp eminently extensible. Chapter 10 explores the use of lists, using the Scheme dialect of Lisp.

See also Chapter 13, which contains an interpreter for a small subset of Scheme, and Chapter 14, which covers the lambda calculus.

Part V: Other Paradigms

Logic programming goes hand in hand with Prolog, in Chapter 11. Logic programming deals with relations rather than functions. Where it fits, programs are concise, consisting of facts and rules. The languages uses the facts and rules to deduce responses to queries.

Concurrent programming is illustrated using Ada, in Chapter 12. An alternative approach would have been to cover concurrent programming after object-oriented programming. Processes can be formed by giving each object its own thread of computation. The present organization puts functional programming before concurrent programming.

Part VI: Language Description

The methods for language description in Chapter 13 are aimed at specialists. The methods range from attributes used for language translation, to logical rules for used type inference, to interpreters used for clarifying subtle language questions.

A language can be described by writing a definitional interpreter for it, so called because its purpose is to define the interpreted language; efficiency is not a concern. McCarthy's & original definitional interpreter for Lisp in Lisp remains important for language description, so language description is illustrated using the Scheme dialect of Lisp. Chapter 13 develops an interpreter for a small subset of Scheme.

The lambda calculus is the intellectual ancestor of functional languages. The small syntax of the lambda calculus has also led to its use as a vehicle for studying languages. Variants of the lambda calculus are introduced in Chapter 14. The chapter progresses from the pure untyped lambda calculus to typed lambda calculi.

Chapter 15 contains brief summaries of the languages in this book.

Acknowledgments From the First Edition

A graduate seminar at Rutgers University gave me both the opportunity and the incentive to collect material on programming languages. I'd like to thank Alex Borgida, Martin Carroll, Fritz Henglein, Naftaly Minsky, Bob Paige, and Barbara Ryder for keeping the seminar lively.

An undergraduate course at Harvard University used an early draft of this book. Written comments by the students in the course were very helpful.

The organization of this book has benefited greatly from the comments and especially the criticism of the then anonymous reviewers contacted by Addison-Wesley. They are Tom Cheatham, Harvard University, John Crenshaw, Western Kentucky University, Paul Hilfinger, University of California, Berkeley, Barry Kurtz, New Mexico State University, Robert Noonan, College of William and Mary, Ron Olsson, University of California, Davis, William Pervin, University of Texas at Dallas, Paul Reynolds, University of Virginia, David Schmidt, Kansas State University, and Laurie Werth, University of Texas at Austin.

For all their technical help, I am grateful to Al Aho, Jon Bentley, Gerard Berry, Eric Cooper, Bruce Duba, Tom Duncan, Rich Drechsler, Peggy Ellis, Charlie Fischer, Dan Friedman, Georges Gonthier, Bob Harper, Mike Harrison, Bruce Hillyer, Brian Kernighan, Kim King, Chandra Kintala, Dave MacQueen, Dianne Maki, Doug McIlroy, John Mitchell, Mike O'Donnell, Dennis Ritchie, Bjarne Stroustrup, Chris Van Wyk, and Carl Woolf.

This book on programming languages was produced with the help of a number of little languages. The diagrams were drawn using Brian Kernighan's Pic language; the grey-tones in the diagrams rely on the work of Rich Drechsler. The tables were laid out using Mike Lesk's Tbl program. Eqn, Lorinda Cherry and Brian Kernighan's language for typesetting mathematics, handled the pseudo-code as well. The Troff program was originally written by the late Joe Ossanna and is kept vital by Brian Kernighan. Page layout would have suffered without a new Troff macro package and post-processor by Brian Kernighan and Chris Van Wyk. The indexing programs were supplied by Jon Bentley and Brian Kernighan. Cross references were managed using scripts written with the help of Al Aho for managing the text of the ''dragon'' book.

Finally, I'd like to thank AT&T Bell Laboratories for its support. I have learnt more from my colleagues here than they might suspect. Whenever a question occurred, someone in the building always seemed to have the answer.

Acknowledgments

I really appreciate the comments I have received on the first edition. The experience of instructors and the frank opinions of reviewers have guided the revision.

Debbie Lafferty of Addison-Wesley has been the voice on the phone through the months, coordinating reviews and credits, and generally keeping the project on track. I now know that the reviewers include Bill Appelbe, Michael Barnett, Manuel E. Bermudez, Ray Ford, Aditya P. Mathur, L. A. Oldroyd, and Hamilton Richards -- thanks.

For technical help and discussions, I am grateful to Jon Bentley, Lorinda Cherry, Brian Kernighan, Dave MacQueen, Jon Riecke, and Rich Wolf. My colleagues at AT&T Bell Laboratories have been greatly supportive.

A lot has happened while I have been immersed in the Book, including a death, a birth, a move, a fire. Dianne Maki has helped me navigate through it all.

RS

0201590654P04062001

Editorial Reviews

Offers self-contained coverage of major programming paradigms and the core concepts of programming languages. Chapters on syntactic structure; data representation; concurrent programming; and semantic methods include exercises, plus a look at specific languages. This second edition includes expanded discussion of object-oriented, imperative, and functional programming, and new chapters on data types and programming in ML. Requires an introductory programming course. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews