Thank you Dr. Kay, having this set of rules is really useful.
What about adding this to the relevant documentation, and, --> Dave Pawson
<--, to the XSLT FAQ?
Firstly, it's true that the spec says nothing about how functions are
implemented. This is a tricky area and we hit it a lot with streaming: how
do you define > language behaviour that is only observable in terms of
resource usage, not in terms of functional results? The general rule is
that you shouldn't mandate > anything unless you know how to write a test
for it.
So, the creators of FP languages where "tail-recursive" is defined, were
wrong in doing this, were they?
* For templates, tail-call optimization applies to mutual recursion, but
for functions, it applies only to self-recursion.
Does this mean that if a function's code ends with a call to another
function, this will not be tail-call-optimized? Even though the result of
the last-called function is immediately returned?
* Type checking and conversion applied to the result of the recursive
call can mean it isn't treated as tail recursive. This depends on whether
static
analysis is able to determine that type checking at run-time isn't
needed.
This one will not be easy for a human programmer to predict. And writing
self-recursive code just to see if this would be optimized seems
prohibitively expensive in the context of this statement.
Cheers,
Dimitre
On Wed, May 6, 2020 at 2:37 PM Michael Kay mike(_at_)saxonica(_dot_)com <
xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:
Saxon does this for templates, but I believe, not for all types of
functions. In the past I raised this problem and Dr. Michael Kay said that
at the time the XSLT WG didn't mandate recognizing and optimizing
tail-recursion, because they didn't have a definition for "tail-recursion".
Separate questions here.
Firstly, it's true that the spec says nothing about how functions are
implemented. This is a tricky area and we hit it a lot with streaming: how
do you define language behaviour that is only observable in terms of
resource usage, not in terms of functional results? The general rule is
that you shouldn't mandate anything unless you know how to write a test for
it.
Secondly, the question of exactly when templates and functions are
tail-recursive in Saxon. The main differences are:
* For templates, tail-call optimization applies to mutual recursion, but
for functions, it applies only to self-recursion.
* For templates, it is permissible to sequence-concatenate the result of
the recursive call with other items returned by the template. For
functions, any operation performed on the result of the recursive call,
including sequence concatenation, means that the call is not regarded as a
tail call.
* For functions, byte code generation can handle tail call optimization;
for templates, it can't.
* Type checking and conversion applied to the result of the recursive call
can mean it isn't treated as tail recursive. This depends on whether static
analysis is able to determine that type checking at run-time isn't needed.
Michael Kay
Saxonica
XSL-List info and archive <http://www.mulberrytech.com/xsl/xsl-list>
EasyUnsubscribe <http://lists.mulberrytech.com/unsub/xsl-list/782854> (by
email <>)
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--