I just implemented a 23 tree using OpenSCAD functions, and it seems pretty
ugly. I'm wondering if I'm doing something dumb. Here's the script: twothreetree.scad <http://forum.openscad.org/file/t2140/twothreetree.scad>  Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
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:
appearing somewhere in addtreetotreenode function definition seems to be more readable (although not always concise) as something like:
20180126 1:10 GMT02:00 NateTG <[hidden email]>: I just implemented a 23 tree using OpenSCAD functions, and it seems pretty _______________________________________________ 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]]] It would be better to use names, instead of numbers. Ronaldo suggests using helper functions. I tend to use named constants as indexes into lists that actually structures/records, kind of like this: BRANCH1 = 0; VALUE1 = 1; BRANCH2 = 2; VALUE2 = 3; BRANCH3 = 4; [ treenode[BRANCH1], treenode[VALUE1], [ treenode[BRANCH2][BRANCH1], treenode[BRANCH2][VALUE1], treenode[BRANCH2][BRANCH2] ], treenode[BRANCH2][VALUE2], [ treenode[BRANCH2][BRANCH3], treenode[VALUE2], treenode[BRANCH3][VALUE1] ] ] _______________________________________________ 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:
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:
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. 20180126 17:05 GMT02:00 doug moen <[hidden email]>:
_______________________________________________ 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 
In reply to this post by NateTG
My greatest concerns on defining data structures in OpenSCAD language are not the lacking of a garbage collection but the order of complexity. 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. And this is true for any data structure. So, I think there is no point in using complex data structures in OpenSCAD. A simple ordered list is as good as any search tree. _______________________________________________ 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. On 30 January 2018 at 18:05, NateTG <[hidden email]> wrote: > ... For instance, the element insertion and removing from 23 trees have _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
The question is how to build things like Delaunay triangulation when needed. You can't do it without the support of a complex data structure. 20180130 21:16 GMT02:00 doug moen <[hidden email]>:
_______________________________________________ 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. On 30 January 2018 at 18:22, Ronaldo Persiano <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by doug.moen
> 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:
BTW, your insertion code does not deal well with some sequences having repeated values.
20180130 21:59 GMT02:00 NateTG <[hidden email]>: > OpenSCAD uses references to referencecounted, immutable values. Multiple _______________________________________________ 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 
_______________________________________________ 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 how it 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. On 31 January 2018 at 13:22, NateTG <[hidden email]> wrote: I understand what tail recursion is. I'm just not confident about when or how _______________________________________________ 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. 20180131 16:33 GMT02:00 doug moen <[hidden email]>:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by doug.moen
> 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

Free forum by Nabble  Edit this page 