Vaughan Ronald Pratt
Encyclopedia
Vaughan Ronald Pratt a Professor Emeritus
at Stanford University
, was one of the earliest pioneers in the field of computer science
. Publishing since 1969, Pratt has made several contributions to foundational areas such as search algorithm
s, sorting algorithm
s, and primality testing. More recently his research has focused on formal modeling of concurrent systems
and Chu space
s. A pattern of applying models from diverse areas of mathematics such as geometry
, linear algebra
, abstract algebra
, and especially mathematical logic
to computer science pervades his work.
where he was dux in 1961, Pratt attended Sydney University where he completed his masters thesis in 1970, related to what is now known as natural language processing
. He then went to the United States, where he completed a Ph.D. thesis at Stanford University in only 20 months under the supervision of advisor Donald Knuth
. His thesis focused on analysis of the shellsort sorting algorithm and sorting network
s.
Pratt was an Assistant Professor at MIT
(1972 to 1976) and then Associate Professor (1976 to 1982). In 1974, working in collaboration with Knuth and Morris
, Pratt completed and formalized work he had begun in 1970 as a graduate student at Berkeley
; the coauthored result was the Knuth-Morris-Pratt pattern matching algorithm. In 1976, he developed the system of dynamic logic
, a modal logic
of structured behavior.
He went on sabbatical from MIT to Stanford
(1980 to 1981), and was appointed a full professor at Stanford in 1981.
Pratt directed the SUN workstation
project at Stanford from 1980 to 1982. He contributed in various ways to the founding and early operation of Sun Microsystems
, acting in the role of consultant for its first year, then, taking a leave of absence from Stanford for the next two years, becoming Director of Research, and finally resuming his role as a consultant to Sun and returning to Stanford in 1985.
He also designed the Sun logo, which features four interleaved copies of the word "sun"; it is an ambigram
.
Pratt became professor emeritus at Stanford in 2000.
ing problem in the complexity class NP
and providing the first strong evidence that the problem is not co-NP-complete
.
The Knuth-Morris-Pratt algorithm, which Pratt designed in the early 1970s together with fellow Stanford professor Donald Knuth
and independently from Morris
, is still the most efficient general string searching algorithm
known today. Along with Blum
, Floyd
, Rivest
, and Tarjan
, he described the first worst-case optimal selection algorithm
.
AI Lab working paper about CGOL
, an alternative syntax for MACLISP
that he had designed and implemented based on his paradigm for top down operator precedence parsing. His parser is sometimes called a "Pratt parser
" and has been used in later systems, such as MACSYMA
. Douglas Crockford
also used it as the underlying parser for JSLint
. Pratt also implemented a TECO
-based text editor named "DOC", which was later renamed to "ZED".
In 1999, Pratt built the world's smallest (at the time) web server—it was the size of a matchbox.
might have worse consequences than either Intel or IBM was predicting at the time.
Today Pratt has a wide influence. In addition to his Stanford professorship, he holds membership in at least seven professional organizations. He is a fellow with the Association for Computing Machinery
and is on the Editorial Board of three major mathematics journals. He is also the Chairman and CTO of TIQIT Computers, Inc..
Professor
A professor is a scholarly teacher; the precise meaning of the term varies by country. Literally, professor derives from Latin as a "person who professes" being usually an expert in arts or sciences; a teacher of high rank...
at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
, was one of the earliest pioneers in the field of computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. Publishing since 1969, Pratt has made several contributions to foundational areas such as search algorithm
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
s, sorting algorithm
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
s, and primality testing. More recently his research has focused on formal modeling of concurrent systems
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
and Chu space
Chu space
Chu spaces generalize the notion of topological space by dropping the requirements that the set of open sets be closed under union and finite intersection, that the open sets be extensional, and that the membership predicate be two-valued...
s. A pattern of applying models from diverse areas of mathematics such as geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, and especially mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
to computer science pervades his work.
Career
Raised in Australia and educated at Knox Grammar SchoolKnox Grammar School
Knox Grammar School is an independent, Uniting Church, day and boarding school for boys, located in Wahroonga, an upper North Shore suburb of Sydney, New South Wales, Australia....
where he was dux in 1961, Pratt attended Sydney University where he completed his masters thesis in 1970, related to what is now known as natural language processing
Natural language processing
Natural language processing is a field of computer science and linguistics concerned with the interactions between computers and human languages; it began as a branch of artificial intelligence....
. He then went to the United States, where he completed a Ph.D. thesis at Stanford University in only 20 months under the supervision of advisor Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
. His thesis focused on analysis of the shellsort sorting algorithm and sorting network
Sorting network
A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sorts the values by outputting the smaller value to one wire, and the larger to the other...
s.
Pratt was an Assistant Professor at MIT
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
(1972 to 1976) and then Associate Professor (1976 to 1982). In 1974, working in collaboration with Knuth and Morris
James H. Morris
James Hiram Morris is a Professor of Computer Science. He was previously Dean of the Carnegie Mellon School of Computer Science and Dean of Carnegie Mellon Silicon Valley.-Biography:...
, Pratt completed and formalized work he had begun in 1970 as a graduate student at Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
; the coauthored result was the Knuth-Morris-Pratt pattern matching algorithm. In 1976, he developed the system of dynamic logic
Dynamic logic (modal logic)
Dynamic logic is an extension of modal logic originally intended for reasoning about computer programs and later applied to more general complex behaviors arising in linguistics, philosophy, AI, and other fields.-Language:...
, a modal logic
Modal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
of structured behavior.
He went on sabbatical from MIT to Stanford
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
(1980 to 1981), and was appointed a full professor at Stanford in 1981.
Pratt directed the SUN workstation
SUN workstation
The original SUN workstation was a modular computer system designed at Stanford University in the early 1980s.-History:The project name was derived from Stanford University Network, the campus network within Stanford....
project at Stanford from 1980 to 1982. He contributed in various ways to the founding and early operation of Sun Microsystems
Sun Microsystems
Sun Microsystems, Inc. was a company that sold :computers, computer components, :computer software, and :information technology services. Sun was founded on February 24, 1982...
, acting in the role of consultant for its first year, then, taking a leave of absence from Stanford for the next two years, becoming Director of Research, and finally resuming his role as a consultant to Sun and returning to Stanford in 1985.
He also designed the Sun logo, which features four interleaved copies of the word "sun"; it is an ambigram
Ambigram
An ambigram is a typographical design or art form that may be read as one or more words not only in its form as presented, but also from another viewpoint, direction, or orientation. The words readable in the other viewpoint, direction or orientation may be the same or different from the original...
.
Pratt became professor emeritus at Stanford in 2000.
Major contributions
A number of well-known algorithms bear Pratt's name. Pratt certificates, short proofs of the primality of a number, demonstrated in a practical way that primality can be efficiently verified, placing the primality testPrimality test
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
ing problem in the complexity class NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
and providing the first strong evidence that the problem is not co-NP-complete
Co-NP-complete
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that they are the ones most likely not to be in P...
.
The Knuth-Morris-Pratt algorithm, which Pratt designed in the early 1970s together with fellow Stanford professor Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
and independently from Morris
James H. Morris
James Hiram Morris is a Professor of Computer Science. He was previously Dean of the Carnegie Mellon School of Computer Science and Dean of Carnegie Mellon Silicon Valley.-Biography:...
, is still the most efficient general string searching algorithm
String searching algorithm
String searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings are found within a larger string or text....
known today. Along with Blum
Manuel Blum
Manuel Blum is a computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".-Biography:Blum attended MIT, where he received his bachelor's degree and...
, Floyd
Robert Floyd
Robert W Floyd was an eminent computer scientist.His contributions include the design of the Floyd–Warshall algorithm , which efficiently finds all shortest paths in a graph, Floyd's cycle-finding algorithm for detecting cycles in a sequence, and his work on parsing...
, Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
, and Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
, he described the first worst-case optimal selection algorithm
Selection algorithm
In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list . This includes the cases of finding the minimum, maximum, and median elements. There are O, worst-case linear time, selection algorithms...
.
Useful tool building
Pratt built some useful tools. In 1976, he wrote an MITMassachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
AI Lab working paper about CGOL
CGOL
CGOL is an alternative syntax for the MACLISP programming language,featuring an extensible algebraic notation. It was created by Vaughan Pratt....
, an alternative syntax for MACLISP
Maclisp
MACLISP is a dialect of the Lisp programming language. It originated at MIT's Project MAC in the late 1960s and was based on Lisp 1.5. Richard Greenblatt was the main developer of the original codebase for the PDP-6; Jonl White was responsible for its later maintenance and development...
that he had designed and implemented based on his paradigm for top down operator precedence parsing. His parser is sometimes called a "Pratt parser
Pratt parser
A Pratt parser is an improved recursive descent parser that associates semantics with tokens instead of grammar rules. It was first described by Vaughan Pratt in the 1973 paper "Top down operator precedence", and was treated in much more depth in a Masters Thesis under his supervision. Pratt...
" and has been used in later systems, such as MACSYMA
Macsyma
Macsyma is a computer algebra system that was originally developed from 1968 to 1982 at MIT as part of Project MAC and later marketed commercially...
. Douglas Crockford
Douglas Crockford
Douglas Crockford is an American computer programmer and entrepreneur, best known for his ongoing involvement in the development of the JavaScript language, and for having popularized the data format JSON , and for developing JSLint...
also used it as the underlying parser for JSLint
JSLint
JSLint is a static code analysis tool used in software development for checking if JavaScript source code complies with coding rules. It is developed by Douglas Crockford. It is provided primarily as an online tool, but there are also command-line adaptations....
. Pratt also implemented a TECO
Text Editor and Corrector
TECO is a text editor originally developed at the Massachusetts Institute of Technology in the 1960s, after which it was modified by 'just about everybody'...
-based text editor named "DOC", which was later renamed to "ZED".
In 1999, Pratt built the world's smallest (at the time) web server—it was the size of a matchbox.
Other contributions
Pratt was credited in a 1995 Byte magazine article for proposing that the Pentium FDIV bugPentium FDIV bug
The Pentium FDIV bug was a bug in the Intel P5 Pentium floating point unit . Certain floating point division operations performed with these processors would produce incorrect results...
might have worse consequences than either Intel or IBM was predicting at the time.
Today Pratt has a wide influence. In addition to his Stanford professorship, he holds membership in at least seven professional organizations. He is a fellow with the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
and is on the Editorial Board of three major mathematics journals. He is also the Chairman and CTO of TIQIT Computers, Inc..
External links
- Faculty home page at Stanford University
- Abstract page, with full-text downloads of many of Pratt's publications.
- Douglas Crockford walks through creating a Pratt parser in JavaScript.