Functional Programming and the ACM Curriculum

In May 2008, ACM SIGPLAN organized a workshop on Undergraduate Programming Language Curricula. One of the outcomes of this workshop was a proposal to put functional programming in the ACM core curriculum. This was Stuart Reges's brainchild, and Matthias Felleisen and I worked with him on it. We were very pleased to accomplish this in a “zero footprint” fashion.

Of course, this has earned a little (but surprisingly little) sniping from the vasty deep that is the Internet. Stuart and I wrote some prose not only explaining how we planned to accomplish the zero-footprint but, even more importantly, why this material belongs there. It should be useful reading for people who are stuck in the old-fashioned trap of “paradigms” (more on that later).

Because I don't know what will happen to this prose when it's incorporated into the final report from the workshop, I'm posting the original version of it here. If you're stuck in a discussion about this change, feel free to refer to this.

NB: This is co-authored with Stuart Reges, and inspired by some text from Larry Snyder, who both seem to have more sense than to have blogs of their own.

---

Rationale for the Change to the CS2001 Curriculum

The proposed change has the following structure:

Knowledge Unit                       Current Proposed
-----------------------------------------------------
PF4  Recursion                           5       2
PF5  Event-driven programming            4       2

PL1  Overview of PL                      2       0
PL2  Virtual Machines                    1       0
PL3  Language Translation                2       0
PL6  Object-oriented programming        10      10
PL7  Functional Programming              0      10
                                        --      --
     Total                              24      24

The changes have two key design goals:

1. To make the functional programming unit (FP), currently listed as PL7 in the curriculum, required rather than optional.
2. To account for this change in a "budget-neutral" way.

First we describe the high-level motivation for this change.

• Functional programming is not merely about a change in syntax; rather, it forces students to approach problems in a novel way. This increases their mental agility and prepares students for a life of practice in a world where languages continuously grow, morph, and sometimes shift their perspective. This is not just the academic community speaking: this advice comes from influential industrial practitioners including Joel Spolsky, Steve Yegge, Paul Graham, Eric Raymond, and Peter Norvig, who have all written vocally about it.
• The growth and change of languages, and the influence of functional programming, is not hypothetical. Virtually every significant mainstream language that has been designed, has gained prominence, or has been improved in the past decade, from JavaScript to Ruby to Java to C# to Visual Basic, incorporates notable features that used to be associated with functional programming. Datacenter programming techniques such as MapReduce grow directly out of functional programming. Microsoft has championed the use of functional constructs like closures in the .NET framework as the best way to express database and XML queries. The rise of multicore architectures is imposing new pressures on programmers to avoid the use of shared state whenever possible. Learning functional programming takes students directly to the source, without the overhead and pain of sometimes unwieldy encodings of these ideas.
• By exposing students to multiple languages before they graduate, we make a strong statement about what they can expect to see in practice. History shows that the dominant programming language changes roughly every seven years, and over two or three of these changes little stays the same other than syntax. Furthermore, modern systems are rarely built in a single language alone; developers find it advantageous, and sometimes necessary, to use a combination of languages of widely different styles. Therefore, exposing students to a variety of styles is an essential part of their education.

Below we discuss the rationale for changes to specific knowledge units.

• The topics in PF4 (Recursion) and PF5 (Event-driven programming) lend themselves naturally to coverage in both object-oriented and functional programming. Functional programming has traditionally made paradigmatic use of recursion, while the callbacks that guide event-driven programming are a natural fit when discussing closures. Furthermore, by seeing these topics in both contexts, students will be in a better position to compare and contrast their expression in different styles.
• The topics in PL1 (Overview of programming languages), PL2 (Virtual machines) and PL3 (Language translation) are important topics, but we find it difficult to say much of use within this little time. The result is an enumeration of jargon without any deep study of concepts. Students will be better served by a substantial exposure to a functional language that serves as a contrast to whatever object-oriented language they will also learn. This experience of learning two different languages is more important than a superficial coverage of these other PL topics.
• One of our major goals is to bring parity between the number of hours devoted to PL6 (Object-oriented programming) and PL7 (Functional programming) by requiring a substantial experience with each approach.

It is worth noting that the proposal is neutral about implementation. Some schools will choose to incorporate functional programming into their introductory sequence. Other schools might include it in an advanced programming course or a discrete structures course. And other schools will fit this into a required programming languages course.

NNTR / NN2R

Mitch Wand pointed me to this article by an email veteran bemoaning what has become of the medium. Obviously, I concur.

One annoying type of message that continues to throw me off my game is those brief “okay” and “thank you” messages, especially from staff. I've been getting increasingly good at anticipating these and affixing NNTR or NN2R to my preceding message. Amazingly, both the former and the latter are indexed in Web dictionaries, which makes me wonder why people don't use them more. [That's “No Need To Reply”, natch, not a Myers-Briggs indicator, though it might as well be.]

Anyway, I do, and I encourage you to as well.

Meanwhile, you ask, what do you do? I'm afraid I still send those replies to staff members, because I think it's just basic etiquette (though many a misplaced good intention has been born there...). I'd like to ask them someday whether they'd be offended if I stopped doing this and instead used that old classic from the days of Usenet: TIA (that's “Thanks in Advance”, for you wee ones).

Animal Instinct

After years of dealing with a pair of unpolarized shades with optical inserts, an ugly, ungainly, heavy combination, I finally decided to splurge on a pair of custom Oakleys. For the price of a small principality, they will create prescription lenses—not inserts, lenses!—that fit the frame of your choice. Of course, my optician was taking care of all the easy and technical parts (like the prescription); the awesome burden of designing the actual glasses fell to me. Oakley's site has a bewildering set of models, all poorly differentiated, each of which has umpteen customization options. Yee haw!

“These glasses will make you two miles an hour faster!”, my optician had said. Surely the glasses alone were just the beginning of the gains. The right color scheme, I was sure, would only enhance the effect. So I spent a night at it. What, I thought, spelled a combination of speed and stamina better than a zebra? I already have Cinelli cork zebra bar tape—a tribute to the great zebra train of Mario Cipollini, which represents everything that is ridiculously over-the-top about cycling—and this would be the perfect match.

In the morning, I was pottering around pouring cereal as Kathi came by. “I designed my new shades last night!” She responded encouragingly. “Guess the color scheme!” She gamely tried a few lackadaisical options, then confessed ignorance. I paused for effect. “Zebra!”, I proclaimed. Her reaction was a little too stable. “Want to see it?”, I only half-asked, bouncing off in the direction of the monitor.

“Oh, cute! A cow!”

Now would be a good time to point out that later in the week, she confessed to needing to update her prescription. I'm just sayin', is all.

Anyway, the shades are here. They're terrific. In my mind, a zebra is what they will always be. Though I could have sworn I heard a moo as I was waging war with the wind on Blackstone Boulevard earlier this evening.

The Functional Functionary

L.K. Advani is pretty close to my least favorite Indian politician, even after his recent softening. Who would have thought I could find common cause with such a man? And yet, this image, embedded in this article in The Economist, shows him sitting pensively while looming over his left shoulder is...a great big lambda!

It looks a lot closer to the (ugly) Haskell lambda than the (elegant) PLT Scheme lambda. It figures that Advani would have poor taste, and would pick a fundamentalist language.

Major Faux Pas

Life was tougher a hundred years ago, and tougher still in the face of open discrimination. Yet while people like Jackie Robinson are celebrated across the US, an earlier pioneer, Major Taylor, the first black cycling world champion, has been entirely forgotten.

Or would be, if a band of enthusiasts didn't have their way. But this group has kept his memory alive, and just under a month ago crossed a milestone: a statue of Major Taylor now stands outside the public library in Worcester, MA, a city where Taylor lived for much of his active life.

I wasn't there for the statue per se—I find most of these civic monuments uniformly ghastly—but to support Lynn Tolman, who has been the most visible member of this tireless group. They did have two headliners attend the event, Greg Lemond and Edwin Moses, and I figured they might have something interesting to say. In the end, things came out backwards. The statue is quite superb:

Moses was interesting enough, while Lemond continued to embarrass himself and those listening to him. It's one thing for Lemond to declaim about drugs in the sport: he knows something about life in the peloton in a way that the rest of us never will. (It doesn't help that he has become a kind of confidant-in-chief for suspect riders.) But at an event like this—which he knew about well in advance—he not only rambled without continuity or coherence part of the time but, worse, didn't so for the rest. When he wasn't rambling, he was telling us about how terrible a time he had had as a young American in Europe, and somehow linked his own tribulations (immense though they were) to Taylor's (which were unimaginably greater). In the end, one felt pity for Lemond and an even greater sense of Taylor's accomplishment.

So, no photograph of self-promoting celebrities. Here's Tolman during her pleasant and modest address:

Average Intelligence

We were at the doctor's yesterday, and a counselor sat us down to discuss some numbers. Even as I girded myself for the usual array of bewildering physical units, the counselor told us that the array numbers—which all looked surprisingly close to 1—were all in terms of MoMs: multiple of the median. Unitless: perfect.

Most of the numbers looked just right, but one or two were a bit off, so I asked what we should understand by an entry with a MoM value of close to two. Her response: “Oh, that just means its twice the average”. I tried to clarify the distinction, until it became clear that she simply thought “median” meant “average”.

And we paid for this service.

Why Spam Will Improve English

As spam increasingly relies on misspellings, poor grammar, and poor punctuation to penetrate our defenses (one of today's message headers: “run don't walk to yuor broker” [sic]), the only email that will get through any longer will have to be perfect.

Footprint-Neutral Curricular Change

Last wee we had a SIGPLAN-sponsored workshop on programming languages education. Most of the usual luminaries, and people like me, attended. One of the outcomes—what, in fact, I think may be our most significant outcome—was a suggestion to rearrange some hours in the core ACM curriculum. You can find the details of that proposal here.

If at think this is at all a good idea (and you should), please post a comment to that effect. Yes, it'll take an extra minute of your time because you'll have to log in, which will involve remembering your ACM user ID (which you have long forgotten), but believe me, it'll be worth your time.

Third Time Still a Charm: Guston's Drawings

Inspired by my previous successes following The Economist's art recommendations, I spent a good part of today at the Morgan Library & Museum in NYC for their exhibition of drawings by Philip Guston. I had only loosely heard of Guston as an abstract expressionist, so normally I would never have taken the trouble to attend such an exhibition. But the article was persuasive, and I'm glad it was.

After a career of abstract expressionism (and protesting pop art), Guston underwent a crisis in the mid-1960s. Saying, for instance, “I like old-fashioned things like gravity”, Guston began to paint objects in the world around him. This was not, however, a return from the abstract to the concrete so much as a view of the concrete through eyes of abstraction. Some of his earliest paintings in this phase—just a few black brushstrokes on white paper, really—are stunning, such as 1967's Air or Wave II, which is simply an overlapping cascade running eccentrically down the paper. The books he paints become indistinguishable from skyscrapers, gravitas united with gravity.

Then, in 1970s, he finally cuts loose. A flood of drawings, first of caricatured Klansmen and then of boots and books and cobwebs and cherries and the rest of the trash of existence, give his work both a comic-like absurdity and a weight and feeling of urgency as he rushes to pump out his emotions. Some of his most wonderful, color drawings were executed in the very year of his death.

It would be pat to say Guston balanced the literal and the metaphorical, the abstract and the concrete, with ease—pat, and wrong. Instead he struggled with them, and put his struggles on paper. Thus on the one hand he was able to say,

The visible world, I think, is abstract and mysterious enough... Also there was a desire, a powerful desire though an impossibility, to paint things as if one had never seen them before, as if one had come from another planet.

like he painted his books. But he also arrested himself from returning to his earlier phase as an architecture astronaut:

Sometimes when my painting is becoming too artistic, I'll say to myself, ‘What if the shoe salesman asked you to paint a shoe on his window?’

If the salesman had asked, he would have received a cartoon showing the metaphorical weight of the world being fitted to a size 9.

Oops!... I Did It Again

Recently I wrote about my experience running into an art exhibition in New York that I'd learned about thanks to The Economist. Continuing my trend of being a man about town, I've done it again.

I had given myself over a day of free time in London to see Brilliant Women, a collection of portraits of 18th-Century Bluestockings. But I met so many people at Imperial College—and so enjoyed my time there—that I simply never got to the National Portait Gallery. The Imperial folks had also kept me from paying homage at Foyles, so my schedule was looking rather dire. Fortunately I had booked to fly on one of the new late-afternoon flights out of Heathrow (thank you, Open Skies!), so I had a little time in the morning. Foyles opens at 9:30, the NPG at 10:00, and the former is just up Charing Cross from the latter. Still, it was a close-run thing.

The exhibition (which runs for another week, as of this writing) was worth the manic tour of the Piccadilly Line, the second time The Economist's art critic (was it the same one?) has come through for me. The NPG has some of the best captions of art anywhere (well, at least if you read English), and this exhibition was in the same vein. But there were also letters and assorted memorabilia.

Two gems. There is Katherine Read's portrait of Elizabeth Carter, and it is praised as “quite unlike the common run of staring portraits”. And a young Mary Wollstonecraft, just a year or two shy of breaking out into the limelight, is sucking up to Catherine Macaulay in a letter on December 16, 1790:

I respect M^rs Macaulay Graham because she contends for laurels whilst most of her sex only seek for flowers.

If you find yourself in the vinicity, run.