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.
Addendum:
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.
Hello, Gregor.
I’m one of the students who, through a great deal of effort and occasional frustration, managed to get through to the end of ISPD1. I’m also one for whom the class has helped ameliorate the lack of formal education. By the time I regained my undeveloped childhood interest in programming I was already an adult with a family and a mere year’s worth of a degree in music performance. What little programming experience I have was picked up from books on my own time. I have never gotten far with it for various reasons. On my own it’s easy to get frustrated or bored—most books are either too dry, or too slow, or are too advanced—and without a real sense of need for programming, it’s easy to get distracted and go on to something else.
This class was a watershed event for me. I’ll leave it to someone else spill over with empowerment jargon, but for me the opportunity here has been truly life changing in the best, most effective, but un-glamorous sort of way. It got me over the hump. It ignited a dormant interest. It changed my perspective on myself and the world around me. All this sounds grandiose and ridden with cliché. And yet it is all, quite simply, true.
I’m very grateful for the class, with a gratitude verging on transference, because of the change it has effected in my perspective. You may be right that “it is mostly those who are advantaged already who make use of them,” but I would argue that this is irrelevant. These MOOCs are making available to me at least pieces of an education which I had resigned myself to never gaining. I find it hard to believe I’m the only one.
Best wishes,
Christopher
Thanks for sharing this, Christopher! I agree that it is difficult to find books that are suitable for autodidacts, and that (good) MOOCs offer tremendous value. I don’t doubt that there are many individuals who experience MOOCs as transformational, but those people are the minority. It’s just like at university. You might have the most inspiring, charismatic and smartest guy in front of you, and half the class is barely awake. I’m exaggerating, but in general people are not that interested in education, and that’s particularly true for those who think they have to attend university. Most just want to pass the test, by any means necessary, and do the minimum amount of work. Thanks to grade inflation, they all get their As.
On a side note, a great example of pearls before swine in higher education are some of the MIT OCW recordings. I was once watching a couple of calculus videos, and some of the students were asking questions that were downright absurd. The lecturer quickly recapitulated that if you differentiate sin(x), you get cos(x), and if you differentiate cos(x), you get -sin(x). In other words, if you differentiate sin(x) twice, you end up with the negation of the original function — and then some girl asked whether this was true for every function. I couldn’t close my mouth for a good ten seconds afterwards. Another example I came across some time ago is provided by a lecture series on algorithms by one of the IITs, the Indian elite technical universities. The lecturer was going through properties of a particular algorithm, and students were asking the most basic questions about Java.
Now I’ve rambled on for a bit, but the point I’m trying to make is that MOOCs certainly widen access to education, and motivated individuals can make use of it. However, I don’t quite buy the rhetoric that surrounds it, and not just because the average student would rather do a million things before studying on his own. Then there is the economic aspect. Coursera aggressively touts itself to be a “social enterprise”. What will happen, though, is that Coursera will put universities out of business. I won’t cast judgment on whether this is good or bad, but draw attention to the possibility that providers of MOOCs will not so much make the pie bigger but instead simply take over a good chunk of the market, while marginally increasing the pie (due to a small minority of motivated autodidacts).
On a somewhat related note, I can’t help but notice, when I look back at the history of technological progress, that breakthrough inventions were first glamorized and praised for their potential, before reality hit. Radio was supposed to educate the masses. Now we’ve got Top 40 music while quality content has only a small niche. After radio failed to live up to its promises, television was seen to fulfill the promises radio didn’t live up to. What did we get instead? Talk shows, reality TV, and infomercials. When MTV started, some saw potential for it as a medium to express an artistic vision through music videos. Instead, it quickly turned into a platform for nothing but promotion. Or think of the Internet. It’s primarily commercial, and places where you can have discussions on a relatively high level are far and between. Most Internet traffic goes to, well, sports, cat pictures, and porn. Feel free to call me a skeptic, but I just don’t see how MOOCs will have a large-scale impact. What might happen, though, is that they’ll undermine the very idea of “college”, and that only very few elite universities survive, while the hoi polloi will have to get their certificates and diplomas via Coursera or Udacity at a fraction of the current cost, possibly in their spare time, while they slave away at minimum-wage jobs.
I haven’t followed the development of MOOCs closely. This was my first experience with them, and I am still relatively ignorant of the rhetoric surrounding them. I can imagine, though. And I share your skepticism with regards to the general pattern of technological development. For the time being, however, and for me personally, they provide an opportunity which was formerly scarce and difficult to access.
I’m very skeptical of the state of education in general, most specifically in terms of the topics which have meant most to me. Our STEM programs may or may not be relatively healthy—I have little experience with them—but the humanities are, I am convinced, in a very bad state. I am autodidact enough to have a possibly over-idealized view of what the liberal arts could be and perhaps once were. I am certainly idealistic enough to lament the obsession with pragmatism and commercial application of every skill set and domain of knowledge.
Currently what I am seeing with the MOOCs is the possibility of advancing my own knowledge while schlepping my way through my unfulfilling and poorly paying day job. I’ve been struggling with this problem for years. Not just in technology, in almost everything that I have pursued, the books out there are either completely popular and have too low of a value density—and are usually pragmatic and imperative, and again this is not just to do with technical topics—or are aimed at those who have already gained a certain degree of mastery. And my suspicion is that colleges are going the way of trade schools and “For Dummies” books. The for-profit online degree options seem to be several steps further in this direction. This could all be ill-informed bias, but it’s the sense of things that I’ve gotten from my attempts to find a way forward in my working life.
Because of my poor life choices in my early 20s I’ve spent the last 15+ years working in one low-grade technical job after another as a retail technician, small business IT grunt, and currently as technical support for software and hardware middleware used in medical labs. 8 years ago I had hopes of getting into programming somehow, but along the way became convinced that it was just unobtainable without a good college education. Having spent the last couple years working alongside programmers (mostly all fresh out of a reputable *IT school, and mostly all of whom seem to only be interested in clocking out) I’m really not sure they’ve got anything that I can’t get for myself through my own hard work. In some ways I’m certainly more systematically inclined than most of them. Maybe it’s really a case similar to the person who looks at some piece of modern art and then says, “Well, hell, I can do that just as well if not better.” But I’m ready to test the theory. I’m nearly 40. I’m not interested in burying myself in school debt, or working 80 hour weeks. I’m not really interested in flashy startup jobs. I want to be able to support my family doing something more fulfilling than what I’m doing now, while contributing back to FOSS, and being a classical dilettante, and bread baker in my spare time. For me, this is what it would mean to be successful. The delusions of grandeur that plagued my youth are gone. Now I want something comfortably challenging and a relatively tidy life of interest. These courses, for however long they last, seem to be a really good way of progressing towards my goals.
Oh, the humanities certainly are in a poor state. The liberal arts were once supposed to provide a well-rounded education for the sons of the gentry and contained grammar, rhetoric, logic, arithmetic, geometry, music, and astronomy. These days, they don’t provide much of that. I guess subjects like comparative literary studies, political science or communications are great if you run a country, want to inflate students numbers and keep people off the street for a few years. They do students a disservice, though. Yet, mainstream opinion is that you have to go to college, no matter whether you’ll be learning anything there or not.
I think you’ve got a good plan. Your competition won’t be graduates from Stanford or MIT but the countless people who have a degree in IT from local schools, and those often don’t learn much at all: some Java, a bit of SQL, very little theory. You can easily learn all of this yourself. Also, you should be aware that you’ve made it through a challenging course already, which should give you further motivation. Recursion (“self-reference”) is an enormous stumbling block and plenty of students do not get it at all, and functional programming is just completely inaccessible to them. By this measure alone, I’m tempted to say that you’re ahead of the average college student already.
There are countless stories floating around about CS graduates who can’t write code, and there are also a lot of stories of people who taught themselves, skipped college, and got a good job. Lack of a degree may be a hindrance if your dream is to write Java code in cubicle #49873 at BigCorp, but the more interesting companies (incl. Google) are more interested in competency than pieces of paper.
Wow. What a perceptive, well written, observant and thorough commentary. There I was expecting some sickly sweet piece of sychophancy but having read bits of your blog before I had an inkling it would be worth reading and you didn’t disappoint.
Having been through the experience (albeit less thoroughly than you) I have little to add but I read with interest your comparative remarks about Odersky’s Scala course.
Very astute observations (well I would say that because I agree). I feel Odersky is not the right person to teach that course. He strikes me as more a creator than an educator and with one particular exception his T.A’s did not exhibit the requisite level of emotional intelligence. Unfortunately because he has a cult following constructive and correct criticisms of his course is curtailed.
A couple of things I’ll add. I think one of the most powerful techniques to teach this course is the use of inventory and outventory templates with examples. This is excellently exposited in Stephen Bloch’s Picturing Programs and I don’t recall (must be careful because I wasn’t always paying full attention) seeing much of it here.
I also believe the peer grading criteria for Project 1 led to rigid interpretations and over did the de-emphasis of a correctly working program. I am glad we are not going to have to repeat that in project 2. I would also like to have seen a stronger connection with roots and the origins of where the recipe came from. Very little is new in CS and as Eric Mejier says it is a discipline that likes to forget it’s history.
Pingback: Backtracking Search in Python with Four Queens | Gregor Ulm
Pingback: Introduction to Systematic Program Design – Part One | Memecoder
Hi Gregor,
Enjoyed your analysis. I am currently taking the Coursera course right now.
What did you think of the How To Design Programs 2e textbook? Is it worth going through if one is taking the Coursera course?
Cheers,
Carl
You mean you’re going through the archived materials on edX, which nowadays offers that course? Introduction to Systematic Program Design is no longer listed on Coursera. It seems that the University of British Columbia has renounced their cooperation with Coursera altogether.
I had a look at that textbook many years ago. Frankly, as I wrote in the article, the pace of it is excruciatingly slow. It seems to be aimed at novices without any technical background. Do you struggle with the pace of the MOOC? If so, then maybe get HtDP. Otherwise, don’t bother with it.
Just after I made my comment they removed the Coursera course! Yes, the first half of the course is on edX and all of the videos are on YouTube for now until the second half is on edX as well.
So far I’m sticking to the UBC material, thanks for the tip on the book.
I have to say now that I am into accumulators and more advanced mutual recursive traversals through binary trees I am finding it a lot tough to solve a couple of the problems myself without a little help (the Harry Potter wizard descendant worklist accumulator problem comes to mind). It’s forcing me to slow down, draw out the trees, and try to work through them step by step and forgo trying to tackle it mentally (deep recursion doesn’t seem to bode well with that method) in one shot which is probably a good thing in general for my modus operandi.
Overall the course has definitely picked up and I am enjoying it much more than I was at the beginning. Did you have any similar issues with regard to working through the more complex problems in the course?
I didn’t find the Coursera course particularly challenging. If you get stuck, then don’t be afraid of asking questions in the course forum.
Thanks Gregor.
After further practice and now being able to recognize the recursive patterns for worklist and results-so-far accumulators the problems are now much, much easier.
I have also been working on my problem solving style and reading a book called Pragmatic Thinking and Learning which has been great so far as well.
Cheers!
Carl
Hi Gregor — Thanks for your great comments. The irony of various “software architects” telling Gregor Kiczales (who has contributed as much as anyone to program design in software engineering) was probably lost on many. Kiczales did a fantastic job with the MOOC and it’s great to read about people who have benefited from it.
You may also want to take a look at the second edition of HtDP [http://www.ccs.neu.edu/home/matthias/HtDP2e/]. It is much less slow-paced, and begins with our new approach to animations and reactive programming, which many might find enlightening. To some extent, starting with something more weighty like a game also helps quell some of the pointless discussion that otherwise (sadly) sidetracks such courses.
For some insight on the origins of the design recipe, see
http://www.ccs.neu.edu/racket/pubs/#jfp2004-fffk
Otherwise read the preface of the two editions for some more details.
“I had a look at [HtDP] many years ago. Frankly, as I wrote in the article, the pace of it is excruciatingly slow. It seems to be aimed at novices without any technical background.”
Absolutely: it was written for a first programming course in high school or college, not for experienced programmers. That said, if you’re motivated and can temporarily put yourself into a “beginner’s mind”, even an experienced programmer (particularly from an imperative/OO paradigm) will learn useful things from it.
“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.”
Absolutely, and intentionally. For a number of years I taught college non-majors, many of whom were mathophobic — their palms would break out in a sweat when they saw a minus sign — and I had that audience (or a general high school audience) in mind when I wrote Picturing Programs. Any time I had a choice between doing something with numbers and doing something equally easy with images, I picked images. As a result, students going through my book are writing event-driven interactive video-games with model-view separation, and following the design recipe to write and test each function, before they ever see an arithmetic operator. That’s intentional, to get them hooked on programming before they get terrified by “math” (i.e. arithmetic).