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.
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. Atomic instructions in java. ECOOP 2002—Object-Oriented Programming. :5-16.
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. The Java memory model. Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. :378-391.
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.
2005. Software repository mining with Marmoset: an automated programming project snapshot and testing system. ACM SIGSOFT Software Engineering Notes. 30(4):1-5.
2004. Mpjava: High-performance message passing in java using java. nio. Languages and Compilers for Parallel Computing. :323-339.
2004. Finding bugs is easy. ACM SIGPLAN NoticesSIGPLAN Not.. 39(12):92-92.
2004. Finding concurrency bugs in java. Proceedings of the PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, Newfoundland, Canada.
2001. Core semantics of multithreaded Java. Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande - JGI '01. :29-38.
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. The Java memory model is fatally flawed. Concurrency - Practice and Experience. 12(6):445-455.
1999. SIPR: A new framework for generating efficient code for sparse matrix computations. Languages and Compilers for Parallel Computing. :213-229.
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.
1999. Compressing Java class files. ACM SIGPLAN Notices. 34:247-258.
1999. Fixing the Java memory model. Proceedings of the ACM 1999 conference on Java Grande. :89-98.
1998. Constraint-based array dependence analysis. ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst.. 20(3):635-678.
1997. Iteration space slicing and its application to communication optimization. Proceedings of the 11th international conference on Supercomputing. :221-228.
1997. Symbolic model checking of infinite state systems using Presburger arithmetic. Computer Aided Verification. :400-411.
1996. Transitive closure of infinite graphs and its applications. Languages and Compilers for Parallel Computing. :126-140.
1996. Efficient distribution analysis via graph contraction. Languages and Compilers for Parallel Computing. :377-391.
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.
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.
1995. Parametric dispatching of hard real-time tasks. IEEE Transactions on ComputersIEEE Trans. Comput.. 44(3):471-479.
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.
1995. Code generation for multiple mappings. Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the. :332-341.
1994. Simplifying polynomial constraints over integers to make dependence analysis more precise. Parallel Processing: CONPAR 94—VAPP VI. :737-748.
1994. Counting solutions to Presburger formulas: how and why. ACM SIGPLAN Notices. 29(6):121-134.
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. A partial evaluator for the Maruti hard real-time system. Real-Time Systems. 5(1):13-30.
1992. The Omega test: a fast and practical integer programming algorithm for dependence analysis. Communications of the ACM. 8(102-114):2-6.
1992. Definitions of dependence distance. ACM Letters on Programming Languages and SystemsACM Lett. Program. Lang. Syst.. 1(3):261-265.
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.
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. Uniform techniques for loop optimization. Proceedings of the 5th international conference on Supercomputing. :341-352.
1990. Two-directional record layout for multiple inheritance. Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation. :85-91.
1990. Probabilistic analysis of set operations with constant-time set equality test. Advances in Computing and Information—ICCI'90. :62-71.
1990. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACMCommun. ACM. 33(6):668-676.
1989. Incremental computation via function caching. Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. :315-328.
1988. An improved replacement strategy for function caching. Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88. :269-276.
1987. ALEX-an Alexical Programming Language. TR87-835