About me

Picture of 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 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

  • Designing a Verifying Compiler: Lessons Learned from Developing Whiley. David J. Pearce and Lindsay Groves. In Science of Computer Programming, pages 191--220, 2015. © Elsevier. A preprint version is also available [ PDF / DOI ].

  • A Space Efficient Algorithm for Detecting Strongly Connected Components. David J. Pearce. In Information Processing Letters, (to appear), 2015. © Elsevier. A preprint version is also available [ PDF / DOI ]. A straightforward implementation of the algorithm is available here.

  • Formalisation and Implementation of an Algorithm for Bytecode Verification of @NonNull Types. Chris Male, David J. Pearce, Alex Potanin and Constantine Dymnikov. In Science of Computer Programming, Volume 76(7), pages 587--608, 2011. © Elsevier. [ DOI ]. A preprint version is also available [ Postscript / PDF ]. The tool can be obtained from here.

  • Implementing a Language with Flow-Sensitive and Structural Typing on the JVM. David J. Pearce and James Noble. In Proceedings of the Workshop on Bytecode Semantics, Verification, Analysis and Transformation (BYTECODE), ENTCS 279(1):47--59, 2011. [ PDF / PPT / DOI / Conference Website ]

  • Computing Tutte Polynomials. Gary Haggard, David J. Pearce and Gordon Royle. In ACM Transactions on Mathematical Software, Volume 37(3), article 24, 2010. © ACM Press. [ DOI ]. A preprint version is also available [ Postscript / PDF ]

  • Edge-Selection Heuristics for Computing Tutte Polynomials. David J. Pearce, Gary Haggard and Gordon Royle. In the Chicago Journal of Theoretical Computer Science, Volume 2010, article 6, 2010. [ CJTCS Link ]. 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. [ DOI ] 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. [ DOI ] 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

  • Comparing Graph Layouts for Vertex Selection Tasks. Roma Klapaukh, David J. Pearce and Stuart Marshall. In Proceedings of the Australian Conference on Human Computer Interaction (OzCHI), (to appear), 2015. [ PDF / Conference Website ]

  • The Whiley Rewrite Language (WyRL). David J. Pearce. In Proceedings of the Conference on Software Language Engineering (SLE), pages 161--166, 2015. [ PDF / Conference Website ]

  • Towards a Vertex and Edge Label Aware Force Directed Layout Algorithm. Roma Klapaukh, David J. Pearce and Stuart Marshall. In Proceedings of the Australasian Computer Science Conference (ACSC), pages 29--37, 2014. [ PDF / Conference Website ]

  • Whiley: a Platform for Research in Software Verification. David J. Pearce and Lindsay Groves. In Proceedings of the Conference on Software Language Engineering (SLE), volume 8225 of Lectures Notes in Computer Science, pages 238--248, 2013. A preliminarly copy is available [ PDF / Slides / DOI / Conference Website ]

  • OwnKit: Inferring Modularly Checkable Ownership Annotations for Java. Constantine Dymnikov, David J. Pearce and Alex Potanin. In Proceedings of the Australasian Software Engineering Conference (ASWEC), pages 181--190, 2013. A preliminarly copy is available [ PDF / Slides / DOI / Conference Website ]

  • Sound and Complete Flow Typing with Unions, Intersections and Negations. David J. Pearce. In Proceedings of the Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI), volume 7737 of Lecture Notes in Computer Science, pages 335--354, 2013. © Springer-Verlag [ Postscript / PDF / Slides / DOI / Conference Website ]

  • Patterns as Objects in Grace. Michael Homer, James Noble, Kim B. Bruce, Andrew P. Black and David J. Pearce. In Proceedings of the Dynamic Languages Symposium (DLS), pages 17--28, 2012. © ACM Press. [ PDF / Conference Website ]

  • Profiling Field Initialization for Java. Stephen Nelson, David J. Pearce and James Noble. In Proceedings of the Conference on Runtime Verification (RV), volume 7687 of Lecture Notes in Computer Science, pages 292--307, 2012. © Springer-Verlag [ PDF / PPT / Conference Website ]

  • JPure: a Modular Purity System for Java. David J. Pearce. In Proceedings of the Conference on Compiler Construction, volume 6601 of Lecture Notes in Computer Science, pages 104--123, 2011. © Springer-Verlag [ Postscript / PDF / PPT / Conference Website ]

  • Understanding the Impact of Collection Contracts on Design. Stephen F. Nelson, David J. Pearce and James Noble. In Proceedings of the Conference on Objects, Models, Components, Patterns (TOOLS EUROPE), volume 6141 of Lecture Notes in Computer Science, pages 61--78, 2010. © Springer-Verlag [ PDF / DOI / Conference Website ]

  • 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 / Conference Website ]

  • 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), Article 26, 2008. © ACM Press. [ Postscript / PDF / DOI / 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 / DOI / 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 / DOI / 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 / DOI / 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 / DOI / 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

  • A Mechanical Soundness Proof for Subtyping over Recursive Types. Timothy Jones and David J. Pearce. In Proceedings of the Workshop on Formal Techniques for Java-like Languages (FTFJP), (to appear), 2016.

  • Some Usability Hypotheses for Verification. David J. Pearce. In Proceedings of the Workshop on Evaluation and Usability of Programming Languages (PLATEAU), [ PDF / Workshop Website ], 2015.

  • Integer Range Analysis for Whiley on Embedded Systems. David J. Pearce. In Proceedings of the IEEE/IFIP Workshop on Software Technologies for Future Embedded and Ubiquitous Systems, pages 26--33, 2015. © IEEE Computer Society Press [ PDF / DOI / Workshop Website ]

  • Reflections on Verifying Software with Whiley. David J. Pearce and Lindsay Groves. In Proceedings of the Workshop on Formal Techniques for Safety-Critical Systems (FTSCS), Communications in Computer and Information Systems (CCIS), 419:142--159, 2014. [ PDF / Workshop Website ]

  • A Calculus for Constraint-Based Flow Typing. David J. Pearce. In Proceedings of the Workshop on Formal Techniques for Java-like Languages (FTFJP), Article 7, 2013. [ Postscript / PDF / DOI / slides / Workshop Website ]

  • Balloon Types for Safe Parallelisation over Arbitrary Object Graphs. Marco Servetto, David J. Pearce, Lindsay Groves, and Alex Potanin. In Proceedings of the Workshop on Determinism and Correctness in Parallel Programming (to appear), 2013. A preliminary copy is available: [ PDF / Workshop Website ]

  • A Calculus for Constraint-Based Flow Typing. David J. Pearce. Presented at the Workshop on Behavioural Types, 2013. [ Postscript / PDF / Slides / Workshop Website ]

  • Implementing relationships using Affinity. Stephen F. Nelson, David J. Pearce and James Noble. In Proceedings of the Workshop on Relationships and Associations in Object-Oriented Languages (RAOOL), 2009. [ DOI / 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. [ DOI / Conference Website ]

  • Implementing First-Class Relationships in Java. Stephen F. Nelson, David J. Pearce and James Noble. In Proceedings of the Workshop on Relationships and Associations in Object-Oriented Languages (RAOOL), 2008. [ Conference Website ]

  • Object State Querying for Optimisation. David J. Pearce and James Noble. In Proceedings of the Workshop on Multiparadigm Programming with Object-Oriented Languages (MPOOL), 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 / DOI / 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 ]

Book Chapters

  • Software Language Engineering - 7th International Conference. Benoit Combemale, David J. Pearce, Olivier Barais, Jurgen J. Vinju (Eds.). LNCS 8706, 2014. [ SpringerLink ]

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

  • Graceful Language Extensions and Interfaces. Michael Homer, PhD Thesis, Victoria University of Wellington, 2014. [ PDF ].

  • An Empirical Evaluation of Force-Directed Graph Layout. Roman Klapaukh, PhD Thesis, Victoria University of Wellington, 2014. [ PDF ].

  • Maintaining Private Views in Java. Paran Haslett, MSc Thesis, Victoria University of Wellington, 2014. [ PDF ].

  • Profiling Initialisation Behaviour in Java. Stephen Nelson, PhD Thesis, Victoria University of Wellington, 2012. [ PDF ].

  • OwnKit: Ownership Inference for Java. Constantine Dymnikov, MSc Thesis, Victoria University of Wellington, 2011. [ PDF ].

  • 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

  • Practical Verification Condition Generation for a Bytecode Language. David J. Pearce, Victoria University of Wellington, Technical Report #ECSTR14-07, 2014. [ PDF ]

  • Reflections on Verifying Software with Whiley. David J. Pearce and Lindsay Groves, Victoria University of Wellington, Technical Report #ECSTR13-06, 2013. [ PDF ]

  • Sound and Complete Flow Typing with Unions, Intersections and Negations. David J. Pearce, Victoria University of Wellington, Technical Report #ECSTR12-20, 2012. [ Postscript / PDF ]

  • A Calculus for Constraint-Based Flow Typing. David J. Pearce, Victoria University of Wellington, Technical Report #ECSTR12-10, 2012. [ Postscript / PDF ]

  • An Algorithmic Framework for Recursive Structural Types. David J. Pearce, Victoria University of Wellington, Technical Report #ECSTR11-10, 2011. [ Postscript / PDF ]

  • Structural and Flow-Sensitive Types for Whiley. David J. Pearce and James Noble, Victoria University of Wellington, Technical Report #ECSTR10-23, 2010. [ Postscript / PDF ]

  • A Featherweight Calculus for Flow-Sensitive Type Systems in Java. David J. Pearce, Victoria University of Wellington, Technical Report #ECSTR10-19, 2010. [ Postscript / PDF ]

  • 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

  • Whiley: a Language with Extended Static Checking Whiley is a hybrid object-oriented and functional programming language. Whiley employs extended static checking to eliminate errors at compile time, including divide-by-zero, array out-of-bounds and null dereference errors. Extended static checking is made possible through the use of an automated theorem prover. Whiley compiles to the Java Virtual Machine and is fully interoperable with existing Java applications. You can more information about Whiley here.

  • The Java JPurity System (JPure) JPure is a novel purity system for Java that employs purity annotations which can be checked modularly. This is done using a flow-sensitive, intraprocedural analysis.

  • 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 Students where age < 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.




Auckland

London

New York

Los Angeles