Stack Overflow: Try tail recursion

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-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 > >

On Mon, Feb 18, 2019 at 10:24 AM Giuseppe G. A. Celano < celano at 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-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 > > >

> On Feb 18, 2019, at 4:51 PM, Jonathan Robie <jonathan.robie at 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 at informatik.uni-leipzig.de <mailto:celano at 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-format <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 > >

> f(x) => s(x) if your termination condition is met (i.e. no more books) > f(x) => f(g(x))

> f(x) => s(x) if your termination condition is met (i.e. no more books) > f(x) => something + f(g(x))

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>

> - mark as tail call: local:sum(if(empty($prices_2)) then (hea...

> Am 18.02.2019 um 19:12 schrieb Giuseppe G. A. Celano <celano at 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 at informatik.uni-leipzig.de <mailto:celano at 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 at gmail.com <mailto:jonathan.robie at 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 at informatik.uni-leipzig.de <mailto:celano at 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-format <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 >> >> >

On Tue, Feb 19, 2019 at 6:14 AM Michael Seiferle <ms at 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 at 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 at 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 at 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 at 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-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 >> >> >> > >

> On Feb 19, 2019, at 6:08 PM, Bridger Dyson-Smith <bdysonsmith at 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 at basex.org <mailto:ms at 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 at informatik.uni-leipzig.de <mailto:celano at 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 at informatik.uni-leipzig.de <mailto:celano at 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 at gmail.com <mailto:jonathan.robie at 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 at informatik.uni-leipzig.de <mailto:celano at 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-format <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 >>> >>> >> >