recursion limit on concat()

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

recursion limit on concat()

kitwallace
I have a function for generating a sequence of points from an L-System
string, such as might be used to define a Dragon curve.

The function itself is tail-recursive but blows up on recursion calling
concat()  -  it fails with list ps length somewhere between 2k and 4k

Anyone able to suggest a work-around?

function string_to_points(s,step=1,angle=90,pos=[0,0,0],dir=0,i=0,ps=[]) =
    i == len(s)
      ? concat([pos],ps)
      : let(c=s[i])
        let(newpos =
          c=="F" ||c=="A" || c=="B"
            ? pos + step*[cos(dir), sin(dir)]
            : pos)
        let(newdir =
            c=="+"
             ? dir + angle
            : c=="-"
              ? dir - angle
              : dir)
       
        string_to_points(s,step,angle,newpos,newdir,i+1,concat([pos],ps))
     ;

Kit



--
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: recursion limit on concat()

tp3
On 14.10.19 15:07, kitwallace wrote:
> Anyone able to suggest a work-around?

Could you please try with the nightly build? I believe it
should be able to do tail recursion elimination with this
code, thanks to
https://github.com/openscad/openscad/pull/3020

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: recursion limit on concat()

Ronaldo
In reply to this post by kitwallace
On, 14.10.2019, 13:59, kitwallace <[hidden email]> wrote:
Anyone able to suggest a work-around?

With the let() clauses of your code, no tail recursion elimination will be done by older OpenSCAD versions.
An alternative to Torsten Paul's suggestion is to eliminate the let() clauses from your code.
Something like:

function string_to_points(s,step=1,angle=90,pos=[0,0,0],dir=0,i=0,ps=[]) =
    i == len(s)
      ? concat([pos],ps)
      : string_to_points(s,
                         step,
                         angle,
                         s[i]=="F" ||s[i]=="A" || s[i]=="B" // newpos
                           ? pos + step*[cos(dir), sin(dir)]
                           : pos,
                         s[i]=="+"                          // newdir
                           ? dir + angle
                           : s[i]=="-"
                              ? dir - angle
                              : dir,
                        i+1,
                        concat([pos],ps) )
     ;

I haven't tested this code.



_______________________________________________
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 limit on concat()

kitwallace
Ronaldo, sadly, that code throws the same error on version 2019-05

Torsten, I'm not quite up with using the nighlies but great to see that tail
recursion is now handling this case -  I will wait for the next development
snapshot  - I could supply the code as a test case if its of interest

Kit



--
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: recursion limit on concat()

Ronaldo

Ronaldo, sadly, that code throws the same error on version 2019-05

That is surprising! Anyway, as another alternative, you may express your function iteractively instead:

function points_from_string(s,step=1,angle=90,pos=[0,0,0],dir=0) =
  [for( i  = 0,
        ps = [pos];

        i <= len(s);

        c   = s[i],
        pos = c=="F" ||c=="A" || c=="B"
               ? pos + step*[cos(dir), sin(dir)]
               : pos,
        dir = c=="+"  
              ? dir + angle
              : c=="-"
                ? dir - angle
                : dir,
        ps  = concat([pos], ps),
        i   = i+1 )
      if(i==len(s)) each ps ];
     
s = "FA+BA-FB";
echo(string_to_points(s));
echo(points_from_string(s));

_______________________________________________
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 limit on concat()

jschobben
Just to make things a bit less mysterious, the reason why 2019.05 and before
don't do tail recursion in Ronaldo's recursive example, is that the old
implementation requires exactly one branch of the ternary to be a function
call. But both branches are function calls: "concat" and "string_to_points".

A hack-around can be to replace "? concat([pos],ps)" with "? assert(true)
concat([pos],ps)", or something similarly silly (and note that the "assert"
function is not present in the 2015 versions). Iteratively is probably the
way to go here :)



--
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: recursion limit on concat()

kitwallace
Well blow me! I've never seen that iterative style before. Certainly a viable
workaround -although I feel a bit - you know - dirty :)

<http://forum.openscad.org/file/t229/dragon-13.jpg>

Dragon curve after 13 iterations

Actually my original code was flawed because it added duplicate points but
easily fixed.

 L-system code with examples is here
https://github.com/KitWallace/openscad/blob/master/tiling/lsystem.scad

Thanks guys

Kit



--
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: recursion limit on concat()

adrianv
In reply to this post by Ronaldo
That is interesting.  So by putting the variables inside the for loop it is
possible to update variable values with dependency on the last iteration?  

I compared run time performance and the run time of the iterative solution
is not faster than the tail recursive one (using the "assert" hack).  
That's sort of disappointing.  




--
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: recursion limit on concat()

tp3
On 15.10.19 02:34, adrianv wrote:
> That is interesting.  So by putting the variables inside
> the for loop it is possible to update variable values with
> dependency on the last iteration?

No, each iteration has a new variable scope just as with
recursion. See the manual for what the recursive call
looks like.

> I compared run time performance and the run time of the
> iterative solution is not faster than the tail recursive
> one (using the "assert" hack). That's sort of disappointing.

How could it be faster? The resulting evaluation is exactly
the same.

ciao,
  Torsten.

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

Re: recursion limit on concat()

tp3
In reply to this post by kitwallace
On 14.10.19 16:55, kitwallace wrote:
> Torsten, I'm not quite up with using the nighlies but> great to see that tail recursion is now handling this
> case -  I will wait for the next development snapshot
> I could supply the code as a test case if its of interest

Yes, that would be nice. I suspect that code did not get
much real world testing so far, so throwing some bigger
examples at it would be interesting.

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: recursion limit on concat()

kitwallace

The (corrected and as a result simpler) recursive version of this function
is used in this version of the  l-system code

https://github.com/KitWallace/openscad/blob/master/tiling/lsystem-recursive.scad

The Hilbert curve fails at k=5



--
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: recursion limit on concat()

Ronaldo
 kitwallace <[hidden email]> wrote:

The (corrected and as a result simpler) recursive version of this function
is used in this version of the  l-system code

The last version you referred defines a string_to_points() function which still is unable to have the tail recursion eliminated. 
Applying your correction to my alternative recursion version, it becomes:

function string_to_points(s,step=1,angle=90,pos=[0,0,0],dir=0,i=0,ps=[]) =
    i == len(s)
      ? ps
      : string_to_points(s,
                         step,
                         angle,
                         s[i]=="F" ||s[i]=="A" || s[i]=="B" // newpos
                           ? pos + step*[cos(dir), sin(dir)]
                           : pos,
                         s[i]=="+"                          // newdir
                           ? dir + angle
                           : s[i]=="-"
                              ? dir - angle
                              : dir,
                        i+1,
                        concat([pos],ps) );

And now it will be eligible to tail recursion elimination.

With that correction, the iterative version also gets simpler and don't need any explicit concat() (neither 'each'):

function string_to_points(s,step=1,angle=90,pos=[0,0,0],dir=0) =
  [for( i  = 0;

        i <= len(s);

        c   = s[i],
        pos = c=="F" ||c=="A" || c=="B"
               ? pos + step*[cos(dir), sin(dir)]
               : pos,
        dir = c=="+"  
              ? dir + angle
              : c=="-"
                ? dir - angle
                : dir,
        i   = i+1 )
       pos ];

The Hilbert curve fails at k=5
 
This failure is due to something else: the 'for' in module path() has more then 9999 elements. This is an arbitrary (and low) limit in OpenSCAD range 'for's.
As an workaround, you may consider the following code with two nested 'for' meant to 'cheat' the limit rule:

module path(points,width,closed=false) {
  r=width/2;
  for (j=[0:len(points)/1000]) { // this { brace pair is
 mandatory  
   for(i=[0:min(999,len(points)-2-1000*j)]) {
    hull() {    
        translate(points[1000*j+i]) circle(r);
        translate(points[1000*j+i+1]) circle(r);
    }    
   }
  }
  if (closed) {
    hull() {    
        translate(points[len(points)-1]) circle(r);
        translate(points[0]) circle(r);
    }
  }
};


It should work up to 999999 elements in 'points'.

Now, Hilbert curve works with k=6 which has 13651 points and with the 54611 points generated when k=7.





_______________________________________________
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 limit on concat()

kitwallace

Re the recusion example - I posted it at Torsten's request that so that it
could be used as a test case for the enhancement which I believe should
handle that case.  

The correction I made was to concatenate only new points and I couldnt get
that to work with your inlined version - maybe didnt try hard enough!

Re the for range limit, i posted separately about that and the workaround I
came up with:

for (i=to_n(len(points)-2))

where

function to_n(n) = [for (i=0;i<=n;i=i+1) i];



--
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: recursion limit on concat()

tp3
On 15.10.19 16:56, kitwallace wrote:
> Re the recusion example - I posted it at Torsten's
> request that so that it could be used as a test case
> for the enhancement which I believe should handle
> that case.

Thanks for that, I can confirm it works as expected. The
nightly does not abort with stack overflow so the tail
recursion elimination works nicely.

With the range workaround it successfully generates the
design with k=8.

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: recursion limit on concat()

thehans
Hi kitwallace, I also have an L-system implementation which I've posted about previously on the list: http://forum.openscad.org/L-systems-demo-Fractal-designs-interpreter-performance-stress-testing-tp23295p25927.html

The latest revision is here:

I spent a lot of time optimizing this code (and even made changes to OpenSCAD to support recursion more efficiently specifically because of it).  It's pretty good with high iterations.









On Tue, Oct 15, 2019 at 10:23 AM Torsten Paul <[hidden email]> wrote:
On 15.10.19 16:56, kitwallace wrote:
> Re the recusion example - I posted it at Torsten's
> request that so that it could be used as a test case
> for the enhancement which I believe should handle
> that case.

Thanks for that, I can confirm it works as expected. The
nightly does not abort with stack overflow so the tail
recursion elimination works nicely.

With the range workaround it successfully generates the
design with k=8.

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: recursion limit on concat()

kitwallace
Hi thehans

Thanks for the pointer - sorry I missed your work earlier - my L-system
doesn't handle moves nor pop and push so that's very useful.  My code
generates a list of points first, then the curve or a polygon as a separete
step because I'm particularly interested in fractals which tesselate - like
the 5-rep-tile  ["5-rep-tile", "F-F-F-F-", [["F", "F+F-F"]], 90] and
terdragon boundary ["Terdragon boundary", "A-B--A-B--", [["A","A+B"],
["B","A-B"]],  60]. I like your handling of F synonyms and will steal that.

Kit  




--
Sent from: http://forum.openscad.org/

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