Recursion with anonymous (inline) functions in XPath 3.0

A few days ago Roger Costello asked at the xsl-list
forum:

Hi Folks

Is it possible to do recursion in an anonymous function?

Example: I would like to implement an "until" function. It has 
three arguments:

1. p is a boolean function
2. f is a function on x
3. x is the value being processed

Read the following function call as: decrement 3 until 
it is negative
$until ($isNegative, $decrement, 3)

where
$isNegative := function($x as xs:integer) {$x lt 0}
$decrement := function($x as xs:integer) {$x - 1}

Here's how I attempted to implement function until:

$until := function(
                   $p as function(item()*) as xs:boolean,
                   $f as function(item()*) as item()*,
                   $x as item()*
                   ) as item()*
            {
             if ($p($x))
                then
                   $x
                else
                   $until($p, $f, $f($x))  <-- RECURSE ...THIS IS
                           NOT ALLOWED, I THINK
            }

Is there a way to implement function until in XPath 3.0? 
(I know how to implement it in XSLT 3.0)

Roger is strictly speaking correct – because an anonymous function cannot call itself by name – it just doesn’t have a name …

However, we can still implement recursion using only inline function(s).

Here is my first attempt on a factorial inline function:

let $f := function($n as xs:integer,
                   $f1 as function(xs:integer) as xs:integer
                  ) as xs:integer
          {if($n eq 0)
               then 1
               else $n * $f1($n -1, $f1)
          }
     return
        $f(5, $f)

The result we get is correct:

120

OK, what happens here?

An inline function cannot call itself, because it doesn’t know its name and in this respect behaves like an Alzheimer disease victim.

The idea is to give this sick person a written note identifying the person to whom he has to pass the remainder of the task. And if he himself happens to be on this note, he will pass the task to himself (and forget immediately it was him doing the previous step).

The only special thing to notice here is how the processing is initiated:

$f(5, $f)

calling the function and passing itself to itself.

This initiation may seem weird to a client and is also error-prone. This is why we can further improve the solution so that no weirdness remains on the surface:

let $f := function($n as xs:integer,
                   $f1 as function(xs:integer,
                   function()) as xs:integer
                   ) as xs:integer
             {if($n eq 0)
                 then 1
                 else $n * $f1($n -1, $f1)

              },
    $F := function($n as xs:integer) as xs:integer
            {
                $f($n, $f)
            }

   return
           $F(5)

Now we produced an inline, anonymous function $F, which given an argument $n, produces $n!

There are two interesting sides of this story:

  1. We show how elegant and powerful XPath 3.0 HOFs are.
  2. More than ever it is clear now that XPath 3.0 is emerging as a full-pledged, stand-alone functional programming language in its own right that doesn’t need to be hosted by another language, such as XSLT or XQuery.

Some nice features we might still need, that could be just after the turn of the road (Read: In a post – 3.0 XPath version):

  1. Stand-alone XPath processors.
  2. Import/include directives for XPath-only files.
  3. Separate packaging/compilation of XPath-only programs.
  4. New data structures such as tuples.
  5. Generics – parametric data types.

I have been dreaming about this since the time I shared in this blog the XPath-only implementation of the Binary Search tree and the Set datatype.

About these ads
This entry was posted in Higher Order Functions, XPath 3.0 and tagged , , . Bookmark the permalink.

3 Responses to Recursion with anonymous (inline) functions in XPath 3.0

  1. Oh, Dmitre, that is just beautiful!

    • Thank you Michael. Yes this is a beatiful result. Now, one can better understand why it would be very good to predefine the XML schema namespace (and its associated prefix “xs”) in XSLT, the same way this is done in XQuery. We can execute the XPath code with any XQuery processor and it will perform as expected. The same cannot be said for XSLT (pasting the XPath code into the “select” attribute of <xsl:sequence>) because the XSLT stylesheet may not have defined the association between the XSD namespace and the prefix “xs”. It would be really good if such automatic association is added to the XSLT 3.0 specification.

  2. Pingback: Recursion with anonymous (inline) functions in XPath 3.0 — Part II | XSLT: Riding the challenge

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s