TP
Torsten Paul
Mon, Oct 14, 2019 1:05 PM
On 14.10.19 15:07, kitwallace wrote:
Anyone able to suggest a work-around?
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.
K
kitwallace
Mon, Oct 14, 2019 1:07 PM
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/
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/
RP
Ronaldo Persiano
Mon, Oct 14, 2019 1:37 PM
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.
On, 14.10.2019, 13:59, kitwallace <kit.wallace@gmail.com> 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.
K
kitwallace
Mon, Oct 14, 2019 2:55 PM
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/
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/
RP
Ronaldo Persiano
Mon, Oct 14, 2019 7:50 PM
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));
> 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));
J
jschobben
Mon, Oct 14, 2019 9:16 PM
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/
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/
K
kitwallace
Mon, Oct 14, 2019 10:56 PM
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/
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/
TP
Torsten Paul
Tue, Oct 15, 2019 12:30 AM
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.
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.
A
adrianv
Tue, Oct 15, 2019 12:34 AM
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/
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/
TP
Torsten Paul
Tue, Oct 15, 2019 12:35 AM
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.
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.
