Concepts, techniques, and models of computer programming

Peter Van Roy, Seif Haridi9780262220699, 0262220695

This innovative text presents computer programming as a unified discipline in a way that is both practical and scientifically sound. The book focuses on techniques of lasting value and explains them precisely in terms of a simple abstract machine. The book presents all major programming paradigms in a uniform framework that shows their deep relationships and how and where to use them together. After an introduction to programming concepts, the book presents both well-known and lesser-known computation models (“programming paradigms”). Each model has its own set of techniques and each is included on the basis of its usefulness in practice. The general models include declarative programming, declarative concurrency, message-passing concurrency, explicit state, object-oriented programming, shared-state concurrency, and relational programming. Specialized models include graphical user interface programming, distributed programming, and constraint programming. Each model is based on its kernel language–a simple core language that consists of a small number of programmer- significant elements. The kernel languages are introduced progressively, adding concepts one by one, thus showing the deep relationships between different models. The kernel languages are defined precisely in terms of a simple abstract machine. Because a wide variety of languages and programming paradigms can be modeled by a small set of closely related kernel languages, this approach allows programmer and student to grasp the underlying unity of programming. The book has many program fragments and exercises, all of which can be run on the Mozart Programming System, an Open Source software package that features an interactive incremental development environment.

---

Table of contents :
Team DDU……Page 1
Table of Contents……Page 8
Preface……Page 14
Running the Example Programs……Page 30
1.1 A calculator……Page 32
1.3 Functions……Page 33
1.4 Lists……Page 35
1.5 Functions over lists……Page 38
1.6 Correctness……Page 40
1.7 Complexity……Page 41
1.8 Lazy evaluation……Page 42
1.9 Higher-order programming……Page 44
1.10 Concurrency……Page 45
1.11 Data.ow……Page 46
1.12 Explicit state……Page 47
1.13 Objects……Page 48
1.14 Classes……Page 49
1.15 Nondeterminismand time……Page 51
1.16 Atomicity……Page 52
1.17 Where do we go from here?……Page 53
1.18 Exercises……Page 54
I GENERAL COMPUTATION MODELS……Page 58
2 Declarative Computation Model……Page 60
2.1 De.ning practical programming languages……Page 61
2.2 The single-assignment store……Page 73
2.3 Kernel language……Page 80
2.4 Kernel language semantics……Page 87
2.5 Memorymanagement……Page 103
2.6 From kernel language to practical language……Page 110
2.7 Exceptions……Page 121
2.8 Advanced topics……Page 127
2.9 Exercises……Page 138
3 Declarative Programming Techniques……Page 142
3.1 What is declarativeness?……Page 145
3.2 Iterative computation……Page 149
3.3 Recursive computation……Page 155
3.4 Programmingwith recursion……Page 158
3.5 Time and space e.ciency……Page 197
3.6 Higher-order programming……Page 208
3.7 Abstract data types……Page 226
3.8 Nondeclarative needs……Page 241
3.9 Program design in the small……Page 249
3.10 Exercises……Page 261
4 Declarative Concurrency……Page 264
4.1 The data-driven concurrentmodel……Page 266
4.2 Basic thread programming techniques……Page 277
4.3 Streams……Page 287
4.4 Using the declarative concurrent model directly……Page 303
4.5 Lazy execution……Page 309
4.6 Soft real-time programming……Page 335
4.7 The Haskell language……Page 339
4.8 Limitations and extensions of declarative programming……Page 344
4.9 Advanced topics……Page 357
4.10 Historical notes……Page 368
4.11 Exercises……Page 369
5 Message-Passing Concurrency……Page 376
5.1 The message-passing concurrent model……Page 378
5.2 Port objects……Page 381
5.3 Simple message protocols……Page 384
5.4 Program design for concurrency……Page 393
5.5 Lift control system……Page 396
5.6 Using the message-passing model directly……Page 408
5.7 The Erlang language……Page 417
5.8 Advanced topic……Page 425
5.9 Exercises……Page 430
6 Explicit State……Page 436
6.1 What is state?……Page 439
6.2 State and systembuilding……Page 441
6.3 The declarative model with explicit state……Page 444
6.4 Data abstraction……Page 450
6.5 Stateful collections……Page 466
6.6 Reasoning with state……Page 471
6.7 Program design in the large……Page 481
6.8 Case studies……Page 494
6.9 Advanced topics……Page 510
6.10 Exercises……Page 513
7 Object-Oriented Programming……Page 520
7.1 Inheritance……Page 522
7.2 Classes as complete data abstractions……Page 523
7.3 Classes as incremental data abstractions……Page 533
7.4 Programming with inheritance……Page 549
7.5 Relation to other computation models……Page 568
7.6 Implementing the object system……Page 576
7.7 The Java language (sequential part)……Page 582
7.8 Active objects……Page 587
7.9 Exercises……Page 598
8 Shared-State Concurrency……Page 600
8.2 Programming with concurrency……Page 604
8.3 Locks……Page 613
8.4 Monitors……Page 623
8.5 Transactions……Page 631
8.6 The Java language (concurrent part)……Page 646
8.7 Exercises……Page 649
9 Relational Programming……Page 652
9.1 The relational computation model……Page 654
9.2 Further examples……Page 658
9.3 Relation to logic programming……Page 662
9.4 Natural language parsing……Page 672
9.5 A grammar interpreter……Page 681
9.6 Databases……Page 685
9.7 The Prolog language……Page 691
9.8 Exercises……Page 702
II SPECIALIZED COMPUTATION MODELS……Page 708
10 Graphical User Interface Programming……Page 710
10.1 The declarative/procedural approach……Page 712
10.2 Using the declarative/procedural approach……Page 713
10.3 The Prototyper interactive learning tool……Page 720
10.4 Case studies……Page 721
10.6 Exercises……Page 734
11 Distributed Programming……Page 738
11.1 Taxonomy of distributed systems……Page 741
11.2 The distribution model……Page 743
11.3 Distribution of declarative data……Page 745
11.4 Distribution of state……Page 751
11.5 Network awareness……Page 754
11.6 Common distributed programming patterns……Page 755
11.7 Distribution protocols……Page 763
11.8 Partial failure……Page 770
11.9 Security……Page 774
11.10 Building applications……Page 776
11.11 Exercises……Page 777
12 Constraint Programming……Page 780
12.1 Propagate-and-search……Page 781
12.2 Programming techniques……Page 786
12.3 The constraint-based computation model……Page 789
12.4 De.ning and using computation spaces……Page 793
12.5 Implementing the relational computation model……Page 803
12.6 Exercises……Page 805
III SEMANTICS……Page 808
13 Language Semantics……Page 810
13.1 The general computation model……Page 811
13.2 Declarative concurrency……Page 835
13.3 Eight computation models……Page 837
13.5 Historical notes……Page 839
13.6 Exercises……Page 840
IV APPENDIXES……Page 844
A.1 Interactive interface……Page 846
A.2 Command line interface……Page 848
B.1 Numbers (integers, oats, and characters)……Page 850
B.2 Literals (atoms and names)……Page 855
B.3 Records and tuples……Page 856
B.5 Lists……Page 859
B.6 Strings……Page 861
B.7 Virtual strings……Page 862
C Language Syntax……Page 864
C.2 Statements and expressions……Page 865
C.4 Operators……Page 867
C.6 Lexical syntax……Page 870
D General Computation Model……Page 874
D.1 Creative extension principle……Page 875
D.2 Kernel language……Page 876
D.3 Concepts……Page 877
D.4 Di.erent forms of state……Page 880
D.6 Layered language design……Page 881
References……Page 884
Index……Page 894