Concepts, Techniques, and Models of Computer Programming

by Van Roy, Peter; Haridi, Seif

• ISBN13: 9780262220699
• ISBN10: 0262220695
• Format: Hardcover
• Copyright: 2004-02-20
• Publisher: The MIT Press

Summary

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.

Author Biography

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 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.

Table of Contents

Preface	xiii
Running the Example Programs	xxix
Introduction to Programming Concepts	1	(26)
A calculator	1	(1)
Variables	2	(1)
Functions	2	(2)
Lists	4	(3)
Functions over lists	7	(2)
Correctness	9	(1)
Complexity	10	(1)
Lazy evaluation	11	(2)
Higher-order programming	13	(1)
Concurrency	14	(1)
Dataflow	15	(1)
Explicit state	16	(1)
Objects	17	(1)
Classes	18	(2)
Nondeterminism and time	20	(1)
Atomicity	21	(1)
Where do we go from here?	22	(1)
Exercises	23	(4)
I GENERAL COMPUTATION MODELS	27	(650)
Declarative Computation Model	29	(82)
Defining practical programming languages	30	(12)
The single-assignment store	42	(7)
Kernel language	49	(7)
Kernel language semantics	56	(16)
Memory management	72	(7)
From kernel language to practical language	79	(11)
Exceptions	90	(6)
Advanced topics	96	(11)
Exercises	107	(4)
Declarative Programming Techniques	111	(122)
What is declarativeness?	114	(4)
Iterative computation	118	(6)
Recursive computation	124	(3)
Programming with recursion	127	(39)
Time and space efficiency	166	(11)
Higher-order programming	177	(18)
Abstract data types	195	(15)
Nondeclarative needs	210	(8)
Program design in the small	218	(12)
Exercises	230	(3)
Declarative Concurrency	233	(112)
The data-driven concurrent model	235	(11)
Basic thread programming techniques	246	(10)
Streams	256	(16)
Using the declarative concurrent model directly	272	(6)
Lazy execution	278	(26)
Soft real-time programming	304	(4)
The Haskell language	308	(5)
Limitations and extensions of declarative programming	313	(13)
Advanced topics	326	(11)
Historical notes	337	(1)
Exercises	338	(7)
Message-Passing Concurrency	345	(60)
The message-passing concurrent model	347	(3)
Port objects	350	(3)
Simple message protocols	353	(9)
Program design for concurrency	362	(3)
Lift control system	365	(12)
Using the message-passing model directly	377	(9)
The Erlang language	386	(8)
Advanced topic	394	(5)
Exercises	399	(6)
Explicit State	405	(84)
What is state?	408	(2)
State and system building	410	(3)
The declarative model with explicit state	413	(6)
Data abstraction	419	(16)
Stateful collections	435	(5)
Reasoning with state	440	(10)
Program design in the large	450	(13)
Case studies	463	(16)
Advanced topics	479	(3)
Exercises	482	(7)
Object-Oriented Programming	489	(80)
Inheritance	491	(1)
Classes as complete data abstractions	492	(10)
Classes as incremental data abstractions	502	(16)
Programming with inheritance	518	(19)
Relation to other computation models	537	(8)
Implementing the object system	545	(6)
The Java language (sequential part)	551	(5)
Active objects	556	(11)
Exercises	567	(2)
Shared-State Concurrency	569	(52)
The shared-state concurrent model	573	(1)
Programming with concurrency	573	(9)
Locks	582	(10)
Monitors	592	(8)
Transactions	600	(15)
The Java language (concurrent part)	615	(3)
Exercises	618	(3)
Relational Programming	621	(56)
The relational computation model	623	(4)
Further examples	627	(4)
Relation to logic programming	631	(10)
Natural language parsing	641	(9)
A grammar interpreter	650	(4)
Databases	654	(6)
The Prolog language	660	(11)
Exercises	671	(6)
II SPECIALIZED COMPUTATION MODELS	677	(100)
Graphical User Interface Programming	679	(28)
The declarative / procedural approach	681	(1)
Using the declarative / procedural approach	682	(7)
The Prototyper interactive learning tool	689	(1)
Case studies	690	(13)
Implementing the GUI tool	703	(1)
Exercises	703	(4)
Distributed Programming	707	(42)
Taxonomy of distributed systems	710	(2)
The distribution model	712	(2)
Distribution of declarative data	714	(6)
Distribution of state	720	(3)
Network awareness	723	(1)
Common distributed programming patterns	724	(8)
Distribution protocols	732	(7)
Partial failure	739	(4)
Security	743	(2)
Building applications	745	(1)
Exercises	746	(3)
Constraint Programming	749	(28)
Propagate-and-search	750	(5)
Programming techniques	755	(3)
The constraint-based computation model	758	(4)
Defining and using computation spaces	762	(10)
Implementing the relational computation model	772	(2)
Exercises	774	(3)
III SEMANTICS	777	(36)
Language Semantics	779	(34)
The general computation model	780	(24)
Declarative concurrency	804	(2)
Eight computation models	806	(2)
Semantics of common abstractions	808	(1)
Historical notes	808	(1)
Exercises	809	(4)
IV APPENDIXES	813	(40)
A Mozart System Development Environment	815	(4)
A.1 Interactive interface	815	(2)
A.2 Command line interface	817	(2)
B Basic Data Types	819	(14)
B.1 Numbers (integers, floats, and characters)	819	(5)
B.2 Literals (atoms and names)	824	(1)
B.3 Records and tuples	825	(3)
B.4 Chunks (limited records)	828	(1)
B.5 Lists	828	(2)
B.6 Strings	830	(1)
B.7 Virtual strings	831	(2)
C Language Syntax	833	(10)
C.1 Interactive statements	834	(1)
C.2 Statements and expressions	834	(2)
C.3 Nonterminals for statements and expressions	836	(1)
C.4 Operators	836	(3)
C.5 Keywords	839	(1)
C.6 Lexical syntax	839	(4)
D General Computation Model	843	(10)
D.1 Creative extension principle	844	(1)
D.2 Kernel language	845	(1)
D.3 Concepts	846	(3)
D.4 Different forms of state	849	(1)
D.5 Other concepts	850	(1)
D.6 Layered language design	850	(3)
References	853	(10)
Index	863