In  another thread
http://forum.openscad.org/Simple-polygon-triangulation-tp16755.html  ,
Torsten said:

However, not all recursive functions that match the model "cond ? result :
recurse()" are interpreted to tail recursion by OpenSCAD. For instance:

So, the question is: which expressions cond are allowed in "cond ? result :
recurse()" to get tail recursion?

--
View this message in context: http://forum.openscad.org/Tail-recursion-tp17040.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

On 04/11/2016 07:49 PM, Ronaldo wrote:

Exactly those that match this pattern. The test_all_2() example
does not match, it has a second condition instead of the direct
recursive call.

ciao,
Torsten.

Transcription mistake:  test_all_2 should be written as:

May be I got an answer to my own question. The following function seems to
be a tail recursion:

A few parenthesis made the difference.

--
View this message in context: http://forum.openscad.org/Tail-recursion-tp17040p17042.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

On 04/11/2016 08:11 PM, Ronaldo wrote:

Indeed, as they change the top level expression to the
structure which is currently the only supported case
for tail recursion elimination.

If someone has pointers for how to implement better
solutions, please post those. Searching for this so
far mainly returns documentation about how to use
it.

ciao,
Torsten.

My plan for implementing tail recursion is to compile OpenSCAD into byte
codes, and write a byte code interpreter with an explicitly managed stack.
(Maybe separate data and control stacks.) This should run a lot faster than
the current parse tree interpreter.

While compiling the function 'g', if the compiler detects a tail call to a
user defined function 'f(x)', such that the value returned by 'f(x)' is
immediately returned as the result of 'g', then instead of emitting a CALL
instruction, it instead emits a TAIL_CALL instruction, which basically
fixes up the stack so that the activation record for 'g' is replaced by the
arguments to 'f', and then it jumps to 'f'. As a special case, if 'g'
recursively calls itself in tail position, that is also handled as a jump,
without any stack growth.

I don't know an easy way to implement generalized tail recursion
elimination for a parse tree interpreter. There is a technique called a
'trampoline' that might be applicable, but that's probably more trouble
than it is worth.

On 11 April 2016 at 14:14, Torsten Paul Torsten.Paul@gmx.de wrote:

Ronaldo: test_all_2 does not match the pattern, because the body of the
function is

i >= len(p)
? true
: (! test_one(p,i)
? false
: test_all_2(p, i+1))

The body is X ? Y : Z where neither Y nor Z is a call to test_all_2. In
this case, Z is (! test_one(p,i)
? false
: test_all_2(p, i+1)

On 11 April 2016 at 13:49, Ronaldo rcmpersiano@gmail.com wrote:

doug.moen wrote

I understand that now. But I have another question. The code bellow is an
attempt to write a tail recursion version of quicksort. It seems to follow
the pattern you mentioned:

However, I have two recursive calls in the last line of qs(). Is it really a
tail recursion? How evaluator deal with it?

--
View this message in context: http://forum.openscad.org/Tail-recursion-tp17040p17052.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

The innermost call to qs is not tail recursive, so the stack will grow
while evaluating nested calls to qs. Quicksort is inherently
non-tail-recursive in any language.

On 11 April 2016 at 22:13, Ronaldo rcmpersiano@gmail.com wrote:

On Mon, Apr 11, 2016 at 10:34:28PM -0400, doug moen wrote:

Tail recursion does not always have to happen in the tail.

It depends a bit on your definition of "tail recursion". But Tail
recursion can be said to happen when a function call is followed
immediately by a return-from-this-function.

This can happen in the middle of a function.

In the case of quicksort, there are two recursive calls to
quicksort. The first needs to allocate a stack frame, but the second
one can be optimized to a tail-recursion (i.e. jump (not call) to the
beginning of the function.)

In the implementation below, a concat operation needs to be done after
return from the second quicksort. That prevents tail-recursion. This
happens because the sort is not happening in-place.In a language where
it would happen in-place, like C quicksort can become tail-recursive.

Roger. 

--
** R.E.Wolff@BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    Delftechpark 26 2628 XH  Delft, The Netherlands. KVK: 27239233    **
-- BitWizard writes Linux device drivers for any device you may have! --
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.