Concepts, Techniques, and Models of Computer Programming

✍ Scribed by Seif Haridi, Peter Van-Roy

• Publisher: Mit Pr
• Year: 2004
• Tongue: English
• Leaves: 931
• Category: Library

✦ Synopsis

Teaching the science and the technology of programming as a unified discipline that shows the deep relationships between programming paradigms.

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

Short Contents
Table of Contents
Preface
Goals of the book
Main features
Teaching from the book
History and acknowledgments
Final comments
Running the Example Programs
Chapter 1. Introduction to Programming Concepts
1.1 A calculator
1.2 Variables
1.3 Functions
1.4 Lists
1.5 Functions over lists
1.6 Correctness
1.7 Complexity
1.8 Lazy evaluation
1.9 Higher-order programming
1.10 Concurrency
1.11 Dataflow
1.12 Explicit state
1.13 Objects
1.14 Classes
1.15 Nondeterminism and time
1.16 Atomicity
1.17 Where do we go from here?
1.18 Exercises
Part I. General Computation Models
Chapter 2. Declarative Computation Model
2.1 Defining practical programming languages
2.2 The single-assignment store
2.3 Kernel language
2.4 Kernel language semantics
2.5 Memory management
2.6 From kernel language to practical language
2.7 Exceptions
2.8 Advanced topics
2.9 Exercises
Chapter 3. Declarative Programming Techniques
3.1 What is declarativeness?
3.2 Iterative computation
3.3 Recursive computation
3.4 Programming with recursion
3.5 Time and space efficiency
3.6 Higher-order programming
3.7 Abstract data types
3.8 Nondeclarative needs
3.9 Program design in the small
3.10 Exercises
Chapter 4. Declarative Concurrency
4.1 The data-driven concurrent model
4.2 Basic thread programming techniques
4.3 Streams
4.4 Using the declarative concurrent model directly
4.5 Lazy execution
4.6 Soft real-time programming
4.7 The Haskell language
4.8 Limitations and extensions of declarative programming
4.9 Advanced topics
4.10 Historical notes
4.11 Exercises
Chapter 5. Message-Passing Concurrency
5.1 The message-passing concurrent model
5.2 Port objects
5.3 Simple message protocols
5.4 Program design for concurrency
5.5 Lift control system
5.6 Using the message-passing model directly
5.7 The Erlang language
5.8 Advanced topic
5.9 Exercises
Chapter 6. Explicit State
6.1 What is state?
6.2 State and system building
6.3 The declarative model with explicit state
6.4 Data abstraction
6.5 Stateful collections
6.6 Reasoning with state
6.7 Program design in the large
6.8 Case studies
6.9 Advanced topics
6.10 Exercises
Chapter 7. Object-Oriented Programming
7.1 Inheritance
7.2 Classes as complete data abstractions
7.3 Classes as incremental data abstractions
7.4 Programming with inheritance
7.5 Relation to other computation models
7.6 Implementing the object system
7.7 The Java language (sequential part)
7.8 Active objects
7.9 Exercises
Chapter 8. Shared-State Concurrency
8.1 The shared-state concurrent model
8.2 Programming with concurrency
8.3 Locks
8.4 Monitors
8.5 Transactions
8.6 The Java language (concurrent part)
8.7 Exercises
Chapter 9. Relational Programming
9.1 The relational computation model
9.2 Further examples
9.3 Relation to logic programming
9.4 Natural language parsing
9.5 A grammar interpreter
9.6 Databases
9.7 The Prolog language
9.8 Exercises
Part II. Specialized Computation Models
Chapter 10. Graphical User Interface Programming
10.1 The declarative/procedural approach
10.2 Using the declarative/procedural approach
10.3 The Prototyper interactive learning tool
10.4 Case studies
10.5 Implementing the GUI tool
10.6 Exercises
Chapter 11. Distributed Programming
11.1 Taxonomy of distributed systems
11.2 The distribution model
11.3 Distribution of declarative data
11.4 Distribution of state
11.5 Network awareness
11.6 Common distributed programming patterns
11.7 Distribution protocols
11.8 Partial failure
11.9 Security
11.10 Building applications
11.11 Exercises
Chapter 12. Constraint Programming
12.1 Propagate-and-search
12.2 Programming techniques
12.3 The constraint-based computation model
12.4 Defining and using computation spaces
12.5 Implementing the relational computation model
12.6 Exercises
Part III. Semantics
Chapter 13. Language Semantics
13.1 The general computation model
13.2 Declarative concurrency
13.3 Eight computation models
13.4 Semantics of common abstractions
13.5 Historical notes
13.6 Exercises
Part IV. Appendixes
A. Mozart System Development Environment
A.1 Interactive interface
A.2 Command line interface
B. Basic Data Types
B.1 Numbers (integers, floats, and characters)
B.2 Literals (atoms and names)
B.3 Records and tuples
B.4 Chunks (limited records)
B.5 Lists
B.6 Strings
B.7 Virtual strings
C. Language Syntax
C.1 Interactive statements
C.2 Statements and expressions
C.3 Nonterminals for statements and expressions
C.4 Operators
C.5 Keywords
C.6 Lexical syntax
D. General Computation Model
D.1 Creative extension principle
D.2 Kernel language
D.3 Concepts
D.4 Different forms of state
D.5 Other concepts
D.6 Layered language design
References
Index