• Graduate Level (Master) at the ULB (Université Libre de Bruxelles) - 5 ECTS
• Prof. Dr. Wolfgang De Meuter
• Necessary prerequisite/corequisite for "Functional Programming" (Prof. Dr. Wolfgang De Meuter - VUB Course)
• Recommended prerequisite/corequisite for "Principles of Object-Oriented Languages" (Prof. Dr. Andy Kellens - VUB Course)
• Recommended prerequisite for "Distributed and Mobile Programming Paradigms" (Prof. Dr. Elisa Gonzalez Boix - VUB Course)
• VUB students that want to take this course have to register manually by sending an email to the trajectory counselor Reen Tallon. ULB students need to register with their faculty.

Last change: 20 September 2015 (update for new academic year)

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 (Python, C, Pascal, C++, Java, Visual Basic, …) what Latin is to roman languages (French, Spanish, Romanian, …).

In the second part, we will explain the concept of a continuation. Continuations are a way to turn computations into first class objects. That allows us to manipulate entire computations inside a computation. We will exemplify continuations by making our own version of multi-tasking, a goto statement and an exception handling system.

In the third 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. We will study 4 interpreters: a "vanila" version, a CPS-version, a lazy interpreter and an ambiguous "non-deterministic" interpreter.

In the fourth part, we present a very brief introduction to the lambda calculus and explain how Scheme relates to this calculus. We end by proving and using the fixed point theorem.

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.

Prerequisites

Although MIT's SICP was meant as an introduction to computer science, this course will be taught at a fast pace. This version of the course assumes that students already know how to program in a mainstream imperative language such as Python, 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).

Contents and Material

The course follows a large part of the SICP Book quite closely.

Here are the transparencies of the course (they will gradually become available):

• Chapter 0 (Color)
• Chapter 0 (Printer friendly)
• Chapter 1 (Color)
• Chapter 1 (Printer friendly)
• Chapter 2 (Color)
• Chapter 2 (Printer friendly)
• Chapter 3 (Color)
• Chapter 3 (Printer friendly)

Software:

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

• [ to be updated ] An R6RS-version of the stream procedures of SICP can be found here.

• [ to be updated ] The R6RS-version of the source code for the evaluators of chapters 5+6 can be downloaded here.

Assessment & Exam

Students will be evaluated on two levels. An oral exam tests their understanding of the concepts. A programming assignment will test their technical skills. The programming project will be done with ARMpit Scheme.