Other Research
Other research areas past and present include:
- Efficient fixpointing in abstract domains (1984 - 1987)
- Abstract interpretation of computer programs can derive compile-time information about whether or not a function always evaluates its arguments. This information is essential for parallel functional programming systems that support lazy evaluation and retain the termination characteristics of normal-order evaluation. Unfortunately, the time complexity of the algorithms to derive this information can be exponential in the number of arguments to a function. The problem reduces to how to detect convergence of the ascending Kleene chain of a function in the abstract domain; specifically, how to discover the extensional equality of two monotonic boolean functions. Though worst-case behaviour may remain exponential, is it possible to find the fixed point efficiently for the common, well-behaved functions? (Clack & Peyton Jones 1985) and (Peyton Jones & Clack 1987) provide detailed practical guidance, identify mistakes in previous published work, and introduce a new combinatorially-implosive technique based on tracking "frontiers" in lattices of finite height.
- An abstract machine for parallel graph reduction (1985 - 1987)
- In the early 1980s, parallel functional programming was a technology with huge potential, seeming to offer "painless parallelism'" due to the lack of side effects. However, the ALICE system was disappointingly slow --- 16,000 nfibs/sec on 32 processors, i.e. about four times slower than nfib running on a single sequential processor! Did this presage some fundamental problem with parallel functional programming, or was the ALICE prototype technology simply immature? The way forward for parallel evaluation was unclear: could the compiler truly bridge the gap between the highly abstract functional program source and the details of parallel execution? The design of abstract machines for parallel graph reduction became a hot research topic. The four-stroke reduction engine (4SRE - see (Clack & Peyton Jones 1986)) was one of the earliest such abstract machines, and the first to be implemented on the GRIP parallel architecture. It focused (inter alia) on the following research questions: (i) how should results be communicated between parallel tasks? (ii) should data be copied or pointers used? (iii) how should the dump be encoded? (iv) how should parallelism be managed? (v) how should task interaction (blocking and resumption) be managed? The 4SRE was the progenitor of several novel features that are found in subsequent parallel functional programming systems: e.g. the "evaluate and die" model for transparent communication of results from child to parent tasks; the encoding of the dump in the heap; several novel mechanisms for throttling parallelism (including "discardable sparks" and preferential resumption of suspended tasks); and the lack of explicit communication between tasks.
- Foundational work in Intelligent Systems
- Intelligent Systems applied to commerce
- Dynamic Memory Management (see MemWise)
- Functional Programming Languages
- High Performance Computing (Parallel Architectures, Static Analysis Techniques)
My PhD students past and present:
- Tristan Fletcher - Intelligent Systems in Finance. Subsequently changed research direction and supervisor
- Samet Gogus (Barclays Treasury) - Credit risk
- Ghada Hassan (Egyptian Culture Bureau) - Intelligent Systems in Finance
- Chih-Chun Chen (EPSRC DTA) - Intelligent Systems in Biology
- Manish Patel (I am Manish's second supervisor) - model integration for computational biology
- David Coffin (EPSRC) - Intelligent Systems (GA search space decomposition) - subsequently changed research direction and supervisor
- Wei Yan (industry) - Intelligent Systems in Finance (GP for portfolio optimisation)
- Katie Bentley (industry / DTA) - "Adaptive Behaviour through Morphological Plasticity in Natural and Artificial Systems" 2006
- Lee Braine (EPSRC CASE) - "Design and Implementation of an Object-Oriented Functional Language" 2000
- Kanta Vekaria (EPSRC 97701326) - Intelligent Systems: "Selective Crossover as an Adaptive Strategy for Genetic Algorithms" 2000 (link to thesis)
- Tina Yu - Intelligent Systems: "An Analysis of the Impact of Functional Programming Techniques on Genetic Programming" 1999 (link to thesis)
- Simon Courtenage (EPSRC 90311629) - "The Analysis of Resource Use in the Lambda-Calculus by Type Inference" 1995 (link to thesis)
- Stuart Clayman (SERC) - "Developing and Measuring Parallel Rule-Based Systems in a Functional Programming Environment" 1993 (link to thesis)
- David Parrott - "Synthesising Parallel Functional Programs to Improve Dynamic Scheduling" 1993
An incomplete list of PhDs I have examined:
- Behzad Behzadan (UCL, 2011)
- Andrew Cheadle (Imperial, 2010)
- Sebastien Marion - Using Class-Level Static Properties and Data Mining to Predict Object Lifetimes(Kent, 2009)
- Trevor A. Graham - The expansion of mutant clones in tumorigenesis (UCL, 2009)
- Kun (Max) Jiang - MILCS: A Mutual Information based Learning Classifier System (UCL, 2009)
- Adrian Ramirez-Cabrera - An Extension of the Strong Typing Genetic Programming Model (MPhil, Manchester, 2000)
- Benoit Lanaspre - Static Analysis for Distributed Prograph (Southampton, 1997)
- Jin Yang - Co-ordination Based Structured Parallel Programming (Imperial, 1997)
- Patrick J. Wright - Optimised Redundant Cell Collection for Graph Reduction (UCL, 1993)
- David Lillie - Polymorphic Subtype Inference in Combinator Languages (Imperial, 1992)
- Guido K. Jouret - Exploiting Data-Parallelism in Functional Languages (Imperial, 1991)
List of publications:
