[Bug 8662] New: [XQuery 1.1] Need an easy way to define a recursive inline function

http://www.w3.org/Bugs/Public/show_bug.cgi?id=8662

           Summary: [XQuery 1.1] Need an easy way to define a recursive
                    inline function
           Product: XPath / XQuery / XSLT
           Version: Working drafts
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: XQuery 1.1
        AssignedTo: jonathan.robie@redhat.com
        ReportedBy: int19h@gmail.com
         QAContact: public-qt-comments@w3.org
                CC: john.snelson@oracle.com


With the syntax and semantics of inline functions as defined by XQuery 1.1
Working Draft from 15 December 2009, there is no clean and easy way to define
an inline function that can recursively call itself, nor there is any such way
to define two or more mutually recursive inline functions. In particular:

    let $fib := function($n as xs:integer) as xs:integer {
       if ($n < 3) then 1 else $fib($n-1) + $fib($n+2)
    }
    return $fib(10)

doesn't work, because $fib isn't yet bound within the body of the inline
function used for its initializer. The only workaround is to explicitly pass
the function to itself:

    let $fib := function($fib as item(), $n as xs:integer) as xs:integer {
       if ($n < 3) then 1 else $fib($n-1) + $fib($n+2)
    }
    return $fib($fib, 10)

however, this requires the type of $fib to be specified as item(), as there is
no way to spell out a recursive function type (that has parameter of its own
type).

A typical usage scenario for this is a loop where every iteration depends on
the result of computation of the previous one, expressed as a self-recursive
inline function with accumulator-passing style (since such a thing cannot, in
general, be expressed as an FLWOR expression) - a very common case in many
other functional languages, such as Scheme, ML or Haskell.

Some possible approaches to tackle this:

1) Add a special construct analogous to "let", specifically to define recursive
local functions, with identifier being defined accessible within the body of
the function. E.g. "local function ... return ...":

    local function fib($n as xs:integer) as xs:integer {
       if ($n < 3) then 1 else $fib($n-1) + $fib($n+2)
    }
    return fib(10)

This has the advantage that it could be trivially extended to mutually
recursive functions, wherein "local function" would allow a comma-separated
list of function definitions like "let", all of which would be in scope of all
function bodies thus defined within the same construct:

    local function foo() { bar() },
                   bar() { foo() }
    return foo()

2) Add a special, strongly typed construct to reference or call the function
from within its body, e.g. "recurse":

    return (function($n as xs:integer) as xs:integer {
        if ($n < 3) then 1 else recurse($n-1) + recurse($n+2)
    })(10)

where "recurse" is only defined within a function body, always has exact same
signature as the innermost enclosing function, and, ideally, can be used with
operator # to produce function items, as in "recurse#1" in the above example.

This only covers the self-recursive case, but is significantly shorter for a
particularly common case of function being called only once outside its body,
by removing the need to bind it to a variable altogether. It may also make the
typical intent of such a construct clearer, especially with a well-chosen
syntax.


-- 
Configure bugmail: http://www.w3.org/Bugs/Public/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.

Received on Wednesday, 6 January 2010 17:21:23 UTC