tail recursion issue in 9.4.3

On 9/13/20, Mark McSweeny <mcsweeny at shaw.ca> wrote: > Hello, > > I have encountered a difference in behaviour between versions 9.3.3 and > 9.4.3 for a certain query involving tail recursion. In 9.3.3 the > compiled query plan correctly applied tail call optimization. But in > 9.4.3 tail call optimization is not applied, resulting in a stack > overflow during execution. > > Here is a minimal query that demonstrates the issue: > > > declare function local:f($n, $xs) > { > if ($n = 0) then $xs > else > let $x := > copy $node := <a/> modify ( rename node $node as 'x') return $node > return local:f($n - 1, ($xs, $x)) > }; > local:f(2000, ()) > > > > Mark > >

On 2020-09-13 10:42, Christian Grün wrote: > Hi Mark, > > With BaseX 9.4.3, your FLWOR expression will be rewritten to a simple > map expression – for which no TCOs detection was implemented so far. > It works with the latest snapshot [1]. > > If you want to stick with 9.4.3, you can manually inline $x: > > declare function local:f($n, $xs) { > if ($n = 0) then $xs else local:f($n - 1, ($xs, > copy $node := <a/> > modify rename node $node as 'x' > return $node > )) > }; > local:f(2000, ()) > > Hope this helps > Christian > > [1] https://files.basex.org/releases/latest/ > > > On 9/13/20, Mark McSweeny <mcsweeny at shaw.ca> wrote: >> Hello, >> >> I have encountered a difference in behaviour between versions 9.3.3 and >> 9.4.3 for a certain query involving tail recursion. In 9.3.3 the >> compiled query plan correctly applied tail call optimization. But in >> 9.4.3 tail call optimization is not applied, resulting in a stack >> overflow during execution. >> >> Here is a minimal query that demonstrates the issue: >> >> >> declare function local:f($n, $xs) >> { >> if ($n = 0) then $xs >> else >> let $x := >> copy $node := <a/> modify ( rename node $node as 'x') return $node >> return local:f($n - 1, ($xs, $x)) >> }; >> local:f(2000, ()) >> >> >> >> Mark >> >>