About me
Having moved from Imperial College London to Victoria University (Wellington, NZ) in 2004, I'm now enjoying life in New Zealand! At Imperial College, I was a PhD student in the department of Computing. My thesis topic was on pointer analysis, although this lead me in some interesting and alternative directions. Pointer analysis is the problem of determining what the pointer variables in a program may point to without running it. Thus, it is a form of static analysis and an increasingly important component of compilers and program understanding tools.
My current research interests focus around the issues of improving software quality. In particular, using advanced compiler technologies to automatically find errors in programs. Finally, my other interests include: programming language design, Tutte polynomials and graph algorithms.
My CV is available in MS Word / PDF and my email address is david.pearce@ecs.vuw.ac.nz.
Publications
Here you will find a complete list of my publications to date, divided into refereed conference/workshop papers, journal articles, my Ph.D. thesis. and, finally, technical reports.
DISCLAIMER: Many of these works are subject to copyright (as indicated). As such, personal use is permitted. However, permission to reprint/republish these works (or any component thereof) for any purpose must be first obtained from the respective publisher.
Journal Articles
Computing Tutte Polynomials. Gary Haggard, David J. Pearce and Gordon Royle. In ACM Transactions on Mathematical Software (TO APPEAR).
Edge-Selection Heuristics for Computing Tutte Polynomials. David J. Pearce, Gary Haggard and Gordon Royle. In the Chicago Journal of Theoretical Computer Science (TO APPEAR). This is an extended version of our CATS paper (see below). A preprint version is available [ Postscript / PDF ]
Efficient Field-Sensitive Pointer Analysis for C. David J. Pearce, Paul H.J. Kelly and Chris Hankin. In ACM Transactions on Programming Languages and Systems (TOPLAS), volume 30(1), 2007. © ACM Press. [ ACM Link ] This is an extended version of the PASTE'04 paper and gives a better exposition, a larger experimental study and a time complexity proof. A preprint version is available [ Postscript / PDF ]
Profiling with AspectJ. David J. Pearce, Matthew Webster, Robert Berry and Paul H.J. Kelly. Software: Practice and Experience, Volume 37(7), pages 747--777, 2007. © Wiley [ abstract / Wiley Link ] A preprint version is also available [ Postscript / PDF ]
A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs. David J. Pearce and Paul H.J. Kelly. ACM Journal of Experimental Algorithmics (JEA), volume 11, pages 1.7, 2007. © ACM Press. This is an extended version of the WEA'04 paper and gives a better exposition and more accurate data. [ ACM Link ] A preprint is also available [ Postscript / PDF ]
Online Cycle Detection and Difference Propagation: Applications to Pointer Analysis. David J. Pearce, Paul H.J. Kelly and Chris Hankin. In Software Quality Journal, volume 12(4), pages 309--335, 2004. © Kluwer Academic Publishers. [ SpringerLink ]
Refereed Conference Papers
A Batch Algorithm for Maintaining a Topological Order. David J. Pearce and Paul H.J. Kelly. In Proceedings of the Australasian Computer Science Conference (ACSC), pages 79--88, CPRIT vol 102, 2010. [ Postscript / PDF / PPT ]
Edge-Selection Heuristics for Computing Tutte Polynomials. David J. Pearce, Gary Haggard and Gordon Royle. In Proceedings of the Computing: The Australasian Theory Symposium, pages 153--162, 2009. A technical report version is available [ Postscript / PDF / PPT / Conference Website]
Patterns for ADT Optimisation. David J. Pearce and James Noble. In Proceedings of the conference on Pattern Languages of Programs (PLoP), (to appear), 2008. A technical report version is available [ Postscript / PDF / Conference Website]
Caching and Incrementalisation for the Java Query Language. Darren Willis, David J. Pearce and James Noble. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages & Applications, pages 1--17, 2008. © ACM Press. [ Postscript / PDF / Conference Website]
Java Bytecode Verification for @NonNull Types. Chris Male, David J. Pearce, Alex Potanin and Constantine Dymnikov. In Proceedings of the Conference on Compiler Construction (CC), volume 4959 of Lecture Notes in Computer Science, pages 229-244, 2008. © Springer-Verlag [ Postscript / PDF / Powerpoint / SpringerLink / Conference Website ]. An extended technical report version is also available [ Postscript / PDF ], while the tool can be obtained from here.
Visualising the Tutte Polynomial Computation. Bennett Thompson, David J. Pearce and Gary Haggard. In Proceedings of the New Zealand Conference on Software Engineering (SIENZ), 2007. [ Postscript / PDF / Powerpoint / Conference Website ]
Patterns of Aspect-Oriented Design. James Noble, Arno Schmidmeier, David J. Pearce and Andrew Black. In Proceedings of the European Conference on Pattern Languages of Programs (EuroPLOP), pages 769--796, 2007. [ Postscript / PDF / Conference Website ]
Relationship Aspect Patterns. David J. Pearce and James Noble. In Proceedings of the European Conference on Pattern Languages of Programs (EuroPLOP), pages 531--546, 2006. [ Postscript / PDF / Conference Website ]
Towards a Semiotics of Object- and Aspect-Oriented Design. James Noble, Robert Biddle, Ewan Tempero and David J. Pearce. In Proceedings of the European Conference on Computing and Philosophy (ECAP), 2006. [ PDF / Conference Website ]
Efficient Object Querying for Java. Darren Willis, David J. Pearce and James Noble. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), pages 28--49, 2006. © Springer-Verlag. [ Postscript / PDF / Powerpoint / SpringerLink / Conference Website ]
Relationship Aspects. David J. Pearce and James Noble. In Proceedings of the ACM conference on Aspect-Oriented Software Development (AOSD'06), pages 75--86, March 2006. © ACM Press. [ Postscript / PDF / Powerpoint / ACM Link / Conference Website ]
Automating Optimized Table-with-Polynomial Function Evaluation for FPGAs. Dong-U Lee, Oskar Mencer, David J. Pearce and Wayne Luk. In Proceedings of the fourteenth international conference on Field-Programmable Logic and its Applications (FPL'04), volume 3203 of Lecture Notes in Computer Science, pages 364--373, August 2004. © Springer-Verlag. [ Postscript / PDF / SpringerLink / Conference Website ]
Design Space Exploration with A Stream Compiler. Oskar Mencer, David J. Pearce, Lee W. Howes and Wayne Luk. In Proceedings of the IEEE Conference on Field-Programmable Technology (FPT'03), pages 270--277, Tokyo, December 2003. © IEEE Computer Society Press. [ Postscript / PDF / IEEE Link / Conference Website ]
GILK: A Dynamic Instrumentation Tool for the Linux Kernel. David J. Pearce, Paul H.J. Kelly, Tony Field and Uli Harder. In Proceedings of the 12th international conference on Modelling Techniques and Tools for Computer Performance Evaluation (TOOLS), volume 2324 of Lecture Notes in Computer Science, pages 220--226, 2002. © Springer-Verlag. [ Postscript / PDF / SpringerLink / Conference Website ]
Refereed Workshop Papers
Implementing relationships using Affinity. Stephen F. Nelson, David J. Pearce and James Noble. In Proceedings Workshop on Relationships and Associations in Object-Oriented Languages (RAOOL), 2009. [ ACM Link / Conference Website ]
Visualizing the computation tree of the Tutte Polynomial. Bennett Thompson, David J. Pearce, Craig Anslow and Gary Haggard. In Proceedings ACM symposium on Software visuallization (SoftViz), pages 211--212, 2008. [ ACM Link / Conference Website ]
Implementing First-Class Relationships in Java. Stephen F. Nelson, David J. Pearce and James Noble. In Proceedings Workshop on Relationships and Associations in Object-Oriented Languages (RAOOL), 2008. [ Conference Website ]
Introducing Software Modelling with Alloy at VUW. James Noble, David J. Pearce and Lindsay Groves. In Proceedings of the Workshop on Formal Methods in Computer Science Education (FORMED), pages 81--90, 2008. [ (email for copy) / Conference Website ]
AspectJ for Multilevel Security. Roshan Ramachandran, David J. Pearce and Ian Welch. In Proceedings of the Workshop on Aspects, Components, and Patterns for Infrastructure Software (ACP4IS), pages 13--17, March 2006 (University of Virginia, Technical Report CS-2006-01). [ Postscript / PDF / Powerpoint / Conference Website ]
Efficient Field-Sensitive Pointer Analysis for C. David J. Pearce, Paul H. J. Kelly and Chris Hankin. In Proceedings of the ACM workshop on Program Analysis for Software Tools and Engineering (PASTE'04), pages 37--42, June 2004. © ACM Press. [ Postscript / PDF / Powerpoint / ACM Link / Conference Website ]
A Dynamic Algorithm for Topologically Sorting Directed Acyclic Graphs. David J. Pearce and Paul H. J. Kelly. In Proceedings of the 3rd international Workshop on Efficient and experimental Algorithms (WEA'04), volume 3059 of Lecture Notes in Computer Science, pages 383--398, 2004. © Springer-Verlag. [ Postscript / PDF / Powerpoint / SpringerLink / Conference Website ]
Online Cycle Detection and Difference Propagation for Pointer Analysis. David J. Pearce, Paul H. J. Kelly and Chris Hankin. In Proceedings of the third international IEEE Workshop on Source Code Analysis and Manipulation (SCAM'03), pages 3--12, Amsterdam, 2003. © IEEE Computer Society Press. [ Postscript / PDF / Powerpoint / IEEE Link / Conference Website ]
Ph.D. Thesis
Some directed graph algorithms and their application to pointer analysis. David J. Pearce. Ph.D. Thesis, Imperial College of Science, Technology and Medicine, University of London, February 2005. [ Postscript / PDF ]
Theses Supervised
Mocha: Type Inference for Java. Chris Male, MSc Thesis, Victoria University of Wellington, 2009. [ PDF ]. Chris is now working for a web search company based in Amsterdamn.
The Java Query Language. Darren Willis, MSc Thesis, Victoria University of Wellington, 2008. [ PDF ]. Darren is now working for a small Wellington based company, called Innaworks.
Technical Reports
Computing Tutte Polynomials. Gary Haggard, David J. Pearce and Gordon Royle, Isaac Newton Institute for Mathematical Sciences, #NI09024-CSM, 2009. [ Postscript / PDF / INI Website ]
Mocha: Local Type Inference for Java. Chris Male and David J. Pearce, 2008. [ Postscript / PDF ]
Java Bytecode Verification for @NonNull Types. Chris Male, David J. Pearce, Alex Potanin and Constantine Dymnikov, 2007. This is an extended, technical report version of our Compiler Construction conference paper (see above) [ Postscript / PDF ]. The JACK @NonNull type verification tool can be obtained from here.
An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph. David J. Pearce, Technical Report, 2005. [ Postscript / PDF ]
Online algorithms for topological order and strongly connected components. David J. Pearce and Paul H. J. Kelly. Technical Report, September 2003. [ Postscript / PDF ]
Online algorithms for maintaining the topological order of a directed acyclic graph. David J. Pearce and Paul H. J. Kelly. Technical Report, July 2003. [ Postscript / PDF ]
Projects
The Java Compiler Kit (JKit) The Java Compiler Kit (JKit) is a straightforward implementation of a Java compiler, designed with extensibility in mind. In building the JKit compiler, there aims were: firstly, to help with teaching compilers by considering an implementation for a fully fledged language (Java), rather than a stripped-down imitation language; secondly, to aid research in programming languages, compilers and verification. With JKit you can easily prototype new extensions to the Java language, or implement completely new languages and compile them down to Java Bytecode. You can more information about JKit here.
Code for Computing Tutte Polynomials In these pages, you can find an implementation of Gary Haggard's algorithm for computing tutte polynomials, written in C++ and developed by myself and Gary. We hope that this code may be useful to the algorithms community and that it will eventually lead to an efficient method for computing the Tutte polynomials of large graphs. More details of JACK can be found here.
The Java Annotation ChecKer (JACK) JACK is a prototype tool for checking Java annotations. Currently, it supports only @NonNull annotations, although we plan to extend this to others (e.g. @ReadOnly, @Secure) in the future. The tool uses type inference technology (specifically, flow-sensitive dataflow analysis) in order to infer the affect of conditional statements on variable types. The tool assumes method parameters, return types and fields are already annotated appropriately. With this information, it checks method bodies for "type errors". More details of JACK can be found here.
The Java Query Language (JQL) JQL is an extension for Java that provides support for querying objects across collections (similar to Python's list comprehensions) and also their extent sets (i.e. the set of all allocated objects of the given class). Queries provide a powerful abstraction for operating on object subsets determined by a query expression (e.g. all
Studentswhereage < 3). The query engine takes care of efficiently searching the source set to identify those matching the query expression and uses several well-known database techniques (e.g. using hash joins, sorted joins and selecting good join orders) for this purpose. This results in shorter, clearer code that is typically also more efficient than the average programmer might produce by hand. More details of JQL can be found here.Relationship Aspect Library (RAL) The Relationship Aspect Library provides a novel and more coherent approach to implementing relationships (also called associtions in UML). Typically, relationships are hand-coded by modifiying the participants to include links (i.e. pointers or references) to those objects they are associated with. In RAL, however, relationships are implemented as aspects which may cross-cut the participants. This provides a simpler, more coherent and more maintainable approach to implemented relationships. Details of the library can be found here, where the current release may also be downloaded.
DJProf DJProf is an experimental Java profiling tool which employs AspectJ to insert the necessary instrumentation for profiling rather than, for example, the Java Machine Profiler Interface (JVMPI). You can find more information here.
Dynamic Topological Sort You can find software written in C++ for several dynamic topological sort algorithms here. This software has been used in several of my papers to experimentally evaluate different algorithms for this problem.
PCS the Pointer Constraint System. This is a set-constraint based pointer analysis framework written in C++, including various solvers and components for implementing different iteration strategies. This project is currently my main focus and has been used to provide empirical data on the speed and accuracy of pointer analysis. The system consists of two components: the constraint system and some utilities to help in compiling GNU programs with the SUIF 2.0 research compiler.
GILK A tool for dynamic instrumentation of the Linux Kernel, which formed part of my masters thesis. The tool allows an unmodified kernel to have arbitrary instrumentation code added whilst in operation. This feat is achieved through a technique called ``Dynamic Code Splicing''. Currently, the tool only supports kernel versions 2.0.x - 2.2.x. Go here for more information.
SUIF pages The SUIF research compiler from Stanford comes in two versions: 1.3.X and 2.0. I have used the latter extensively in conjunction with the PCS project. To this end, I have written several patches to fix bugs and provide compatibility with the Standard Template Library. In addition, some non-related work required me to port the 1.3.X version to run under Windows, in the Cygwin environment. More information on the compiler can be found here.
Do you trust HProf? Several examples illustrate that results from the HProf profiling tool are not always what they seem. More information can be found here.
|
|
|
|