Some years ago I tried reading How to Design Programs (HtDP) by Felleisen et al., which is an introductory computer science text book. It focuses on a special “design recipe” for designing programs and teaches programming in a Lisp-variant. The authors claim that students who start with HtDP and then proceed to study Java for one term tend to become better Java programmers than those who have been taught Java for two terms.
The premise of the book did sound tempting. Sadly, I found that the pace was way too slow to keep my attention. How to Design Programs was tedious to read because it was rather verbose, and, for my taste, there were too many comparatively insignificant exercises. What I also didn’t like was that the authors went out of their way to avoid mathematical examples, which occasionally led to programs that were more complex than they otherwise would have been. My memory is a bit foggy, but I vaguely remember an exercise in which you had to process a list that consisted of images, but the underlying principle could just as well have been illustrated through some basic mathematical operations on a list of integers.
I eventually put HtDP on the shelf and forgot about it, but I was reminded of it again when I learnt that Prof. Gregor Kiczales of the University of British Columbia was about to teach a course based on HtDP on Coursera, called Introduction to Systematic Program Design. I signed up because I still had an interest in learning the design recipe, and was curious whether it really helped turning you into a better programmer. The original announcement promised a course that would teach you the design recipe in a special “student language”, a variant of Lisp, and once you’ve made it through that sequence, you could pick a different language to tackle the same material again, and see how the design recipe would help you to become more productive in a possibly unfamiliar language more quickly.
Coursera logo of How to Design Programs
Before I go on, I should probably talk about what the design recipe is. In short, it’s a systematic approach to designing programs. There are recipes for designing functions, data definitions, and even interactive programs that use Racket. Further recipes cover, for instance, function composition, backtracking search, or generative recursion. You shouldn’t think of those recipes as straightjackets but as guides. They may be unnecessary for simple programs, but with more complex ones, they allow to reason about the problem you want to solve in a more disciplined way.
Here is the recipe for designing functions, which I’ve taken from the course site:
;; Number -> Number
;; produces n times 2
(check-expect (double 0) (* 0 2))
(check-expect (double 1) (* 1 2))
(check-expect (double 3) (* 3 2))
;(define (double n) 0) ; this is the stub
;(define (double n) ; this is the template
; (... n))
(define (double n)
(* n 2))
The first line describes the involved data types. To the left are the types that constitute the input, to the right the types that will be returned by the function. The next line is the purpose, which informs the reader about the function in English. The “check-expects” are tests for the function, but before you write those, you are supposed to write the stub. With the stub, you can then run the tests and check whether they were well-formed.
The templates were recommended for beginners, and were dropped in the latter half of the course. As the name implies, they give you a template for the actual function you’re going to write. Now, in the given example, this may look a bit silly, but when you’re working on a more complex function that requires, for instance, generative recursion, the templates are quite useful. There is a bit more to the design recipe as it extends to data definitions and recommendations for function decomposition, but their general outline should now be clear.
Introduction to Systematic Program Design was originally planned as a single course, spanning 14 weeks, if I recall correctly. However, this was changed and the course split into two parts. A starting date for part 2 has not been announced yet. However, Prof. Gregor Kiczales wrote that they might offer part I again first, aimed at students at the University of British Columbia first, before hosting part II on Coursera.
The course itself targets both beginners and experienced programmers. According to Prof. Kiczales, more experienced programmers who took his course said that it helped them improve their craft. I’m in the latter camp, and I subscribe to that notion. Introduction to Systematic Program Design took me a few dozen hours to complete, but I’ve probably saved half of that amount time on various programming projects already thanks to following the design recipe at times.
The course takes eight weeks and consists of eight units. There are eight weekly quizzes, two programming projects, and one final exam. To pass the course and earn a certificate, you have to have a score of 50% for a regular certificate of accomplishment, and if you want to earn a certificate with distinction, you need 80%. Homework counts 40% of the grade, the projects 30%, and the final exam 30%. I’ll say more about grading and the projects further down.
The first few weeks of the course are relatively slow-paced. If you’ve got no experience with programming, you should pay close attention and only proceed if you really understand all the concepts that are taught. The videos offer excellent support as they not only cover the necessary theoretical foundations, but also walk you through many examples. Experienced programmers can go through the first three weeks probably rather quickly. They cover data types, function composition, and how to model data. However, the course uses a Lisp-variant as its teaching language. If you come from an imperative background, you may find some of the assignments challenging. However, each week numerous practice exercises in various degrees of difficulty were provided that enable you to smoothly work your way up from the lecture material to the homework problems.
Week 4 introduced interactive programs. I was quite surprised how easy it was to animate some geometric shapes on screen. As the programs became more complex, I was pleased by the user-friendliness of the DrRacket environment, which was a real joy to use. In week 4 there also was a noticeable increase in difficulty. It should probably be pointed out that some of the practice exercises tended to be more challenging than the homework problems, which were assessed in the quizzes. One of the exercises had you code up a rolling lambda symbol, the DrRacket logo. It was supposed to change direction when you click the mouse, or when it hit the left or right border of the screen. I’m not sure the following still image can convey it clearly, but I hope it’ll do:
Rolling lambda, moving from right to left
This problem involved rotation in positive and negative direction, translation on the x-axis, collision detection, as well as user interaction due to capturing mouse inputs. I noticed that there were many complaints in the forum about that exercise. I then checked my solution with the one that was provided, and could see what the issue was: the solution the course staff provided was tersely written and needlessly complicated, and therefore difficult to follow.
However, I was pleasantly surprised that the people involved with the course reacted quickly to the, in my opinion, justified complaints and revised their sample solution. Some days later an additional practice problem was added that slightly simplified the original problem. I found this attitude most impressive. From university I am used to a “sink or swim” approach, which is a stance you can encounter in some online courses as well. For instance, in Martin Odersky’s Functional Programming Principles in Scala there was an enormous discrepancy between the material in the lectures and the exercises, but the TAs thought this was no problem at all and only reiterated that this course was basically identical to the one at EPFL, and that they had no intention of making the material more accessible. What the TAs didn’t tell you, or didn’t want to draw attention to, though, was that at universities you don’t just have lectures and hand-ins, but also tutorial sessions or “labs” and office-hours. In one of the announcements Prof. Kiczales specifically made the point that the course, when taught at UBC, has a weekly three-hour lab session, which obviously can’t be replicated online, and that as a result, the online offering may be more challenging. However, instead of UBC only putting their course material online, they did their best to provide a supportive infrastructure, without watering down the course.
That this course wasn’t “dumbed down” became clear in the second half, which covered recursion and mutually referential types, eventually leading to generative recursion. Week 8 had, fittingly, some of the most challenging exercises which asked you to write programs that generate various fractals. The final project was an application of the backtracking search that was introduced in the lectures that discussed how to solve Sudoku puzzles. The variation was to write a solver for the 4-queens problem, with the option to generalize the solution to the n-queens problem. By week 8 I saw the value of the “design recipe”. While it looks like overkill in the first few weeks, which is a point Prof. Kiczales acknowledged himself repeatedly, it does make your life easier if you stick to it.
Judging from the discussions in the forum, a vocal minority seemed either unprepared for a programming course or unwilling to forget about “object-oriented programming”, adapt the mindset of a beginner and just learn the basics of Lisp. There were threads with literally hundreds of replies in which “seasoned software architects” tried to argue that Lisp was the wrong choice for the course and that it should be taught in Java or Python instead. This was quite tragic to see since Lisp and especially the “student language” we used can be described very concisely. I wonder what would have happened if those people just had sat down with an open mind and tried to learn the few language rules of Lisp instead of making a post about how “useless” and “weird” that language was.
Lastly, a word about grading: I had the impression that there was a dramatic rate of attrition throughout the course. While the forum seemed lively during the first few weeks, activity slowed down noticeably as the course went on. Yet, I would assume that concepts like “closure” or the traversal of arbitrary-arity trees would generate more questions than, say, the problem of concatenating two strings or changing the color of a rectangle. I’d be interested to see some retention statistics. In the latter weeks, it seemed that almost exclusively people with significant previous experience were populating the forums. One guy shared personal anecdotes from meeting John McCarthy, the creator of Lisp, for instance.
There were quite a few discussions in which Prof. Kiczales contributed, too. One thread I particularly enjoyed was devoted to optimization strategies for the Sudoku solver. While I avoided the forums in the first half of the course, I saw them becoming increasingly valuable in the second half. However, if my perception is correct, then the other side of the coin is that courses like this only increase the “digital divide”. It seemed that one of the promises of MOOCs was to bring higher education to people who would otherwise not have access to it, but I have the impression that it is mostly those who are advantaged already who make use of them. This is a more philosophical issue, but one that shouldn’t be ignored. I noticed that Udacity made great strides in offering preparatory courses that try bridge the gap between high school and university-level courses, so there is hope that MOOCs may one day indeed educate the masses and not just further the education of an intellectually curious minority. Making college-level courses more accessible by providing preparatory introductory and remedial courses is a challenge for Coursera and not necessarily UBC, though, so this is in no way intended to be a criticism of Introduction to Systematic Program Design.
After this diversion, let me now make some remarks about the grading. The homework problems are not automatically graded but evaluated through quizzes. Probably peer-review may be a better solution. In their current form the homework problems may be difficult to grade automatically since the majority of the exercises was such that there was more than one possible solution. I’m not sure a satisfying solution exists for this problem. For instance, MIT’s Introduction to Computer Science and Programming on EdX split up the more elaborate assignments and had students submit their solution in multiple parts. This was a tedious process, and not only because there were plenty of instances were the autograder expected a certain approach instead while rejecting a perfectly valid alternative one.
Speaking of projects, the first project was to write a simple text editor similar to what is found on old mobile phones:
Screenshot of the editor
This is a neat little interactive application. The program rejects invalid input, the cursor can be freely moved around to change the insertion point, and the backspace key deletes the character to the left of the cursor if there is any.
The second project was, as I said above, a solver for the 4 queens problem, based on a backtracking search. This was a very enjoyable exercise too, and one where it quickly paid off to follow the design recipe. There was a change in grading this last exercise, though. I suspect it had at least to some degree to do with the fact that the rate of attrition has, or at least seemed to be, very high. The deadline for the project was pushed back by four week to give copious amounts of time to finish the course material and the project. However, the final project was self-assessed, meaning that in theory you could just give yourself the highest score without doing the any work and thus get 15% of the course grade for free. I found this change of the course policy unsatisfactory. On the other hand, most probably enrolled in this course to learn something and not just to weasel their way to a PDF certificate.
The final exam was worth 30%. It was designed as the equivalent to a 24-hour take-home exam. It covered material drawn from all eight weeks of the course. The exam was not particularly challenging, but this may just be testament to the high quality of the teaching. Overall, Introduction to Systematic Program Design – Part 1 was a fantastic course, and I’m eagerly awaiting the second part.
After I wrote this review, Prof. Kiczales announced that Introduction to Systematic Program Design – Part 1 will be offered again on the 4th of September. Changes include an increase in the duration of the course form eight to ten weeks to even out the workload, the addition of a third project, and a change in the assessment of the homework problems.