Team DDU......Page 1
Table of Contents......Page 7
Preface......Page 13
Running the Example Programs......Page 29
1.1 A calculator......Page 31
1.3 Functions......Page 32
1.4 Lists......Page 34
1.5 Functions over lists......Page 37
1.6 Correctness......Page 39
1.7 Complexity......Page 40
1.8 Lazy evaluation......Page 41
1.9 Higher-order programming......Page 43
1.10 Concurrency......Page 44
1.11 Data.ow......Page 45
1.12 Explicit state......Page 46
1.13 Objects......Page 47
1.14 Classes......Page 48
1.15 Nondeterminismand time......Page 50
1.16 Atomicity......Page 51
1.17 Where do we go from here?......Page 52
1.18 Exercises......Page 53
I GENERAL COMPUTATION MODELS......Page 57
2 Declarative Computation Model......Page 59
2.1 De.ning practical programming languages......Page 60
2.2 The single-assignment store......Page 72
2.3 Kernel language......Page 79
2.4 Kernel language semantics......Page 86
2.5 Memorymanagement......Page 102
2.6 From kernel language to practical language......Page 109
2.7 Exceptions......Page 120
2.8 Advanced topics......Page 126
2.9 Exercises......Page 137
3 Declarative Programming Techniques......Page 141
3.1 What is declarativeness?......Page 144
3.2 Iterative computation......Page 148
3.3 Recursive computation......Page 154
3.4 Programmingwith recursion......Page 157
3.5 Time and space e.ciency......Page 196
3.6 Higher-order programming......Page 207
3.7 Abstract data types......Page 225
3.8 Nondeclarative needs......Page 240
3.9 Program design in the small......Page 248
3.10 Exercises......Page 260
4 Declarative Concurrency......Page 263
4.1 The data-driven concurrentmodel......Page 265
4.2 Basic thread programming techniques......Page 276
4.3 Streams......Page 286
4.4 Using the declarative concurrent model directly......Page 302
4.5 Lazy execution......Page 308
4.6 Soft real-time programming......Page 334
4.7 The Haskell language......Page 338
4.8 Limitations and extensions of declarative programming......Page 343
4.9 Advanced topics......Page 356
4.10 Historical notes......Page 367
4.11 Exercises......Page 368
5 Message-Passing Concurrency......Page 375
5.1 The message-passing concurrent model......Page 377
5.2 Port objects......Page 380
5.3 Simple message protocols......Page 383
5.4 Program design for concurrency......Page 392
5.5 Lift control system......Page 395
5.6 Using the message-passing model directly......Page 407
5.7 The Erlang language......Page 416
5.8 Advanced topic......Page 424
5.9 Exercises......Page 429
6 Explicit State......Page 435
6.1 What is state?......Page 438
6.2 State and systembuilding......Page 440
6.3 The declarative model with explicit state......Page 443
6.4 Data abstraction......Page 449
6.5 Stateful collections......Page 465
6.6 Reasoning with state......Page 470
6.7 Program design in the large......Page 480
6.8 Case studies......Page 493
6.9 Advanced topics......Page 509
6.10 Exercises......Page 512
7 Object-Oriented Programming......Page 519
7.1 Inheritance......Page 521
7.2 Classes as complete data abstractions......Page 522
7.3 Classes as incremental data abstractions......Page 532
7.4 Programming with inheritance......Page 548
7.5 Relation to other computation models......Page 567
7.6 Implementing the object system......Page 575
7.7 The Java language (sequential part)......Page 581
7.8 Active objects......Page 586
7.9 Exercises......Page 597
8 Shared-State Concurrency......Page 599
8.2 Programming with concurrency......Page 603
8.3 Locks......Page 612
8.4 Monitors......Page 622
8.5 Transactions......Page 630
8.6 The Java language (concurrent part)......Page 645
8.7 Exercises......Page 648
9 Relational Programming......Page 651
9.1 The relational computation model......Page 653
9.2 Further examples......Page 657
9.3 Relation to logic programming......Page 661
9.4 Natural language parsing......Page 671
9.5 A grammar interpreter......Page 680
9.6 Databases......Page 684
9.7 The Prolog language......Page 690
9.8 Exercises......Page 701
II SPECIALIZED COMPUTATION MODELS......Page 707
10 Graphical User Interface Programming......Page 709
10.1 The declarative/procedural approach......Page 711
10.2 Using the declarative/procedural approach......Page 712
10.3 The Prototyper interactive learning tool......Page 719
10.4 Case studies......Page 720
10.6 Exercises......Page 733
11 Distributed Programming......Page 737
11.1 Taxonomy of distributed systems......Page 740
11.2 The distribution model......Page 742
11.3 Distribution of declarative data......Page 744
11.4 Distribution of state......Page 750
11.5 Network awareness......Page 753
11.6 Common distributed programming patterns......Page 754
11.7 Distribution protocols......Page 762
11.8 Partial failure......Page 769
11.9 Security......Page 773
11.10 Building applications......Page 775
11.11 Exercises......Page 776
12 Constraint Programming......Page 779
12.1 Propagate-and-search......Page 780
12.2 Programming techniques......Page 785
12.3 The constraint-based computation model......Page 788
12.4 De.ning and using computation spaces......Page 792
12.5 Implementing the relational computation model......Page 802
12.6 Exercises......Page 804
III SEMANTICS......Page 807
13 Language Semantics......Page 809
13.1 The general computation model......Page 810
13.2 Declarative concurrency......Page 834
13.3 Eight computation models......Page 836
13.5 Historical notes......Page 838
13.6 Exercises......Page 839
IV APPENDIXES......Page 843
A.1 Interactive interface......Page 845
A.2 Command line interface......Page 847
B.1 Numbers (integers, oats, and characters)......Page 849
B.2 Literals (atoms and names)......Page 854
B.3 Records and tuples......Page 855
B.5 Lists......Page 858
B.6 Strings......Page 860
B.7 Virtual strings......Page 861
C Language Syntax......Page 863
C.2 Statements and expressions......Page 864
C.4 Operators......Page 866
C.6 Lexical syntax......Page 869
D General Computation Model......Page 873
D.1 Creative extension principle......Page 874
D.2 Kernel language......Page 875
D.3 Concepts......Page 876
D.4 Di.erent forms of state......Page 879
D.6 Layered language design......Page 880
References......Page 883
Index......Page 893