Supplements for "Concepts, Techniques, and Models of Computer Programming"

This Web site supplements the book's official site with course material for four general-purpose second and third-year courses on programming concepts: Our experience shows that the second year is a good time to give a course based on programming concepts. In the first year, students lack the maturity to understand the concepts and in the third and fourth years, students tend to become conservative. In the second year, students are mature enough to understand the concepts and open enough to appreciate them.

Here are some specialized courses:

This Web site also contains errata for the book, a poster showing the principal programming paradigms, a pointer to a Wiki devoted to the book, an animated kernel language interpreter, some example code, and other technical information. For more general information on the book please go to the main Web site. We would like to ask anyone who makes new material or improves this material, to please contact the authors so that we can add your material to this Web site.

Errata

Here is a list of errata for the book.

Poster showing the principal programming paradigms

Here is a poster that shows the principal programming paradigms and their relationships (programming paradigms poster in JPEG). The poster is inspired by the book.

Wiki for the book

There is a Wiki for the book with extra information contributed by readers, including how to express the book's ideas and code examples in other languages than Oz, pointers to discussions on Lambda the Ultimate related to the book, and other contributions. We thank Dominic Fox for his initiative in setting up the Wiki.

Kernel language interpreters

The kernel language interpreter VamOz was developed by Frej Drejhammar, Dragan Havelka, and Christian Schulte to animate the execution of the kernel languages according to the abstract machine semantics of the book. A lab session based on the interpreter and a compiled version for Mozart 1.3.0 is available here (unfortunately the source code is not available). The interpreter single-steps through execution and shows the instruction executed and the state of the single-assignment store. The interpreter supports concurrent execution and garbage collection in an especially nice way: it allows the student to choose which thread to single-step or whether to do garbage collection (which "cleans up" the store).

Another kernel language interpreter, ozInOz, was developed by Yves Jaradin. This one is available with full source code here.

Mozart system supplements and example programs

Course: Principles of programming languages (CS 330)

This is a third-year course on computer programming for computer science majors. The course covers about one half of the content of the book. The course is given by Irene Langkilde-Geary at Brigham Young University. The course material including slides is available here. The main page of the course is here. This is probably the most thorough course using the book.

Course: A computer programming course for the 21st century (CS2104)

This is a full set of course material for a second-year course on computer programming for computer science majors. The course follows the structure of the book and covers approximately one third of its content. Feel free to use and modify the course as you wish. We ask only that you give credit to Christian Schulte and Seif Haridi, who developed the course material.

The course starts with functional programming, continues with declarative concurrency, and concludes with multi-agent systems. This approach is nontraditional but simple and extremely powerful. We find that it leads naturally to the right default for structuring programs, namely as concurrent components that communicate through asynchronous message passing. For example, at the end of the course students can implement a contract net protocol in three lines of code.

More traditional approaches, such as starting with object-oriented programming or starting with functional programming and adding state, are also possible with the book. But we strongly discourage both of these approaches, because they place too much emphasis on state, sequential programming, and inheritance. Instead, we encourage the use of composition and higher-order programming instead of inheritance. We give a broad view of data abstraction, of which traditional object-oriented programming is just a part. We show how to do concurrent programming in a much simpler way than the usual shared-state concurrency.

This course material was used by Seif Haridi for CS2104, a two semester-hour course given at the National University of Singapore in the Fall 2003 semester. Student evaluations at the end of the course were very positive; typical quotes are "workload a bit too much ... but the assignments were great", "great experience learning from him [Haridi]", "very good tutorials and lectures", "enjoyed this module very much".

The course material was developed by Seif Haridi and Christian Schulte, based mainly on the course material developed for Datalogi II by Christian Schulte, with some contributions from other sources. Christian Schulte was awarded Best Teacher in Information Technology at KTH for his Datalogi II course.

Lecture slides (more than 1100 slides)

Slides are given two to a page in PDF format. They can be obtained in PowerPoint format upon request from Christian Schulte or Seif Haridi.
  1. Introduction to Programming Concepts I: Organization, Overview, Getting Started (PDF)
  2. Introduction to Programming Concepts II: Compound Values, Partial Values, Lists, Pattern Matching, Towards the Model (PDF)
  3. Declarative Computation Models I: Syntax, Semantics, Kernel Language (PDF)
  4. Declarative Computation Models II: Kernel Language, Computation Model, Abstract Machine (PDF)
  5. Declarative Computation Models III: Pattern Matching, Lexical Scoping, Procedure Definitions and Values (PDF)
  6. Declarative Computation Model and Declarative Programming Techniques: Last Call Optimization, Iterative Computations (PDF)
  7. Declarative Programming Techniques: Iterative Computations, Higher-Order Programming, Abstract Data Types (PDF)
  8. Midterm Exam and Higher-Order Programming, Abstract Data Types (PDF)
  9. Declarative Concurrency: Threads, Dataflow, Streams, Lazy Evaluation (PDF)
  10. Declarative Concurrency and Agents (PDF)
  11. Message-Passing Concurrency: Concurrent Program Design (PDF)
  12. Conclusions / Final Exam: Agents, Course Summary (PDF)

Tutorials (guided exercise sessions)

Lab assignments

These lab assignments were developed by Christian Schulte.
  1. Train Shunting (PDF) This assignment uses a visualizer (Visualizer.zip).
  2. Abstract Machine and Computation Model (PDF) This assignment is theory only; no programming is required.
  3. Huffman Compression (PDF) This assignment uses a program fragment (FindLowest.oz), a test file to compress (TestToCompress.ps), and a test maker (for Mozart 1.3.0: MakeTest.ozf).
  4. RC Circuits (PDF) This assignment uses a simulator graphic visualizer (SimGraph.oz).
  5. Lift Simulation (PDF) This assignment uses the following programs: Agent.oz, Cabin.oz, Floor.oz, Lift.oz, Main.oz, and MemoryCell.oz.

Exams

Here are some previous exams for Datalogi II: Exam1, Exam2, Exam3, Exam4, Exam5. These exams cover similar topics as CS2104. Exam4 and Exam5 are given with solutions.

Course: A more traditional course (LINF1251/Datalogi II)

These slides were used for earlier second-year courses, in particular the LINF1251 course at UCL and the original Datalogi II course at KTH. We will release up-to-date versions of these slides during 2005. In the meantime you may find these useful as raw material. They cover some parts of the book better than the previous course, such as data abstraction, higher-order programming, and object-oriented programming. Feel free to use and modify the slides as you wish. We ask only that you give credit to Seif Haridi and Peter Van Roy, who developed the slides. We would appreciate if you would make any improvements available to the general community.

Lecture slides (more than 600 slides)

  1. Introduction to Programming (chapter 1) (44 slides)
  2. Declarative Computation Model (chapter 2) (136 slides)
  3. Declarative Programming Techniques (chapter 3) (175 slides)
  4. Declarative Concurrency (chapter 4 except laziness) (66 slides)
  5. Lazy Execution (chapter 4 only laziness) (32 slides)
  6. Explicit State (chapter 6) (99 slides)
  7. Object-Oriented Programming (chapter 7) (first version, 80 slides) (second version, 61 slides)
  8. Active Objects (chapter 7, active objects) (20 slides)

Other material for general programming courses

Some additional course material is available at Datalogi II (various materials, developed by Christian Schulte), INGI2131 (lab sessions on concurrent programming, developed at UCL), and LINF1251 (various materials in French and some in English, developed by Seif Haridi, Peter Van Roy, and Raphaël Collet).

Course: A short and intensive second-year course (FSAC1450)

Here are the slides and lab sessions for FSAC1450, a second-year course that takes eight weeks. There is also an extended version, FSAB1402, that takes 12 weeks. Both courses are in French and are described in detail in French on this page. A English-language course with similar goals is available here.

The FSAC1450 course consists of seven two-hour lectures, six four-hour lab sessions, a test, and a final exam. The course was given to all engineering students at UCL (around 300 students, includes non-CS majors) in Fall 2004. In my view, this is the best short programming course that we have developed so far. It gives a self-contained and no-nonsense introduction to programming concepts, covering declarative programming, semantics, state, data abstraction including objects and abstract data types, polymorphism, inheritance, concurrency, and multi-agent systems. As prerequisites, students must have had a first introduction to programming and to simple mathematical concepts such as sets and lists. After this course, students are ready to continue in many different directions, such as object-oriented programming, concurrent programming, software engineering, and theoretical computer science.

The course was developed by Peter Van Roy, with some inspiration from the two previous courses. The lab sessions were developed by Raphaël Collet, Isabelle Dony, Boris Mejías, and Luis Quesada. Feel free to use and modify the course material as you wish. We ask only that you give credit to the developers. Here are the official course Web site and the most up-to-date Web site. The eight weeks are organized as follows:

  1. Introduction and basic concepts (lecture (54 slides), lab session).
  2. Recursion with integers (lecture (40 slides), lab session).
  3. Test: given the third week, it counts for one third of the final grade (test questions with solutions).
  4. Recursion with lists (lecture (52 slides), lab session).
  5. Formal semantics (lecture (61 slides), lab session).
  6. State and data abstraction (lecture (58 slides), lab session).
  7. Objects, classes, polymorphism, and inheritance (lecture (48 slides), lab session).
  8. Closing lecture: Concurrency and multi-agent systems (lecture (45 slides), no lab session).
  9. Final exam: it counts for two thirds of the final grade (exam questions).
The lecture slides and lab sessions for this course are in French. UCL is a French-speaking university in Belgium. See this site for the most up-to-date course notes and explanation in French. We may eventually translate them into English, if there is an opportunity. In the meantime, here is a bilingual English/French glossary of all the technical terms used in the course.

Courses on constraint programming and natural language processing

Several other courses have been developed that use Mozart. We can recommend the following: