Robert (Bob) W Floyd

Bob Floyd was born in New York in 1936. He was a very bright child and was recognized as a prodigy when he was 6. Despite moving many times during his school years, he completed high school at age 14 and was admitted into a special program for gifted children at the University of Chicago. He received a BA degree in 1953 when he was only 17. He started working to support himself and, at the same time, completed a second bachelor’s degree in physics in 1958.

His introduction to computing came from an early job as a computer operator at the Armour Research Foundation of the Illinois Institute of Technology. His curiosity led him to become a programmer by reading the manuals, and he quickly advanced to being a senior programmer and analyst. At the same time he started his research career by publishing a paper on radio interference [1]. At Armour he became interested in the compilers that translate high level languages into machine code. He published a paper describing a new notation for symbol manipulation systems that could be used to construct compilers. He then published a paper on a new method of scanning arithmetic expressions that results in more efficient machine code. [2]

In 1962 he became Senior Project Scientist at Massachusetts-based Computer Associates. He worked on compilers and published additional papers in the area. In 1966 Donald Knuth was preparing the chapter of his famous book series The Art of Computer Programming dealing with compilers and syntax analysis, and he noticed that “only five really good papers about compilers had been written so far, and Bob had been the author of all five”. Floyd is the most cited author in The Art series.

In 1967 Floyd built on earlier work of Alan Perlis, Saul Gorn and John McCarthy for proving programs correct. He developed a notation, initially for flowcharts and later for real programs, that assigned conditions at each branch and entry point in the program. Some conditions related to the value of variables, and ensured that if these conditions were true upon entry then they could be proven true at exit. Other conditions proved a program would halt, by requiring that, at each step, some value would decrease that could not decrease indefinitely. Before this approach, ensuring that a program satisfies its specifications required testing with different data, examining the output, fixing bugs, and then trying it again. While sometimes effective, this debugging process could not test every possible situation.  Errors were often found in large programs years after they had been put into production. Floyd’s mathematical analysis was the beginning of a long series of attempts by him and others to prove a program correct before it was released to users. His paper on this topic [3] was very influential and inspired Tony Hoare to develop a system known as Hoare triples that furthered this work.

Bob also invented many important practical algorithms. Best known are those that find the shortest paths through networks, compute the median of data, and render gray scale images with binary pixels using error diffusion—the Floyd-Steinberg algorithm.

Early in his career Floyd met Donald Knuth and they became both collaborators and friends. Floyd was the main proof reader and critic for Knuth’s famous The Art of Computer Programming before it expanded from a single book into a series. The collaboration grew stronger, and Knuth sponsored Floyd’s application for a position at Stanford University. Floyd was appointed as an Associate Professor at Stanford in 1968, which was unusual for someone without a graduate degree. Floyd used to joke that he intended to get his PhD via the “green stamp” method—collecting the envelopes of all the letters he received addressed to “Dr. R. Floyd,” and when he had enough he would trade them for a real degree. He was promoted to Full Professor in 1970, and became Chair of the Department of Computer Science in 1973.

Bob had a strong social conscience and was a leading member of Amnesty International. He used his influence to help release former Chilean Minister of Education Fernando Flores from imprisonment by the military junta. Flores subsequently joined the Stanford computer science department as a researcher.

Bob loved hiking and rock climbing. He was an avid backgammon player, and studied the game carefully. He had his middle name changed to the single letter “W”, but he often wrote it as an abbreviation with a period (“W.”). He was married and divorced twice, and had a daughter and three sons.

When he retired in 1994, he and Richard Biegel published a book The Language of Machines: An Introduction to Computability and Formal Languages [4], describing a machine-based theory of computational complexity.  It gave him great satisfaction to see it translated into other languages.

Sometime shortly before his retirement in 1994 Floyd was stricken with a neurodegenerative disease that began to rob him of both his mental and physical facilities. His intellectual abilities were so strong that he managed to continue with his research, but at a slower pace. In a few years his condition had deteriorated to the point that he became unresponsive. He died in 2001.

When he died a memorial resolution was created by his colleagues at Stanford. That resolution includes other details of his life and work and can be found here.

Don Knuth, a colleague and close friend, wrote another memorial piece describing their relations and Bob’s effect on Knuth’s work. It was published as “Robert W Floyd, In Memoriam,” ACM SIGACT News, Volume 34, Issue 4, December 2003, pp. 3-13 and is available here .