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:

CS330 course (3 semester-hours, most thorough course in English, taught by Irene Geary at BYU)
CS2104 course (2 semester-hours, approach using concurrent programming)
LINF1251/Datalogi II course (2 semester-hours, a more traditional approach)
FSAC1450 course (2 semester-hour, most thorough course in French)

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:

constraint programming and natural language processing

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

The source code of the book's figures. These figures have been corrected according to the book's errata.
The extensions to the basic Mozart system that are used in the book.
- Basic system supplements. This should be put in the .ozrc file in your home directory.
- Basic file I/O (functor File.oz).
- Set utilities (functor Set.oz).
- Distribution utilities (functor Distribution.oz).
- dserver, dclient, Guard utility (functors).
The functors should be compiled using the ozc command (see Appendix A in the book or the Mozart documentation).
Other useful Mozart source code.
- The tree-drawing algorithm of chapter 3. This contains the tree-drawing algorithm as well as the GUI code necessary to display it as shown in the book.
- The Ping-Pong program of chapter 5. This contains the Ping-Pong program as well as the graphical progress monitor used to show its progress on the screen.
- The simple graphics package of chapter 7. This is an example of multiple inheritance.
- Functional Reactive Programming (FRP). This shows how to do Functional Reactive Programming in Oz.
- Lazy quicksort and lazy mergesort. These are two examples to show how the smart use of lazy execution can create an efficient incremental algorithm starting from a declarative algorithm. Starting from an efficient sorting algorithm, we add lazy declarations to create an incremental algorithm that efficiently calculates the smallest k elements out of n without knowing k in advance.
- Communicating Sequential Processes (CSP). This shows how to implement the send and receive operations of CSP in Oz.
- Contract Net Protocol. This shows how to implement a contract net protocol in just three lines using functional building blocks as concurrency patterns.
- Observable port objects. This shows how to extend a port object to output a stream of the object's internal states. This is another example of using functional building blocks as concurrency patterns.
- Partial barrier synchronization. This shows how to implement several variations on barrier synchronization. The examples show when to stay in the declarative subset and when to use ports. This is another example of using functional building blocks as concurrency patterns.
- Multi-core execution. This shows how to use Mozart's transparent distribution support to run programs on multi-core processors to exploit all the cores.
- Declarative memoization by Lyle Kopnicky. This shows how to do memoization by using lazy evaluation to build an infinite table of results as they are needed.
The Oz Minesweeper (paper). This looks like the usual minesweeper game, but it is extended with a digital assistant that uses constraint programming to deduce squares that are known to be safe. When it cannot deduce that a square is safe, it calculates the probability that a square contains a mine, assuming a uniform distribution of mines. This program comes with complete source code for Mozart version 1.3.0 (which also runs on 1.4.0).
FlexClock (paper). This is a clock utility with a dynamically adaptive display. It uses the powerful multiparadigm GUI library QTk to dynamically adapt the display to changing window size. This program comes with complete source code for Mozart version 1.4.0.
Mozart System Limitations for Version 1.3.0 (PDF) explains the differences between the ideal computer of the book and Mozart version 1.3.0.

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.

Introduction to Programming Concepts I: Organization, Overview, Getting Started (PDF)
Introduction to Programming Concepts II: Compound Values, Partial Values, Lists, Pattern Matching, Towards the Model (PDF)
Declarative Computation Models I: Syntax, Semantics, Kernel Language (PDF)
Declarative Computation Models II: Kernel Language, Computation Model, Abstract Machine (PDF)
Declarative Computation Models III: Pattern Matching, Lexical Scoping, Procedure Definitions and Values (PDF)
Declarative Computation Model and Declarative Programming Techniques: Last Call Optimization, Iterative Computations (PDF)
Declarative Programming Techniques: Iterative Computations, Higher-Order Programming, Abstract Data Types (PDF)
Midterm Exam and Higher-Order Programming, Abstract Data Types (PDF)
Declarative Concurrency: Threads, Dataflow, Streams, Lazy Evaluation (PDF)
Declarative Concurrency and Agents (PDF)
Message-Passing Concurrency: Concurrent Program Design (PDF)
Conclusions / Final Exam: Agents, Course Summary (PDF)

Tutorials (guided exercise sessions)

Getting Started (for lecture 1) (PDF)
Tuples, Records, Lists, and List Processing (for lecture 2) (PDF)
Data Structures and Grammars (for lecture 3) (PDF)
Computation Model, Abstract Machine I (for lecture 4) (PDF)
Computation Model, Abstract Machine II (for lecture 5) (PDF)
Iterative Computations, Types, Higher-Order Programming (for lectures 6-7) (PDF)
Abstract Data Types, Declarative Concurrency (for lecture 8) (PDF)
Message-Passing Concurrency (for lectures 9-10) (PDF)

Lab assignments

These lab assignments were developed by Christian Schulte.

Train Shunting (PDF) This assignment uses a visualizer (Visualizer.zip).
Abstract Machine and Computation Model (PDF) This assignment is theory only; no programming is required.
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).
RC Circuits (PDF) This assignment uses a simulator graphic visualizer (SimGraph.oz).
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)

Introduction to Programming (chapter 1) (44 slides)
Declarative Computation Model (chapter 2) (136 slides)
Declarative Programming Techniques (chapter 3) (175 slides)
Declarative Concurrency (chapter 4 except laziness) (66 slides)
Lazy Execution (chapter 4 only laziness) (32 slides)
Explicit State (chapter 6) (99 slides)
Object-Oriented Programming (chapter 7) (first version, 80 slides) (second version, 61 slides)
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:

Introduction and basic concepts (lecture (54 slides), lab session).
Recursion with integers (lecture (40 slides), lab session).
Test: given the third week, it counts for one third of the final grade (test questions with solutions).
Recursion with lists (lecture (52 slides), lab session).
Formal semantics (lecture (61 slides), lab session).
State and data abstraction (lecture (58 slides), lab session).
Objects, classes, polymorphism, and inheritance (lecture (48 slides), lab session).
Closing lecture: Concurrency and multi-agent systems (lecture (45 slides), no lab session).
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:

2G1515 Constraint Programming. This course is given at KTH by Christian Schulte. The 2G1515 Web site has a full set of course material including lecture slides and assignments.
Constraint Programming For Natural Language Processing. This course was given at ESSLLI 2000 by Denys Duchier. Additional material can be found in the draft book Concurrent Constraint Programming in Oz for Natural Language Processing, by Denys Duchier, Claire Gardent, and Joachim Niehren. A related course, Multi-Paradigm Programming in Oz for Natural Language Processing, was given at the Graduate School of Language Technology, Gothenburg University, Sweden, by Torbj�rn Lager and Denys Duchier.