Quite an interesting challenge it seems. If you are interested in the theory behind this type of function rewriting, it is an optimization technique to rewrite a recursive function that has two recursive exit points into a function that has one recursive exit point to allow it to be tail-call optimized. With this technique, any function can be rewritten to become tail-call optimized.

In this O'Caml paper, chapter 4, there's quite a readable version of the function and an explanation of how it works:

http://www.cs.rice.edu/~taha/publications/journal/gttse07.pdf

Thanks for looking into it!

Abel

On 7-2-2013 0:08, Michael Kay wrote:
On further investigation the tail call seems to be a red herring. In the inner inline function $second, the closure contains two variables $countfun and $x, and the slot numbers for these variable references have not been allocated (properly or at all) so values are being picked up from the wrong place. To be continued...

Michael Kay
Saxonica

On 06/02/2013 22:32, Michael Kay wrote:

I have added this to the XSLT 3.0 test suite as test case higher-order-functions-068, and I confirm it is still failing with the current development build.

The hypothesis I am exploring is that it is an interaction between function closures and tail recursion; my suspicion is that when the stackframe is reused/overwritten for the purpose of tail-recursion, the values required for the function closure are being corrupted. It's all pretty complex!

Michael Kay
Saxonica

On 06/02/2013 03:14, Abel Braaksma wrote:
When I define the following continuation version of the Fibonacci sequence in XSLT 3:

    <xsl:function name="f:fib">
        <xsl:param name="n" as="xs:integer" />
        <xsl:param name="countfun" as="function(*)" />
       
        <xsl:sequence select="
            if ($n = 1 or $n = 2)
            then $countfun(1)
            else let $first :=
                     function($x as xs:integer) as function(*)
                     {
                        let $second := function($y as xs:integer) as function(*)
                        {
                            $countfun($x + $y)
                        }
                        return f:fib($n - 2, $second)
                     }
                 return f:fib($n - 1, $first)" />
    </xsl:function>

and I call it as follows:

<xsl:value-of select="f:fib(10, function($a as xs:integer){$a})" />

the expected result is 55. However, I receive the following error:

Engine name: Saxon-EE 9.4.0.4
Severity: fatal
Description: Required item type of second argument of anonymous function is function(); supplied value has item type xs:integer
Start location: 36:0
URL: http://www.w3.org/TR/xslt20/#err-XTTE0790

The function is inspired by this snippet http://fssnip.net/eU, though other functional languages have similar examples. The idea behind the excercise is to eliminate the double recursive exit point of the function by creating a continuation function.
However, either the error is confusing (I don't see any anonymous function call with a function argument) or something else is happening.

I also tried the fully typed version, and an untyped version. Here's the fully typed variant:

<xsl:function name="f:fib" as="xs:integer">
    <xsl:param name="n" as="xs:integer" />
    <xsl:param name="countfun" as="function(xs:integer) as xs:integer" />
   
    <xsl:sequence select="
        if ($n = 1 or $n = 2)
        then $countfun(1)
        else let $first :=
                 function($x as xs:integer) as xs:integer
                 {
                    let $second := function($y as xs:integer) as xs:integer
                    {
                        $countfun($x + $y)
                    }
                    return f:fib($n - 2, $second)
                 }
             return f:fib($n - 1, $first)" />
</xsl:function>


Any idea what I'm missing here, or is this perhaps an error with Saxon?

Thanks,
Abel




------------------------------------------------------------------------------
Free Next-Gen Firewall Hardware Offer
Buy your Sophos next-gen firewall before the end March 2013 
and get the hardware for free! Learn more.
http://p.sf.net/sfu/sophos-d2d-feb


_______________________________________________
saxon-help mailing list archived at http://saxon.markmail.org/
saxon-help@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/saxon-help 



------------------------------------------------------------------------------
Free Next-Gen Firewall Hardware Offer
Buy your Sophos next-gen firewall before the end March 2013 
and get the hardware for free! Learn more.
http://p.sf.net/sfu/sophos-d2d-feb


_______________________________________________
saxon-help mailing list archived at http://saxon.markmail.org/
saxon-help@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/saxon-help 



------------------------------------------------------------------------------
Free Next-Gen Firewall Hardware Offer
Buy your Sophos next-gen firewall before the end March 2013 
and get the hardware for free! Learn more.
http://p.sf.net/sfu/sophos-d2d-feb


_______________________________________________
saxon-help mailing list archived at http://saxon.markmail.org/
saxon-help@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/saxon-help