9780201590654

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

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.

0201590654AB04062001

I INTRODUCTION

1

(54)

The Role of Programming Languages

3

(22)

Toward Higher-Level Languages

4

(4)

Problems of Scale

8

(3)

Programming Paradigms

11

(7)

Language Implementation: Bridging the Gap

18

(7)

Exercises

21

(2)

Bibliographic Notes

23

(2)

Language Description: Syntactic Structure

25

(30)

Expression Notations

28

(3)

Abstract Syntax Trees

31

(2)

Lexical Syntax

33

(2)

Context-Free Grammars

35

(6)

Grammars for Expressions

41

(5)

Variants of Grammars

46

(9)

Exercises

49

(3)

Bibliographic Notes

52

(3)

II IMPERATIVE PROGRAMMING

55

(150)

Statements: Structured Programming

59

(42)

The Need for Structured Programming

59

(4)

Syntax-Directed Control Flow

63

(9)

Design Considerations: Syntax

72

(5)

Handling Special Cases in Loops

77

(3)

Programming with Invariants

80

(6)

Proof Rules for Partial Correctness

86

(4)

Control flow in C

90

(11)

Exercises

94

(5)

Bibliographic Notes

99

(2)

Types: Data Representation

101

(46)

The Role of Types

102

(5)

Basic Types

107

(4)

Arrays: Sequences of Elements

111

(6)

Records: Named Fields

117

(3)

Unions and Variant Records

120

(3)

Sets

123

(2)

Pointers: Efficiency and Dynamic Allocation

125

(8)

Two String Tables

133

(3)

Types and Error Checking

136

(11)

Exercises

143

(3)

Bibliographlc Notes

146

(1)

Procedure Activations

147

(58)

Introduction to Procedures

148

(7)

Parameter-Passing Methods

155

(5)

Scope Rules for Names

160

(6)

Nested Scopes in the Source Text

166

(6)

Activation Records

172

(9)

Lexical Scope: Procedures as in C

181

(9)

Lexical Scope: Nested Procedures and Pascal

190

(15)

Exercises

198

(4)

Bibliographic Notes

202

(3)

III OBJECT-ORIENTED PROGRAMMING

205

(96)

Groupings of Data and Operations

209

(44)

Constructs for Program Structuring

210

(7)

Information Hiding

217

(3)

Program Design with Modules

220

(9)

Modules and Defined Types

229

(3)

Class Declarations in C++

232

(6)

Dynamic Allocation in C++

238

(6)

Templates: Parameterized Types

244

(1)

Implementation of Objects in C++

245

(8)

Exercises

248

(3)

Bibliographic Notes

251

(2)

Object-Oriented Programming

253

(48)

What is an Object?

253

(3)

Object-Oriented Thinking

256

(4)

Inheritance

260

(7)

Object-Oriented Programming in C++

267

(7)

An Extended C++ Example

274

(7)

Derived Classes and Information Hiding

281

(4)

Objects in Smalltalk

285

(6)

Smalltalk Objects have a Self

291

(10)

Exercises

294

(5)

Bibliographic Notes

299

(2)

IV FUNCTIONAL PROGRAMMING

301

(122)

Elements of Functional Programming

305

(36)

A Little Language of Expressions

306

(7)

Types: Values and Operations

313

(5)

Function Declarations

318

(3)

Approaches to Expression Evaluation

321

(6)

Lexical Scope

327

(4)

Type Checking

331

(10)

Exercises

335

(4)

Bibliographic Notes

339

(2)

Functional Programming in a Typed Language

341

(44)

Exploring a List

342

(4)

Function Declaration by Cases

346

(5)

Functions as First-Class Values

351

(6)

ML: Implicit Types

357

(3)

Data Types

360

(7)

Exception Handling in ML

367

(2)

Little Quilt in Standard ML

369

(16)

Exercises

380

(3)

Bibliographic Notes

383

(2)

Functional Programming with Lists

385

(38)

Scheme, a Dialect of Lisp

386

(6)

The Structure of Lists

392

(4)

List Manipulation

396

(8)

A Motivating Example: Differentiation

404

(5)

Simplification of Expressions

409

(4)

Storage Allocation for Lists

413

(10)

Exercises

417

(4)

Bibliographic Notes

421

(2)

V OTHER PARADIGMS

423

(90)

Logic Programming

425

(50)

Computing with Relations

426

(4)

Introduction to Prolog

430

(8)

Data Structures in Prolog

438

(4)

Programming Techniques

442

(8)

Control in Prolog

450

(11)

Cuts

461

(14)

Exercises

470

(2)

Bibliographic Notes

472

(3)

An Introduction to Concurrent Programming

475

(38)

Parallelism in Hardware

476

(2)

Streams: Implicit Synchronization

478

(4)

Concurrency as Interleaving

482

(3)

Liveness Properties

485

(4)

Safe Access to Shared Data

489

(2)

Concurrency in Ada

491

(7)

Synchronized Access to Shared Variables

498

(15)

Exercises

507

(3)

Bibliographic Notes

510

(3)

VI LANGUAGE DESCRIPTION

513

(100)

Semantic Methods

515

(32)

Synthesized Attributes

517

(3)

Attribute Grammars

520

(3)

Natural Semantics

523

(6)

Denotational Semantics

529

(1)

A Calculator in Scheme

530

(2)

Lexically Scoped Lambda Expressions

532

(3)

An Interpreter

535

(7)

An Extension: Recursive Functions

542

(5)

Exercises

545

(1)

Bibliographic Notes

546

(1)

Static Types and the Lambda Calculus

547

(32)

Equality of Pure Lambda Terms

549

(5)

Substitution Revisited

554

(2)

Computation with Pure Lambda Terms

556

(5)

Programming Constructs as Lambda-Terms

561

(5)

The Typed Lambda Calculus

566

(3)

Polymorphic Types

569

(10)

Exercises

576

(1)

Bibliographic Notes

577

(2)

A Look at Some Languages

579

(34)

Pascal: A Teaching Language

579

(4)

C: Systems Programming

583

(8)

C++: A Range of Programming Styles

591

(3)

Smalltalk, the Language

594

(4)

Standard ML

598

(4)

Scheme, a Dialect of Lisp

602

(5)

Prolog

607

(6)

Bibliography

613

(14)

Credits

627

(2)

Index

629

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

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 likewhilestatements 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 la

Amazon no longer offers textbook rentals. We do!

Programming Languages Concepts and Constructs

Programming Languages Concepts and Constructs

0201590654

Summary

Author Biography

Table of Contents

Supplemental Materials

Excerpts

Write a Review