<HTML> <TITLE>The Mercury Project: Papers and Presentations</TITLE> <BODY bgcolor="#ABCDEF" text="#000000"> <TABLE border="0" cellpadding="5" cellspacing="0" width="100%"> <TR> <TD> <CENTER><H1>The Mercury Project Papers and Presentations </H1></CENTER> </TD> <TD width="10%"> <IMG SRC="../images/merclogo_small.jpg" border="2" hspace="10" width="147" height="130" ALT="[Mercury Logo]"> </TD> </TR> </TABLE> <TABLE border="0" cellpadding="5" cellspacing="0" width="100%"> <TR> <TD valign="top" bgcolor="#fcf4d4" width="15%"> <a href="../index.html">Home</a> <a href="../news.html">News</a> <a href="../information.html">Information</a> <a href="../information/motivation.html">Overview</a> <a href="../information/features.html">Features</a> <a href="../information/benchmarks.html">Benchmarks</a> <a href="../information/papers.html">Papers</a> <a href="../information/deep_demo.html">Deep profiler demo</a> &nbsp<a href="../information/developer.html">Developers</a> &nbsp<a href="../information/events.html">Events</a> &nbsp<a href="../information/reports.html">Reports</a> <a href="../information/documentation.html">Documentation</a> <a href="../mailing-lists/mailing-lists.html">Mailing Lists</a> <a href="../backends.html">Back-ends</a> <a href="../download.html">Download</a> <a href="../information/related.html">Related</a> <a href="../contact.html">Contact</a> <a href="../search.html">Search</a> </TD> <TD valign="top">  <h2>Papers and Presentations</h2> The Mercury team have written quite a few papers about the Mercury programming language, its implementation techniques, design, theoretical basis and other topics. In addition, we have written several papers on <a href = "papers.html#related">related</a> topics. Almost all are available here as postscript files, compressed using gzip. Below the papers, the notes from a number of <a href="papers.html#presentations">presentations</a> given on Mercury, at a variety of levels, are also available. <h2>Contents</h2> <h3><a href = "papers.html#mercury">Papers on Mercury</a></h3> <ul> <li> Towards parallel Mercury Thomas Conway. Ph.D. thesis, Department of Computer Science and Software Engineering, The University of Melbourne, July 2002. <a href = "papers.html#conway-thesis"> Available below (562K). </a> <li> Expressive type systems for logic programming languages David Jeffery. Ph.D. thesis, Department of Computer Science and Software Engineering, The University of Melbourne, February 2002. <a href = "#dgj-thesis-final"> Available below (370K). </a> <li> Constraint-based mode analysis of Mercury David Overton, Zoltan Somogyi and Peter Stuckey to appear in the Proceedings of the Fourth International Conference on Principles and Practice of Declarative Programming, Pittsburgh, Pennsylvania, October 2002. <a href = "#p33-overton"> Available below (188K). </a> <li> Using the heap to eliminate stack accesses Zoltan Somogyi and Peter Stuckey to appear in the Proceedings of the Fourth International Conference on Principles and Practice of Declarative Programming, Pittsburgh, Pennsylvania, October 2002. <a href = "papers.html#p81-somogyi"> Available below (190K). </a> <li> Accurate garbage collection in an uncooperative environment Fergus Henderson Proceedings of the 2002 International Symposium on Memory Management Berlin, Germany, June 2002, pages 150-156. <a href = "papers.html#high_level_gc"> Available below (83K). </a> <li> Compiling Mercury to the .NET Common Language Runtime Tyson Dowd, Fergus Henderson, and Peter Ross BABEL'01 First International Workshop on Multi-Language Infrastructure and Interoperability, Firenze, Italy, September 2001. Preliminary Proceedings pages 70-85. To appear in Electronic Notes in Theoretical Computer Science 59.1. <a href = "papers.html#mercury_to_clr"> Available below (93K). </a> <li> Compiling Mercury to high-level C code Fergus Henderson and Zoltan Somogyi Proceedings of the 2002 International Conference on Compiler Construction Grenoble, France, April 2002. © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href = "papers.html#hlc_cc">Available below (67K)</a>. </a> <li> Deep profiling: engineering a profiler for a declarative programming language Thomas C. Conway and Zoltan Somogyi Technical Report 2001/24, Department of Computer Science, University of Melbourne, Melbourne, Australia, July 2001, 61 pages. <a href = "papers.html#mu_01_24"> Available below (207K). </a> <li> Practical aspects for a working compile time garbage collection system for Mercury Nancy Mazur, Peter Ross, Gerda Janssens and Maurice Bruynooghe Proceedings of ICLP 2001 - Seventeenth International Conference on Logic Programming , Paphos, Cyprus, November 2001. Lecture Notes in Computer Science 2237, Springer Verlag, Pages 105-119 © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href = "papers.html#iclp2001_ctgc"> Available below (84K). </a> <li> Binding-time analysis by constraint solving: a modular and higher-order approach for Mercury Wim Vanhoof Proceedings of the Seventh International Conference on Logic for Programming and Automated Reasoning , Reunion Island, France, November 2000. Lecture Notes in Computer Science 1955, Springer Verlag, Pages 399-416 © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers.html#bta_higher_order">Available below (106K)</a>. <li> A module based analysis for memory reuse in Mercury Nancy Mazur, Gerda Janssens and Maurice Bruynooghe Proceedings of the First International Conference on Computational Logic , London, United Kingdom, July 2000. Lecture Notes in Artificial Intelligence, Springer Verlag, Pages 1255-1269 © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers.html#memory_reuse_analysis">Available below (93K)</a>. <li> Making Mercury programs tail recursive Peter Ross, David Overton and Zoltan Somogyi Proceedings of the Ninth International Workshop on Logic-based Program Synthesis and Transformation, Venice, Italy, September 1999. To appear in Lecture Notes in Computer Science, Springer Verlag, © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers.html#tail_lopstr_lncs">Available below (84K)</a>. <li> State update transformation Peter Ross and Zoltan Somogyi <a href="papers.html#update">Available below (57K)</a>. <li> Using impurity to create declarative interfaces in Mercury Tyson Dowd, Peter Schachte, Fergus Henderson and Zoltan Somogyi <a href="papers.html#purity">Available below (52K)</a>. <li> Towards memory reuse for Mercury Nancy Mazur, Gerda Janssens and Maurice Bruynooghe Proceedings of the International Workshop on Implementation of Declarative Languages , Paris, France, October 1999 <a href="papers.html#liveness">Available below (61K)</a>. <li> Binding-time analysis for Mercury Wim Vanhoof and Maurice Bruynooghe Proceedings of the Sixteenth International Conference on Logic Programming , Las Cruces, New Mexico, November 1999, pages 500-514 <a href="papers.html#bta">Available below (76K)</a>. <li> The implementation technology of the Mercury debugger Zoltan Somogyi and Fergus Henderson. Proceedings of the Tenth Workshop on Logic Programming Environments , Las Cruces, New Mexico, November 1999, pages 35-49. <a href="papers.html#debugger_wlpe99">Available below (66K)</a>. <li> Making Mercury programs tail recursive (extended abstract) Peter Ross, David Overton and Zoltan Somogyi. Pre-Proceedings of the Ninth International Workshop on Logic-based Program Synthesis and Transformation , Venice, Italy, September 1999, pages 107-118. <a href="papers.html#tail_lopstr">Available below (62K)</a>. <li> Run time type information in Mercury Tyson Dowd, Zoltan Somogyi, Fergus Henderson, Thomas Conway and David Jeffery. Proceedings of the International Conference on the Principles and Practice of Declarative Programming , Paris, France, September/October 1999, Lecture Notes in Computer Science 1702, Springer Verlag, Pages 224-243, © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers.html#rtti_ppdp">Available below (75K)</a>. <li> Optimization of Mercury programs Simon Taylor. Honours report. Department of Computer Science, University of Melbourne, November 1998. <a href = "papers.html#stayl_hons"> Available below (120K). </a> <li> MCORBA: A CORBA Binding for Mercury David Jeffery, Tyson Dowd and Zoltan Somogyi. In Proceedings of the First International Workshop on Practical Aspects of Declarative Languages , San Antonio, Texas, January 1999, Lecture Notes in Computer Science 1551, Springer Verlag, Pages 211-227, © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers.html#mcorba_padl99">Available below (65K)</a>. <li> Type classes in Mercury David Jeffery, Fergus Henderson and Zoltan Somogyi. Technical Report 98/13, Department of Computer Science, University of Melbourne, Melbourne, Australia, September 1998, 22 pages. <a href = "papers.html#mu_98_13"> Available below (82K). </a> <li> Termination analysis for Mercury Chris Speirs, Zoltan Somogyi and Harald Sondergaard. Proceedings of the Fourth Static Analysis Symposium , Paris, France, September 1997, pages 157-171. <a href = "papers.html#sas97">available below (75K)</a>. <li> Status of the Mercury system Zoltan Somogyi, Fergus Henderson, Thomas Conway, Andrew Bromage, Tyson Dowd, David Jeffery, Peter Ross, Peter Schachte and Simon Taylor. Proceedings of the JICSLP '96 Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Bonn, Germany, September 1996, pages 207-218. <a href = "papers.html#jicslpw">Available below (46K)</a>. <li> The execution algorithm of Mercury: an efficient purely declarative logic programming language Zoltan Somogyi, Fergus Henderson and Thomas Conway. Journal of Logic Programming, volume 29, number 1-3, October-December 1996, pages 17-64. <a href = "papers.html#jlp">Available below (138K)</a>. Elsevier owns the copyright of this paper; it is made available here by their permission. <li> Determinism analysis in the Mercury compiler Fergus Henderson, Zoltan Somogyi and Thomas Conway. Proceedings of the Australian Computer Science Conference, Melbourne, Australia, January 1996, pages 337-346. <a href = "papers.html#acsc96">Available below (78K)</a>. <li> Code generation for Mercury Thomas Conway, Fergus Henderson, and Zoltan Somogyi. Proceedings of the 1995 International Symposium on Logic Programming, Portland, Oregon, December 1995, pages 242-256. <a href = "papers.html#code_gen_mit">Available below (68K)</a>. <li> Compiling logic programs to C using GNU C as a portable assembler Fergus Henderson, Zoltan Somogyi and Thomas Conway. Proceedings of the ILPS '95 Postconference Workshop on Sequential Implementation Technologies for Logic Programming Languages. Portland, Oregon, December 1995. <a href = "papers.html#mercury_to_c">Available below (65K)</a>. <li> Mercury: an efficient purely declarative logic programming language Zoltan Somogyi, Fergus Henderson and Thomas Conway. Proceedings of the Australian Computer Science Conference, Glenelg, Australia, February 1995, pages 499-512. <a href = "papers.html#acsc95">Available below (85K)</a>. <li> The implementation of Mercury: an efficient purely declarative logic programming language Zoltan Somogyi, Fergus Henderson and Thomas Conway. Proceedings of the ILPS '94 Postconference Workshop on Implementation Techniques for Logic Programming Languages, Syracuse, New York, November 1994. <a href = "papers.html#ilps94w">Available below (96K)</a>. <li> Code generation for Mercury Thomas Conway. Honours report. Department of Computer Science, University of Melbourne, November 1994. <a href = "papers.html#conway_hons">Available below (188K)</a>. </ul> <h3><a href = "papers.html#related">Related papers</a></h3> <ul> <li> Termination analysis for logic programs Chris Speirs. Technical Report 97/23, Department of Computer Science, University of Melbourne, October 1997. <a href = "papers.html#mu_97_23"> Available below (67K). </a> <li> Logic programming for the real world Zoltan Somogyi, Fergus Henderson, Thomas Conway and Richard O'Keefe. Proceedings of the ILPS '95 Postconference Workshop on Visions for the Future of Logic Programming, Portland, Oregon, December 1995. <a href = "papers.html#vision"> Available below (59K). </a> <li> A system of precise modes for logic programs Zoltan Somogyi. Proceedings of the Fourth International Conference on Logic Programming, Melbourne, Australia, May 1987, pages 769-787. <a href = "papers.html#iclp87"> Available below (40K). </a> <li> Strong modes can change the world! Fergus Henderson. Honours Report. Department of Computer Science, University of Melbourne, November 1992. <a href = "papers.html#fjh_hons_thesis"> Available below (114K). </a> <li> Database transactions in a purely declarative logic programming language David B. Kemp, Thomas Conway, Evan Harris, Fergus Henderson, Kotagiri Ramamohanarao and Zoltan Somogyi. Technical Report 96/45 Department of Computer Science, University of Melbourne, December 1996. <a href = "papers.html#mu_96_45"> Available below (58K) </a> </ul>  <h3><a href = "papers.html#presentations">Presentations</a></h3> <ul> <li> <a name="sas_talk"> Termination analysis for Mercury </a> Chris Speirs, Zoltan Somogyi and Harald Sondergaard. Talk presented at the Fourth Static Analysis Symposium. Paris, France, September 1997. <a href = "papers.html#sas_talk"> Available below (6K). </a> <li> <a name="unif"> Unification in Mercury </a> Zoltan Somogyi. Invited talk presented at the Eighth Benelux Workshop on Logic Programming. Louvain-la-Neuve, Belgium, September 1996. <a href = "papers.html#unif"> Available below (12K). </a> <li> <a name="jicslp_talk"> The design and implementation of Mercury </a> Zoltan Somogyi and Fergus Henderson. Tutorial presented at the Joint International Conference and Symposium on Logic Programming. Bonn, Germany, September 1996. <a href = "papers.html#jicslp_talk"> Available below (18K). </a> <li> <a name="jicslpw_talk"> Status of the Mercury system </a> Zoltan Somogyi, Fergus Henderson, Thomas Conway, Andrew Bromage, Tyson Dowd, David Jeffery, Peter Ross, Peter Schachte and Simon Taylor. Presented at the JICSLP '96 Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Bonn, Germany, September 1996. <a href = "papers.html#jicslpw_talk"> Available below (5K). </a> <li> <a name="acsc95_slides"> Mercury: an efficient purely declarative logic programming language </a> Zoltan Somogyi, Fergus Henderson and Thomas Conway. Presented at the Eighteenth Australasian Computer Science Conference, Adelaide, South Australia, February 1995. <a href = "papers.html#acsc95_slides"> Available below (33K). </a> <li> <a name="257_1999"> Lecture notes for the expanded Mercury segment of the subject 433-257 Frontiers of Computer Science, given in 1999 (whereas the segment in 1997 had four lectures, in 1999 it had six) </a> Zoltan Somogyi. <a href = "papers.html#257_1999"> Available below (40K). </a> <li> <a name="257"> Lecture notes for the Mercury segment of the subject 433-257 Frontiers of Computer Science, given in 1997 </a> Zoltan Somogyi. <a href = "papers.html#257"> Available below (21K). </a> <li> <a name="247"> Lecture notes for the Mercury segment of the subject 433-247 Frontiers of Computer Science, given in 1995 </a> Zoltan Somogyi. <a href = "papers.html#247"> Available below (21K). </a> <li> <a name="dgj-talk"> Type classes for logic programming languages, given in March 1998 </a> David Jeffery. <a href = "papers.html#dgj-talk"> Available below (30K). </a> <li> <a name="rtti_talk_98"> Runtime type information in Mercury, given in March 1998 </a> Tyson Dowd. <a href = "papers.html#rtti_talk_98"> Available below (48K). </a> </ul> <hr> <h2><a name="mercury">Papers on Mercury</a></h2> <ul> <li> <a name="conway-thesis"> Towards parallel Mercury </a> Thomas Conway. Ph.D. thesis, Department of Computer Science and Software Engineering, The University of Melbourne, July 2002. <a href = "papers/conway-thesis.ps.gz"> Available here (562K). </a> This thesis presents the foundations for extending the implementation of the declarative logic programming language Mercury to support the parallel execution of programs. The new material in this thesis is in three parts. The first part presents an extension to the existing (sequential) execution model for Mercury that allows programs to be executed in parallel. Programmers can exploit this extension simply by replacing some sequential conjunction operators connecting independent goals with a new parallel conjunction operator. Such changes do not change the declarative semantics of the program, but can improve performance. The second part of the new material presents a model for explicit threading in Mercury, which is useful when the programmer's goal is not efficiency but the explicit representation of concurrent tasks and control of their interactions. We show how our extended execution model supports the usual operations on threads. We also present a new interpretation for Mercury's system for input and output that provides an intuitive understanding of the interactions between the I/O operations executed by the different threads of a program or by different programs. The final part of the new material presented in this thesis presents a new technique for obtaining a detailed and accurate picture of the performance of a program. The basis of our technique is associating a complete context with each measurement, rather than approximating the context as conventional profilers do. In order to make our new profiling system feasible we have had to develop sophisticated techniques for reducing the cost of recording complete contexts; in order to make its output tractable, we also had to develop techniques for dealing with interactions between higher order constructs and recursion. We have also developed a tool for helping programmers (and eventually compilers) to digest the large volume of data generated by our profiling technique. All the ideas presented in this thesis have been implemented in the Melbourne Mercury compiler. <li> <a name="dgj-thesis-final"> Expressive type systems for logic programming languages </a> David Jeffery. Ph.D. thesis, Department of Computer Science and Software Engineering, The University of Melbourne, February 2002. <a href = "papers/dgj-thesis-final.ps.gz"> Available here (370K). </a> The aim of this thesis is the design of a type system for an industrial strength logic programming language. The type system we describe has been implemented for the Mercury programming language, in the Melbourne Mercury compiler. We begin by presenting a simple higher order extension of the Mycroft-O'Keefe type system. We then use this type system as a basis for two significant extensions. The first extension is the adoption of a type class system similar to that found in some modern functional languages in the context of higher order logic programming. We give a set of typing rules which both provide a formal definition of type correctness and define the source-to-source transformation we have used to implement type classes. This transformation is simple and effective, and can be easily shown to preserve Mercury's mode, determinism and uniqueness correctness properties. The second extension is to allow existentially quantified type variables in the types of function symbols and of predicates. This represents the most significant contribution of this thesis. We then formally define the type system that results from the combination of both type classes and existential quantification of type variables. The two type system extensions are quite orthogonal. As a result, the definition of type correctness in the combined system is a fairly simple combination of the definitions for the individual systems. However, the mechanisms contributed by the two systems combine synergistically; the resulting type system is extremely expressive. We then show how the type system we have designed allows the programmer to take advantage of many object oriented design techniques. We give an in depth analysis of object oriented design and isolate the mechanisms which are likely to result in reusable and maintainable software systems. We show that our type system allows the programmer to directly express these kinds of designs and discourages the use of the kinds of object oriented designs which reduce maintainability by introducing unnecessary implementation dependencies. We show that these principles apply in a direct and simple manner to the modelling of component interfaces as supported by modern component frameworks such as CORBA. We present MCORBA, an implementation of a CORBA binding for Mercury. This interface is bi-directional, allowing the programmer to write CORBA components in Mercury and to use existing CORBA components from within Mercury programs. <li> <a name="p33-overton"> Constraint-based mode analysis of Mercury </a> David Overton, Zoltan Somogyi and Peter Stuckey to appear in the Proceedings of the Fourth International Conference on Principles and Practice of Declarative Programming, Pittsburgh, Pennsylvania, October 2002. <a href = "papers/p33-overton.ps.gz"> Available here (188K). </a> Recent logic programming languages, such as Mercury and HAL, require type, mode and determinism declarations for predicates. This information allows the generation of efficient target code and the detection of many errors at compile-time. Unfortunately, mode checking in such languages is difficult. One of the main reasons is that, for each predicate mode declaration, the compiler is required to decide which parts of the procedure bind which variables, and how conjuncts in the predicate definition should be re-ordered to enforce this behaviour. Current mode checking systems limit the possible modes that may be used because they do not keep track of aliasing information, and have only a limited ability to infer modes, since inference does not perform reordering. In this paper we develop a mode inference system for Mercury based on mapping each predicate to a system of Boolean constraints that describe where its variables can be produced. This allows us handle programs that are not supported by the existing system. <li> <a name="p81-somogyi"> Using the heap to eliminate stack accesses </a> Zoltan Somogyi and Peter Stuckey to appear in the Proceedings of the Fourth International Conference on Principles and Practice of Declarative Programming, Pittsburgh, Pennsylvania, October 2002. <a href = "papers/p81-somogyi.ps.gz"> Available here (190K). </a> The value of a variable is often given by a field of a heap cell, and frequently the program will pick up the values of several variables from different fields of the same heap cell. By keeping some of these variables out of the stack frame, and accessing them in their original locations on the heap instead, we can reduce the number of loads from and stores to the stack at the cost of introducing a smaller number of loads from the heap. We present an algorithm that finds the optimal set of variables to access via a heap cell instead of a stack slot, and transforms the code of the program accordingly. We have implemented this optimization in the Mercury compiler, and our measurements show that it can reduce program runtimes by up to 12% while at the same time reducing program size. The optimization is straightforward to apply to Mercury and to other languages with immutable data structures; its adaptation to languages with destructive assignment would require the compiler to perform mutability analysis. <li> <a name="high_level_gc"> Accurate garbage collection in an uncooperative environment </a> Fergus Henderson Proceedings of the 2002 International Symposium on Memory Management Berlin, Germany, June 2002, pages 150-156. <a href = "papers/high_level_gc.ps.gz"> Available here (83K). </a> Previous attempts at garbage collection in uncooperative environments have generally used conservative or mostly-conservative approaches. We describe a technique for doing fully type-accurate garbage collection in an uncooperative environment, using a ``shadow stack'' to link structs of pointer-containing variables, together with the data or code needed to trace them. We have implemented this in the Mercury compiler, which generates C code, and present preliminary performance data on the overheads of this technique. We also show how this technique can be extended to handle multithreaded applications. <li> <a name="mercury_to_clr"> Compiling Mercury to the .NET Common Language Runtime </a> Tyson Dowd, Fergus Henderson, and Peter Ross BABEL'01 First International Workshop on Multi-Language Infrastructure and Interoperability, Firenze, Italy, September 2001. Preliminary Proceedings pages 70-85. To appear in Electronic Notes in Theoretical Computer Science 59.1. <a href = "papers/mercury_to_clr.ps.gz"> Available here (93K). </a> The .NET Common Language Runtime (CLR) offers a new opportunity to experiment with multi-language interoperation, and provides a relatively rare chance to explore deep interoperation of a wide range of programming language paradigms. This article describes how Mercury is compiled to the CLR. We describe the problems we have encountered with generating code for the CLR, give some preliminary benchmark results, and suggest some possible improvements to the CLR regarding separate compilation, verifiability, tail calls, and efficiency. <li> <a name="hlc_cc"> Compiling Mercury to high-level C code </a> Fergus Henderson and Zoltan Somogyi Proceedings of the 2002 International Conference on Compiler Construction Grenoble, France, April 2002. © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href = "papers/hlc_cc.ps.gz">Available here (67K)</a>. </a> Many logic programming implementations compile to C, but they compile to very low-level C, and thus discard many of the advantages of compiling to a high-level language. We describe an alternative approach to compiling logic programs to C, based on continuation passing, that we have used in a new back-end for the Mercury compiler. The new approach compiles to much higher-level C code, which means the compiler back-end and run-time system can be considerably simpler. We present a formal schema for the transformation, and give benchmark results which show that this approach delivers performance that is more than competitive with the fastest previous implementation, with greater simplicity and better portability and interoperability. The approach we describe can also be used for compiling to other target languages, such as IL (the Microsoft .NET intermediate language). The benchmark data on which the performance evaluation section of this paper is based is <a href = "papers/hlc_cc_perf.tar.gz">available here (9.7M)</a>. <li> <a name="mu_01_24"> Deep profiling: engineering a profiler for a declarative programming language </a> Thomas C. Conway and Zoltan Somogyi Technical Report 2001/24, Department of Computer Science, University of Melbourne, Melbourne, Australia, July 2001, 61 pages. <a href = "papers/mu_01_24.ps.gz"> Available here (207K). </a> Declarative programs differ from imperative programs in several respects, the main ones being their heavy use of recursion, of various forms of polymorphism, and of higher order. Existing profilers tend not to produce very useful information in the presence of these constructs. We present a new profiling technique we call \emph{deep profiling} that yields detailed and useful information about programs even in the presence of these constructs, information that is significantly richer than the output of other profilers. The heart of deep profiling is a source-to-source transformation. We have implemented this transformation and its associated infrastructure in the compiler for Mercury, a purely declarative logic programming language. While our measurements of this implementation show that deep profiling has slightly greater overhead than some other profiling techniques, the wealth of information it provides makes this extra overhead worthwhile. The deep profiling algorithms themselves are applicable to most other language styles, including imperative, object-oriented, and functional languages. <li> <a name="iclp2001_ctgc"> Practical aspects for a working compile time garbage collection system for Mercury </a> Nancy Mazur, Peter Ross, Gerda Janssens and Maurice Bruynooghe Proceedings of ICLP 2001 - Seventeenth International Conference on Logic Programming , Paphos, Cyprus, November 2001. Lecture Notes in Computer Science 2237, Springer Verlag, Pages 105-119 © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href = "papers/iclp2001_ctgc.ps.gz"> Available here (84K). </a> Compile-time garbage collection (CTGC) is still a very uncommon feature within compilers. In previous work we have developed a compile-time structure reuse system for Mercury, a logic programming language. This system indicates which datastructures can safely be reused at run-time. As preliminary experiments were promising, we have continued this work and have now a working and well performing near-to-ship CTGC-system built into the Melbourne Mercury Compiler (MMC). In this paper we present the multiple design decisions leading to this system, we report the results of using CTGC for a set of benchmarks, including a real-world program, and finally we discuss further possible improvements. Benchmarks show substantial memory savings and a noticeable reduction in execution time. <li> <a name="bta_higher_order"> Binding-time analysis by constraint solving: a modular and higher-order approach for Mercury </a> Wim Vanhoof Proceedings of the Seventh International Conference on Logic for Programming and Automated Reasoning , Reunion Island, France, November 2000. Lecture Notes in Computer Science 1955, Springer Verlag, Pages 399-416 © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers/bta_higher_order.ps.gz">Available here (106K)</a>. In this paper we present a binding-time analysis for the logic programming language Mercury. Binding-time analysis is a key analysis needed to perform off-line program specialisation. Our analysis deals with the higher-order aspects of Mercury, and is formulated by means of constraint normalisation. This allows (at least part of) the analysis to be performed on a modular basis. <li> <a name="memory_reuse_analysis"> A module based analysis for memory reuse in Mercury </a> Nancy Mazur, Gerda Janssens and Maurice Bruynooghe Proceedings of the First International Conference on Computational Logic , London, United Kingdom, July 2000. Lecture Notes in Artificial Intelligence, Springer Verlag, Pages 1255-1269 © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers/memory_reuse_analysis.ps.gz">Available here (93K)</a>. In previous work Bruynooghe, Janssens and Kågedal developed a live-structure analysis for Mercury which detects memory cells available for reuse. Seperate compilation of modules is an essential ingredient of a language such as Mercury which supports programming in the large. Hence, to be practical, a live-structure analysis also has to be module based. This paper develops a modular live-structure analysis and extends it with a modular reuse analysis. It also describes preliminary results obtained with a first prototype of the module based analysis. <li> <a name="tail_lopstr_lncs"> Making Mercury programs tail recursive </a> Peter Ross, David Overton and Zoltan Somogyi Proceedings of the Ninth International Workshop on Logic-based Program Synthesis and Transformation, Venice, Italy, September 1999. To appear in Lecture Notes in Computer Science, Springer Verlag, © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers/tail_lopstr_lncs.ps.gz">Available here (84K)</a>. We present two optimizations for making Mercury programs tail recursive. Both operate by taking computations that occur after a recursive call and moving them before the recursive call, modifying them as necessary. The first optimization moves calls to associative predicates; it is a pure source to source transformation. The second optimization moves construction unifications; it required extensions to the mode system (to record aliases) and to the parameter passing convention (to allow arguments to be returned in memory). The two optimizations are designed to work together, and can make a large class of programs tail recursive. The raw data on which the evaluation is based is available as a <a href = "papers/tail_data.tar.gz">5 Kb tar file</a>. <li> <a name="update"> State update transformation </a> Peter Ross and Zoltan Somogyi <a href="papers/update.ps.gz">Available here (57K)</a>. Recursive predicates frequently generate some state which is updated after the recursive call. We present a source to source transformation which can move the state update before the recursive call, thus helping to make the predicate tail recursive, and report on its implementation in the Mercury compiler. <li> <a name="purity"> Using impurity to create declarative interfaces in Mercury </a> Tyson Dowd, Peter Schachte, Fergus Henderson and Zoltan Somogyi <a href="papers/purity.ps.gz">Available here (52K)</a>. The logic/functional language Mercury allows the programmer to annotate predicates and functions to mark impure predicates, allowing impure code to be safely integrated into a declarative language. By using purity declarations with the foreign language interface, programmers can take advantage of many of the features of a high level programming language while writing imperative code to interface with existing imperative libraries. This paper outlines the purity system in Mercury and how it affects operational semantics, compares this purity system with other approaches to declaring impurity in a pure language, and gives an extended example of how impurity and foreign language interfaces can work together to simplify the chore of writing declarative interfaces to libraries. <li> <a name="liveness"> Towards memory reuse for Mercury </a> Nancy Mazur, Gerda Janssens and Maurice Bruynooghe Proceedings of the International Workshop on Implementation of Declarative Languages , Paris, France, October 1999 <a href="papers/liveness.ps.gz">Available here (61K)</a>. While Mercury allows destructive input/unique output modes which direct the compiler to reuse memory, use of these modes can be cumbersome for the programmer. In most situations, it would be nicer if the programmer didn't have to worry about the details of memory management. The paper briefly reports on some experiments with a prototype analyser which aims at detecting memory available for reuse. The prototype is based on the live-structure analysis developed by us for logic programs extended with declarations. Yet the major contribution of this paper consists of the development of the principles of a module based analysis which are essential for the analysis of large Mercury programs with code distributed over many modules. <li> <a name="bta"> Binding-time analysis for Mercury </a> Wim Vanhoof and Maurice Bruynooghe Proceedings of the Sixteenth International Conference on Logic Programming , Las Cruces, New Mexico, November 1999, pages 500-514 <a href="papers/bta.ps.gz">Available here (76K)</a>. In this paper, we describe a binding-time analysis (BTA) for a statically typed and strongly moded pure logic programming language, in casu Mercury. Binding-time analysis is the key concept in achieving off-line program specialisation: the analysis starts from a description of the program's input available for specialisation, and propagates this information throughout the program, deriving directives for when and how to perform specialisation. Exploiting the possibilities offered by Mercury's strong type and mode system, we present a completely automatic BTA dealing with partially static binding-times. <li> <a name="debugger_wlpe99"> The implementation technology of the Mercury debugger </a> Zoltan Somogyi and Fergus Henderson. Proceedings of the Tenth Workshop on Logic Programming Environments , Las Cruces, New Mexico, November 1999, pages 35-49. <a href="papers/debugger_wlpe99.ps.gz">Available here (66K)</a>. Every programming language needs a debugger. Mercury now has three debuggers: a simple procedural debugger similar to the tracing systems of Prolog implementations, a prototype declarative debugger, and a debugger based on the idea of automatic trace analysis. In this paper, we present the shared infrastructure that underlies the three debuggers, and describe the implementation of the procedural debugger. We give our reasons for each of our main design decisions, and show how several of these decisions are rooted in our experience with the debugging of large programs working with large data structures. <li> <a name="tail_lopstr"> Making Mercury programs tail recursive (extended abstract) </a> Peter Ross, David Overton and Zoltan Somogyi. Pre-Proceedings of the Ninth International Workshop on Logic-based Program Synthesis and Transformation , Venice, Italy, September 1999, pages 107-118. <a href="papers/tail_lopstr.ps.gz">Available here (62K)</a>. This paper has been superceded by the LNCS version. <li> <a name="rtti_ppdp"> Run time type information in Mercury </a> Tyson Dowd, Zoltan Somogyi, Fergus Henderson, Thomas Conway and David Jeffery. Proceedings of the International Conference on the Principles and Practice of Declarative Programming , Paris, France, September/October 1999, Lecture Notes in Computer Science 1702, Springer Verlag, Pages 224-243, © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers/rtti_ppdp.ps.gz">Available here (75K)</a>. The logic/functional language Mercury uses a strong, mostly static type system based on polymorphic many-sorted logic. For efficiency, the Mercury compiler uses type specific representations of terms, and implements polymorphic operations such as unifications via generic code invoked with descriptions of the actual types of the operands. These descriptions, which consist of automatically generated data and code, are the main components of the Mercury runtime type information (RTTI) system. We have used this system to implement several extensions of the Mercury system, including an escape mechanism from static type checking, generic input and output facilities, a debugger, and automatic memoization, and we are in the process of using it for an accurate, native garbage collector. We give detailed information on the implementation and uses of the Mercury RTTI system as well as measurements of the space costs of the system. The raw data on which the evaluation is based is available as a <a href = "papers/rtti_data.tar.gz">70 Kb tar file</a> <li> <a name="stayl_hons"> Optimization of Mercury programs </a> Simon Taylor. Honours report. Department of Computer Science, University of Melbourne, November 1998. <a href = "papers/stayl_hons.ps.gz"> Available here (120K). </a> This paper describes the implementation of several of the high-level optimization passes of the Mercury compiler, including deforestation, type specialization, constraint propagation and structure reuse. <li> <a name="mcorba_padl99"> MCORBA: A CORBA Binding for Mercury </a> David Jeffery, Tyson Dowd and Zoltan Somogyi. In Proceedings of the First International Workshop on Practical Aspects of Declarative Languages , San Antonio, Texas, January 1999, Lecture Notes in Computer Science 1551, Springer Verlag, Pages 211-227, © <a href="http://www.springer.de/comp/lncs/index.html">Springer-Verlag</a>. <a href="papers/mcorba_padl99.ps.gz">Available here (65K)</a>. MCORBA is a binding to the CORBA distributed object framework for the purely declarative logic/functional language Mercury. The binding preserves the referential transparency of the language, and has several advantages over similar bindings for other strongly typed declarative languages. As far as we know, it is the first such binding to be bidirectional; it allows a Mercury program both to operate upon CORBA components and to provide services to other CORBA components. Whereas the Haskell binding for COM maps COM interfaces onto Haskell types, MCORBA maps CORBA interfaces onto Mercury type classes. Our approach simplifies the mapping, makes the implementation of CORBA's interface inheritance straightforward, and makes it trivial for programmers to provide several different implementations of the same interface. It uses existential types to model the operation of asking CORBA for an object that satisfies a given interface but whose representation is unknown. <li> <a name="mu_98_13"> Type classes in Mercury </a> David Jeffery, Fergus Henderson and Zoltan Somogyi. Technical Report 98/13, Department of Computer Science, University of Melbourne, Melbourne, Australia, September 1998, 22 pages. <a href = "papers/mu_98_13.ps.gz"> Available here (82K). </a> In this paper, we explain how we have extended Mercury's type system to include support for type classes. We give a formal semantics for this extension to our type system, adapting the typing rules used in functional languages to the differing demands of logic programming languages. We show that type classes integrate very nicely with Mercury's mode, uniqueness and determinism systems, and describe how our implementation works. <li> <a name="sas97"> Termination analysis for Mercury </a> Chris Speirs, Zoltan Somogyi and Harald Sondergaard. Proceedings of the Fourth Static Analysis Symposium , Paris, France, September 1997, pages 157-171. <a href = "papers/sas97.ps.gz">available here (75K)</a>. A longer version of the paper appeared as Technical Report 97/9, Department of Computer Science, University of Melbourne, Melbourne, Australia, July 1997, 25 pages. it is <a href = "papers/mu_97_09.ps.gz">available here (99K)</a>. This paper presents the algorithms of the Mercury termination analyser, discusses how real-world aspects of the language such as modules, higher-order features, foreign language code, and declarative input/output can be handled, and evaluates the performance of the analyser both on a set of standard test programs and on the Mercury compiler itself. The raw data on which the evaluation is based is available as a <a href = "papers/termination_data.tar.gz">5.2 Mb tar file</a>. <li> <a name="jicslpw"> Status of the Mercury system </a> Zoltan Somogyi, Fergus Henderson, Thomas Conway, Andrew Bromage, Tyson Dowd, David Jeffery, Peter Ross, Peter Schachte and Simon Taylor. Proceedings of the JICSLP '96 Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Bonn, Germany, September 1996, pages 207-218. <a href = "papers/jicslpw.ps.gz">Available here (46K)</a>. <li> <a name="jlp"> The execution algorithm of Mercury: an efficient purely declarative logic programming language </a> Zoltan Somogyi, Fergus Henderson and Thomas Conway. Journal of Logic Programming, volume 29, number 1-3, October-December 1996, pages 17-64. <a href = "papers/jlp.ps.gz">Available here (138K)</a>. Elsevier owns the copyright of this paper; it is made available here by their permission. This paper contains a brief overview of the Mercury language, and a reasonably detailed overview of the implementation technology used in the Mercury compiler. It describes the abstract machine that the compiler generates code for. (Our other papers listed below go into more detail on exactly how the code is generated, and on how the abstract machine instructions are implemented as C or GNU C code.) The raw data on which the evaluation is based is available on our <a href = "./benchmarks.html">benchmarking page</a>. <li> <a name="acsc96"> Determinism analysis in the Mercury compiler </a> Fergus Henderson, Zoltan Somogyi and Thomas Conway. Proceedings of the Australian Computer Science Conference, Melbourne, Australia, January 1996, pages 337-346. <a href = "papers/acsc96.ps.gz">Available here (78K)</a>. A longer version of the paper is <a href = "papers/detism.ps.gz">available here (76K)</a>. This paper discusses Mercury's determinism system in detail, including the algorithms for switch detection, deep indexing, determinism inference, and determinism checking. <li> <a name="code_gen_mit"> Code generation for Mercury </a> Thomas Conway, Fergus Henderson, and Zoltan Somogyi. Proceedings of the 1995 International Symposium on Logic Programming, Portland, Oregon, December 1995, pages 242-256. <a href = "papers/code_gen_mit.ps.gz">Available here (68K)</a>. This paper describes the structure of the Mercury compiler, its calling conventions, and the algorithms it uses in generating code. These algorithms include lazy code generation and a novel way of handling nested disjunctions. <li> <a name="mercury_to_c"> Compiling logic programs to C using GNU C as a portable assembler </a> Fergus Henderson, Zoltan Somogyi and Thomas Conway. Proceedings of the ILPS '95 Postconference Workshop on Sequential Implementation Technologies for Logic Programming Languages. Portland, Oregon, December 1995. <a href = "papers/mercury_to_c.ps.gz">Available here (65K)</a>. This paper discusses the merits of using C, and in particular GNU C, as an intermediate target language for the compilation of logic programs, and describes the approach we have taken in the implementation of Mercury. <li> <a name="acsc95"> Mercury: an efficient purely declarative logic programming language </a> Zoltan Somogyi, Fergus Henderson and Thomas Conway. Proceedings of the Australian Computer Science Conference, Glenelg, Australia, February 1995, pages 499-512. <a href = "papers/acsc95.ps.gz">Available here (85K)</a>. An overview paper. <li> <a name="ilps94w"> The implementation of Mercury: an efficient purely declarative logic programming language </a> Zoltan Somogyi, Fergus Henderson and Thomas Conway. Proceedings of the ILPS '94 Postconference Workshop on Implementation Techniques for Logic Programming Languages, Syracuse, New York, November 1994. <a href = "papers/ilps94w.ps.gz">Available here (96K)</a>. The first paper on Mercury. It is superseded by the paper in the Journal of Logic Programming. <li> <a name="conway_hons"> Code generation for Mercury </a> Thomas Conway. Honours report. Department of Computer Science, University of Melbourne, November 1994. <a href = "papers/conway_hons.ps.gz">Available here (188K)</a>. This is the first paper on the code generator. Warning: several aspects of the code generator have changed since this paper was written. Some of these are documented in the version in the ILPS 95 proceedings. </ul> <hr> <h2><a name="related">Related Papers</a></h2> <a name="mu_97_23"> This paper gives an introduction to automatic termination analysis. It surveys termination analysis of logic programs and provides an overview of the important concepts involved in automatic termination analysis. </a> <ul> <li> Termination analysis for logic programs Chris Speirs. Technical Report 97/23, Department of Computer Science, University of Melbourne, October 1997. <a href = "papers/mu_97_23.ps.gz"> Available here (67K). </a> </ul> <a name="vision"> This paper outlines the features that we believe to be important in a modern logic programming language: </a> <ul> <li> Logic programming for the real world Zoltan Somogyi, Fergus Henderson, Thomas Conway and Richard O'Keefe. Proceedings of the ILPS '95 Postconference Workshop on Visions for the Future of Logic Programming, Portland, Oregon, December 1995. <a href = "papers/vision.ps.gz"> Available here (59K). </a> </ul> <a name="iclp87"> The mode system and the uniqueness system of Mercury are based on the following papers: </a> <ul> <li> A system of precise modes for logic programs Zoltan Somogyi. Proceedings of the Fourth International Conference on Logic Programming, Melbourne, Australia, May 1987, pages 769-787. <a href = "http://www.cs.mu.oz.au/~zs/papers/iclp87.ps.gz"> Available here (40K). </a> <li> <a name="fjh_hons_thesis"> Strong modes can change the world! </a> Fergus Henderson. Honours Report. Department of Computer Science, University of Melbourne, November 1992. <a href = "http://www.cs.mu.oz.au/~fjh/papers/hons_thesis.ps.gz"> Available here (114K). </a> </ul> <a name="mu_96_45"> The following paper describes the method used to express database transactions and updates that is used in the Mercury ODBC database interface. </a>  <ul> <li> Database transactions in a purely declarative logic programming language David B. Kemp, Thomas Conway, Evan Harris, Fergus Henderson, Kotagiri Ramamohanarao and Zoltan Somogyi. Technical Report 96/45 Department of Computer Science, University of Melbourne, December 1996. <a href = "http://www.cs.mu.OZ.AU/publications/tr_db/mu_96_45.ps.gz"> Available here (58K) </a> <a href = "http://www.cs.mu.OZ.AU/publications/tr_db/mu_96_45_cover.ps.gz"> with cover page. </a> </ul>  <hr> <h2><a name="presentations">Presentations on Mercury<a></h2> <ul> <li> <a name="sas_talk"> Termination analysis for Mercury </a> Chris Speirs, Zoltan Somogyi and Harald Sondergaard. Talk presented at the Fourth Static Analysis Symposium. Paris, France, September 1997. <a href = "papers/sas_talk.ps.gz"> Available here (6K). </a> <li> <a name="unif"> Unification in Mercury </a> Zoltan Somogyi. Invited talk presented at the Eighth Benelux Workshop on Logic Programming. Louvain-la-Neuve, Belgium, September 1996. <a href = "papers/unif.ps.gz"> Available here (12K). </a> <li> <a name="jicslp_talk"> The design and implementation of Mercury </a> Zoltan Somogyi and Fergus Henderson. Tutorial presented at the Joint International Conference and Symposium on Logic Programming. Bonn, Germany, September 1996. <a href = "papers/jicslp_talk.ps.gz"> Available here (18K). </a> <li> <a name="jicslpw_talk"> Status of the Mercury system </a> Zoltan Somogyi, Fergus Henderson, Thomas Conway, Andrew Bromage, Tyson Dowd, David Jeffery, Peter Ross, Peter Schachte and Simon Taylor. Presented at the JICSLP '96 Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Bonn, Germany, September 1996. <a href = "papers/jicslpw_talk.ps.gz"> Available here (5K). </a> <li> <a name="acsc95_slides"> Mercury: an efficient purely declarative logic programming language </a> Zoltan Somogyi, Fergus Henderson and Thomas Conway. Presented at the Eighteenth Australasian Computer Science Conference, Adelaide, South Australia, February 1995. <a href = "papers/acsc95_slides.ps.gz"> Available here (33K). </a> <li> <a name="257_1999"> Lecture notes for the expanded Mercury segment of the subject 433-257 Frontiers of Computer Science, given in 1999 (whereas the segment in 1997 had four lectures, in 1999 it had six) </a> Zoltan Somogyi. <a href = "papers/257_1999.ps.gz"> Available here (40K). </a> <li> <a name="257"> Lecture notes for the Mercury segment of the subject 433-257 Frontiers of Computer Science, given in 1997 </a> Zoltan Somogyi. <a href = "papers/257.ps.gz"> Available here (21K). </a> <li> <a name="247"> Lecture notes for the Mercury segment of the subject 433-247 Frontiers of Computer Science, given in 1995 </a> Zoltan Somogyi. <a href = "papers/247.ps.gz"> Available here (21K). </a> <li> <a name="dgj-talk"> Type classes for logic programming languages, given in March 1998 </a> David Jeffery. <a href = "papers/dgj-talk.ps.gz"> Available here (30K). </a> <li> <a name="rtti_talk_98"> Runtime type information in Mercury, given in March 1998 </a> Tyson Dowd. <a href = "papers/rtti_talk_98.ps.gz"> Available here (48K). </a> </ul> <hr> All these papers and presentations are for A4 paper. Unfortunately, we cannot generate US paper size versions. </TD> </TR> </TABLE> </BODY> </HTML>