David B. MacQueen Summary of Accomplishments, Jan. 2001 Research Contributions: ----------------------- David MacQueen began his professional career in Mathematical Logic. His Ph.D. thesis (MIT, under Prof. Gerald Sachs) dealt with various problems of generalizing recursion theory to functions of higher types. After a hiatus for military service, he joined Rod Burstall's Theory of Computation research group in the Dept. of Artificial Intelligence at the University of Edinburgh. His first contribution to Computer Science was the development of the semantics and pragmatics of demand driven stream processing programs with Gilles Kahn of INRIA. He developed an experimental implementation of a stream-processing dataflow language and with Kahn explored the expressive power of the paradigm and developed semantic analysis techniques for properties like deadlock and resource management. This was a pioneering contribution to both lazy evaluation and data flow programming, and was reported in an influential paper in the IFIP 77 proceedings ("Coroutines and networks of parallel processes") and a widely circulated INRIA Technical report on "Models of Distributed Computing". From 1978 through 1981, he worked with Rod Burstall on the design of Hope, an early and important example of a pure functional language. Hope was the first language to provide algebraic data types (recursive, parametric, discriminated unions) and pattern matching over such types, with a sophisticated pattern match compiler. Hope used strict evaluation, but provided a lazy datatype of lists. It borrowed polymorphic types and Hindley-Milner type inference from the LCF/ML language. MacQueen implemented Hope in Pop-2 with the assistance of Don Sannella, and later did a second implementation in Lisp. As an extension of Hope he then designed the first version of a true parametric module system ("Structure and Parameterization in a Typed Functional Language", 1981 FPCA). This was the precursor of the module system of Standard ML. MacQueen left Edinburgh at the end of 1979 and joined Steve Crocker's research group at UCS Information Sciences Institute, where he continued collaborating with Burstall and Sannella on the development of Hope and worked with Mike Gordon on single threading in denotational semantics. After a year at ISI, he moved on to Bell Labs, joining Doug McIlroy's department. During the early 1980s at Bell Labs, MacQueen continued work on Hope and early module system designs, while starting to investigate the semantics of types with Ravi Sethi and later Gordon Plotkin. The main idea of this work was the semantic representation of types as order-theoretic ideals in domains (CPOs), and this came to be known as the ideal semantics of types. This work led to influential publications in LFP 82, POPL 84 and Information and Control (1986), workshops on the theory of data types at MIT and CMU in 1983, and the first international symposium on Semantics of Data Types, which MacQueen organized with Gilles Kahn. The resulting flowering of work on types and their applications in programming languages has continued and has become one of the main areas of progress in programming languages during the 1980s and early 1990s, as can be discerned by browsing the proceedings of POPL and LICS during this period. Starting in 1983, during one of his regular visits to Edinburgh, MacQueen began collaborating with Robin Milner, Rod Burstall, Cardelli, and others on the Standard ML language design. The Standard ML language was intended to consolidate developments in ML (such as Cardelli's 1981 dialect) as well as Hope. MacQueen was involved in the detailed design of the core language, but his major contribution was an elegant and powerful module system derived from his earlier Hope-based prototype (LFP 1984). The main characteristics of this design are the independence of interfaces (signatures) and implementations (structures) and the ability to define parametric modules by lambda-abstracting over module names typed by their interfaces. Later (POPL 1986), MacQueen gave a type-theoretic analysis of the Standard ML module design, using dependent types, that became the starting point for several later studies of the foundations of module systems (e.g. Harper-Mitchell, Harper-Mitchell-Moggi, Harper-Stone, Leroy,...). Also, in 1985 MacQueen and Cardelli wrote a paper on "Persistence and Type Abstraction" for the Datatypes and Persistence workshop that was a precursor of later work on the "dot-notation" approach to module semantics (Cardelli-Leroy, Leroy). In 1986, MacQueen began to work with Andrew Appel, who had just joined the faculty of Princeton University, on a new implementation of Standard ML that they called "Standard ML of New Jersey" (SML/NJ for short). This implementation soon developed into the most widely used ML implementation because of it's robustness and efficiency, and the fact that the implementation was ported to most of the leading architectures and operating systems (eventually including PCs and Macs). Because SML/NJ was written in Standard ML, and was distributed freely with source code, it also became a platform for several other language and compiler research efforts. Many modern systems for interactive theorem proving (HOL 90, Isabelle, Lego, ELF, Lambda-Prolog, STeP,...) and formal methods (Concurrency Workbench, Design ML, ...) are implemented in SML/NJ. SML/NJ has been used both for implementing major systems, and as an experimental testbed for language development. In 1991-2, MacQueen, Appel and Bruce Duba added first-class continuations to SML/NJ, and MacQueen, Harper and Duba established the soundness of the typing of first-class continuations (JFP 1993). In 1992-3, MacQueen and Pierre Cregut added higher-order functors (parametric modules) to SML/NJ, and MacQueen and Mads Tofte developed their semantics (ESOP 94). Also, in 1993-94, MacQueen and Andrew Appel developed an innovative compiler architecture that enables a sophisticated compilation manager that implements efficient cutoff recompilation, and a "visible compiler" interface that allows user programs to access internal mechanisms and data structures of the compiler, like environments and abstract syntax. During a stay at the Newton Institute at Cambridge University in 1995, MacQueen joined with Robin Milner, Robert Harper, and Mads Tofte to begin a revision of the Standard ML design to correct problems and add capabilities that had been discovered since the original design was completed in 1989. This redesign incorporated several features that had been implemented in SML/NJ as experimental extensions. During 1996-7, the SML/NJ compiler was updated to implement the resulting revised language, called SML '97. In 1993, MacQueen, Robert Harper, and John Mitchell began discussions aiming toward a next generation ML family language, with a working title of ML2000. In a series of annual meetings they and a small group of talented language researchers have been discussing the design questions and related problems of semantics and implementation that are involved in making progress beyond ML. A number of research results have come out of these discussions, and as well as some concrete design proposals (e.g. Moby). Professional Contributions: --------------------------- David MacQueen has been professionally active in the field of programming languages, as indicated by the following list of activities. * Conference Chair/Organizer - 1984 International Symposium on Semantics of Types - 1988 25th ACM POPL Symposium * Workshop organizer ML Workshops - 1989 Princeton ML Workshop (with A. Appel) - 1990 Edinburgh ML Workshop (with A. Mycroft, K. Mitchell?, ...) - 1992 San Francisco: ACM SIGPLAN Workshop on ML and its Applications - 1998 Baltimore: ACM SIGPLAN Workshop on ML Theory of Data Types Workshops - 1983 MIT - 1983 CMU * Program Committee chairmanships - 1989 4th International Conference on Functional Programming and Computer Architecture - 1989 ACM Symposium on Principles of Programming Languages - 1984 International Symposium on Semantics of Data Types, Sophia-Antipolis (with G. Kahn, G. D. Plotkin) * Program Committee memberships - 1993 ACM Symposium on Principles of Programming Languages - 1986 ACM Symposium on Lisp and Functional Programming - 1984 ACM Symposium on Principles of Programming Languages - 1981 ACM Conference on Functional Programming Languages and Computer Architecture * Charter (founding) member of IFIP Working Group 2.8 (Functional Programming) In addition, as head of the Software Principles Research Department at Bell Labs, he built up a strong research group in programming languages (semantics, type theory, design, compilation, gc & runtime systems) and applied logic/formal methods. In the mid-90s, this was one of the two or three strongest such groups in the US. During his career, MacQueen hs mentored, supported and encouraged the development of young researchers, including Luca Cardelli (Microsoft Cambridge Lab) John Mitchell (Stanford University) Robert Harper (Carnegie-Mellon University) James Hook (OGI, PacSoft director) Andrew Tolmach (Portland State, PacSoft) John Reppy (Bell Labs) Jon Riecke (Bell Labs) Elsa Gunter (Bell Labs) Amy Felty (Bell Labs) Leonid Libkin (Bell Labs) Nevin Heintze (Bell Labs) Trevor Jim (U. Penn) Pierre Cregut (France Telecom) (other summer students: D. Tarditi, G. Morrisett, D. Doligez, ...) He is an active member of the New Jersey Programming Systems Seminar, which brings together programming languages and compiler researchers from the mid-Atlantic area. He has taught various courses on topics such as Programming Languages, Types, Semantics of Prog. Languages, at Univ. of Penn, Princeton, NYU, Rutgers Univ, and Edinburgh Univ, and has given numerous invited seminar talks at universities and research institutions. Impact: * His pioneering work on lazy evaluation and demand-driven dataflow programming with Gilles Kahn in the mid 1970s has had a wide and continuing impact. * He helped initiate a major push to develop type theory and its applications to programming languages in the early 1980s (with Sethi and Plotkin). * He worked to develop ML into a general-purpose language incorporating modern programming language ideas like type safety, modularity, higher-order functions, algebraic types and pattern matching, and exception handling, and through Standard ML made these ideas available to a wide audience. * The development of SML/NJ with Andrew Appel and many other collaborators, in a sustained effort over the last fourteen years, has helped push the implementation technology for modern high level languages and has provided an excellent tool for research, education, and practical system development. * His module system for SML is a very successful example of principled programming language design, providing power and elegance based on well-defined principles and mathematical models. * He has influenced, worked with, and promoted the development of a generation of talented young researchers in programming languages and type theory during the 1980s and 90s.