Note: This was originally meant to be published on January 17, but I forgot to remove the draft tag so it never happened. I’m republishing it with today’s date in case someone would be sad that they missed it if it appeared somewhere far below more recent articles.
I had the incredible opportunity to attend a lecture by Don Knuth yesterday. Incredible not because Knuth is a great public speaker – he is clearly experienced; but not mind-blowing11 In fact, toward the end he was noticeably tired, which is very understandable given how much he has accomplished.. The reason I was excited about this opportunity was because it was a chance for me (and the other attendees) to pick his brain with our inane questions. He is incredibly intelligent and has these on-the-spot flash insights about topics he’s not spent any time researching at all, and that is something I admire a lot.
Figure 1: Unfortunately, this was the best picture I managed to get. But I have pics! It did happen!
I got the chance to ask a question, but that’s not what this is about. Someone else asked if Knuth writes literate programs in the order we read them, or if the bulk of the prose is written afterwards. In summary, he really attempts to write all material in the order he thinks of it.
Top-down vs Bottom-up
While answering that question he wanted to clarify what he meant with the top-down and bottom-up22 Not involving alcoholic beverages. approaches to programming.
Why does this matter? Don’t I already know what top-down and bottom-up means?
Sure, I do.
Can I give you a brief definition of them, using only words?
Not until yesterday.
So here’s what I realised as Knuth was talking about it:
- Top-down programming
- You think of ways to subdivide a problem into smaller pieces. This is pretty straight-forward but we can use an example anyway. How can we subdivide the problem of writing an irc client? Maybe we need two components: one to maintain the connection to the server, and another to interface with the user. Obviously, these components need to be subdivided further.
- Bottom-up programming
You think of which language you would like to use to express your solution to the problem – and then you try to guess what fundamental units that language has.
We can keep going with the previous example. For an irc client, a basic unit might be a method that establishes a tcp connection, and one that receives an input string from the user. From these fundamental units, the “words” of our language, we can construct more complicated procedures (“phrases”) that, e.g. sets up the irc connection in full, including asking the user for their username.
So that was satisfying.