Parallel functional programming, abstract machines and strictness analysis
Clack's early work with Simon Peyton Jones and others focused on the design and development of the “Graph Reduction In Parallel” (GRIP) machine for parallel functional programming, including system architecture design, strictness analysis and abstract machine design; his work in this area continued beyond the GRIP project with the development of a dynamic profiling technique and advisory work in system architecture design for securities settlement systems in the finance sector.
Strictness analysis via abstract interpretationThe Church-Rosser theorem makes functional programs well suited to parallel evaluation, since (caveat termination) order of execution does not affect the result. However, unrestricted parallel evaluation can destroy the strong termination properties of Normal Order evaluation. Abstract interpretation could theoretically determine which parts of a program would always be executed during Normal Order evaluation, thereby giving a route to parallel evaluation and strong termination properties, but a practical and efficient algorithm was missing. Clack and Peyton Jones [1] were the first to address the practical challenge, based on foundational work by Mycroft, and this was the springboard for the enormously successful GRIP project. This seminal paper has 150 citations, and influenced other publications by Clack that have attracted over 425 additional citations by researchers from over 27 countries in total. One of those other pubilcations [2] gives a particulalrly nice example of a combinatorially implosive algorithm for searching a very large lattive with a monotinicity constraint. Many seminal features of the GRIP project were subsequently used in systems developed by other academic research teams: e.g. the <ν,G> Machine, the HDG Machine and DREAM. Some of the architecture design was used in the ICL/Fujitsu Goldrush parallel database system. Key publications are: [1] Clack, C.D., Peyton Jones, S.L. (1985). Strictness analysis — a practical approach. Lecture Notes in Computer Science, 201 35-49. doi:10.1007/3-540-15975-4_28 [2] C.D. Clack and S.L. Peyton Jones (1987) Finding fixpoints in abstract interpretation. Chapter 11 (pp 246-265) in Abstract Interpretation of Declarative Languages, ed. Abramsky and Hankin, Ellis Horwood. ISBN 0-7458-0109-9 Abstract machines for parallel graph reduction[3] C.D. Clack and S.L. Peyton-Jones (1986) The four-stroke reduction engine. Proceedings ACM Conference on Lisp and Functional Programming, pp 220-232, Boston (USA) Design and construction of parallel hardware and system software to support parallel functional programming[4] S.L. Peyton-Jones, C.D. Clack, J. Salkild and M. Hardie (1987) GRIP - a high performance architecture for parallel graph reduction. Proceedings IFIP International Conference on Functional Programming Languages and Computer Architecture (FPLCA), Portland (USA), Springer-Verlag LNCS 274, pp 98-112. Lexical profilingSubsequent work on runtime profiling of the time and space performance of lazy functional programs pioneered the concept of attributing lazy evaluation runtime costs to portions of the source code as if strict evaluation had occurred. This assists in identifying which parts of the source code are incurring excessive cost. [5] C.D. Clack, S. Clayman and D.J. Parrott (1995) Lexical Profiling: Theory and Practice. Journal of Functional Programming, Vol 5 No. 2, pp 225-277 ImpactClack's strictness analysis, abstract machines and GRIP research is widely cited and has attracted over 570 citations by researchers from over 27 countries. Strictness analysis provided efficient and correct algorithms to enable the simultaneous benefits of (i) high performance via parallel evaluation and (ii) strong termination properties via non-strict evaluation. The research on strictness analysis, abstract machines and GRIP provided elegant parallel execution of functional programs and included many seminal features, such as the “evaluate and die” model for task communication and coding the dump in the heap, that were subsequently used in abstract machine design and parallel functional programming systems developed by other academic research projects internationally (e.g. the <ν,G> Machine in Sweden, the Parallel ABC Machine in the Netherlands, Alfalfa and Buckwheat in the USA, and DREAM in Germany). GRIP also had broader impact on the development of parallel systems in industry; for example, elements of the GRIP architecture design were used in the ICL/Fujitsu Goldrush parallel database system. Later work on algorithm prototyping techniques using functional languages was transferred to industry and incorporated into Andersen Consulting’s global knowledge base (see below), and further work on garbage collection and memory management led to a patent. Clack was a founder member of IFIP Working Group 2.8 (initially comprising 35 leading international researchers in the field), invited to serve on the JISC-funded Executive Board of the London and South East Centre for High Performance Computing (influencing the uptake of high performance computing in academia and industry), to chair three successive international conferences on the Implementation of Functional Languages (’97-’99) and to be an editor for the three related journal volumes. He was also invited to provide advisory services on computer systems architectures for the Charity Commission and for two leading banks – Clearstream in Luxembourg (settlement systems) and LloydsTSB (payment systems). His work for Clearstream directly contributed to changes in a key component of the international securities settlement infrastructure for the global financial markets:
|