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.

Last Sunday, I ran 9 miles. It was my longest long run since coming down with whatever ails me 10 weeks ago or so. It felt better than I expected. The result was 30+ miles for that week. My plan for the past week was to repeat that mileage and let my body adjust before trying to do more.

But then I felt rundown all week. I felt slow when I was on the road, and I felt listless at work and at home. I decided to skip my Friday run, in order to recover a bit, and maybe rest a little.

Friday night, my whole family drove three hours to Minneapolis. My wife and older daughter were to attend a dance camp for a few days, and my younger daughter and I tagged along for Friday evening and Saturday.

Saturday, the three of us who weren't dancing spent all day on our feet, mostly walking to, from, and at the Mall of America. (Yes, it's a very big mall.) At the end of the day, I was exhausted, and my younger daughter and I drove home.

This morning, I slept in, recovering a bit. I decided to give my planned 9-miler a go in the afternoon, but even before I started I was thinking of contingencies. I would take it slow, and if I didn't feel well, I could trim it back to 8, 7, or even 6 miles. The weather would be quite warm, and I usually run in the morning before heat is an issue, so I carried water for even this short "long run".

I felt good. I ran faster and more comfortably than last week. For Mile 7, I ran a shocking 8:18. (The time is shocking only in the context of the last ten weeks!) I slowed over the last 2.5 miles, yet my overall time was almost 3 minutes than last week's run over the same route.

Of course, soon I had to sleep, and sleep I did, hard and deep for an hour or more.

My body is getting back into the swing of running, but in certain ways I'm still where I was weeks ago. What's worse, I don't know how my body will react to any given run or day. I'm still figuring things out, and hoping to get well all the while.

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.)

[Update: Added a linked to my interview at Confessions of a Science Librarian.]

Some months, I go through stretches when I write a lot. I started this month with a few substantive posts and a few light posts in the span of a week. Back in November 2007, I wrote twice as many posts as the typical month and more than any month since my first few months blogging. That month, I posted entries eleven days in a row, driven by a burst of thoughts from time spent at a workshop on science and computer science. This month, I had the fortune to read some good articles and the chance to skip real work, think, and write. Sometimes, the mood to write takes hold.

I have had an idea for a long time to write an entry that was motivated by reading George Orwell's essay Why I Write, but never seem to get to it. I'm not getting to it today, either. But it came to mind again for two reasons. First, I spent the morning giving a written interview to John Dupuis, who blogs at Confessions of a Science Librarian. John is a reader of my blog and asked me to share some of my ideas with his readers. I was honored to be asked, and so spent some time this morning reflecting on my blog, what and why I write. Second, today is the fourth anniversary of my first blog post.

Responding to John's questions is more writing than I do on most days. I don't have enough energy left to write a substantive post yet today, but I'm still in a reflective frame of mind about why I write.

Do I really need to blog? Someone has already said what I want to say. In that stretch of posts last November, I cited Norvig, Minsky, and Laurel, among others, talking about the same topics I was writing about. Some reasons I can think of are:

• My experiences are different, so maybe I have something to add, however small that might be.
• My posts link to all that great work, and someone who reads my blog may find an article they didn't know about and read it. Or they may remember it from the past, feel guilty at not having read it before, and finally go off to read it.
• If nothing else, I write to learn, and to make myself happy. Some days, that's more than enough reason for me.

There are certainly other self-interested reasons to write. There is noble self-interest:

Share your knowledge. It's a way to achieve immortality.
-- the 14th Dalai Lama

And there is the short-term self-interest. I get to make connections in my own mind. Sometimes I am privileged to see my influence on former students, when they respond to something I've written. And then there is the lazy blog, where some reader knows or has something I don't and shares. At times, these two advantages come together, as when former student Ryan Dixon brought me a surprise gift last winter.

Year Five begins today, even if still without comments.

While reading this morning I came across a link to this essay. College students should read it, because it points out many of the common anti-patterns in the essays that we professors see -- even in papers written for computer science courses.

Of course, if you read this blog, you know that my writing is a poster child for linguistic diffidence, and pat expressions are part of my stock in trade. It's sad to know that these anti-patterns make up so much of my word count.

This web page also introduced me to Roberts's book Patterns in English. With that title, I must check it out. I needed a better reason to stop by the library than merely to return books I have finished. Now I have one.

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.

On my way into a store this afternoon to buy some milk, I ran into an old friend. He moved to town a decade or so ago and taught art at the university for five years before moving on to private practice. As we reminisced about his time on the faculty, we talked about how much we both like working with students. He mentioned that he recently attended his 34th wedding of a former student.

Thirty-four weddings from five years of teaching. I've been teaching for sixteen years and have been invited to only a handful of weddings -- three or four.

Either art students are a different lot from CS students, or I am doing something wrong...

I wrote about a recent CS curricular discussion, which started with a blog posting by Mark Guzdial. Reading the comments to Guzdial's post is worth the time, as you'll find a couple of lengthy remarks by Alan Kay. As always, Kay challenges even computer science faculty to think beyond the boundaries of our discipline to the role what our students learn from us plays in a democratic world.

One of Kay's comments caught my attention for connections to a couple of things I've written about in recent years. First, consider this:

I posit that this is still the main issue in America. "Skilled children" is too low a threshold for our system of government: we need "educated adults". ... I think the principle is clear and simple: there are thresholds that have to be achieved before one can enter various conversations and processes. "Air guitar and attitude" won't do.

Science is a pretty good model (and it was used by the framers of the US). It is a two level system. The first level has to admit any and all ideas for consideration (to avoid dogma and becoming just another belief system). But the dues for "free and open" are that science has built the strongest system of critical thinking in human history to make the next level threshold for "worthy ideas" as high as possible. This really works.

This echoes the split mind of a scientist: willing to experiment with the widest set of ideas we can imagine, then setting the highest standard we can imagine for accepting the idea as true. As Kay goes on to say, this approach is embedded in the fabric of the American mentality for free society and government. This is yet another good reason for all students to learn and appreciate modern science; it's not just about science.

Next, consider this passage that follows soon after:

"Air guitar" is a metaphor for choosing too tiny a subset of a process and fooling oneself that it is the whole thing. ... You say "needs" and I agree, but you are using it to mean the same as "wants", and it is simply not the case that education should necessarily adapt to the "wants" of students. This is where the confusion of education and marketing enters. The marketeers are trying to understand "wants" (and even inject more) and cater to them for a price; real educators are interested in "needs" and are trying to fulfill these needs. Marketeers are not trying to change but to achieve fit; educators are trying to change those they work with. Introducing marketing ideas into educational processes is a disaster in the making.

I've written occasionally about ideas from marketing, from the value of telling the right story to the creating of new programs. I believe those things and think that we in academia can learn a lot from marketers with the right ideas. Further, I don't think that any of this is in conflict with what Kay says here. He and I agree that we should not change our curriculum to cater solely to the perceptions and base desires of our clientele, whether students, industry, or even government. My appeal to marketing for inspiration lies in finding better ways to communicate what we do and offer and in making sure that what we do and offer are in alignment with the long-term viability of the culture. The best companies are in business for the long haul and must stay aligned with the changing needs of the world.

Further, as I am certain Kay will agree based on many of the things he has said about Apple of the 1980s, the very best companies create and sell products that their customers didn't even know they wanted. We in academia might learn something from the Apples of our world about how to provide the liberal and professional education that our students need but don't realize they need. The same goes for convincing state legislatures and industry when they view too short a horizon for what we do.

Like Kay, I want to give my students "real computing" and "real education".

I think it is fitting and proper to talk about these issues on Independence Day in the United States. We depend on education to preserve the democratic system in which we live and the values by which we live. But there's more. Education -- including, perhaps especially, science -- creates freedom in the student. The mind becomes free to think greater thoughts and accomplish greater deeds when it has been empowered with our best ideas. Science is one.