Programming Languages / Edition 2

by Allen Tucker, Robert Noonan

Overview

Most current programming language text that provides a balanced mix of explanation and experimentation. Opening chapters present the fundamental principals of programming languages, while optional companion chapters provide implementation-based, hands-on experience that delves even deeper. This edition also includes a greatly expanded treatment of the four major programming paradigms, incorporating a number of the most current languages such as Perl and Python. Special topics presented include event-handling, concurrency, and an all-new chapter on correctness. Overall, this edition provides both broad and deep coverage of language design principles and the major paradigms, allowing users the flexibility of choosing what topics to emphasize.

Product Details

ISBN-13:	9780072866094
Publisher:	McGraw-Hill Professional Publishing
Publication date:	08/14/2006
Edition description:	New Edition
Pages:	624
Product dimensions:	7.30(w) x 9.40(h) x 1.13(d)

Table of Contents

Overview     1
Principles     2
Paradigms     3
Special Topics     5
A Brief History     6
On Language Design     11
Design Constraints     11
Outcomes and Goals     14
Compilers and Virtual Machines     18
Summary     20
Exercises     21
Syntax     23
Grammars     24
Backus-Naur Form (BNF) Grammars     25
Derivations     26
Parse Trees     28
Associativity and Precedence     30
Ambiguous Grammars     31
Extended BNF     35
Syntax of a Small Language: Clite     37
Lexical Syntax     39
Concrete Syntax     41
Compilers and Interpreters     42
Linking Syntax and Semantics     48
Abstract Syntax     49
Abstract Syntax Trees     51
Abstract Syntax of Clite     51
Summary     54
Exercises     55
Lexical and Syntactic Analysis     57
Chomsky Hierarchy     58
Lexical Analysis     60
Regular Expressions     62
Finite State Automata     63
From Design to Code     67
Syntactic Analysis     70
Preliminary Definitions     71
Recursive Descent Parsing     74
Summary     82
Exercises     82
Names     85
Syntactic Issues     86
Variables     88
Scope     89
Symbol Table     92
Resolving References     93
Dynamic Scoping     94
Visibility     95
Overloading     96
Lifetime     98
Summary     99
Exercises     99
Types     101
Type Errors     102
Static and Dynamic Typing     104
Basic Types     105
Nonbasic Types     112
Enumerations     112
Pointers     113
Arrays and Lists     115
Strings     119
Structures     120
Variant Records and Unions     121
Recursive Data Types     123
Functions as Types     124
Type Equivalence     125
Subtypes      126
Polymorphism and Generics     127
Programmer-Defined Types     132
Summary     133
Exercises     133
Type Systems     135
Type System for Clite     137
Implicit Type Conversion     144
Formalizing the Clite Type System     147
Summary     150
Exercises     151
Semantics     153
Motivation     154
Expression Semantics     155
Notation     155
Associativity and Precedence     157
Short Circuit Evaluation     158
The Meaning of an Expression     159
Program State     160
Assignment Semantics     162
Multiple Assignment     162
Assignment Statements vs. Assignment Expressions     163
Copy vs. Reference Semantics     163
Control Flow Semantics     164
Sequence     164
Conditionals     165
Loops     166
Go To Controversy     168
Input/Output Semantics     169
Basic Concepts     170
Random Access Files     175
I/O Error Handling Semantics      177
Exception Handling Semantics     179
Strategies and Design Issues     181
Exception Handling in Ada, C++, and Java     183
Exceptions and Assertions     191
Summary     194
Exercises     194
Semantic Interpretation     197
State Transformations and Partial Functions     198
Semantics of Clite     199
Meaning of a Program     199
Statement Semantics     201
Expression Semantics     205
Expressions with Side Effects     209
Semantics with Dynamic Typing     210
A Formal Treatment of Semantics     214
State and State Transformation     214
Denotational Semantics of a Program     216
Denotational Semantics of Statements     217
Denotational Semantics of Expressions     220
Limits of Formal Semantic Models     222
Summary     222
Exercises     222
Functions     225
Basic Terminology     226
Function Call and Return     226
Parameters     227
Parameter Passing Mechanisms     229
Pass by Value     229
Pass by Reference      231
Pass by Value-Result and Result     233
Pass by Name     234
Parameter Passing in Ada     235
Activation Records     236
Recursive Functions     237
Run-Time Stack     238
Summary     240
Exercises     241
Function Implementation     243
Function Declaration and Call in Clite     244
Concrete Syntax     244
Abstract Syntax     246
Completing the Clite Type System     247
Semantics of Function Call and Return     249
Non-Void Functions     250
Side Effects Revisited     251
Formal Treatment of Types and Semantics     252
Type Maps for Clite     252
Formalizing the Type Rules for Clite     254
Formalizing the Semantics of Clite     255
Summary     260
Exercises     260
Memory Management     263
The Heap     264
Implementation of Dynamic Arrays     266
Heap Management Problems: Garbage     267
Garbage Collection     268
Reference Counting     269
Mark-Sweep     271
Copy Collection     273
Comparison of Strategies     274
Summary     275
Exercises     276
Imperative Programming     277
What Makes a Language Imperative?     278
Procedural Abstraction     280
Expressions and Assignment     281
Library Support for Data Structures     283
Imperative Programming and C     284
General Characteristics     285
Example: Grep     286
Example: Average     288
Example: Symbolic Differentiation     289
Imperative Programming and ADA     290
General Characteristics     293
Example: Average     295
Example: Matrix Multiplication     296
Imperative Programming and Perl     296
General Characteristics     299
Example: Grep     300
Example: Mailing Grades     303
Summary     307
Exercises     307
Object-Oriented Programming     309
Prelude: Abstract Data Types     310
The Object Model     315
Classes     315
Visibility and Information Hiding     318
Inheritance      319
Multiple Inheritance     321
Polymorphism     323
Templates     325
Abstract Classes     326
Interfaces     327
Virtual Method Table     329
Run-Time Type Identification     330
Reflection     331
Smalltalk     332
General Characteristics     333
Example: Polynomials     336
Example: Complex Numbers     338
Example: Bank Account     340
Java     340
Example: Symbolic Differentiation     341
Example: Backtracking     343
Python     350
General Characteristics     351
Example: Polynomials     352
Example: Fractions     354
Summary     356
Exercises     357
Functional Programming     361
Functions and the Lambda Calculus     362
Scheme     366
Expressions     367
Expression Evaluation     368
Lists     368
Elementary Values     371
Control Flow     372
Defining Functions     372
Let Expressions      375
Example: Semantics of Clite     378
Example: Symbolic Differentiation     382
Example: Eight Queens     384
Haskell     388
Introduction     389
Expressions     390
Lists and List Comprehensions     391
Elementary Types and Values     394
Control Flow     395
Defining Functions     395
Tuples     399
Example: Semantics of Clite     400
Example: Symbolic Differentiation     404
Example: Eight Queens     405
Summary     408
Exercises     408
Logic Programming     413
Logic and Horn Clauses     414
Resolution and Unification     416
Logic Programming in Prolog     417
Prolog Program Elements     417
Practical Aspects of Prolog     425
Prolog Examples     430
Symbolic Differentiation     430
Solving Word Puzzles     431
Natural Language Processing     433
Semantics of Clite     436
Eight Queens Problem     440
Summary     443
Exercises     443
Event-Driven Programming     447
Event-Driven Control     448
Model-View-Controller     449
Events in Java     450
Java GUI Applications     453
Event Handling     454
Mouse Clicks     454
Mouse Motion     456
Buttons     456
Labels, TextAreas, and TextFields     458
Combo Boxes     459
Three Examples     461
A Simple GUI Interface     461
Designing a Java Applet     467
Event-Driven Interactive Games     468
Other Event-Driven Applications     476
ATM Machine     476
Home Security System     478
Summary     479
Exercises     479
Concurrent Programming     483
Concurrency Concepts     484
History and Definitions     485
Thread Control and Communication     486
Races and Deadlocks     487
Synchronization Strategies     490
Semaphores     490
Monitors     491
Synchronization in Java     494
Java Threads     494
Examples     496
Interprocess Communication      506
IP Addresses, Ports, and Sockets     507
A Client-Server Example     507
Concurrency in Other Languages     513
Summary     515
Exercises     516
Program Correctness     519
Axiomatic Semantics     521
Fundamental Concepts     521
The Assignment Rule     524
Rules of Consequence     525
Correctness of the Max Function     526
Correctness of Programs with Loops     527
Perspectives on Formal Methods     530
Formal Methods Tools: JML     532
JML Exception Handling     538
Correctness of Object-Oriented Programs     539
Design By Contract     540
The Class Invariant     541
Example: Correctness of a Stack Application     542
Final Observations     548
Correctness of Functional Programs     548
Recursion and Induction     549
Examples of Structural Induction     550
Summary     553
Exercises     553
Definition of Clite     557
Lexical and Concrete Syntax of Clite     558
Abstract Syntax of Clite      559
Type System of Clite     559
Semantics of Clite     561
Adding Functions to Clite     563
Lexical and Concrete Syntax     563
Abstract Syntax     564
Type System     564
Semantics     565
Discrete Math Review     567
Sets and Relations     567
Graphs     571
Logic     572
Inference Rules and Direct Proof     576
Proof by Induction     577
Glossary     579
Bibliography     587
Index     591