One reason that I started this blog was to record my experiences with a new course on functional programming for freshmen at Carnegie Mellon. Classes have ended, the final exam is graded, and we are in the process of taking stock of what we accomplished, and what we could do better. This was the first instance of the course, taught to 83 first-year computer science students who volunteered to be part of the new curriculum. (This represents about 2/3 of the freshman class.) All had taken a new course on imperative programming taught by Frank Pfenning the previous semester, and all were simultaneously taking 251, the legendary theory foundation course developed here over the last dozen or so years.

Starting this fall the course will be part of the standard curriculum, and will be taught to a broader range of students, including the electrical engineers and the full class of CS students. We’re still working out whether the standard order will be imperative, then functional, or functional, then imperative. Much depends on the mathematical maturity of the incoming students. Those with weak mathematical skills (the vast majority), but some programming experience, will likely start with imperative programming, which they will take simultaneously with a standard discrete math course taught in the mathematics department. Those with strong mathematical skills, or high ambitions, will start with functional programming. A small number will park for one semester, taking discrete math and a programming course primarily intended for non-majors, to bring themselves up to speed.

Our new data structures and algorithms course, being developed by Guy Blelloch, will be offered in the fall for students who have already have the IP and FP classes. Guy plans to make heavy use of functional programming, and will be stressing parallel algorithms on persistent data structures as the common case, leaving the traditional sequential, ephemeral case to the imperative programming class. Guy’s course is essentially a continuation (ahem) of the FP class that emphasizes more sophisticated data structures and algorithms, and more complex programming problems.

For those who might be interested, I’m attaching the final exam for the course. The students did exceptionally well (average score of 88%), even though we feared it was too long and difficult beforehand. The spread was very narrow, perhaps because the exam was too easy, or because this being a class of volunteers, their skills were unusually strong and uniform. We’ll know more after the fall once we’ve taught the class to a broader range of students. I do think the exam is representative of what we expected them to be able to do at the end, and they showed us that they can do it. A clear success!

15-150 Final Exam (Spring 2011)

Re: functional programming first

At Northeastern, our freshmen take functional programming (out of HtDP). We follow this up with a course called “Logic and Computation” where we make them prove properties of programs using ACL2. This seems to work well.

Yes, I was emboldened by Northeastern’s success to move us from the quagmire of object nonsense into the modern world. Thanks for helping show the way!

You may not like to know that I failed to get HtDP adopted for our non-majors course, mostly because I can’t single-handedly do everything. For now it’s teaching ugly methods using python, but maybe one day we can update that course too.

If the staff were wearing their shirts, I hope that nobody got 1(a) wrong!

Dave Eckhardt gave an anecdote once of when he was teaching networks, in which there was a question on the midterm that completely wrecked about half the class. I can’t remember with whom he was co-teaching it, but his co-instructor recommended assigning

the same questionon the final — and to make it even more fun, mentioning in class that they would do this.Well, they did; surprisingly to them, everyone got wrecked on the same question on the final

still. Hopefully the t-shirts hammered it home, though…Regardless, I skimmed the exam, and that is difficult to be sure; so it is especially commendable that your class got an average of 88%.

I look forward to seeing what happens next semester, and in particular, how this helps reshape the ECE curriculum. I suspect that a lot of ECE students who take 18-240 after taking 150 may begin to think about hardware description languages in a truly different light; I hope that the ECE instructors can build on the skills that the students learn in 150, rather than simply ignoring them and plodding down the same old path.

If you’d like, I would be curious to hear the rationale for delaying functional programming for “mathematically immature” students. I would think that learning FP would be a good motivator for students who, so far, haven’t figured out quite what the point of math is. I learned functional programming when I hadn’t taken any math beyond pre-calculus (hadn’t taken a discrete math class yet, in particular), and it made perfect sense to me. (I did learn an imperative language first, but I don’t think it was at all necessary.)

Besides a general way of thinking, is there anything in particular from a discrete math class that you think is crucial for someone simultaneously learning programming and functional programming for the first time?

A very good question. What we’re looking for is some understanding of what is a theorem and what is a proof. Many students don’t have the sense of what a proof looks like, or how to go about writing one, or how to judge when a proof is solid and when it is shakey. We rely on essentially nothing from discrete math per se, just on mathematical maturity. It’s a tall order for a student who is not comfortable with the basic principles of mathematical expression to learn that as well as learn functional programming. I believe that the two topics are uniquely synergistic, but it helps if the student has some “real math” experience, which sadly is not the norm in American high schools these days.

In the future I plan to create a freshman course on the mathematical vernacular, a kind of “freshman composition” class focusing on mathematical expression, and not on mathematical content. So my goal would not be to teach them to solve problems (that comes in 251), but rather in how to state things clearly, what a mathematician means when she says “choose x arbitrarily, then ….” or “without loss of generality, …” or similar such phrases that confuse students. My idea is that once they learn the “rules of grammar”, then they can concentrate on problem-solving and programming.

Does this mean we should expect fewer or less frequent posts?

That would be sad if it is the case.

I plan to write about some current research interests. Next up, higher-dimensional type theory.