Wednesday, February 2, 2011

Programming and proofs

This post talks about two completely different topics, then tries to merge them together.

How to Solve It

First I want to talk about How to Solve It by G. Polya. This book was recommended on the forums at Topcoder several years ago, and it was one of the most important things I got from participating at that site. (Besides relearning a bunch of algorithms I hadn't seen in a long time, and getting much more comfortable with the STL, and …)

This book talks about teaching math, and how to help students learn to solve the problems themselves. In part of the book, Polya mentions that for some hard problems, first the student must get a general idea of the "big steps" that are needed to solve the problem. Once she thinks the big steps look promising, then she can start working out the details.

I wish I had this book in college. Another important lesson in the book is that the most important step in solving a problem is review. Figure out what lessons you learned, what you could have done differently, and seek out new uses for what you learned.

Great Programmers

Next, I want to talk about great programmers.

When I read stuff by Donald Knuth, Philip Wadler, Peter Norvig, or any other number of super programmers, I feel ashamed of how I program. I don't sit down, think a lot, and then spew the well thought out code that these people seem too. Of course a lot of their published work is not first drafts, and they have had a lot of time to edit, and think things through again. Reading their papers though, surely makes it seem like they don't hack through things the way I do. Knuth certainly didn't when he was using punch cards.

Even in the normal world of mortal programmers, several coworkers of mine have mentioned how much better they used to be when they had to batch compile everything. They were far more careful to get things right before they attempted to compile. I blushed a little while they were saying it because I was running M-x compile just to see if I had the syntax right on an STL iterator.

I am not trying to argue against the merits of a REPL loop, or a very fast code-compile-test iteration. I love both of those. I just realize how human I am compared to some of my programming heros.

A Hasty Conclusion

Working on some ugly problems, I realized something. I cannot program exactly the way that Polya recommends I do a math proof. With a program, I often cannot be sure the big parts will work together until I try them together. Also, with a program, the small parts are code. So, in some cases, I have to have the small parts (code) working before I can see if the big parts work together.

That goes too far of course. In many cases, I could be much more careful in my thinking about the large parts of the program before I spend too much time on code. But I think I can relax some, and realize that I cannot always be sure that my design for a program is correct until I try it out.

As a corollary, just because my program isn't working as I had hoped doesn't mean that the big parts are wrong. In the AI contest, several times I had good ideas, but buggy code. With a lack of sleep, and too much excitement to push out new ideas, I lost my bearings a little and forgot that I should use a minimum of care when I was programming.

All three names I mentioned above, as well as many of the Haskell writers, all follow some steps I would be well off to imitate. If I could just stop for a moment, think about what I am trying to do, what I expect my solution to accomplish, and what properties I think both the problem and solution have, I should be a much better programmer than I am today.

A little more evidence

The winner of the Google AI contest, Gabor Melis, did a webinar. He talked about thinking things through, working out the ideas in his head, establishing some principles for his solution, and then coding it. He mentioned that you must test and debug the code before you give up on the design, because a bug may make you abandon a good idea.

This is more evidence that I am not careful enough when I code, and it is an extra push that it is ok to think things through before writing code.

I won't be emitting code that looks like proofs, but maybe I can spend some more time thinking instead of debugging. I have come full circle here… my intent was to say that hacking things out was needed, because the code is the proof. Instead, I think I could profit from being a bit more careful with what I do.

Something that has held me back is that I am good at the way I work now. There is always room to improve though.

No comments: