Stack Overflow: Try tail recursion
I am writing a recursive function which is similar to the one here: https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-for... Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion". Any idea? Ciao, Giuseppe
To make it tail-recursive, make the recursive call the last operation in the function. https://en.wikipedia.org/wiki/Tail_call The else() clause is what keeps it from being tail recursive. Something like this should work: *declare variable* *$bookstore* := <bookstore> <book> <name>story</name> <price>50.00</price> <author>smith</author> </book> <book> <name>history</name> <price>150.00</price> <author>kelly</author> </book> <book> <name>epic</name> <price>300.00</price> <author>jones</author> </book> </bookstore>; *declare function* *local:sum*(*$books*, *$sum*) { *let* *$sum* := *$sum* + *$books*[1]/*price* *return* ( <price>{ *$sum* }</price>, *$books*[2] ! *local:sum*(*tail*(*$books*), *$sum*) ) }; <prices> { *local:sum*(*$bookstore*/*book*, 0) } </prices> Jonathan On Mon, Feb 18, 2019 at 10:24 AM Giuseppe G. A. Celano < celano@informatik.uni-leipzig.de> wrote:
I am writing a recursive function which is similar to the one here:
https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-for...
Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion".
Any idea?
Ciao, Giuseppe
Hi Jonathan, Thanks for that. However, it returns the same stack overflow error as the other script, when <book/> are 38000. Encreasing the JVM size does not help either. E-mail: celano@informatik.uni-leipzig.de <mailto:celano@informatik.uni-leipzig.de> Web site 1: http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano <http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano> Web site 2: https://sites.google.com/site/giuseppegacelano/ <https://sites.google.com/site/giuseppegacelano/>
On Feb 18, 2019, at 4:51 PM, Jonathan Robie <jonathan.robie@gmail.com> wrote:
To make it tail-recursive, make the recursive call the last operation in the function.
https://en.wikipedia.org/wiki/Tail_call <https://en.wikipedia.org/wiki/Tail_call>
The else() clause is what keeps it from being tail recursive. Something like this should work:
declare variable $bookstore := <bookstore> <book> <name>story</name> <price>50.00</price> <author>smith</author> </book> <book> <name>history</name> <price>150.00</price> <author>kelly</author> </book> <book> <name>epic</name> <price>300.00</price> <author>jones</author> </book> </bookstore>;
declare function local:sum($books, $sum) { let $sum := $sum + $books[1]/price return ( <price>{ $sum }</price>, $books[2] ! local:sum(tail($books), $sum) ) };
<prices> { local:sum($bookstore/book, 0) } </prices>
Jonathan
On Mon, Feb 18, 2019 at 10:24 AM Giuseppe G. A. Celano <celano@informatik.uni-leipzig.de <mailto:celano@informatik.uni-leipzig.de>> wrote: I am writing a recursive function which is similar to the one here:
https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-for... <https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-format>
Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion".
Any idea?
Ciao, Giuseppe
Hi Guiseppe, unfortunately the example won’t be tail-call optimized as your last statement is not the function call itself but a sequence construction that happens to contain the function call. Your function must be of the form:
f(x) => s(x) if your termination condition is met (i.e. no more books) f(x) => f(g(x))
Your function is defined (more or less) as something like:
f(x) => s(x) if your termination condition is met (i.e. no more books) f(x) => something + f(g(x))
So you have to get that something (i.e. the sequence concatenation) part inside your g-function, here’s what I think you might want: Cross-posted as gist for better readability https://gist.github.com/micheee/ef75c9f30449c2de3406182ff2fdce50 <https://gist.github.com/micheee/ef75c9f30449c2de3406182ff2fdce50>
declare variable $bookstore := <bookstore>{ for $i in 1 to 300000 return element book { element name { "Book " || $i }, element price { 1 }, element author { "Author "|| $i } } } </bookstore>;
(:~ Rolling total of prices @param $prices, accumulates the book prices. $prices[$n] contains the sum of prices for $book[position() <= $n] @param $books sequence of books not yet added to $prices :) declare function local:sum($prices, $books) { let $book := head($books) (: Get first book in sequence :) let $prices := if(count($prices) = 0) (: if empty, initialize prices with first price :) then ($book/price ) else ( (: add the current rolling total to the list of rolling totals :) (: that’s the concatenation part :) $prices, element price { $prices[count($prices)] + $book/price } ) return ( if(count($books) > 1) then local:sum($prices, tail($books)) (: here's the tail call :) else $prices ) };
<prices> { local:sum((), $bookstore/book) } </prices>
You can check if your query is tail-call optimized using the query info panel:
- mark as tail call: local:sum(if(empty($prices_2)) then (hea...
Hope this helps! Best from Konstanz Michael
Am 18.02.2019 um 19:12 schrieb Giuseppe G. A. Celano <celano@informatik.uni-leipzig.de>:
Hi Jonathan,
Thanks for that. However, it returns the same stack overflow error as the other script, when <book/> are 38000. Encreasing the JVM size does not help either.
E-mail: celano@informatik.uni-leipzig.de <mailto:celano@informatik.uni-leipzig.de> Web site 1: http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano <http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano> Web site 2: https://sites.google.com/site/giuseppegacelano/ <https://sites.google.com/site/giuseppegacelano/>
On Feb 18, 2019, at 4:51 PM, Jonathan Robie <jonathan.robie@gmail.com <mailto:jonathan.robie@gmail.com>> wrote:
To make it tail-recursive, make the recursive call the last operation in the function.
https://en.wikipedia.org/wiki/Tail_call <https://en.wikipedia.org/wiki/Tail_call>
The else() clause is what keeps it from being tail recursive. Something like this should work:
declare variable $bookstore := <bookstore> <book> <name>story</name> <price>50.00</price> <author>smith</author> </book> <book> <name>history</name> <price>150.00</price> <author>kelly</author> </book> <book> <name>epic</name> <price>300.00</price> <author>jones</author> </book> </bookstore>;
declare function local:sum($books, $sum) { let $sum := $sum + $books[1]/price return ( <price>{ $sum }</price>, $books[2] ! local:sum(tail($books), $sum) ) };
<prices> { local:sum($bookstore/book, 0) } </prices>
Jonathan
On Mon, Feb 18, 2019 at 10:24 AM Giuseppe G. A. Celano <celano@informatik.uni-leipzig.de <mailto:celano@informatik.uni-leipzig.de>> wrote: I am writing a recursive function which is similar to the one here:
https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-for... <https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-format>
Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion".
Any idea?
Ciao, Giuseppe
Hi Michael - that's a very nice solution! Thanks for sharing! On Tue, Feb 19, 2019 at 6:14 AM Michael Seiferle <ms@basex.org> wrote:
Hi Guiseppe,
unfortunately the example won’t be tail-call optimized as your last statement is not the function call itself but a sequence construction that happens to contain the function call.
Your function must be of the form:
f(x) => s(x) if your termination condition is met (i.e. no more books) f(x) => f(g(x))
Your function is defined (more or less) as something like:
f(x) => s(x) if your termination condition is met (i.e. no more books) f(x) => something + f(g(x))
So you have to get that something (i.e. the sequence concatenation) part inside your g-function, here’s what I think you might want:
Cross-posted as gist for better readability https://gist.github.com/micheee/ef75c9f30449c2de3406182ff2fdce50
declare variable $bookstore := <bookstore>{ for $i in 1 to 300000 return element book { element name { "Book " || $i }, element price { 1 }, element author { "Author "|| $i } } } </bookstore>;
(:~ Rolling total of prices @param $prices, accumulates the book prices. $prices[$n] contains the sum of prices for $book[position() <= $n] @param $books sequence of books not yet added to $prices :) declare function local:sum($prices, $books) { let $book := head($books) (: Get first book in sequence :) let $prices := if(count($prices) = 0) (: if empty, initialize prices with first price :) then ($book/price ) else ( (: add the current rolling total to the list of rolling totals :) (: that’s the concatenation part :) $prices, element price { $prices[count($prices)] + $book/price } ) return ( if(count($books) > 1) then local:sum($prices, tail($books)) (: here's the tail call :) else $prices ) };
<prices> { local:sum((), $bookstore/book) } </prices>
You can check if your query is tail-call optimized using the query info panel:
- mark as tail call: local:sum(if(empty($prices_2)) then (hea...
Hope this helps!
Best from Konstanz
Michael
Am 18.02.2019 um 19:12 schrieb Giuseppe G. A. Celano < celano@informatik.uni-leipzig.de>:
Hi Jonathan,
Thanks for that. However, it returns the same stack overflow error as the other script, when <book/> are 38000. Encreasing the JVM size does not help either.
E-mail: celano@informatik.uni-leipzig.de Web site 1: http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano Web site 2: https://sites.google.com/site/giuseppegacelano/
On Feb 18, 2019, at 4:51 PM, Jonathan Robie <jonathan.robie@gmail.com> wrote:
To make it tail-recursive, make the recursive call the last operation in the function.
https://en.wikipedia.org/wiki/Tail_call
The else() clause is what keeps it from being tail recursive. Something like this should work:
*declare variable* *$bookstore* := <bookstore> <book> <name>story</name> <price>50.00</price> <author>smith</author> </book> <book> <name>history</name> <price>150.00</price> <author>kelly</author> </book> <book> <name>epic</name> <price>300.00</price> <author>jones</author> </book> </bookstore>;
*declare function* *local:sum*(*$books*, *$sum*) { *let* *$sum* := *$sum* + *$books*[1]/*price* *return* ( <price>{ *$sum* }</price>, *$books*[2] ! *local:sum*(*tail*(*$books*), *$sum*) ) };
<prices> { *local:sum*(*$bookstore*/*book*, 0) } </prices>
Jonathan
On Mon, Feb 18, 2019 at 10:24 AM Giuseppe G. A. Celano < celano@informatik.uni-leipzig.de> wrote:
I am writing a recursive function which is similar to the one here:
https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-for...
Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion".
Any idea?
Ciao, Giuseppe
Thanks! This works perfectly
On Feb 19, 2019, at 6:08 PM, Bridger Dyson-Smith <bdysonsmith@gmail.com> wrote:
Hi Michael - that's a very nice solution! Thanks for sharing!
On Tue, Feb 19, 2019 at 6:14 AM Michael Seiferle <ms@basex.org <mailto:ms@basex.org>> wrote: Hi Guiseppe,
unfortunately the example won’t be tail-call optimized as your last statement is not the function call itself but a sequence construction that happens to contain the function call.
Your function must be of the form:
f(x) => s(x) if your termination condition is met (i.e. no more books) f(x) => f(g(x))
Your function is defined (more or less) as something like:
f(x) => s(x) if your termination condition is met (i.e. no more books) f(x) => something + f(g(x))
So you have to get that something (i.e. the sequence concatenation) part inside your g-function, here’s what I think you might want:
Cross-posted as gist for better readability https://gist.github.com/micheee/ef75c9f30449c2de3406182ff2fdce50 <https://gist.github.com/micheee/ef75c9f30449c2de3406182ff2fdce50>
declare variable $bookstore := <bookstore>{ for $i in 1 to 300000 return element book { element name { "Book " || $i }, element price { 1 }, element author { "Author "|| $i } } } </bookstore>;
(:~ Rolling total of prices @param $prices, accumulates the book prices. $prices[$n] contains the sum of prices for $book[position() <= $n] @param $books sequence of books not yet added to $prices :) declare function local:sum($prices, $books) { let $book := head($books) (: Get first book in sequence :) let $prices := if(count($prices) = 0) (: if empty, initialize prices with first price :) then ($book/price ) else ( (: add the current rolling total to the list of rolling totals :) (: that’s the concatenation part :) $prices, element price { $prices[count($prices)] + $book/price } ) return ( if(count($books) > 1) then local:sum($prices, tail($books)) (: here's the tail call :) else $prices ) };
<prices> { local:sum((), $bookstore/book) } </prices>
You can check if your query is tail-call optimized using the query info panel:
- mark as tail call: local:sum(if(empty($prices_2)) then (hea...
Hope this helps!
Best from Konstanz
Michael
Am 18.02.2019 um 19:12 schrieb Giuseppe G. A. Celano <celano@informatik.uni-leipzig.de <mailto:celano@informatik.uni-leipzig.de>>:
Hi Jonathan,
Thanks for that. However, it returns the same stack overflow error as the other script, when <book/> are 38000. Encreasing the JVM size does not help either.
E-mail: celano@informatik.uni-leipzig.de <mailto:celano@informatik.uni-leipzig.de> Web site 1: http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano <http://asv.informatik.uni-leipzig.de/en/staff/Giuseppe_Celano> Web site 2: https://sites.google.com/site/giuseppegacelano/ <https://sites.google.com/site/giuseppegacelano/>
On Feb 18, 2019, at 4:51 PM, Jonathan Robie <jonathan.robie@gmail.com <mailto:jonathan.robie@gmail.com>> wrote:
To make it tail-recursive, make the recursive call the last operation in the function.
https://en.wikipedia.org/wiki/Tail_call <https://en.wikipedia.org/wiki/Tail_call>
The else() clause is what keeps it from being tail recursive. Something like this should work:
declare variable $bookstore := <bookstore> <book> <name>story</name> <price>50.00</price> <author>smith</author> </book> <book> <name>history</name> <price>150.00</price> <author>kelly</author> </book> <book> <name>epic</name> <price>300.00</price> <author>jones</author> </book> </bookstore>;
declare function local:sum($books, $sum) { let $sum := $sum + $books[1]/price return ( <price>{ $sum }</price>, $books[2] ! local:sum(tail($books), $sum) ) };
<prices> { local:sum($bookstore/book, 0) } </prices>
Jonathan
On Mon, Feb 18, 2019 at 10:24 AM Giuseppe G. A. Celano <celano@informatik.uni-leipzig.de <mailto:celano@informatik.uni-leipzig.de>> wrote: I am writing a recursive function which is similar to the one here:
https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-for... <https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-format>
Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion".
Any idea?
Ciao, Giuseppe
You can also increase the JVM stack size for the BaseX GUI. Example, if you are on Linux go to the BaseX bin directory, edit the basexgui file, and change these lines # Options for virtual machine (can be extended by global options) BASEX_JVM="-Xmx6g -Xss4m $BASEX_JVM" There isn't really a specific number you need to use. The default is 1MB on a 64bit PC. More information about Xss JVM flag on [1] [1] https://stackoverflow.com/questions/3700459/how-to-increase-the-java-stack-s... On 2/18/19 5:24 PM, Giuseppe G. A. Celano wrote:
I am writing a recursive function which is similar to the one here:
https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-for...
Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion".
Any idea?
Ciao, Giuseppe
participants (5)
-
Bridger Dyson-Smith -
George Sofianos -
Giuseppe G. A. Celano -
Jonathan Robie -
Michael Seiferle