Recursion issue

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

Recursion issue

jceddy
This post was updated on .
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Recursion issue

MichaelAtOz
Administrator
This post was updated on .
jceddy wrote
So I have a module that iterates over commands in a list and executes them one by one. As each command is executed, there is state that can be modified by the command. The procedural approach to this is straightforward:

module DoStuff(state, commands) {
  for(i = [0 : len(commands) - 1]) {
    state = DoCommand(state, commands[i]);
  }
}

Obviously, this doesn't work in OpenSCAD, since the state "variable" is immutable. So, we switch to recursion:

module DoStuff(state, commands, step = 0) {
  if(step < len(commands)) {
    DoStuff(DoCommand(state, commands[i]), commands, step + 1);
  }
}

This works just fine...until the list of commands is over 1000 or so, then we get the "Recursion detected calling module" error.

Is there any trick I can pull to get around this limitation?
You seem to have unsubscribed, click the link at the top of the page. Edit/ Click 'OpenSCAD' then you will see the subscription link /edit
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain;
to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.
Reply | Threaded
Open this post in threaded view
|

Re: Recursion issue

Ronaldo
Tail recursion elimination is provided just to functions and you can't benefit of it in modules. But your module seems to want just the new state to do something else. So you can compute the sequence of state changes in a list and process it in your module. To generate the state sequence use tail elimination recursion which has a far greater limit. This could be a general scheme:

module DoStuff(state, commands) {
   states = GenStates(state, commands);
   for(i = [0 : len(commands) - 1]) {
     /* do whatever you want with states[i] */
   }
 }

function GenStates(state, commands, stlist=[]) =
    len(stlist)==len(commands) ?
        stlist:
        GenStates(DoCommands(state,commands[i]), commands, concat(stlist, [DoCommands(state,commands[i])]));


But there is something odd here with recursive modules. I've been testing the following simple code:

n = 400;
rec(n);
module rec(n,a)
    if(n==0) { if(a==undef) echo("undef"); else echo(a); }
    else { rec(n-1,a); }


When I set n=400, the console displays ECHO: "undef" and 1 sec. after the process end log and time. The OpenSCAD process required 370Mb to run. When I set n=600, the process takes 6sec. but the display of the echo output is instantaneous and the memory requirements raised after that to 1.2Gb! When I set n=1000, the echo was still instantaneous but the time and memory kept going up until gave up and killed the process when the memory requirements was more then 4Gb.

The same results are observed if the argument 'a' is set in the rec() call: the echo is instantaneous and correct. That smells as a bug.

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

Re: Recursion issue

MichaelAtOz
Administrator
Have a look at the CSG tree.
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain;
to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.
Reply | Threaded
Open this post in threaded view
|

Re: Recursion issue

Ronaldo
2017-03-14 22:06 GMT-03:00 MichaelAtOz <[hidden email]>:
Have a look at the CSG tree.

Well, it is a big tree... with no echo(). Is the tree built after the echo output? Or is the echo output a result of the tree evaluation?



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

Re: Recursion issue

MichaelAtOz
Administrator
As I understand it, compile builds the tree, and echo()'s as it is doing so & doing all the calculations etc, then preview/render evaluates the tree.
It could probably be optimised to drop empty groups, but that would be a very low hit rate in real life.
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain;
to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.
Reply | Threaded
Open this post in threaded view
|

Re: Recursion issue

nophead
It is amazing how long it takes CGAL to evaluate empty groups when you press F6.The implicit union of lots of completely empty sets. How can that be so slow? We can't even blame it on its rational number maths as there are no numbers, no vertices, no edges, no facets.

And how does it use up hundreds of megabytes representing empty sets?

On 15 March 2017 at 03:15, MichaelAtOz <[hidden email]> wrote:
As I understand it, compile builds the tree, and echo()'s as it is doing so &
doing all the calculations etc, then preview/render evaluates the tree.
It could probably be optimised to drop empty groups, but that would be a
very low hit rate in real life.



-----
Admin - PM me if you need anything, or if I've done something stupid...

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
View this message in context: http://forum.openscad.org/Recursion-issue-tp20882p20909.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
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: Recursion issue

Ronaldo


2017-03-15 5:20 GMT-03:00 nop head <[hidden email]>:
It is amazing how long it takes CGAL to evaluate empty groups when you press F6.The implicit union of lots of completely empty sets. How can that be so slow? We can't even blame it on its rational number maths as there are no numbers, no vertices, no edges, no facets.

And how does it use up hundreds of megabytes representing empty sets?


In my incomplete understanding, CGAL can't be blamed as it is OpenSCAD responsability to build the tree operands and operators for CGAL operation. As well as it is OpenSCAD responsible for keeping reserved all this megabytes in cache for nothing except slowing down the machine.

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