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}}\)
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.
I started this way myself (with earlier, now obsolete languages), and, after completing my schooling, taught within this paradigm for many years. In mid-career, I came across the functional programming language that is now called Racket, and the associated textbook How To Design Programs (HtDP). I taught my own tweener children using these two resources, and then started trying to convince my own university to use them. My argument was that the language and textbook were designed for modern education, and that they facilitated earlier discussion of a broader range of topics. We now put two thousand students a year through a first course in computer science (not just programming) using these excellent tools. The majority of these students are pursuing majors other than computer science, but we consider it important preparation for our own majors.
There are three versions of that first course. One version (that I originally designed and taught) used Racket, but not HtDP. Why, when that book was so helpful to us? HtDP, in order to reach the broadest possible audience, requires only middle-school mathematics. Another offshoot, the Bootstrap programme, is using Racket to help teach mathematics to middle-school students. But at the University of Waterloo, our School of Computer Science is housed within a Faculty of Mathematics, the largest in the world. Every undergraduate student entering the Faculty, regardless of major, is required to take two courses in computer science. These students tend to have very good mathematical skills, and some of them have excellent skills. I had the chance to develop two courses for that audience. What you are reading is the result of that development.
1.1 Required background
My original syllabus for the courses said that students did not need prior experience with computing (which remains true) but they should have mathematical aptitude and enthusiasm for the subject. Presumably, since you are still reading this, the mention of mathematics has not put you off. But what does "mathematical aptitude" mean?
It does not necessarily mean good marks in math classes, or even love for math. There is a lot of mathematical education out there that does not do justice to the subject. Sometimes courses, especially at the primary or secondary level, focus too much on rote computation, or memorization of formulas and techniques. This can discourage students. I personally earned poor marks in math until late middle school and high school. When algebra came along, suddenly I took off. Sometimes it is possible to earn marks for the wrong reasons.
I view mathematical aptitude as ability to deal with abstractions, willingness to reason about the consequences of clearly-defined rules, and appreciation for discovered or elaborated structure. I will not be relying on many topics or details from mathematics; at most a little bit of algebra, and absolutely no calculus. But I will be using mathematical thought throughout, and you should be comfortable with that.
Not only is prior experience with computing not necessary, but prior experience can actually be harmful, if you are not willing to set it aside when needed. The reason is that my approach is unconventional. If you keep trying to do things in ways you learned earlier, you may just make it harder for yourself.
You will need a computer on which you can install Racket. It should be running Mac OS X, Linux, or Windows. Racket’s installation is fairly simple, but you should be comfortable with downloading files and navigating your computer’s file system. You can’t do the suggested programming in a Web browser or on a phone. You will need to use the DrRacket application, which is part of the Racket distribution. This is one of the best IDEs (integrated development environments) I know, so you have something to look forward to.
1.2 Design philosophy
Computing skills are in great demand these days, and a degree in computer science is not a necessary prerequisite for a computing job. Many people are self-taught; others gain rapid exposure in "camps" that last only a few weeks or months. Even with four-year university programmes, there is pressure to use programming languages that are currently popular in industry. Starting students in some of these languages is a little like starting flight school in the cockpit of an Airbus A320.
There have always been educational programming languages. Some have even been later deployed in industry, as graduating students convinced their new employers of their utility. Racket started out as a primarily educational language, and has since become a vehicle for research published in the most respected venues. It is designed in such a way that lets one be precise about what constitutes a legal program and what the result of running that program should be, in a way that is more difficult for other languages. Experience with Racket makes it easier to grasp the essence of other languages.
Mathematics is our best tool for dealing with precision. Much conventional computer science (and many other topics) is taught primarily via examples. The student is left to generalize, but without the tools to fully articulate the generalization, or to fix their understanding if their generalization proves incorrect. The mathematical approach is to describe the general situation, and then illustrate with an example or two. That is the approach I take.
Many students are drawn to computing through experience with compelling applications such as games. Many introductory courses motivate students in this fashion. Even HtDP heavily uses the construction of still images and animations, albeit in a much more effective way than most other sources. Most of the content of a computer science curriculum has little that is specific to gaming or other popular applications, and students are sometimes disappointed after their introductory courses. I wanted to give a more honest view of what the field is like. What is computing? How do we define it and reason about it? What are the major challenges?
My material contains a number of embedded exercises, most of which were originally assignment exercises or exam questions. Doing the exercises is an important part of the learning process. You cannot fully engage with the subject just by reading.
A logistical note: These Web pages use MathJax to render mathematical expressions, which requires the intervention of a third-party server. If the MathJax server is unreachable, you will see the underlying LaTeX code for the expressions instead. This should be readable, though with difficulty that increases with the complexity of the expression.