Programming in Functional OpenSCAD

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

Re: Programming in Functional OpenSCAD

togo
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 <[hidden email]> wrote:

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



--
--
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
Reply | Threaded
Open this post in threaded view
|

Re: Programming in Functional OpenSCAD

doug.moen
In reply to this post by tp3
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 <[hidden email]> wrote:
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


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

Re: Programming in Functional OpenSCAD

Simeon Veldstra
On 1/31/18, doug moen <[hidden email]> wrote:
...

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

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

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

Re: Programming in Functional OpenSCAD

doug.moen
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 <[hidden email]> wrote:
On 1/31/18, doug moen <[hidden email]> wrote:
...
> 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.

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

_______________________________________________
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: Programming in Functional OpenSCAD

Simeon Veldstra
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 <[hidden email]> wrote:

> 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 <[hidden email]> wrote:
>
>> On 1/31/18, doug moen <[hidden email]> wrote:
>> ...
>> > 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.
>>
>> 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
>>
>> _______________________________________________
>> OpenSCAD mailing list
>> [hidden email]
>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>


--
sim

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

Re: Programming in Functional OpenSCAD

TLC123
only in the global scope.


a="GAH";

function x(b)=let(c=b) y();
function y()=c;

echo(x(a));
z();
module z(b){c=b; w();}
module w(){echo(c);}




--
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: Programming in Functional OpenSCAD

doug.moen
In reply to this post by Simeon Veldstra
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 <[hidden email]> 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 <[hidden email]> wrote:
> 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 <[hidden email]> wrote:
>
>> On 1/31/18, doug moen <[hidden email]> wrote:
>> ...
>> > 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.
>>
>> 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
>>
>> _______________________________________________
>> OpenSCAD mailing list
>> [hidden email]
>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>


--
sim

_______________________________________________
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: Programming in Functional OpenSCAD

doug.moen
In reply to this post by TLC123
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 <[hidden email]> wrote:
only in the global scope.


a="GAH";

function x(b)=let(c=b) y();
function y()=c;

echo(x(a));
z();
module z(b){c=b; w();}
module w(){echo(c);}




--
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
Reply | Threaded
Open this post in threaded view
|

Re: Programming in Functional OpenSCAD

TLC123
So do I on win7. This to me  indicates that scope is not nesting besides the
global.
 I never had any issues with this as i tend to pass parameters with the
function and i don't try to tricky around no reassign paradigm.

Obviously it would be handy to not pass huge lists down a recursion.
But once again let's remind.  Openscad script is not programming it is cad
markup. There are no variables. Only constants defined  with  evaluated
expressions.  
 



--
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: Programming in Functional OpenSCAD

TLC123
In reply to this post by doug.moen
So do I on win7. This to me indicates that scope is not nesting besides the global. I never had any issues with this as i tend to pass parameters with the function and i don't try to tricky around no reassign paradigm. Obviously it would be handy to not pass huge lists down a recursion. But once again let's remind. Openscad script is not programming it is cad markup. There are no variables. Only constants defined with evaluated expressions.

Sent from the OpenSCAD mailing list archive at Nabble.com.

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

Re: Programming in Functional OpenSCAD

doug.moen
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 <[hidden email]> wrote:
So do I on win7. This to me indicates that scope is not nesting besides the global. I never had any issues with this as i tend to pass parameters with the function and i don't try to tricky around no reassign paradigm. Obviously it would be handy to not pass huge lists down a recursion. But once again let's remind. Openscad script is not programming it is cad markup. There are no variables. Only constants defined with evaluated expressions.

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
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: Programming in Functional OpenSCAD

Simeon Veldstra
In reply to this post by doug.moen
Oh wow...
Thanks for the tip!

On 2/1/18, doug moen <[hidden email]> wrote:

> 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 <[hidden email]> 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 <[hidden email]> wrote:
>> > 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 <[hidden email]> wrote:
>> >
>> >> On 1/31/18, doug moen <[hidden email]> wrote:
>> >> ...
>> >> > 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.
>> >>
>> >> 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
>> >>
>> >> _______________________________________________
>> >> OpenSCAD mailing list
>> >> [hidden email]
>> >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>> >>
>> >
>>
>>
>> --
>> sim
>>
>> _______________________________________________
>> OpenSCAD mailing list
>> [hidden email]
>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>


--
sim

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

Re: Programming in Functional OpenSCAD

runsun
In reply to this post by NateTG
What is the application of a 2-3 tree in geometry, specifically in OpenSCAD?



-----

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

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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: Programming in Functional OpenSCAD

NateTG
runsun wrote
> What is the application of a 2-3 tree in geometry, specifically in
> OpenSCAD?

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/

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

Re: Programming in Functional OpenSCAD

runsun
NateTG 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.

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 ); &nbsp; $ tips: Collection of tips on github

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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: Programming in Functional OpenSCAD

Ronaldo
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.



2018-02-12 20:53 GMT-02:00 runsun <[hidden email]>:
NateTG 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.

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

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

Re: Programming in Functional OpenSCAD

NateTG
Yeah, it would be nice if there were a way to make the tree generic so that
it works with many different comparison functions.



--
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: Programming in Functional OpenSCAD

Ronaldo
Yeah, it would be nice if there were a way to make the tree generic so that
it works with many different comparison functions.

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


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

Re: Programming in Functional OpenSCAD

runsun
@Ronaldo, nice code. It's very fast -- sorting 100,000 pts 10 times cost only
6 sec.  Pulling the 'simple?' check out of the loops, like this:

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

gained a little speed (100,000 x 10 => 5 sec) but i guess even in extreme
use of OpenSCAD it doesn't matter.



-----

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

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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: Programming in Functional OpenSCAD

runsun
Inspired by Ronaldo's code, here is a more generalized quick sort for arrays:
<br/>
<blockquote>
function sortArrs(arrs, by=0)=
(
  !(len(arrs)>0) ? [] :
    let( pivot   = arrs[floor(len(arrs)/2)][by],
           lesser  = [ for (y = arrs) if ( y[by]  < pivot ) y ],                                      
,
           equal   = [ for (y = arrs) if ( y[by] == pivot ) y ] ,
           greater = [ for (y = arrs) if ( y[by]  > pivot ) y ]
       )
      concat( sortArrs(lesser, by),
              equal,
              sortArrs(greater, by)
            )
);</blockquote>

/*
ECHO: [[2.9, 1.9, -2.8], [-2.5, -1.5, -2.9], [-0.1, 2.8, 2.4], [0.9, 1.8,
0.8], [-1, -1.3, -0.8]]

 [[-2.5, -1.5, -2.9]
, [-1, -1.3, -0.8]
, [-0.1, 2.8, 2.4]
, [0.9, 1.8, 0.8]
, [2.9, 1.9, -2.8]]

 [[-2.5, -1.5, -2.9]
, [-1, -1.3, -0.8]
, [0.9, 1.8, 0.8]
, [2.9, 1.9, -2.8]
, [-0.1, 2.8, 2.4]
]

 [[-2.5, -1.5, -2.9]
, [2.9, 1.9, -2.8]
, [-1, -1.3, -0.8]
, [0.9, 1.8, 0.8]
, [-0.1, 2.8, 2.4]]

*/




-----

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

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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
123