Knuth, goto, Python, and OOP
April 2009
The year was 1973. Real programmers were still using punch-cards and Pascal. C had barely been invented, and object-oriented programming was hardly a twinkle even in the eyes of top computer scientists. Whether or not to use goto was the hot topic of the day.
Knuth
It was then that Donald Knuth wrote his famous essay Structured Programming with go to Statements. And some essay it is: he covers everything from the current trends on structured programming to premature optimization being the root of all evil. (I read it in Literate Programming, but it’s also available as a scanned PDF here.)
He’s responding to Edsger Dijkstra’s well-known letter Go To Statement Considered Harmful, but (in typical Knuth fashion) he covers so much related ground it’s not funny.
What was striking to me is the context of his discussion. It’s clear that structured programming — which we use every day and think is “common sense” — had to be invented, discussed, and refined. Like most inventions, it’s obvious … 36 years later.
goto
It’s also obvious that goto (or “go to” as Knuth calls it) was much more widely used and abused than it is today. This is probably partly because assembly language was so much more common, but also because “they” had to learn that goto isn’t usually the right abstraction — in fact, it isn’t much of an abstraction at all.
Now it’s 2009, and goto is pretty rare. It’s still used, of course, but I’ve usually seen it only in the cases Knuth is talking about: for efficiency, error exits, and for breaking out of certain kinds of loops.
In C you still occassionally need it for cleaning up before error exits, or for breaking out of efficient nested loops, or in generated code, but these days we also have other constructs and other languages that solve 1973’s problems most of the time.
In C, you have the invaluable break as well as the ability to return early. Knuth advocated the equivalent of C’s break, implying also that most languages at the time didn’t have it.
Compilers are also somewhat better at producing optimized code from non-gotoed source: for example, I can program my virtual machine’s opcode dispatcher as a bunch of case statements, knowing the compiler will probably optimize it into a jump table.
And in most modern high-level languages (C++ and up) you have exceptions, which eliminate the need for error-exit gotos, as well as solve several other problems in a really tidy way.
Python
Python is important in this discussion not only because Knuth is keen on beautiful code, but because Knuth “predicted” its arrival in several different ways. Here’s a quote from the last section of his essay:
It seems clear that languages somewhat different from those in existence today would enhance the preparation of structured programs. We will perhaps eventually be writing only small modules which are identified by name as they are used to build larger ones, so that devices like indentation, rather than delimiters, might become feasible for expressing local structure in the source language.
Of course, many languages now have “small modules which are identified by name as they are used to build larger ones”, but Python really took Knuth seriously about using indentation as a delimiter.
What’s more, you can always add goto to Python if you really need it. :-)
OOP
And it gets even more interesting when he goes on to say:
Although our examples don’t indicate this, it turns out that a given level of abstraction often involves several related routines and data definitions; for example, when we decide to represent a table in a certain way, we simultaneously want to specify the routines for storing and fetching information from that table. The next generation of languages will probably take into account such related routines.
Correct me if I’m wrong, but doesn’t that sound awfully like OOP? So in a single essay apparently about goto statements, Knuth predicted modules, Python’s use of indentation as delimiters, and object-oriented programming. :-)
Comments
Marius 9 Apr 2009, 21:24
object-oriented programming was hardly a twinkle even in the eyes of top computer scientists
Object oriented programming was invented by Simula in the 1960’s and standardized in 1967.
Jason Dusek 10 Apr 2009, 00:16
“several related routines and data definitions” sounds like typed programming to me.
How can you in good faith propose that Knuth predicted Python’s arrival with indentation and small modules, features that are hardly unique to it? You might as well have said that Knuth predicted Haskell. His prediction would be mighty flexible in that case!
How can you talk about indentation without mentioning Landin’s ISWIM (1966)?
Alexander Fairley 10 Apr 2009, 03:11
That’s the way that interpreting prophecy works, Jason. Whatever you have done, claim the prophet foretold it :P .
Ben 10 Apr 2009, 07:53
Marius, as I mentioned on prog.reddit: I knew about Simula (’67, no less). However, Knuth and other “top computer scientists” don’t seem to talk about it. Perhaps it wasn’t well-known in the U.S. by 1973. Perhaps OOP was known and used, but not by that name.
Jason, about the “prediction” of Python: I was being fairly tongue-in-cheek about the modules and OOP, hence the quotes around my first “prediction”. (I’ve added a smiley at the end to clarify.) However, I think the indentation thing is quite striking — more or less a prophecy.
Here’s an article by Jeremy Hylton about Python, Knuth and indentation which also mentions Landin’s ISWIM: Using indentation to represent program structure
Marius 13 Apr 2009, 08:07
I hate to be the nitpicker here, but I searched for “knuth” and “Simula” and got this paper :-)
http://www.tug.org/TUGboat/Articles/tb23-3-4/tb75knuth.pdf
Quote:
“Professor Knuth has a long-lasting and close relationship relationship to Norway. In ’67 he came to an IFIP conference in Oslo where, among other things, SIMULA67 was presented. He spent the academic year ’72–73 at the Univerity of Oslo, and this visit was influential for further development of computer science in Norway.”
Ben 14 Apr 2009, 08:13
Thanks Marius, that’s very interesting. I definitely stand corrected about it not being well-known in the U.S., particularly by Knuth. I still wonder why he doesn’t mention it in his discussion of structured programming. Do you know when the term “object-oriented programming” was invented, or came into common usage?
Marius 15 Apr 2009, 08:21
I don’t know, but I know that it was used when describing Smalltalk.
Gremnebulin 14 Feb 2011, 05:42
Occam used indentation a decade before Python.