Stanford University Home

Stanford News Archive

Stanford Report, November 7, 2001

Robert Floyd, pioneer in computer programming, dead at 65


Computer pioneer Robert W. Floyd, a professor emeritus and former chair of the Department of Computer Science, died at Stanford University Medical Center on Sept. 25 after a long illness. He was 65.

"In the old days, programmers would just twiddle with programs till they seemed to work," says Professor Emeritus of The Art of Computer Programming Donald Knuth. "Floyd showed that there was a way to prove programs would work." His approach of marrying math with computer science was "a revelation to the field," Knuth says.

"Floyd's 1960s method of invariants, in which assertions are attached to points in a computer program, is still the basis of much work in proving that computer programs meet their specifications," says John McCarthy, professor emeritus of computer science.

Born in New York on June 8, 1936, Floyd was recognized as a child prodigy at age 6; he skipped three grades and finished high school at 14. A scholarship allowed him to study at the University of Chicago, where he received a bachelor's degree in liberal arts in 1953 at age 17. After that he supported himself and earned another bachelor's degree in physics in 1958.

"His entire career in computing was based on autodidactic efforts," recalls his second ex-wife, Christiane Floyd, a computer scientist at the University of Hamburg in Germany. "He started as an operator in the night shift, taught himself how to program, started to publish in the early 1960s and re-entered academia as an associate professor at Carnegie Mellon at the age of 27. He was only 32 when he got his full professorship at Stanford."

Though he never went through the formalities of obtaining a doctorate, prior to his appointment as an associate professor of computer science at Stanford in 1968, he had written at least a dozen papers considered superior to any doctoral dissertation in computer science at the time. One of the hottest topics in computer science at the time was the language of computer programming. Says Knuth: "There were only four good papers on the topic -- all by Floyd."

His research included design and analysis of algorithms for finding the shortest paths in a network, parsing (decomposing) programming languages, calculating quantiles, printing shades of gray on a dot printer, sorting information and selecting random permutations and combinations.

His most important scientific achievement, however, was pioneering systematic methods of program verification. His seminal 1967 paper, "Assigning Meanings to Programs," opened the field of program verification. His basic idea was to attach so-called "tags" in the form of logical assertions to individual program statements or branches that would define the effects of the program based on a formal semantic definition of the programming language. Many researchers in formal methods of computing worldwide adopted this method. One of the most important influences was on C. A. R. Hoare, who in 1969, starting from Floyd's work, developed his calculus of pre- and postcondition semantics for computer programs.

Early on, Knuth and Floyd had found their academic exchanges so productive that they decided they had to be at the same institution, and both came to Stanford. The two were in constant communication when Knuth was working on his book The Art of Computer Programming (originally intended to be one volume), which was supposed to assemble all the interesting algorithms that computer science had to offer. But Knuth was not able to finish his book. As he was writing, he constantly had to cope with new, elegant algorithms that he needed to accommodate. Floyd, the book's major pre-publication reviewer and the person cited more than anyone else in the book, was the main "culprit." The Art of Computer Programming eventually was transformed into a series of seven volumes and is still a work in progress.

Floyd may have been the first advocate of refactoring -- the rewriting of working programs from scratch, re-using only the essential ideas. Refactoring is now standard practice among computer programmers. By continuously looking for simpler ways to do the same thing, Floyd aimed to improve not only programs but also programmers' abilities and understanding.

At Stanford, he taught algorithmic courses, including "Sorting and Searching." With his former graduate student Richard Beigel, he wrote a textbook titled The Language of Machines: An Introduction to Computability and Formal Languages (Computer Science Press, 1994).

Floyd was chair of the Department of Computer Science from 1973 to 1975, a period of great departmental growth when Computer Science moved from Forsythe Hall to more centrally located Margaret Jacks Hall. Floyd was able to use the prestige of his post in conjunction with Amnesty International and an international cadre of systems scientists to help save former Chilean Minister of Education Fernando Flores, who was relegated by the Pinochet government to one of Chile's worst prison camps. On the basis of an invitation to study at Stanford, issued by Floyd, Flores was allowed to leave the country with his family; he eventually finished his studies at Berkeley and co-authored a book with Stanford computer science Professor Terry Winograd.

In 1978, Floyd won the Association for Computing Machinery (ACM) Turing Award -- the highest honor in computer science -- "for having a clear influence on methodologies for the creation of efficient and reliable software, and for helping to found the following important subfields of computer science: the theory of parsing, the semantics of programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms."

In 1991, the Institute of Electrical and Electronics Engineers (IEEE) Computer Society awarded Floyd its Computer Pioneer Award for his work on early compilers. (A compiler is software that translates a computer program as a whole into machine code that is saved for subsequent execution at a desired time.)

Floyd, who retired from Stanford in 1994, was a fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science and the ACM.

He enjoyed backgammon -- pitting his skill against computer opponents at home and human opponents in major tournaments, says friend and colleague Gio Wiederhold, professor emeritus of computer science and electrical engineering. He also was a passionate hiker and mountain climber who loved the wilderness country in the High Sierra, recalls Christiane Floyd.

Floyd is survived by four children -- Susan Barnett of Butte, Mont.; Michael Floyd of Urbana, Ill.; Sean Floyd of Berlin, Germany; and Erik Schorr of Roseville, Calif. -- as well as by his mother, Mary Floyd of Alexandria, Va., and siblings Shelby Floyd of Kamuela, Hawaii, Jeff Floyd of Alexandria, Va., and Fred Floyd of Elko, Nev.

A memorial service was held Sept. 29 at Foothills Congregational Church in Los Altos, Calif.

Robert Floyd in 1976