Knowing and Doing

The recent rescue of hostages in Colombia relied on a strategy familiar to people interested in computer network security: a man-in-the-middle attack.

... for months, in an operation one army officer likened to a "broken telephone," military intelligence had been able to convince Ms. Betancourt's captor, Gerardo Aguilar, a guerrilla known as "Cesar," that he was communicating with his top bosses in the guerrillas' seven-man secretariat. Army intelligence convinced top guerrilla leaders that they were talking to Cesar. In reality, both were talking to army intelligence.

As Bruce Schneier reports in Wired magazine, this strategy is well-known on the internet, both to would-be system crackers and to security experts. The risk of man-in-the-middle attacks is heightened on-line because the primary safeguard against them -- shared social context -- is so often lacking. Schneier describes some of the technical methods available for reducing the risk of such attacks, but his tone is subdued... Even when people have a protection mechanism available, as they do in SSL, they usually don't take advantage of it. Why? Using the mechanism requires work, and most of us are just too lazy.

Then again, the probability of being victimized by a man-in-the-middle attack may be small enough that many of us can rationalize that the cost is greater than the benefit. That is a convenient thought, until we are victimized!

The problem feature that makes man-in-the-middle attacks possible is unjustified trust. This is not a feature of particular technical systems, but of any social system that relies on mediated communication. One of the neat things about the Colombian hostage story it that shows that some of the problems we study in computer science are relevant in a wider context, and that some of our technical solutions can be relevant, too. A little computer science can amplify the problem solving of almost anyone who deals with "systems", whatever their components.

This story shows a potential influence from computing on the wider world. Just so that you know the relationship runs both ways, I point you to Joshua Kerievsky's announcement of "Programming with the Stars", one of the events on the Developer Jam stage at the upcoming Agile 2008 conference. Programming with the Stars adapts the successful formula of Dancing with the Stars, a hit television show, to the world of programming. On the TV show, non-dancers of renown from other popular disciplines pair with professional dancers for a weekly dance competitions. Programming with the Stars will work similarly, only with (pair) programming plugged in for dancing. Rather than competitions involving samba or tango, the competitions will be in categories such as test-driven development of new code and refactoring a code base.

As in the show, each pair will include an expert and a non-expert, and there will be a panel of three judges:

• Rachel Davies
• Uncle Bob Martin
• Crazy Mike Hill

I've already mentioned Uncle Bob in this blog, even in a humorous vein, and I envision him playing the role of Simon Cowell from "American Idol". How Davies and Hill compare to Paula Abdul and Randy Jackson, I don't know. But I expect plenty of sarcasm, gushing praise, and hip lingo from the panel, dog.

Computer scientists and software developers can draw inspiration from pop culture and have a little fun along the way. Just don't forget that the ideas we play with are real and serious. Ask those rescued hostages.

I've been trying to take a break from the office and spend some time at home and with my family. Still, I enjoy finding time to read an occasional technical article and be inspired. While waiting for my daughter's play rehearsal to end last night, I read A Conversation with Christos Papadimitriou, a short interview in the August 2008 of Dr. Dobb's Journal. I first learned of Papadimitriou from a textbook of his that we used in one of my earliest graduate course, Elements of the Theory of Computation. Since that time, he has done groundbreaking work in computational complexity and algorithms, with applications in game theory, economics, networks, and most recently bioinformatics. It seems that many of the best theoreticians have a knack for grounding their research in problems that matter.

The article includes several tidbits that might interest computer scientists and professional programmers of various sorts. Some are pretty far afield from my work. For instance, Papadimitriou and two of his students recently produced an important result related to the Nash Equilibrium in game theory (have you seen A Beautiful Mind?) Nash's theorem tells us that an equilibrium exists in every game, but it does not tell us how to find the equilibrium. Is it possible to produce a tractable algorithm for finding it? Papadimitriou and his students showed that Nash's theorem depends intrinsically on the theorem which is the basis of Nash's proof, which means that, in practice, we cannot produce such an algorithm; finding the Nash equilibrium for any given problem is intractable.

The interview spent considerable time discussing Papadimitriou's recent work related to the Internet and the Web, which are ideas I will likely read more about. Papadimitriou sees the net as an unusual opportunity for computer scientists: a chance to study a computational artifact we didn't design. Unlike our hardware and software systems, it "emerged from an interaction of millions of entities on the basis of deliberately simple protocols". The result is a "mystery" that our designed artifacts can't offer. For a theoretical CS guy, the net and web serve as a research lab of unprecedented size.

It also offers a platform for research at the intersection of computing and other disciplines, such as communication, where my CS grad student Sergei Golitsinski is taking his research. The interviewer quoted net pioneer John Gilmore in the same arena: "The Net interprets censorship as damage and routes around it." This leads to open questions about how rumors spread, an area that Papadimitriou calls "information epidemiology". One of my former grad students, Nate Labelle, worked in this area for a particular part of the designed world, open-source software packages, and I'd love to have a student delve into the epidemiology of more generalized information.

I would also like to read Papadimitriou's novel, Turing. I recall when it came out and just haven't gotten around to asking my library to pick it up or borrow it. In the interview, Papadimitriou said,

I discovered this [novel] was inside me and had to come out, so I took time to write it. I couldn't resist it. ... If I had not done it, I would be a less happy man.

Powerful testimony, and the chance to read CS-themed fiction doesn't come along every day.

After reading Lockhart, I read Matthias Felleisen's response to Lockhart, and from there I read Matthias's design for a second course to follow How to Design Programs. From an unlinked reference there, I finally found A Critique of Abelson and Sussman, also known as "Why Calculating Is Better Than Scheming" (and also available from the ACM Digital Library). I'm not sure why I'd never run into this old paper before; it appeared in a 1987 issue of the SIGPLAN Notices. In any case, I am glad I did now, because it offers some neat insights on teaching introductory programming. Some of you may recall its author, Philip Wadler, from his appearance in this blog as Lambda Man a couple of OOPSLAs ago.

In this paper, Wadler argues that Structure and Interpretation of Computer Programs, which I have lauded as one of the great CS books, could be improved as a vehicle for teaching introductory programming by using a language other than Scheme. In particular, he thinks that four particular language features are helpful, if not essential:

• pattern matching
• a more mathematics-like syntax
• types, both static and user-defined
• lazy evaluation

Read the paper for an excellent discussion of each, but I will summarize. Pattern matching pulls syntax of many decisions out of a single function and creates separate expressions for each. This is similar to writing separate functions for each case, and in some ways resembles function overloading in languages such as Java and C++. A syntax more like traditional math notation is handy when teaching students to derive expressions and to reason about values and correctness. Static typing requires code to state clearly the kinds of objects it manipulates, which eliminates a source of confusion for students. Finally, lazy evaluation allows programs to express meaningful ideas in a natural way without having the language enforce conclusions that are not strictly necessary. This can be also be useful when doing derivation and proof, but it also opens the door to some cool applications, such as infinite streams.

We teach functional programming and use some of these concepts in a junior-/senior-level programming languages course, where many of Wadler's concerns are less of an issue. (They do come into play with a few students, hough; Wadler might say we wouldn't have these problems if we taught our intro course differently!) But for freshmen, the smallest possibilities of confusion become major confusions. Wadler offers a convincing argument for his points, so much so that Felleisen, a Scheme guy throughout, has applied many of these suggestions in the TeachScheme! project. Rather than switching to a different language, the TeachScheme! team chose to simplify Scheme through a series of "teaching languages" that expose concepts and syntax just-in-time.

If you want evidence that Wadler is describing a very different way to teach introductory programming, consider this from the end of Section 4.1:

I would argue that the value of lazy evaluation outweighs the value of being able to teach assignment in the first course. Indeed, I believe there is great value in delaying the introduction of assignment until after the first course.

The assignment statement is like mom and apple pie in most university CS1 courses! The typical CS faculty could hardly conceive of an intro course without assignment. Abelson and Sussman recognized that assignment need not be introduced so early by waiting until the middle of SICP to use set. But for most computer scientists and CS faculty, postponing assignment would require a Kuhn-like paradigm shift.

Advocates of OOP in CS1 encountered this problem when they tried to do real OOP in the first course. Consider the excellent Object-Oriented Programming in Pascal: A Graphical Approach, which waiting until the middle of the first course to introduce if-statements. From the reaction of most faculty I know, you would have thought that Conner, Niguidula, and van Dam were asking people to throw away The Ten Commandments. Few universities adopted the text despite its being a wonderful and clear introduction to programming in an object-oriented style. As my last post noted, OOP causes us to think differently, and if the faculty can't make the jump in CS1 then students won't -- even if the students could.

(There is an interesting connection between the Conner, Niguidula, and van Dam approach and Wadler's ideas. The former postpones explicit decision structures in code by distributing them across objects with different behavior. The latter postpones explicit decision structures by distributing them across separate cases in the code, which look like overloaded function definitions. I wonder if CS faculty would be more open to waiting on if-statements through pattern matching than they were through the dynamic polymorphism of OOP?)

Wadler indicates early on that his suggestions do not presuppose functional programming except perhaps for lazy evaluation. Yet his suggestions are not likely to have a wide effect on CS1 in the United States any time soon, because even if they were implemented in a course using an imperative language, most schools simply don't teach CS1 in a way compatible with these ideas. Still, we would be wise to take them to heart, as Felleisen did, and use them where possible to help us make our courses better.

Most papers presented at SIGCSE and the OOPSLA Educators' Symposium are about teaching methods, not computational methods. When the papers do contain new technical content, it's usually content that isn't really new, just new to the audience or to mainstream use in the classroom. The most prominent example of the latter that comes to mind immediately is the series of papers by Zung Nguyen and Stephen Wong at SIGCSE on design patterns for data structures. Those papers were valuable in principle because they showed that how one conceives of containers changes when one is working with objects. In practice, they sometimes missed their mark because they were so complex that many teachers in the audience said, "Cool! But I can't do that in class."

However, the OOPSLA Educators' Symposium this year received a submission with a cool object-oriented implementation of a common introductory programming topic. Unfortunately, it may not have made the cut for inclusion based on some technical concerns of the committee. Even so, I was so happy to see this paper and to play with the implementation a little on the side! It reminded me of one of the first efforts I saw in a mainstream CS book to show how we think differently about a problem we all know and love when working with objects. That was Tim Budd's implementation of the venerable eight queens problem in An Introduction to Object-Oriented Programming.

Rather than implement the typical procedural algorithm in an object-oriented language, Budd created a solution that allowed each queen to solve the problem for herself by doing some local computation and communicating with the queen to her right. I remember first studying his code to understand how it worked and then showing it to colleagues. Most of them just said, "Huh?" Changing how we think is hard, especially when we already have a perfectly satisfactory solution for the problem in mind. You have to want to get it, and then work until you do.

You can still find Budd's code from the "download area" link on the textbook's page, though you might find a more palatable version in the download area for the book's second edition. I just spent a few minutes creating a Ruby version, which you are welcome to. It is slightly Ruby-ized but mostly follows Budd's solution for now. (Note to self: have fun this weekend refactoring that code!)

Another thing I liked about "An Introduction to Object-Oriented Programming" was its linguistic ecumenism. All examples were given in four languages: Object Pascal, C++, Objective C, and Smalltalk. The reader could learn OOP without tying it to a single language, and Budd could point out subtle differences in how the languages worked. I was already a Smalltalk programmer and used this book as a way to learn some Objective C, a skill which has been useful again this decade.

(Budd's second edition was a step forward in one respect, by adding Java to the roster of languages. But it was also the beginning of the end. Java soon became so popular that the next version of his book used Java only. It was still a good book for its time, but it lost some of its value when it became monolingual.)

Last week I wrote about an essay by Paul Lockhart from a few years ago that has been making the rounds this year. Lockhart lamented that math is so poorly misrepresented in our schools that students grow up missing out on its beauty, and even still not being able to perform the skills in whose name we have killed scholastic math. I've long claimed that we would produce more skilled students if we allowed them to approach these skills from the angle of engaging problems. For Lockhart, such problems come form the minds of students themselves and may have no connection to the "real world".

In computer science, I think letting students create their own problems is also quite valuable. It's one of the reasons that open-ended project courses and independent undergraduate research so often lead to an amazing level of learning. When a group of students wants to train a checkers-playing program to learn from scratch, they'll figure out ways to do it. Along the way, they learn a ton -- some of it material I would have selected for them, some beyond what I would have guessed.

The problems CS students create for themselves often do come straight out of their real world, and that's okay, too. Many of us CS love abstract problems such as the why of Y, but for most of us -- even the academics who make a living in the abstractions -- came to computing from concrete problems. I think I was this way, starting when I learned Basic in high school and wanted to make things, like crosstables for chess tournaments and ratings for the players in our club. From there, it wasn't that far a journey into Gödel, Escher, Bach and grad school! Along the way, I had professors and friends who introduced me to a world much larger than the one in which I wrote programs to print pages on which to record chess games.

This is one reason that I tout Owen Astrachan's problem-based learning project for CS. Owen is interested in problems that come from the real world, outside the minds of the crazy but harmless computer scientists he and I know, love, and are. These are the problems that matter to other people, which is good for the long-term prospects of our discipline and great for hooking the minds of kids on the beauty and power of computing. For computer science students, I am a proponent of courses built around projects, because they are big enough to matter to CS students and big enough to teach them lessons they can't learn working on smaller pieces of code.

With an orientation toward the ground, discussions of functional programming versus object-oriented programming seem almost not to matter. Students can solve any problem in either style, right? So who cares? Well, those of us who teach CS care, and our students should, too, but it's important to remember that this is an inward-looking discussion that won't mean much to people outside of CS. It also won't matter much to our students as they first begin to study computer science, so we can't turn our first-year courses into battlegrounds of ideology. We need to be sure that, whatever style we choose to teach first, we teach it in a way that helps students solve problems -- and create the problems that interest them. They style needs to feel right for the kind of problems we expose them to, so that the students can begin to think naturally about computational solutions.

In my department we have for more than a decade introduced functional programming as a style in our programming languages course, after students have seen OOP and procedural programming. I see a lot of benefit in teaching FP sooner, but that's would not fit our faculty all that well. (The students would probably be fine!) Functional programming has a natural home in our languages course, where we teach it as an especially handy way of thinking about how programming languages work. This is a set of topics we want students to learn anyway, so we are able to introduce and practice a new style in the context of essential content, such as how local variables work and how to write a parser. If a few students pick up on some of the beautiful ideas and go do something crazy, like fire up a Haskell interpreter and try to grok monads, well, that's just fine.

So no, I'm not complaining about the presence
of facts and formulas in our mathematics classes,
I'm complaining about the lack of mathematics
in our mathematics classes.
-- Paul Lockhart

A week or so ago I mentioned reading a paper called A Mathematician's Lament by Paul Lockhart and said I'd write more on it later. Yesterday's post, which touched on the topic of teaching what is useful reminded me of Lockhart, a mathematician who stakes out a position that is at once diametrically opposed to the notion of teaching what is useful about math and yet grounded in a way that our K-12 math curriculum is not. This topic is especially salient for me right now because our state is these days devoting some effort to the reform of math and science education, and my university and college are playing a leading role in the initiative.

Lockhart's lament is not that we teach mathematics poorly in our K-12 schools, but rather that we don't teach mathematics at all. We teach definitions, rules, and formal systems that have been distilled away from any interesting context, in the name of teaching students skills that will be useful later. What students do in school is not what mathematicians do, and that's a shame, because mathematicians is fun, creative, beautiful -- art.

As Lockhart described his nightmare of music students not being allowed to create or even play music, having to copy and transpose sheet music, I cringed, because I recognized how much of our introductory CS courses work. As he talked about how elementary and HS students never get to "hear the music" in mathematics, I thought of Brian Greene's Put a Little Science in Your Life, which laments the same problem in science education. How have we managed to kill all that is beautiful in these wonderful ideas -- these powerful and even useful ideas -- in the name of teaching useful skills? So sad.

Lockhart sets out an extreme stance. Make math optional. Don't worry about any particular content, or the order of topics, or any particular skills.

Mathematics is the music of reason. To do mathematics is to engage in an act of discovery and conjecture, intuition and inspiration; to be in a state of confusion--not because it makes no sense to you, but because you gave it sense and you still don't understand what your creation is up to; to have a breakthrough idea; to be frustrated as an artist; to be awed and overwhelmed by an almost painful beauty; to be alive, damn it.

I teach computer science, and this poetic sense resonates with me. I feel these emotions about programs all the time!

In the end, Lockhart admits that his position is extreme, that the pendulum has swung so far to the "useful skills" side of the continuum he feels a need to shout out for the "math is beautiful" side. Throughout the paper he tries to address objections, most of which involve our students not learning what they need to know to be citizens or scientists. (Hint: Does anyone really think that most students learn that now? How much worse off could we be to treat math as art? Maybe then at least a few more students would appreciate math and be willing to learn more.)

This paper is long-ish -- 25 pages -- but it is a fun read. His screed on high school geometry is unrestrained. He calls geometry class "Instrument of the Devil" because it so thoroughly and ruthlessly kills the beauty of proof:

Other math courses may hide the beautiful bird, or put it in a cage, but in geometry class it is openly and cruelly tortured.

His discussion of proof as a natural product of a student's curiosity and desire to explain an idea is as well written as any I've read. It extends another idea from earlier in the paper that fits quite nicely with something I have written about computer science: Mathematics is the art of explanation.

By concentrating on what, and leaving out why, mathematics is reduced to an empty shell. The art is not in the "truth" but in the explanation, the argument. It is the argument itself which gives the truth its context, and determines what is really being said and meant. Mathematics is the art of explanation. If you deny students the opportunity to engage in this activity--to pose their own problems, make their own conjectures and discoveries, to be wrong, to be creatively frustrated, to have an inspiration, and to cobble together their own explanations and proofs--you deny them mathematics itself.

I am also quite sympathetic to one of the other themes that runs deeply in this paper:

Mathematics is about problems, and problems must be made the focus of a student's mathematical life.

(Ditto for computer science.)

... you don't start with definitions, you start with problems. Nobody ever had an idea of a number being "irrational" until Pythagoras attempted to measure the diagonal of a square and discovered that it could not be represented as a fraction.

Problems can motivate students, especially when students create their own problems. That is one of the beautiful things about math: almost anything you see in the world can become a problem to work on. It's also true of computer science. Students who want to write a program to do something -- play a game, predict a sports score, track their workouts -- will go out of their way to learn what they need to know. I'm guessing anyone who has taught computer science for any amount of time has experienced this first hand.

As I've mentioned here a few times, my colleague Owen Astrachan is working on a big project to explore the idea of problem-based learning in CS. (I'm wearing the project's official T-shirt as I type this!) This idea is also right in line with Alan Kay's proposal for an "exploratorium" of problems for students who want to learn to commmunicate via computation, which I describe in this entry.

I love this passage from one of Lockhart's little dialogues:

SALVIATI:     ... people learn better when the product comes out of the process. A real appreciation for poetry does not come from memorizing a bunch of poems, it comes from writing your own.

SIMPLICIO:     Yes, but before you can write your own poems you need to learn the alphabet. The process has to begin somewhere. You have to walk before you can run.

SALVIATI:     ... No, you have to have something you want to run toward.

You just have to have something you want to run toward. For teenaged boys, that something is often a girl, and suddenly the desire to write a poem becomes a powerful motivator. We should let students find goals to run toward in math and science and computer science, and then teach them how.

It's interesting that I end with a running metaphor, and not just because I run. My daughter is a sprinter and now hurdler on her school track team. She sprints because she likes to run short distances and hates to run anything long (where, I think, "long" is defined as anything longer than her race distance!). The local runners' club leads a summer running program for high school students, and some people thought my daughter would benefit. One benefit of the program is camaraderie; one drawback that it involves serious workouts. Each week the group does a longer run, a day of interval training, and a day of hill work.

I suggested that she might be benefit more from simply running more -- not doing workouts that kill her, just building up a base of mileage and getting stronger while enjoying some longer runs. My experience is that it's possible to get over the hump and go from disliking longs runs to enjoying them. Then you can move on to workouts that make you faster. So she and I are going to run together a couple of times a week this summer, taking it easy, enjoying the scenery, chatting and otherwise not stressing about "long runs".

There is an element of beauty versus duty in learning most things. When the task is all duty, you may do it, but you may never like it. Indeed, you may come to hate it and stop altogether when the external forces that keep you on task (your teammates, your sense of belonging) disappear. When you enjoy the beauty of what you are doing, everything else changes. So it is with math, I think, and computer science, too.

A couple of weeks ago I linked to Shriram Krishnamurthi, who mentioned a recent SIGPLAN-sponsored workshop that has proposed a change to ACM's curriculum guidelines. The change is quite simple, shifting ten hours of instruction in programming languages from small topics into a single ten-hour category called "functional programming". Among the small topics that would be affected, coverage of recursion and event-driven programming would be halved, and coverage of virtual machines and language translation would no longer be mandated separately, nor would an "overview" of programming languages.

In practice, the proposal to eliminate coverage of some areas has less effect than you might think. Recursion is a natural topic in functional programming, and event-driven programming is a natural topic on object-oriented programming. The current recommendation of three hours total to cover virtual machines and language translation hardly does them justice anyway; students can't possibly learn any of the valuable ideas in depth in that amount of time. If schools adopt this change, they would be spending the time spent more productively helping students to understand functional programming well. Many schools will probably continue to teach those topics as part of their principles of programming languages course anyway.

I didn't comment on the proposal in detail earlier because it seemed more like the shuffling of deck chairs than a major change in stance. I do approve of the message the proposal sends, namely that functional programming is important enough to be a core topic in computer science. Readers of this blog already know where I stand on that.

Earlier this week, though, Mark Guzdial blogged Prediction and Invention: Object-oriented vs. functional, which has created some discussion in several circles. He starts with "The goal of any curriculum is to prepare the students for their future." Here is my take.

Mark seems to be saying that functional programming is not sufficiently useful to our students to make it a core programming topic. Mandating that schools teach ten hours each of functional and object-oriented programming, he thinks, tells our students that we faculty believe functional programming is -- or will be -- as important as object-oriented programming to their professional careers. Our students get jobs in companies that primarily use OO languages and frameworks, and our curricula should reflect that.

This piece has a vocational tone that I find surprising coming from Mark, and that is perhaps what most people are reacting to when they read it. When he speaks of making sure the curriculum teaches what is "real" to students, or how entry-level programmers often find themselves modifying existing code with an OO framework, it's easy to draw a vocational theme from his article. A lot of academics, especially computer scientists, are sensitive to such positions, because the needs of industry and the perceptions of our students already exert enough pressure on CS curriculum. In practical terms, we have to find the right balance between practical skills for students and the ideas that underlie those skills and the rest of computing practice. We already know that, and "esoteric" topics such as functional programming and computing theory are already part of that conversation.

Whether Mark is willing to stand behind the vocational argument or not, I think there is another theme in his piece that also requires a balance he doesn't promote. It comes back to the role of curriculum guidelines in shaping what schools teach and expressing what we think students should learn. Early on, he says,

I completely disagree that we should try to mandate that much functional programming through manipulation of the curriculum standards.

And later:

Then, when teaching more functional programming becomes a recognized best practice, it will be obvious that it should be part of the curriculum standards.

The question is whether curriculum standards should be prescriptive or descriptive. Mark views the current SIGPLAN proposal as prescribing an approach that contradicts both current best practice and the needs of industry, rather describing best practice in schools around the country. And he thinks curriculum standards should be descriptive.

I am sensitive to this sort of claim myself, because -- like Mark! -- I have been contending for many years with faculty who think OOP is a fad and has no place in a CS curriculum, or at least in our first-year courses. These faculty, both at my university and throughout the country, argue that our courses should be about what students "really do" in the world, not about esoteric design patterns and programming techniques. In the end, these people end up claiming that people like me are trying to prescribe a paradigm for how our students should think.

The ironic thing, of course, is that over the last fifteen years OOP and Java have gone from being something new to the predominant tools in industry. It's a good things that some schools started teaching more OOP, even in the first year, and developing the texts and teaching materials that other schools could use to join in later.

(The people arguing against OOP in the first year have not given up the case; they've now shifted to claiming that we should teach even Java "fundamentals first", going "back to basics" before diving into all that complicated stuff about data and procedures bearing some relation to one another. I've written about that debate before and have tremendous respect for many of the people on the front line of "basics" argument. I still disagree.)

As in the case of vocational versus theoretical content, I think we need to find the right balance between prescriptive and descriptive curriculum standards. These two dimensions are not wholly independent of each other, but they are different and so call for different balances. I agree with Mark that at least part of our curriculum standard should be descriptive of current practice, both in universities and in industry. Standard curricular practice is important in helping to create some consistency across universities and helping to keep schools who are out of the know on a solid and steady path. And the simple fact is that our students do graduate into professional careers and need to be prepared to participate in an economy that increasingly depends on information technology. For those of us at state-supported universities, this is a reasonable expectation of the people who pay our bills.

However, I think that we also need some prescriptive elements to our curricula. As Alan Kay says in a comment on Mark's blog, universities have a responsibility not only to produce graduates capable in participating in the economy but also to help students become competent, informed citizens in a democracy. This is perhaps even more important at state-supported universities, which serve the citizenry of the state. This may sound too far from the ground when talking about computer science curriculum, but it's not. The same ideas apply -- to growing informed citizens, and to growing informed technical professionals.

The notion that curriculum standards are partly prescriptive is not all that strange, because it's not that different from how curriculum standards have worked in the past, really. Personally, I like having experts in areas such as programming languages and operating systems helping us keep our curricular standards up to date. I certainly value their input for what they know to be current in the field. I also value their input because they know what is coming, what is likely to have an effect on practice in the near future, and what might help students understand better the more standard content we teach.

At first I had a hard time figuring out Mark's position, because I know him to grok functional programming. Why was he taking this position? What were his goals? His first paragraph seems to lay out his goal for the CS curriculum:

The goal of any curriculum is to prepare the students for their future. In just a handful of years, teachers aim to give the students the background to be successful for several decades.

He then recognizes that "the challenge of creating a curriculum is the challenge of predicting the future."

These concerns seem to sync quite nicely with the notion of encouraging that all students learn a modicum about functional programming! I don't have studies to cite, but I've often heard and long believed that the more different programming styles and languages a person learns, the better a programmer she will be. Mark points to studies show little direct transfer from skills learned in one language to skills learned in another, and I do not doubt their truth. But I'm not even talking about direct transfer of knowledge from functional programming to OOP; I'm thinking of the sort of expansion of the mind that happens when we learn different ways to think about problems and implement solutions. A lot of the common OO design patterns borrow ideas from other domains, including functional programming. How can we borrow interesting ideas if we don't know about them?

It is right and good that our curriculum standards push a little beyond current technical and curricular practice, because then we are able to teach ideas that can help computing evolve. This evolution is just as important in the trenches of a web services group at an insurance company as it is to researchers doing basic science. In the particular case of functional programming, students learn not only beautiful ideas but also powerful ideas, ideas that are germinating now in the development of programming languages in practice, from Ruby and Python to .NET. Our students need those ideas for their careers.

As I mentioned, Alan Kay chimed in with a few ideas. I think he disagrees that we can't predict the future by inventing it through curriculum. His idealism on these issues seems to frustrate some people, but I find it refreshing. We can set our sights higher and work to make something better. When I used the allusion to "shuffling the deck chairs" above, I was thinking of Kay, who is on record as saying that how we teach CS is broken. He has also talked to CS educators and exhorted us to set our sights higher. Kay supports the idea of prescriptive curricula for a number of reasons, the most relevant of which to this conversation is that we don't want to hard-code accidental or misguided practice, even if it's the "best" we have right now. Guzdial rightly points out that we don't want to prescribe new accidental or misguided practices, either. That's where the idea of striking a balance comes in for me. We have to do our best to describe what is good now and prescribe at least a little of what is good for the future.

I see no reason that we can't invent good futures by judiciously defined curriculum, any more than inventing futures in other arenas. Sure, we face social, societal, and political pressures, but how many arenas don't?

So, what about the particular curriculum proposal under discussion? Unlike Guzdial, I like the message it sends, that functional programming is an important topic for all CS grads to learn about. But in end I don't think it will cause any dramatic changes in how CS departments work. I used the word "encourage" above rather than Guzdial's more ominous "mandate", because even ACM's curriculum standards have no force of law. Under the proposed plan, maybe a few schools might try to present a coherent treatment of functional programming where now they don't, at the expense of covering a few good ideas at a shallow level. There will continue to be plenty of diversity, one of the values that guides Guzdial's vision. On this, he and I agree strongly. Diversity in curricula is good, both for the vocational reasons he asserts but also because we learn even better how to teach CS well from the labors and explorations of others.

I'm not yet thinking about my Programming Languages course this fall, but I wish I were. The first temptation came via my newsreader and Martin Fowler's recent piece ParserFear. Martin is writing a book on domain-specific languages and blogging occasionally on his ideas. This article is about just what the title says, programmers' often irrational fears of rolling a parser, which deter them from implementing their own DSLs. He speculates:

So why is there an unreasonable fear of writing parsers for DSLs? I think it boils down to two main reasons.

• You didn't do the compiler class at university and therefore think parsers are scary.
• You did do the compiler class at university and are therefore convinced that parsers are scary.

The first is easy to understand, people are naturally nervous of things they don't know about. The second reason is the one that's interesting. What this boils down to is how people come across parsing in universities.

CS students tend to learn about parsing for the first time in a compiler class, working on a large language with a full range of constructs. Parsing such languages is hard. In a few compiler courses, including my own, students still learn to build a parser by hand and so don't even have the chance to use parser generators as a labor- and pain-saving device. That's okay in a compiler course, which students take in large part to learn how their tools really work.

Martin doesn't suggest that we change the compiler course, and I don't either (though I'm open to possibilities). He does seem to think it's a shame that students are turned off to parsing and language design by first, and perhaps only, seeing them at their most complex. I agree and think that we should do more to introduce these ideas to students earlier.

I introduce students to the idea of parsing in my Programming Languages course, and ask students to write a few very small parsers to handle simple languages. I've been thinking for a while that I should do more in this area, and reading Martin's article has me itching to redesign the latter part of my course to allow more work with parsing and parsers. Another possibility is to use parsing as the content of some of our early programming exercises, when students are nominally learning to program in a functional style. Students can certainly apply the programming techniques they are learning to translate simple data formats into more abstract forms. This might help them to begin to see that parsing is an idea broader than just general-purpose programming languages. It might ease their transition a couple of weeks later to the idea of syntax-as-data structure and allow us to do some simple work with DSLs.

I have tried the idea of parsing at its simplest with relative novices as early as CS 1. When I taught a media computation CS1, one of the last programming assignments was to write a program to read a file of simple graphics commands and produce the desired graphical image. The idea was to bypass Java's verbose syntax for doing simple AWT/Swing graphics and allow non-programmers (artists) to make images. I asked students to implement a couple of simple commands, such as "draw line", and create at least one command of their own. I expected all of their graphics languages to be "straight-line", with no control or data structures, but that didn't mean that the resulting DSLs were not useful. They were just simple. A couple of students did really interesting work, creating very high-level commands for swirls and splashes. These students wrote methods to interpret those command using control and data structures that their "programmers" didn't have to know about.

Any change to my Programming Languages needs to be "footprint-neutral", to use Shriram Krishnamurthi's phrase. Anything I add has to fit in my fifteen-week course and either displace existing material or work in parallel. Shriram used this phrase in the broader context of rejiggering the teaching of teaching of programming languages within the core ACM curriculum, which a recent SIGPLAN-sponsored workshop tried to do. After having just read Martin's article on parsing, I was eager to refresh my memory on where parsing fits into the core curriculum proposal. Parsing falls under knowledge unit PL3, Language Translation, which has two hours allotted to it in the core. (An optional knowledge unit on Language Translation Systems includes more.) Interestingly, the working group Shriram reports on recommends cutting those two hours to zero, on the grounds that the current coverage is too superficial, and using those hours to build up a 10-hour unit on Functional Programming. That's a worthy goal, though I haven't hard a chance to think deeply about the proposal yet.

Working with constrained resources sometimes requires making tough choices. I know that Shriram and the people with whom he worked think that parsing is a worthwhile topic for CS students to know, so perhaps they have in mind something like what I suggested above: piggybacking some coverage of parsing on top of the coverage of functional programming. In any case, I think I'll work on finding more ways for my Programming Languages students to engage parsing and domain-specific languages.

The second half of the workshop opened with one of the best sessions of the event, the presentation "What Research Tells Us About Best Practices for Recruiting Girls into Computing" by Lecia Barker, a senior research scientist at the National Center for Women and IT. This was great stuff, empirical data on what girls and boys think and prefer. I'll be spending some time looking into Barker's summary and citations later. Some of the items she suggested confirm commonsense, such as not implying that you need to be a genius to succeed in computing; you only need to be capable, like anything else. I wonder if we realize how often our actions and examples implicitly say "CS is difficult" to interested young people. We can also use implicit cues to connect with the interests of our audience, such as applications that involve animals or the health sciences, or images of women performing in positions of leadership.

Other suggestions were newer to me. For example, evidence shows that Latina girls differ more from white and African-American girls than white and African-American girls differ from each other. This is good to know for my school, which is in the Iowa metro area with the highest percentage of African-Americans and a burgeoning Latina population. She also suggested that middle-school girls and high-school girls have different interests and preferences, so outreach activities should be tailored to the audience. We need to appeal to girls now, not to who they will be in three years. We want them to be making choices now that lead to a career path.

A second Five-Minute Madness session had less new information for me. I thought most about funding for outreach activities, such as ongoing support for an undergraduate outreach assistant whom we have hired for next year using a one-time grant form the university's co-op office. I had never considered applying for a special projects grant from the ACM for outreach, and the idea of applying to Avon was even more shocking!

The last two sessions were aimed at helping people get a start on designing an outreach project. First, the whole group brainstormed ideas for target audiences and goals, and then the newbies in the room designed a few slides for an outreach presentation with guidance from the more experienced people. Second, the two groups split, with the newbies working more on design and the experienced folks discussing the biggest challenges they face and ways to overcome them.

These sessions again made clear that I need to "think bigger". One, Outreach need not aim only at schools; we can engage kids through libraries, 4-H (which has broadened its mission to include technology teams), the FFA, Boys and Girls Clubs, and the YMCA and YWCA. Some schools report interesting results from working with minority girls through mother/daughter groups at community centers. Sometimes, the daughters end up encouraging the moms to think bigger themselves and seek education for more challenging and interesting careers. Two, we have a lot more support from upper administration and from CS faculty at my school than most outreach groups have at their schools. This means that we could be more aggressive in our efforts. I think we will next year.

The workshop ended with a presentation by Gabe Cohen, the project manager for Google Apps. This was the only sales pitch we received from Google in the time we were here (other than being treated and fed well), and it lasted only fifteen minutes. Cohen showed a couple of new-ish features of the free Apps suite, including spreadsheets with built-in support for web-based form input. He closed hurriedly with a spin through the new AppEngine, which debuted to the public on Wednesday. It looks cool, but do I have time?

The workshop was well-done and worth the trip. The main point I take away is to be more aggressive on several fronts, especially in seeking funding opportunities. Several companies we work with have funded outreach activities at other schools, and our state legislative and executive branches have begun to take this issue seriously from the standpoint of economic development. I also need to find ways to leverage faculty interest in doing outreach and interest from our administration in both STEM education initiatives and community service and outreach.

The workshop has ended. Google was a great host, from beginning to end. They began offering food and drinks almost immediately, and we never hungered or thirsted for long. That part of the trip made Google feel like the young person's haven it is. Wherever we went, the meeting tables included recessed power and ethernet cables for every kind of laptop imaginable, including my new Mac. (Macbook Pros were everywhere we went at Google.) But we also learned right away that visitors also must stay within bounds. No wandering around was allowed; we had to remain within sight of a Googler. And we were told not to take any photos on the grounds or in the buildings.

The workshop was presented live from within Google Docs, which allowed the leaders and presenters to display from a common tool and to add content as we went along. The participants didn't have access to the doc, but we were it as a PDF file -- on the smallest flash drive I've ever owned. It's a 1GB stick with the dimensions of the delete key on my laptop (including height).

The introduction to the workshop consisted of a linked-list game in which each person introduced the person to his left, followed by remarks from Maggie Johnson, the Learning and Development Director at Google Engineering, and Chris Stephenson, the executive director of ACM's Computer Science Teachers Association. The game ran a bit long, but it let everyone see how many different kinds of people were in the room, including a lot of non-CS faculty who lead outreach activities for some of the bigger CS departments. Chris expressed happiness that K-12, community colleges, and universities were beginning to work together on the CS pipeline. Outreach is necessary, but it can also be joyful. (This brought to mind her panel statement at SIGCSE, in a session I still haven't written up...)

Next up was Liz Adams reporting on her survey of people and places who are doing road shows or thinking about it. She has amassed a lot of raw data, which is probably most useful as a source of ideas. During her talk, someone asked, does anyone know if what they are doing is working? This led to a good discussion of assessment and just what you can learn. The goals of these road shows are many. When we meet with students, are we recruiting for our own school? Or are we trying to recruit for discipline, getting more kids to consider CS as a possible major? Are we working to reach more girls and underrepresented groups, or do we seek a rising tide? Perhaps we are doing service for the economy of our community, region, or state? The general answer is 'yes' to all of these things, which makes measuring success all the more difficult. While it's comforting to shoot wide, this may not be the most effective strategy for achieving any goal at all!

One idea I took away from this session was to ask students to complete a short post-event evaluation. I view most of our outreach activities these days as efforts to broaden interest in computer science generally, and to broaden students' views of the usefulness and attractiveness of computing even more generally. So I'd like to ask students about their perceptions of computing after we work with them. Comparing these answers to ones gathered before the activity would be even better. My department already asks students declaring CS majors to complete a short survey, and I plan to ensure it includes a question that will allow us to see whether our outreach activities have had any effect on the new students we see.

Then came a session called Five-Minute Madness, in which three people from existing outreach programs answered several questions in round-robin fashion, spending five minutes altogether on each. I heard a few useful nuggets here:

• Simply asking a young student "What will you be when you grow up?" and then talking about what we do can be a powerful motivator for some kids.

• Guidance counselors in the high schools are seriously misinformed about computing. No surprise there. But they often don't have access to the right information, or the time to look for it. The outreach program at UNC-Charlotte has produced a packet of information specifically for school counselors, and they visit with the counselors on any school visit they can.

• Reaching the right teacher in a high school can be a challenge. It is hard to find "CS teachers" because so few states certify that specialty. Don't send letters addressed to the "computing teacher"; it will probably end up in the trash can!

• We have to be creative in talking to people in the Department of Education, as well as making sure we time our mailings and offerings carefully. Know the state's rules about curriculum, testing, and the like.

• It's a relationship. Treat initial contacts with a teacher like a first date. Take the time to connect with the teacher and cultivate something that can last. One panelist said, "We HS teachers need a little romance." If we do things right, these teachers can become our biggest advocates and do a lot of "recruiting" for us through their everyday, long-term relationship with the students.

Dinner in one of the Google cafeterias was just like dinner in one of my university's residence halls, only with more diverse fare. A remarkable number of employees were there. Ah, to be young again.

Our first day closed with people from five existing programs telling us about their road shows. My main thought throughout this session was that these people spend a lot of time talking to -- at -- the kids. I wonder how effective this is with high school students and imagine that as the audience gets younger, this approach becomes even less effective. That said, I saw a lot of good slides with information that we can use to do some things. The presenters have developed a lot of good material.

Off to bed. Traveling west makes for long, productive days, but it also makes me ready to sleep!

A while back I read this xkcd comic, which introduced the idea of geohashing, selecting a meet-up location based on a date, the Dow-Jones Industrial Average, and MD5 hashing. Last month I ran across this wiki page on geohashing, which offers a reference implementation in Python. That's fine, even with all those underscores, but I decided to write a Ruby implementation for kicks. In particular, I had never worked with Ruby's MD5 digests and was glad to have a reason.

So, during a few stolen moments at the roadshow workshop (summary soon...), I knocked off an implementation. Here's my code. It's very simple and can certainly be improved. I tried to use idiomatic Ruby where I knew it, but some bits feel awkward. In other places, I mimicked the reference implementation perhaps too closely, so they still feel Python-y. Please send me your suggestions!

I'm preparing for a quick visit to the Google campus tomorrow and Friday. This is my first trip to the Google campus, and I have to admit that I'm looking forward to it. To this wide-eyed Midwestern computer scientist, it feels as if I am visiting Camelot.

The occasion of my trip is a "roadshow summit" co-sponsored by the Computer Science Teachers Association and SIGCSE, and hosted by Google. The CSTA is a unit of the ACM "that supports and promotes the teaching of computer science and other computing disciplines" in K-12 schools. The goal of the workshop is:

... to bring together faculty and students who are currently offering, or planning to develop, outreach "road shows" to local K-12 schools. Our goal is to improve the quality and number of college and university-supported careers and equity outreach programs by helping to develop a community that will share research, expertise, and best practices, and create shared resources.

My selfish goal in wanting to attend the workshop initially was to steal lots of good ideas with more experience and creativity than I. My contribution will be to share what we have done in our department, especially over the last semester. I asked two faculty members to develop curricula for K-12 outreach activities, in lieu of one of their usual course assignments. The curriculum materials should be useful whether we take them on the road to the schools or when we have students on campus for visits. One professor started with robotics in mind but quickly switched to some simple programming activities with the Scratch programming environment. The other worked on high-performance and parallel computing for pre-college students, an education thread he has been working in for much of this decade. I do not have a link to materials he developed specifically for our outreach efforts yet, but I can point you to LittleFe, one of his ongoing projects.

I'm curious to see what other schools have done and still plan to steal as many ideas as I can! And, while I'm looking forward to the workshop and seeing Google's campus, I am not looking forward to the fast turnaround... My flight leaves tomorrow morning; we work Thursday afternoon, Thursday evening, Friday morning, and Friday early afternoon; and then I start the sojourn back home. I'll cover a lot of miles in forty-eight hours, but I hope they prove fruitful.

I grew up on the sitcom of the 1970s and 1980s. As kids, we watched almost everything we saw in reruns, whether from the '60s or the '70s, but I enjoyed so many of them. By the time I got to college, I had well-thought ideas on why The Dick Van Dyke Show remains one of the best sitcoms ever, why WKRP in Cincinnati was underrated for its quality, and why All in the Family was _the_ best sitcom ever. I still hold all these biases in my heart. Of course, I didn't limit myself to sitcoms; I also loved light-action dramas, especially The Rockford Files.

Little did I know then that my TV viewing was soaking up a cognitive surplus in a time of social transition, or that it had anything in common with gin pushcarts in the streets of London at the onset of the Industrial Revolution.

Clay Shirky has published a wonderful little essay, Gin, Television, and Social Surplus that taught me these things and put much of what we see on happening on the web into the context of a changing social, cultural, and economic order. Shirky contends that, as our economy and technology evolve, a "cognitive surplus" is created. Energy that used to be spent on activities required in the old way is now freed for other purposes. But society doesn't know what to do with this surplus immediately, and so there is a transition period where the surplus is dissipated in (we hope) harmless ways.

My generation, and perhaps my parents', was part of this transition. We consumed media content produced by others. Some denigrate that era as one of mindless consumption, but I think we should not be so harsh. Shows like All in the Family and, yes, WKRP in Cincinnati often tackled issues on the fault lines of our culture and gave people a different way to be exposed to new ideas. Even more frivolous shows such as The Dick Van Dyke Show and The Rockford Files helped people relax and enjoy, and this was especially useful for those who were unprepared for the expectations of a new world.

We are now seeing the advent of the new order in which people are not relegated to consuming from the media channels of others but are empowered to create and share their own content. Much attention is given by Shirky and many, many others to the traditional media such as audio and video, and these are surely where the new generation has had its first great opportunities to shape its world. As Shirky says:

Here's something four-year-olds know: A screen that ships without a mouse ships broken. Here's something four-year-olds know: Media that's targeted at you but doesn't include you may not be worth sitting still for.

But as I've been writing about here, lets not forget the next step: the power to create and shape the media themselves via programming. When people can write programs, they are not relegated even to using the media they have been given but are empowered to create new media, and thus to express and share ideas that may otherwise have been limited to the abstraction of words. Flickr and YouTube didn't drop from the sky; people with ideas created new channels of dissemination. The same is true of tools like Photoshop and technologies such as wikis: they are ideas turned into reality through code.

Do read Shirky's article, if you haven't already. It has me thinking about the challenge we academics face in reaching this new generation and engaging them in the power that is now available to them. Until we understand this world better, I think that we will do well to offer young people lots of options -- different ways to connect, and different paths to follow into futures that they are creating.

One thing we can learn from the democratized landscape of the web. I think, is that we are not offering one audience many choices; we are offering many audiences the one or two choices each that they need to get on board. We can do this through programming courses aimed at different audiences and through interdisciplinary major and minor programs that embed the power of computing in the context of problems and issues that matter to our students.

Let's keep around the good old CS majors as well, for those students who want to go deep creating the technology that others are using to create media and content -- just as we can use the new technologies and media channels to keep great old sitcoms available for geezers like me.

I still have a couple of entries to make on SIGCSE 2008 happenings. If I don't hurry up, it will be time for reports from PLoP or OOPSLA! But I do have a bit of related good news to post...

I've received an invitation to Peter Denning's "Rebooting Computing" summit, which I first mentioned when covering Denning's talk at SIGCSE. The summit is scheduled for January 2009 and is part of Denning's NSF-funded Resparking Innovation in Computing Education project. This will be a chance to spend a few days with others thinking about this issue to outline concrete steps that we all might take to make change. I've written about this issue frequently here, most recently in the form of studio-based computing, project-based and problem-based learning, and programming for non-CS folks like computing into their own work. (Like scientists and artists. I'm excited about this chance.

I notice a common rhetorical device in many academic arguments. It goes like this. One person makes a claim and offers some evidence. Often, the claim involves doing something new or seeing something in a new way. The next person rebuts the argument with a claim that the old way of doing or seeing things is more "fundamental" -- it is the foundation on which other ways of doing and seeing are built. Oftentimes, the rebuttal comes with no particular supporting evidence, with the claimant relying on many in the discussion to accept the claim prima facie. We might call this The Fundamental Imperative.

This device is standard issue in the CS curriculum discussions about object-oriented programming and structured programming in first-year courses. I recently noticed its use on the SIGCSE mailing list, in a discussion of what mathematics courses should be required as part of a CS major. After several folks observed that calculus was being de-emphasized in some CS majors, in favor of more discrete mathematics, one frequent poster declared:

(In a word, computer science is no longer to be considered a hard science.)

If we know [the applicants'] school well we may decide to treat them as having solid and relevant math backgrounds, but we will no longer automatically make that assumption.

Often, the conversation ends there; folks don't want to argue against what is accepted as basic, fundamental, good, and true. But someone in this thread had the courage to call out the emperor:

If you want good physicists, then hire people who have calculus. If you want good computer scientists, then hire people who have discrete structures, theory of computation, and program verification.

I don't believe that people who are doing computer science are not doing "hard science" just because it is not physics. The world is bigger than that.

...

You say "solid and relevant" when you really should be saying "relevant". The math that CS majors take is solid. It may not be immediately relevant to problems [at your company]. That doesn't mean it is not "solid" or "hard science".

I sent this poster a private "thank you". For some reason, people who drop the The Fundamental Imperative into an argument seem to think that it is true absolutely, regardless of context. Sure, there may be students who would benefit from learning to program using a "back to the basics" approach, and there may be CS students for whom calculus will be an essential skill in their professional toolkits. But that's probably not true of all students, and it may well be that the world has changed enough that most students would benefit from different preparation.

"The Fundamental Imperative" is a nice formal name for this technique, but I tend to think of it as "if it was good enough for me...", because so often it comes down to old fogies like me projecting our experience onto the future. Both parties in such discussions would do well not to fall victim to their own storytelling.

In his recent bestseller The Black Swan: The Impact of the Highly Improbable, Nassim Nicholas Taleb uses the term narrative fallacy to describe man's penchant for creating a story after the fact, perhaps subconsciously, in order to explain why something happened -- to impute a cause for an event we did not expect. This fallacy derives from our habit of imposing patterns on data. Many view this as a weakness, but I think it is a strength as well. It is good when we use it to communicate ideas and to push us into backing up our stories with empirical investigation. It is bad when we let our stories become unexamined truth and when we use the stories to take actions that are not warranted or well-founded.

Of late, I've been thinking of the narrative fallacy in its broadest sense, telling ourselves stories that justify what we see or want to see. My entry on a response to the Onward! submission by my ChiliPLoP group was one trigger. Those of us who believe strongly that we could and perhaps should be doing something different in computer science education construct stories about what is wrong and what could be better; we're like anyone else. That one OOPSLA reviewer shed a critical light on our story, questioning its foundation. That is good! It forces us to re-examine our story, to consider to what extent it is narrative fallacy and to what extent it matches reality. In the best case, we now know more about how to tell the story better and what evidence might be useful in persuading others. In the worst, we may learn that our story is a crock. But that's a pretty good worst case, because it gets us back on the path to truth, if indeed we have fallen off.

A second trigger was finding a reference in Mark Guzdial's blog to a short piece on universal programming literacy at Ken Perlin's blog. "Universal programming literacy" is Perlin's term for something I've discussed here occasionally over the last year, the idea that all people might want or need to write computer programs. Perlin agrees but uses this article to consider whether it's a good idea to pursue the possibility that all children learn to program. It's wise to consider the soundness of your own ideas every once in a while. While Perlin may not be able to construct as challenging a counterargument as our OOPSLA reviewer did, he at least is able to begin exploring the truth of his axioms and the soundness of his own arguments. And the beauty of blogging is that readers can comment, which opens the door to other thinkers who might not be entirely sympathetic to the arguments. (I know...)

It is essential to expose our ideas to the light of scrutiny. It is perhaps even more important to expose the stories we construct subconsciously to explain the world around us, because they are most prone to being self-serving or simply convenient screens to protect our psyches. Once we have exposed the story, we must adopt a stance of skepticism and really listen to what we hear. This is the mindset of the scientist, but it can be hard to take on when our cherished beliefs are on the line.

The verdict is in on the paper we wrote at ChiliPLoP and submitted to Onward!: rejected. (We are still waiting to hear back on our Educators' Symposium submission.) The reviews of our Onward! paper were mostly on mark, both on surface features (e.g., our list of references was weak) and on the deeper ideas we offer (e.g., questions about the history of studio approaches, and questions about how the costs will scale). We knew that this submission was risky; our time was simply too short to afford enough iterations and legwork to produce a good enough paper for Onward!.

I found it interesting that the most negative reviewer recommended the paper for acceptance. This reviewer was clearly engaged by the idea of our paper and ended up writing the most thorough, thoughtful review, challenging many of our assumptions along the way. I'd love to have the chance to engage this person in conversation at the conference. For now, I'll have to settle for pointing out some of the more colorful and interesting bits of the review.

In at least one regard, this reviewer holds the traditional view about university education. When it comes to the "significant body of knowledge that is more or less standard and that everyone in the field should acquire at some point in time", "the current lecture plus problem sets approach is a substantially more efficient and thorough way to do this."

Agreed. But isn't it more efficient to give the students a book to read? A full prof or even a TA standing in a big room is an expensive way to demonstrate standard bodies of knowledge. Lecture made more sense when books and other written material were scarce and expensive. Most evidence on learning is that lecture is actually much less effective than we professors (and the students who do well in lecture courses) tend to think.

The reviewer does offer one alternative to lecture: "setting up a competition based on mastery of these skills". Actually, this approach is consistent with the spirit of our paper's studio-based, apprenticeship-based, and project-based. Small teams working to improve their skills in order to win a competition could well inhabit the studio. Our paper tended to overemphasize the softer collaboration of an idyllic large-scale team.

This comment fascinated me:

Another issue is that this approach, in comparison with standard approaches, emphasizes work over thinking. In comparison with doing, for example, graph theory or computational complexity proofs, software development has a much lower ratio of thought to work. An undergraduate education should maximize this ratio.

Because I write a blog called Knowing and Doing, you might imagine that I think highly of the interplay between working and thinking. The reviewer has a point: an education centered on projects in a studio must be certain to engage students with the deep theoretical material of the discipline, because it is that material which provides the foundation for everything we do and which enables us to do and create new things. I am skeptical of the notion that an undergrad education should maximize the ratio of thinking to doing, because thinking unfettered by doing tends to drift off into an ether of unreality. However, I do agree that we must try to achieve an appropriate balance between thinking and doing, and that a project-based approach will tend to list toward doing.

One comment by the reviewer reveals that he or she is a researcher, not a practitioner:

In my undergraduate education I tried to avoid any course that involved significant software development (once I had obtained a basic mastery of programming). I believe this is generally appropriate for undergraduates.

Imagine the product of an English department saying, "In my undergraduate education I tried to avoid any course that involved significant composition (once I had obtained a basic mastery of grammar and syntax). I believe this is generally appropriate for undergraduates." I doubt this person would make much of a writer. He or she might be well prepared, though, to teach lit-crit theory at a university.

Most of my students go into industry, and I encourage them to take as many courses as they can in which they will build serious pieces of software with intellectual content. The mixture of thinking and doing stretches them and keeps them honest.

An education system that produces both practitioners and theoreticians must walk a strange line. One of the goals of our paper was to argue that a studio approach could do a better job of producing both researchers and practitioners than our current system, which often seems to do only a middling job by trying to cater to both audiences.

I agree wholeheartedly, though, with this observation:

A great strength of the American system is that it keeps people's options open until very late, maximizing the ability of society to recognize and obtain the benefits of placing able people in positions where they can be maximally productive. In my view this is worth the lack of focus.

My colleagues and I need to sharpen our focus so that we can communicate more effectively the notion that a system based on apprenticeship and projects in a studio can, in fact, help learners develop as researchers and as practitioners better than a traditional classroom approach.

The reviewer's closing comment expresses rather starkly the challenge we face in advocating a new approach to undergraduate education:

In summary, the paper advocates a return to an archaic system that was abandoned in the sciences for good reason, namely the inefficiency and ineffectiveness of the advocated system in transmitting the required basic foundational information to people entering the field. The write-up itself reflects naive assumptions about the group and individual dynamics that are required to make the approach succeed. I would support some of the proposed activities as part of an undergraduate education, but not as the primary approach.

The fact that so many university educators and graduates believe our current system exists in its current form because it is more efficient and effective than the alternatives -- and that it was designed intentionally for these reasons -- is a substantial cultural obstacle to any reform. Such is the challenge. We owe this reviewer our gratitude for laying out the issues so well.

In closing, I can't resist quoting one last passage from this review, for my friends in the other sciences:

The problem with putting students with no mastery of the basics into an apprenticeship position is that, at least in computer science, they are largely useless. (This is less true in sciences such as biology and chemistry, which involve shallower ideas and more menial activities. But even in these sciences, it is more efficient to teach students the basics outside of an apprenticeship situation.)

The serious truth behind this comment is the one that explains why building an effective computer science research program around undergraduates can be so difficult. The jocular truth behind it is that, well, CS is just plain deeper and harder! (I'll duck now.)

I've tried to explain the idea of software patterns in a lot of different ways, to a lot of different kinds of people. Reading James Tauber's Grammar Rules reminds me of one of my favorites: a pattern language is a descriptive grammar. Patterns describe how (good) programmers "really speak" when they are working in the trenches.

Talking about patterns as grammar creates the potential for the sort of misunderstanding that Tauber discusses in his entry. Many people, including many linguists, think of grammar rules as, well, rules. I was taught to "follow the rules" in school and came to think of the rules as beyond human control. Linguists know that the rules of grammar are man-made, yet some still seem to view them as prescriptive:

It is as if these people are viewing rules of grammar like they would road rules--human inventions that one may disagree with, but which are still, in some sense, what is "correct"...

Software patterns are rarely prescriptive in this sense. They describe a construct that programmers use in a particular context to balance the forces at play in the problem. Over time, they have been found useful and so recur in similar contexts. But if a programmer decides not to use a pattern in a situation where it seems to apply, the programmer isn't "wrong" in any absolute sense. But he'll have to resolve the competing forces in some other way.

While the programmer isn't wrong, other programmers might look at him (or, more accurately, his program) funny. They will probably ask "why did you do it that way?", hoping to learn something knew, or at least confirm that the programmer has done something oddly.

This is similar to how human grammar works. If I say, "Me wrote this blog", you would be justified in looking at me funny. You'd probably think that what I speaking incorrectly.

Tauber points out that, while I might be violating the accepted rules of grammar, I'm not wrong in any absolute sense:

... most linguists focus on modeling the tacit intuitions native speakers have about their language, which are very often at odds with the "rules of grammar" learnt at school.

He gives a couple of examples of rules that we hear broken all of the time. For example, native speakers of English almost always say "It's me", not "It's I", though that violates the rules of nominative and accusative case. Are we all wrong? In Sr. Jeanne's 7th-grade English class, perhaps. But English grammar didn't fall from the heavens as incontrovertible rules; it was created by humans as a description of accepted forms of speech.

When a programmer chooses not to use a pattern, other programmers are justified in taking a second look at the program and asking "why?", but they can't really say he's guilty of anything more than doing things differently.

Like grammar rules, some patterns are more "right" than others, in the sense that it's less acceptable to break some than others. I can get away with "It's me", even in more formal settings, but I cannot get away with "Me wrote this blog", even in the most informal settings. An OO programmer might be able get away with not using the Chain of Responsibility pattern in a context where it applies, but not using Strategy or Composite in appropriate contexts just makes him look uninformed, or uneducated.

A few more thoughts:

So, patterns are not like a grammar for programming language, which is prescriptive. To speak Java at all, you have to follow the rules. They are like the grammar of a human language, which model observations about how people speak in the wild.

As a tool for teaching and learning, patterns are so useful precisely because they give us a way to learn accepted usages that go beyond the surface syntactic rules of a language. Even better, the pattern form emphasizes documenting when a construct works and why. Patterns are better than English grammar in this regard, at least better than the way English grammar is typically taught to us as schoolchildren.

There are certainly programmers, software engineers, and programming language theorists who want to tell us how to program, to define prescriptive rules. There can be value in this approach. We can often learn something from a model that has been designed based on theory and experience. But to me prescriptive models for programming are most useful when we don't feel like we have to follow them to the letter! I want to be able to learn something new and then figure out how I can use it to become a better programmer, not a programmer of the model's kind.

But there is also a huge, untapped resource in writing the descriptive grammar of how software is built in practice. It is awfully useful to know what real people do -- smart, creative people; programmers solving real problems under real constraints. We don't understand programming or software development well enough yet not to seek out the lessons learned by folks working in the trenches.

This brings to mind a colorful image, of software linguists venturing into the thick rain forest of a programming ecosystem, uncovering heretofore unexplored grammars and cultures. This may not seem as exotic as studying the Pirahã, but we never know when some remote programming tribe might upend our understanding of programming...

Brian Marick lamented recently that his daughter's homework probably wasn't affecting her future in the same way that some of his school experiences affected his. I've had that feeling, too, but sometimes wonder whether (1) my memory is good enough to draw such conclusions and (2) my daughters will remember key experiences from their school days anyway. After teaching for all these years I am sometimes surprised by what former students remember from their time in my courses, and how those memories affect them.

Brian's mention of New Math elicited some interesting comments. Kevin Lawrence hit on a point that has been on my mind in two contexts lately:

A big decision point in education is whether you are optimizing for people who will go on to be very good at a subject or for people who find it difficult.

In the context of university CS curricula, I often field complaints from colleagues here and everywhere about how the use of (graphics | games | anything post-1980 | non-scientific applications) in CS courses is dumbing down of our curriculum. These folks claim that we are spending too much time catering to folks who won't succeed in the discipline, or at least excel, and that at the same time we drive away the folks who would be good at CS but dislike the "softness" of the new approach.

In the context of reaching out to pre-university students, to show folks cool and glitzy things that they might do in computer science, I sometimes hear the same sort of thing. Be careful, folks say, not to popularize the science too much. We might mislead students into thinking that CS is not serious, or that it is easy.

I fully agree that we don't want to mislead middle schoolers or CS majors about the content or rigor of our discipline, or to give the impression that we cannot do serious and important work. But physics students and math geeks are not the only folks who can or should use computing. They are most definitely not the only folks who can make vital contributions to the discipline. (We can even learn from people who quote "King Lear".)

By not reaching out to students with different views and interests, we do computer science a disservice. Once they are attracted to the discipline and excited to learn, we can teach them all about rigor and science and math. Some of those folks won't succeed in CS, but then again neither do some of the folks who come in with the more traditional "geeky" interests.

If this topic interests you, follow the trail from Brian's blog to two blog entries by Kevin Lawrence, one old and one new. Both are worth a read. (I always knew there was a really good reason to enable comments on my blog -- Alan Kay might drop by!)

I may not be a web guy, but some of my students are -- and very good ones. Back in December, I wrote about one of my students, Sergei Golitsinski, defending an MA thesis in Communications, which used computing to elucidate a problem in that discipline. For that study, he wrote tools that allowed him to trace the threads of influence in a prominent blog-driven controversy.

Sergei finally defended his MS thesis in computer science yesterday. Its title -- "Specification and Automatic Code Generation of the Data Layer for Data-Intensive Web-Based Applications" -- sounds like the usual thesis title, but as is often the case the idea behind it is really quite accessible. This thesis shows how you can use knowledge about your web application to generate much of the code you need for your site.

I like this work for several reasons. First, it was all about finding patterns in real applications and using them to inform software development. Second, it focused on how to use domain knowledge to get leverage from the patterns. Third, it used standard language-processing ideas to create a modeling language and then use models written in it to generate code. This thesis demonstrates how several areas of computer science -- database, information storage and retrieval, and programming languages among them -- can work together to help us write programs to do work for us. I also like it because Sergei applied his ideas to his own professional work and took a critical look at what the outcome means for his own practice.

Listening to the defense, I had two favorite phrases. The first was recursive weakness. He used this term in reference to weak entities in a database that are themselves parents to weak entities. But it brought to mind so many images for the functional programmer in me. (I'm almost certainly recursively weak myself, but where is the base case?) The second arose arose while discussing alternative approaches to a particular problem. Referring to one, he said trivial approach; non-trivial implementation. It occurred to me that so many ideas fall into this category, and part of understanding your domain well is recognizing them. Sometimes we need to avoid their black holes; other times, we need their challenges. Another big part of becoming a master is knowing which path to choose once you have recognized them.

Sergei is a master, and soon he will have a CS degree that says so. But like all masters, he has much to learn. When I wrote about his previous defense, his plan was up in the air but pointing toward applying CS in the world of communications. Since then, he has accepted admission to a Ph.D. program in communications at the University of Maryland, where he hopes to be in the vanguard of a new discipline he calls computational communications. I look forward to watching his progress.

You can read his CS thesis on-line, and all of the code used in his study will be, too, soon.

I am not a web guy. If I intend to teach languages (PHP) or frameworks (Rails) with the web as their natural home, I need to do a lot more practice myself. It's too easy to know how to do something and still not know it well enough to teach it well. Unexpected results under time pressure create too much trouble.

MySQL, no. PostgreSQL, yes. This, twenty years after cutting my database teeth on Ingres.

Ruby's dynamic features are so, so nice. Still, I occasionally find myself wishing for Smalltalk. First love never dies.

Fifteen hours of instruction -- 5 weeks at 3 hours per week -- is plenty of time to teach most or all of the ideas in a language like bash, PHP, or Ruby. But the instructor still needs to select specific examples and parts of the class library carefully. It's too easy to start down a path of "Now look at this [class, method, primitive]..."

When I succeeded in selecting carefully, I suffered from persistent omitter's resource. "But I wish I could have covered that... Sometimes that is what students wanted to see. But most of the time they can figure that out. What they want is some insight. What insight could I have shared had I covered that instead of this?

If you want to know what students want, ask them. Easy to say, hard to do unless I slow down occasionally to reflect.

Practice, practice, practice. That's where students learn. It's also where students who don't learn don't learn.

Oh, and professor: That "Practice, practice, practice" thing -- it applies to you, too. You'll remember just how much fun programming can be.

I remember learning in courses on simulation, operating systems, and networking that, for a given period, the number of events such as cars arriving at an intersection or processes arriving at a scheduler is often best modeled using the Poisson distribution. Mostly, I recall being surprised that these events often occur in clumps, rather than uniformly distributed over a larger time period. Sometimes, it feels like ideas work this way... When I encounter an idea once during the day, I often seem to bump into it again and again. I'm sure that it's just that my mind is sensitized to the idea and recognize -- or project -- it more easily, much as magic books affect us. In any case, yesterday was such a day.

At 3:30 PM I attended a department seminar on bioinformatics by a colleague. I asked him what sort of questions he and his students could ask about bacteriophages in a data-rich environment that they could not ask before. He said that they could now quantify the notions of similarity and difference between phages in ways inaccessible to them before and write programs to apply their metrics. Eventually, he talked about how digital processing of large data sets enforced a more disciplined approach on the approach to problems, in order to battle complexity. Now, they convert big questions into a sequence of smaller, well-defined steps that can be tackled in a clear way. For him as a biologist, this was a surprising and wonderful phenomenon.

I stayed in the same room for a 5:00 PM class taught by one of our adjuncts, whose teaching I was to evaluate. He was teaching a "skills and concepts" course for non-majors, and the day's topic was databases. They talked about the similarities and differences between spreadsheets and databases, especially on how the structural integrity of a database makes it possible to formulate concise queries that can find useful answers. He some of the ideas using an Access database, first using a wizard to query the system and then looking at a raw SQL query. For many queries, he told them, the wizard does all you need. But there will times when you want to ask a question the wizard doesn't support, and then the ability to write your own select statements in SQL becomes a valuable skill.

After class, I caught upon some paperwork in my office until 7:00 PM, when I attended a panel presentation entitled "Visual Art, the Big Screen, and Orchestral Performance". (Here is a poster for the talk, in PDF.) Three local artists -- illustrator Gary Kelley, conductor Jason Weinberger, and videographer Scott Smith -- shared parts of their recent multimedia presentation of Gustav Holst's The Planets and discussed the creative forces that drove them individually and collectively to produce the work. I learned that multimedia presentations of The Planets are relatively common but that this show differed in significant ways from the usual, not the least of which was Kelley's creation of thirty new paintings and monotypes for the show.

(You may recall Smith's name from an earlier post... He had a small acting role in the play I did last winter!)

The panel ended with a discussion of how changes in technology were fundamentally changing how artist work are created and distributed. Not long ago, Hollywood and other media centers produced the entertainment that we all consumed, but now it is possible for folks in the middle of nowhere -- Iowa! -- to create and export their work to a global audience. This is, of course, nothing new in the age of the Internet and YouTube, but it is still cause for marvel to artists who recently lived and worked in a different world.

One of the central themes of the panel was the level of trust and surrender that this kind of presentation required, especially of the symphony members and conductor Weinberger. The timing of the video required the orchestra to hit certain marks in the music on a dot, and Weinberger, who usually controls tempo and shapes the sound of the performance, had to give up control the artwork produced by Kelley and Smith. The visual artists expressed a willingness to turn the tables and find a way to cede control to Weinberger in a future collaboration.

This set me to thinking... The reason that the musicians had to surrender control was essentially technological. Once a video is produced, it is set. Performance of the music was the more malleable medium, as the players could speed up or slow down in real-time to stay in sync. Ideally, of course, they would play a steady predefined pace, but that is quite difficult. But these days, "video" is much more malleable because it is digital. Why not let the musicians play however they and the conductor see fit, and adjust the pace of the video playback to keep in sync with the music? I don't know if such a digital tool exists already, but if not, what fun it would be to write! Then in performance, the videographer could "play" the video by reacting in real-time to the music.

All three of these stories had me thinking the same thing: "Now there's programming." I know the feeling well the feeling my biologist colleague expressed, because both of his answers come down to programming as discipline and medium. When our adjunct instructor told his non-CS students from all over campus about the power of knowing a little SQL, I smiled at the thought of non-programmers writing programs, albeit small ones, to scratch their own itches. Likewise, the ability to imagine how the orchestra might turn the tables on the visual artists in their multimedia collaborations, and then implement the vision in a working tool, is nothing more or less than programming.

[A transcript of the SIGCSE 2008 conference: Table of Contents]

Of the 20 greatest engineering achievements of the 20th century, two lie within computing: computers (#8) and the Internet (#13). Those are broad categories defined around general-purpose tools that have affected the lives of almost every person and the practice of almost every job.

In 2004, human beings harvested 10 quintillion grains of rice. In 2004, humans beings fabricated 10 quintillion transistors. 10 quintillion is a big number: 10,000,000,000,000,000,000.

Ed Lazowska of the University of Washington opened his Saturday luncheon talk at SIGCSE with these facts, as a way to illustrate the broad effect that our discipline has had on the world and the magnitude of the discipline today. He followed by putting the computational power available today into historical context. The amount of computational power that was available in the mainstream in the 1950s is roughly equivalent to an electronic greeting card today. Jump forward to the Apollo mission to the moon, and that computation power is now available in a Furby. Lazowska didn't give sources for these claims or data to substantiate them, but sound reasonable to me within an order of magnitude.

The title of Lazowska's talk was "Computer Science: Past, Present, and Future", and it was intended to send conference attendees home energized about our discipline. He energized folks with cool facts about computer science's growth and effect. Then he looked to the future, at some of the challenges and some of the steps being taken to address them.

One of the active steps being taken within computing is the <