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/
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, avm4@cornell.edu 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
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/
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.
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.
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:
https://github.com/openscad/openscad/blob/926c5d58234fad38e46313572716b182321fd065/src/function.cc#L114-L126
And how it performs the actual evaluation is just above that:
https://github.com/openscad/openscad/blob/926c5d58234fad38e46313572716b182321fd065/src/function.cc#L86-L110
Contributions are welcome if you have ideas to improve the
detection/evaluation.
On Fri, Mar 22, 2019 at 1:24 PM jon jon@jonbondy.com 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.
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 thehans@gmail.com 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 jon@jonbondy.com 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.
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 thehans@gmail.com 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 thehans@gmail.com 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 jon@jonbondy.com 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.
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.
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 Torsten.Paul@gmx.de 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org