This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 21597 - [XT3TS] higher-order-functions-068
Summary: [XT3TS] higher-order-functions-068
Alias: None
Product: XPath / XQuery / XSLT
Classification: Unclassified
Component: XSLT 3.0 Test Suite (show other bugs)
Version: Candidate Recommendation
Hardware: PC All
: P2 normal
Target Milestone: ---
Assignee: Abel Braaksma
QA Contact: Mailing list for public feedback on specs from XSL and XML Query WGs
Depends on:
Reported: 2013-04-05 17:17 UTC by Michael Kay
Modified: 2016-11-05 14:00 UTC (History)
1 user (show)

See Also:


Description Michael Kay 2013-04-05 17:17:36 UTC
I believe this test is incorrect.

The variable $first is bound to:

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)

But f:fib does not return a function; it returns an integer, so the body of this $first function does not return what it is declared to return. This would be clearer if the types of each function were properly declared; but certainly the outermost caller of f:fib is expecting it to return an integer.
Comment 1 Abel Braaksma 2014-01-15 16:39:43 UTC
I finally had some time to look more deeply into this. I agree that the function as written contains errors. It was a rewrite of the following example:

<xsl:function name="f:fibcont" as="xs:integer">
    <xsl:param name="n" as="xs:integer" />
    <xsl:param name="cont" as="function(xs:integer) as xs:integer" />
    <xsl:sequence select="
            if($n le 1) then $cont(1)
            else f:fibcont($n - 2, function($a as xs:integer) as xs:integer {
                f:fibcont($n - 1, function($b as xs:integer) as xs:integer {
                    $cont($a + $b)

which should be called with an identity function. However, the error in the test was not apparent because it is the same error the above function gets (i.e. "Required item type of second argument of anonymous function is function(*)"), which led me to trying to write it correctly while ignoring the error. In the above function, there is no anonymous function that takes function(*) as second argument, so the error is either misleading or wrong (or I made a typo again ;)).

I think that the above version is a more readable way of writing the CPS version of the Fibonacci algorithm and I think it should work in XSLT 3.0. I checked this version with the 2-argument cpsFunc JavaScript example here:, which I will copy below in case of linkrot:

function cpsFib(n, _return) {
    if (n <= 1) {
        return _return(1);
    } else {
        return cpsFib(n-2, function(a) {
            return cpsFib(n-1, function(b) {
                return _return(a+b);

I will also try to correct the $first/$second style version of the same CPS function, but without ability to test it, it's hard to write it correctly. The reasoning behind that rewrite was to find a way to express it in XPath/XSLT without having errors.
Comment 2 Abel Braaksma 2014-01-16 00:46:55 UTC
I just ran the example from my last comment against our processor and it returns the expected result, which leads me to conclude that it is written correctly. I also fixed the version in the test (using variables for the CPS functions) and like Michael said, the return type was incorrect (though it's incorrect on the anonymous functions, not on the stylesheet function).

The new function signature is as follows:

<xsl:function name="f:fib">
    <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)" />

I will leave this bug open for the moment to allow others to comment on whether they agree it is indeed corrected now.
Comment 3 Abel Braaksma 2014-05-23 15:19:16 UTC
There was no pushback from the community. I pushed this fix into the repository. Bug was resolved today.
Comment 4 Abel Braaksma 2015-05-06 21:11:59 UTC
Was resolved > 30 days ago, closing.
Comment 5 Michael Kay 2016-10-24 14:24:45 UTC
(For some reason we haven't been running this test recently. I've just removed it from our "don't run" exceptions list).

I believe the correct result of this test is now 89, not 55.

If I change the test to

    <xsl:template name="main">
         select="for $n in 1 to 12 return f:fib($n, function($a) {$a})" /></out>

I get 

    <out>1 1 2 3 5 8 13 21 34 55 89 144</out>

that is, the first 12 terms of the Fibonacci sequence. With the parameter 11 given in the published test, the correct result should be the 11th term of the sequence, that is 89.
Comment 6 Abel Braaksma 2016-11-05 14:00:33 UTC
I just ran this with Exselt and got 89 as well. And since it is clearly the 11th fib number, I fixed it accordingly.