[m-dev.] for review: add LNCS paper to web site

[Peter Ross]

Hi,


===================================================================


Estimated hours taken: 0.5

Add the LNCS version of the "Making Mercury Programs Tail Recursive" to
the web site.

information/include/papers.inc:
information/papers/tail_data.tar.gz:
information/papers/tail_lopstr_lncs.ps.gz:
news/newsdb.inc:

Index: information/include/papers.inc
===================================================================
RCS file: /home/staff/zs/imp/w3/information/include/papers.inc,v
retrieving revision 1.17
diff -u -r1.17 papers.inc
--- information/include/papers.inc	2000/02/22 02:46:23	1.17
+++ information/include/papers.inc	2000/03/16 03:22:06
@@ -16,6 +16,40 @@
 <ul>
 <li>
 <strong>
+Making Mercury Programs Tail Recursive
+</strong>
+<br>
+Peter Ross, David Overton and Zoltan Somogyi
+<br>
+<em>
+Proceedings of the Ninth International Workshop on Logic-based Program
+Synthesis and Transformation
+</em>,
+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>.
+<p>
+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.
+<p>
+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>
+<p>
+
+<li>
+<strong>
 Towards memory reuse for Mercury
 </strong>
 <br>
@@ -104,56 +138,14 @@
 Peter Ross, David Overton and Zoltan Somogyi.
 <br>
 <em>
-Proceedings of the Ninth International Workshop on Logic-based Program
+Pre-Proceedings of the Ninth International Workshop on Logic-based Program
 Synthesis and Transformation
 </em>,
 Venice, Italy, September 1999, pages 107-118.
 <a href="papers/tail_lopstr.ps.gz">Available here (62K)</a>.
 <p>
 
-Recursive calls are often very close to being the last action in a clause.
-Frequently, however, the recursive call computes a value
-which must be put into a memory cell or used in a simple computation.
-Therefore the generated code will consume stack space for each iteration,
-and will need to execute
-stack frame setup and teardown code in every iteration.
-This paper presents two optimisations that in many common cases
-can transform such code into a tail recursive form
-by moving code from after the recursive call to before the recursive call.
-These optimisations have been implemented in the Melbourne Mercury compiler.
-<p>
-The first optimisation is a pure source to source transformation.
-It looks for recursive calls followed by associative computations
-which depend on the outputs of the recursive call.
-The optimisation then creates a specialised version of the predicate
-in which the associative computation is done before the recursive call.
-This specialised predicate will have
-extra arguments that act as accumulators:
-they hold the cumulative results of the associative computations so far.
-<p>
-The second optimisation looks for
-recursive calls followed by construction unifications
-that put some of the results of that call into memory cells,
-and moves those construction unifications before the call.
-This required extending the Mercury mode system
-to allow a restricted form of partially instantiated data structures
-and to record aliases,
-since in the transformed program the cell is not ground when it is created,
-but will become ground when the recursive call returns.
-To allow this to happen, we also had to extend
-the parameter passing conventions of the Mercury abstract machine
-to allow predicates to return selected output arguments in memory,
-not in registers.
-<p>
-Some predicates contain both
-associative computations and construction unifications
-after the recursive call.
-To allow us to make such predicates tail recursive,
-the accumulator introduction optimisation will perform its transformation
-even when the recursive call is followed by construction unifications
-as well as associative computations,
-knowing that the other optimisation
-will move the construction unifications before the call.
+This paper has been superceded by the LNCS version of this paper.
 <p>
 
 <li>
Index: information/papers/tail_data.tar.gz
===================================================================
RCS file: tail_data.tar.gz
diff -N tail_data.tar.gz
Binary files /dev/null and tail_data.tar.gz differ
Index: information/papers/tail_lopstr_lncs.ps.gz
===================================================================
RCS file: tail_lopstr_lncs.ps.gz
diff -N tail_lopstr_lncs.ps.gz
Binary files /dev/null and tail_lopstr_lncs.ps.gz differ
Index: news/newsdb.inc
===================================================================
RCS file: /home/staff/zs/imp/w3/news/newsdb.inc,v
retrieving revision 1.44
diff -u -r1.44 newsdb.inc
--- news/newsdb.inc	2000/02/22 01:39:45	1.44
+++ news/newsdb.inc	2000/03/20 04:42:54
@@ -21,6 +21,14 @@
 
 $newsdb = array(
 
+"21 Mar 2000" => array("New paper",
+
+"A new paper on Mercury is now available from our
+<A HREF=\"information/papers.html\">papers page</A>.
+The paper describes two optimizations, implemented in the Mercury
+compiler, which make predicates tail recursive."
+),
+
 "21 Feb 2000" => array("New papers",
 
 "Two new papers on Mercury are now available from our

----
Peter Ross
PhD Student University of Melbourne
http://www.cs.mu.oz.au/~petdr/
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------