new function - fn:tail-recurse a function to allow users to hand roll their recursion and guarentee tail recursion.

[MarkNicholls]

Motivation:

• I as a user of XPath want to write a recursive function.
• I write the function,
• I run it,
• it causes a stack overflow

So,

• I don't believe tail recursion detection is part of the spec thus an implementation may not implement it
• tail recursion detection I suspect is hard, and I suspect there are cases that are tail recursion that an implementation doesnt detect

Tail recursion is not an uncommon problem in other languages, in imperative languages I would simply implement the algorithm using a 'while' loop, creating the 'body' of the while loop is my problem, but once I've done it, I KNOW that in all implementations my algorithm will be executed tail recursively (imperative code is FULL of loops, stack overloads are not an issue).

An example

I want to implement a power function in C# I know how to write it recursively, but C# doesn't support tail recursion, so I have to turn it into a loop. I could do this in an ad hoc way using a while loop, but I could also write the loop once, and then ask the developer to pass in a function that defines the body of the loop

in C# that function could have the type (i.e. it takes a state and either returns a new state or null, a null would indicte the end of the 'loop')

State? recurse(State state)

and the library function that executes it have the signature:

State TailRecurse<State>(Func<State,State?> f, State state)

a complete example of how this would appear in C# would be:
(note C# has a nuance w.r.t. the higher kinded type '?' and so the signature of TailRecurse below is slightly weaker than the one above).

var toPower3 = TailRecursion.Power2(3);
var result = TailRecursion.TailRecurse(toPower3, (0, 2));

Console.WriteLine(result.Value.Item2);

class TailRecursion
{
    // actually we want, but because of a quirk in C# around the '?' higher kinded type we have to write the signature symetrically (I think).
    //public static State TailRecurse<State>(Func<State, State?> f, State state)
    public static State TailRecurse<State>(Func<State?,State?> f, State state)
    {
        while (true)
        {
            var result = f(state);
            if (result == null)
            {
                return state;
            }
            state = result;
        }
    }

    public static Func<(int,int)?,(int,int)?> Power2(int n)
    {
        return powerAndX =>
        {
            if (powerAndX.Value.Item1 > n)
            {
                return null;
            }
            return (powerAndX.Value.Item1 + 1, powerAndX.Value.Item2 * powerAndX.Value.Item2);
        };
    }
}

in XSLT I could write this function

<xsl:function name="kooks:pow" as="xs:integer">
    <xsl:param name="x" as ="xs:integer"/>
    <xsl:param name="n" as ="xs:integer"/>
    <xsl:choose>
        <xsl:when test="$n = 0">
            <xsl:sequence select="$x"/>
        </xsl:when>
        <xsl:otherwise>
            <xsl:sequence select="$x * kooks:pow($x,$n - 1)"/>
        </xsl:otherwise>
    </xsl:choose>
</xsl:function>

I know its tail recursive, but my environment may not for whatever reason detect it (I would hope it does, but I could be doing something much more complex, that IS tail recursive but the environment simply doesn't see it).

I can't write a loop in XPath etc, it doesnt exist, so I can't escape like I do in C# or scala, in F# (which also doesnt support while loops), I would have to write a function that I was sure F# detected as tail recursive and then path the 'body' of the while loop as a function.

in XSLT this could look like this (basically the same as the C# example)

here the C# signature
State TailRecurse<State>(Func<State,State?> f, State state)
has been translated by using item()* for state an array(*) for State?, where an empty array corresponds to null/none, and an array with 1 element corresponds to 'some' State.

This function IS tail recursive in a very simple way that I think all implementations would detect as such, and thus (if it does) I can pass any function I like and be confident it is processed tail recursively - I can of course do this now, I use saxon, (even though I'm wrestling with it to detect tail recursion for some bizarre reason which is probably my fault) I think it would ideally be a library function and (using a loop) allow non tail recursive environments to support tail recursion, or allow me to simply do the detection myself.

    <xsl:function name="kooks:tailRecurse">
        <xsl:param name="unfolder" as="function(item()*) as array(*)"/>
        <xsl:param name="state" as="item()*"/>
        <xsl:variable name="newState" select="$unfolder($state)"/>
        <xsl:choose>
            <!-- loop returns null/none - end of recurstion -->
            <xsl:when test="array:size($newState) = 0">
                <xsl:sequence select="$state"/>
            </xsl:when>
            <!-- else, unpack the state and loop again -->
            <xsl:otherwise>
                <xsl:sequence select="kooks:tailRecurse($unfolder,array:get($newState,1))"/>
            </xsl:otherwise>
        </xsl:choose>        
    </xsl:function>

For environments that don't do tail recursion detection, they can simple implement the analogous code to the C# example in their implementation i.e. map it to a while loop.

In both cases I think this is hopefully trivial for the implementor of the language.

Here's a complete example, with tailRecurse defined as above, that would guarentee (in an environment that detected it correctly) that any passed function is processed.

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:array="http://www.w3.org/2005/xpath-functions/array"
    xmlns:map="http://www.w3.org/2005/xpath-functions/map"
    exclude-result-prefixes="xs"
    version="3.0"
    xmlns:kooks="http://www.kookerella.com">
    
    <!-- (state -> Maybe state) -> state -> state --> 
    <xsl:function name="kooks:tailRecurse">
        <xsl:param name="unfolder" as="function(item()*) as array(*)"/>
        <xsl:param name="state" as="item()*"/>
        <xsl:variable name="newState" select="$unfolder($state)"/>
        <xsl:choose>
            <!-- loop returns null/none - end of recurstion -->
            <xsl:when test="array:size($newState) = 0">
                <xsl:sequence select="$state"/>
            </xsl:when>
            <!-- else, unpack the state and loop again -->
            <xsl:otherwise>
                <xsl:sequence select="kooks:tailRecurse($unfolder,array:get($newState,1))"/>
            </xsl:otherwise>
        </xsl:choose>        
    </xsl:function>
    
    <xsl:function name="kooks:powUnfolder" as="function(item()*) as array(*)">
        <xsl:param name="x" as="xs:integer"/>
        <xsl:param name="n" as="xs:integer"/>
        <xsl:sequence select="function($state) {
                if (map:get($state,'power') >= $n)
                (: we're done so return null/none :)
                then array {}
                else
                (: else calculate the next power and loop again :)
                    let $newState := map { 
                        'power': map:get($state,'power') + 1,
                        'result': map:get($state,'result') * $x
                        }
                    return array { $newState }
            }"/>
    </xsl:function>
    
    <xsl:template match="/">
        <twoToThePower4>
            <xsl:variable name="seed" select="map { 'power':0,'result':1 }"/>
            <xsl:sequence select="map:get(kooks:tailRecurse(kooks:powUnfolder(2,4),$seed),'result')"/>
        </twoToThePower4>
    </xsl:template>    
</xsl:stylesheet>

I suspect these lines are not obvious.

            <xsl:variable name="seed" select="map { 'power':0,'result':1 }"/>
            <xsl:sequence select="map:get(kooks:tailRecurse(kooks:powUnfolder(2,4),$seed),'result')"/>

The first line says anything to the power 0 is 1, the second line says, I want the 'result of 2 to the power 4.

Note its VERY similar to xsl:iterate, but that requires an sequence to drive it, this is just general recursion.

[michaelhkay]

I'm sorry, I don't understand what you are asking for. Apart from the title, all I see is a lot of code, and I can't reverse engineer your requirement from the code.

Are you perhaps looking for something like the new do-until() and while-do() functions?

[ChristianGruen]

Same for me. Would it be possible to add a minimized XPath example that demonstrates what would happen with and without using the proposed function?

[MarkNicholls]

ah ok, hmmm let me rejig it all a bit then,

[MarkNicholls]

its now rejigged and hopefully a bit more understandable.

[michaelhkay]

If I've understood it correctly the end result is exactly what can be achieved with fn:do-until() (or fn:while-do()).

Something like

fn:do-until($seed, kooks:power-unfolder(2, 4), array:empty#1)

Bringing in tail recursion seems just to complicate the discussion. There's no need for recursion here, so no need to detect tail calls.

[ChristianGruen]

its now rejigged and hopefully a bit more understandable.

I’ll keep watching, my XSLT knowledge is too limited to digest all of this in a few minutes (unless you can express it in XQuery?).

I can't write a loop in XPath etc, it doesnt exist

For loops, you can use the for and return clauses of XPath:

for $n in 1 to 10
return $n * $n

For recursive functions, you can declare function items and pass a self reference to the invoked function…

let $func := function($f) { $f($f) }
return $func($func)

…but the XQuery approach is certainly better readable:

declare function local:f() {
  local:f()
};
local:f()

[MarkNicholls]

If I've understood it correctly the end result is exactly what can be achieved with fn:do-until() (or fn:while-do()).

Something like

fn:do-until($seed, kooks:power-unfolder(2, 4), array:empty#1)

Bringing in tail recursion seems just to complicate the discussion. There's no need for recursion here, so no need to detect tail calls.

I assume do-until() or while-do() actually don't currently exist?

in which case yes, loops are tail recursion, there is no difference (I can map code 1:1 and back), you've just changed the label, those labels are probably better.

(from a functional perspective though the issue is the inability to define a tail recursion, 'loops' don't exist, an imperative programmer would never ask for this because while loops exists in the foundation)

Just to be clear though the motivation is writing a recursive function and not being able to explicitly define it in tail recursive terms, if people want to additionally see it as an imperative construct for 'looping', I have no problem with that, and it solves the problem BUT it isnt my motivation, one could easily tell devolopers to write such a function, and then they find it isnt tail recursive in their runtime and the problem isnt solved.

[MarkNicholls]

its now rejigged and hopefully a bit more understandable.

I’ll keep watching, my XSLT knowledge is too limited to digest all of this in a few minutes (unless you can express it in XQuery?).

I can try tomorrow, my XQuery is limited too.

For loops, you can use the for and return clauses of XPath:

for $n in 1 to 10
return $n * $n

here you know in advance the termination point, I'm talking about scenarios where you don't know, e.g. a function that given a prime returns the next prime, you need while condition

For recursive functions, you can declare function items and pass a self reference to the invoked function…

let $func := function($f) { $f($f) }
return $func($func)

yes but this is not inherently tail recursive

…but the XQuery approach is certainly better readable:

declare function local:f() {
  local:f()
};
local:f()

absolutely, this is recursive, but in general unless the runtime detects tail recursion, this sort of thing can blow the stack.

fn:do-while

as suggested by MK is a better name, though implies a more imperative style signature

I'll try to write it in XQuery tomorrow

[ChristianGruen]

absolutely, this is recursive, but in general unless the runtime detects tail recursion, this sort of thing can blow the stack.

Even better if you are already aware of the syntax. I just mentioned the examples to help you generate an XPath/XQuery example for fn:tail-recurse.

fn:do-while
as suggested by MK is a better name, though implies a more imperative style signature

Visit the following links to learn more about fn:while-do and fn:do-until and their history:

• Issues: [FO] fn:while (before: fn:until) #80, fn:iterate-while → fn:while-do, fn:do-until #946
• Definition: https://qt4cg.org/specifications/xpath-functions-40/Overview.html#func-while-do

[MarkNicholls]

ah ok, I did check the existing specs, and I thought id checked the 4.0 spec, though maybe I don't know where they all are.

ignore me, I think fn:do-until would do it.

[ChristianGruen]

Feel free to close the issue if you think it is resolved.