Programming Language Design Concepts

Team DDU......Page 1
Contents......Page 8
Preface......Page 16
Part I: Introduction......Page 20
1.1.1 Concepts and paradigms......Page 22
1.1.2 Syntax, semantics, and pragmatics......Page 24
1.2 Historical development......Page 25
Exercises......Page 29
Part II: Basic Concepts......Page 32
2.1 Types......Page 34
2.2.1 Built-in primitive types......Page 35
2.2.2 Defined primitive types......Page 37
2.2.3 Discrete primitive types......Page 38
2.3 Composite types......Page 39
2.3.1 Cartesian products, structures, and records......Page 40
2.3.2 Mappings, arrays, and functions......Page 42
2.3.3 Disjoint unions, discriminated records, and objects......Page 46
2.4.1 Lists......Page 52
2.4.2 Strings......Page 54
2.4.3 Recursive types in general......Page 55
2.5 Type systems......Page 56
2.5.1 Static vs dynamic typing......Page 57
2.5.2 Type equivalence......Page 59
2.5.3 The Type Completeness Principle......Page 61
2.6.1 Literals......Page 62
2.6.2 Constructions......Page 63
2.6.3 Function calls......Page 65
2.6.4 Conditional expressions......Page 66
2.6.5 Iterative expressions......Page 67
2.7.1 Representation of primitive types......Page 68
2.7.3 Representation of arrays......Page 69
2.7.5 Representation of recursive types......Page 70
Exercises......Page 71
3.1 Variables and storage......Page 76
3.2 Simple variables......Page 77
3.3 Composite variables......Page 78
3.3.1 Total vs selective update......Page 79
3.3.2 Static vs dynamic vs flexible arrays......Page 80
3.4 Copy semantics vs reference semantics......Page 82
3.5.1 Global and local variables......Page 85
3.5.2 Heap variables......Page 87
3.5.3 Persistent variables......Page 90
3.6 Pointers......Page 92
3.6.1 Pointers and recursive types......Page 93
3.6.2 Dangling pointers......Page 94
3.7.2 Assignments......Page 96
3.7.3 Proper procedure calls......Page 97
3.7.5 Collateral commands......Page 98
3.7.6 Conditional commands......Page 99
3.7.7 Iterative commands......Page 101
3.8 Expressions with side effects......Page 104
3.8.1 Command expressions......Page 105
3.9 Implementation notes......Page 106
3.9.1 Storage for global and local variables......Page 107
3.9.2 Storage for heap variables......Page 108
3.9.3 Representation of dynamic and flexible arrays......Page 109
Further reading......Page 110
Exercises......Page 111
4.1 Bindings and environments......Page 114
4.2.1 Block structure......Page 116
4.2.2 Scope and visibility......Page 118
4.2.3 Static vs dynamic scoping......Page 119
4.3.1 Type declarations......Page 121
4.3.3 Variable declarations......Page 123
4.3.5 Collateral declarations......Page 124
4.3.6 Sequential declarations......Page 125
4.3.7 Recursive declarations......Page 126
4.4 Blocks......Page 127
4.4.1 Block commands......Page 128
4.4.3 The Qualification Principle......Page 129
Summary......Page 130
Exercises......Page 131
5.1 Function procedures and proper procedures......Page 134
5.1.1 Function procedures......Page 135
5.1.2 Proper procedures......Page 137
5.1.3 The Abstraction Principle......Page 139
5.2 Parameters and arguments......Page 141
5.2.1 Copy parameter mechanisms......Page 143
5.2.2 Reference parameter mechanisms......Page 144
5.2.3 The Correspondence Principle......Page 147
5.3 Implementation notes......Page 148
5.3.2 Implementation of parameter mechanisms......Page 149
Exercises......Page 150
Part III: Advanced Concepts......Page 152
6.1 Program units, packages, and encapsulation......Page 154
6.1.1 Packages......Page 155
6.1.2 Encapsulation......Page 156
6.2 Abstract types......Page 159
6.3 Objects and classes......Page 164
6.3.1 Classes......Page 165
6.3.2 Subclasses and inheritance......Page 170
6.3.3 Abstract classes......Page 176
6.3.4 Single vs multiple inheritance......Page 179
6.3.5 Interfaces......Page 181
6.4.1 Representation of objects......Page 183
6.4.2 Implementation of method calls......Page 184
Summary......Page 185
Exercises......Page 186
7.1 Generic units and instantiation......Page 190
7.1.1 Generic packages in ADA......Page 191
7.1.2 Generic classes in C++......Page 193
7.2.1 Type parameters in ADA......Page 195
7.2.2 Type parameters in C++......Page 199
7.2.3 Class parameters in JAVA......Page 202
7.3.1 Implementation of ADA generic units......Page 205
7.3.2 Implementation of C++ generic units......Page 206
Summary......Page 207
Exercises......Page 208
8.1.1 Types and subtypes......Page 210
8.1.2 Classes and subclasses......Page 214
8.2.1 Polymorphic procedures......Page 217
8.2.2 Parameterized types......Page 219
8.2.3 Type inference......Page 221
8.3 Overloading......Page 223
8.4 Type conversions......Page 226
8.5.1 Implementation of parametric polymorphism......Page 227
Further reading......Page 229
Exercises......Page 230
9.1 Sequencers......Page 234
9.2 Jumps......Page 235
9.3 Escapes......Page 237
9.4 Exceptions......Page 240
9.5.1 Implementation of jumps and escapes......Page 245
Summary......Page 246
Exercises......Page 247
10.1 Why concurrency?......Page 250
10.2 Programs and processes......Page 252
10.3.2 Speed dependence......Page 253
10.3.3 Deadlock......Page 255
10.3.4 Starvation......Page 256
10.4.2 Competing processes......Page 257
10.4.3 Communicating processes......Page 258
10.5 Concurrency primitives......Page 259
10.5.1 Process creation and control......Page 260
10.5.3 Spin locks and wait-free algorithms......Page 262
10.5.4 Events......Page 267
10.5.5 Semaphores......Page 268
10.5.6 Messages......Page 270
10.5.7 Remote procedure calls......Page 271
10.6.1 Conditional critical regions......Page 272
10.6.2 Monitors......Page 274
10.6.3 Rendezvous......Page 275
Further reading......Page 277
Exercises......Page 278
Part IV: Paradigms......Page 282
11.1 Key concepts......Page 284
11.2 Pragmatics......Page 285
11.2.1 A simple spellchecker......Page 287
11.3.1 Values and types......Page 288
11.3.2 Variables, storage, and control......Page 291
11.3.4 Procedural abstraction......Page 293
11.3.5 Independent compilation......Page 294
11.3.6 Preprocessor directives......Page 295
11.3.7 Function library......Page 296
11.3.8 A simple spellchecker......Page 297
11.4.1 Values and types......Page 300
11.4.3 Bindings and scope......Page 301
11.4.5 Data abstraction......Page 302
11.4.6 Generic abstraction......Page 304
11.4.7 Separate compilation......Page 307
11.4.9 A simple spellchecker......Page 308
Summary......Page 311
Exercises......Page 312
12.1 Key concepts......Page 316
12.2 Pragmatics......Page 317
12.3 Case study: C++......Page 318
12.3.3 Bindings and scope......Page 319
12.3.4 Procedural abstraction......Page 320
12.3.5 Data abstraction......Page 321
12.3.6 Generic abstraction......Page 325
12.3.8 Class and template library......Page 326
12.3.9 A simple spellchecker......Page 327
12.4 Case study: JAVA......Page 330
12.4.1 Values and types......Page 331
12.4.2 Variables, storage, and control......Page 332
12.4.4 Procedural abstraction......Page 333
12.4.5 Data abstraction......Page 334
12.4.6 Generic abstraction......Page 336
12.4.7 Separate compilation and dynamic linking......Page 337
12.4.8 Class library......Page 338
12.4.9 A simple spellchecker......Page 339
12.5.1 Types......Page 341
12.5.2 Data abstraction......Page 344
Further reading......Page 347
Exercises......Page 348
13.1 Key concepts......Page 352
13.2 Pragmatics......Page 353
13.3.1 Process creation and termination......Page 355
13.3.2 Mutual exclusion......Page 357
13.3.3 Admission control......Page 358
13.3.4 Scheduling away deadlock......Page 366
13.4 Case study: JAVA......Page 374
13.4.1 Process creation and termination......Page 375
13.4.2 Mutual exclusion......Page 377
13.4.3 Admission control......Page 378
13.5 Implementation notes......Page 380
Exercises......Page 382
14.1 Key concepts......Page 386
14.1.1 Eager vs normal-order vs lazy evaluation......Page 387
14.3.1 Values and types......Page 389
14.3.2 Bindings and scope......Page 393
14.3.3 Procedural abstraction......Page 395
14.3.4 Lazy evaluation......Page 398
14.3.5 Data abstraction......Page 400
14.3.6 Generic abstraction......Page 401
14.3.7 Modeling state......Page 403
14.3.8 A simple spellchecker......Page 405
Summary......Page 406
Further reading......Page 407
Exercises......Page 408
15.1 Key concepts......Page 412
15.3.1 Values, variables, and terms......Page 415
15.3.3 Relations......Page 417
15.3.4 The closed-world assumption......Page 421
15.3.5 Bindings and scope......Page 422
15.3.6 Control......Page 423
15.3.7 Input/output......Page 425
15.3.8 A simple spellchecker......Page 426
Summary......Page 428
Exercises......Page 429
16.1 Pragmatics......Page 432
16.2 Key concepts......Page 433
16.2.1 Regular expressions......Page 434
16.3 Case study: PYTHON......Page 436
16.3.1 Values and types......Page 437
16.3.2 Variables, storage, and control......Page 438
16.3.4 Procedural abstraction......Page 440
16.3.5 Data abstraction......Page 441
16.3.6 Separate compilation......Page 443
16.3.7 Module library......Page 444
Exercises......Page 446
Part V: Conclusion......Page 448
17.1 Criteria......Page 450
17.2 Evaluation......Page 452
Exercises......Page 455
18.1 Selection of concepts......Page 456
18.3 Simplicity......Page 457
18.4 Efficiency......Page 460
18.5 Syntax......Page 461
18.6 Language life cycles......Page 463
18.7 The future......Page 464
Further reading......Page 465
Exercises......Page 466
Bibliography......Page 468
Glossary......Page 472
Index......Page 484