Concepts of Programming Languages, 9th Edition

Chapter 1 Preliminaries 1

1.1 Reasons for Studying Concepts of Programming Languages ...............2

1.2 Programming Domains .....................................................................5

1.3 Language Evaluation Criteria ............................................................7

1.4 Influences on Language Design .......................................................19

1.5 Language Categories .......................................................................22

1.6 Language Design Trade-Offs ............................................................24

1.7 Implementation Methods ................................................................25

1.8 Programming Environments ............................................................32

Summary • Review Questions • Problem Set .............................................33

 

Chapter 2 Evolution of the Major Programming Languages 37

2.1 Zuse’s Plankalkül ...........................................................................38

2.2 Minimal Hardware Programming: Pseudocodes ...............................41

2.3 The IBM 704 and Fortran ..............................................................44

2.4 Functional Programming: LISP ......................................................49

2.5 The First Step Toward Sophistication: ALGOL 60 ............................54

2.6 Computerizing Business Records: COBOL ........................................60

2.7 The Beginnings of Timesharing: BASIC ............................................65

Interview: ALAN COOPER–User Design and Language Design..................68

2.8 Everything for Everybody: PL/I .......................................................70

2.9 Two Early Dynamic Languages: APL and SNOBOL .........................73

2.10 The Beginnings of Data Abstraction: SIMULA 67 ............................74

2.11 Orthogonal Design: ALGOL 68 ........................................................75

2.12 Some Early Descendants of the ALGOLs ......................................... 77

2.13 Programming Based on Logic: Prolog ............................................. 81

2.14 History’s Largest Design Effort: Ada .............................................. 83

2.15 Object-Oriented Programming: Smalltalk ........................................ 87

2.16 Combining Imperative and Object-Oriented Features: C++ ................ 90

2.17 An Imperative-Based Object-Oriented Language: Java ...................... 93

2.18 Scripting Languages ....................................................................... 97

2.19 A C-Based Language for the New Millennium: C# ......................... 103

2.20 Markup/Programming Hybrid Languages ....................................... 106

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises..... 108

 

Chapter 3 Describing Syntax and Semantics 115

3.1 Introduction ................................................................................. 116

3.2 The General Problem of Describing Syntax .................................... 117

3.3 Formal Methods of Describing Syntax ........................................... 119

3.4 Attribute Grammars ..................................................................... 134

History Note......................................................................................... 135

3.5 Describing the Meanings of Programs: Dynamic Semantics ............ 141

History Note........................................................................................ 156

Summary • Bibliographic Notes • Review Questions • Problem Set ...........163

 

Chapter 4 Lexical and Syntax Analysis 171

4.1 Introduction ................................................................................. 172

4.2 Lexical Analysis ........................................................................... 173

4.3 The Parsing Problem .................................................................... 182

4.4 Recursive-Descent Parsing ............................................................ 185

4.5 Bottom-Up Parsing ...................................................................... 194

Summary • Review Questions • Problem Set • Programming Exercises......202

 

Chapter 5 Names, Bindings, and Scopes 207

5.1 Introduction ................................................................................. 208

5.2 Names ......................................................................................... 208

History Note.........................................................................................209

History Note.........................................................................................210

5.3 Variables ......................................................................................211

History Note.........................................................................................212

5.4 The Concept of Binding .................................................................214

Interview: RASMUS LERDORF–Scripting Languages and Other Examples of Slick Solutions .......218

5.5 Scope ...........................................................................................225

History Note.........................................................................................227

5.6 Scope and Lifetime .......................................................................234

5.7 Referencing Environments .............................................................235

5.8 Named Constants ........................................................................237

Summary • Review Questions • Problem Set • Programming Exercises ... 239

 

Chapter 6 Data Types 247

6.1 Introduction .................................................................................248

6.2 Primitive Data Types .....................................................................250

6.3 Character String Types ..................................................................254

History Note.........................................................................................255

6.4 User-Defined Ordinal Types ............................................................259

6.5 Array Types ..................................................................................263

History Note.........................................................................................264

History Note.........................................................................................267

6.6 Associative Arrays ........................................................................277

Interview: ROBERTO IERUSALIMSCHY–Lua ................................280

6.7 Record Types ................................................................................282

6.8 Union Types ..................................................................................287

6.9 Pointer and Reference Types ..........................................................291

History Note.........................................................................................294

6.10 Type Checking ..............................................................................304

6.11 Strong Typing ...............................................................................305

6.12 Type Equivalence ..........................................................................306

6.13 Theory and Data Types .................................................................. 310

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises ......312

 

Chapter 7 Expressions and Assignment Statements 319

7.1 Introduction ................................................................................. 320

7.2 Arithmetic Expressions ................................................................. 321

7.3 Overloaded Operators ................................................................... 330

7.4 Type Conversions .......................................................................... 331

History Note......................................................................................... 334

7.5 Relational and Boolean Expressions .............................................. 335

History Note......................................................................................... 335

7.6 Short-Circuit Evaluation .............................................................. 337

7.7 Assignment Statements ................................................................ 339

History Note......................................................................................... 343

7.8 Mixed-Mode Assignment .............................................................. 343

Summary • Review Questions • Problem Set • Programming Exercises .... 344

 

Chapter 8 Statement-Level Control Structures 349

8.1 Introduction ................................................................................. 350

8.2 Selection Statements .................................................................... 352

History Note......................................................................................... 352

History Note......................................................................................... 354

8.3 Iterative Statements ..................................................................... 365

History Note......................................................................................... 365

Interview: LARRY WALL–Part 1: Linguistics and the Birth of Perl ........ 370

History Note......................................................................................... 378

8.4 Unconditional Branching .............................................................. 380

8.5 Guarded Commands ..................................................................... 381

8.6 Conclusions .................................................................................. 383

Summary • Review Questions • Problem Set • Programming Exercises..... 384

 

Chapter 9 Subprograms 391

9.1 Introduction .................................................................................392

9.2 Fundamentals of Subprograms ......................................................392

9.3 Design Issues for Subprograms .....................................................403

9.4 Local Referencing Environments ...................................................404

9.5 Parameter-Passing Methods .........................................................406

Interview: LARRY WALL–Part 2: Scripting Languages in General and Perl in Particular ........408

History Note.........................................................................................416

History Note.........................................................................................416

History Note.........................................................................................420

9.6 Parameters That Are Subprograms ................................................427

History Note.........................................................................................429

9.7 Overloaded Subprograms ..............................................................429

9.8 Generic Subprograms ...................................................................431

9.9 Design Issues for Functions ...........................................................438

9.10 User-Defined Overloaded Operators ...............................................439

9.11 Coroutines ....................................................................................440

History Note.........................................................................................440

Summary • Review Questions • Problem Set • Programming Exercises .....442

 

Chapter 10 Implementing Subprograms 449

10.1 The General Semantics of Calls and Returns .................................450

10.2 Implementing “Simple” Subprograms ..........................................451

10.3 Implementing Subprograms with Stack-Dynamic Local Variables ...............453

10.4 Nested Subprograms ...................................................................462

Interview: NIKLAUS WIRTH–Keeping It Simple ............................464

10.5 Blocks ........................................................................................470

10.6 Implementing Dynamic Scoping ...................................................472

Summary • Review Questions • Problem Set • Programming Exercises ....475

 

Chapter 11 Abstract Data Types and Encapsulation Constructs 481

11.1 The Concept of Abstraction ......................................................... 482

11.2 Introduction to Data Abstraction ................................................. 483

11.3 Design Issues for Abstract Data Types .......................................... 486

11.4 Language Examples .................................................................... 487

Interview: BJARNE STROUSTRUP–C++: Its Birth, Its Ubiquitousness, and Common Criticisms ....... 490

11.5 Parameterized Abstract Data Types .............................................. 504

11.6 Encapsulation Constructs ............................................................ 508

11.7 Naming Encapsulations ............................................................... 512

Summary • Review Questions • Problem Set • Programming Exercises .... 517

 

Chapter 12 Support for Object-Oriented Programming 523

12.1 Introduction ................................................................................ 524

12.2 Object-Oriented Programming ...................................................... 524

12.3 Design Issues for Object-Oriented Languages ................................ 527

12.4 Support for Object-Oriented Programming in Smalltalk ................ 532

12.5 Support for Object-Oriented Programming in C++ ........................ 535

Interview: BJARNE STROUSTRUP–On Paradigms and Better Programming ........ 536

12.6 Support for Object-Oriented Programming in Java ........................ 546

12.7 Support for Object-Oriented Programming in C# .......................... 550

12.8 Support for Object-Oriented Programming in Ada 95 .................... 552

12.9 Support for Object-Oriented Programming in Ruby........................ 557

12.10 Implementation of Object-Oriented Constructs .............................. 560

Summary • Review Questions • Problem Set • Programming Exercises..... 564

 

Chapter 13 Concurrency 569

13.1 Introduction ................................................................................ 570

13.2 Introduction to Subprogram-Level Concurrency ............................ 574

History Note ....................................................................................... 577

13.3 Semaphores ................................................................................ 578

13.4 Monitors .....................................................................................583

13.5 Message Passing .........................................................................585

13.6 Ada Support for Concurrency .......................................................587

13.7 Java Threads ...............................................................................598

13.8 C# Threads ..................................................................................606

13.9 Statement-Level Concurrency ......................................................608

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises .....610

 

Chapter 14 Exception Handling and Event Handling 615

14.1 Introduction to Exception Handling ..............................................616

History Note........................................................................................620

14.2 Exception Handling in Ada ..........................................................622

14.3 Exception Handling in C++ ..........................................................629

14.4 Exception Handling in Java ..........................................................634

Interview: JAMES GOSLING–The Birth of Java .............................636

14.5 Introduction to Event Handling ....................................................643

14.6 Event Handling with Java ............................................................644

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises ..... 650

 

Chapter 15 Functional Programming Languages 655

15.1 Introduction ................................................................................656

15.2 Mathematical Functions ..............................................................657

15.3 Fundamentals of Functional Programming Languages ..................659

15.4 The First Functional Programming Language: LISP .....................661

15.5 An Introduction to Scheme ..........................................................664

15.6 COMMON LISP ..........................................................................682

15.7 ML .............................................................................................682

15.8 Haskell .......................................................................................686

15.9 Applications of Functional Languages ..........................................691

15.10 A Comparison of Functional and Imperative Languages ................692

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises ....694

 

Chapter 16 Logic Programming Languages 701

16.1 Introduction ................................................................................ 702

16.2 A Brief Introduction to Predicate Calculus ................................... 702

16.3 Predicate Calculus and Proving Theorems .................................... 706

16.4 An Overview of Logic Programming ............................................. 708

16.5 The Origins of Prolog .................................................................. 710

16.6 The Basic Elements of Prolog ...................................................... 711

16.7 Deficiencies of Prolog .................................................................. 725

16.8 Applications of Logic Programming ............................................ 731

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises.... 733

Bibliography ...............................................................................737

Index ..........................................................................................747