Except Donald Knuth is 7’ tall.

Judge me by my size do you?

What NYT thinks devs are doing in Silicon Valley: AI and machine learning hacking in VR 3D

What devs are really doing in Silicon Valley: debugging yet another "undefined is not an function"

Most of programming is just moving shit around; not interesting mathematics like knuth has done

We're 21st century plumbers.

We're 21st century plumbers.

I tell people this all the time when they ask what I do. I've met quite a few master plumbers, and they are extremely intelligent technical geniuses for the most part. I'm completely convinced that I would have been one of them (or some other trade craft) if I were born 50 years ago.

- IT: Sanitation engineers

- Developers: Hazmat engineers

- CS: Civil engineers

Sounds accurate to me, but I'm interested if people will downvote you because they don't like the IT line.

Hmpf, considering that the author spent a whole day with Knuth there is disappointingly little interviewing going on. Other people (e.g. Norvig) are quoted more extensively.

At Knuth's current age-related physical state, he probably didn't say much over the course of a day.

Ok, so this journalist gets to spend WHOLE day with Knuth and all we get is some bits of history and quotes from couple of Google guys. Massively lost opportunity to provide window in this legends daily life, thoughts and habits...

At age 19, Dr. Knuth published his first technical paper, “The Potrzebie System of Weights and Measures,” in Mad magazine.

I'd say she did something positive with the opportunity.

I have a copy of the issue, so when I went to see one of his Christmas Tree Lectures a few years ago I took it with me to get signed after the talk.

Instead of just signing it, he opened to his article and corrected a typo in the Potrzebie article--I think it amounted to two numbers being transposed somewhere around the millionths place (My copy is packed away from a recent move so it's not too convenient to verify).

What was funny was he had a poem he used to remember the order of the numbers after the decimal. He couldn't quite remember it, so he ssh'd into his home machine (or University, dunno), fired up Emacs, and opened a file containing the poem. Then he corrected the typo.

And that's how Donald Knuth "signed" my copy.

+1 I was behind you in this line and can confirm this story :-) He was surprised someone brought this and IIRC asked you how you got hold of this MAD magazine issue. I remember him not wanting to sign without fixing the typo, and also ssh-ing to find the correct numbers after he wasn't sure he remembered them.

Taking the opportunity to post the video of Knuth mishearing the question "What makes a good teacher?" as "What makes a good T-shirt?" at my uni.

https://youtu.be/74BfHoE66rc?t=42m17s

I wish the guy would have let him answer as to what the CompSci equivalent of that T-Shirt is.

I lived in Sweden for a while, Swedes are very proficient in English. Yet, they almost always pronounce ch as sh. They even have TV ads that make fun of this.

My favorite Knuth story, attributed to Alan Kay (if you're around, would love confirmation):

When I was at Stanford with the AI project [in the late 1960s] one of the things we used to do every Thanksgiving is have a computer programming contest with people on research projects in the Bay area. The prize I think was a turkey.

[John] McCarthy used to make up the problems. The one year that Knuth entered this, he won both the fastest time getting the program running and he also won the fastest execution of the algorithm. He did it on the worst system with remote batch called the Wilbur system. And he basically beat the shit out of everyone.

And they asked him, "How could you possibly do this?" And he answered, "When I learned to program, you were lucky if you got five minutes with the machine a day. If you wanted to get the program going, it just had to be written right. So people just learned to program like it was carving stone. You sort of have to sidle up to it. That's how I learned to program."

[0] http://www.softpanorama.org/People/Knuth/index.shtml

There's another interesting story about Knuth that's worth repeating here.

http://www.leancrew.com/all-this/2011/12/more-shell-less-egg...

The tl;dr is that Knuth wrote an elaborate implementation of a program to solve a particular problem, and Doug McIlroy replaced it entirely with a six step shell pipeline. (Knuth's program was written using his literate programming tools, could be typeset in TeX, and involved some precise work with data structures and algorithms.)

I love this story as an example both of Knuth's genius and perspective, but also as a way to show what his level of dedication can achieve. It's an amazing intellectual accomplishment.

I also love this story as a demonstration what those of us without that skill and dedication can achieve using the advancements built on the work of Knuth and others.

I love that story, although I think the takeaway needs to be slightly updated. It's quite possible that a sorted word count was easiest to do with bash and unix utilities in 1992. Now, it's easier and more comprehensible in your favorite scripting language (which I'm assuming isn't bash).

The real lesson is to program using the most powerful tools at your disposal.

That's a good lesson, but we shouldn't stop there. Knuth is a computer scientist, but also an artist: writer, musician, typographer, and creative programmer. His insights into programming-as-literature have infused an often-soulless industry with something soulful. He began with the popular notion that programming should be a creative, playful act, and tried to elevate mere playfulness into the realm of fine art. An incredible detour in an amazing career, and an enriching lesson of a different kind.

It's quite possible that a sorted word count was easiest to do with bash and unix utilities in 1992. Now, it's easier and more comprehensible in your favorite scripting language

It'd be interesting to see how true this is in reality. I'm not at all convinced that most scripting languages can do this quite as concisely as bash and the Unix userland. (But, being honest, this problem seems very well aligned to that tooling's strenghts.)

Well, what is easy or comprehensible isn't necessarily concise. Bash is great for code golf but I know few people who prefer to code in it.

It is easy to do in your favorite scripting language. But is unlikely to be as short. Comprehensibility is in the eye of the beholder.

Here is a Perl solution for comparison.

    use strict;
    use warnings;

    my $limit = shift @ARGV;

    my %count;
    for my $line (<>) {
        while ($line =~ /(\w+)/g) {
            $count{lc $1}++;
        }
    }

    @words = sort {$count{$b} <=> $count{$a} or $a cmp $b} keys %count;
    $limit = @words if @words < $limit;
    print "$_\t$count{$_}\n" for @words[0..($limit-1)];

Python is relatively short, batteries included and all that:

  import re
  import sys
  import collections
  
  words = re.findall('[a-z]+', sys.stdin.read().lower())
  c = collections.Counter(words)
  for word, count in c.most_common(int(sys.argv[1])):
      print(f'{count:>7} {word}')

Three times the character count of the Unix pipe version, but IMHO a lot more readable (and generalisable).

You don't want to read all input into memory first.

Just for reference: a Perl 6 version:

    sub MAIN($limit = Inf) {
        my %bag is Bag = words.map(&lc);
        say "{.key}\t{.value}" for %bag.sort( {
          $^b.value cmp $^a.value || $^a.key cmp $^b.key
        } )[^$limit]
    }

And for what it's worth, the `words` function is lazy, so it won't read all of the words into memory first.

There is no bash (or any scripting) involved, the complete command from the article is:

  tr -cs A-Za-z '\n' |
  tr A-Z a-z |
  sort |
  uniq -c |
  sort -rn |
  sed ${1}q

The real benefit is that each is a single command that is easy to test in isolation and it's multi-process. That's not possible in most scripting languages.

McIlroy literally calls it a script in his review (notice the ${1}).

Nothing prevents you from unit testing in scripting languages. Multi-process, sure, but most people aren't looking for that.

McIlroy literally calls it a script in his review (notice the ${1}).

Ok, there's a single shell substitution, if it was fixed would you still call it a script? Technically the result of that is itself a sed script "3q", but if you count either of those then there isn't a lot of wiggle room between script and command, the arguments to tr are by far the most complex "script" involved.

Nothing prevents you from unit testing in scripting languages.

That is a world away from what I'm talking about. Each line of that command can be executed on the CLI in isolation, you'd be replicating a lot more in nearly any scripting language, except maybe perl and awk.

Multi-process, sure, but most people aren't looking for that.

Neither am I generally, still quite nice when you get it for free though.

That's a good one. It's one of the classic examples of the Unix philosophy and how pipelines can be powerful, although of course not applicable in all cases, and they have their issues too - which often becomes an argument on HN (about text streams vs. object pipes a la PowerShell, etc.).

I had seen it a while ago and blogged about it here, with solutions (approx.) in Python and shell:

The Bentley-Knuth problem and solutions:

https://jugad2.blogspot.com/2012/07/the-bentley-knuth-proble...

Also, previous HN thread about it here:

Revisiting Knuth and McIlroy's word count programs (2011) (franklinchen.com)

https://news.ycombinator.com/item?id=15264997

There is also the book "Exercises in Programming Style" that uses the term frequency problem to illustrate 33 different programming paradigms (including a shell solution).

https://www.amazon.com/Exercises-Programming-Style-Cristina-...

That was quite unfair criticism, and even Doug McIlroy knew it (as he admitted later). The background is this:

- Bentley, the author of the column, invited Knuth to demonstrate literate programming using a program of his choice.

- Knuth insisted that to be fair, Bentley ought to specify the program to be written; else someone might object that Knuth chose a program that would be good for literate programming.

- Bentley chose (what we'd now call) the term frequency problem (list the top k most frequent words in a text file), and accordingly Knuth wrote a system program for solving just this one particular task. (Did everything from opening the input file to formatting the output, etc.)

- Doug McIlroy was asked to “review” this program, the way works of literature are reviewed. He happens to be the inventor of Unix pipes. Towards the end of his review, along with many other points (e.g. Knuth didn't include diagrams in cases where most of us would appreciate them, something I still struggle with when reading TeX and other programs), he used the opportunity to demonstrate his own invention, a shell pipeline using now-standard Unix tools (tr, sort, uniq, sed).

There are a few things wrong with this criticism:

- The main thing is that DEK wrote the program he was asked to write, so pointing out that he shouldn't have written that program is a criticism of the one who chose the program (Bentley mentioned this when printing McIlroy's review).

- At the time, Unix wasn't even widely available outside Bell Labs and a few places; it definitely wasn't available to Knuth or most of the column's readers.

- Knuth's program, fine-tuned for the task, is more efficient than the shell pipeline.

- Even if you use a shell pipeline, someone has to write the “standard” programs that go into it (the "tr", "sort", "uniq" and "sed" above), and literate programming can be used there. In fact, Knuth did exactly that a few years later, rewriting Unix's “wc” (IIRC) and compared the resulting program with that of Sun Unix's wc, and his LP version had, among things, better error handling. (He's explained it by saying that in conventional programming, if you have a small function and 90% of it is error-checking, it looks like the function is “about” error-checking, so there's a psychological resistance to doing too much of that, while with LP you move the error-handling to a separate section entirely about error-checking and then you tend to do a better job. BTW, TeX's error handling is phenomenally good IMO; the opposite of the situation with LaTeX.)

All that said, there is some valid criticism that Knuth prefers to write monolithic programs, but that works for him. He seems not to consider it a problem that to change something you have to understand more-or-less the entire program; he seems to prefer doing that anyway (he reads other people's code a lot: in Peter Seibel's Coders at Work, he was the only person interviewed who read others' programs regularly).

re: At the time, Unix wasn't even widely available outside Bell Labs and a few places; it definitely wasn't available to Knuth or most of the column's readers.

At that time, 1986, Unix was widely available - there were more than 100k Unix installations around the world by 1984. AT&T Unix Sys V and UCB 4.3bsd were available. Knuth was friendly with McIlroy, who was head of the Bell Labs computer science research group that begat Unix. Sun Microsystems was formed in 1982 - their boxes ran Unix, and Sun was a startup spun off from Stanford.

OK, Unix was probably available to Knuth, but the task given to Knuth was not to promote any already written programs! Had he done so it would be claimed that he missed to do what was requested of him to do.

Even today, if you would get the exactly same task, with the goal to make the most efficient solution when you have to care about the limitations of hardware available to you and to produce the self contained program (e.g. because your algorithm should run with hundreds of billions of words of input) you'd still at the end probably produce something closer to what Knuth did then what McIlroy did.

Which doesn't mean that it's not brilliant. But it's also not obvious, i.e. not something a "normal user" would "know":

- even if you knew that "tr command translates the characters to characters" did you know that you could (and must) write

   tr -cs A-Za-z'
   '

to perform the first operation from 6? What the -c does? What the -s does? That you could and even had to form the command line to contain the newline? I bet a lot of Unix users of today would still not know that one.

- did you know what the fifth line was supposed to do "sort -rn" Would you know that you're to sort "numerically" (-n) and that it would "work"?

- "sed ${1}q" how many people even today would know that one?

And after all that, the first of two sorts needs to sort the file that is as big as the original input! If you have hundreds of gigabytes of input, you'd have to have at least that much more just to sort it. McIlroy's approach is a good one for one-off program or not too big input processing, and if you knew that you can use these commands as he used them. But it's still not "a program" in the same sense a Knuth's program is.

Knuth's algorithm would, unsurprisingly, handle the huge inputs orders of magnitude more efficiently. And that is what McIlroy was aware of and intentionally hand-waved it in his "critique." Read the original text:

https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/pearls-...

But the major point is still: Knuth's task was not "use the existing programs" (or libraries) but "write a program" that does what's said to be done: The fair comparison would then include the source of all the sort, uniq, tr etc. programs which McIlroy used.

And once that is being done, McIlroy's code would still be both less readable, less efficient and worse overall.

Which on the other side also doesn't mean that for some purposes "worse" isn't "better": https://yosefk.com/blog/what-worse-is-better-vs-the-right-th... But for some purposes, on "better" works and "worse" simply doesn't, e.g. when the scale of the problem is big enough. And Knuth teaches us how to solve such, harder problems. And presents the complete solution v.s. doing tricks (just call that library/executable which I'm going to avoid to explain you how it is implemented and what its limitations really are).

And giving the misunderstanding in the difference between showing how something is implemented (most efficiently) and that "just use pre-written tool X" approach, I understand even more why Knuth uses assembly in his "The Art of Computer Programming" books.

But it's also not obvious, i.e. not something a "normal user" would "know":

- even if you knew that "tr command translates... "sed ${1}q" how many people even today would know that one?

Are you suggesting it's ever been more likely for people to understand how to manage a trie structure in Pascal than use Unix command line tools? Or look flags up in the manpages?

Personally speaking, I'm comfortable doing both, but can't imagine many scenarios where I'd rather have ten pages of a custom datastructure than six lines of shell. (And they all involve either high volumes of data or situations where I can't easily get to the process-level tools.)

The fair comparison would then include the source of all the sort, uniq, tr etc. programs which McIlroy used.

If you're including the code that provides the surface abstractions, where do you draw that line? If the code for sort, uniq, etc. is fair game, why not the code for the shell that provides the pipelining, the underlying OS, the file system, the firmware on the disk? After all, who's to say that the programs in the pipeline don't just run one after another with temporary files written to disk, rather than in parallel? (Which I've seen happen in reality.)

The same is true for the other side, of course. The 'fair comparison' could easily require Knuth's solution to include the source for weave/tangle, TeX/Metafont/CMR, the OS, etc.

And once that is being done, McIlroy's code would still be both less readable, less efficient and worse overall.

What definition of 'worse' are you using?

* I expect sort/uniq/tr/sed to be more well tested and understood than a bespoke program.

* If there are issues with the program, it'll be easier to find skills/time to maintain a shell pipeline than custom trie-balancing code written in Pascal. (Sitting aside a prose description of the same.)

* The shell pipeline runs on a machine that can be found in a retail store today, rather than requiring an elaborate download/build process.

* It's possible that the custom solution runs faster, but not obvious without testing. (None of which is worthwhile outside of demonstrated need.)

Point being: it's very easy to find a definition of 'worse' that applies more to the custom solution than to the pipeline.

The shell pipeline runs on a machine that can be found in a retail store today, rather than requiring an elaborate download/build process.

That argument points to the fact that your “view” of the whole topic changes the assumed definition of the problem that was given to Knuth to solve. Read once again the original text: he was supposed to illustrate how the “Literate programming” could be ised while writing a program which solves a given program. It was definitely not “write an example of calling the existing pre-written programs”.

And, of course, it was all in 1986, definitely not “to target the machine which can be found in the retail store in 2018.”

McIlroy already behaved as the goal had been different than it was.

McIlroy already behaved as the goal had been different than it was.

How would you feel about McIlroy's solution if it was semantically exactly the same, but written in a literate approach? (Essentially a version of 'weave/tangle', but for shell scripts.)

McIlroy's critique is both astute on it's own yet perhaps not relevant in the context of what Knuth had been asked to do, namely present an example of literate programming. That's not to say the McIlroy's script can't have a literate form, only that it wouldn't serve as a good exemplar.

It all serves as a good reminder of how Knuth's work should be used & viewed: It shouldn't be taken as insight into how to manage and develop for software projects. It's more useful as teaching tools for how to think about solving problems. In my mind it's the difference between "pure" science and practical engineering, though I'm not sure that's a perfect analogy.

To try another analogy, it's like Knuth was asked to make a custom set of clothes. And McIlroy's critique seems like saying "Not everyone can afford custom made clothes, and the GAP produces perfectly serviceable clothes that are far more practical in most situations" It's correct, sure, but rather besides the point in the context of the original request.

Yes, I love this story too. It really demonstrates so much. And oh, the hackles it raises. :)

I once had to write a program for a class didn't have access to a compiler. I wrote it all in notepad and double checked everything more thoroughly than I ever would have done otherwise. When I got the computer lab the compiler found one or two type-o's and the program ran perfectly the first time. The experience changed how I write code. It's worth trying out at least one time.

I used to sit in my grade 12 English class working out polygon fill-and-shade routines on graph paper instead of whatever nonsense Shakespeare we were going through at the time.

Worked out really well for me - I'm employed well as a programmer, and I got to come to Shakespeare basically fresh when I was old enough to actually appreciate the work.

How old is that? I'm over 50 and I still can't get into Shakespeare. Watching a performance is OK, though not something I'd choose to do on my own, but reading the plays? Can't get into it at all.

Have you tried an annotated one? Shakespeare is full of, essentially, in-jokes and memes from the 1500s. There is a ton of depth in his writing that you'll totally miss if you don't know all of that context.

Try the "Sonetts" instead of the plays!

To me, this is one way to show evidence of mastery of an engineering discipline: The ability to do it once and have it come out right. If you asked a modern software engineer who's used to fast modern tools, they'd tell you this was impossible. Everyone's pretty much settled into this kind of workflow:

Write -> Compile -> Fix Compile Errors -> Compile -> Fix Compile Errors -> Compile -> Fix Compile Errors -> Compile -> Run -> Fix Runtime Bugs -> Compile -> Run -> Fix Runtime Bugs -> Compile -> Run -> Fix Runtime Bugs -> Compile -> Run -> Fix Runtime Bugs -> Compile -> Run -> Fix Runtime Bugs -> Git Push and Pray

With maybe a few "Write Unit Tests" steps intermixed. Totally different mentality. Is it really a faster or more productive way to work?

Do you really encounter compiler errors that frequently? The compiler stopped barking at me for the most part after my first year or two.

During big refactorings, I admit I sometimes find myself relying on compiler errors as a crutch to find (for example) which API layer I haven’t added the parameter to yet.

I’ll also rely heavily on my IDE’s function signature completion, to remind me whether some method I’m calling takes an int or an unsigned int, rather than have it memorized like I used to.

This might be why a lot of people (including me) hate whiteboard-coding interviews: we’ve gotten so spoiled by our tools that we can’t code without them!

During big refactorings, I admit I sometimes find myself relying on compiler errors as a crutch to find (for example) which API layer I haven’t added the parameter to yet.

That's not a 'crutch' - it's literally what those compiler errors are for! The alternative would be for the compiler to do something non-sensical, which would error out at runtime.

And when it comes to white-board coding, you should arguably be using pseudo-code anyway - your goal is then not to come up with something that will run, but to convince your interviewer that the code is 'morally' correct and that any subsequent fixes are well within your skill level.

My biggest problem with whiteboard coding is writing text in straight lines. You never realize how much of a liability being left handed is until someone asks you to do whiteboard coding (ya, many lefties train for this, but some don’t).

Computers have been a godsend for my penmenship. On the other hand, I guess I relied on them too much as a kid.

I thought lefties learn to read and write backwards and then mirror the final result before submission.

This might be why a lot of people (including me) hate whiteboard-coding interviews: we’ve gotten so spoiled by our tools that we can’t code without them!

Isn't that like someone saying they've gotten so spoiled by training wheels, they can't ride a bike without them? It's not like I'm one to talk 100% of the time. I think I couldn't get my company's project to build, without a few weeks of reading and understanding a lot more of the build system. However, I've also coded on an 8 bit machine by flipping 8 switches and pressing a commit button for each byte.

It's a worthwhile exercise to do some coding with nothing but a text editor and a debugger once in a while. That isn't going 100% to the bare metal, but it's a level that's very worthwhile for working on basic skills. Entire programming education books have been based on this idea.

The difference is that training wheels are intended to be a temporary assistance until you've learned to operate without them, while development tools are meant to be a productivity boost. If you're working with a toolchain and aren't leaning on it, you're not working to your full potential.

Whether being able to work without the chain is also important is an independent issue. (I happen to prefer vim+scripting languages over IDEs+compiled. But I recognize it as a personal preference, and not a question of moral superiority.)

The difference is that training wheels are intended to be a temporary assistance until you've learned to operate without them, while development tools are meant to be a productivity boost.

Right, but pro cyclists don't say they couldn't do it without piece of equipment X. X is just a performance boost. Some coders say they couldn't practically do it at all without X. There would be a big difference in fitness between a commuter being unable to make a certain trip without a motor assist, and a rider who could do the same trip without the motor assist. I think most would look askance at a "pro" in the 1st category.

If you're working with a toolchain and aren't leaning on it, you're not working to your full potential.

Yes, but you need to be wary that you're using the toolchain for its intended purpose. The toolchain is supposed to be saving you typing and lookup time. It's not supposed to be substituting for your actual understanding of the code. The former is a good thing, and you should be good at using the tool for that. The latter is a bad thing, and you shouldn't be doing that. By working out with nothing but an editor sometimes, you can work out in a way that guards against that.

No football player plays actual games running through tires, but the exercise is apparently helpful.

But I recognize it as a personal preference, and not a question of moral superiority.

It's not moral superiority. It's using tools as intended and not substituting for understanding.

It's like a lumberjack so used to cutting down trees with a chainsaw that they'd have trouble to put down a decent tree with an axe. Powerful tools do certain subtasks for you, if you expect to use them all the time (and it's a reasonable expectation in your domain), then it makes all sense that you'd forget these subtasks.

It's like manual memory allocation and proper deallocation - been there, done that, but after 10+ years of working with GC languages, I would definitely have some memory leak bugs if I suddenly had to do that again. It is a basic skill, but just as many other basic skills, it's one that you can ignore in most domains.

Yes. A real feedback loop is better than a mental one in your head. “Turn off your targeting computer and use the force, Luke” only works if you hone a lot of mental power into it (like Knuth), but it would have also discouraged a lot more people without that ability from programming at all.

In the past you had to be Hawkeye to program, now most of us just put on our Ironman suit and get on with it.

Nevertheless, the more complete and accurate your picture of what you are attempting to achieve, and where you are, is (at every level of abstraction), the fewer iterations it will take to get done - or the fewer bugs remaining after a given elapsed time.

It's like situational awareness: https://en.wikipedia.org/wiki/Situation_awareness

If we want to go there, modern tooling allows you to forget some of the details you used to care about and focus more on other things, the tooling is rarely comprehensive and there will always be more to consider until the entire programming process is automated.

The difference is other people.

Yes, if you're writing your -own- code, learning to envision what the system must do in your head first is very, very valuable.

When you're on a team, however, you -have- to compartmentalize. You have to create abstractions, black boxes, functionalities that you -could- dive into, but which you will accept only understanding at a contract (interface) level. The skill of envisioning the system is still useful, of course, but there will be black boxes.

The problem that causes, of course, is that every abstraction is leaky. You didn't know that calling this method also fired off this event, and so you -also- triggered that event. Or whatever. Hence, bugs and iteration. You also have to deal with -bad- interfaces, a bajillion parameters, or a parameter object that isn't intuitively obvious how to initialize, and you start having to iterate.

Sort of. I've seen these productivity-enhancing tools used by people who have absolutely no clue what those tools are doing on their behalf produce some nightmares that sort of work sometimes. To get geekier with the analogy, a lot of people are like spiderman (the Tom Holland spiderman) who need to learn to use the powers of their suit before they're given access to the more powerful, more dangerous stuff.

It is much more impressive that Knuth came up with and wrote TeX than that it was bug-free or written all in his head.

Computer time is no longer at a premium and bugs can be fixed.

Useful, creative, and clear solutions usually trump perfectly correct ones, except in special cases such as when life is on the line or you're writing programs to fly to the moon where getting it right the first time is of utmost importance.

When I was a kid, I learned Pascal from a book. We didn't even have a PC at home (it was the 80s) but my mother was a college professor and had access to the mainframe there. I wrote out a whole program to run Conway's Game of Life on a bunch of notebook paper, and one day when I was off from school I came in and typed the whole thing in at a terminal. I ran the command to compile it, and it spit out hundreds of syntax errors. Then it was time to go home.

It was not an auspicious start to my career in computer science.

It was not an auspicious start to my career in computer science.

I'd argue the opposite!

Learning how to "run" code in your head, cover edge cases and invariants, is a great skill to practice. When I was at a hospital after a difficult operation, I used to write down pages and pages of C64 programs in my notebook, too :-)

Even if I never even typed all them out later, I like to think this made me a better programmer. It trains your brain in a way that REPL doesn't.

He did it on the worst system with remote batch called the Wilbur system.

I think you mean WYLBUR.

I had the "opportunity" to work with WYLBUR once in 1993, and I remember it to this day. "the worst system with remote batch" dramatically understates how bad it was. Hearing this raises Knuth even higher in my estimation.

https://en.wikipedia.org/wiki/ORVYL_and_WYLBUR

“Here at Google, sometimes we just throw stuff together,” Dr. Norvig said, during a meeting of the Google Trips team, in Mountain View, Calif. “But other times, if you’re serving billions of users, it’s important to do that efficiently. A 10-per-cent improvement in efficiency can work out to billions of dollars, and in order to get that last level of efficiency, you have to understand what’s going on all the way down.”

I'm interested in this low level systems opimization. What type of jobs hire for this work? What areas in graduate school should one focus in? Is this type of skill set still employable?

Amongst other things, know your hardware.

For example, you could read the C++ spec forwards and backwards for a year and know your data structure big O notation just as well, but they will never tell you that inserting into the middle of a vector is faster than inserting into the middle of a linked list in a great many common cases.

Sure, ideally you'd measure, but you need to have some idea of what options to even compare with your measurements.

I may be missing something here, but your example seems to be a textbook case for big-O analysis. Writing in a vector is O(1), while linked list is O(n), isn’t it?

Writing into a vector is O(n), writing into a LL is O(1), assuming you have an iterator to the location to write to. If you don't, then it becomes O(n), and writing into a vector can be O(1) if you're writing to the end.

C++ stl, LL appending is always O(1) and writing into a vector is O(n). There are plenty of caveats to this and the documentation should be referenced.

He's right btw that insert into a vector is generally faster in the C++ stl than insert into a LL. I don't recall off the top of my head why that is, just remember it's the case.

Data locality is a big reason. Sure, it's O(N) writes, but those writes are neatly lined up in such a way that the likelihood of a cache miss is low. As opposed to a linked list, where just traversing to the middle may entail multiple round trips to main memory.

It's not strictly related to C++ and/or STL. This is how computers work nowadays.

There's a position like that in my company, open to new hires (only bachelor's needed). The goal is to optimize algorithms and data analysis models that run on our HPC cluster. It basically boils down to changing compiler settings and seeing what runs the fastest.

Funny, The NeXT Book by Bruce Webster referred to Knuth as the "Obi Wan of Computer Science".

I guess we can split the difference and agree on Jedi. :-)

Ah but who is the Han Solo of comp Sci?

Linus Torvald

"I was sitting in Steve's office when Lynn Takahashi, Steve's assistant, announced Knuth's arrival. Steve bounced out of his chair, bounded over to the door and extended a welcoming hand.

"It's a pleasure to meet you, Professor Knuth," Steve said. "I've read all of your books."

"You're full of shit," Knuth responded.

http://www.folklore.org/StoryView.py?project=Macintosh&story...

No way; I worked for him from 1978-1986, and never heard him say a naughty word. Also, I tagged along when he went to Apple to meet Jobs, who wanted to show him a late prototype of the Mac, and don’t recall hearing any such thing at the time (and it would have shocked me).

Well the website is called "folklore", so I think your skepticism is well placed. ;)

Is there a way to dispute the story on folklore? drfuch's comment should be appended there.

I've also heard that story with several different people in the place of Jobs (mid 90's it was almost always Bill Gates, for example), making me believe it to be apocryphal.

Perhaps everyone misheard when he said "you're full of t-shirts."

Knuth was asked if this was true by R Munroe (xkcd) on a talk on campus at Google, and Knuth denied it.

As they say, "never let the truth spoil a good story."

FWIW Knuth himself doesn't think this happened nor does he sound like the kind of person (to me) who would try to cut someone down like that: https://m.youtube.com/watch?v=zJOS0sV2a24&t=26m

More likely Knuth made an earnest comment about being impressed about reading all his books.

That comment was then misinterpreted as sarcasm, which is what the folklore author remembered. Later having forgotten the words, and only remembering the mistaken interpretation's overall feel, it was paraphrased, poorly.

I like this response because it doesn't put the blame into anyone.

Never attribute to malice that which can be explained by incompetence.

I like these two quotes of Knuth where he lets us know how hard he worked.

--

From this small interview [1]:

"When I'm working on a research problem I generally begin by filling dozens of sheets of scratch paper with partial calculations. When I eventually get to a point where I can think about the problem while swimming, then I'm often ready to solve it."

--

From this other interview [2]:

"So I went to Case, and the Dean of Case says to us, says, it’s a all men’s school, says, “Men, look at, look to the person on your left, and the person on your right. One of you isn’t going to be here next year; one of you is going to fail.” So I get to Case, and again I’m studying all the time, working really hard on my classes, and so for that I had to be kind of a machine.

I, the calculus book that I had, in high school we — in high school, as I said, our math program wasn’t much, and I had never heard of calculus until I got to college. But the calculus book that we had was great, and in the back of the book there were supplementary problems that weren’t, you know, that weren’t assigned by the teacher. The teacher would assign, so this was a famous calculus text by a man named George Thomas, and I mention it especially because it was one of the first books published by Addison-Wesley, and I loved this calculus book so much that later I chose Addison-Wesley to be the publisher of my own book.

But Thomas’s Calculus would have the text, then would have problems, and our teacher would assign, say, the even numbered problems, or something like that. I would also do the odd numbered problems. In the back of Thomas’s book he had supplementary problems, the teacher didn’t assign the supplementary problems; I worked the supplementary problems. I was, you know, I was scared I wouldn’t learn calculus, so I worked hard on it, and it turned out that of course it took me longer to solve all these problems than the kids who were only working on what was assigned, at first. But after a year, I could do all of those problems in the same time as my classmates were doing the assigned problems, and after that I could just coast in mathematics, because I’d learned how to solve problems. So it was good that I was scared, in a way that I, you know, that made me start strong, and then I could coast afterwards, rather than always climbing and being on a lower part of the learning curve."

[1] http://authenticinquirymaths.blogspot.pt/2015/11/maths-in-sc....

[2] Transcript from here: https://github.com/kragen/knuth-interview-2006

Good article, two things: I noticed looking at the pictures after reading the whole thing in a go...

He looks nothing like Yoda! Wondering what made the author pick that title!

He has/had a standing desk at home!

Somebody actually changed the title of the post, so now it only says Yoda and doesn't reference Knuth at all. Seems backwards to me.

Can anyone ID this keyboard depicted in the article?

https://static01.nyt.com/images/2018/12/18/science/18SCI-KNU...

Looks like a Logitech G19 to me. I wouldn't have thought Knuth would have a gaming keyboard, let alone one with a screen.

EDIT: I think the other comment is correct, a Logitech G110

I'm an old-school programmer (though not as old as Knuth) and I use a gaming keyboard. I like the "click click" and full travel and the new "buckle spring" keyboards I can get aren't as good as the cherry clicky ones.

I learned to type on a a mechanical typewriter in High School and in college punched programs on keypunch machines. A lot of us old-timers use gaming keyboards.

My favorite book from Knuth isn't computer-related at all.

3:16 Bible Texts Illuminated

https://smile.amazon.com/3-16-Bible-Texts-Illuminated/dp/089...

Donald Knuth shaved the ultimate yak. He wanted to write a book with mathematics in it so he implemented what for decades has been industry-standard mathematical typesetting system: TeX.

That's remarkable. I just wish he'd finish the book.

The details are even hairier.

He wrote TeX82 (modern TeX) in WEB, a literate programming language he invented that could be tangled into the Pascal machine code or weaved into literate documentation in ... TeX itself.

In fact he wrote WEB itself in WEB and by hand compiled the output of the tangle program, which he ran on the tangle source to get the same output.

He also wrote the program METAFONT to produce the typefaces, which he used to design the Computer Modern font.

And then he used that to write instruction books for TeX and METAFONT as well as new editions of The Art of Computer Science and others.

TeX is still in regular use in the academic community (ported via Web2C) over 35 years later, despite the changes in technology in that time (with hacks to deal with modern fonts, outputting PDFs instead of DVI, including images and the like).

He taught the yak to shave itself, and it's still clean shaven 35 years later.

Dr. Knuth has gone so far as to argue that some computer programs are, like Elizabeth Bishop’s poems and Philip Roth’s “American Pastoral,” works of literature worthy of a Pulitzer.

I'd love to know which programs he's thinking of.

Any ideas?

I was unsure of what to get for christmas. Now I know, I want the full collection of "the Art of Computer Programming".

It's not a novel to read through, front to back.

Even Dr. Knuth says to skip around and read relevant chapters.

Just out of curiousity, does anyone know what kind of notebooks and paper he’s using in the photo captioned “A few notes”?

Yes the notepaper with triangular tiling was gifted at Knuth's 80th birthday celebration in Piteå, Sweden: http://knuth80.elfbrink.se/ (Sorry I don't remember where I read/heard about this.)

There are a few names in CS that stand out to me as legendary. Some examples are Von Neumann and Turing. IMO, Knuth stands among them.

"Following Dr. Knuth’s doctrine helps to ward off moronry. He is known for introducing the notion of “literate programming,” emphasizing the importance of writing code that is readable by humans as well as computers — a notion that nowadays seems almost twee."

I liked a lot of this profile, but this came off as kind of weird.

I seem to remember older programming languages (COBOL?) being far closer to English-as-spoken as they are today, using, for example Do/END instead of today’s more common c-style { and }.

My favorite Knuth quote: "Email is a wonderful thing for people whose role in life is to be on top of things. But not for me; my role is to be on the bottom of things. What I do takes long hours of studying and uninterruptible concentration. I try to learn certain areas of computer science exhaustively; then I try to digest that knowledge into a form that is accessible to people who don't have time for such study."

source: https://www-cs-faculty.stanford.edu/~knuth/email.html

Thats an amazing quote.

Reminds me of a "hermit-like wizard in his tower in solitary uninterrupted study of their craft."

I once used two weeks of vacation to learn category theory - that was a really fun and rich time. It really relaxed me, but it also brought me more knowledge than one year of shallowly engaging with the topic.

I've heard many times on HN people bring up category theory and how beneficial it has been to learn it, so I've recently ordered a textbook on it.

Can I ask how has it benefited your thinking?

I'm curious to know not only how it benefits an understanding of software development, programming languages and functional programming, but also has it helped you understand the world at large in new and novel ways?

If category theory is your first exposure to proofs and logic it can benefit you a lot, although number theory might be a more fun and more concrete way to get the same result. If you know a lot about more than one field of math, as a great big generalization over everything category theory can also help.

I should warn you that there is a social bias towards saying that you found a lot of insight in studying something, and a bias against saying that studying it was a waste of time, irrespective of whether or not the thing is actually helpful. Aristotle could stare at a rock and end up with some insight, so anyone who stares at a rock and admits it hasn't helped them has to publicly admit they are not as smart as Aristotle. They say this is how geology got started. ;)

Aristotle might have been able to stare at a rock and say something clever, but most of his ideas about science were wrong, starting from the very definition of science, which he believed should be based on unprovable first principles (like mathematical axioms).

He rejected atomic theory, believed the Earth was the center of the universe and the four fundamental elements were air, fire, water, and earth, and thought heavy objects fell faster and moving objects would tend to come to a stop if nothing interacted with them.

These were observations that Aristotle and his audience accepted as "obvious". It took more careful and patient observers to discern the less obvious truth.

It's this vogueish thing among a certain set of programmers to go around saying they learned category theory. I studied category theory as a math graduate student and frankly, if your goal is simply to become a better programmer, there are much more direct and productive ways to achieve that goal.

Now imagine having a year of this kind of intensive study of category theory (or similar), that is, graduate-level classes in math.

I envy those. I pity not having done my undergrad in maths! I have to say tho that we the examples learned in math department category theory are often not that important or interesting to programmers, and the same is true for the abstractions being studied.

I feel completely the opposite.

Not that email or any of the million other apps don't produce constant interruptions - but in terms of what I want my role to be and what I find pleasure in.

A world of high stimulation and constant social interaction? A million things shouting at me and I have to sort through them and grab the most important one and hop from thing to thing fast? That's what I like.

Focusing on one topic for hours, days, even weeks to really understanding every facet of it? I think it'd kill me. I know people theoretically need these big blocks of uninterrupted time to get work done, but I'd much rather have a bunch of meetings where we can figure out the path forward.

I have mad respect for him... but I never could have been an academic.

I like to take in all those digested kernels of knowledge, I like to digest as many of them as I can; I know I lose the details, but integrating them all into something bigger has always been my dream; it's just how I live my life.

It's only after you've developed a deep understanding that any efforts at integration would be successful. If you just like orchestrating, that's fine but I've met too many managers/product managers who think up lofty ideas on how to integrate various pieces without a deeper understanding of the underlying technology.

Yup, been around a lot of them, they are the ones who love to sling words around and are a prime definition of tech bros always looking to debate not on the basis of firm knowledge but as a cover-up for their inadequacies.

I have seen the other side of this where the developers trying to implement business requirements in code are making bad assumptions and end up in confrontations with middle management because their technically "pure" vision for how something should work doesn't solve the business goal.

I like both.

The problem I find with surface level knowledge is you make a lot of mistakes. When I have a surface level knowledge of a piece of tech and make a decision based upon that, then talk to someone with deep knowledge it's pretty common for them to say "why didn't you just do XYZ, it's easier/more robust".

Ultimately you can produce OK or even sometimes good solutions to problems but not great ones, unless you have direct access to people that know more than you.

This becomes even more pronounced when different pieces of tech can be combined with eachother.

I simply do make a lot of mistakes in most domains of my life.

I'm ADHD (diagnosed, etc), and medication did help, but didn't solve it. For much of my life, I fought against this natural tendency. But for most part I essentially kept telling myself "pay more attention"! It didn't work.

Compensation is important. Detecting the mistakes I make, and avoiding situations where the cost of them is very high. One part of that is accepting things I can never do, like be an academic :).

In the engineering world there's lots of means of compensating. One you mentioned; knowing people who know more than you. Another one would be automated testing; at almost every workplace I've had, I have put a lot of effort into expanding and increasing it, and generally detecting errors wherever they might occur. I'm always asking "what if there's a typo somewhere, will we know, will that go to production?" Might I create a PR I think I've tested but I haven't? The odds I've done this are higher than my peers, so I need to protect myself from that.

If I'm at a workplace that values accuracy above else - that views being able to focus on the code and get the best (not "good enough") solution to every problem as the main trait that I'm evaluated on, I will not succeed. I'm never going to be the guru of anything. This kind of sucks, because a lot of places view being really good at those things as necessary before you can move to another area (IE, management) where you don't use those skills.

I'm a "good not great" or "move fast and break things" kind of person. My usual working style is to produce prototypes very fast; then whoever I'm making it for can see that I didn't quite read the design thoroughly and miss something before it's a huge disaster.

I need the feedback of fast release cycles. I can detect errors fast, take action fast, fix them fast. But "take your time and make sure it's perfect before you throw the switch"? That's just not my personality. I'm high volume (when not artificially constrained) but error prone.

I'm smart enough to know it, smart enough to insist that my code gets reviewed, smart enough to say we really have to test for these cases, things like that. But it's absolutely something I have to compensate a lot for.

I don’t have ADHD but I can relate to feeling that deep knowledge is inaccessible to me. My issue has always been around some kind of internal optimization function that is always asking “how will this help me”?

A solution that’s worked well for me is to only study deeply when I have a concrete need.

For example, when I felt my work suffering because I didn’t deeply understand z-index, it was easy to sell my brain on reading the complete z-index spec.

One of my hobbies is music, and I’m just starting to feel the limitations imposed by not understanding music theory deeply. That means it’s a good time for me to study music theory.

Some people feel compelled to learn things. I feel compelled to do things, and if I can’t do something as well as I want to for lack of knowledge, then I know I’m ready to learn things.

Out of curiosity, what is your profession?

I like how it's a nice articulation of a preference that doesn't denigrate people who have the opposite preference.

Stanford CS has at least a couple of people who seem to be really decent humans as well as great computer scientists. Besides Don Knuth, John Ousterhout is another person who comes to mind. Both of them have a humility combined with humor that I find quite admirable.

Really? So everyone else in CS isn't even a "decent human being" by default for you?

I just read the outline for volume one, sounds really interesting. Has anyone read V1? What sort of mathematical background is required to understand it? Is it proof heavy and really terse like CLRS?

I've read the first three, and attempted every single exercise (besides the few he marks as "suggested research problems"). It took me four years to finish, and I had a MSCS when I started. The first volume is probably the most math-intensive, but also the easiest, since a lot of the math is review. V1 is split into two parts: a pure math half, and then a programming half. All of the programming examples and exercises are done in a custom assembler that he calls MIX, but you can find emulators online to run your programs. I've read CLRS and Knuth and I definitely enjoyed Knuth a lot more - there's just something about his writing and exposition that makes the books compelling. They dare as well as entice you to understand them. It's not really as proof-heavy as CLRS IMHO, and TAOCP covers different ground that CLRS does; the only real overlap there is that volume 3 covers sorting algorithms.

If you like the math in Volume 1, or find yourself having difficulty with it, Concrete Mathematics is a good companion (though also challenging). It goes into greater depth on some of the topics in Chapter 1 of TAOCP and some additional directions. It started as a course aimed at providing the mathematical basis for going into TAOCP.

Golang comes to mind when I read this:

"He is known for introducing the notion of “literate programming,” emphasizing the importance of writing code that is readable by humans ... "

I believe he was thinking far more of something like Jupyter Notebook.

I’m waiting for VSCode to implement a bit of API that would allow me to start on an extension turning comments into first-class citizen, with, for example, diagrams, links, or images.

Knuth is just ONE section away from writing about my (current) topic of study: Constraint Programming.

His 4th volume of TAOCP is so big that its beginning for him to take decades to write sections. Backtracking search + 3-SAT solvers is really interesting (and very closely related to Constraint Programming), but I'm deeply curious to know what his take on Constraint Programming will be.

Its really odd to be "waiting" for the next chapter of TAOCP. Its a serious body of work that has spanned decades of research and writing... I really hope he finishes the next section sooner.

Maybe I'll go and buy the fascicle for 3SAT and read it while waiting.

In his recent Dancing Links talk (a couple of weeks ago), he mentioned a generalization of exact cover that also covers constraint programming. You may want to look into that (XCC) in the meantime, in Knuth's fascicle on Dancing Links (https://cs.stanford.edu/~knuth/fasc5c.ps.gz).

I know the feeling of waiting for new chapters of TAOCP; I'm waiting for Chapter 8 on recursion because his idea of it is so different from everyone else's.

What makes his idea different from everyone else's? I know he covers coroutines, being something not really available in most languages. That said, I thought it was an accepted term and I didn't think that was his invention.

What makes his idea different from everyone else's

Depth and coverage.

Case in point: Knuth's coverage of Quicksort doesn't calculate the Big-O. It calculates the precise average running time. He literally counts the assembly-language statements. You might say "But arrays might be randomly sorted", and yeah, Knuth averages the runtime across all possible ways that an array can be sorted. Its a beautiful work of math.

There's almost no room for questions once Knuth finishes a subject. Its so exhaustively covered that I can't even imagine questions I have on any subject after he's done writing about it.

The few questions I do have are the "Difficulty 40+" questions that Knuth puts at the end of each section, which would serve as excellent questions for Masters Thesis or a PH.D Thesis. IE: There's no answer to those questions yet.

Anyway, while most textbooks hand-wave the idea of "Quicksort is faster than Mergesort, even both are O(n*log(n))". Knuth is pretty simple, he says: Look at these two precise numbers I've calculated (and proved). Quicksort is faster (or at least, the Assembly-language version of Quicksort he wrote on his imaginary computer is faster)

Basically, Knuth got "to the bottom of it", there's no hand-waving involved in the explanation. He just tackles the hard questions head on and solves it more precisely than everyone else.

----------

Some of the older chapters are going out of date, which is natural for a work so complete. There is so much material out there that Knuth has to make a decision on whether to revise older stuff (which he does occasionally) or to write about subjects which don't have a major unifying work yet (ie: Constraint Programming has some textbooks here and there, but most of its ideas are only in academic journals, and haven't really been unified into a singular work yet IMO. Even the textbooks on the subjects are mostly introductions + references to papers)

And sometimes, Knuth gets lucky. Knuth's Book3 "Searching and Sorting" includes a HUGE table of sorting methods applied to tape drives.

But today's RAM is now faster sequentially rather than random-access. So Knuth's calculations on Tape-Drive sorts actually applies to modern DDR4 RAM better than any other treatment on the subject. No one else calculated the cost of "internal movements" (aka: cache on modern systems, but it was RAM on older computers) + "external movements" (which was Tape Drives in Knuth TAOCP / Book 3, but is really DDR4 RAM on today's machines).

So yeah, Book 3 is out of date and focuses a huge amount of time on external sorting methods. But... it just so happens that if you know a bit about the sequential nature of modern DDR4 RAM, it is actually super-relevant to today's computers.

Oh sorry, to be clear, by "his idea of it" I meant "the way he thinks about it [recursion]". What's different is that when most people learn programming, they pick up the idea that iterative structures (loops etc) are simple, and recursion is something more "advanced", harder to understand. Knuth thinks that recursion is the simpler thing (what comes to humans/children naturally), and the mark of a better programmer is being able to translate recursion into iterative structures.

This seems to tie in with his attitude towards programming in general: while in the zeitgeist the idea is that a good program builds better abstractions until the structure of the program reflects human thought, Knuth seems to think that a good programmer is one who starts with a human-level description of the solution and carefully refines it until it translates into a good set of instructions (in machine code). (There's no contradiction, but the point of view seems different from the usual.)

He briefly mentions something related in his Structured Programming with Go To Statements (1974) https://pic.plover.com/knuth-GOTO.pdf#page=21

I 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 it at about the time he is studying data structures. This topic is the subject of Chapter 8 in my multivolume work; but it's only by accident that recursion wasn't Chapter 3, since it conceptually belongs very early in the table of contents.

I think some of this is likely to be a product of the times. The vast majority of early programming languages were not friendly to recursion. It wasn't at all uncommon for functions not to be reentrant, and to rely on self manipulation to set the return stack, if I recall.

Even today, for many "systems level" programs, you have to take extreme care around recursion, since you are likely to blow the stack limits. (That is, you can't just use recursion freely, but instead have to prove the maximum depth that you will trigger it.)

That is to say, I don't see what makes this different than how most others view recursion. If you can afford to do it, then you should do so. If you can't, then you should be ready for a lot of his other tricks. (Threaded trees being my personal favorite, at the moment. DFS with no stacks? Crazy talk! :) )

Definitely a product of his times (like everyone). Let me put it this way: to my knowledge, Knuth is the only programmer from his times, still writing, programming, and writing about programming. So you get a 1960s perspective from someone who's seen (and programmed in) 2018; that's not very usual.

(BTW I'm not sure that Knuth would wholeheartedly agree with “If you can afford recursion, then you should use recursion”. Perhaps he'd consider the program half-written. That's in some sense the crux of what I think is different.)

Let me put it another way: I thought I knew how to generate all permutations of a set of numbers. When I saw questions about it on Stack Overflow or Quora, I answered. When I opened Volume 4A, it disposed of what I knew in the first half-page, and proceeded to discuss the problem for over 50 more pages. I thought I knew about backtracking, having written backtracking programs hundreds of times (always implemented using recursion). Knuth's section on backtracking obliterated everything I knew (and with no recursion in sight). So I'm looking forward to when he gets around to writing about recursion, to see what I can (un)learn about something so fundamental.

His dlx algorithm makes heavy use of recursion. As do many of his cweb programs. In one, he comments it as "textbook" stuff.

Your point on him being one of the main programmers from his time still programming is fair.

Ah but see, his DLX program is not written using recursion! Look at his CWEB program dance.w from his website (or if you don't have cweave handy, download the program from here: https://github.com/shreevatsa/knuth-literate-programs/blob/m... and click around on the hyperlinks) — all the backtracking happens inside “main”; there are only two subroutines “cover” and “uncover”, and neither of them is recursive.

Here is what he says in the (very early) draft of fasc16a (only 2.5 pages written):

We've already seen hundreds of examples of recursion in previous chapters. Early on, we encountered sequences of numbers that were defined by relating each member to earlier members after getting started; these “recurrence relations” were sometimes simple formulas like […], sometimes more involved like […], and sometimes considerably more elaborate and complex. We also found that basic data structures for trees are inherently recursive, because all but the simplest trees are composed of subtrees. We discussed numerous instances where problems of sorting or searching or optimization could be solved effectively by a “divide and conquer” approach, with which a large problem is reduced to smaller problems of the same kind.

Yet we didn't dwell on the recursive nature of those concepts. We transformed them into equivalent notions that could be dealt with directly and nonrecursively. Because “at bottom” a computer operates by means of the physical properties of electrons, which are not recursive.

For example, in Algorithm 2.3.1T we traversed the nodes of a binary tree by using an auxiliary stack A, not by using the recursive definition of symmetric order to define that algorithm in terms of itself.

Don't want to quote the whole thing (though there isn't much), but from the sample I feel I'm going to learn from a new perspective (new to me, anyway).

It's completely bizarre that it is taught in this way. Knuth is absolutely right. Recursion is easy but the problem is computers don't actually work that way. I don't understand how anyone who has programmed for a while can think recursion is the cool or tricky thing to do.

Even worse is that recursion is taught using stupid examples like the fibonacci numbers rather than something that actually needs it like quicksort.

For some reason on this particular article I found it amusing to realize several times that a given concept they were talking about was something I'm familiar with, but it had been translated first from "nerd language" into "layman." Pretty common practice for a general audience, so I'm not sure why it stood out this time. Examples: bytecode, assembly language, frameworks, machine learning. Counterexample: Libraries, where they used the actual word, denying me the silly little pleasure of going "Oh you mean libraries."

The world would be such a better place if there were 1000 more people like him. What a wonderful human being.

More worrisome, perhaps, are the algorithms that are not written by humans, algorithms written by the machine, as it learns.

Can anyone show even one example of a computer writing an original and useful algorithm on it's own? Total misunderstanding of deep learning and "AI" is so common in today's PopSci.

When weights are tuned you are technically left with a different behavior of an algorithm than when it started. When this tuning happened automatically, it's not really a misunderstanding.

I actually think this is a pretty literal description of automatically learned decision trees, which are used in practice (directly or as sub parts of state-of-the-art techniques like gradient boosting). It is basically learning a series of complex nested if statements.

Edit: also, there is actual work done in so-called “program synthesis”, especially employing Bayesian techniques, although it’s way more experimental and I haven’t heard of it being used “in the wild”.

Decision tree models are trained by a machine learning algorithm that a human implemented. DTrees don't create new algorithms, they are calculated/trained through the application of an algorithm on data.

You can find these DTree-generating algorithms in any decent machine learning algorithm textbook, and you can execute the steps by hand. For example, on page 56 (or pdf page 68) of [0], you can step through the ID3 decision tree algorithm. At no point is a new algorithm generated.

[0]: https://www.cs.ubbcluj.ro/~gabis/ml/ml-books/McGrawHill%20-%...

to my understanding, a bunch of nested if-else statements is an algorithm, and if you change all the conditions in the if statements, you get a different algorithm.

so e.g. ID3 is an algorithm, designed by a human, that produces new algorithms, only indirectly designed by a human. we may be talking past each other, though. i just think it's reasonable to apply the word "algorithm" to things that are simple/stupid enough to be generated automatically, and so it's no big deal to talk about algorithms writing algorithms.

https://en.wikipedia.org/wiki/Program_synthesis

It's quite clear from the Wikipedia page that program synthesis is not producing new algorithms.

If I'm wrong, it should be easy to show. Simply point out one concrete example. Not research or articles discussing the idea but an example of actual original computer generated algorithm.

One thing I found really fascinating in the article is, the author when trying to provide an example of an algorithm used the "Command+F" combination to suggest searching on a page. This is distinctly a mac thing. Not just that it doesn't exist on Windows. Have we moved to a point where using Mac only things is acceptable in a general article like this? I mean, even now the bulk of the machines in the world run Windows, so is that an error in proof reading or is that ok now? I couldn't have imagined someone doing that 10 or even 5 years ago.

One fine spring afternoon, I saw Don Knuth at the Golden Gate Park. I think he and his partner were out bird watching or some such thing. I decided not to approach them and let them be.

Seeing him in person is something I'd never forget and take it with me to my grave. Such is the mastery of their craft that even a glimpse of their presence from a distance leaves a lasting impression.

Don Knuth is simply too precious.

I've been at one of his Ask Me Anything-lectures. They are pretty cool, but I feel that they are limited by the audiences questions. If he doesn't get interesting questions then he can't provide interesting answers.

I wanted to ask if he had Autism because he looks, talks and walks as if he had, but I didn't get the chance. I wonder if Knuth has elaborated on the subject? Anyone knows?