My informal title of the course is: In search of programming abstractions for concurrency.

In the real world, there are many events whose relative timing is unconstrained. They may even be simultaneous. For example, you and I may both have lunch independently; we may eat at the same time, but we may also eat one before the other; our lunch times may overlap or not. We call such events (whose ordering is unconstrained/undetermined) concurrent.

Concurrent programming is an essential skill for a modern computing professional, because

• The world is concurrent. We often need to model physical interactions (as in the lunch example above) whose ordering really is unconstrained and may vary over multiple interactions.
• Computer systems include multiple physical entities that can work independently.
• Modern computing environments include distributed components (on multiple, different computers), which, again, work independently.
• Multi-core processors (whose individual cores are no longer getting exponentially faster) are a fact of life, and we want to exploit them.

Programming concurrent actions helps us increase responsiveness, model behaviors more accurately, account for realistic properties of our computing environment, scale our programs to very large problems, and sometimes even make things go faster.

This course poses the questions:

• How can we write concurrent programs, i. e., programs in which parts of the program can run in any order or simultaneously (in parallel)?
• What programming model(s)/abstractions support effective concurrent programming?

Specifically, by taking this course, a student will:

• Understand what concurrency is, how it arises, and why concurrent programming is difficult.
• Understand the implementation basis of concurrent programs.
• Develop and understand solutions to practical and classical synchronization problems.
• Become competent in at least two different models of concurrent programming. This term, we'll do:
  • Conventional, shared-memory threads programming.
  • Actor-style message-passing programming.
• Will complete an in-depth, substantial, team project investigating an application of concurrency or a programming model of concurrency of their choosing.
• Gain experience presenting material in a group setting. Every student will present something to the class at least twice during the semester.

There may be some exposure to other programming models, especially data parallelism, if there is time and interest.

Prerequisites:

• CS 15 or another data structures course
• At least 2 other programming courses, preferably in which students learn one or two programming languages besides their first one
• A spirit of adventure
• A sense of humor

Explanation: Having offered the course a few times, the data sugggests that taking CS 21 directly after CS 15 is not a great idea. Learning two new programming languages, one of them a functional language, and understanding/debugging concurrent programs is a steep challenge for those with only two semesters of programming experience.

If you have taken CS 15 (or equivalent) and have another semester or two of experience, especially if that involved learning another programming language or three, then you will be in a good position to succeed in CS 21.

Course structure and what students will do

The course is organized roughly into thirds (each about a month long). The purpose of the first 2 thirds is to prepare students to do the project in the final part of the course, and therefore also to prepare them for continued study and/or professional practice implemeting concurrent systems.

Please note: You do not have to know anything about the programming languages we will use: I will teach you what you need to know! Don't worry — it works!

1. Programming in a natively concurrent environment. As concurrent programming has become more important, the collection of tools available to help has blossomed. Still, it is much easier to program such applications directly in a language and runtime environment specifically designed to support concurrency.

   In our case, we will use a system that supports the natively concurret Actor model: either Erlang (see also www.erlang.org) or Elixir (see also elixir-lang.org), both of which run on the same virtual machine (the BEAM).

   Specific topics include: sequential functional programming including fundamental immutable data structures, an overview of CSP (Communicating Sequential Processes), extensive experience using Actors including fundamental programming patterns based on message-passing among shared-nothing independent processes. We'll see linked and monitored processes (where one process can track the health of another process). We will look quite a bit at client-server patterns with an introduction to the OTP (the Erlang/Elixir library for robust, generic, concurrent programming).

   In this month of the course, students will do approximately weekly programming assignments (3 or 4), first learning the sequential form of the language, then the concurrent part. In the final assignment, you will write a very simple concurrent application based on our work in class. There will be an exam at the end of this unit.

2. Programming with shared-memory threads. This is a lower-level model and can be more challenging to program in, but there are two reasons to learn it:
   • To understand what is going on under the covers. In that sense, it is to natively concurrent systems as learning a real assembly language is to ordinary sequential programming. You know how things work and have a better idea of what is up when things don't work right.
   • To be prepared for professional or academic work in this area. It's still true that most concurrent programming use some type of shared-memory model, and so you have to know it from a practical point of view.

   We will use Python (see also python.org). Python is not terribly performant, but it is easy to learn, very popular in industry and academia, and will allow us to explore all the problems that arise in concurrent programs and their solutions … all in about a month.

   Specific topics include: what goes wrong without syncrhonization, mutual exclusion, locks, semaphores, common synchronization patterns using those tools including Hoare monitors (implemented in Python classes).

   In this month of the course, students will do approximately weekly programming assignments, first learning the basics of Python, and then learning about concurrent threads and synchronization mechanisms, and finally doing a simple application that uses monitors embedded in Python classes. Students will also do some synchronization puzzles and take turns presenting solutions to the class. There will be an exam at the end of this unit.

3. Team projects! This is really what the whole course is about! Students will form teams of ~3 students each and design and build a final project.

   In this month of the course, teams will turn in project deliverables about every two weeks, starting with an idea, then a detailed design, and culminating with the final project submission (a written report and code) and a presentation to the class. Perhaps we will invite the rest of the department, but at least we in the class will see your work! We will likely devote a fair amount of class time to check-ins and project work. There will be no final exam: just the project.

   Previous projects have included, in no particular order:

   • A simulation of bird flocking behavior
   • Parallel ray tracing
   • Shared canvas, multi-user drawing
   • Shared score, multi-user music composition
   • A distributed orchestra with each computer playing an instrument
   • A distributed, redundant data storage facility
   • A simulation of an ocean ecosystem
   • A multiplayer, distributed game of Halligan Clue
   • A multiplayer, distrubuted snake game
   • A simulation of a child daycare facility
   • …and more…

   If I have time, I can try to put up a gallery.