Vaughan Pratt (born April 12, 1944) is a
Professor Emeritus
''Emeritus'' (; female: ''emerita'') is an adjective used to designate a retired chair, professor, pastor, bishop, pope, director, president, prime minister, rabbi, emperor, or other person who has been "permitted to retain as an honorary title ...
at
Stanford University, who was an early pioneer in the field of
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
. Since 1969, Pratt has made several contributions to foundational areas such as
search algorithm
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with eith ...
s,
sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important ...
s, and
primality testing. More recently, his research has focused on formal modeling of
concurrent systems
In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the outcome. This allows for parallel execution of the concurr ...
and
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 (of points in open sets ...
s.
Career
Raised in Australia and educated at
Knox Grammar School
, motto_translation = The Manly Thing Is Being Done
, established =
, founder = John Gilmore, William McIlrath, Robert Gillespie and Andrew Reid
, type = Independent school, Independe ...
, where he was
dux
''Dux'' (; plural: ''ducēs'') is Latin for "leader" (from the noun ''dux, ducis'', "leader, general") and later for duke and its variant forms (doge, duce, etc.). During the Roman Republic and for the first centuries of the Roman Empire, '' ...
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
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
. His thesis focused on analysis of the
Shellsort
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion ( insertion sort). The method starts by sorting pairs of ...
sorting algorithm and
sorting network
In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such net ...
s.
Pratt was an assistant professor at
MIT
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...
(1972 to 1976) and then associate professor (1976 to 1982). In 1974, working in collaboration with Knuth and
James H. 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
The SUN workstation was a modular computer system designed at Stanford University in the early 1980s. It became the seed technology for many commercial products, including the original workstations from Sun Microsystems.
History
In 1979 Xerox do ...
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 Microsystems logo,
which features
four interleaved copies of the word "sun"; it is an
ambigram
An ambigram is a calligraphic design that has several interpretations as written.
The term was coined by Douglas Hofstadter in 1983. Most often, ambigrams appear as visually symmetrical words. When flipped, they remain unchanged, or they mutate ...
.
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 testing problem in the complexity class
NP and providing the first strong evidence that the problem is not
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 any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial ...
.
The
Knuth–Morris–Pratt algorithm, which Pratt designed in the early 1970s together with fellow Stanford professor
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
and independently from
Morris
Morris may refer to:
Places
Australia
*St Morris, South Australia, place in South Australia
Canada
* Morris Township, Ontario, now part of the municipality of Morris-Turnberry
* Rural Municipality of Morris, Manitoba
** Morris, Manitob ...
, is still the most efficient general
string searching algorithm
In computer science, 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 (also called patterns) are found within a larger stri ...
known today. Along with
Blum,
Floyd,
Rivest, and
Tarjan, he described
median of medians
In computer science, the median of medians is an approximate (median) selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, mainly the quickselect, that selects the ''k''th smallest element of an initially u ...
, the first worst-case optimal
selection algorithm
In computer science, a selection algorithm is an algorithm for finding the ''k''th smallest number in a list or array; such a number is called the ''k''th ''order statistic''. This includes the cases of finding the minimum, maximum, and median e ...
.
Useful tool building
Pratt built some useful tools. In 1976, he wrote an
MIT
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...
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
Macsyma (; "Project MAC's SYmbolic MAnipulator") is one of the oldest general-purpose computer algebra systems still in wide use. It was originally developed from 1968 to 1982 at MIT's Project MAC.
In 1982, Macsyma was licensed to Symbolics a ...
.
Douglas Crockford
Douglas Crockford is an American computer programmer who is involved in the development of the JavaScript language. He specified the data format JSON (JavaScript Object Notation), and has developed various JavaScript related tools such as the st ...
also used it as the underlying parser for
JSLint
JSLint is a static code analysis tool used in software development for checking if JavaScript source code complies with coding rules. It is provided primarily as a browser-based web application accessible through the domain jslint.com, but ther ...
. 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.
Other contributions
Pratt was credited in a 1995
Byte magazine
''Byte'' (stylized as ''BYTE'') was a microcomputer magazine, influential in the late 1970s and throughout the 1980s because of its wide-ranging editorial coverage. "''Byte'' magazine, the leading publication serving the homebrew market ..."
'' ...
article for proposing that the
Pentium FDIV bug might have worse consequences than either Intel or IBM was predicting at the time.
"Chain Reaction in Pentiums"
Vaughan Pratt, 1994. In wdv-notes334, 22 Jan, 1995. Article is formatted from a newsgroup posting:
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 of the Association for Computing Machinery and is on the editorial board of three major mathematics journals. He was also the founder, chairman, and CTO o
TIQIT Computers, Inc.
for the ten years prior to when it closed its doors in 2010.
References
External links
*
with full-text downloads of many of Pratt's publications.
{{DEFAULTSORT:Pratt, Vaughan
1944 births
Living people
Australian computer scientists
Fellows of the Association for Computing Machinery
Stanford University alumni
Stanford University School of Engineering faculty
Theoretical computer scientists