Concepts, Techniques, and Models of Computer Programming

Textbook and Reference Work

MIT Press, hardcover, 900pp+xxix, ISBN 0-262-22069-5, March 2004

by Peter Van Roy and Seif Haridi

“More is not better (or worse) than less, just different.”
— The paradigm paradox.

“Wonderful book, very insightful, strangely easy to read (haven't figured that out yet), very unusual in many respects.”
— Doug Merritt.

“The overarching achievement of this book is to be so provocative that one wants to engage the authors in debate about almost everything they say. Partly this is due to the chirpy writing style [...] but mostly it is their delicious iconoclasm.”
— Peter Gammie, Book Review, Journal of Functional Programming, March 2009.

Errata

Supplements

News items
URLs News item
Programming paradigms poster Poster showing all major programming paradigms and their relationships.
Translations Since the end of 2007, translations of the book exist in French, Polish, and Japanese. A Spanish translation is upcoming (contact Juan Diaz).
CTM Wiki There is a Wiki devoted to discussions about the book and its approach (thanks to Dominic Fox).
Course in French There are now full course materials, a book, and software in French.
IRCAM and UPMC P. Van Roy gave talks on programming paradigms including functional, concurrent, and multiagent programming at IRCAM and UPMC in 2006, 2007, and 2008.
Active book demo A demonstration was made of an active version of chapter 4 (Declarative Concurrency) at the UPMC/ScienceActive stand of the colloquium L'Université à l'Ere du Numérique, May 22-24, 2006, Paris, France.
The Reasoned Schemer in Oz Many of the examples from The Reasoned Schemer have been translated into Oz by Chris Rathman.
FLOPS 2006 P. Van Roy gave an invited talk at FLOPS 2006 (Apr. 24-26, 2006, Fuji Sosono, Japan) on what we can learn about a definitive programming language (article, talk slides, demo code).
Colombian edition The book is available in a Colombian edition since late 2005, by the Universidad del Valle and the Pontificia Universidad Javeriana (see Tienda Javeriana store at Javeriana).
Lecture tour P. Van Roy visited and gave talks at five American universities during the week of Nov. 7-11, 2005.
Springer Web site, table of contents, order form The MOZ 2004 proceedings are now available as Springer LNCS volume 3389, with a foreword by Peter Norvig of Google, Inc.
CLEI 2005 CLEI is the major annual Latin-American computer science conference (Oct. 10-14, 2005). P. Van Roy gave a keynote talk and a tutorial on concepts-based teaching of programming.
Prentice-Hall of India There is an Eastern Economy Edition for India, Pakistan, and neighboring countries that is available since early 2005.

This textbook brings the computer science student a comprehensive and up-to-date presentation of all major programming concepts, techniques, and paradigms in a unified framework. The textbook is designed for second-year to graduate courses in computer programming. It is also designed for practitioners and researchers: it gives insightful discussions on many topics, reconciles opposing viewpoints, and emphasizes concepts of lasting value. It has the following notable features:

The book is organized around programming concepts. It starts with a small language containing just a few concepts. It shows how to design, write programs, and reason in this language. It then adds concepts one by one to overcome limitations in expressiveness. In this way, it situates all major programming paradigms in a uniform framework that is as simple as possible, but no simpler (see the table of contents). More than twenty paradigms are given, all represented as subsets of the multiparadigm language Oz. We find that all have their place: “more is not better (or worse) than less, just different”.

Here are a few highlights of the book. • • A presentation of declarative concurrency, a little-known but extremely useful paradigm for concurrent programming without race conditions. With declarative concurrency, functional building blocks such as map, forall, and fold take on new meaning as concurrency patterns. This paradigm is especially useful for multicore programming and for distributed parallel programming (e.g., MapReduce). • • An explanation of why the right default for structuring programs is as concurrent components that communicate through asynchronous message passing. • • A mixed declarative/imperative approach to graphical user interface design that is well-suited to context-sensitive and plastic user interfaces. • • A lift control system using multi-agent programming. • • A transaction system using optimistic concurrency control with strict two-phase locking and deadlock avoidance. • • A deep discussion of the uses and limits of declarative programming. • • A survey of programming techniques using lazy evaluation. • • An efficient approach to network-transparent distributed programming. • • An introduction to constraint programming.

What other people say

Endorsements

Book review by Scott Johnson on the original WikiWikiWeb hosted by Cunningham & Cunningham, Inc.

Book review by Yves Deville et al in Theory and Practice of Logic Programming, Cambridge University Press, vol. 5, issue 4-5, pp. 595-600, July 2005.

Book review by Edgar R. Chavez in ACM Computing Reviews, July 18, 2006 (requires ACM account).

Book review by Ranjit Mathew, Jan. 21, 2007.

Book review by Peter Gammie in Journal of Functional Programming, Cambridge University Press, vol. 19, issue 2, pp. 254-256, March 2009.

Ask Google about popular programming textbooks and see where we stand: ask the oracle

Ask Google Image Search about programming paradigms and see where we stand: ask the oracle

The TUNES Project recommends the book in its PL 101 Learning Lounge course on Programming Languages.

Some comments that appeared on blogs, newsgroups, and other public forums, regarding the book and online drafts from 2003. • • “Just finished reading it and I feel like I have read the Bible.” (Slashdot article, June 18, 2003) • • “In many ways [book title] feels like an (overdue) update of 'Structure and Interpretation of Computer Programs'.” • • “The Rosetta Stone of software.” • • “One of the best CS books that I have ever read.” • • “One of the rare books you can really learn programming science from.” • • “A book of great wisdom.” • • “It seems just about every page of the book introduces some new concept requiring contemplation and digestion.” • • “If you doubt that any language could possibly merge all these paradigms and still be useful, look at the draft of the upcoming book [book title] where the underlying ideas are clearly spelled out.” • • “I'd recommend this book to anyone thinking about programming.” • • “Van Roy and Haridi might be the first good text on programming languages.” • • “In short, this is a Masters in Computer Science in one language and text.”

Free course material, talks, and articles

Talks

Articles

Other links

Open source software support

The book is designed to be accompanied by version 1.3.0 of the Mozart Programming System (released on April 15, 2004) and all later versions. Mozart is a production-quality development platform that can run all code fragments in the book. The Supplements Web site gives the code supplements to Mozart that are used by the book. Mozart is available without charge under an Open Source license. It exists for various flavors of Unix and Windows and for Mac OS X. Mozart is actively developed and maintained by the Mozart community (version 1.4.0 was released on July 3, 2008).

We chose Mozart for the textbook because it implements Oz, a multiparadigm language that supports the concepts-based approach perfectly well. Oz combines in a natural way many concepts traditionally associated with different programming paradigms. This makes Oz difficult to classify: it is a functional language, a logic language, an object-oriented language, a dataflow language, a constraint language, and much more. Using a single language instead of several (e.g., Java, Prolog, Haskell, and Erlang) makes it easier to show the deep relationships between the paradigms as well as reducing the administrative burden for student and teacher (only one system needs to be installed and learned instead of many).

Teaching with the book

There are several sets of course material available free (more than 2000 lecture slides, also tutorials, lab sessions, and exams) on the Supplements Web site. You can use and modify this material freely for your own courses. The CTM in Alice site has translations of many of the book's example programs into the statically typed language Alice. The TRS in other languages site has translations of many of the examples from The Reasoned Schemer into Oz.

The book has been available since March 2004, but drafts have been used before that for teaching. What follows in this section is a list of some institutions that use the book and their courses. If you are teaching a course with the book or thinking of teaching one, we would appreciate hearing from you.

Complete courses

Some courses that use the book as primary text (unfortunately, this list is more and more out of date, please send me mail if you want to be mentioned here):

Partial courses

Some courses that use the book for a significant part of their course material:

The concepts-based approach for teaching programming

Scientific foundation

The book's scientific foundation is the kernel language approach. In this approach, practical programming languages are defined by translating them to kernel languages that consist of a small number of programmer-significant concepts. A wide variety of programming languages and paradigms can be defined as subsets of a general kernel language. The general language is easy to understand by practicing programmers and has a simple formal semantics that allows programmers to reason about correctness and complexity at a high level of abstraction. The simplicity of the semantics means that the language's behavior is easily predicted. Even if programmers do not use the semantics directly, its mere existence ensures that there are no unpleasant surprises. The semantics supports whatever degree of formality best suits the problem: from the most rigorous formal methods to the most intuitive craftsmanship.

The two approaches most similar to the kernel language approach are the foundational calculus and the virtual machine. We explain how the kernel language approach differs from these approaches. A foundational calculus, like the lambda-calculus or pi-calculus, reduces programming to a minimal number of primitive concepts. This is especially useful for the theoretical study of computation. A virtual machine defines a language in terms of an implementation on an idealized machine. This is especially useful for language implementors and compiler writers. The problem with both approaches is that any realistic program written in them will be cluttered with technical details about language mechanisms. The kernel language approach avoids this clutter by choosing concepts wisely. The kernel languages are designed for programmers.

How concepts lead to multiparadigm programming

We define the precise concept of computation model to capture the intuitive concept of “programming paradigm”. Each kernel language is the basis of a computation model. The book introduces more than twenty computation models in a uniform framework and in a progressive way. Programming paradigms appear as a kind of epiphenomenon, depending on which concepts one uses. We examine the relationships between the models and show how and why to use different models together in the same program. This leads to multiparadigm programming in a completely natural way. Often models that seem vastly different have kernel languages that differ only in one concept (e.g., this is the case for declarative versus object-oriented programming).

General models covered include declarative programming (functional and logic), imperative programming (component-based and object-oriented), and concurrent programming (both synchronous and asynchronous, including dataflow, streams, lazy execution, message passing, and shared state). Specialized models covered include graphical user interface programming, distributed programming, and constraint programming. All models are fully implemented for practical programming and incorporate many of the latest research ideas.

The current trend in computer science education is to restrict the student to one or two models. The most extreme case is where a single rather complex model and language, namely object-oriented programming in Java, is used as a general-purpose approach with which all problems should be solved. This trend is driven by market forces and has no scientific basis. One goal of the book is to be a counterweight to this trend, to situate object-oriented programming in a more general context. In addition to giving the student a deep insight, this has immediate practical benefits. Many problems that are hard to solve in Java become simple when viewed in the proper computation model. For example, both concurrent programming and graphical user interface design are difficult in Java. The book shows how these two areas can be much simplified.

History

The Mozart Board

The Mozart system is being actively developed by the Mozart community, with the guidance and responsibility of a core group, the Mozart Board. The Mozart Programming System was originally developed by Gert Smolka and his research group at Saarland University in the early 1990s. At that time it was called DFKI Oz. In 1999, development continued with an international group, the Mozart Consortium, that consisted of Saarland University, the Swedish Institute of Computer Science, and the Université catholique de Louvain. In 2005, the responsibility for managing Mozart development was transferred to the Mozart Board, with the express purpose of opening Mozart development to a larger community.

The authors

The authors have been collaborating closely since 1995. They started writing the textbook in 1999. Both have extensive experience in different areas of computer science including hardware and software systems, programming language design and implementation, parallel and distributed systems, simulation, logic and constraint programming, and application development.

Peter Van Roy is professor in the Department of Computing Science and Engineering at the Université catholique de Louvain (UCL) in Louvain-la-Neuve, Belgium (research page). The Grand Challenge in Programming Languages, ALP Newsletter, Volume 8/4, 1995 (archive, local copy).

As Darth Vader in combat with two young Jedi knights.

As Peter Pan teaching the course INGI1131.

Seif Haridi is professor in the Department of Microelectronics and Information Technology at the Royal Institute of Technology (KTH) and chief scientific advisor of the Swedish Institute of Computer Science (SICS), both near Stockholm, Sweden.