# tail recursion: how to ensure it? Classic List Threaded 11 messages Open this post in threaded view
|

## tail recursion: how to ensure it?

 I wrote a sum function that uses tail recursion.  I know it uses tail recursion because it can add up 0.9 million entries whereas a previous version would get the "recursion" error.  I tried to write an "all" function the same way, but it's not getting tail recursion.  The intention was that all() would quit recursing as soon as it got a "false", and also that it would recurse into sublists.  But the code has the form of ending with a recursive call, so why don't I get the tail recursion unwrapped?  How can I fix it?   function replist(list, N) = [for(i=[0:N-1]) list]; test = replist(true,900000); function all(list,n=0) =    n==len(list) ? true :    !(is_list(list[n])? all(list[n]) : list[n]) ? false :    all(list,n+1); function sum(list, n=0, total=0) =  n == len(list) ? total : sum(list, n+1, total+list[n]); function sumall(list) =     sum([for(entry=list) (is_list(entry) ? sumall(entry) : entry) ? 0 : 1])==0; echo("sum all: ", sumall(test)); echo("all:",all(test)); -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: tail recursion: how to ensure it?

 Although it has a tail recursion, it also has non-tail recursion. My guess is that it will unwrap to make a loop with a recursive call in the middle.On Fri, 22 Mar 2019, 13:28 adrianv, <[hidden email]> wrote:I wrote a sum function that uses tail recursion.  I know it uses tail recursion because it can add up 0.9 million entries whereas a previous version would get the "recursion" error.  I tried to write an "all" function the same way, but it's not getting tail recursion.  The intention was that all() would quit recursing as soon as it got a "false", and also that it would recurse into sublists.  But the code has the form of ending with a recursive call, so why don't I get the tail recursion unwrapped?  How can I fix it?  function replist(list, N) = [for(i=[0:N-1]) list]; test = replist(true,900000); function all(list,n=0) =    n==len(list) ? true :    !(is_list(list[n])? all(list[n]) : list[n]) ? false :    all(list,n+1); function sum(list, n=0, total=0) =  n == len(list) ? total : sum(list, n+1, total+list[n]); function sumall(list) =     sum([for(entry=list) (is_list(entry) ? sumall(entry) : entry) ? 0 : 1])==0; echo("sum all: ", sumall(test)); echo("all:",all(test)); -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: tail recursion: how to ensure it?

 Taking out the obvious non-tail recursion as a test (and disregarding that the answer is wrong) does not fix it.  I still get non-tail recursion.  The recursive call in the middle is very limited since it only calls on nested lists.  You can't hit the recursion limit from that call.   But the point is that this also fails to get tail recursion.  Now there's only the one recursive call at the end.   function all(list,n=0) =    n==len(list) ? true :    !(is_list(list[n])? /*all(list[n])*/ list[n] : list[n]) ? false :    all(list,n+1); Simplifying more: function all(list,n=0) =    n==len(list) ? true :    !list[n] ? false :    all(list,n+1); Still I don't get the tail recursion.  If I reduce it this far: function all(list,n=0) =    n==len(list) ? true :    all(list,n+1); then it finally "works".  So do I have to write my function with just a single test in it, without any cascaded tests, if I want to get the tail recursion unwrapping?   Then it seems I have to rewrite it like this: function all(list,n=0) =    n!=len(list) && (is_list(list[n]) && all(list[n]) || !is_list(list[n]) && list[n]) ? all(list,n+1) :    n==len(list) ? true : false; which is somewhat more obscure.  Is there any better way?   -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: tail recursion: how to ensure it?

 The only case where tail recursion is currently supported is if the top level expression is a ternary operator (?:) and one of the branches is the function itself. function sum1(v, i = 0, a = 0) = i >= len(v) ? a : sum1(v, i + 1, a + v[i]); echo(sum1(rands(0, 1, 1000000))); vs. function sum2(v, i = 0) = i < len(v) ? v[i] + sum2(v, i + 1) : 0; echo(sum2(rands(0, 1, 10000))); ciao,    Torsten. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org -- Torsten
Open this post in threaded view
|

## Re: tail recursion: how to ensure it?

 Well, that will be easy to remember... :( On 3/22/2019 12:36 PM, Torsten Paul wrote: > The only case where tail recursion is currently supported is > if the top level expression is a ternary operator (?:) and one > of the branches is the function itself. > > function sum1(v, i = 0, a = 0) = i >= len(v) ? a : sum1(v, i + 1, a + > v[i]); > echo(sum1(rands(0, 1, 1000000))); > > vs. > > function sum2(v, i = 0) = i < len(v) ? v[i] + sum2(v, i + 1) : 0; > echo(sum2(rands(0, 1, 10000))); > > ciao, >   Torsten. > _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: tail recursion: how to ensure it?

 Basically what Torsten said, but I would add that the other branch can be any other expression *except* a direct function call (a function call inside another expression should be ok I think).  So you can nest ternarys on non-recurring branch as much as you want.I was actually just looking at the source code that handles this the other day out of curiosity.  You can see the check here:And how it performs the actual evaluation is just above that:Contributions are welcome if you have ideas to improve the detection/evaluation.On Fri, Mar 22, 2019 at 1:24 PM jon <[hidden email]> wrote:Well, that will be easy to remember... :( On 3/22/2019 12:36 PM, Torsten Paul wrote: > The only case where tail recursion is currently supported is > if the top level expression is a ternary operator (?:) and one > of the branches is the function itself. > > function sum1(v, i = 0, a = 0) = i >= len(v) ? a : sum1(v, i + 1, a + > v[i]); > echo(sum1(rands(0, 1, 1000000))); > > vs. > > function sum2(v, i = 0) = i < len(v) ? v[i] + sum2(v, i + 1) : 0; > echo(sum2(rands(0, 1, 10000))); > > ciao, >   Torsten. > _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: tail recursion: how to ensure it?

 Another workaround I was recently experimenting with is to split the workload into recursive binary tree of calls.  Here is an example I just function I wrote that can join huge lists of strings(or "character" strings).  On 1 million items it should only reach recursion depth of about 20.function join(list, sep="") = let(size = len(list)) size > 0 ?   (sep == "" ? _jb(list,0,size) : let(\$sep=sep) _js(list,0,size,sep)) :  "";// "join binary", splits list into halves and joins them. // l=list, b=begin(inclusive), e=end(exlusive), s=size, m=midpointfunction _jb(l,b,e) = let(s=e-b, m=floor(b+s/2)) s > 2 ?   str(_jb(l,b,m), _jb(l,m,e)) :  s == 2 ?     str(l[b],l[b+1]) :     l[b];// join with separator p (s was already taken)function _js(l,b,e,p) = let(s=e-b, m=floor(b+s/2)) s > 2 ?   str(_js(l,b,m,p),p,_js(l,m,e,p)) :  s == 2 ?     str(l[b],p,l[b+1]) :     l[b];On Fri, Mar 22, 2019 at 7:54 PM Hans L <[hidden email]> wrote: Basically what Torsten said, but I would add that the other branch can be any other expression *except* a direct function call (a function call inside another expression should be ok I think).  So you can nest ternarys on non-recurring branch as much as you want.I was actually just looking at the source code that handles this the other day out of curiosity.  You can see the check here:And how it performs the actual evaluation is just above that:Contributions are welcome if you have ideas to improve the detection/evaluation.On Fri, Mar 22, 2019 at 1:24 PM jon <[hidden email]> wrote:Well, that will be easy to remember... :( On 3/22/2019 12:36 PM, Torsten Paul wrote: > The only case where tail recursion is currently supported is > if the top level expression is a ternary operator (?:) and one > of the branches is the function itself. > > function sum1(v, i = 0, a = 0) = i >= len(v) ? a : sum1(v, i + 1, a + > v[i]); > echo(sum1(rands(0, 1, 1000000))); > > vs. > > function sum2(v, i = 0) = i < len(v) ? v[i] + sum2(v, i + 1) : 0; > echo(sum2(rands(0, 1, 10000))); > > ciao, >   Torsten. > _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: tail recursion: how to ensure it?

 Another thing it might be worth discussing is if we should bump the somewhat arbitrary limits for various loops and recursion, or maybe allow them to be user-configurable/overridable.I've been revisiting my L-system script recently and wasn't sure if I was the only one bumping up against these sort of limits.  If its a pain point for a number of people, requiring weird workarounds or very specifically-written code, then it might be worth raising those limits.On Fri, Mar 22, 2019 at 8:03 PM Hans L <[hidden email]> wrote:Another workaround I was recently experimenting with is to split the workload into recursive binary tree of calls.  Here is an example I just function I wrote that can join huge lists of strings(or "character" strings).  On 1 million items it should only reach recursion depth of about 20.function join(list, sep="") = let(size = len(list)) size > 0 ?   (sep == "" ? _jb(list,0,size) : let(\$sep=sep) _js(list,0,size,sep)) :  "";// "join binary", splits list into halves and joins them. // l=list, b=begin(inclusive), e=end(exlusive), s=size, m=midpointfunction _jb(l,b,e) = let(s=e-b, m=floor(b+s/2)) s > 2 ?   str(_jb(l,b,m), _jb(l,m,e)) :  s == 2 ?     str(l[b],l[b+1]) :     l[b];// join with separator p (s was already taken)function _js(l,b,e,p) = let(s=e-b, m=floor(b+s/2)) s > 2 ?   str(_js(l,b,m,p),p,_js(l,m,e,p)) :  s == 2 ?     str(l[b],p,l[b+1]) :     l[b];On Fri, Mar 22, 2019 at 7:54 PM Hans L <[hidden email]> wrote: Basically what Torsten said, but I would add that the other branch can be any other expression *except* a direct function call (a function call inside another expression should be ok I think).  So you can nest ternarys on non-recurring branch as much as you want.I was actually just looking at the source code that handles this the other day out of curiosity.  You can see the check here:And how it performs the actual evaluation is just above that:Contributions are welcome if you have ideas to improve the detection/evaluation.On Fri, Mar 22, 2019 at 1:24 PM jon <[hidden email]> wrote:Well, that will be easy to remember... :( On 3/22/2019 12:36 PM, Torsten Paul wrote: > The only case where tail recursion is currently supported is > if the top level expression is a ternary operator (?:) and one > of the branches is the function itself. > > function sum1(v, i = 0, a = 0) = i >= len(v) ? a : sum1(v, i + 1, a + > v[i]); > echo(sum1(rands(0, 1, 1000000))); > > vs. > > function sum2(v, i = 0) = i < len(v) ? v[i] + sum2(v, i + 1) : 0; > echo(sum2(rands(0, 1, 10000))); > > ciao, >   Torsten. > _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: tail recursion: how to ensure it?

 On 23.03.19 02:41, Hans L wrote: > Another thing it might be worth discussing is if we should bump the > somewhat arbitrary limits for various loops and recursion, or maybe > allow them to be user-configurable/overridable. For loops, yes. For recursion, that's not possible as it's memory based. It tries to stop before running out of stack space. The only way to improve there is to reduce stack usage on recursion and/or increase available stack space. ciao,    Torsten. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org -- Torsten