Silicon Valley Yoda

Donald Knuth, master of algorithms, reflects on 50 years of work on his main creation, the book “The Art of Programming”, which does not stop complementing

Donald Knut at his home in Stanford, California. Creepy perfectionist, has appointed a reward for finding errors in his books.

For half a century, Stanford computer scientist Donald Knuth, a little reminiscent of Yoda - although he is 193 cm tall and wears glasses - occupies a dominant position of the spiritual teacher in the field of algorithms.

He is the author of “The Art of Programming,” a monograph that he still continues to write, having reached volume 4, and which is the work of his whole life. The first volume was released in 1968, and all volumes together (sold in a set for $ 250 [or $ 12,500 / approx. Transl.]) In 2013 were included in the list of books that formed the last century of science compiled by American Scientist magazine. It also includes a special edition of Charles Darwin’s Autobiographies, Tom Wolfe’s book Guys What We Need!, Rachel Carson’s book Silent Spring , and the monographs of Albert Einstein, John von Neumann and Richard Feynman.

“The art of programming”, printed in over one million copies, is a bible in its field. “It is like a real Bible — it is very long and comprehensive; there are no other such comprehensive books, ”says Peter Norvig, director of research at Google. After 652 pages, the volume closes with a quote on the back cover of a book belonging to Bill Gates: “If you can read the entire book, send me your resume.”
')
The volume opens with an excerpt from the McCall Recipe Collection:

Here you have a book that you have requested to publish in thousands of your letters. It took us years to check and recheck countless recipes in order to provide you with only the best, interesting, and perfect.

The book lists the algorithms, recipes that feed the digital age - although, as Dr. Knut likes to point out, algorithms can also be found on the Babylonian tablets aged 3,800 years. He is a highly respected algorithmist; some of the most important swatches are named after him, for example, the Knut-Morris-Pratt algorithm for finding a substring in a string. It was coined in 1970 and finds all occurrences of a given sequence of letters in the text — for example, when you press Ctrl-F to search for a word in a document.

Now Dr. Knut is 80, and he usually dresses like he was a young geek when he started this odyssey: a long-sleeved shirt with a short-sleeved shirt and jeans — at least at this time of year. In those days he wrote programs in machine code, played with zeros and ones.

“Knut made it clear that the system can be understood across the depth, down to the level of machine codes,” said Dr. Norvig. Today, when algorithms are controlled (and interfered) in our lives, the average programmer does not have time to dig with binary porridge, he works with hierarchies of abstraction, with layers of code — and often with chains of code borrowed from libraries. But the elite of programmers sometimes descends to the lowest levels.

“At Google, we sometimes just collect code from what we have,” said Norvig during a meeting of the Google Trips in Mountain View. “And sometimes, when you need to serve billions of users, you need to do this effectively. A 10% improvement in efficiency can result in billions of dollars, and in order to achieve this last level of efficiency, you need to understand what is going on to its very foundation. ”


Dr. Knut at Caltech, where he received his doctorate in 1963.

Or, as Andrei Broder, a well-known scientist working at Google, and one of Knut’s former students, explained during the meeting: “We need some theoretical basis of our work. We do not need frivolous, clumsy, second-rate algorithms. We do not want other algorithms say: "Yes, you guys are idiots."

The Google Trips application, created in 2016, is an algorithm for tourists, marking up entertainment for tourists for the whole day. The team worked on " maximizing the quality of the worst of the days " - for example, the algorithm should avoid sending the user several times to the same places to explore different places of interest. They were inspired by a 300-year-old algorithm, invented by the Swiss [as well as German and Russian] mathematician Leonard Euler, who wanted to draw a path that passes through the Prussian city of Königsberg [now - Kaliningrad], which intersected all its seven bridges only once. Knut addresses the classic problem of Euler in the first volume of his treatise. Once he used the Euler method to program a computer-controlled sewing machine.


Following the Knut Doctrine helps to avoid idiocy. He is known for introducing the concept of “literary programming”, emphasizing the importance of writing code that not only computers can read, but also people — a concept that today seems to be something old-fashioned. Knut even claimed that some computer programs could be considered literary works, along with Elizabeth Bishop's poems and the American Pastoral novel Philip Roth worthy of a Pulitzer Prize.

And he is notorious for his perfectionism. Randal Munro, the author of the xkcd and Thing Explainer cartoons, first learned about Knut from programmers who mentioned the reward he promised to pay to any person who found a mistake in any of his books. As Monroe recalls, "people talked about getting such a check, as if it was a Nobel science informatics."

Knuth's demanding standards, both literary and otherwise, may explain why his life's work is far from complete. He argued with Sergey Brin, co-founder of Google and his former student, whether Brin would finish his doctoral thesis before Knut finished his monograph.

Dawn of the algorithm

At the age of 19, Knut published his first work on a technical topic, “The Plot System of Weights and Measures ” in the journal Mad [This was a humorous magazine, and potretsibi is a Polish word used in English to indicate absurdity. For example, in his work Knut introduced a new measure of length in one potretsibi, equal to the thickness of the 26th issue of the journal / approx. trans.]. He became an informatics expert even before the advent of computer science, studying mathematics at an educational institution, which is now called Keys University of the Western Reserve District. He studied selected programs written for the IBM 650 650 school mainframe, a decimal computer, and, having encountered inaccuracies, rewrote them and the textbook used in the classroom. As a hobby, he calculated statistics for the basketball team, and wrote a program that helped them win in their league, thanks to which well-known TV journalist Walter Cronkite even filmed a television program about him called “Electronic Coach”.


During the summer holidays, Knut earned more money than his teachers for the year, creating compilers. The compiler is similar to a translator, it turns a high-level programming language (resembling algebra) into a low-level language (sometimes it's a mysterious binary code), and, ideally, improves the program in the process. In computer science, optimization is an art, which is reflected in another Knut proverb: "Premature optimization is the root of all evil."

As a result, Knut himself became a compiler, accidentally discovering a new area, which he later called “algorithm analysis”. The publisher hired him to write a book about compilers, but the project turned into a book that collects everything he knew about how to write programs for computers — a book about algorithms.


Knut in 1981, studies the Mad Magazine issue of 1957, where his first technical article was printed.


“The Art of Programming,” volumes 1-4.

“By the time of the Renaissance, there were already doubts about the emergence of this word,” the book begins. “Early linguists tried to understand its origin by creating combinations such as algiros [painful] + arithmos [number].” In fact, Knut continues, this name appeared in honor of the Persian author of the 9th century textbook, Abu Abdullah Muhammad ibn Musa al-Khorezmi, whose name in the Latin record began to sound like "Algorithm". Knut, who was never satisfied with half measures, went on a pilgrimage to his homeland of al-Khorezmi in 1979, to Uzbekistan [ more precisely, he took part in a conference in Urgench / approx. trans. ].

From the very beginning, Knut wanted to write one book. Soon there was a big bang in computer science, so he reworked his project, breaking it into seven volumes. Now it releases sub-volumes, or issues. The following “Volume 4, Issue 5”, where, among other things, such things as “bektreking” and “dancing links” are described, should have been released as far back as 2018th. However, he stayed until April, as the author constantly finds more and more new tasks that he necessarily wants to present.

To optimize the chances of getting to the end of work, Knut has long been strictly tracking his time. He retired at 55, limited his public speeches, and refused email (at least officially). Andrew Broder recalls that time management was a defining characteristic of his teacher back in the 1980s.

Usually Knut met with students on Fridays in the morning, until he began to spend evenings in the laboratory of John McCarthy, one of the pioneers of development in the field of artificial intelligence, to gain access to computers when they were free. Afraid of how dear to his heart the book began to look after the advent of digital publishing systems, Knut set himself the goal of developing a computer system for typographic typing TeX, remaining the gold standard for all forms of scientific communications and publications. Some consider it the greatest contribution of Knuth, and the greatest contribution to the printing house since the days of Gutenberg.

This ten-year delay happened at a time when different people used computers, and when they worked faster at night, when most people sleep. Therefore, Knut switched to nocturnal lifestyle, moved the schedule to 12 hours, and changed the time of meetings with students for the period from 8 to 12 nights on Friday. Broder recalls: “When I told my girlfriend that we couldn’t do anything on Friday night, because at 10 pm I had an appointment with my supervisor, she thought:“ It sounds so stupid that it seems to be true. ” ".

However, when Knut decides to attend somewhere in person, he gives all his attention to this event. “Being close to him is fun,” says Jennifer Chace, managing director of Microsoft Research. “He is the maximum in the community. If you had an optimization function that represented warmth and depth, then it would be Don. ”


Knut discusses fonts with Hermann Zapf, the font designer.

Sunday with the algorithmist

Whip lives at Stanford and meets people on Sundays. The fact that he singled out a whole day for the meeting was exceptional - usually it is not available during the nap of the day, which is a sacred ritual that takes place from 13 to 16 hours. He began his day early, at the First Lutheran Church of Palo Alto, where he gave a lesson for Sunday school in front of a crowd of people gathered in a room without chairs. On the way home, he begins to philosophize about mathematics.

“I will never know everything,” he said. “My life would be much worse if there were no questions for which I would know the answers, and if there were no questions for which I would not know the answers.” He then offered a tour of the “modern Californian” home that he and his wife built in 1970. His office is packed with piles of flash drives and decorated with handicrafts by Gil, a graphic designer, on the theme of St. Valentine's Day. The greatest impression is made by the music room, built around a custom-made organ for 812 pipes. Ended the day at a party with beer and riddles.

Riddles, games, writing a novel about surreal numbers , composing a 90-minute multimedia musical composition Fantasia Apocalyptica - such things give birth to it . One section of his book is called “Riddles against the Real World.” He sent an excerpt from the book to a team consisting of father and son, Martin DeMein, artist, and Eric DeMeyne, an IT specialist working at MIT, because Knut included their " algorithmic fonts-puzzles " in the book.

“I was pleasantly surprised,” said Eric Demaine. “To get into this book is an honor.” He mentioned another quote by Knut, which inspired the twice-yearly conference “ Fun with Algorithms ”: “The main goal was probably always pleasure.”

And then, said Demain, this area has become a practical one. Engineers, scientists, artists - they all unite to solve real problems, such as folding protein, robotics, airbags, using origami designed by two Demeinis, ways of folding paper and tying it into different shapes.

Of course, this whole algorithmic bother causes real problems. Algorithms written by people - approaching ever more complex tasks, and issuing code filled with errors and prejudices - are already a rather unpleasant thing. But, what's even worse is the algorithms, written not by people, but by machines.

Programmers are still training machines, and feeding them data. Data is a new area for errors and biases, and it is more difficult to catch and correct them. However, as Kevin Slavin, an associate professor at the MIT Media Lab, said: “Now we are writing algorithms that are incapable of reading. This marks a unique historical moment when we work with ideas, actions and attempts caused by physics, originating from people, but not understood by people. ” Slavin often remarks : "You have a bright future, if you are an algorithm."


Knut at his desk at home, 1999.


Notes

And it will be all the more beautiful if you are an algorithm well versed in Knut. “Today, programmers use what Knut and others used as components of their algorithms, and combine it with all sorts of other things they need,” said Dr. Norvig of Google.

“With AI, we do the same thing. Simply, the stage of combining occurs automatically, based on data, and not on the basis of the work of the programmer. We need the AI ​​to be able to combine the components in order to get a suitable response based on the data. However, you must decide what these components are. It may happen that each of the components will be a page or chapter from the Knut, as this will be the best way to accomplish any task. ”

So we are lucky that Knut continues to do this. He thinks that he should take another 25 years to complete “The Art of Programming,” although this estimate has not changed since the 1980s. Will the algorithms that write other algorithms get their chapter in the book, or a page in the epilogue? “Definitely not,” said Knut.

“I’m worried about the effect that algorithms have on the world,” he added. - It all started with the fact that computer scientists were worried because no one listened to them. Now I worry that too many people are listening to us. ”

☃