Re: [OpenSCAD] function defined by recursion (How not to ...)
It seems as if some of you have never been caught in an infinite loop.
--
View this message in context: http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p13577.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
This is my first post to an openscad dlist ever. I haven't been using
openscad for that long, but I'm just incredibly grateful that it exists. If
I'm ever critical in the future, it's because I've come to depend on this
wonderful tool. OMG openscad is sooooo much better than using the !@#$%#@#@
mouse. OMG OMG OMG. Now that I've got my eternal gratefulness off my chest:
In an imperative language it makes some sense to limit recursion to <small
number>, but in a functional language it is hard to (for instance) find the
minimum value of a list without recursion. Recursion is how you iterate over
lists.
I had this same issue with recursion depth in openscad. I figured out how to
turn my recursion into tail recursion, so I'm all set. Alternatively, I
could have used binary subdivision to keep depth down
function minList(list,start, length) =
(length<=1) ? list[start] : min(minList(start, length/2),
minList(start+length/2, length/2);
this is a little sloppy, but it will actually work and can't recur more than
log_2(len(list)) deep.
I just wanted to make the point that while avoidable, recursion to a depth
equal to the maximum expected number of points in a list isn't a weird thing
to do.
It would be nifty if the manual said something about tail recursion, or
otherwise gave more of a hint on how to get around small recursion limits.
I'd rather see openscad run out of memory and crash than give up at a
recursion depth of 100. 1,000,000 wouldn't even think about crashing on a
modern PC unless the stack is eensy, and it definitely wouldn't be
antisocial. My F6 renders can take a couple of hours.
Here you can imagine me raving again and otherwise wasting bandwidth one
last time about how happy I was to find Openscad. Duuuudes. WTG. etc.
--
View this message in context: http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14079.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Hi John,
To clarify:
In OpenSCAD, recursion depth is currently limited by stack size, not a fixed maximum depth. The exception to this is tail recursion which is converted into a loop, where we cut at 1M iterations (since there is no stack growth) to avoid infinite loops.
Are you saying that 1M is too hard of a limit for your design? I’d love to see practical examples of this :)
Having a better way of reporting and cancelling potentially infinite jobs could be a decent alternative to such a limit.
I would prefer if we didn’t crash or lock up, forcing users to kill the process in these cases.
-Marius
Thanks for getting back to me Marius.
I was getting "recursion detected errors", so I did a search for the
problem. This forum thread seemed to indicate that the non-tail recursion
depth was 100. My function should have been recurring to a depth of about
10,000.
It's possible that my function was recurring deeper due to a bug that got
fixed when I switched to tail recursion. I don't know. It's hard to find
bugs in functions without the proposed fecho function (separate issue). 1M
iterations seems like a fine limit to me. I don't think I'd have time to
render very many 1M point polyhedra. :)
On Wed, Oct 7, 2015 at 1:29 PM, kintel [via OpenSCAD] <
ml-node+s1091067n14085h43@n5.nabble.com> wrote:
Hi John,
To clarify:
In OpenSCAD, recursion depth is currently limited by stack size, not a
fixed maximum depth. The exception to this is tail recursion which is
converted into a loop, where we cut at 1M iterations (since there is no
stack growth) to avoid infinite loops.
Are you saying that 1M is too hard of a limit for your design? I’d love to
see practical examples of this :)
Having a better way of reporting and cancelling potentially infinite jobs
could be a decent alternative to such a limit.
I would prefer if we didn’t crash or lock up, forcing users to kill the
process in these cases.
-Marius
OpenSCAD mailing list
[hidden email] http:///user/SendEmail.jtp?type=node&node=14085&i=0
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
If you reply to this email, your message will be added to the discussion
below:
http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14085.html
To unsubscribe from function defined by recursion (How not to ...), click
here
http://forum.openscad.org/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4299&code=am9obm1kYW5za2luQGdtYWlsLmNvbXw0Mjk5fC0xNzA3MzY2NzM=
.
NAML
http://forum.openscad.org/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml
--
View this message in context: http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14086.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
johnmdanskin wrote
My function should have been recurring to a depth of about 10,000.It's
possible that my function was recurring deeper due to a bug that gotfixed
when I switched to tail recursion. I don't know. It's hard to findbugs in
functions without the proposed fecho function (separate issue).
It may not but a bug but the nature of non-tail recursion, in which when you
set to recur n times, the times it call the function is actually far more n.
Consider this example that calc the !n = 123...*n:
function prod(n)= n<=1?1
: n*prod(n-1);
echo( prod(3) ) ==> 123 = 6
echo( prod(4) ) ==> 123*4 = 24
For case prod(1): calc once
For prod(2):
2) outermost call(n=2) = 1 1) 2prod(1) = 1
--------------------------- ==> #n(2) = 2 ( prod() is
called twice ) prod(3): 3) outermost call (n=3)= 1
2) 3prod(2) ==> #n(2) = 2 1) 2*prod(1) ==> #n(1) = 1
--------------------------- ==> #n(3) = 4 ( prod() is
called 4 times )
That is, when you increase the n from 2 to 3, the times the prod(n) is
called increases from 2 to 4, not 2 to 3. Let's see more:
prod(4): 4) outermost call (n=4)= 1 3) 4*prod(3) ==>
#n(3) = 4 2) 3prod(2) ==> #n(1) = 2 1) 2prod(1) ==> #n(1)
= 1 --------------------------- ==> #n(4) = 8
prod(5): 5) outermost call (n=5)= 1 4) 5prod(4) ==>
#n(3) = 8 3) 4prod(3) ==> #n(3) = 4 2) 3prod(2) ==>
#n(1) = 2 1) 2prod(1) ==> #n(1) = 1
--------------------------- ==> #n(5) = 16
From these we can observe:
- Most of the calls are repetitive. For example, if you do prod(5), the
same prod(2) is calculated 3 times. - When asking a non-tail recursive function to run n steps, it actually
call itself (n-1)^2 times, but not n times;
This means that your function is actually called (10,000-1)^2 times when
you set the step to 10,000. Maybe that's where the problem is.
$ Runsun Pan, PhD
$ libs: doctest , faces ( git ), offline doc ( git ),runscad.py( 1 , 2 , git );
$ tips: hash( 1 , 2 ), sweep , var , lerp , animGif
--
View this message in context: http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14088.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
When asking a non-tail recursive function to run n steps, it actually
call itself (n-1)^2 times, but not n times;
I don't see why that is the case. The function will recurse until n = 1. At
that point you have n stack frames on the stack. The top one returns 1, the
one below it returns 2 * 1, next one 3 * 2 and so on. Why do you think it
gets called more than once for a particular n?
On 8 October 2015 at 06:08, runsun runsun@gmail.com wrote:
johnmdanskin wrote
My function should have been recurring to a depth of about 10,000. It's
possible that my function was recurring deeper due to a bug that got fixed
when I switched to tail recursion. I don't know. It's hard to find bugs in
functions without the proposed fecho function (separate issue).
It may not but a bug but the nature of non-tail recursion, in which when
you set to recur n times, the times it call the function is actually far
more n. Consider this example that calc the !n = 123...*n:
function prod(n)= n<=1?1
: n*prod(n-1);
echo( prod(3) ) ==> 123 = 6
echo( prod(4) ) ==> 123*4 = 24
For case prod(1): calc once
For prod(2):
2) outermost call(n=2) = 1
1) 2*prod(1) = 1
---------------------------
==> #n(2) = 2 ( prod() is called twice )
prod(3):
3) outermost call (n=3)= 1
2) 3*prod(2) ==> #n(2) = 2
1) 2*prod(1) ==> #n(1) = 1
---------------------------
==> #n(3) = 4 ( prod() is called 4 times )
That is, when you increase the n from 2 to 3, the times the prod(n) is
called increases from 2 to 4, not 2 to 3. Let's see more:
prod(4):
4) outermost call (n=4)= 1
3) 4*prod(3) ==> #n(3) = 4
2) 3*prod(2) ==> #n(1) = 2
1) 2*prod(1) ==> #n(1) = 1
---------------------------
==> #n(4) = 8
prod(5):
5) outermost call (n=5)= 1
4) 5*prod(4) ==> #n(3) = 8
3) 4*prod(3) ==> #n(3) = 4
2) 3*prod(2) ==> #n(1) = 2
1) 2*prod(1) ==> #n(1) = 1
---------------------------
==> #n(5) = 16
From these we can observe:
- Most of the calls are repetitive. For example, if you do prod(5), the
same prod(2) is calculated 3 times. - When asking a non-tail recursive function to run n steps, it
actually call itself (n-1)^2 times, but not n times;
This means that your function is actually called (10,000-1)^2 times when
you set the step to 10,000. Maybe that's where the problem is.
$ http://forum.openscad.org/mailing_list/MailingListOptions.jtp?forum=1 Runsun
Pan, PhD
$ libs: doctest https://github.com/runsun/openscad_doctest, faces
http://forum.openscad.org/A-faces-function-for-simple-polyhedrons-td12809.html
(git https://github.com/runsun/faces.scad), offline doc
http://forum.openscad.org/Use-openscad-offliner-for-offline-documentation-td13096.html
(git https://github.com/runsun/openscad_offliner),runscad.py(1
http://forum.openscad.org/Animating-gif-with-3D-rotation-tp14011p14029.html
,2 http://forum.openscad.org/Symmetrical-Rotation-tp14062p14075.html,git
https://gist.github.com/runsun/995250a8002386ab9abc);
$ tips: hash(1
http://forum.openscad.org/parameterized-models-td8303.html#a8306,2
http://forum.openscad.org/Can-I-get-some-code-review-up-in-here-tp12341p12355.html
),sweep http://forum.openscad.org/Two-annoyances-td12935i20.html#a13110,
var
http://forum.openscad.org/Ignoring-unknown-variable-issue-tp13156p13321.html
,lerp
http://forum.openscad.org/Irregular-mesh-generated-tp13765p13779.html,
animGif
http://forum.openscad.org/Animating-gif-with-3D-rotation-tp14011.html
View this message in context: Re: function defined by recursion (How not
to ...)
http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14088.html
Sent from the OpenSCAD mailing list archive http://forum.openscad.org/
at Nabble.com.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
You are right, nophead. I was thinking too much and fall into my own trap.
Thx for pointing that out.
$ Runsun Pan, PhD
$ libs: doctest , faces ( git ), offline doc ( git ),runscad.py( 1 , 2 , git );
$ tips: hash( 1 , 2 ), sweep , var , lerp , animGif
--
View this message in context: http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14091.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
A small change to the prod( ) to prove how wrong I was:
function prod(n)=
(
n<=1?"1"
: str("n=",n, ", ", prod(n-1)) // return a string
);
echo( prod(5) ); //==> "n=5, n=4, n=3, n=2, 1"
A trick similar like this is what I use often to debug a recursive function.
$ Runsun Pan, PhD
$ libs: doctest , faces ( git ), offline doc ( git ),runscad.py( 1 , 2 , git );
$ tips: hash( 1 , 2 ), sweep , var , lerp , animGif
--
View this message in context: http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14092.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
More or less for fun, here is the tail recursive version that finds the min
value in a specified dimension (dI=dimension index) in a list of points.
There is a non-recursive wrapper.
function minDimPtsTail(pts, end, minSoFar, dI, index)=
(index < end) ?
minDimPtsTail(pts, end, min(minSoFar, pts[index][dI]), dI, index + 1) :
minSoFar;
function minDimPts(pts, dI, index=0)=
minDimPtsTail(pts, len(pts), pts[index][dI], dI, index+1);
On Thu, Oct 8, 2015 at 10:41 AM, runsun [via OpenSCAD] <
ml-node+s1091067n14092h60@n5.nabble.com> wrote:
A small change to the prod( ) to prove how wrong I was:
function prod(n)=
(
n<=1?"1"
: str("n=",n, ", ", prod(n-1)) // return a string
);
echo( prod(5) ); //==> "n=5, n=4, n=3, n=2, 1"
A trick similar like this is what I use often to debug a recursive
function.
$ http://forum.openscad.org/mailing_list/MailingListOptions.jtp?forum=1 Runsun
Pan, PhD
$ libs: doctest https://github.com/runsun/openscad_doctest, faces
http://forum.openscad.org/A-faces-function-for-simple-polyhedrons-td12809.html
(git https://github.com/runsun/faces.scad), offline doc
http://forum.openscad.org/Use-openscad-offliner-for-offline-documentation-td13096.html
(git https://github.com/runsun/openscad_offliner),runscad.py(1
http://forum.openscad.org/Animating-gif-with-3D-rotation-tp14011p14029.html
,2 http://forum.openscad.org/Symmetrical-Rotation-tp14062p14075.html,git
https://gist.github.com/runsun/995250a8002386ab9abc);
$ tips: hash(1
http://forum.openscad.org/parameterized-models-td8303.html#a8306,2
http://forum.openscad.org/Can-I-get-some-code-review-up-in-here-tp12341p12355.html
),sweep http://forum.openscad.org/Two-annoyances-td12935i20.html#a13110,
var
http://forum.openscad.org/Ignoring-unknown-variable-issue-tp13156p13321.html
,lerp
http://forum.openscad.org/Irregular-mesh-generated-tp13765p13779.html,
animGif
http://forum.openscad.org/Animating-gif-with-3D-rotation-tp14011.html
If you reply to this email, your message will be added to the discussion
below:
http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14092.html
To unsubscribe from function defined by recursion (How not to ...), click
here
http://forum.openscad.org/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4299&code=am9obm1kYW5za2luQGdtYWlsLmNvbXw0Mjk5fC0xNzA3MzY2NzM=
.
NAML
http://forum.openscad.org/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml
--
View this message in context: http://forum.openscad.org/function-defined-by-recursion-How-not-to-tp4299p14093.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On Oct 7, 2015, at 13:53 PM, johnmdanskin johnmdanskin@gmail.com wrote:
This forum thread seemed to indicate that the non-tail recursion depth was 100. My function should have been recurring to a depth of about 10,000.
We recently lifted the recursion limitation (2015.03), so some old discussion are not valid any longer.
-Marius