Structure and Interpretation of Computer Programs (taught in English)

• Graduate Level (Master) at the ULB (Université Libre de Bruxelles)
• Prof. Dr. Wolfgang De Meuter

Last change: 24 September 2011 (added course material)

The course starts out from scratch as if we were teaching computer science to 18 year olds, by teaching you the programming language Scheme. Scheme is a dialect of Lisp which is an old artificial intelligence language. The course is not really about Scheme. Nevertheless, a deep understanding of how Scheme works is essential for understanding the rest of the course. Mastering Scheme's concepts will give the student an extremely deep understanding of how programming languages work. And that is what this course is all about!

In the first part, we will explain Scheme's deep semantic concepts (evaluation, scoping, environment diagrams, symbolic data, sameness and change,…). As we go along we will study functional (higher order) programming, imperative programming, object-oriented programming, stream programming and constraint programming in Scheme. The goal is to show that Scheme's (very few) abstractions are universal abstractions that underly all these very different computational paradigms. The goal is to show you that Scheme is to sequential programming languages (C, Pascal, C++, Java, Visual Basic, …) what Latin is to roman languages (French, Spanish, Romanian, …).

In the second part, we will explain you the inner workings of programming languages by writing an interpreter for Scheme, in Scheme. This is known as meta-circularity. This will allow us to study all the deep semantic concepts from an implementational point of view. Having a metacircular interpreter for Scheme will allow us to discuss a number of variations of Scheme and experiment with these variations by modifying our interpreter.

In the third part, we will study the inner workings of programming languages by transforming them into a low level formalism. This will be explained by presenting a compiler for Scheme to a simplistic assembly language that is executed by a virtual machine written in … Scheme. This will give the students insight into how the aforementioned deep semantic concepts are executed by a low level machine.

This course will permanently change the way you think about programming and programming languages. And above all, it's big fun! The course is based on the famous “Structure and Interpretation of Computer Programs” (SICP) that has been used for more than 20 years as the introductory course in computer science at the Massachusetts Institute of Technology (MIT). Experience at the VUB since the early 90ies has shown that even experienced computer science students (year 3 or higher) had to radically change their view on computer science after having gone through this course.

Although SICP was meant as an introduction to computer science, this course will teach it at a fast pace. This version of the course assumes that students already know how to program in a mainstream imperative language such as C, C++, Java or C#, or, that the students are learning such a language in parallel at the master level (e.g. students that already have a master in some other subject).

In academic year 2011-2012, the course will be taught in room P.OF.2072, campus de la plaine ULB.

In the first 3 weeks, the course is taught on Mondays from 16hrs till 18hrs.

The course follows the SICP Book quite closely.

Here are the transparencies for chapters 1 to 3. Chapter 4 and 5 are under construction.

• Chapter 1 (Color)
• Chapter 1 (Printer friendly)
• Chapter 2 (Color)
• Chapter 2 (Printer friendly)
• Chapter 3 (Color)
• Chapter 3 (Printer friendly)
• Chapter 4 (Color)
• Chapter 4 (Printer friendly)
• Chapter 5 (Color)
• Chapter 5 (Printer friendly)
• Chapter 6 (Color)
• Chapter 6 (Printer friendly)

Software:

• There are several implementations of Scheme. For didactic purposes, I recommend DrRacket .

• An R6RS-version of the stream procedures of SICP can be found here.

• The R6RS-version of the source code for the evaluators of chapter 4 can be downloaded here.

Students will be evaluated on two levels. An oral exam tests their understanding of the concepts. A bunch of small programming assignment during the semester will test their technical skills. A French-speaking assistant will be present at the oral exam.

Here is a link to the programming assignments.