{"id":283,"date":"2009-08-27T04:23:22","date_gmt":"2009-08-27T04:23:22","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2009\/08\/27\/knuth-on-go-to-1974\/"},"modified":"2016-11-27T07:18:36","modified_gmt":"2016-11-27T12:18:36","slug":"knuth-on-go-to-1974","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2009\/08\/27\/knuth-on-go-to-1974\/","title":{"rendered":"Knuth on go to – 1974"},"content":{"rendered":"

\r\nEarlier this year, Perl programmer and author Mark Jason Dominus<\/a> mentioned in an e-mail list that the 1974 paper \"Structured Programming with go to<\/strong> Statements,\" by Donald E. Knuth, was one of his favorite computer science papers. I printed a copy and have been carrying it in my briefcase, unread, since then. I finally got a chance to read it on an airplane this week. I found it to be amazingly informative and entertaining, and I wanted to share a bit of it with you.\r\n<\/p>\r\n\r\n

\r\nBy the time I encountered Fortran 77 in my freshman year at Georgia Tech in 1982, the transition to structured programming was pretty much a done deal. Also, since I was in electrical engineering and not computer science, I did not learn anything at the time about the evolution of programming languages. So I was fascinated to read Knuth's perspective on the transition to structured programming, written as the transition was happening. I was also very interested to see how many themes that still concern and guide software developers today are mentioned by Knuth in this 1974 paper.\r\n<\/p>\r\n\r\n

\r\nKnuth discusses in detail various techniques for eliminating go to<\/strong> statements in some illustrative algorithms, considering efficiency, readability, safety, etc. He looks at mechanical transformation techniques and compares proposed programming language features such as event indicators and different looping constructs. He considers a case involving multiway branching where he regards the go to<\/strong> as beneficial.\r\n<\/p>\r\n\r\n

\r\nBut his remarkable collection of asides and almost parenthetical observations fascinates me the most. Let me share a few choice bits with you.\r\n<\/p>\r\n\r\n

\r\nKnuth introduces his paper with three quotes:\r\n<\/p>\r\n\r\n

\r\nYou may go when you will go, And I will stay behind. —Edna St. Vincent Millay
\r\nMost likely you go your way and I'll go mine. —Song title by Bob Dylan
\r\nDo you suffer from painful elimination? —Advertisement, J. B. Williams Co.\r\n<\/blockquote>\r\n\r\n

\r\nKnuth on the sometimes heated nature of the go to<\/strong> discussions:\r\n<\/p>\r\n\r\n

\r\nIn fact, the discussion has apparently caused some people to feel threatened; Dijkstra once told me that he actually received \"a torrent of abusive letters\" after publication of his article.\r\n<\/blockquote>\r\n\r\n

\r\nI was curiously comforted to discover that even legendary programmers can have trouble adjusting to new ideas:\r\n<\/p>\r\n\r\n

\r\nI remember feeling frustrated on several occasions, at not seeing how to write programs in the new style; I would run to Bob Floyd's office asking for help, and he usually showed me what to do.\r\n<\/blockquote>\r\n\r\n

\r\nKnuth on some proposed alternatives to go to<\/strong> that don't really change anything:\r\n<\/p>\r\n\r\n

\r\nOther go to<\/strong>-less languages for system programming have similarly introduced other statements which provide \"equally powerful\" alternative ways to jump. In other words, it seems that there is widespread agreement that go to<\/strong> statements are harmful, yet programmers and language designers still feel the need for some euphemism that \"goes to\" without saying go to<\/strong>.\r\n<\/blockquote>\r\n\r\n

\r\nKnuth's famous quote about premature optimization in context:\r\n<\/p>\r\n\r\n

\r\nThere is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
\r\nYet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail.\r\n<\/blockquote>\r\n\r\n

\r\nOn avoiding code duplication:\r\n<\/p>\r\n\r\n

\r\n[Copying common code] would be a pointless waste of energy just to eliminate a perfectly understandable go to<\/strong> statement: the resulting program would actually be harder to maintain than the former, since the action of printing a character now appears in two difference places.\r\n<\/blockquote>\r\n\r\n

\r\nOn a pitfall of code comments:\r\n<\/p>\r\n\r\n

\r\nAccompanying comments explain the program, [but] it is easy to make mistakes, partly because we rely so much on comments which might possibly be inaccurate descriptions of what the program really does.\r\n<\/blockquote>\r\n\r\n

\r\nSkepticism of quantitative metrics:\r\n<\/p>\r\n\r\n

\r\nBut there has been far too much emphasis on go to<\/strong> elimination instead of the really important issues; people have a natural tendency to set up an easily understood quantitative goal like the abolishment of jumps, instead of working directly for a qualitative goal like good program structure.\r\n<\/blockquote>\r\n\r\n

\r\nProgramming puns about the 1960s:\r\n<\/p>\r\n\r\n

\r\nI discussed [a] weakness of ALGOL in a letter to Niklaus Wirth in 1967, and he proposed two solutions to the problem, together with many other instructive ideas in an unpublished report on basic concepts of programming languages. His first suggestion was to write
\r\n  repeat begin S; when B exit; T; end<\/strong>
\r\nand readers who remember 1967 will also appreciate his second suggestion,
\r\n  turn on begin S; when B drop out; T; end<\/strong>\r\n<\/blockquote>\r\n\r\n

\r\nOn teaching programming:\r\n<\/p>\r\n\r\n

\r\nI have always felt that the transformation from recursion to iteration is one of the most fundamental concepts of computer science, and that a student should learn about it at about the same time he is studying data structures. [...] It surprises me that the literature on recursion removal is primarily concerned with \"baby\" examples like computing factorials or reversing lists [...]\r\n<\/blockquote>\r\n\r\n

\r\nOn table-driven logic:\r\n<\/p>\r\n\r\n

\r\nMultiway branching is an important programming technique which is all too often replaced by an inefficient sequence of if<\/strong> tests. Peter Naur recently wrote me that he considers the use of tables to control program flow as a basic idea of computer science that has been nearly forgotten; but he expects it will be ripe for rediscovery any day now. It is the key to efficiency in all the best compilers I have discovered.\r\n<\/blockquote>\r\n\r\n

\r\nOn flowcharts:\r\n<\/p>\r\n\r\n

\r\nAs an undergraduate, in 1959, I published an octopus flowchart which I sincerely hope is the most horribly complicated that will ever appear in print; anyone who believes that flowcharts are the best way to understand program flow is urged to look at this example.\r\n<\/blockquote>\r\n\r\n

\r\nAnd finally, I learned that the joke about using come from<\/strong> instead of go to<\/strong> dates back to at least R. Lawrence Clark in 1973.\r\n<\/p>\r\n\r\n

\r\nIf you ask me about the possibility of go to<\/strong> in MATLAB, I'll simply direct you to Loren's April 1 2006 post on the subject<\/a>.\r\n<\/p>","protected":false},"excerpt":{"rendered":"

\r\nEarlier this year, Perl programmer and author Mark Jason Dominus mentioned in an e-mail list that the 1974 paper \"Structured Programming with go to Statements,\" by Donald E. Knuth, was one of his... read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/283"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/comments?post=283"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/283\/revisions"}],"predecessor-version":[{"id":2412,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/283\/revisions\/2412"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=283"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=283"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=283"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}