Concepts of Programming Languages by Robert W. Sebesta

From the Publisher

This best-selling book, now in its fourth edition, provides a wide-ranging and in-depth discussion of programming language concepts. As in previous editions, the author describes fundamental concepts of programming languages by presenting design issues of the various language constructs, examining the design choices for these constructs in a few common languages, and critically comparing the design alternatives. The book covers the most widely used methods of syntax description and introduces the most common approaches to describing the semantics of programming languages. Discussions of implementation methods and issues are integrated throughout the book.

Booknews

A textbook that describes fundamental concepts of programming languages by defining the design issues of the various language constructs, examining the design choices for these constructs in some of the most common languages, and critically comparing the design alternatives. This revised edition includes new coverage of C++, Ada 95, and other recent developments in programming languages; and adds collections of review questions to all chapters. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Product Details

• Table of Contents
• Forewords & Introductions
• Read an Excerpt

Table of Contents

Forewords & Introductions

The goals, overall structure, and approach of this third edition of Concepts of Programming Languages remain the same as those of the two earlier editions. The principal goal is to provide the reader with the tools necessary for the critical evaluation of eXisting and future programming languages and constructs. An additional goal is to prepare the reader for the study of compiler design and construction.

The book should also answer a myriad of questions that may have occurred to the reader who may know only one highlevel programming language. For eXample, why are there so many different programming languages? How and why were they developed? In what ways are they similar? What are their differences? What kinds of programming languages may be developed and used in the future? Why wouldn't we simply continue to use what we have now?

There are two ways in which a book on the concepts of programming languages can be organized: a horizontal approach and a vertical approach. With the horizontal approach, each language selected is presented in some depth. With the vertical approach, the general concepts and constructs of programming languages are described in some particular sequence. For each construct, design issues are eXplored and eXamples from a variety of languages are presented. Both methods have merit. In order to accurately describe individual language concepts it is important to focus on the concepts and consider their impact on programming and the evolution of languages. However, a chronological analysis of language developments necessitates the study of specific languages and their origins anddevelopment.Furthermore, the design of a specific facility of a particular language is often influenced by other characteristics of the language. Because of these considerations, this book uses the vertical approach for the majority of the material, but the horizontal approach when it is advantageous.

In this book I describe the fundamental concepts of programming languages by defining the design issues of the various language constructs, eXamining the design choices for these constructs in some of the most common languages, and critically comparing the design alternatives.

Taking this approach requires studying a collection of closely related topics. To discuss languages and language constructs, descriptive tools are vital. I discuss in detail the most effective and widely used methods of syntaX description. I also introduce the most common methods for describing the semantics of programming languages. To understand some of the reasons why the particular design choices for eXisting languages were made, I describe the historical conteXt and specific needs that spawned them. Because difficulty of implementation is often a significant influence on language design, discussions of implementation methods and issues are integrated throughout the book.

The following paragraphs outline the contents of the third edition.

Chapter 1 begins with a rationale for studying programming languages. It then discusses the criteria for evaluating programming languages. I recognize that defining these criteria is risky; however, evaluation principles are essential to any serious study of the design of programming languages. The primary influences on language design, common design tradeoffs, and the basic approaches to implementation are also eXamined in the chapter.

Chapter 2 uses the horizontal approach to chart the chronological evolution of most of the important languages discussed in this book. Although no language is described completely, the origins, purposes, and contributions of each are discussed. This historical overview is valuable because it provides the background necessary to understanding the practical and theoretical basis for contemporary language design. It also motivates the further study of language design and evaluation. However, since none of the remainder of the book depends on Chapter 2, it can be skipped in its entirety.

Chapter 3 describes the primary formal methods for describing the syntaX of programming languages: EBNF and syntaX graphs. This is followed by a description of attribute grammars, which play a prominent role in compiler design. The difficult task of semantic description is then eXplored, including brief introductions to the three most common methods: operational, aXiomatic, and denotational semantics.

Chapters 412 use the vertical approach to describe in detail the design issues for the primary constructs of the imperative languages. In each case, the design choices for several eXample languages are presented and evaluated. Specifically, the many characteristics of variables are covered in Chapter 4; more complicated data types in Chapter 5; eXpressions and assignment statements in Chapter 6; control statements in Chapter 7; subprograms and their implementation in Chapters 8 and 9; data abstraction facilities in Chapter 10; concurrent program units in Chapter 11; eXception handling in Chapter 12. I use the vertical approach because it is inappropriate to describe and evaluate the details of a particular construct in several different parts of the book, as the horizontal approach would require for these topics. Discussing in a single chapter the various methods for providing concurrency, for eXample, allows for a concise comparison and evaluation of those methods.

The last three chapters, 13, 14, and 15, describe three of the most important alternative programming paradigms: functional programming, logic programming, and objectoriented programming. Each is discussed as a programming methodology, and then eXemplified through a brief introduction to a specific language.

Specifically, Chapter 13 begins by discussing simple mathematical functions, functional forms, and functional programming languages. It then presents an introduction to Scheme, including descriptions of some of its primitive functions, special forms, functional forms, and some eXamples of simple functions written in Scheme. Brief introductions to COMMON LISP, ML, and Miranda are given to illustrate some different kinds of functional languages. The chapter concludes with a comparison of functional and imperative languages.

The topic of Chapter 14 is logic programming and logic programming languages. I begin by introducing predicate calculus and eXplaining how it is used to prove theorems. This is followed by an overview of logic programming. The bulk of the chapter is an introduction to Prolog, including descriptions of resolution and unification, and some eXample programs and descriptions of their behavior.

Chapter 15 is on objectoriented programming and objectoriented programming languages. After the principles of objectoriented programming have been introduced, a subset of Smalltalk is described, including two complete eXample programs. Features of C++ and Ada 95 that support objectoriented programming are then described. Comparisons are then made between Smalltalk and C++ and between C++ and Ada 95.

Changes for the Third Edition

The third edition of this book is a significant revision of the second edition. Many of the changes result from the continuing evolution of currently popular languages. Others reflect changes in the computer science curriculums of many colleges and universities. The following paragraphs list the most important of these changes.

The first and second editions of this book were written with the assumption that most of the students who would use it already knew either Pascal or Modula2. EXample programs could be in either of these two languages or in Ada, which is based on Pascal. Because there has been a dramatic shift from the use of Pascal and Modula2 in CS1 and CS2 courses, primarily to C, C++, and Ada, the dependence on prior knowledge of Pascal is no longer reasonable. Therefore, many of the eXample programs and code segments from the second edition that were in Pascal or Modula2 have been replaced in the third edition by similar programs and code segments written in C, C++, or Ada.

Because of the new features of C++ and Ada 95, several new sections have been added. These discuss the templated functions and templated classes of C++, the eXception handling of C++, Ada 95 protected objects, asynchronous task communications, and, perhaps most important, Ada 95 inheritance.

The appearance of High Performance FORTRAN, with its importance to parallel programming, prompted the addition of a section describing the primary features of that language. To complement this addition, a new section has been added that discusses the primary categories of parallel computer architectures.

Because of the declining popularity of flowcharts, they have been replaced in the third edition by operational semantics descriptions to describe control structures.

Chapter 13, on functional programming, now uses Scheme as its primary language because of the easy availability of Scheme interpreters. Also added to this chapter are brief descriptions of the most interesting features of ML and Miranda.

To help promote the importance of formal syntaX description, I have added to Chapter 3 a section that briefly introduces recursive descent parsing. The sections in Chapter 3 on attribute grammars and aXiomatic semantics have been strengthened.

Besides adding new features of new language versions, I have deleted some discussion of older languages. For eXample, ALGOL 68 pointers, SIMULA 67 coroutines, and CLU eXception handling have been dropped.

Numerous smaller changes ensure that the third edition correctly reflects the current state of programming language evolution. Finally, collections of review questions have been added to every chapter in the book.

To the Instructor.

In the juniorlevel programming language course at the University of Colorado at Colorado Springs, the book is used as follows. We typically cover Chapters 1 and 3 in detail. Chapter 2 requires little lecture time because of its lack of hard technical content. Students find it interesting and beneficial reading, however. Because no material in subsequent chapters depends on Chapter 2, it can, as noted earlier, be skipped entirely.

Chapters 48 and 10 should be relatively easy for students with eXtensive programming eXperience in Pascal, C, C++, Modula2, or Ada. Chapters 9, 11, and 12 are more challenging and require more detailed lectures.

Chapters 1315 are entirely new to most students at the junior level. Ideally, language processors for Scheme and Prolog should be available for Chapters 13 and 14. Sufficient material is included in these chapters to allow students to dabble with some simple programs. Use of Smalltalk requires, beyond the material in Chapter 15, an introduction to its user interface, which is not included here.

Undergraduate courses will probably not be able to cover all of the last three chapters in detail. Graduate courses, however, by skipping over parts of the early chapters on imperative languages will be able to completely discuss the nonimperative languages.

Supplements

Two important and useful supplements are available for this book. A diskbased solutions manual (ISBN 895374) that includes answers to many of the problems in the chapter problem sets can be obtained upon request from an AddisonWesley Publishing sales representative. A set of lecture notes slides is also available. These slides are in the form of Microsoft Powerpoint source files, one for each of the first 12 chapters of the book. I developed them over the past few years in teaching a course based on the book. The Powerpoint files are available through an anonymous ftp account on aw.com in directory cseng/authors/sebesta. Please check the README or .message files at this site for further details and information on this and other supplements.

Acknowledgments

The quality of this book was significantly improved as a result of the eXtensive suggestions, corrections, and comments provided by its reviewers. The first two editions were reviewed by Vicki Allan, Henry Bauer, Peter Brouwer, John Crenshaw, Mary Lou Haag, Jon Mauney, Robert McCoard, Andrew Oldroyd, Jeffery Popyack, Hamilton Richard, and Mary Louise Soffa. The third edition was reviewed by:

• Paosheng Chang, University of Oklahoma at Norman
• Barbara Ann Greim, University of North Carolina at Wilmington
• Mary Lou Haag, University of Colorado at Colorado Springs
• Michael G. Murphy, Southern College of Technology
• Steven Rapkin, College of William & Mary
• Tom Sager, University of Missouri at Rolla
• Joseph Schell, University of North Carolina at Charlotte

Carter Shanklin, acquisitions editor for the second and third editions, Christine Kulke, assistant editor, Juliet Silveri, production supervisor, and Barbara Conway, copyeditor, all deserve my gratitude for their efforts to make the third edition significantly better than the second.

Finally, I thank my wife, Joanne, and our children, Jake and Darcie, for their patience in enduring my absence from them throughout the endless hours of effort I invested in writing the three editions of this book.

Read an Excerpt

The goals, overall structure, and approach of this third edition of Concepts of Programming Languages remain the same as those of the two earlier editions. The principal goal is to provide the reader with the tools necessary for the critical evaluation of eXisting and future programming languages and constructs. An additional goal is to prepare the reader for the study of compiler design and construction.

The book should also answer a myriad of questions that may have occurred to the reader who may know only one highlevel programming language. For eXample, why are there so many different programming languages? How and why were they developed? In what ways are they similar? What are their differences? What kinds of programming languages may be developed and used in the future? Why wouldn't we simply continue to use what we have now?

There are two ways in which a book on the concepts of programming languages can be organized: a horizontal approach and a vertical approach. With the horizontal approach, each language selected is presented in some depth. With the vertical approach, the general concepts and constructs of programming languages are described in some particular sequence. For each construct, design issues are eXplored and eXamples from a variety of languages are presented. Both methods have merit. In order to accurately describe individual language concepts it is important to focus on the concepts and consider their impact on programming and the evolution of languages. However, a chronological analysis of language developments necessitates the study of specific languages and their origins and development.Furthermore, the design of a specific facility of a particular language is often influenced by other characteristics of the language. Because of these considerations, this book uses the vertical approach for the majority of the material, but the horizontal approach when it is advantageous.

In this book I describe the fundamental concepts of programming languages by defining the design issues of the various language constructs, eXamining the design choices for these constructs in some of the most common languages, and critically comparing the design alternatives.

Taking this approach requires studying a collection of closely related topics. To discuss languages and language constructs, descriptive tools are vital. I discuss in detail the most effective and widely used methods of syntaX description. I also introduce the most common methods for describing the semantics of programming languages. To understand some of the reasons why the particular design choices for eXisting languages were made, I describe the historical conteXt and specific needs that spawned them. Because difficulty of implementation is often a significant influence on language design, discussions of implementation methods and issues are integrated throughout the book.

The following paragraphs outline the contents of the third edition.

Chapter 1 begins with a rationale for studying programming languages. It then discusses the criteria for evaluating programming languages. I recognize that defining these criteria is risky; however, evaluation principles are essential to any serious study of the design of programming languages. The primary influences on language design, common design tradeoffs, and the basic approaches to implementation are also eXamined in the chapter.

Chapter 2 uses the horizontal approach to chart the chronological evolution of most of the important languages discussed in this book. Although no language is described completely, the origins, purposes, and contributions of each are discussed. This historical overview is valuable because it provides the background necessary to understanding the practical and theoretical basis for contemporary language design. It also motivates the further study of language design and evaluation. However, since none of the remainder of the book depends on Chapter 2, it can be skipped in its entirety.

Chapter 3 describes the primary formal methods for describing the syntaX of programming languages: EBNF and syntaX graphs. This is followed by a description of attribute grammars, which play a prominent role in compiler design. The difficult task of semantic description is then eXplored, including brief introductions to the three most common methods: operational, aXiomatic, and denotational semantics.

Chapters 412 use the vertical approach to describe in detail the design issues for the primary constructs of the imperative languages. In each case, the design choices for several eXample languages are presented and evaluated. Specifically, the many characteristics of variables are covered in Chapter 4; more complicated data types in Chapter 5; eXpressions and assignment statements in Chapter 6; control statements in Chapter 7; subprograms and their implementation in Chapters 8 and 9; data abstraction facilities in Chapter 10; concurrent program units in Chapter 11; eXception handling in Chapter 12. I use the vertical approach because it is inappropriate to describe and evaluate the details of a particular construct in several different parts of the book, as the horizontal approach would require for these topics. Discussing in a single chapter the various methods for providing concurrency, for eXample, allows for a concise comparison and evaluation of those methods.

The last three chapters, 13, 14, and 15, describe three of the most important alternative programming paradigms: functional programming, logic programming, and objectoriented programming. Each is discussed as a programming methodology, and then eXemplified through a brief introduction to a specific language.

Specifically, Chapter 13 begins by discussing simple mathematical functions, functional forms, and functional programming languages. It then presents an introduction to Scheme, including descriptions of some of its primitive functions, special forms, functional forms, and some eXamples of simple functions written in Scheme. Brief introductions to COMMON LISP, ML, and Miranda are given to illustrate some different kinds of functional languages. The chapter concludes with a comparison of functional and imperative languages.

The topic of Chapter 14 is logic programming and logic programming languages. I begin by introducing predicate calculus and eXplaining how it is used to prove theorems. This is followed by an overview of logic programming. The bulk of the chapter is an introduction to Prolog, including descriptions of resolution and unification, and some eXample programs and descriptions of their behavior.

Chapter 15 is on objectoriented programming and objectoriented programming languages. After the principles of objectoriented programming have been introduced, a subset of Smalltalk is described, including two complete eXample programs. Features of C++ and Ada 95 that support objectoriented programming are then described. Comparisons are then made between Smalltalk and C++ and between C++ and Ada 95.

Changes for the Third Edition

The third edition of this book is a significant revision of the second edition. Many of the changes result from the continuing evolution of currently popular languages. Others reflect changes in the computer science curriculums of many colleges and universities. The following paragraphs list the most important of these changes.

The first and second editions of this book were written with the assumption that most of the students who would use it already knew either Pascal or Modula2. EXample programs could be in either of these two languages or in Ada, which is based on Pascal. Because there has been a dramatic shift from the use of Pascal and Modula2 in CS1 and CS2 courses, primarily to C, C++, and Ada, the dependence on prior knowledge of Pascal is no longer reasonable. Therefore, many of the eXample programs and code segments from the second edition that were in Pascal or Modula2 have been replaced in the third edition by similar programs and code segments written in C, C++, or Ada.

Because of the new features of C++ and Ada 95, several new sections have been added. These discuss the templated functions and templated classes of C++, the eXception handling of C++, Ada 95 protected objects, asynchronous task communications, and, perhaps most important, Ada 95 inheritance.

The appearance of High Performance FORTRAN, with its importance to parallel programming, prompted the addition of a section describing the primary features of that language. To complement this addition, a new section has been added that discusses the primary categories of parallel computer architectures.

Because of the declining popularity of flowcharts, they have been replaced in the third edition by operational semantics descriptions to describe control structures.

Chapter 13, on functional programming, now uses Scheme as its primary language because of the easy availability of Scheme interpreters. Also added to this chapter are brief descriptions of the most interesting features of ML and Miranda.

To help promote the importance of formal syntaX description, I have added to Chapter 3 a section that briefly introduces recursive descent parsing. The sections in Chapter 3 on attribute grammars and aXiomatic semantics have been strengthened.

Besides adding new features of new language versions, I have deleted some discussion of older languages. For eXample, ALGOL 68 pointers, SIMULA 67 coroutines, and CLU eXception handling have been dropped.

Numerous smaller changes ensure that the third edition correctly reflects the current state of programming language evolution. Finally, collections of review questions have been added to every chapter in the book.

To the Instructor.

In the juniorlevel programming language course at the University of Colorado at Colorado Springs, the book is used as follows. We typically cover Chapters 1 and 3 in detail. Chapter 2 requires little lecture time because of its lack of hard technical content. Students find it interesting and beneficial reading, however. Because no material in subsequent chapters depends on Chapter 2, it can, as noted earlier, be skipped entirely.

Chapters 48 and 10 should be relatively easy for students with eXtensive programming eXperience in Pascal, C, C++, Modula2, or Ada. Chapters 9, 11, and 12 are more challenging and require more detailed lectures.

Chapters 1315 are entirely new to most students at the junior level. Ideally, language processors for Scheme and Prolog should be available for Chapters 13 and 14. Sufficient material is included in these chapters to allow students to dabble with some simple programs. Use of Smalltalk requires, beyond the material in Chapter 15, an introduction to its user interface, which is not included here.

Undergraduate courses will probably not be able to cover all of the last three chapters in detail. Graduate courses, however, by skipping over parts of the early chapters on imperative languages will be able to completely discuss the nonimperative languages.

Supplements

Two important and useful supplements are available for this book. A diskbased solutions manual (ISBN 895374) that includes answers to many of the problems in the chapter problem sets can be obtained upon request from an AddisonWesley Publishing sales representative. A set of lecture notes slides is also available. These slides are in the form of Microsoft Powerpoint source files, one for each of the first 12 chapters of the book. I developed them over the past few years in teaching a course based on the book. The Powerpoint files are available through an anonymous ftp account on aw.com in directory cseng/authors/sebesta. Please check the README or .message files at this site for further details and information on this and other supplements.

Acknowledgments

The quality of this book was significantly improved as a result of the eXtensive suggestions, corrections, and comments provided by its reviewers. The first two editions were reviewed by Vicki Allan, Henry Bauer, Peter Brouwer, John Crenshaw, Mary Lou Haag, Jon Mauney, Robert McCoard, Andrew Oldroyd, Jeffery Popyack, Hamilton Richard, and Mary Louise Soffa. The third edition was reviewed by:

• Paosheng Chang, University of Oklahoma at Norman
• Barbara Ann Greim, University of North Carolina at Wilmington
• Mary Lou Haag, University of Colorado at Colorado Springs
• Michael G. Murphy, Southern College of Technology
• Steven Rapkin, College of William & Mary
• Tom Sager, University of Missouri at Rolla
• Joseph Schell, University of North Carolina at Charlotte

Carter Shanklin, acquisitions editor for the second and third editions, Christine Kulke, assistant editor, Juliet Silveri, production supervisor, and Barbara Conway, copyeditor, all deserve my gratitude for their efforts to make the third edition significantly better than the second.

Finally, I thank my wife, Joanne, and our children, Jake and Darcie, for their patience in enduring my absence from them throughout the endless hours of effort I invested in writing the three editions of this book.