tail-end recursion

Subject: tail-end recursion
From: "Nick-Lawson.org" <nick@xxxxxxxxxxxxxxx>
Date: Thu, 12 Oct 2000 06:47:48 +0100
Hi,

My first reaction on seeing XSLT was "looks like Prolog"!

imho optimizing tail-end recursion is _very_ significant,
given that variables are "final" and there is no "return value"
from templates.

Mike Kay's example (earlier in this thread) is typical: suppose you want to
sum values
extracted from siblings. e.g. from a (long) list of rows in a table.
Tail-end recursion is the technique to use?

Anyone know which implementations do this optimization ?

Nick Lawson

Kennedy, Chris wrote:

Seems to me the points you are making apply more to
prolog than lisp.

Joseph Kesselman wwrote:

> The project's stylesheet makes heavy use of a tail recursive template.

I presume you  mean fully tail-recursive -- it's explicitly using
call-template to reinvoke itself, and doing no work thereafter. As you
said, your Lisp pseudocode example is cheating a bit by explicitly calling
(output) on the result of the recursion, so it isn't really tail-recursion;
to make it qualify, you'd need to have the body of your pseudocode generate
the output and have the recursion _only_ recurse.

I haven't thought about XSLT in these terms. The concept seems plausable;
the trick is structuring the code to recognize and take advantage of it
without incurring significant overhead in other cases. Might be possible to
do that in a static optimizing pass before running the stylesheet. Hm.

How common is tail recursion in XSLT? It's heavily used in Lisp, but Lisp
also tends to recurse much more deeply; I have the impression that in most
XSLT stylesheets recursion is on the order of the depth of the source
document... and documents (so far) have tended to grow in breadth more
rapidly than depth.


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


Current Thread