
123

I have already pointed out that it is hard to write nontrivial data structures in OpenSCAD. I see two main reasons for that: the only intrinsic data structure in OpenSCAD is list (officially called vector) with very basic operators and any change in a data structure implies in rewriting all the structure because of the lack of variables and assignments in OpenSCAD. Yes, I know that OpenSCAD is not a programming language.
A 23 tree is not a trivial data structure and I suspect its implementation code would be ugly in any programming language. But I think you could improve your code readability by providing a proper set of atomic functions to operate over the subjacent node representation. So, your higher level functions (for insertion for instance) would not be cluttered by operations on the list components of tree nodes. As an example, the expression:
[node[1],[tree,node[1],[node[2],node[3],node[4]]]]
appearing somewhere in addtreetotreenode function definition seems to be more readable (although not always concise) as something like:
let( lval = left_val(node), l2node = left_val(node) ) ...
new_2_leaf( lval, new_2_node( tree, lval, l2node ) )
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Thanks for looking at it. Reading other people's code isn't always the
easiest thing in the world. I'm still finding my feet in this purely
functional approach, so it's not surprising that it's ugly. (TBH, I'm a
little surprised at how easily I got it working.)
> I have already pointed out that it is hard to write nontrivial data
> structures in OpenSCAD. I see two main reasons for that: the only
> intrinsic data structure in OpenSCAD is list (officially called vector)
> with very basic operators and any change in a data structure implies in
> rewriting all the structure because of the lack of variables and
> assignments in OpenSCAD.
A specific question is whether my sense that adding or removing any data
from a structure is always going to involve reconstructing the insert or
remove path, and it seems like the answer to that is yes.
Do you know if OpenSCAD has garbage collection or some other memory
management scheme?

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


As Ronaldo says, "OpenSCAD is not a programming language". It's missing features that would make this kind of programming easier and more comfortable. I don't like calling OpenSCAD a functional programming language, because it's missing many of the features that you expect in a functional language, such as function values.
OpenSCAD uses reference counting for memory management.
You wrote: :(1==len(tree))?
(value==tree[0])?
true
:
false
You could make the code shorter by writing :(1==len(tree))?
value==tree[0]
I don't claim this is easier to understand, but it it is shorter.
This kind of code is hard to read, because of all of the "magic number" indexes: [treenode[0],treenode[1],[treenode[2][0],treenode[2][1],treenode[2][2]],treenode[2][3],[treenode[2][4],treenode[3],treenode[4][1]]]
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


There is no information hiding resource in OpenSCAD. However, the coder can avoid to mix lower and higher level operations by using proper atomic functions for creation, inspecting and information retrieval of data nodes virtually isolating its data representation from data structure operations. I would not call those atomic functions as helper functions.
Nate's treefindvalue() function for instance might have the following much more readable form:
function is_in_tree(tree, value) = let( Lvalue = Lvalue(tree), Rvalue = Rvalue(tree), left = Lbranch(tree), right = Rbranch(tree) ) is_2node(tree)? ( value==Lvalue )  ( (value<Lvalue) && is_in_tree(left, value) )  is_in_tree(right, value) :is_3node(tree)? (value==Lvalue)  ( value==Rvalue )  ( (value<Lvalue) && is_in_tree(left, value) )  ( (value>Rvalue) && is_in_tree(right, value) )  is_in_tree(Cbranch(tree), value) :is_2leaf(tree)? ( value==Lvalue )  ( value==Rvalue ) :is_leaf(tree) && (value==Lvalue) ;
where a bunch of data representation access functions are called. To write and read this code we don't need know where the left branch Lbranch() is stored or how the test is_2node(tree) is performed. The code of is_in_tree may be a bit less efficient than Nate's one but readability, maintainability are prime qualities.
The algorithms for value insertion and removal from a 23 tree require the manipulation of temporary abnormal nodes storing 3 values. So, the node data representation should be able to store that kind of nodes. A set of functions for creation, testing and value retrieval of temporary nodes may be:
// temporary nodes function tnode(v1,v2,v3, t1,t2,t3) = [t1, v1, t2, v2, t3, v3]; // creation function is_temp(t) = (len(t)==6); // testing
function Tvalue(tree,ind) = t[2*ind+1]; // retrieval
function Tbranch(tree,ind) = t[2*ind];
By calling those functions, the value insertion coding will be easier and the code clearer.
23 tree is a data abstraction for the user code. The node might be regarded as a data abstraction for the 23 tree data structure.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Those named indexes is a neat style .
Paired with some selected glue comments it has potential.
And with a helper constructor function it hides the "listness" of the data.
I like it.
// NamedStruct "23TreeNode"
BRANCH1 = 0; // pointer
VALUE1 = 1; // value
BRANCH2 = 2; // pointer
VALUE2 = 3; // value
BRANCH3 = 4; // pointer
//
function new_23TreeNode ( BRANCH1, VALUE1 , BRANCH2, VALUE2, BRANCH3)=
[BRANCH1, VALUE1 , BRANCH2, VALUE2,
BRANCH3];

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


> ... For instance, the element insertion and removing from 23 trees have
order O(log n). However, an analysis of your implementation in OpenSCAD will
show that its order of complexity is O(n2) or worst due to the repeated
structure copies required by any change in it. ...
Does OpenSCAD never use references (so that if there's some variable a, then
b=[a] is going to create a copy of it)?

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


OpenSCAD uses references to referencecounted, immutable values. Multiple variables can point to the same immutable list object. There is no need for OpenSCAD to make copies of lists, since there are no operations for mutating a list. AFAIK; I haven't read all the code in the interpreter.
I don't think there's much point in worrying about this, though. Like Ronaldo says, just use the simplest possible data structure. If this leads to a performance problem, and you want to use a more complicated data structure, you should measure the performance to ensure that the more complicated code is actually faster. OpenSCAD doesn't have the same performance characteristics as conventional languages, so your complicated code might be slower.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


It may be possible to use some purely functional data structures in OpenSCAD. Unlike the 23 tree, these data structures are designed to be efficient in a language with only immutable objects.
OpenSCAD is missing some language features needed by some functional data structures, but maybe this is a starting point.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


> OpenSCAD uses references to referencecounted, immutable values. Multiple
variables can point to the same immutable list object. There is no need for
OpenSCAD to make copies of lists, since there are no operations for mutating
a list. AFAIK; I haven't read all the code in the interpreter.
The 23 tree implementation should only replace the nodes on the insertion
or removal path which should individually take a fixed amount of time. I
don't understand how it will take O( N^2 ) time and would really like to
understand. (Even if OpenSCAD is copying the lists every time, it seems
like it should be at worst O(N (log N)^2).)

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


Under my initial hyphotesis that copies are made, an insertion or deletion from a 23 tree with N element would be O(N). And to build a tree from scratch the time would be O(N^2). It is hard to get good time estimates with the OpenSCAD system but I got worst than linear time building trees by insertion of 250030000 elements.
To minimize stack overflows I have used the tail recursive versions:
function treeinsert(tree,value)= (treeinsertiterate(tree,value))[1] ;
function treeinsertlisti(tr,list,i)= treeinsertlisti(treeinsert(tr,list[i]),list,i1) ;
BTW, your insertion code does not deal well with some sequences having repeated values.
ECHO: foo = [40, 57, 65, 14, 65, 80, 82, 65] ECHO: bar = [[14, 40], 57, [65], 80, [65]]
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


> Under my initial hyphotesis that copies are made, an insertion or deletion
from a 23 tree with N element would be O(N). And to build a tree from
scratch the time would be O(N^2).
Those are both totally plausible to me. I may have misunderstood this:
> For instance, the element insertion and removing from 23 trees have
> order O(log n). However, an analysis of your implementation in OpenSCAD
> will show that its order of complexity is O(n2) or worst due to the
> repeated structure copies required by any change in it.
Where I thought the claim was that a single insertion was O(N^2).
> I got worst than linear time building trees by insertion of 250030000
> elements.
Building a tree from N elements is expected to take O(N log N) time  which
is worse than linear.
> To minimize stack overflows I have used the tail recursive versions:
> ...
> BTW, your insertion code does not deal well with some sequences having
> repeated values.
Thanks for that info. I still don't really understand the "this tail
recurses" thing.

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


>> I still don't really understand the "this tail
>> recurses" thing.
From a language user point of view, it can be ignored.
From an optimization point of view, conventional calls
and returns stack up and grow the stack, but a tail return
can avoid putting a redundant return on the stack.
Another way to think about it is a recursive call can be
a goto, and not grow the stack.


Best Regards.
This is unedited.
This message came out of me
via a suboptimal keyboard.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


I understand what tail recursion is. I'm just not confident about when or how
it gets applied in OpenSCAD.
> From a language user point of view, it can be ignored.
It would be nice if that were true, but the nature of OpenSCAD means that
things can easily get stack constrained. even when they are working
properly. For example, Ronaldo didn't modify the tree insertion function
for some aesthetic reason but rather because stack overflows were a
practical issue.

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


" I understand what tail recursion is. I'm just not confident about when or howit gets applied in OpenSCAD."
The tail recursion optimization is only applied in two very specific circumstances. It is not implemented in a general way.
The first case:
function f(x) = shouldExit ? result : f(...);
Note that there is a tail recursive function call after the :
The second case:
function f(x) = keepGoing ? f(...) : result;
Note that there is a tail recursive function call between ? and :
The body of the function must match one of the two patterns. If you change these patterns in any way (eg, add a 'let' to define local variables), then the pattern no longer matches, and tail recursion optimization is not applied.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Not always it is easy to write a tail recursion qualified to elimination. And sometimes it is possible to avoid the recursion at all using a Clike *for* enabled in a snapshot version. The treeinsertlist(() function, for instance, may be rewritten iteractively as:
function treeinsertlist(tree,list) = [for(i=len(list), tr=tree; i>=0; i=i1, tr = treeinsert(tr,list[i]) ) if(i==0) tr ][0];
I am not an advocate of this form that is not easily grasped, but a complex tail recursion elimination form may be also hard to read.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


> The tail recursion optimization is only applied in two very specific
> circumstances. It is not implemented in a general way.
>
Do you have any pointers to documentation about how to implement tail
recursion or how it's implemented in some language?
I was searching for that some time ago and there's lots of discussion
about how to use tail recursion but not so much about how to actually
implement it.
ciao,
Torsten.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
 Torsten

123
