Concepts, Techniques, and Models of Computer Programming

by Peter Van Roy and Seif Haridi

ISBN: 9780262332590 | Copyright 2004

Click here to preview

Tabs

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.

This book follows in the fine tradition of Abelson/Sussman and Kamin's book on interpreters, but goes well beyond them, covering functional and Smalltalk-like languages as well as more advanced concepts in concurrent programming, distributed programming, and some of the finer points of C++ and Java.

Peter Norvig Google Inc.

In almost 20 years since Abelson and Sussman revolutionized the teaching of computer science with their Structure and Interpretation of Computer Programs, this is the first book I've seen that focuses on big ideas and multiple paradigms, as SICP does, but chooses a very different core model (declarative programming). I wouldn't have made all the choices Van Roy and Haridi have made, but I learned a lot from reading this book, and I hope it gets a wide audience.

Brian Harvey Lecturer, Computer Science Division, University of California, Berkeley
Expand/Collapse All
Short Contents (pg. v)
Table of Contents (pg. vii)
Preface (pg. xiii)
Goals of the book (pg. xv)
Main features (pg. xviii)
Teaching from the book (pg. xxi)
History and acknowledgments (pg. xxiv)
Final comments (pg. xxvi)
Running the Example Programs (pg. xxix)
Chapter 1. Introduction to Programming Concepts (pg. 1)
1.1 A calculator (pg. 1)
1.2 Variables (pg. 2)
1.3 Functions (pg. 2)
1.4 Lists (pg. 4)
1.5 Functions over lists (pg. 7)
1.6 Correctness (pg. 9)
1.7 Complexity (pg. 10)
1.8 Lazy evaluation (pg. 11)
1.9 Higher-order programming (pg. 13)
1.10 Concurrency (pg. 14)
1.11 Dataflow (pg. 15)
1.12 Explicit state (pg. 16)
1.13 Objects (pg. 17)
1.14 Classes (pg. 18)
1.15 Nondeterminism and time (pg. 20)
1.16 Atomicity (pg. 21)
1.17 Where do we go from here? (pg. 22)
1.18 Exercises (pg. 23)
Part I. General Computation Models (pg. 27)
Chapter 2. Declarative Computation Model (pg. 29)
2.1 Defining practical programming languages (pg. 30)
2.2 The single-assignment store (pg. 42)
2.3 Kernel language (pg. 49)
2.4 Kernel language semantics (pg. 56)
2.5 Memory management (pg. 72)
2.6 From kernel language to practical language (pg. 79)
2.7 Exceptions (pg. 90)
2.8 Advanced topics (pg. 96)
2.9 Exercises (pg. 107)
Chapter 3. Declarative Programming Techniques (pg. 111)
3.1 What is declarativeness? (pg. 114)
3.2 Iterative computation (pg. 118)
3.3 Recursive computation (pg. 124)
3.4 Programming with recursion (pg. 127)
3.5 Time and space efficiency (pg. 166)
3.6 Higher-order programming (pg. 177)
3.7 Abstract data types (pg. 195)
3.8 Nondeclarative needs (pg. 210)
3.9 Program design in the small (pg. 218)
3.10 Exercises (pg. 230)
Chapter 4. Declarative Concurrency (pg. 233)
4.1 The data-driven concurrent model (pg. 235)
4.2 Basic thread programming techniques (pg. 246)
4.3 Streams (pg. 256)
4.4 Using the declarative concurrent model directly (pg. 272)
4.5 Lazy execution (pg. 278)
4.6 Soft real-time programming (pg. 304)
4.7 The Haskell language (pg. 308)
4.8 Limitations and extensions of declarative programming (pg. 313)
4.9 Advanced topics (pg. 326)
4.10 Historical notes (pg. 337)
4.11 Exercises (pg. 338)
Chapter 5. Message-Passing Concurrency (pg. 345)
5.1 The message-passing concurrent model (pg. 347)
5.2 Port objects (pg. 350)
5.3 Simple message protocols (pg. 353)
5.4 Program design for concurrency (pg. 362)
5.5 Lift control system (pg. 365)
5.6 Using the message-passing model directly (pg. 377)
5.7 The Erlang language (pg. 386)
5.8 Advanced topic (pg. 394)
5.9 Exercises (pg. 399)
Chapter 6. Explicit State (pg. 405)
6.1 What is state? (pg. 408)
6.2 State and system building (pg. 410)
6.3 The declarative model with explicit state (pg. 413)
6.4 Data abstraction (pg. 419)
6.5 Stateful collections (pg. 435)
6.6 Reasoning with state (pg. 440)
6.7 Program design in the large (pg. 450)
6.8 Case studies (pg. 463)
6.9 Advanced topics (pg. 479)
6.10 Exercises (pg. 482)
Chapter 7. Object-Oriented Programming (pg. 489)
7.1 Inheritance (pg. 491)
7.2 Classes as complete data abstractions (pg. 492)
7.3 Classes as incremental data abstractions (pg. 502)
7.4 Programming with inheritance (pg. 518)
7.5 Relation to other computation models (pg. 537)
7.6 Implementing the object system (pg. 545)
7.7 The Java language (sequential part) (pg. 551)
7.8 Active objects (pg. 556)
7.9 Exercises (pg. 567)
Chapter 8. Shared-State Concurrency (pg. 569)
8.1 The shared-state concurrent model (pg. 573)
8.2 Programming with concurrency (pg. 573)
8.3 Locks (pg. 582)
8.4 Monitors (pg. 592)
8.5 Transactions (pg. 600)
8.6 The Java language (concurrent part) (pg. 615)
8.7 Exercises (pg. 618)
Chapter 9. Relational Programming (pg. 621)
9.1 The relational computation model (pg. 623)
9.2 Further examples (pg. 627)
9.3 Relation to logic programming (pg. 631)
9.4 Natural language parsing (pg. 641)
9.5 A grammar interpreter (pg. 650)
9.6 Databases (pg. 654)
9.7 The Prolog language (pg. 660)
9.8 Exercises (pg. 671)
Part II. Specialized Computation Models (pg. 677)
Chapter 10. Graphical User Interface Programming (pg. 679)
10.1 The declarative/procedural approach (pg. 681)
10.2 Using the declarative/procedural approach (pg. 682)
10.3 The Prototyper interactive learning tool (pg. 689)
10.4 Case studies (pg. 690)
10.5 Implementing the GUI tool (pg. 703)
10.6 Exercises (pg. 703)
Chapter 11. Distributed Programming (pg. 707)
11.1 Taxonomy of distributed systems (pg. 710)
11.2 The distribution model (pg. 712)
11.3 Distribution of declarative data (pg. 714)
11.4 Distribution of state (pg. 720)
11.5 Network awareness (pg. 723)
11.6 Common distributed programming patterns (pg. 724)
11.7 Distribution protocols (pg. 732)
11.8 Partial failure (pg. 739)
11.9 Security (pg. 743)
11.10 Building applications (pg. 745)
11.11 Exercises (pg. 746)
Chapter 12. Constraint Programming (pg. 749)
12.1 Propagate-and-search (pg. 750)
12.2 Programming techniques (pg. 755)
12.3 The constraint-based computation model (pg. 758)
12.4 Defining and using computation spaces (pg. 762)
12.5 Implementing the relational computation model (pg. 772)
12.6 Exercises (pg. 774)
Part III. Semantics (pg. 777)
Chapter 13. Language Semantics (pg. 779)
13.1 The general computation model (pg. 780)
13.2 Declarative concurrency (pg. 804)
13.3 Eight computation models (pg. 806)
13.4 Semantics of common abstractions (pg. 808)
13.5 Historical notes (pg. 808)
13.6 Exercises (pg. 809)
Part IV. Appendixes (pg. 813)
A. Mozart System Development Environment (pg. 815)
A.1 Interactive interface (pg. 815)
A.2 Command line interface (pg. 817)
B. Basic Data Types (pg. 819)
B.1 Numbers (integers, floats, and characters) (pg. 819)
B.2 Literals (atoms and names) (pg. 824)
B.3 Records and tuples (pg. 825)
B.4 Chunks (limited records) (pg. 828)
B.5 Lists (pg. 828)
B.6 Strings (pg. 830)
B.7 Virtual strings (pg. 831)
C. Language Syntax (pg. 833)
C.1 Interactive statements (pg. 834)
C.2 Statements and expressions (pg. 834)
C.3 Nonterminals for statements and expressions (pg. 836)
C.4 Operators (pg. 836)
C.5 Keywords (pg. 839)
C.6 Lexical syntax (pg. 839)
D. General Computation Model (pg. 843)
D.1 Creative extension principle (pg. 844)
D.2 Kernel language (pg. 845)
D.3 Concepts (pg. 846)
D.4 Different forms of state (pg. 849)
D.5 Other concepts (pg. 850)
D.6 Layered language design (pg. 850)
References (pg. 853)
Index (pg. 863)

Peter Van Roy

Peter Van Roy is Professor in the Department of Computing Science and Engineering at Université catholique de Louvain, at Louvain-la-Neuve, Belgium.


Seif Haridi

Seif Haridi is Professor of Computer Systems in the Department of Microelectronics and Information Technology at the Royal Institute of Technology, Sweden, and Chief Scientific Advisor of the Swedish Institute of Computer Science.


eTextbook
Go paperless today! Available online anytime, nothing to download or install.
Device Compatibility

Features

  • Bookmarking
  • Note taking
  • Highlighting
Support