tail recursion: how to ensure it?

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

tail recursion: how to ensure it?

adrianv
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
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

nophead
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
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

adrianv
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
tp3
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

tp3
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
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

jon_bondy
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
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

thehans
 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
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

thehans
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=midpoint
function _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
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

thehans
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=midpoint
function _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
tp3
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

tp3
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
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

thehans
Ah, yeah I wasn't really thinking when I wrote that.  You're right for regular module/function recursion detection it is stack limited.  
I guess I just had tail recursion in mind, the special case which is specifically made to avoid stack issues, still has a hard-coded limit of 1 million.  Make it a 100M or 1B I say :D

On Fri, Mar 22, 2019 at 8:46 PM Torsten Paul <[hidden email]> wrote:
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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
tp3
Reply | Threaded
Open this post in threaded view
|

Re: tail recursion: how to ensure it?

tp3
On 23.03.19 03:52, Hans L wrote:
> of 1 million.  Make it a 100M or 1B I say :D

Or maybe even better, make it possible to cancel, so we don't
need to have a number at all?

ciao,
   Torsten.


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
-- Torsten