Bill Pugh

Professor Emeritus
4121 A.V. Williams Building
(301) 405-2705
(301) 405-6707
Education: 
Ph.D., Cornell University (Computer Science)
Special Awards/Honors: 
Packard Fellow
Biography: 

William "Bill" Pugh is a professor emeritus in the Department of Computer Science.

Pugh is a Packard Fellow, and invented Skip Lists, a randomized data structure that is widely taught in undergraduate data structure courses. He has also made research contributions in the fields of incremental computation, implementation of functional and object-oriented languages, the use of partial evaluation for hard real-time systems, in techniques for analyzing and transforming scientific codes for execution on supercomputers, and in a number of issues related to the Java programming language, including the development of JSR 133 - Java Memory Model and Thread Specification Revision.

Pugh's current research focus is on developing tools to improve software productivity, reliability and education. Current research projects include FindBugs, a static analysis tool for Java, and Marmoset, an innovative framework for improving the learning and feedback cycle for student programming projects.

He consulted for Google from 2000 to 2003 on research that resulted in U.S. Patent 665 8423, on detecting duplicate and near-duplicate files. Pugh has served as a visiting scientist at Google on and off since 2000, and spent the 2008-2009 school year there on sabbatical.

He has spoken at numerous developer conferences, including JavaOne, Goto/Jaoo in Aarhus, the Devoxx conference in Antwerp, and CodeMash. At JavaOne, he received six JavaOne RockStar awards, given to the speakers that receive the highest evaluations from attendees.

Pugh received a B.S. in computer science from Syracuse University in 1980 and received a doctorate in computer science (with a minor in acting) from Cornell University in 1988.

Publications

2007


Foster JS, Hicks MW, Pugh W.  2007.  Improving software quality with static analysis. Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering.
:83-84.

2006


Hovemeyer D, Pugh W, Spacco J.  2006.  Atomic instructions in java. ECOOP 2002—Object-Oriented Programming.
:5-16.

Grossman D, Manson J, Pugh W.  2006.  What do high-level memory models mean for transactions? Proceedings of the 2006 workshop on Memory system performance and correctness - MSPC '06.
:62-62.

2005


Manson J, Pugh W, Adve SV.  2005.  The Java memory model. Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages.
:378-391.

Hovemeyer D, Spacco J, Pugh W.  2005.  Evaluating and tuning a static analysis to find null pointer bugs. Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering.
:13-19.

Spacco J, Strecker J, Hovemeyer D, Pugh W.  2005.  Software repository mining with Marmoset: an automated programming project snapshot and testing system. ACM SIGSOFT Software Engineering Notes. 30(4):1-5.

2004


Pugh W, Spacco J.  2004.  Mpjava: High-performance message passing in java using java. nio. Languages and Compilers for Parallel Computing.
:323-339.

Hovemeyer D, Pugh W.  2004.  Finding bugs is easy. ACM SIGPLAN NoticesSIGPLAN Not.. 39(12):92-92.

Hovemeyer D, Pugh W.  2004.  Finding concurrency bugs in java. Proceedings of the PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, Newfoundland, Canada.

2001


Manson J, Pugh W.  2001.  Core semantics of multithreaded Java. Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande - JGI '01.
:29-38.

Hovemeyer D, Pugh W.  2001.  More efficient network class loading through bundling. Proceedings of the 2001 Symposium on Java TM Virtual Machine Research and Technology Symposium-Volume 1.
:17-17.

2000


Pugh W.  2000.  The Java memory model is fatally flawed. Concurrency - Practice and Experience. 12(6):445-455.

1999


Pugh W, Shpeisman T.  1999.  SIPR: A new framework for generating efficient code for sparse matrix computations. Languages and Compilers for Parallel Computing.
:213-229.

Bultan T, Gerber R, Pugh W.  1999.  Model-checking concurrent systems with unbounded integer variables: symbolic representations, approximations, and experimental results. ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst.. 21(4):747-789.

Pugh W.  1999.  Compressing Java class files. ACM SIGPLAN Notices. 34:247-258.

Pugh W.  1999.  Fixing the Java memory model. Proceedings of the ACM 1999 conference on Java Grande.
:89-98.

1998


Pugh W, Wonnacott D.  1998.  Constraint-based array dependence analysis. ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst.. 20(3):635-678.

1997


Pugh W, Rosser E.  1997.  Iteration space slicing and its application to communication optimization. Proceedings of the 11th international conference on Supercomputing.
:221-228.

Bultan T, Gerber R, Pugh W.  1997.  Symbolic model checking of infinite state systems using Presburger arithmetic. Computer Aided Verification.
:400-411.

1996


Sheffler T, Schreiber R, Pugh W, Gilbert J, Chatterjee S.  1996.  Efficient distribution analysis via graph contraction. Languages and Compilers for Parallel Computing.
:377-391.

Kelly W, Pugh W, Rosser E, Shpeisman T.  1996.  Transitive closure of infinite graphs and its applications. Languages and Compilers for Parallel Computing.
:126-140.

1995


Pugh W, Wonnacott D.  1995.  Going beyond integer programming with the Omega test to eliminate false data dependences. IEEE Transactions on Parallel and Distributed Systems. 6(2):204-211.

Kelly W, Pugh W, Rosser E.  1995.  Code generation for multiple mappings. Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the.
:332-341.

Pugh W, Kelly W.  1995.  Finding Legal Reordering Transformations using Mappings. Languages and compilers for parallel computing: 7th International Workshop, Ithaca, NY, USA, August 8-10, 1994: proceedings. 7:107-107.

Kelly W, Pugh W.  1995.  A unifying framework for iteration reordering transformations. Algorithms and Architectures for Parallel Processing, 1995. ICAPP 95. IEEE First ICA/sup 3/PP., IEEE First International Conference on. 1:153-162.

Gerber R, Pugh W, Saksena M.  1995.  Parametric dispatching of hard real-time tasks. IEEE Transactions on ComputersIEEE Trans. Comput.. 44(3):471-479.

1994


Pugh W, Wonnacott D.  1994.  Static analysis of upper and lower bounds on dependences and parallelism. ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst.. 16(4):1248-1278.

1993

1992


Pugh W.  1992.  Definitions of dependence distance. ACM Letters on Programming Languages and SystemsACM Lett. Program. Lang. Syst.. 1(3):261-265.

Nirkhe V, Pugh W.  1992.  Partial evaluation of high-level imperative programming languages with applications in hard real-time systems. Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages.
:269-280.

Pugh W, Wonnacott D.  1992.  Eliminating false data dependences using the Omega test. Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation.
:140-151.

1991


Pugh W.  1991.  Uniform techniques for loop optimization. Proceedings of the 5th international conference on Supercomputing.
:341-352.

1990


Pugh W.  1990.  Skip lists: a probabilistic alternative to balanced trees. Communications of the ACMCommun. ACM. 33(6):668-676.

Pugh W, Weddell G.  1990.  Two-directional record layout for multiple inheritance. Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation.
:85-91.

1989


Pugh W, Teitelbaum T.  1989.  Incremental computation via function caching. Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages.
:315-328.

1988


Pugh W.  1988.  An improved replacement strategy for function caching. Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88.
:269-276.

1987


Kozen D, Teitelbaum T, Chen WZ, Field JH, Pugh W, Vander Zanden BT.  1987.  ALEX-an Alexical Programming Language. TR87-835