1 Introduction

\(\newcommand{\la}{\lambda} \newcommand{\Ga}{\Gamma} \newcommand{\ra}{\rightarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\La}{\Leftarrow} \newcommand{\tl}{\triangleleft} \newcommand{\ir}[3]{\displaystyle\frac{#2}{#3}~{\textstyle #1}}\)

I will assume you have read and hopefully worked through Part I of this flânerie. Here is the first paragraph of the introduction to Part I.

This flânerie is a stroll through the more easily accessible districts of computer science, of which programming is just a part, albeit a significant one. A conventional approach to the subject starts with a course that is primarily concerned with programming in a popular imperative language (such as C++, Java, or Python). These are large and complex languages designed for experts, and consequently much initial effort is aimed at mastering idiosyncratic syntax and corner cases, at the expense of solid mental models, deeper understanding, and truly representative topics.

Instead of taking a conventional approach, Part I made use of the idea that originally inspired Racket, using small, purely-functional teaching languages that introduce powerful features one by one, and exploring the implications of each new capability. This approach is much more effective and interesting.

But we still have to deal with the fact that most work in computer science is carried out using large, complex imperative languages. How should we proceed to learn about these? Unfortunately, even at educational institutions that use a functional-first introduction, usually the next course reverts to a conventional approach, with little or no reference to lessons learned in the functional setting.

The first edition of How To Design Programs (HtDP) tried to address this in its last several chapters, with the help of a fifth teaching language, Advanced Student, that introduced imperative concepts. This had two unfortunate consequences. The first was to make it seem as imperative features were more advanced than functional ones. In fact, they are more primitive. Imperative languages are not popular because they are objectively better to work with; the reasons have more to do with historical development and inertia.

The second unfortunate consequence is that imperative features distort the computational model to the point where it is difficult to use. It remains useful for a primarily-functional language with some imperative features (like full Racket), but it is not very useful for a primarily-imperative language with some functional features added later on. It’s a depressing way to end a book or a course, and the second edition of HtDP left out this material, with the promise of a second book to address the transition.

I originally designed our second course to follow up on Part I material, and I chose C as the imperative language to focus on. What remains of that design is now in my short flânerie If You Must Learn C (IYMLC). Here is a quote from the first paragraph of the introduction to IYMLC.

C provides thin abstractions over assembly language, and many features of the language are best understood by thinking about similar tasks carried out by sequences of machine instructions in a model that more closely resembles a physical electronic computer (as opposed to the more abstract computational model based on program rewriting typically used to explain Racket).

My initial idea was to first introduce imperative features using full Racket, because this is a natural setting in which they are used judiciously for the right reasons. Following that, we would start learning C by learning about the new computational model mentioned above, based on physical components and machine instructions, but with suitable simplifications. That would motivate the design of C and thus the design of successor languages that were heavily influenced by C.

This proved to still be too much of a leap, without the ability to carry along enough lessons from the earlier functional material. It was hard to motivate the machine model without material that was presented several weeks later. Although C is not as complex as C++ or Java, it still has a number of quirks that make things messy for beginners. Python is easier to use, but it’s not so simple to give a proper computational model for it, especially with respect to efficiency. And while C is the best choice for a first imperative language for CS majors, it is not suitable for non-CS majors.

I decided to move the C material from lectures to tutorials (those tutorials are what you see in IYMLC) and to invert the order of what remained. Instead of moving up from a machine model, we would move down from what we knew. There’s still a motivational issue, but at least it’s confined to the boundary of an expanding set of knowledge, instead of with a completely new topic.

No suitable teaching languages existed, so I would have to invent them. Although it is possible to create new languages within Racket, I didn’t need to go that far. Since writing small interpreters was so effective at the end of Part I, we could continue to do that, with all the benefits detailed earlier. Further motivation is provided with the promise to learn enough about what was happening at the machine level to be able to discuss how to efficiently implement a functional interpreter in an imperative language. It turns out that this opens the door to even more advanced features of Racket itself, and so the development concludes on a high note rather than down in the weeds.

This alternative second course is still largely taught this way at the University of Waterloo, though I am no longer involved with it. The materials have not previously been publicly available. Following the timeline sketched above, the first thing to do is to move to full Racket and start introducing key imperative features, starting with ones that have the least effect on the computational model. We’ll get to that right away.