[xquery-talk] tail recursive identity transformation

[Kendall Shaw]

I don't remember seeing an xquery function that tries to return it's
input unchanged.

Can this be improved:

declare function local:id($e as element()?, $acc as element()?) as
element() {
  if (empty($e)) then
    $acc
 else
    local:id(()
            , element {node-name($e)} {
              $e/@*
              , for $node in $e/node()
                return typeswitch($node)
                         case element() return local:id($node, $acc)
                         default return $node
            })
};

The idea is that functions that do more than return their input could be
based on the function, and benefit from tail call optimization.

Kendall


_______________________________________________
***@x-que

[Michael Kay]

I'm very confused by this. The function body contains two recursive calls. The one inside the typeswitch is certainly not tail-recursive, so you're going to get recursion depth equal to the maximum tree depth. The other call, as far as I can see, merely returns its second argument unchanged, which seems totally pointless.

Michael Kay
Saxonica

I don't remember seeing an xquery function that tries to return it's input unchanged.
declare function local:id($e as element()?, $acc as element()?) as element() {
if (empty($e)) then
$acc
else
local:id(()
, element {node-name($e)} {
, for $node in $e/node()
return typeswitch($node)
case element() return local:id($node, $acc)
default return $node
})
};
The idea is that functions that do more than return their input could be based on the function, and benefit from tail call optimization.
Kendall
_______________________________________________
http://x-query.com/mailman/listinfo/talk

_______________________________________________
***@x-query.com
http://x-query.com/mailman/listinfo/talk

[Kendall Shaw]

I was trying to do something like:

  def id(e: List[Int], acc: List[Int]): List[Int] =
    if (e.isEmpty)
      acc.reverse
    else
      id(e.tail, e.head :: acc)

or

<xsl:template match="@*|node()">
  <xsl:copy>
    <xsl:apply-templates select="@*|node()"/>
  </xsl:copy>
</xsl:template>

But, I didn't figure how to pass anything analogous to "head" of an
element, or analagous to <xsl:copy/>.

If you can give an example of a tail recursive identity transformation
in XQuery that would be helpful to me.

Kendall

Post by Michael Kay
I'm very confused by this. The function body contains two recursive calls. The one inside the typeswitch is certainly not tail-recursive, so you're going to get recursion depth equal to the maximum tree depth. The other call, as far as I can see, merely returns its second argument unchanged, which seems totally pointless.
Michael Kay
Saxonica

I don't remember seeing an xquery function that tries to return it's input unchanged.
declare function local:id($e as element()?, $acc as element()?) as element() {
if (empty($e)) then
$acc
else
local:id(()
, element {node-name($e)} {
, for $node in $e/node()
return typeswitch($node)
case element() return local:id($node, $acc)
default return $node
})
};
The idea is that functions that do more than return their input could be based on the function, and benefit from tail call optimization.
Kendall
_______________________________________________
http://x-query.com/mailman/listinfo/talk

_______________________________________________
http://x-query.com/mailman/listinfo/talk

_______________________________________________
talk

[Michael Kay]

If you can give an example of a tail recursive identity transformation in XQuery that would be helpful to me.

I don't see how it can be possible. It's a task that naturally requires a stack. One could possibly do something very contrived that uses an application-level data structure in place of the stack, but it's not clear what benefits this would bring.

Michael Kay
Saxonica


_______________________________________________
***@x-query.com
http://x-query.com/mailman/listinfo/talk

[John Snelson]

I don't think you can do a tail recursive tree walk of an XDM tree - you
at least need a stack of the path taken to a particular node in order to
process first it's children, and then it's following siblings. You could
track the stack as an accumulating argument to the recursive call, but
it may just be easier and more readable to use the function call stack.

Additionally when constructing a result tree, I think most XQuery
implementations will need to generate an "end tag" after the recursive
call - which will mean the recursive call won't be at the "tail" at all.
It's probably possible to optimize this case specifically - but again it
will entail the implementation keeping track of constructed elements
that still need to be closed in some kind of stack.

John

Post by Kendall Shaw
def id(e: List[Int], acc: List[Int]): List[Int] =
if (e.isEmpty)
acc.reverse
else
id(e.tail, e.head :: acc)
or
<xsl:copy>
</xsl:copy>
</xsl:template>
But, I didn't figure how to pass anything analogous to "head" of an
element, or analagous to <xsl:copy/>.
If you can give an example of a tail recursive identity transformation
in XQuery that would be helpful to me.
Kendall

Post by Michael Kay
I'm very confused by this. The function body contains two recursive
calls. The one inside the typeswitch is certainly not tail-recursive,
so you're going to get recursion depth equal to the maximum tree
depth. The other call, as far as I can see, merely returns its second
argument unchanged, which seems totally pointless.
Michael Kay
Saxonica

I don't remember seeing an xquery function that tries to return it's input unchanged.
declare function local:id($e as element()?, $acc as element()?) as element() {
if (empty($e)) then
$acc
else
local:id(()
, element {node-name($e)} {
, for $node in $e/node()
return typeswitch($node)
case element() return local:id($node, $acc)
default return $node
})
};
The idea is that functions that do more than return their input
could be based on the function, and benefit from tail call
optimization.
Kendall
_______________________________________________
http://x-query.com/mailman/listinfo/talk

_______________________________________________
http://x-query.com/mailman/listinfo/talk

_______________________________________________
http://x-query.com/mailman/listinfo/talk