Computer pioneer Robert W. Floyd, a professor emeritus and former chair of the Department of Computer Science, died 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.
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.
Dawn Levy (Stanford News Service)
