I have already pointed out that it is hard to write non-trivial 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 2-3 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 ) )

2018-01-26 1:10 GMT-02:00 NateTG nate-openscadforum@pedantic.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.)

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/

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 2-3 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[2ind+1]; // retrieval
function Tbranch(tree,ind) = t[2ind];

By calling those functions, the value insertion coding will be easier and
the code clearer.

2-3 tree is a data abstraction for the user code. The node might be
regarded as a data abstraction for the 2-3 tree data structure.

2018-01-26 17:05 GMT-02:00 doug moen doug@moens.org:

2018-01-26 13:35 GMT-02:00 NateTG nate-openscadforum@pedantic.org:

​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 re​moving from  2-3 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.

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 uses references to reference-counted, 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 nate-openscadforum@pedantic.org wrote:

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.

2018-01-30 21:16 GMT-02:00 doug moen doug@moens.org:

It may be possible to use some purely functional data structures in
OpenSCAD. Unlike the 2-3 tree, these data structures are designed to be
efficient in a language with only immutable objects.

https://en.wikipedia.org/wiki/Purely_functional_data_structure

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 rcmpersiano@gmail.com wrote:

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 2-3 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/

Under my initial hyphotesis that copies are made, an insertion or deletion
from a 2-3 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 2500-30000 elements.

To minimize stack overflows I have used the tail recursive versions:

function treeinsert(tree,value)=
(0==len(tree))?
[value]  :
(treeinsertiterate(tree,value))[1] ;

function treeinsertlisti(tr,list,i)=
(i==0)?
treeinsert(tr,list[0]) :
treeinsertlisti(treeinsert(tr,list[i]),list,i-1)  ;

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]]

2018-01-30 21:59 GMT-02:00 NateTG nate-openscadforum@pedantic.org:

from a 2-3 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:

Where I thought the claim was that a single insertion was O(N^2).

Building a tree from N elements is expected to take O(N log N) time - which
is worse than linear.

Thanks for that info.  I still don't really understand the "this tail
recurses" thing.

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

​
​Yes, I mixed things up.​

I still don't really understand the "this tail

<goog_634797904>
​
https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/User-Defined_Functions_and_Modules#Recursive_functions

​
http://forum.openscad.org/Tail-recursion-td17040.html
http://forum.openscad.org/Tail-recursion-td17040.html

​

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.

I understand what tail recursion is. I'm just not confident about when or how
it gets applied in OpenSCAD.

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/

"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 nate-openscadforum@pedantic.org wrote:

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 C-like
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=i-1, 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.

2018-01-31 16:33 GMT-02:00 doug moen doug@moens.org:

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.

https://en.wikipedia.org/wiki/Tail_call#cite_note-aim-443-1

The rest of the footnotes there are also good.

On Wed, Jan 31, 2018 at 11:57 AM, Torsten Paul Torsten.Paul@gmx.de wrote:

--

Best Regards.
This is unedited.
This message came out of me
via a suboptimal keyboard.

In order to implement generalized tail recursion optimization, you need to
add a compilation pass that compiles the code into an executable form that
is different from the original parse tree. This executable form is a
sequence of instructions. These are traditionally byte codes, but you could
also use a linked list of instruction objects, or an array of pointers to
instruction objects. This is like compiling into abstract machine code.

The interpreter uses a separate stack data structure to store argument
values and local variables for each function call. A linked list of
dynamically allocated stack frame objects is one possibility.

The interpreter is a state machine with a set of registers. You need at
least: a current instruction pointer IP, a current stack frame pointer FP.
After each instruction is executed, these registers are updated. The IP is
updated to the next instruction to be executed. The FP is updated after a
call or return.

Instructions need operands: some way to access the data that is to be
operated on. In a parse tree interpreter, like what OpenSCAD uses, a tree
node like "+" contains child nodes for the left and right operands of "+".
However, in this style of interpreter, an expression like 'A+B' is compiled
into:
evaluate A, store the result
evaluate B, store the result
fetch the A result, fetch the B result, add them, store the result

There are two basic styles that can be used for fetching and storing data:

1. One is a "stack machine", where you are pushing and popping intermediate
   results on the stack. In this style, 'A+B' compiles into:

   • push A on the stack
   • push B on the stack
   • pop 2 values from the stack, add them, push the result on the stack

2. Another style is a "register machine", where there is an array of slots
   indexed by integers that hold values. Each operation has slot indexes
   indicating which slots it should load and store data from. Register
   machines are currently more popular. It seems you can generate faster code,
   and they aren't any more difficult to implement. Even with a stack machine,
   you need a slot array to store local variables.

A?B:C expressions are compiled into an instruction sequence that contains
conditional and unconditional jumps. Like machine code.

In Curv, my stack is a linked list of dynamically allocated stack frame
objects. Each frame contains an array of slots. The number of slots for a
particular function call frame is determined by the compiler. A function
object contains the number of slots needed for a call to that function.

To compile a function call, you first emit instructions to evaluate the
arguments (which are either pushed on the stack, or stored in one or more
slots), then you emit a function-call instruction, which allocates stack
space for the function call, possibly copies the arguments into the new
stack frame, depending on your design, then it sets the FP to point to the
new stack frame and it sets the IP to point to the first instruction of the
function. The old IP needs to be stored somewhere, eg in the return address
field of the new stack frame, so that it can be restored by the return
instruction.

To return from a function call, you execute a return instruction. This
takes the return value and places it somewhere where it can be found by the
function-call instruction that called the current function. You need to
restore the FP to its previous value (pop the current frame off the stack),
and set the IP to the next instruction following the original function
call. Deallocate the current frame, which is no longer needed.

There is also a tail-call instruction. In the general case, you can perform
a tail call to the same function, or to a different function. Suppose that
your stack is a linked list of dynamically allocated frame objects. A
general tail call instruction will create and initialize the new stack
frame, just like regular function call. But then it will set the return
address field of the new stack frame to the same value as the return
address of the current stack frame. Then it destroys the current stack
frame, replacing it with the new stack frame.

Now, your compiler needs a strategy for figuring out when it can safely
replace a regular function-call instruction with a tail-call instruction.

• The body of a function is in tail-position.
• If a let expression is in tail-position, then the body of the let is also
  in tail-position.
• If A?B:C is in tail position, then B and C are also in tail-position.
• These rules for marking an expression as "in tail-position" are applied
  recursively to the parse tree of a function body.
• If a function call is in tail position, then it can be compiled using a
  tail-call instruction.

One caveat. In the style of language interpreter I'm familiar with,
variable and argument references are lexically scoped. In Curv, I compile
variable and argument references into slot indexes, which index into the
slot array of the current stack frame. So the scope of a variable name is
fixed at compile time, before the program is evaluated. This is probably
why the Curv interpreter is so much faster than the OpenSCAD interpreter:
array indexing is faster than hash table lookup. By contrast, OpenSCAD is
dynamically scoped. Variable and argument references are names, and these
names are looked up dynamically during evaluation, which leads to semantics
that are different from lexical scoping. The same variable name node in the
parse tree may have different scopes in different calls to the same
function or module. So you'll have to figure out how to preserve these
dynamic scoping semantics if you implement this style of compiler, and I'm
not sure there are any references to help you, because the dynamic scoping
semantics of OpenSCAD seem utterly unique to me.

On 31 January 2018 at 14:57, Torsten Paul Torsten.Paul@gmx.de wrote:

On 1/31/18, doug moen doug@moens.org wrote:
...

Emacs lisp is another place where dynamic scope is found. This is
considered a mistake by some, and lexical scoping has been added
to recent versions.
https://www.emacswiki.org/emacs/DynamicBindingVsLexicalBinding

I suppose you could index into a global table of slots to
implement dynamic scope in the compiler you describe, but it
would not be an improvement, except perhaps if your goal was
compatibility. Dynamically scoped programs are considerably
harder to reason about than lexically scoped programs. This is
true both for humans and optimizing compilers.

You can get dynamic scope by accident in an interpreter with a
slight change in how you handle the environment.

The best explanation I've seen for this is published here:
http://cs.brown.edu/courses/cs173/2012/book/From_Substitution_to_Environments.html
In Shriram Krishnamurthi's excellent book
Programming Languages: Application and Interpretation

--
sim

Yes, but what I call "dynamic scoping" in OpenSCAD is not the same as
dynamic scoping in Lisp. So I don't think that references to the theory of
Lisp interpreters helps much.

Example 1.

1    a = 0;
2    module m()
3    {
4        function f() = a;
5        x = f();
6        a = 1;
7        y = f();
8        echo(x,y);
9    }
10  m();

Look at line 4. In a lexically scoped language, the variable name 'a' would
statically refer to either the outer definition on line 1, or the inner
definition on line 6. One or the other. But in OpenSCAD the scope of 'a'
seems to be chosen at runtime, and varies dynamically. So the output is:
ECHO: 0,1

Example 2.

1    a = 0;
2    function f() = a;
3    module m()
4    {
5        x = f();
6        a = 1;
7        y = f();
8        echo(x,y);
9    }
10  m();

Here, the output is "ECHO: 0,0". In this case, the variable 'a' is
lexically scoped within the function 'f'. In the previous case, the
variable 'a' was dynamically scoped within the function 'f'.

To me, this looks like a bug. It's as if the intention was to implement
lexical scoping, but the implementation is buggy. Marius has previously
stated that we can't fix this bug in a way that changes the behaviour of
existing programs.

On 1 February 2018 at 11:37, Simeon Veldstra sim@puddle.ca wrote:

Oh, I see, "broken scoping" might be a clearer term perhaps.

The docs pretty clearly discourage reassignment at least, and the
language gives us let.

I was happy to discover OpenSCAD. Despite its warts, it suits my
style of thinking. ImplicitCAD and Ruckus were exciting to
find, but appear to be dead projects. I'm enjoying digging into
Curv, keep up the good work!

I'm quite sure you know more about language design than I do. I
find it a fascinating subject and thought my comments would be of
interest to the list.

On 2/1/18, doug moen doug@moens.org wrote:

--
sim

Thanks, Simeon. You might also want to look at Matt Keeter's libfive. It's
another implicit-function 3D modelling language, based on the Guile dialect
of Scheme. https://github.com/libfive/libfive

On 1 February 2018 at 22:21, Simeon Veldstra sim@puddle.ca wrote:

Torleif: With macOS version 2017.12.23, I get

WARNING: Ignoring unknown variable 'c'.

ECHO: undef

WARNING: Ignoring unknown variable 'c'.

ECHO: undef

On 1 February 2018 at 23:08, TLC123 torleif.ceder@gmail.com wrote:

Torleif: If I add 'c="TOP";' to the beginning of the program, then I get

ECHO: "TOP"
ECHO: "TOP"

which is correct behaviour for lexical scoping.

If I then wrap this entire program in a module, like so:

module top()
{
...
}
top();

then the behaviour doesn't change, so that's lexical scoping inside a
module.

On 1 February 2018 at 23:45, TLC123 torleif.ceder@gmail.com wrote:

Oh wow...
Thanks for the tip!

On 2/1/18, doug moen doug@moens.org wrote:

--
sim

runsun wrote

I did it as an exercise.  I expected there to be a need for a data
structure with search,insert and remove, but I guess people just munge lists
instead.

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

NateTG wrote

Thx Nate. I might find it useful later when doing some geometrical calc.

$  Runsun Pan, PhD $ libs: doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), synwrite ( 2 );   $ tips: Collection of tips on github

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

A 2-3 tree is an efficient balanced tree and it might be helpful to store
geometrical data that should be sorted for fast retrieval. To be useful, a
2-3 tree data structure should store a register containing the relevant
geometrical data besides the sorting key. A simple example of that is the
quicksort method that is found in the OpenSCAD manual [1]. It allows to
sort an array of numbers. However, it is useless to sort a list of points
by its first coordinates a much more useful task. I had to write my own
version.

[1]
https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/List_Comprehensions#Sorting_a_vector

2018-02-12 20:53 GMT-02:00 runsun runsun@gmail.com:

​

Since we don't have first class functions in OpenSCAD, a simple alternative
solution would be to insert arrays in the tree: by convention the sorting
key is the first element of the array and the remaining is something to be
interpreted by the calling code. Like, for instance:

function quick_sort(arr, simple=true) =
!(len(arr)>0) ? [] :
let( pivot  = simple ? arr[floor(len(arr)/2)] :
arr[floor(len(arr)/2)][0],
lesser  = [ for (y = arr) if ( (simple ?  y : y[0])  < pivot ) y ],
equal  = [ for (y = arr) if ( (simple ?  y : y[0]) == pivot ) y ],
greater = [ for (y = arr) if ( (simple ?  y : y[0])  > pivot ) y ]
)
concat( quick_sort(lesser,  simple),
equal,
quick_sort(greater, simple) );

l = [ 5,2,8,0,4,7 ]; // simple list of numbers
echo(quick_sort(l));
// ECHO: [0, 2, 4, 5, 7, 8]
v = [ [-1,2], [-7,[4]], [-9,2,4,5], [-3] ]; // list of non void lists
echo(quick_sort(v, simple=false));
// ECHO: [[-9, 2, 4, 5], [-7, [4]], [-3], [-1, 2]]