Reversing a Linked List using Recursion

[Bilal]

Hi everyone,
I am a bit confused about using recursion with linked list. Below is the code that I ran which works perfectly (as shown in output) but somehow is confusing for me.

Let's say we have a list {1,2,3,4}. When RecursiveReverse(&rest) is called for 1, in Line 9 rest is set to 2. similarly when RecursiveReverse(&rest) is called for 2, in Line 9 rest is set to 3. Then why in Line 25 rest is always 4 also shown in the output? I used printf statements to trace the code/recursion operation.

Please help me figure it out. thanks.
-Bilal


C++ Code:
----------------------------------------------
1 RecursiveReverse(Node **headRef)
2 {
3 // Base case
4 if(*headRef == NULL)
5 return;
6
7 Node *first = *headRef;
8
9 Node *rest = (*headRef)->next;
10
11 if(rest == NULL)
12 {
13 printf("-------------------------------\n");
14 return;
15 }
16 printf("1st CALL: rest is %d \n",rest->data);
17
18 recursiveReverse(&rest);
19
20 first->next->next = first;
21
22 first->next = NULL;
23 printf("2nd CALL: rest is %d \n",rest->data);
24 // rest always point to the last
25 *headRef = rest;
26 }
----------------------------------------------
Output:
1st CALL: rest is 2
1st CALL: rest is 3
1st CALL: rest is 4
--------------------
2nd CALL: rest is 4
2nd CALL: rest is 4 //How? Shouldn't be 3?
2nd CALL: rest is 4 //How? Shouldn't be 2?

[Ben Bacarisse]

Bilal <bilal...@googlemail.com> writes:

> I am a bit confused about using recursion with linked list. Below is
> the code that I ran which works perfectly (as shown in output) but
> somehow is confusing for me.
>
> Let's say we have a list {1,2,3,4}. When RecursiveReverse(&rest) is
> called for 1, in Line 9 rest is set to 2. similarly when
> RecursiveReverse(&rest) is called for 2, in Line 9 rest is set to
> 3. Then why in Line 25 rest is always 4 also shown in the output?

Because rest changes as a result of the call on line 18 -- what it was
on line 9 (and at the printf call on line 16) is not the same as what it
has on line 23.

> C++ Code:

Not quute:

> ----------------------------------------------
> 1 RecursiveReverse(Node **headRef)
> 2 {
> 3 // Base case
> 4 if(*headRef == NULL)
> 5 return;
> 6
> 7 Node *first = *headRef;
> 8
> 9 Node *rest = (*headRef)->next;
> 10
> 11 if(rest == NULL)
> 12 {
> 13 printf("-------------------------------\n");
> 14 return;
> 15 }
> 16 printf("1st CALL: rest is %d \n",rest->data);
> 17
> 18 recursiveReverse(&rest);

Is this supposed to be RecursiveReverse? Make sure you cut and paste
code so readers know that a looking at the real thing!

> 19
> 20 first->next->next = first;
> 21
> 22 first->next = NULL;
> 23 printf("2nd CALL: rest is %d \n",rest->data);
> 24 // rest always point to the last
> 25 *headRef = rest;
> 26 }

<snip>
--
Ben.

[Alf P. Steinbach]

On 16-Jun-17 9:12 AM, Bilal wrote:
> Hi everyone, I am a bit confused about using recursion with linked
> list. Below is the code that I ran which works perfectly (as shown in
> output) but somehow is confusing for me.
>
> Let's say we have a list {1,2,3,4}. When RecursiveReverse(&rest) is
> called for 1, in Line 9 rest is set to 2. similarly when
> RecursiveReverse(&rest) is called for 2, in Line 9 rest is set to 3.
> Then why in Line 25 rest is always 4 also shown in the output? I used
> printf statements to trace the code/recursion operation.
>

Well, to understand this code I first cleaned it up and placed it in a
complete little program:


-----------------------------------------------------------------------
struct Node
{
int value;
Node* next;
};

void recursive_reverse( Node **head_ref )
{
if( *head_ref == nullptr ) { return; }

Node* first = *head_ref;
Node* rest = (*head_ref)->next;

if( rest == nullptr ) { return; }

recursive_reverse( &rest );

first->next->next = first;

first->next = nullptr;
*head_ref = rest;
}

#include <iostream>
using namespace std;

void display( Node const* const p_list )
{
for( auto p = p_list; p; p = p->next )
{
cout << p->value << ' ';
}
cout << endl;
}
auto main() -> int
{
Node* list = new Node{ 1 };
Node* p = list;
for( int i = 2; i <= 4; ++i ) { p->next = new Node{ i }; p = p->next; }
display( list );
recursive_reverse( &list );
display( list );
}
-----------------------------------------------------------------------


This proved that the code worked (which I was a bit skeptical about), so
I looked closer at it.

Now a key feature that makes it harder than necessary to understand is
that it takes a pointer to pointer argument in order to /modify/ that
original first-node pointer.

Instead just make a function that returns the new pointer to first node.
That's in general a much better way to communicate a value back to the
caller. Hm, I need a function result, what should I use? Aha! A C++
function result!

Another complicating feature is that it returns for invalid argument, in
every recursive call, as if that could happen.

Instead it should just, if that's at all deemed necessary, `assert` that
the argument is valid.


-----------------------------------------------------------------------
struct Node
{
int value;
Node* next;
};

namespace impl {

// Returns pointer to first node in the reversed list:
auto recursively_reversed( Node* const first )
-> Node*
{
Node* const rest = first->next;
if( rest == nullptr ) { return first; }
Node* const new_first = recursively_reversed( rest );

first->next->next = first;

first->next = nullptr;

return new_first;
}

} // namespace impl

auto reversed( Node* const list )
-> Node*
{
if( list == nullptr)
{
return nullptr;
}
return impl::recursively_reversed( list );
}

#include <iostream>
using namespace std;

void display( Node const* const p_list )
{
for( auto p = p_list; p; p = p->next )
{
cout << p->value << ' ';
}
cout << endl;
}
auto main() -> int
{
Node* list = new Node{ 1 };
Node* p = list;
for( int i = 2; i <= 4; ++i ) { p->next = new Node{ i }; p = p->next; }
display( list );
list = reversed( list );
display( list );
}
-----------------------------------------------------------------------

I'm not sure of a pattern name for the kind of restructuring I did here.

I guess it's something to do with delegation and single responsibility.

Anyway, in this tidied up code, after impl::recursively_reversed has
called itself to reverse the rest of the list, it changes the next
pointer in the previously second node, now the last node in the reversed
rest of the list, to point to the former first node, which now is last.

That's it, essentially.

Tip: where you really need an in/out-argument, use a C++ reference
rather than e.g. pointer to pointer.


Cheers & hth.,

- Alf

[Mr Flibble]

On 16/06/2017 09:45, Alf P. Steinbach wrote:
> using namespace std;

Egregious.

> auto main() -> int

Egregious OCD.

/Flibble

[Tim Rentsch]

Bilal <bilal...@googlemail.com> writes:

> I am a bit confused about using recursion with linked list. Below

> is the code [...]

The function you wrote has a recursive call "in the middle" of
the function body. That is, the function body does more work
after the recursive call is done, rather than just returning the
result of a recursive call (which would need to be a different
call).

In cases like this, where the depth of recursion might be very
large (what if we have a list with 1,000,000 elements in it?),
it's important to write such functions so any recursive call is a
tail call (usually called tail recursion). Often such function
bodies will be optimized during compilation so recursive calls
are turned into loops rather than calls. Here is a short example
of how to implement list reversal using tail recursion:

typedef struct list_node *List;

struct list_node {
List next;
char value;
};

static List
reverse_onto( List s, List r ){
List t;
return s ? t = s->next, s->next = r, reverse_onto( t, s ) : r;
}

void
reverse( List &s ){
s = reverse_onto( s, 0 );
}

Look at the '?' branch of the conditional expression, which is
taken when 's' is non-null. Notice how the last thing done in
this case, and the value returned from the function, is the
result of the recursive call to reverse_onto().

When 's' is null, the return value is just 'r', the list we
are reversing "onto".

Here is what reverse() compiles to under gcc -Os (minus some
lines that have unimportant assembly noise):

_Z7reverseRP9list_node:
movq (%rdi), %rax
xorl %edx, %edx
.L15:
testq %rax, %rax
je .L14
movq (%rax), %rcx
movq %rdx, (%rax)
movq %rax, %rdx
movq %rcx, %rax
jmp .L15
.L14:
movq %rdx, (%rdi)
ret

Using tail recursion has given us a nice compact loop to effect
list reversal.

Do you understand how the list reversal functions shown
above work, or is more explanation needed?

[Jerry Stuckle]

Whether it is head, middle or tail recursion makes little difference in
the amount of memory consumed. It does, however, make a difference in
the processing. Any work performed before the recursive call (tail
recursion) is done on the way down the recursion; any work performed
after the recursive call (head recursion) is done on the way back. The
result is whatever recursion is being performed is done in opposite order.

For instance, if recursing a linked list, tail recursion (performing
work before the recursion) will process the list from front to back.
Head recursion will process the list from back to front.

--
==================
Remove the "x" from my email address
Jerry Stuckle
jstu...@attglobal.net
==================

[Chris Vine]

What you say is true but misses the point. Tail recursion, provided
there are no objects in local scope having a non-trivial destructor,
will be optimized into a goto with gcc and -O2 or -O3 optimization,
and apparently -Os also as demonstrated above. Non-tail recursion will
build up results on the stack for the purposes of post-rercursion
processing as you have mentioned, resulting in higher memory usage. With
enough recursion it will bust your stack. Where tail call elimination
is possible, it will not. In functional programming, tail call
recursion is normally described as "iterative", and non-tail recursion
as "recursive".

Chris

[Chris Vine]

On Fri, 16 Jun 2017 19:04:32 +0100
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
> What you say is true but misses the point. Tail recursion, provided

^^^^
Except as regards your comments about memory usage.

[Jerry Stuckle]

Yes - PROVIDE THERE ARE NO OBJECT... Tail recursion itself does NOT mean
that the function can be optimized into a goto. There are many factors
involved.

And "iterative" is not the same as "recursive" - and has not been for
the last 40+ years. Even if the function is optimized to a goto it is
still considered recursive.

[Chris Vine]

On Fri, 16 Jun 2017 15:07:24 -0400
Jerry Stuckle <jstu...@attglobal.net> wrote:
> On 6/16/2017 2:04 PM, Chris Vine wrote:

[snip]

>> What you say is true but misses the point. Tail recursion, provided

^^^^
>> Except as regards your comments about memory usage.

>> there are no objects in local scope having a non-trivial destructor,
>> will be optimized into a goto with gcc and -O2 or -O3 optimization,
>> and apparently -Os also as demonstrated above. Non-tail recursion
>> will build up results on the stack for the purposes of
>> post-rercursion
>> processing as you have mentioned, resulting in higher memory usage.
>> With enough recursion it will bust your stack. Where tail call
>> elimination is possible, it will not. In functional programming,
>> tail call recursion is normally described as "iterative", and
>> non-tail recursion as "recursive".

> Yes - PROVIDE THERE ARE NO OBJECT... Tail recursion itself does NOT
> mean that the function can be optimized into a goto. There are many
> factors involved.

You misunderstand, and there are no other factors involved, other than
the choice of optimization level. If there is an object in function
scope with a non-trivial destructor, in C++ the function call is not
in tail position: there is still a destructor to execute. If on the
other hand it is in tail position, gcc will optimize the function call
away.

There is no point in arguing about it in your usual style. You claimed
that there is "little difference" between tail calls and non-tail calls
as regards stack usage. With gcc and other modern compilers that is
wrong.

> And "iterative" is not the same as "recursive" - and has not been for
> the last 40+ years. Even if the function is optimized to a goto it is
> still considered recursive.

I prepended the words "in functional programming". You are talking out
of your ass, not for the first time.

[Christiano]

******************
INITIAL STATUS:
Stack:
[ head is 1 ]
Linked List:
1->2->3->4->NULL
******************

Calling function
RecursiveReverse(&head);

Debugging
Setting breakpoints to line 1 and line 26

RUN >>

PAUSE line 1 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is ?, rest is ?, position = line 1 ]
Linked List:
1->2->3->4->NULL
---------------------------------------------

RUN >>

PAUSE line 1 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 2, position = line 18 ]
#3 [ first is ?, rest is ?, position = line 1 ]
Linked List:
1->2->3->4->NULL
---------------------------------------------

RUN >>

PAUSE line 1 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 2, position = line 18 ]
#3 [ first is 2, rest is 3, position = line 18 ]
#4 [ first is ?, rest is ?, position = line 1 ]
Linked List:
1->2->3->4->NULL
---------------------------------------------

RUN >>

PAUSE line 1 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 2, position = line 18 ]
#3 [ first is 2, rest is 3, position = line 18 ]
#4 [ first is 3, rest is 4, position = line 18 ]
#5 [ first is ?, rest is ?, position = line 1 ]
Linked List:
1->2->3->4->NULL
---------------------------------------------

RUN >>

PAUSE line 26 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 2, position = line 18 ]
#3 [ first is 2, rest is 4, position = line 18 ]
#4 [ first is 3, rest is 4, position = line 26 ]
Linked List:
1->2->3<-4
`-->NULL
---------------------------------------------

RUN >>

PAUSE line 26 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 4, position = line 18 ]
#3 [ first is 2, rest is 4, position = line 26 ]
Linked List:
1->2<-3<-4
`-->NULL
---------------------------------------------

RUN >>

PAUSE line 26 ||
---------------------------------------------
Stack:
#1 [ head is 4 ]
#2 [ first is 1, rest is 4, position = line 26 ]
Linked List:
NULL<-1<-2<-3<-4
---------------------------------------------

******************
FINAL STATUS:
Stack:
#1 [ head is 4 ]
Linked List:
NULL<-1<-2<-3<-4
******************

[Jerry Stuckle]

No, I don't misunderstand. There is much more involved than just the
optimization level. And you base everything on gcc - which is not the
only compiler - and not always standards-compliant.

> There is no point in arguing about it in your usual style. You claimed
> that there is "little difference" between tail calls and non-tail calls
> as regards stack usage. With gcc and other modern compilers that is
> wrong.
>

See above.

>> And "iterative" is not the same as "recursive" - and has not been for
>> the last 40+ years. Even if the function is optimized to a goto it is
>> still considered recursive.
>
> I prepended the words "in functional programming". You are talking out
> of your ass, not for the first time.
>

Once again you resort to ad hominem attacks instead of the facts. That
shows you cannot refute facts.

[Alf P. Steinbach]

On 16-Jun-17 5:42 PM, Tim Rentsch wrote:
> Bilal <bilal...@googlemail.com> writes:
>
>> I am a bit confused about using recursion with linked list. Below
>> is the code [...]
>
> The function you wrote has a recursive call "in the middle" of
> the function body. That is, the function body does more work
> after the recursive call is done, rather than just returning the
> result of a recursive call (which would need to be a different
> call).
>
> In cases like this, where the depth of recursion might be very
> large (what if we have a list with 1,000,000 elements in it?),
> it's important to write such functions so any recursive call is a
> tail call (usually called tail recursion). Often such function
> bodies will be optimized during compilation so recursive calls
> are turned into loops rather than calls.

Good teaching point.

For C++ it's important to note that if there are local variables with
destructors, whose destructors run after the recursive call, then the
term “tail-recursive” doesn't really apply, and the optimization can be
foiled. I.e. one should not write code as if this optimization were an
effectively guaranteed feature. In fact it's worse: at least some
earlier version of Visual C++ failed to optimize the usual tail
recursive factorial function beginner's example, when the return type
was floating point (it optimized that tail recursion fine for `int`).

> Here is a short example
> of how to implement list reversal using tail recursion:
>
> typedef struct list_node *List;
>
> struct list_node {
> List next;
> char value;
> };
>
> static List
> reverse_onto( List s, List r ){
> List t;
> return s ? t = s->next, s->next = r, reverse_onto( t, s ) : r;
> }
>
> void
> reverse( List &s ){
> s = reverse_onto( s, 0 );
> }
>

[snipped a part that did not include discussion of how this works]

> Using tail recursion has given us a nice compact loop to effect
> list reversal.

At the cost of clarity.

> Do you understand how the list reversal functions shown
> above work, or is more explanation needed?

Can't say I did at first glance, so I am not at all sure that it helped
the OP with the question of understanding. Though it probably helped in
other ways, including teaching that tail recursion can often be optimized.

At first this looked to me like something from a an obfuscated code
contest, apparently intentionally using common obfuscation techniques:

• uninformative single letter names,

• inconsistent naming conventions (`List` versus `list_node`),

• the perplexing and apparently misleading name `reverse_onto` (which
however does make some sense /after/ figuring out how this works),

• expression with side effects, and

• a recursive call, indirection, in there, with apparent
switching/change of meaning of arguments in each call.

Instead I think it's good to teach beginners that

• source code is about communicating to humans, not so much about
communicating to a compiler.

And therefore to use /self-describing names/, except where there is
nothing easy to describe or where there is a strongly established
convention such as `T` or `i`.

And also, consistent with that principle, I think it's good to teach
beginners that

• programming is not a contest in brevity and terseness.

And therefore to not at all be afraid of producing many lines of code,
but rather to embrace that eagerly where it improves clarity. But of
course, to not do it needlessly. Being able to fit much of the relevant
code for something in one screen-full, is helpful in actual work.

And third, also consistent with the first principle, that

• comments can/should be used for non-obvious things.

I rewrote the code according to the above principles:


------------------------------------------------------------------
using List = struct Node*;

struct Node
{
int value; // Having this first supports curly braces init.
List next;
};

namespace impl {

auto reversed(
List const s, // A valid list
Node* const node_originally_before_s // Start of a rev list
)
-> List
{
if( s == nullptr )
{
return node_originally_before_s;
}

List const rest_of_the_list = s->next;
s->next = node_originally_before_s;
return reversed( rest_of_the_list, s );
}

} // namespace impl

void reverse( List& s )
{

s = impl::reversed( s, 0 );
}
------------------------------------------------------------------

With self-describing names, consistent naming conventions, unambiguous
function name, and no side-effect expressions, the recursive call with
the apparent switch/change of arguments should be easier to understand.

However, as the English say, the proof is in the pudding.


- Alf

[Chris Vine]

On Fri, 16 Jun 2017 20:18:53 -0400
Jerry Stuckle <jstu...@attglobal.net> wrote:
[snip]

> Once again you resort to ad hominem attacks instead of the facts.
> That shows you cannot refute facts.

The facts are that:

* In response to a poster who said "it's important to write such
functions so any recursive call is a tail call", you said "Whether it

is head, middle or tail recursion makes little difference in the

amount of memory consumed",

* That poster was right and you were wrong. Whatever obfuscation you
may try to introduce now, as I pointed out the key to the issue with
gcc and clang is to avoid having objects in function scope with
non-trivial destructors, in order to keep the recursive calls as tail
calls.

[guinne...@gmail.com]

On Saturday, 17 June 2017 01:59:05 UTC+1, Alf P. Steinbach wrote:
>
<snip>

>
> However, as the English say, the proof is in the pudding.

No, we don't. We say "the proof of the pudding is in the eating."

The mangled (and unintelligible) version you quoted probably
originated on the other side of the Atlantic.

[Alf P. Steinbach]

Thanks! Learned something… :)

From <url: https://en.wiktionary.org/wiki/the_proof_is_in_the_pudding
>, essentially what you wrote:

“Etymology: This phrase is a shortened form of the proof of the pudding
is in the eating (14th century). The shorter version dates back to the
1920s and came into common use in the United States in the 1950s.”


Cheers!,

- Alf

[Jerry Stuckle]

Nope. You went on to qualify IF there isn't an object with a
non-trivial destructor... IF the function call is in the tail
position... IF you use gcc ... IF you use -O2 or -O3 THEN gcc MIGHT make
this a iterative call.

One can always make special cases. However, the general case is not
true. Any change in the above and it won't be iterative. Counting on
it being an iterative operation is an invitation to bugs when
maintenance changes those conditions and the call is no longer iterative.

[Öö Tiib]

On Sunday, 18 June 2017 00:33:18 UTC+3, Jerry Stuckle wrote:
> On 6/17/2017 4:27 AM, Chris Vine wrote:
> > On Fri, 16 Jun 2017 20:18:53 -0400
> > Jerry Stuckle <jstu...@attglobal.net> wrote:
> > [snip]
> >> Once again you resort to ad hominem attacks instead of the facts.
> >> That shows you cannot refute facts.
> >
> > The facts are that:
> >
> > * In response to a poster who said "it's important to write such
> > functions so any recursive call is a tail call", you said "Whether it
> > is head, middle or tail recursion makes little difference in the
> > amount of memory consumed",
> >
> > * That poster was right and you were wrong. Whatever obfuscation you
> > may try to introduce now, as I pointed out the key to the issue with
> > gcc and clang is to avoid having objects in function scope with
> > non-trivial destructors, in order to keep the recursive calls as tail
> > calls.
> >
>
> Nope. You went on to qualify IF there isn't an object with a
> non-trivial destructor... IF the function call is in the tail
> position... IF you use gcc ... IF you use -O2 or -O3 THEN gcc MIGHT make
> this a iterative call.

Red herring. Microsoft's compiler does tail recursion optimization also
with /O2. Now I take Mac and clang does it with -O2 and ICC does it
with -02 there. These are the usual C++ compilers and usual optimization
levels for release builds of those compilers.

>
> One can always make special cases. However, the general case is not
> true. Any change in the above and it won't be iterative. Counting on
> it being an iterative operation is an invitation to bugs when
> maintenance changes those conditions and the call is no longer iterative.

You are making special case here, Jerry. In several ways special case.

Indeed there can exist C++ compiler incapable of doing tail recursion optimization. I don't know that compiler. What *special* compiler it is,
Jerry?

On all compilers the optimizations can be turned off. That is done on
very *special* cases (typically for to avoid defects in compiler
or in legacy code to manifest). What is your reason to turn it off, Jerry?

There even can be code where compiler can not do that optimization.
Please show that *special* example code Jerry. I am close to certain that
we can refactor it to repair the issue.

[leigh.v....@googlemail.com]

One shouldn't rely on compiler optimizations to ensure code correctness. Rather than using recursion write an explicit loop if there is likelihood of lots of iterations.

/Flibble

[Öö Tiib]

On Sunday, 18 June 2017 15:18:43 UTC+3, leigh.v....@googlemail.com wrote:
> One shouldn't rely on compiler optimizations to ensure code correctness. Rather than using recursion write an explicit loop if there is likelihood of lots of iterations.

What you mean by code correctness? One should not rely on writing code in
one way or other to ensure code correctness. There are sanity checks in
code, unit tests, peer reviews and testing that help to find most defects.
We are all humans and so we are all fallible.

[leigh.v....@googlemail.com]

One should not write code in a way where correctness isn't guaranteed. Testing and peer review does not guarantee code correctness.

/Flibble

[Alf P. Steinbach]

On 18-Jun-17 3:08 PM, Öö Tiib wrote:
> On Sunday, 18 June 2017 15:18:43 UTC+3, leigh.v....@googlemail.com wrote:
>> One shouldn't rely on compiler optimizations to ensure code
>> correctness. Rather than using recursion write an explicit loop if
>> there is likelihood of lots of iterations.
>
> What you mean by code correctness?

I think he means, do it iteratively instead of recursive if the depth of
recursion can exceed say 200 (a number that I grabbed from thin air, not
to say vacuum, but I think it's large enough to support common things
like binary tree traversal, at least for them balanced trees).

Because if the compiler fails to optimize the recursion, perhaps after
some maintainer has added a “useful” call tracer variable whose
destructor execution foils the optimization, then the correctness of the
code depends on usually not-so-extremely-high implementation limits.

Usually only a few MB of stack space are available.

On the other hand, when one does employ recursion, then if
tail-recursion is practically possible it's the thing to aim for.

In some cases, e.g. the gcd function, I find the recursive version very
easy to comprehend, while the iterative version is more complex to me,
and I have to understand it /in terms of/ the recursive version. So I
think for code clarity some functions should ideally be expressed with
recursion instead of loops. But it depends very much on the function.

> One should not rely on writing
> code in one way or other to ensure code correctness. There are sanity
> checks in code, unit tests, peer reviews and testing that help to
> find most defects. We are all humans and so we are all fallible.

I just wish our bodies weren't so fallible. :(


Cheers!,

- Alf

[Öö Tiib]

On Sunday, 18 June 2017 16:15:50 UTC+3, leigh.v....@googlemail.com wrote:
> One should not write code in a way where correctness isn't guaranteed. Testing and peer review does not guarantee code correctness.

Person can guarantee correctness like "money back guarantee" and the like. Scientific proof of correctness can prove it (but not guarantee it). Rules
don't have neither power. Whatever "grammatical" rules can help to avoid
certain errors but at the end there have to remain limitless ways to
express nonsense.

Testing and peer review can however help to find and to repair enough
defects to make the software useful in practice so people will use it.

[Jerry Stuckle]

No, I'm not the saying "if this... and if that... then the compiler can
optimize to iteration. And if ANY of those conditions change, the
compiler cannot".

That is the definition of "special case".

> Indeed there can exist C++ compiler incapable of doing tail recursion optimization. I don't know that compiler. What *special* compiler it is,
> Jerry?
>

Any number of compilers. Even gcc if you don't use -O2 or -O3.

Additionally, this can lead to all kinds of bugs. For instance, maybe
you need to change a class so that the destructor is no longer trivial.
Now the compiler can't optimize to an iteration - potentially causing
problems in one or more areas of the code completely unrelated to the
changes made to the destructor.

> On all compilers the optimizations can be turned off. That is done on
> very *special* cases (typically for to avoid defects in compiler
> or in legacy code to manifest). What is your reason to turn it off, Jerry?
>
> There even can be code where compiler can not do that optimization.
> Please show that *special* example code Jerry. I am close to certain that
> we can refactor it to repair the issue.
>

There are many reasons for turning it off. Debugging is a very common
reason why. And there have been known problems in gcc which show up
with incorrect optimizations.

And older compilers (many of which are still in use for various reasons)
may not perform that optimization.

The bottom line here is - don't depend on the compiler to perform this
particular iteration. If you want an iterative solution, write an
iterative solution.

[Richard Damon]

I think I am detecting a difference of definitions.

The classic definition of 'tail-recursion' is when a function ends with
a recursive call, and the only thing that needs to be done following is
a return, possibly of the results of the recursive call.

Such a call can be (on appropriate architectures) replaced with a bit of
code and a goto, and not need to build additional stack frames.

The exceptions quoted above are cases where even if the last statement
is a return statement of the recursive call, and thus appear to the
untrained eye as tail-recursive, the fact that there are some other
implicit actions between the return of the recursive call and the return
from this function, makes it NOT tail-recursive by the definition.

If you want to use an alternate (and likely less really useful
definition) of tail-recursive to make something that just appears to be
tail-recursive by the classic definition to be tail-recursive by
definition, you need to be clear on this, and accept that some standard
properties don't hold anymore.

[Öö Tiib]

On Sunday, 18 June 2017 16:46:13 UTC+3, Alf P. Steinbach wrote:
> On 18-Jun-17 3:08 PM, Öö Tiib wrote:
> > On Sunday, 18 June 2017 15:18:43 UTC+3, leigh.v....@googlemail.com wrote:
> >> One shouldn't rely on compiler optimizations to ensure code
> >> correctness. Rather than using recursion write an explicit loop if
> >> there is likelihood of lots of iterations.
> >
> > What you mean by code correctness?
>
> I think he means, do it iteratively instead of recursive if the depth of
> recursion can exceed say 200 (a number that I grabbed from thin air, not
> to say vacuum, but I think it's large enough to support common things
> like binary tree traversal, at least for them balanced trees).

I have seen recursion with depth of thousands but that was naive algorithm.
There if it is loop or recursion does not matter. Correct is to make
better algorithm. Note that balanced binary tree with 200 levels is
*huge*. It has billion times more nodes than there are atoms on Earth.
It can be that we never reach such technologies.

>
> Because if the compiler fails to optimize the recursion, perhaps after
> some maintainer has added a “useful” call tracer variable whose
> destructor execution foils the optimization, then the correctness of the
> code depends on usually not-so-extremely-high implementation limits.
>
> Usually only a few MB of stack space are available.

Yes, the problem with clever algorithms has always been that performance
of those is simple to damage with some cargo cult edit. So if performance
matters then critical parts of program should be covered with automated
stress tests that will help to notice that some maintenance edit has
broken something of it.

>
> On the other hand, when one does employ recursion, then if
> tail-recursion is practically possible it's the thing to aim for.
>
> In some cases, e.g. the gcd function, I find the recursive version very
> easy to comprehend, while the iterative version is more complex to me,
> and I have to understand it /in terms of/ the recursive version. So I
> think for code clarity some functions should ideally be expressed with
> recursion instead of loops. But it depends very much on the function.

I have had opinion that it is worth to avoid recursion before, because it
often resulted with weaker efficiency back then. It has changed. Now I
use recursion when it is easier to understand than loop. Compilers can
optimize well and so readability has higher priority. *When* efficiency is
needed *and* compiler can't achieve it then it can be rearranged manually.

> > One should not rely on writing
> > code in one way or other to ensure code correctness. There are sanity
> > checks in code, unit tests, peer reviews and testing that help to
> > find most defects. We are all humans and so we are all fallible.
>
> I just wish our bodies weren't so fallible. :(

Yes, no one is Spider-man and everyone better be careful. Current direction
is seemingly even towards more fallible. Modern medicine does not let
weaker of us (or the ones with defects) to die as small kids OTOH can't
fully compensate either. Globalization lets all diseases to spread faster
than ever.

[Jerry Stuckle]

But that cannot be determined from the function. You would have to look
at each object used in the function to determine if that is the case.
Not only is that against OO philosophy, you may not even have access to
the source for those objects. But then neither would the compiler, so
it wouldn't know if the code were tail recursive or not.

> If you want to use an alternate (and likely less really useful
> definition) of tail-recursive to make something that just appears to be
> tail-recursive by the classic definition to be tail-recursive by
> definition, you need to be clear on this, and accept that some standard
> properties don't hold anymore.
>
>

There are all kinds of special cases in C++. What I am saying is not to
count on optimizations such as tail recursion. If it's there, that's
nice and can speed up the code as well as save resources. But too many
unrelated actions can change the situation and making the optimization
no longer possible.

[Öö Tiib]

Yes if it is ANY of special cases that you bring up then compiler does
not do the optimization.

>
> > Indeed there can exist C++ compiler incapable of doing tail recursion optimization. I don't know that compiler. What *special* compiler it is,
> > Jerry?
> >
>
> Any number of compilers. Even gcc if you don't use -O2 or -O3.

With gcc these are common options not special options.

> Additionally, this can lead to all kinds of bugs. For instance, maybe
> you need to change a class so that the destructor is no longer trivial.
> Now the compiler can't optimize to an iteration - potentially causing
> problems in one or more areas of the code completely unrelated to the
> changes made to the destructor.

When compiler can not turn it into iteration then it can cause worse
performance. Bad performance does not usually manifest itself as
outright defect or bug. Where it does there it must be is quite special
case.

>
> > On all compilers the optimizations can be turned off. That is done on
> > very *special* cases (typically for to avoid defects in compiler
> > or in legacy code to manifest). What is your reason to turn it off, Jerry?
> >
> > There even can be code where compiler can not do that optimization.
> > Please show that *special* example code Jerry. I am close to certain that
> > we can refactor it to repair the issue.
> >
>
> There are many reasons for turning it off. Debugging is a very common
> reason why. And there have been known problems in gcc which show up
> with incorrect optimizations.

It sounds very special case when performance of debug version is good
enough reason for to do manual optimizations. I can recall such cases
but those were several years ago. Turning all optimizations off sounds
like really special solution since usually it is easier to work with
imperfect tools than just with teeth and toenails.

>
> And older compilers (many of which are still in use for various reasons)
> may not perform that optimization.

Indeed there were old times when compilers were weaker and we had to
manually optimize more. There still are some teams who have to use these
old compilers. That is not good reason for others to manually optimize
their code.

>
> The bottom line here is - don't depend on the compiler to perform this
> particular iteration. If you want an iterative solution, write an
> iterative solution.

I did not suggest to depend on such implementation details one way or
other. I would suggest to try to remove that fragility that causes
such dependency on details of algorithm instead.

[Jerry Stuckle]

They are not the defaults. That's key.

>> Additionally, this can lead to all kinds of bugs. For instance, maybe
>> you need to change a class so that the destructor is no longer trivial.
>> Now the compiler can't optimize to an iteration - potentially causing
>> problems in one or more areas of the code completely unrelated to the
>> changes made to the destructor.
>
> When compiler can not turn it into iteration then it can cause worse
> performance. Bad performance does not usually manifest itself as
> outright defect or bug. Where it does there it must be is quite special
> case.
>

Not *USUALLY*. However, in this case the difference can be extreme.
Recursion adds to the stack. A change in the code - as in making a
destructor non-trivial - which changes the optimization from iteration
to recursion could cause the program to run out of stack space.

>>
>>> On all compilers the optimizations can be turned off. That is done on
>>> very *special* cases (typically for to avoid defects in compiler
>>> or in legacy code to manifest). What is your reason to turn it off, Jerry?
>>>
>>> There even can be code where compiler can not do that optimization.
>>> Please show that *special* example code Jerry. I am close to certain that
>>> we can refactor it to repair the issue.
>>>
>>
>> There are many reasons for turning it off. Debugging is a very common
>> reason why. And there have been known problems in gcc which show up
>> with incorrect optimizations.
>
> It sounds very special case when performance of debug version is good
> enough reason for to do manual optimizations. I can recall such cases
> but those were several years ago. Turning all optimizations off sounds
> like really special solution since usually it is easier to work with
> imperfect tools than just with teeth and toenails.
>

Not really. In fact, every project I've ever been on starts with
unoptimized code. Once that is working, we check to see if it works
optimized. You'd be surprised how many times compiler bugs have shown
up in the optimization code - even in gcc.

>>
>> And older compilers (many of which are still in use for various reasons)
>> may not perform that optimization.
>
> Indeed there were old times when compilers were weaker and we had to
> manually optimize more. There still are some teams who have to use these
> old compilers. That is not good reason for others to manually optimize
> their code.
>

I didn't say anything about manually optimizing the code. What I said
was if you need an iterative solution, write an iterative solution.
Don't depend on the compiler to optimize it.

>>
>> The bottom line here is - don't depend on the compiler to perform this
>> particular iteration. If you want an iterative solution, write an
>> iterative solution.
>
> I did not suggest to depend on such implementation details one way or
> other. I would suggest to try to remove that fragility that causes
> such dependency on details of algorithm instead.
>

But that is exactly what you are arguing.

[Richard Damon]

On 6/18/17 4:05 PM, Jerry Stuckle wrote:

> There are all kinds of special cases in C++. What I am saying is not to
> count on optimizations such as tail recursion. If it's there, that's
> nice and can speed up the code as well as save resources. But too many
> unrelated actions can change the situation and making the optimization
> no longer possible.
>

If the choice is to write readable code that directly implements the
algorithm, making sure I do things so the compiler can perform a common
optimization that has great impact on the performance, or changing the
code to apply the optimization manually, and making it noticeably harder
to read, I will chose the readable version, and perhaps include a note
on the conditions that need to be met so the optimization is available.

Tail recursion is a simple to see case, and you generally know if your
compiler can do it, so if the tail recursive version is signifcantly
cleaner than the equivalent iterative version, then it makes sense to
design it in.

Now, for THIS problem, the recursive solution is probably harder to
understand than the iterative solution (maybe if the recursive algorithm
was documented it might be clearer), and so maybe not the best, unless
it was presented as a learning exercise (in which case all the arguments
about efficiency are irrelevant), in which case, perhaps part of the
exercise should be to write up documentation for the function explaining
HOW it does its work.

[Jerry Stuckle]

On 6/18/2017 8:18 PM, Richard Damon wrote:
> On 6/18/17 4:05 PM, Jerry Stuckle wrote:
>
>> There are all kinds of special cases in C++. What I am saying is not to
>> count on optimizations such as tail recursion. If it's there, that's
>> nice and can speed up the code as well as save resources. But too many
>> unrelated actions can change the situation and making the optimization
>> no longer possible.
>>
>
> If the choice is to write readable code that directly implements the
> algorithm, making sure I do things so the compiler can perform a common
> optimization that has great impact on the performance, or changing the
> code to apply the optimization manually, and making it noticeably harder
> to read, I will chose the readable version, and perhaps include a note
> on the conditions that need to be met so the optimization is available.
>
> Tail recursion is a simple to see case, and you generally know if your
> compiler can do it, so if the tail recursive version is signifcantly
> cleaner than the equivalent iterative version, then it makes sense to
> design it in.
>

It is *NOT* always simple to see. It is *NOT* just the function - it is
also the objects which are being used.

And there is the problem - maybe you think it will optimize to iteration
today. But there is absolutely *NO* guarantee that a change to the code
for the objects being used won't change that. And if it does, you can
have major problems unrelated to the changes that were made.

> Now, for THIS problem, the recursive solution is probably harder to
> understand than the iterative solution (maybe if the recursive algorithm
> was documented it might be clearer), and so maybe not the best, unless
> it was presented as a learning exercise (in which case all the arguments
> about efficiency are irrelevant), in which case, perhaps part of the
> exercise should be to write up documentation for the function explaining
> HOW it does its work.

Possibly, possibly not. I always recommend coding for clarity. But I
also recommend NOT depending on compiler optimizations for the code to
work. This is a perfect example of what can happen when you do.

[Robert Wessel]

On Sun, 18 Jun 2017 05:18:33 -0700 (PDT),
leigh.v....@googlemail.com wrote:

>One shouldn't rely on compiler optimizations to ensure code correctness. Rather than using recursion write an explicit loop if there is likelihood of lots of iterations.

Certainly not for a language like C or C++ where there is no guarantee
that the compiler does anything like tail recursion.

OTOH, a number of languages mandate tail-recursion optimization under
certain conditions, and it's entirely normal to express (some)
functions in a way that depends on that.

[Chris Vine]

On Sun, 18 Jun 2017 17:55:59 -0400

Jerry Stuckle <jstu...@attglobal.net> wrote:
[snip]

> I didn't say anything about manually optimizing the code. What I said
> was if you need an iterative solution, write an iterative solution.
> Don't depend on the compiler to optimize it.

I think the problem may be that you express yourself poorly (or
alternatively you have changed the argument). The original exchange
which prompted this now lengthy "I'll argue to the death" discussion was

that:

* In response to a poster who said "it's important to write such
functions so any recursive call is a tail call", you said "Whether it
is head, middle or tail recursion makes little difference in the
amount of memory consumed",

* That poster was right and you were wrong. As I pointed out the key

to the issue with gcc and clang is to avoid having objects in
function scope with non-trivial destructors, in order to keep the

recursive calls as tail calls which can be optimized.

This has morphed into your proposition that you should not rely on
optimizations of this kind, because you can subsequently inadvertently
modify (or add to) the objects in function scope so that one of them
acquires a non-trivial destructor. That is a separate matter on which
you are on stronger ground.

[Jerry Stuckle]

No, I was not wrong. And I am being very clear in my statements. But
you seem to choose to pick bits and pieces instead of understanding the
entire subject.

Under very specific conditions, a tail call *MAY* be optimized into an
iterative solution. However, any change in those conditions may change
that - and the solution is no longer iterative.

A tail call can *NOT* always be optimized to an iterative solution, and
one should *NEVER* depend on that optimization. Even things like a
change to the destructor of an object being used in the routine may
change the result to a non-iterative solution. And when that happens,
there is no change in the amount of memory consumed by the tail
recursion vs. other recursions.

Additionally, the C++ standard does not require this optimization, so a
change in compilers (or even a change in the version if the compiler you
are using) can change the optimization, making it non-iterative.

The bottom line here is - although the compiler *MAY* optimize the code,
which results in memory savings (or speed or other something else). But
that should *NOT* be a design consideration for your program. Relying
on a specific optimization for your code to work is just a bug waiting
to appear.

[Alf P. Steinbach]

On 19-Jun-17 3:30 PM, Jerry Stuckle wrote:
> On 6/19/2017 8:58 AM, Chris Vine wrote:

> [snip]

>
> The bottom line here is - although the compiler *MAY* optimize the code,
> which results in memory savings (or speed or other something else). But
> that should *NOT* be a design consideration for your program. Relying
> on a specific optimization for your code to work is just a bug waiting
> to appear.

It's possible you guys are in violent agreement, heh. :)


Cheers & hth.,

- Alf

[Chris Vine]

On Mon, 19 Jun 2017 09:30:03 -0400

Since you are just repeating the points you have already made on your
second (different) point - that you should not rely on optimizations
such as tail call elimination - it seems best to end this by concluding
that you express yourself poorly on occasions, of which the posting to
which I have referred is one.

[Jerry Stuckle]

Yes, and since I have to keep repeating the same points I have already
made, it seems best to end this by concluding that you have a problem
understanding plain English.

[Chris Vine]

On Mon, 19 Jun 2017 14:38:15 -0400
Jerry Stuckle <jstu...@attglobal.net> wrote:
> On 6/19/2017 12:11 PM, Chris Vine wrote:

[snip]

> > Since you are just repeating the points you have already made on
> > your second (different) point - that you should not rely on
> > optimizations such as tail call elimination - it seems best to end
> > this by concluding that you express yourself poorly on occasions,
> > of which the posting to which I have referred is one.
>
> Yes, and since I have to keep repeating the same points I have
> already made, it seems best to end this by concluding that you have
> a problem understanding plain English.

A weak response: you were doing OK but you have now let yourself down.

I don't think you are claiming a divine mandate along the lines of Brian
(http://comp.lang.cpp.narkive.com/q0Yuq9Cf/comments-on-interview-of-scott-meyers)
with whatever vicarious perfection comes with it. Assuming that's
right for you, expressing oneself poorly on occasions comes with the
territory. Get over it.

[Jerry Stuckle]

On 6/19/2017 3:14 PM, Chris Vine wrote:
> On Mon, 19 Jun 2017 14:38:15 -0400
> Jerry Stuckle <jstu...@attglobal.net> wrote:
>> On 6/19/2017 12:11 PM, Chris Vine wrote:
> [snip]
>>> Since you are just repeating the points you have already made on
>>> your second (different) point - that you should not rely on
>>> optimizations such as tail call elimination - it seems best to end
>>> this by concluding that you express yourself poorly on occasions,
>>> of which the posting to which I have referred is one.
>>
>> Yes, and since I have to keep repeating the same points I have
>> already made, it seems best to end this by concluding that you have
>> a problem understanding plain English.
>
> A weak response: you were doing OK but you have now let yourself down.
>

The truth hurts, doesn't it? But you'd never admit you have a problem
with basic understanding. Others with whom I have discussed this and
similar topics of the years don't have that problem. You seem to be a
majority of one.

> I don't think you are claiming a divine mandate along the lines of Brian
> (http://comp.lang.cpp.narkive.com/q0Yuq9Cf/comments-on-interview-of-scott-meyers)
> with whatever vicarious perfection comes with it. Assuming that's
> right for you, expressing oneself poorly on occasions comes with the
> territory. Get over it.
>

Nope, but I am claiming I explained things as you could find in "C for
Dummies". Too bad you can't understand it.

Get over it.

[Chris Vine]

On Mon, 19 Jun 2017 15:46:13 -0400
Jerry Stuckle <jstu...@attglobal.net> wrote:
> The truth hurts, doesn't it? But you'd never admit you have a problem
> with basic understanding. Others with whom I have discussed this and
> similar topics of the years don't have that problem. You seem to be a
> majority of one.

A majority of one? I don' think so. Most of your "discussions" end
similarly. You let yourself down at the end.

[Jerry Stuckle]

On 6/19/2017 3:50 PM, Chris Vine wrote:
> On Mon, 19 Jun 2017 15:46:13 -0400
> Jerry Stuckle <jstu...@attglobal.net> wrote:
>> The truth hurts, doesn't it? But you'd never admit you have a problem
>> with basic understanding. Others with whom I have discussed this and
>> similar topics of the years don't have that problem. You seem to be a
>> majority of one.
>
> A majority of one? I don' think so. Most of your "discussions" end
> similarly. You let yourself down at the end.
>

ROFLMAO! Lusers always try to blame the messenger.

>>> I don't think you are claiming a divine mandate along the lines of
>>> Brian
>>> (http://comp.lang.cpp.narkive.com/q0Yuq9Cf/comments-on-interview-of-scott-meyers)
>>> with whatever vicarious perfection comes with it. Assuming that's
>>> right for you, expressing oneself poorly on occasions comes with
>>> the territory. Get over it.
>>
>> Nope, but I am claiming I explained things as you could find in "C for
>> Dummies". Too bad you can't understand it.
>>
>> Get over it.
>

[Chris Vine]

On Mon, 19 Jun 2017 17:44:15 -0400
Jerry Stuckle <jstu...@attglobal.net> wrote:
> On 6/19/2017 3:50 PM, Chris Vine wrote:
> > A majority of one? I don' think so. Most of your "discussions" end
> > similarly. You let yourself down at the end.
> >
>
> ROFLMAO! Lusers always try to blame the messenger.

Quod erat demonstrandum

[Jerry Stuckle]

Yup, you're one of the biggest lusers here, Chris. And your lack of
understanding of simple concepts (not just this one) proves it.

[Jerry Stuckle]

On 6/19/2017 5:58 PM, Chris Vine wrote:

I should also add - that is a phrase you should be well familiar with.
Lusers use it regularly.

[Tim Rentsch]

Jerry Stuckle <jstu...@attglobal.net> writes:

> On 6/16/2017 11:42 AM, Tim Rentsch wrote:
>
>> Bilal <bilal...@googlemail.com> writes:
>>
>>> I am a bit confused about using recursion with linked list. Below
>>> is the code [...]
>>
>> The function you wrote has a recursive call "in the middle" of
>> the function body. That is, the function body does more work
>> after the recursive call is done, rather than just returning the
>> result of a recursive call (which would need to be a different
>> call).
>>
>> In cases like this, where the depth of recursion might be very
>> large (what if we have a list with 1,000,000 elements in it?),

>> it's important to write such functions so any recursive call is a

>> tail call (usually called tail recursion). Often such function
>> bodies will be optimized during compilation so recursive calls
>> are turned into loops rather than calls. Here is a short example
>> of how to implement list reversal using tail recursion:
>>
>> typedef struct list_node *List;
>>
>> struct list_node {
>> List next;
>> char value;
>> };
>>
>> static List
>> reverse_onto( List s, List r ){
>> List t;
>> return s ? t = s->next, s->next = r, reverse_onto( t, s ) : r;
>> }
>>
>> void
>> reverse( List &s ){
>> s = reverse_onto( s, 0 );
>> }
>>
>> Look at the '?' branch of the conditional expression, which is
>> taken when 's' is non-null. Notice how the last thing done in
>> this case, and the value returned from the function, is the
>> result of the recursive call to reverse_onto().
>>
>> When 's' is null, the return value is just 'r', the list we
>> are reversing "onto".
>>
>> Here is what reverse() compiles to under gcc -Os (minus some
>> lines that have unimportant assembly noise):
>>
>> _Z7reverseRP9list_node:
>> movq (%rdi), %rax
>> xorl %edx, %edx
>> .L15:
>> testq %rax, %rax
>> je .L14
>> movq (%rax), %rcx
>> movq %rdx, (%rax)
>> movq %rax, %rdx
>> movq %rcx, %rax
>> jmp .L15
>> .L14:
>> movq %rdx, (%rdi)
>> ret
>>
>> Using tail recursion has given us a nice compact loop to effect
>> list reversal.
>>
>> Do you understand how the list reversal functions shown
>> above work, or is more explanation needed?

>
> Whether it is head, middle or tail recursion makes little

> difference in the amount of memory consumed. [...]

The tail-recursive list reversal shown above uses just one stack
frame to reverse a list of arbitrary length.

Here is the non-tail-recursive reversal function of the OP,
cleaned up slightly and with the printf() calls removed:

void
RecursiveReverse( Node **headRef ){
// Base case
if( *headRef == NULL )
return;

Node *first = *headRef;

Node *rest = (*headRef)->next;

if( rest == NULL ){
return;
}

RecursiveReverse( & rest );

first->next->next = first;

first->next = NULL;
// rest always point to the last
*headRef = rest;
}

which compiles to (again under gcc -Os)

_Z16RecursiveReversePP9list_node:
pushq %rbp
pushq %rbx
subq $24, %rsp
movq (%rdi), %rbx
movq %fs:40, %rax
movq %rax, 8(%rsp)
xorl %eax, %eax
testq %rbx, %rbx
je .L16
movq (%rbx), %rax
testq %rax, %rax
movq %rax, (%rsp)
je .L16
movq %rdi, %rbp
movq %rsp, %rdi
call _Z16RecursiveReversePP9list_node
movq (%rbx), %rax
movq %rbx, (%rax)
movq (%rsp), %rax
movq $0, (%rbx)
movq %rax, 0(%rbp)
.L16:
movq 8(%rsp), %rax
xorq %fs:40, %rax
je .L19
call __stack_chk_fail
.L19:
addq $24, %rsp
popq %rbx
popq %rbp
ret

which uses one stack frame per list element of the list being
reversed. (Notice the 'call' instruction in the middle of the
generated assembly.) A list with a million elements means a
million stack frames.

[Scott Lurndal]

Tim Rentsch <t...@alumni.caltech.edu> writes:

On the other hand, this function uses 48 bytes of stack, so
a million element recursion would use 48MB. While this is
ten times the memory of a VAX 11/780, it's in the noise on
a 32GByte server.

On the gripping hand, the default maximum stack size on Redhat 6
is 10MB.

$ ulimit -s
10240

[Alf P. Steinbach]

On 20-Jun-17 2:20 PM, Tim Rentsch wrote:
>
> The tail-recursive list reversal shown above uses just one stack
> frame to reverse a list of arbitrary length.

You can't rely on that, the optimization is not guaranteed by the
standard, so when the number of items can be in the millions (your use
case) just /don't do that/.

Express the iteration directly, and guaranteed.

For guaranteed correctness trumps clarity.


> [snipped example of generated assembly for non-tail recursion]

>
> which uses one stack frame per list element of the list being
> reversed. (Notice the 'call' instruction in the middle of the
> generated assembly.) A list with a million elements means a
> million stack frames.

Yes, but for a list with a million item /don't use recursion/ in C++.

It's not guaranteed correct, because tail recursion optimization isn't
guaranteed in C++. As I mentioned earlier, even an apparently innocent
thing like `double` result instead of `int` can foil such optimization
with certain compilers; it's essentially not predictable, and I've never
seen it documented. My example was Visual C++ with a recursive gcd.


- Alf

[Jerry Stuckle]

That is true - for this special case. But changes in other areas of the
code, such as making a destructor non-trivial, will change this code to
be recursive instead of iterative.

Additionally, there is nothing in the C++ standard requiring such
optimization. The optimization is compiler (and compiler option)
dependent; other compilers (or even other versions of the same compiler)
and other options can change this.

The result is you should take advantage of such optimizations, but never
*depend* on those optimizations. Any code which depends on
optimizations to work correctly can fail after any recompile.

OTOH, a minor change to your original code:

typedef struct list_node *List;

struct list_node {
List next;
char value;
};

class Log {
public:
Log();
~Log();

};

static List
reverse_onto( List s, List r ){
List t;

Log l;

return s ? t = s->next, s->next = r, reverse_onto( t, s ) : r;
}

void
reverse( List &s ){
s = reverse_onto( s, 0 );
}

Note the addition of the Log class object to the function. Now the
generated assembler is:

_ZL12reverse_ontoP9list_nodeS0_:
.LFB0:
pushq %rbp
pushq %rbx
movq %rdi, %rbx
movq %rsi, %rbp
subq $24, %rsp
leaq 15(%rsp), %rdi
.LEHB0:
call _ZN3LogC1Ev
.LEHE0:
testq %rbx, %rbx
je .L4
movq (%rbx), %rdi
movq %rbx, %rsi
movq %rbp, (%rbx)
.LEHB1:
call _ZL12reverse_ontoP9list_nodeS0_
.LEHE1:
movq %rax, %rbx
.L2:
leaq 15(%rsp), %rdi
.LEHB2:
call _ZN3LogD1Ev
.LEHE2:
addq $24, %rsp
movq %rbx, %rax

popq %rbx
popq %rbp
ret

Note that even though the function is still tail recursive, an iterative
solution cannot be generated.

[Tim Rentsch]

leigh.v....@googlemail.com writes:

> One shouldn't rely on compiler optimizations to ensure code
> correctness. Rather than using recursion write an explicit loop if
> there is likelihood of lots of iterations.

[..and also..]

> One should not write code in a way where correctness isn't
> guaranteed. Testing and peer review does not guarantee code
> correctness.

Point one: the concern here is not one of correctness but
one of resource requirements.

Point two: whether one should rely on "compiler optimizations"
to achieve a desired effect depends on the particular case
involved. It is just as wrong to never rely on what a compiler
will do as it is to always rely on what a compiler will do.

Point three: in most environments it is easy to perform a static
automated check to verify that the code produced will behave as
expected for functions like the tail-recursive example shown
upthread. (And more complicated examples aren't that much
harder.) This check provides the needed guarantee, without the
need of any test cases or peer review.

[Alf P. Steinbach]

On 20-Jun-17 4:28 PM, Tim Rentsch wrote:
> leigh.v....@googlemail.com writes:
>
>> One shouldn't rely on compiler optimizations to ensure code
>> correctness. Rather than using recursion write an explicit loop if
>> there is likelihood of lots of iterations.
>
> [..and also..]
>
>> One should not write code in a way where correctness isn't
>> guaranteed. Testing and peer review does not guarantee code
>> correctness.
>
> Point one: the concern here is not one of correctness but
> one of resource requirements.

When you exceed available machine stack space you get UB.

Correctness is therefore not a separate issue from resource requirements.

It's not separate even with a single compiler or small set of compilers,
for a new version or different options, or really anything (since there
is no guarantee), can foil the crucial optimization of tail recursion.

> Point two: whether one should rely on "compiler optimizations"
> to achieve a desired effect depends on the particular case
> involved. It is just as wrong to never rely on what a compiler
> will do as it is to always rely on what a compiler will do.

This seems reasonable.

> Point three: in most environments it is easy to perform a static
> automated check to verify that the code produced will behave as
> expected for functions like the tail-recursive example shown
> upthread. (And more complicated examples aren't that much
> harder.) This check provides the needed guarantee, without the
> need of any test cases or peer review.

How much work is it to implement such a check?

It would be nice if you could provide one, to put this argument on a
more solid foundation.


- Alf

[Dan Cross]

In article <20170619171...@bother.homenet>,

Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
>On Mon, 19 Jun 2017 09:30:03 -0400
>Jerry Stuckle <jstu...@attglobal.net> wrote:
>> A tail call can *NOT* always be optimized to an iterative solution,

I plonked Stuckle some time ago, but this point deserves rebuttal since
it is simply wrong. A true *tail call* can always be optimized away and
replaced by a goto. However, something like a non-trivial destructor
means that the function is no longer making a tail-call.

>> and one should *NEVER* depend on that optimization. Even things like
>> a change to the destructor of an object being used in the routine may
>> change the result to a non-iterative solution. And when that happens,
>> there is no change in the amount of memory consumed by the tail
>> recursion vs. other recursions.

By definition, in that case it is no longer tail recursive. Perhaps that
is what you are trying to say, but you are conflating terminology in a
confused way.

>> [snip]

>
>Since you are just repeating the points you have already made on your
>second (different) point - that you should not rely on optimizations
>such as tail call elimination - it seems best to end this by concluding
>that you express yourself poorly on occasions, of which the posting to
>which I have referred is one.

My sincere recommendation is to just plonk the guy and ignore him.

- Dan C.

[Ben Bacarisse]

Jerry Stuckle <jstu...@attglobal.net> writes:

> On 6/20/2017 8:20 AM, Tim Rentsch wrote:
>> Jerry Stuckle <jstu...@attglobal.net> writes:
>>
>>> On 6/16/2017 11:42 AM, Tim Rentsch wrote:

<snip>

>>>> typedef struct list_node *List;
>>>>
>>>> struct list_node {
>>>> List next;
>>>> char value;
>>>> };
>>>>
>>>> static List
>>>> reverse_onto( List s, List r ){
>>>> List t;
>>>> return s ? t = s->next, s->next = r, reverse_onto( t, s ) : r;
>>>> }
>>>>
>>>> void
>>>> reverse( List &s ){
>>>> s = reverse_onto( s, 0 );
>>>> }
>>>>
>>>> Look at the '?' branch of the conditional expression, which is
>>>> taken when 's' is non-null. Notice how the last thing done in
>>>> this case, and the value returned from the function, is the
>>>> result of the recursive call to reverse_onto().

<snip>

> OTOH, a minor change to your original code:
>
> typedef struct list_node *List;
>
> struct list_node {
> List next;
> char value;
> };
>
> class Log {
> public:
> Log();
> ~Log();
> };
>
> static List
> reverse_onto( List s, List r ){
> List t;
> Log l;
> return s ? t = s->next, s->next = r, reverse_onto( t, s ) : r;
> }

A minor but significant change: the reverse_into call is no longer a
tail call.

> void
> reverse( List &s ){
> s = reverse_onto( s, 0 );
> }

<snip>

> Note that even though the function is still tail recursive, an iterative
> solution cannot be generated.

I would not call this function tail recursive. I think your point would
be better made without saying that. I think you point is that seemingly
innocent chances can have a dramatic effect on what is and is not a call
call.

--
Ben.

[Dan Cross]

In article <kfnbmpo...@x-alumni2.alumni.caltech.edu>,

Tim Rentsch <t...@alumni.caltech.edu> wrote:
>Bilal <bilal...@googlemail.com> writes:
>
>> I am a bit confused about using recursion with linked list. Below
>> is the code [...]
>
>The function you wrote has a recursive call "in the middle" of
>the function body. That is, the function body does more work
>after the recursive call is done, rather than just returning the
>result of a recursive call (which would need to be a different
>call).
>
>In cases like this, where the depth of recursion might be very
>large (what if we have a list with 1,000,000 elements in it?),
>it's important to write such functions so any recursive call is a
>tail call (usually called tail recursion). Often such function
>bodies will be optimized during compilation so recursive calls
>are turned into loops rather than calls. Here is a short example
>of how to implement list reversal using tail recursion:
>

> [snip]

Much ado has been made in this thread about tail recursion and
optimization, yet it seems to me that a perfectly readable iterative
list-reversal algorithm that runs in linear time and constant space
is being overlooked.

My suggestion would be to ditch the recursive functions and instead
just implement this:

typedef struct node Node;
struct node {
Node *next;
int value;
};

Node *
Reverse(Node *head)
{
Node *list, *prev;

prev = nullptr;
list = head;
while (list != nullptr) {
node *current = list;
list = list->next;
current->next = prev;
prev = current;
}

return prev;
}

Of course, doing so would be contrary to the comp.lang.c++ spirit
of arguing minutae to death, so feel free to ignore me. :-)

- Dan C.

[Tim Rentsch]

Richard Damon <Ric...@Damon-Family.org> writes:

> [concerning a recursive definition for list reversal]

>
> Now, for THIS problem, the recursive solution is probably harder to
> understand than the iterative solution (maybe if the recursive
> algorithm was documented it might be clearer),

Personally I find a tail-recursive definition (even the very
short one I gave upthread) easier to understand than an iterative
one. I will acknowledge though that I am used to reading and
writing such functions recursively like this, and other people
are often less familiar with a recursive style. I think anyone
who wants to be an accomplished developer should at least aspire
to being able to read either style with roughly equal ease.

> and so maybe not the
> best, unless it was presented as a learning exercise (in which case
> all the arguments about efficiency are irrelevant), in which case,
> perhaps part of the exercise should be to write up documentation for
> the function explaining HOW it does its work.

An excellent suggestion. If I could go back I would definitely
have included some comment along these lines as part of my
example.

[Jerry Stuckle]

OK, but now let's change Log to:

class Log {
public:
void func();
};

And add to the recursive function

l.func();

just to keep the compiler from optimizing the object out completely.

Now suddenly this function does optimize to an iteration - with no real
change to the function itself. And if you add the constructor and
destructor back to the class definition - notice NO CHANGE TO THE
FUNCTION AT ALL - the function once again cannot be optimized to an
iteration.

>> void
>> reverse( List &s ){
>> s = reverse_onto( s, 0 );
>> }
>
> <snip>
>> Note that even though the function is still tail recursive, an iterative
>> solution cannot be generated.
>
> I would not call this function tail recursive. I think your point would
> be better made without saying that. I think you point is that seemingly
> innocent chances can have a dramatic effect on what is and is not a call
> call.
>

As far as the function itself goes, there are no calls after the
recursion, so it is tail recursive. The presence or absence of
constructors and destructors is invisible to the function - but an have
a severe effect on the optimization of the code.

[Jerry Stuckle]

Exactly. If you want an iterative solution, code an iterative solution.
Don't code a recursive solution and expect the compiler to make it
iterative for you. That may or may not happen.

[Tim Rentsch]

Robert Wessel <robert...@yahoo.com> writes:

> On Sun, 18 Jun 2017 05:18:33 -0700 (PDT),
> leigh.v....@googlemail.com wrote:
>
>> One shouldn't rely on compiler optimizations to ensure code
>> correctness. Rather than using recursion write an explicit loop if
>> there is likelihood of lots of iterations.
>
> Certainly not for a language like C or C++ where there is no guarantee

> that the compiler does anything like tail recursion. [...]

I find the brouhaha raised in the thread here to be somewhat
amusing. I routinely write simple functions using tail
recursion, finding them easier to read, easier to write, and
easier to understand. IME compilers have no difficulty turning
such functions into simple loops internally, and that has been
true for well over a decade. (Probably also before that, but
I don't have any earlier data readily available.)

I remember a time when programmers were told not to multiply by a
power of two but to use a shift instead. These days the advice
is just the opposite - use a multiply operation to multiply, and
rely on the compiler to do whatever micro-optimization is called
for.

Going farther back, I remember a time when there was debate over
whether to program in a "high-level language" (not really very
high level back then) or assembly language. In retrospect it
seems obvious, but at the time there were serious proponents of
the assembly language choice. Eventually the old-timers were
left behind, and as usual the rest is history.

Fast forward almost 50 years, and the same kind of debates are
happening. It's only a matter of time (and maybe that time is
already here) before compilers will perform these transformations
so reliably that new developers won't give it a second thought.
And as often happens in "scientific revolutions", many old-timers
won't ever change their minds but just become less and less
relevant as they slowly die off.

In the meantime I am happy to make my comments and observations
and sit back and enjoy the show. :)

[Mr Flibble]

On 20/06/2017 15:28, Tim Rentsch wrote:
> leigh.v....@googlemail.com writes:
>
>> One shouldn't rely on compiler optimizations to ensure code
>> correctness. Rather than using recursion write an explicit loop if
>> there is likelihood of lots of iterations.
>
> [..and also..]
>
>> One should not write code in a way where correctness isn't
>> guaranteed. Testing and peer review does not guarantee code
>> correctness.
>
> Point one: the concern here is not one of correctness but
> one of resource requirements.

If a stack fault occurs then the code is incorrect.

>
> Point two: whether one should rely on "compiler optimizations"
> to achieve a desired effect depends on the particular case
> involved. It is just as wrong to never rely on what a compiler
> will do as it is to always rely on what a compiler will do.

There is no guarantee that compilers will optimize the same code the
same way when other changes to other parts of the codebase happen (e.g.
whole program optimizations and link time optimizations). Also,
compiler settings may be changed for a variety of different reasons
which can cause the code to become incorrect.

>
> Point three: in most environments it is easy to perform a static
> automated check to verify that the code produced will behave as
> expected for functions like the tail-recursive example shown
> upthread. (And more complicated examples aren't that much
> harder.) This check provides the needed guarantee, without the
> need of any test cases or peer review.

A static unit test would have to be written for EVERY *use* of the
function in question. If this function is open source it could be used
in hundreds of different projects/programs.

Sorry but your arguments simply don't wash; I stand by my assertion.

/Flibble

[Manfred]

On 6/20/2017 7:27 PM, Tim Rentsch wrote:
> Robert Wessel <robert...@yahoo.com> writes:
>
>> On Sun, 18 Jun 2017 05:18:33 -0700 (PDT),
>> leigh.v....@googlemail.com wrote:
>>
>>> One shouldn't rely on compiler optimizations to ensure code
>>> correctness. Rather than using recursion write an explicit loop if
>>> there is likelihood of lots of iterations.
>>
>> Certainly not for a language like C or C++ where there is no guarantee
>> that the compiler does anything like tail recursion. [...]

I am with Leigh here, what he wrote is just true.

It looks like you are a bit confused about what compiler optimization is.
Compiler optimization /can/ (no guarantee) produce faster code and/or
use less resources. The only guarantee (because this is dictated by the
standard) is that optimized code will produce the same results "as if"
no optimization were in place. In other words, optimizations /must not/
alter the result of the program, and they /can/ make the program
faster/smaller.
In particular, there is absolutely no guarantee that optimizations will
correct broken code.
There is a substantial difference between the examples you cited, and
the case at hand:
In your examples about "old-timers" and young revolutionaries the matter
was whether to optimize code by hand or not, but nonetheless both
choices had the precondition to be correct code.
In the case at hand, blind use of tail recursion can result in stack
overflow, which is just broken code.

Obviously this does not mean that recursion is bad. It is in fact a very
useful technique, but one must know how to use it.
Actually I /do/ use recursion and tail recursion, but, when I do, I
ensure that stack overflow cannot occur - typically this means ensuring
a proper limit in stack usage and recursion depth.

[Chris Vine]

On Tue, 20 Jun 2017 15:03:15 +0000 (UTC)
cr...@spitfire.i.gajendra.net (Dan Cross) wrote:
> In article <20170619171...@bother.homenet>,
> Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
> >On Mon, 19 Jun 2017 09:30:03 -0400
> >Jerry Stuckle <jstu...@attglobal.net> wrote:
> >> A tail call can *NOT* always be optimized to an iterative
> >> solution,
>
> I plonked Stuckle some time ago, but this point deserves rebuttal
> since it is simply wrong. A true *tail call* can always be optimized
> away and replaced by a goto. However, something like a non-trivial
> destructor means that the function is no longer making a tail-call.
>
> >> and one should *NEVER* depend on that optimization. Even things
> >> like a change to the destructor of an object being used in the
> >> routine may change the result to a non-iterative solution. And
> >> when that happens, there is no change in the amount of memory
> >> consumed by the tail recursion vs. other recursions.
>
> By definition, in that case it is no longer tail recursive. Perhaps
> that is what you are trying to say, but you are conflating
> terminology in a confused way.

That was not me, that was Jerry. I had made the point that if a
destructor remains to be executed then the call is not in tail
position, which is the same point you are making - see my original
posting about the effect of non-trivial destructors of objects in
function scope. (The obfuscation to which you refer was part of
Jerry's responses. I understand that it is easy to miss the
development of the thread, particularly if, because of your plonking,
you can only see one side of the "conversation".)

> >> [snip]
> >
> >Since you are just repeating the points you have already made on your
> >second (different) point - that you should not rely on optimizations
> >such as tail call elimination - it seems best to end this by
> >concluding that you express yourself poorly on occasions, of which
> >the posting to which I have referred is one.
>
> My sincere recommendation is to just plonk the guy and ignore him.

I have found it quite amusing. Admittedly it is probably less amusing
for other readers of the newsgroup which is why I decided not to see
how far Jerry can be taken (quite a long way would be my guess): this
newsgroup is for C++ rather than exploration of his psyche.

What is surprising is that Jerry apparently uses his real name, but
still doesn't mind presenting himself to the world as a weirdo. I
suppose you have to give him credit for that in some odd sense.

[Chris Vine]

On Tue, 20 Jun 2017 19:54:48 +0100
Mr Flibble <flibbleREM...@i42.co.uk> wrote:
> On 20/06/2017 15:28, Tim Rentsch wrote:

[snip]

> > Point two: whether one should rely on "compiler optimizations"
> > to achieve a desired effect depends on the particular case
> > involved. It is just as wrong to never rely on what a compiler
> > will do as it is to always rely on what a compiler will do.
>
> There is no guarantee that compilers will optimize the same code the
> same way when other changes to other parts of the codebase happen
> (e.g. whole program optimizations and link time optimizations).
> Also, compiler settings may be changed for a variety of different
> reasons which can cause the code to become incorrect.

You cannot ignore optimizations in deciding how to write your code. It
would be unreasonable to write code which does not rely on return value
optimization if the outcome is that you construct heap objects to be
returned where constructing local objects with RVO would be more
efficient. RVO is required by C++17 but you should be coding for it
with any compiler produced in the last 10 years.

[Dan Cross]

In article <20170620200...@bother.homenet>,

Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
>On Tue, 20 Jun 2017 15:03:15 +0000 (UTC)
>cr...@spitfire.i.gajendra.net (Dan Cross) wrote:

>> [snip]

>> By definition, in that case it is no longer tail recursive. Perhaps
>> that is what you are trying to say, but you are conflating
>> terminology in a confused way.
>
>That was not me, that was Jerry. I had made the point that if a
>destructor remains to be executed then the call is not in tail
>position, which is the same point you are making - see my original
>posting about the effect of non-trivial destructors of objects in
>function scope. (The obfuscation to which you refer was part of
>Jerry's responses. I understand that it is easy to miss the
>development of the thread, particularly if, because of your plonking,
>you can only see one side of the "conversation".)

Ah yes, I know: I was trying to indirectly respond to Stuckle's comment
by quoting "through" your post (if you'll excuse the analogy). Hence my
comments about having plonk'ed him but having to respond to that bit of
his note.... Apologies if that was not sufficiently clear.

To be explicit: You are correct, he is wrong, but he is even more wrong
than he realizes because he is using terminology incorrectly.

> [snip]

- Dan C.

[Mr Flibble]

Bad analogy. RVO not happening doesn't result in a stack fault
(incorrect code). Read up on the "as-if" rule and observable behaviour.

/Flibble

[Chris Vine]

On Tue, 20 Jun 2017 21:48:14 +0100

A failure of RVO could result in stack failure because more stack
objects are being created than would otherwise be the case. Admittedly
this is not as likely as stack failure from tail elimination not being
carried out, but you seem to be standing on principle.

Your suggestion that I do not know about the as-if rule and observable
behaviour, as a kind of put down, is rather Stuckle-like. You might
like to consider whether to avoid it. It is also misplaced here,
because RVO is the only case in C++98/11, and one of the only two cases
in C++14, where the as-if rule does not apply: side effect elimination
by virtue of the RVO is permissible in C++98/11/14.

[Mr Flibble]

Relying on RVO when RVO not happening would cause a stack fault is again
incorrect code so I see no difference.

/Flibble

[Tim Rentsch]

Let's explore these comments a bit. We would like to compare an
iterative list reversal function and a recursive list reversal
function. To simplify the discussion, let's stipulate that the two
entry points have the same interface (which is easy to arrange),
that function bodies use only parameter variables and local
variables (ie, such as would be put in registers or in the local
stack frame), and that they are each independently compiled in a
separate translation unit (ie, so at least one stack frame is
needed in either case, rather than functions being expanded
inline). What can we say about what behavior we might observe?

First, what happens if they are invoked with enough stack space
(without saying how much stack space is needed)?

Iterative: produces correct result
Recursive: produces correct result

Second, what happens if they are invoked with not enough stack
space (again without saying how much stack space is needed)?

Iterative: fails
Recursive: fails

Now we would like to inquire what range of values the language
tolerates. Does the language specification allow each case
to be compiled to take only one stack frame?

Iterative: yes
Recursive: yes

So how about the other end? Does the language specification
allow each case to be compiled to take O(n) stack frames?

Iterative: yes
Recursive: yes

I hope these results are not surprising. As far as the abstract
machine is concerned, the semantics in the two cases are
identical. Under the rules laid out in the language standard,
they are therefore completely interchangeable. In fact, a
perverse implementation could compile an iterative version so it
would take O(n) stack space, and a recursive version so it would
take O(1) stack space. As far as correctness goes, the two
approaches have identical semantics, so either both are correct
or neither is. The issue here is not one of correctness in the
language but a practical consideration related to quality of
implementation. Do you see what I mean when I say that?

(Incidentally, in response to your comment about not understanding
what optimization is - my education in formal semantics goes back
more than 40 years, and I have read the relevant sections in both
the C standard and the C++ standard fairly closely, and more than
once each. So I think it's fair to say my understanding of what
optimization is is pretty good in this particular context.)

> In the case at hand, blind use of tail recursion can result in stack
> overflow, which is just broken code.

Sure, but I'm not advocating blind use of tail recursion. In
fact very much the opposite - I am advocating /informed/ use of
tail recursion, including automated static checks to ensure
things don't get out of hand.

> Obviously this does not mean that recursion is bad. It is in fact a
> very useful technique, but one must know how to use it.
> Actually I /do/ use recursion and tail recursion, but, when I do, I
> ensure that stack overflow cannot occur - typically this means
> ensuring a proper limit in stack usage and recursion depth.

When I write simple tail-recursive functions like the one shown
upthread, my preferred method is an automated scan of the
generated assembly to verify there are no recursive calls. It's
simple to use (one extra line in the makefile), and very effective
at weeding out bad cases. More complicated algorithms (eg binary
trees) need more sophisticated analyses, but IME a simple static
scan is very good as a first line of defense - ie, most uses of
recursion can and should be written so they compile into assembly
that does not recurse.

[Alf P. Steinbach]

On 22-Jun-17 9:07 PM, Tim Rentsch wrote:
>
> Now we would like to inquire what range of values the language
> tolerates. Does the language specification allow each case
> to be compiled to take only one stack frame?
>
> Iterative: yes
> Recursive: yes
>
> So how about the other end? Does the language specification
> allow each case to be compiled to take O(n) stack frames?
>
> Iterative: yes

Nope, that's not a valid concern.

As an example, the C++ standard formally allows a 1GB `bool` type, so
that a program could in principle, with some given compiler, guaranteed
crash on the first use of a `bool` as an automatic variable. That the
standard doesn't explicitly forbid it doesn't mean that such 1GB `bool`
can occur in practice: no sane person would use that compiler. Likewise,
that the standard doesn't explicitly forbid leaking memory in each
iteration of a loop, doesn't mean that it can ever occur in practice.


> Recursive: yes

Yes.

> I hope these results are not surprising.

They are, in a “how could he believe /that/” way.


- Alf

[Mr Flibble]

Like a complete idiot you have totally missed the point:

Iterative: FIXED O(1) STACK USAGE
Recursive: UNBOUNDED O(n) STACK USAGE

/Flibble

[Chris M. Thomasson]

Fwiw, I have accidentally blown the stack using recursive formulas
before. The pure iterative form does not do this.

[Dan Cross]

In article <kfn8tkj...@x-alumni2.alumni.caltech.edu>,
Tim Rentsch <t...@alumni.caltech.edu> wrote:
>[snip]

Whether one finds these resultings surprising or not depends on what
one is supposed to find surprising. In this case, it is not surprising
that the standard permits O(n) behavior with an iterative algorithm.
It is possible.

But it is not probable, and the likelyhood that a real (as in serious,
not a proof-of-concept or joke) implementation would do something so
silly is 0. For all intents and purposes a programmer may reasonably
assume that an iterative algorithm for something like list reversal
(such as the version I posted earlier; modulo the one little typo I
put in that no one seems to have pointed out [it is still correct]...)
would run in O(1) space. There is some academic truth to the argument
that this may not be universally guaranteed, but that is, frankly, an
obtuse argument.

On the other hand, tail-recurision in inherently unsafe in a language
like C++, where non-trivial side-effects are permitted -- indeed,
encouraged -- in object destructors and objects have block scope. In
languages like Haskell, Scheme, SML and OCaml it is a wonderful
technique; but in C++ a change to an unrelated class can make an
algorithm that had been tail-recursive be no longer so by adding a
hidden destructor call in the recursive invocation, and using such
a function then becomes O(n) in memory usage.

>[snip]

>> In the case at hand, blind use of tail recursion can result in stack
>> overflow, which is just broken code.
>
>Sure, but I'm not advocating blind use of tail recursion. In
>fact very much the opposite - I am advocating /informed/ use of
>tail recursion, including automated static checks to ensure
>things don't get out of hand.

I think the issue here is that techniques like tail recursion, where
the depth is not known a priori, are in general inherently unsafe
optimizations to rely on in languages like C++. Because of some of
the fundamentals of the language's design, what looks like a perfectly
valid tail call may not be a tail call. Put another way, I would argue
that C++ is a language that does not *want* to be programmed that way.

>> Obviously this does not mean that recursion is bad. It is in fact a
>> very useful technique, but one must know how to use it.
>> Actually I /do/ use recursion and tail recursion, but, when I do, I
>> ensure that stack overflow cannot occur - typically this means
>> ensuring a proper limit in stack usage and recursion depth.
>
>When I write simple tail-recursive functions like the one shown
>upthread, my preferred method is an automated scan of the
>generated assembly to verify there are no recursive calls. It's
>simple to use (one extra line in the makefile), and very effective
>at weeding out bad cases. More complicated algorithms (eg binary
>trees) need more sophisticated analyses, but IME a simple static
>scan is very good as a first line of defense - ie, most uses of
>recursion can and should be written so they compile into assembly
>that does not recurse.

Static analysis of the compiler output, however, doesn't prevent you
from regressing after a change, though. Unless you want to check after
every change that may affect the tail-recursive function to make sure
that the compiler could figure out that it was still tail recursive,
that is -- and that seems like more effort than it's worth.

In this specific case, the iterative algorithm is just as easy to
understand (if not easier for programmers who aren't familiar with
tail recursive function optimization -- let alone the hidden pitfalls
given presented by implicit destructor calls, possibly coupled with
temporary objects being created through operator overloading, etc).

There is much to be said for code that is properly tail recursive
and for programming in that style, but this example is not it.

- Dan C.

[Manfred]

On 06/22/2017 09:07 PM, Tim Rentsch wrote:
> Manfred <non...@invalid.add> writes:
>
>> On 6/20/2017 7:27 PM, Tim Rentsch wrote:

[...]

>>
>> It looks like you are a bit confused about what compiler optimization is.
>> Compiler optimization /can/ (no guarantee) produce faster code and/or
>> use less resources. The only guarantee (because this is dictated by
>> the standard) is that optimized code will produce the same results "as
>> if" no optimization were in place. In other words, optimizations /must
>> not/ alter the result of the program, and they /can/ make the program
>> faster/smaller.
>> In particular, there is absolutely no guarantee that optimizations
>> will correct broken code.
>> There is a substantial difference between the examples you cited, and
>> the case at hand:
>> In your examples about "old-timers" and young revolutionaries the
>> matter was whether to optimize code by hand or not, but nonetheless
>> both choices had the precondition to be correct code.
>
> Let's explore these comments a bit. We would like to compare an
> iterative list reversal function and a recursive list reversal
> function. To simplify the discussion, let's stipulate that the two
> entry points have the same interface (which is easy to arrange),
> that function bodies use only parameter variables and local
> variables (ie, such as would be put in registers or in the local
> stack frame), and that they are each independently compiled in a
> separate translation unit (ie, so at least one stack frame is
> needed in either case, rather than functions being expanded
> inline). What can we say about what behavior we might observe?
>

[...]

>
> So how about the other end? Does the language specification
> allow each case to be compiled to take O(n) stack frames?
>
> Iterative: yes
> Recursive: yes
>
> I hope these results are not surprising. As far as the abstract
> machine is concerned, the semantics in the two cases are
> identical. Under the rules laid out in the language standard,
> they are therefore completely interchangeable.

No they are not. Even without practical considerations (which I will
explain below), a formal look already sees clearly that there is a
substantial difference between the two - look at the rules for automatic
storage variables:
In the iterative case the loop body is a block, and storage for
variables declared inside the block is destroyed at the end of the block
/before/ being recreated when re-entering the block.
In the recursive case, storage for variables declared inside the block
(the recursive function body) is destroyed at the end of the block
/after/ recreating new variables by the recursive call (which is inside
the block)

So, in terms of the abstract machine there is a substantial difference
between the two solutions in terms of data /storage/: for the the
iterative case it is O(1) and for the recursive case it is O(n)

Now, your point is based on the fact that the standard does not dictate
a one to one relationship between storage and memory allocation, in fact
it defines the storage duration as "minimum potential lifetime of the
storage containing the object". But this is because the standard defines
the behaviour of an /abstract/ machine. Real implementations deal with
real memory constraints, and assuming that an implementation will
allocate new storage at each loop is just perverse, and you know it.

In fact, a
> perverse implementation could compile an iterative version so it
> would take O(n) stack space, and a recursive version so it would
> take O(1) stack space. As far as correctness goes, the two
> approaches have identical semantics, so either both are correct
> or neither is. The issue here is not one of correctness in the
> language but a practical consideration related to quality of
> implementation. Do you see what I mean when I say that?

Others have already answered why your statement above is wrong. I will
only add here another comment about language "correctness" (i.e. code
which is legal according to the standard) and code correctness.

C++ is not a language which is fool-proof, i.e. if you want to write
correct C++ code, in addition to knowing the language rules, you have to
know what you are doing.

It is trivial to understand that, while it is true that code which is
malformed (by the standard's rules) is also incorrect code, it is /not/
true that code which is legal (according to the standard's rules) is
also guaranteed to be correct, in terms of the results it produces.
In this case, code which can result in stack overflow is just wrong,
even if it is syntactically and semantically correct (seems trivial to
me, but appearently it needs saying).

[...]

>
>> In the case at hand, blind use of tail recursion can result in stack
>> overflow, which is just broken code.
>
> Sure, but I'm not advocating blind use of tail recursion. In
> fact very much the opposite - I am advocating /informed/ use of
> tail recursion, including automated static checks to ensure
> things don't get out of hand.

It depends on what you mean for informed use. Testing is definitely not
enough, and the same applies to static tests (see below), if you do not
also have formal proof of defined and bounded usage of stack space. This
means a formal proof of defined and bounded recursion depth and stack
frame size of each recursion.

[...]

>
> When I write simple tail-recursive functions like the one shown
> upthread, my preferred method is an automated scan of the
> generated assembly to verify there are no recursive calls. It's
> simple to use (one extra line in the makefile), and very effective
> at weeding out bad cases.

This only holds if you are delivering /compiled/ code, but in this case
you are not delivering C++ code, you are delivering a machine executable.
If you are delivering C++ source code, your own check of the compilation
result does not guarantee the same result when your code will be
compiled by your employer or by your customer (possibly with different
compiler settings, or a different version or a different compiler itself
or on a different machine or architecture).
This is expecially true since you are relying on compiler behaviour
which is /not/ dictated by the standard.

More complicated algorithms (eg binary
> trees) need more sophisticated analyses, but IME a simple static
> scan is very good as a first line of defense - ie, most uses of
> recursion can and should be written so they compile into assembly
> that does not recurse.
>

In addition to the above, others have already noted that a maintenance
action on your code might change an iterative compilation into a
recursive compilation (e.g. triggering a destructor call). If and when
this happens, it is still your code's fault, because it is you who wrote
the recursive C++ source.

[Tim Rentsch]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> On 20-Jun-17 4:28 PM, Tim Rentsch wrote:
>
>> leigh.v....@googlemail.com writes:
>>
>>> One shouldn't rely on compiler optimizations to ensure code
>>> correctness. Rather than using recursion write an explicit loop if
>>> there is likelihood of lots of iterations.
>>
>> [..and also..]
>>
>>> One should not write code in a way where correctness isn't
>>> guaranteed. Testing and peer review does not guarantee code
>>> correctness.
>>
>> Point one: the concern here is not one of correctness but
>> one of resource requirements.
>
> When you exceed available machine stack space you get UB.

This is a common misconception, but actually it isn't right. The
abstract machine has no notion of stack, and no notion of running
out of stack space. The semantics of function calls is defined,
without regard to how much "stack space" is available, and there
is no excepting statement to make one undefined (assuming of
course the type of the call matches the type of the definition,
which is not at issue here).

In practical terms, the consequences of running out of stack
space may be just as severe as undefined behavior. But the
distinction is still important, because the issue is not a
language question but rather is extra-linguistic, ie, it depends
on things outside the language definition, and indeed on things
outside the implementation.

If you want to check this out, look at section 1 paragraph 2 in
the C standard (ie, the one that starts "This International
Standard does not specify ..."). AFAICT there is no similar set
of provisions in the C++ standard, but the C++ standard
incorporates the C standard as a normative reference, which I
believe is meant to make the same assertions for C++ as are
made for C in section 1 paragraph 2.

> Correctness is therefore not a separate issue from resource
> requirements.
>
> It's not separate even with a single compiler or small set of
> compilers, for a new version or different options, or really
> anything (since there is no guarantee), can foil the crucial
> optimization of tail recursion.

Maybe you mean something different by "correctness" than I do.
What I mean is that the semantics of the language gives the
program a meaning that agrees with its desired effect. With this
meaning of correctness, the issues here are not about correctness
but about other factors.

Now I grant you, those other concerns are important, and can
matter just as much as having a wrong program or one that has
undefined behavior. I don't mean to dismiss them, just be clear
about where the issues lie. (And we will take up shortly how
they may be addressed.)

>> Point two: whether one should rely on "compiler optimizations"
>> to achieve a desired effect depends on the particular case
>> involved. It is just as wrong to never rely on what a compiler
>> will do as it is to always rely on what a compiler will do.
>
> This seems reasonable.
>
>
>> Point three: in most environments it is easy to perform a static
>> automated check to verify that the code produced will behave as
>> expected for functions like the tail-recursive example shown
>> upthread. (And more complicated examples aren't that much
>> harder.) This check provides the needed guarantee, without the
>> need of any test cases or peer review.
>
> How much work is it to implement such a check?
>
> It would be nice if you could provide one, to put this argument on
> a more solid foundation.

Let me outline a way for the simple case (but probably also the
most common) of self-call. Afterwards there may be some comments
about more elaborate cases.

1. When compiling, have the compiler leave generated
assembly around for the checking step.

2. Scan the generated assembly, doing this:
2a. When a function starts, remember its name
2b. When a function ends, remember it is over
2c. When a 'call' instruction is encounted, if
the call is to the same function as the
last one started, the call is a self-call,
and should be flagged
2d. At the end, if no self-calls have been
flagged, there are no "bad" functions.

I expect you can write one of these yourself, without too much
difficulty. I wrote one in awk that's about 50 lines. (I make
no apologies for my awk code, but I must confess it isn't always
the code I'm most proud of. :) You're a code hound - how about
you try coding that up (in C++ if that can be done easily) and
see how it goes?

There are several limitations that are worth mentioning (listed
roughly in order of increasing difficulty).

1. Some functions, eg quicksort, are meant to be truly recursive
(ie, have self-calls). If we want to allow that there needs to
be a way to identify those functions so they won't be flagged.

2. Scanning the assembly is target specific. If there are
multiple target platforms then there needs to be a scanning
program for each target (or perhaps a single program that
understands many targets).

3. If we want to identify more general patterns, eg foo() calls
bas() and bas() calls foo(), the analysis is more complicated.
Code to flag the more general cases certainly isn't trivial,
but I think it isn't too hard either (similar to call graph
analysis).

4. The scheme outlined looks at one TU at a time, but not
inter-TU mutual recursion. If it's important to identify
"bad" inter-TU mutual recursion, then the analysis needs
to be done on all the generated assemblies at once (or maybe
produce some sort of summary, which can then be combined at
the end for the inter-TU stuff).

5. Indirect function calls (eg, through pointer-to-function
types) don't get flagged (ie, assuming there isn't some sort of
flow analysis that figures out which actual function is called).
This could matter for C++, if we want to identify mutually
recursive virtual functions. Actually I think there is something
useful that can be done here, but for simplicity let's assume
this case is out of bounds (so no large recursion depths for
mutually recursive virtual functions).

It takes a lot to do all of these, but there's no reason we have
to do that. Taking just (1) and (2), that's probably another 10
lines plus maybe 15 lines per target. I should probably go off
and do an implementation for (3) rather than speculate about how
much code it would be. But even without (3) we have a very
useful tool, because direct self-call is what will come up most
often, especially as people start exploring functional/recursive
alternatives.

[Mr Flibble]

On 25/07/2017 18:14, Tim Rentsch wrote:
> roughly in order of increasing difficulty).
>
> 1. Some functions, eg quicksort, are meant to be truly recursive
> (ie, have self-calls). If we want to allow that there needs to
> be a way to identify those functions so they won't be flagged.

Quicksort will only ever consume O(lg N) stack space worst case whilst
recursively traversing a linked list will consume O(N) stack space; an
important difference.

Also the ISO C++ Standard *does* recognize the existence of a machine stack.

Are there any other programming related issues that you are
fundamentally wrong about?

/Flibble

[Manfred]

On 7/25/2017 7:14 PM, Tim Rentsch wrote:
> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

[...]

>> When you exceed available machine stack space you get UB.
>
> This is a common misconception, but actually it isn't right. The
> abstract machine has no notion of stack, and no notion of running
> out of stack space.

It is not a misconception. It is correct: running out of stack is the
same as running out of memory (technically it is running out of
automatic storage), which is UB.

[...]

>> Correctness is therefore not a separate issue from resource
>> requirements.
>>
>> It's not separate even with a single compiler or small set of
>> compilers, for a new version or different options, or really
>> anything (since there is no guarantee), can foil the crucial
>> optimization of tail recursion.
>
> Maybe you mean something different by "correctness" than I do.
> What I mean is that the semantics of the language gives the
> program a meaning that agrees with its desired effect. With this
> meaning of correctness, the issues here are not about correctness
> but about other factors.

No, the issue is about correctness: a program that runs out of stack
space (i.e. out of automatic storage memory) is just broken (I think I
already explained that). No matter if the standard does not specify (for
obvious reasons) any requirements for physical or virtual amount of memory.

[...]

>>
>> How much work is it to implement such a check?
>>
>> It would be nice if you could provide one, to put this argument on
>> a more solid foundation.
>
> Let me outline a way for the simple case (but probably also the
> most common) of self-call. Afterwards there may be some comments
> about more elaborate cases.
>
> 1. When compiling, have the compiler leave generated
> assembly around for the checking step.
>
> 2. Scan the generated assembly, doing this:
> 2a. When a function starts, remember its name
> 2b. When a function ends, remember it is over
> 2c. When a 'call' instruction is encounted, if
> the call is to the same function as the
> last one started, the call is a self-call,
> and should be flagged
> 2d. At the end, if no self-calls have been
> flagged, there are no "bad" functions.
>

[... more complications snipped]
Are you seriously stating that doing this is more clear, more robust,
and better maintainable than writing a correct non-recursive implementation?

[David Brown]

On 25/07/17 19:45, Mr Flibble wrote:
> On 25/07/2017 18:14, Tim Rentsch wrote:
>> roughly in order of increasing difficulty).
>>
>> 1. Some functions, eg quicksort, are meant to be truly recursive
>> (ie, have self-calls). If we want to allow that there needs to
>> be a way to identify those functions so they won't be flagged.
>
> Quicksort will only ever consume O(lg N) stack space worst case whilst
> recursively traversing a linked list will consume O(N) stack space; an
> important difference.

Worst case, quicksort is linear - and will thus consume O(N) stack
space. For a simple and obvious implementation of quicksort, a
currently sorted list is the worst case. Usually, implementations are a
bit more sophisticated than that, but that is the worst case.

>
> Also the ISO C++ Standard *does* recognize the existence of a machine
> stack.

It is quite easy to take a pdf of the C++ standard (I use N3797, C++14)
and search for the word "stack". It turns up about a dozen times in the
context of "stack unwinding", and of course in the container type
"stack". The phrase "machine stack" does not exist, and "stack
unwinding" is just the name given to the process of calling destructors
for automatic objects when an exception is thrown.

So no, the C++ Standard does /not/ require a machine stack of any sort.
It requires a way to handle function calls, including recursive ones,
and it requires a way to track destructable automatic objects in order
to destruct them in the correct order when necessary.

Pretty much the only sane way to implement this is with a machine stack
(or possibly two - I know of a C implementation with separate return
stacks and data stacks, though it did not support C++). I have never
heard of a C++ implementation that does not have a machine stack. But
the standards don't require it.


If you think I am wrong, please give me the reference in the C++
standards where the machine stack is described.


(Note that the C Standard don't mention the word "stack" at all.)

[Mr Flibble]

On 25/07/2017 20:42, David Brown wrote:
> On 25/07/17 19:45, Mr Flibble wrote:
>> On 25/07/2017 18:14, Tim Rentsch wrote:
>>> roughly in order of increasing difficulty).
>>>
>>> 1. Some functions, eg quicksort, are meant to be truly recursive
>>> (ie, have self-calls). If we want to allow that there needs to
>>> be a way to identify those functions so they won't be flagged.
>>
>> Quicksort will only ever consume O(lg N) stack space worst case whilst
>> recursively traversing a linked list will consume O(N) stack space; an
>> important difference.
>
> Worst case, quicksort is linear - and will thus consume O(N) stack
> space. For a simple and obvious implementation of quicksort, a
> currently sorted list is the worst case. Usually, implementations are a
> bit more sophisticated than that, but that is the worst case.

Obviously that is only the case for a naive implementation of quicksort;
for a non-naive implementation the space complexity is, as I said, O(lg N):

"For Quicksort, the combination of end- recursion removal and a policy
of processing the smaller of the two subfiles first turns out to ensure
that the stack need only contain room for about, lg N entries, since
each entry on the stack after the top one must represent a subfile less
than half the size of the previous entry." -- ROBERT SEDGEWICK

>
>>
>> Also the ISO C++ Standard *does* recognize the existence of a machine
>> stack.
>
> It is quite easy to take a pdf of the C++ standard (I use N3797, C++14)
> and search for the word "stack". It turns up about a dozen times in the
> context of "stack unwinding", and of course in the container type
> "stack". The phrase "machine stack" does not exist, and "stack
> unwinding" is just the name given to the process of calling destructors
> for automatic objects when an exception is thrown.
>
> So no, the C++ Standard does /not/ require a machine stack of any sort.
> It requires a way to handle function calls, including recursive ones,
> and it requires a way to track destructable automatic objects in order
> to destruct them in the correct order when necessary.

Stack unwinding is done on a machine stack ergo the C++ ISO Standard
recognizes the existence of machine stacks.

/Flibble

[David Brown]

On 25/07/17 21:36, Manfred wrote:
> On 7/25/2017 7:14 PM, Tim Rentsch wrote:
>> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
> [...]
>>> When you exceed available machine stack space you get UB.
>>
>> This is a common misconception, but actually it isn't right. The
>> abstract machine has no notion of stack, and no notion of running
>> out of stack space.
> It is not a misconception. It is correct: running out of stack is the
> same as running out of memory (technically it is running out of
> automatic storage), which is UB.

It is technically a misconception - the standards do not require a stack
or have any notion of it. In practice, of course, all (AFAIK) C++
implementations use a stack for automatic allocation.

The standards does not, as far as I can see, make any mention of the
possibility of running out of automatic storage space. By definition,
therefore, that would be undefined behaviour (as you say).

>
> [...]
>
>>> Correctness is therefore not a separate issue from resource
>>> requirements.
>>>
>>> It's not separate even with a single compiler or small set of
>>> compilers, for a new version or different options, or really
>>> anything (since there is no guarantee), can foil the crucial
>>> optimization of tail recursion.
>>
>> Maybe you mean something different by "correctness" than I do.
>> What I mean is that the semantics of the language gives the
>> program a meaning that agrees with its desired effect. With this
>> meaning of correctness, the issues here are not about correctness
>> but about other factors.
> No, the issue is about correctness: a program that runs out of stack
> space (i.e. out of automatic storage memory) is just broken (I think I
> already explained that). No matter if the standard does not specify (for
> obvious reasons) any requirements for physical or virtual amount of memory.
>

Exceeding implementation-defined limits will always be undefined
behaviour. It is always very difficult to reason about the correctness
of this sort of thing, because it is difficult to know the sizes in
practice. I would consider it as a correctness issue, but not one that
is handled by the standards. I would say the same thing about speed -
the standards say absolutely nothing about how fast code will be, but if
a program is specified with a time limit and does not meet it on the
required target, then the code is clearly incorrect.

[David Brown]

On 25/07/17 22:43, Mr Flibble wrote:
> On 25/07/2017 20:42, David Brown wrote:
>> On 25/07/17 19:45, Mr Flibble wrote:
>>> On 25/07/2017 18:14, Tim Rentsch wrote:
>>>> roughly in order of increasing difficulty).
>>>>
>>>> 1. Some functions, eg quicksort, are meant to be truly recursive
>>>> (ie, have self-calls). If we want to allow that there needs to
>>>> be a way to identify those functions so they won't be flagged.
>>>
>>> Quicksort will only ever consume O(lg N) stack space worst case
>>> whilst recursively traversing a linked list will consume O(N) stack
>>> space; an important difference.
>>
>> Worst case, quicksort is linear - and will thus consume O(N) stack
>> space. For a simple and obvious implementation of quicksort, a
>> currently sorted list is the worst case. Usually, implementations are
>> a bit more sophisticated than that, but that is the worst case.
>
> Obviously that is only the case for a naive implementation of quicksort;
> for a non-naive implementation the space complexity is, as I said, O(lg N):

Well, yes - I know that. But that is not what you wrote first, so I
think it needed a little more clarification.

>
>>
>>>
>>> Also the ISO C++ Standard *does* recognize the existence of a machine
>>> stack.
>>
>> It is quite easy to take a pdf of the C++ standard (I use N3797,
>> C++14) and search for the word "stack". It turns up about a dozen
>> times in the context of "stack unwinding", and of course in the
>> container type "stack". The phrase "machine stack" does not exist,
>> and "stack unwinding" is just the name given to the process of calling
>> destructors for automatic objects when an exception is thrown.
>>
>> So no, the C++ Standard does /not/ require a machine stack of any
>> sort. It requires a way to handle function calls, including recursive
>> ones, and it requires a way to track destructable automatic objects in
>> order to destruct them in the correct order when necessary.
>
> Stack unwinding is done on a machine stack ergo the C++ ISO Standard
> recognizes the existence of machine stacks.
>

You snipped the bit where I asked for a reference to the section of the
C++ standard (any version you like) which defines or describes the
machine stack. /I/ certainly could not find any such section, but I am
happy to admit that there are plenty of parts of the C++ standards that
I am not very familiar with. However, section 15.2 (of N3797, C++14)
which discusses "stack unwinding" does not give the slightest indication
of there being a requirement for a "machine stack". The term "stack
unwinding" is used because that was a common term for the process, given
that real implementations /do/ use a stack - but it does /not/ imply
that there actually is a "machine stack".

[Alf P. Steinbach]

On 25.07.2017 21:42, David Brown wrote:
> On 25/07/17 19:45, Mr Flibble wrote:
>> On 25/07/2017 18:14, Tim Rentsch wrote:
>>> roughly in order of increasing difficulty).
>>>
>>> 1. Some functions, eg quicksort, are meant to be truly recursive
>>> (ie, have self-calls). If we want to allow that there needs to
>>> be a way to identify those functions so they won't be flagged.
>>
>> Quicksort will only ever consume O(lg N) stack space worst case whilst
>> recursively traversing a linked list will consume O(N) stack space; an
>> important difference.
>
> Worst case, quicksort is linear - and will thus consume O(N) stack
> space. For a simple and obvious implementation of quicksort, a
> currently sorted list is the worst case. Usually, implementations are a
> bit more sophisticated than that, but that is the worst case.

As I recall original Quicksort is O(n^2) worst case, which was
demonstrated by an adversarial algorithm (dynamically choosing data to
make any Quicksort bad) by one of the old Unix gurus.

A recent improvement being considered as new basic sorting algorithm in
Boost, is O(n) worst case.

Sorry I don't have the time to google up references.


Cheers!,

- Alf

[Mr Flibble]

On 25/07/2017 22:27, Alf P. Steinbach wrote:
>
> As I recall original Quicksort is O(n^2) worst case, which was
> demonstrated by an adversarial algorithm (dynamically choosing data to
> make any Quicksort bad) by one of the old Unix gurus.
>
> A recent improvement being considered as new basic sorting algorithm in
> Boost, is O(n) worst case.
>
> Sorry I don't have the time to google up references.

One word: noise.

/Flibble

[Alf P. Steinbach]

But why are you injecting noise now?

[Manfred]

On 07/25/2017 10:58 PM, David Brown wrote:
> On 25/07/17 21:36, Manfred wrote:
>> On 7/25/2017 7:14 PM, Tim Rentsch wrote:
>>> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>> [...]
>>>> When you exceed available machine stack space you get UB.
>>>
>>> This is a common misconception, but actually it isn't right. The
>>> abstract machine has no notion of stack, and no notion of running
>>> out of stack space.
>> It is not a misconception. It is correct: running out of stack is the
>> same as running out of memory (technically it is running out of
>> automatic storage), which is UB.
>
> It is technically a misconception - the standards do not require a stack
> or have any notion of it. In practice, of course, all (AFAIK) C++
> implementations use a stack for automatic allocation.

My point is that the stack is memory, physical resources. It does not
matter if an implementation uses some part of memory organized as a
stack (in the conventional sense) or as anything else; if a program
exceeds the limits of such resources (on which the standard poses no
requirements) obviously it falls into UB. This is not a misconception,
it is basic (like 'abc' basic) computer science.

You get the point is about sizes, but my argument is more definite than
that:
The original question was about unprotected recursive implementation:
using it to reverse a linked list of arbitrary length - think e.g of the
case where the list comes from some external storage, a database or a
network stream.
Such an implementation, that can result in an unbound recursion depth is
definitely incorrect, even if Tim Rentsch was claiming that compiler
optimizations can fix the problem.
On the other hand, as I wrote earlier, recursion when the recursion
depth (and memory usage) is guaranteed a-priori to be bounded and within
implementation limits, /is/ correct - e.g an FFT implementation where
the sample size is fixed.

[David Brown]

On 25/07/17 23:27, Alf P. Steinbach wrote:
> On 25.07.2017 21:42, David Brown wrote:
>> On 25/07/17 19:45, Mr Flibble wrote:
>>> On 25/07/2017 18:14, Tim Rentsch wrote:
>>>> roughly in order of increasing difficulty).
>>>>
>>>> 1. Some functions, eg quicksort, are meant to be truly recursive
>>>> (ie, have self-calls). If we want to allow that there needs to
>>>> be a way to identify those functions so they won't be flagged.
>>>
>>> Quicksort will only ever consume O(lg N) stack space worst case
>>> whilst recursively traversing a linked list will consume O(N) stack
>>> space; an important difference.
>>
>> Worst case, quicksort is linear - and will thus consume O(N) stack
>> space. For a simple and obvious implementation of quicksort, a
>> currently sorted list is the worst case. Usually, implementations are
>> a bit more sophisticated than that, but that is the worst case.
>
> As I recall original Quicksort is O(n^2) worst case, which was
> demonstrated by an adversarial algorithm (dynamically choosing data to
> make any Quicksort bad) by one of the old Unix gurus.
>

O(n²) time, but O(n) stack space for the basic naïve algorithm.

It is not hard to modify the algorithm to have O(lg n) stack space, or
to have near O(n . lg n) run time for almost all cases.

> A recent improvement being considered as new basic sorting algorithm in
> Boost, is O(n) worst case.

O(n) is impossible for worst-case time, and unimpressive for scratch
space or stack space. What is it measuring here?

[David Brown]

That all sounds reasonable.

Compilers can often turn recursive code into loops - but unless your
implementation guarantees it, then relying on it to be sure your code
will work is clearly not a good idea.

[Tim Rentsch]

I wasn't making an argument. I was giving an explanation, and
trying to make a point. It's disappointing that more people
didn't understand the difference between the two.

> [...]

>>> In the case at hand, blind use of tail recursion can result in stack
>>> overflow, which is just broken code.
>>
>> Sure, but I'm not advocating blind use of tail recursion. In
>> fact very much the opposite - I am advocating /informed/ use of
>> tail recursion, including automated static checks to ensure
>> things don't get out of hand.
>
> I think the issue here is that techniques like tail recursion, where
> the depth is not known a priori, are in general inherently unsafe
> optimizations to rely on in languages like C++. Because of some of
> the fundamentals of the language's design, what looks like a perfectly
> valid tail call may not be a tail call. Put another way, I would argue
> that C++ is a language that does not *want* to be programmed that way.

I believe that's a knee-jerk reaction based on how people are
accustomed to thinking. Of course there are cases, and perhaps
more often in C++, where using a recursive formulation is a bad
choice. But there also are cases where it's a good choice. What
I'm hoping to do is help people realize that there are different
choices, and recognize which are which, rather than just continue
the automatic "imperative good, recursive bad" chanting.

>>> Obviously this does not mean that recursion is bad. It is in fact a
>>> very useful technique, but one must know how to use it.
>>> Actually I /do/ use recursion and tail recursion, but, when I do, I
>>> ensure that stack overflow cannot occur - typically this means
>>> ensuring a proper limit in stack usage and recursion depth.
>>
>> When I write simple tail-recursive functions like the one shown
>> upthread, my preferred method is an automated scan of the
>> generated assembly to verify there are no recursive calls. It's
>> simple to use (one extra line in the makefile), and very effective
>> at weeding out bad cases. More complicated algorithms (eg binary
>> trees) need more sophisticated analyses, but IME a simple static
>> scan is very good as a first line of defense - ie, most uses of
>> recursion can and should be written so they compile into assembly
>> that does not recurse.
>
> Static analysis of the compiler output, however, doesn't prevent you
> from regressing after a change, though. Unless you want to check after
> every change that may affect the tail-recursive function to make sure
> that the compiler could figure out that it was still tail recursive,
> that is -- and that seems like more effort than it's worth.

Checking after every compile is done automatically as part of the
make. As for whether it's worth the effort, if people don't try
it they will never know either what effort is involved or what
the payoff is. Thought experiments are notoriously unreliable.
Don't you think people should at least try it out for a while
before reaching a conclusion about how cost effective it is?

> In this specific case, the iterative algorithm is just as easy to
> understand (if not easier for programmers who aren't familiar with
> tail recursive function optimization -- let alone the hidden pitfalls
> given presented by implicit destructor calls, possibly coupled with
> temporary objects being created through operator overloading, etc).
>
> There is much to be said for code that is properly tail recursive
> and for programming in that style, but this example is not it.

I think that can be debated, but it's incidental to the more
general discussion about when using a recursive writing is an
appropriate choice. For most C or C++ developers, their
automatic answer to that question is "Never, except maybe for
things like binary trees or quicksort." I know a lot of those
people will stay stuck in their imperative ruts. My hope is that
some of them will realize the benefits of adopting a functional
style in some cases, and develop a more balanced view of the two
approaches, choosing between them appropriately rather than being
either all one or all the other.

[Alf P. Steinbach]

Sorry, I meant O(n log n).

I still don't recall the name of that beast etc. but I can try to find
it later (in an hour or so). I need breakfast etc. :)

Note, though, that while O(n) complexity appears unattainable, O(n) time
is not impossible as a worst case. The simple spaghetti sort has O(n)
time as worst case. You simply cut each strand of spaghetti so its
length is proportional to one of the numbers to be sorted, and this is
O(n) time; then you slam one end of the bundle against the kitchen
table, which is O(1); and then you repeatedly remove and measure the
spaghetti strand that's longest remaining, and this is also O(n) time.


Cheers!,

- Alf

[David Brown]

Certainly there are many ways of sorting that beat O(n log n) for worst
case time complexity - but they rely on features of the data (like for
bucket sort), or parallel processing (like your spaghetti sort).

[Robert Wessel]

You may be thinking of Musser's Introsort, which switches to Heapsort
if Quicksort appears to be partitioning badly, thus guaranteeing O(n
log n) behavior. This has been standard in C++ (and more recently in
C) library implementations.

There are, however, many sorts that are O(n log n) in the worst case.
Quicksort (which has a O(n**2) worst case) tends to be faster than
most other sorts when it's working well because it's inner loop is so
simple.

>Note, though, that while O(n) complexity appears unattainable, O(n) time
>is not impossible as a worst case. The simple spaghetti sort has O(n)
>time as worst case. You simply cut each strand of spaghetti so its
>length is proportional to one of the numbers to be sorted, and this is
>O(n) time; then you slam one end of the bundle against the kitchen
>table, which is O(1); and then you repeatedly remove and measure the
>spaghetti strand that's longest remaining, and this is also O(n) time.

If you allow parallel sorting O(log n) time is possible, although the
hardware cost is usually absurd. O((log n)**2) is a more common
limit, with algorithms that require "only" O(n (log n)**2) hardware.

O(n) time is possible even with fairly simple parallel sorts, for
example, you can do that with mergesort or Quicksort, with enough
processors (for example, the final pass in a merge sort will require N
steps, but the two sets being merged are of size N/2 and could have
been built in parallel in N/2 time, etc.).

There are several intermediate approaches as well.

A challenge in parallel sorting is efficiency: usually very fast
parallel sorts require much more work than less ambitious algorithms,
but are capable of distributing that work over vast amounts of
hardware. That's not a good tradeoff in many cases, where you'd like
the sort to distribute, at reasonable cost, over a fairly limited
number of nodes.

[Tim Rentsch]

cr...@spitfire.i.gajendra.net (Dan Cross) writes:

> In article <kfnbmpo...@x-alumni2.alumni.caltech.edu>,
> Tim Rentsch <t...@alumni.caltech.edu> wrote:
>
>> Bilal <bilal...@googlemail.com> writes:
>>
>>> I am a bit confused about using recursion with linked list. Below
>>> is the code [...]
>>
>> The function you wrote has a recursive call "in the middle" of
>> the function body. That is, the function body does more work
>> after the recursive call is done, rather than just returning the
>> result of a recursive call (which would need to be a different
>> call).
>>
>> In cases like this, where the depth of recursion might be very
>> large (what if we have a list with 1,000,000 elements in it?),
>> it's important to write such functions so any recursive call is a
>> tail call (usually called tail recursion). Often such function
>> bodies will be optimized during compilation so recursive calls
>> are turned into loops rather than calls. Here is a short example
>> of how to implement list reversal using tail recursion:
>>
>> [snip]
>
> Much ado has been made in this thread about tail recursion and
> optimization, yet it seems to me that a perfectly readable iterative
> list-reversal algorithm that runs in linear time and constant space
> is being overlooked.
>
> My suggestion would be to ditch the recursive functions and instead
> just implement this:
>
> typedef struct node Node;
> struct node {
> Node *next;
> int value;
> };
>
> Node *
> Reverse(Node *head)
> {
> Node *list, *prev;
>
> prev = nullptr;
> list = head;
> while (list != nullptr) {
> node *current = list;
> list = list->next;
> current->next = prev;
> prev = current;
> }
>
> return prev;
> }
>
> Of course, doing so would be contrary to the comp.lang.c++ spirit
> of arguing minutae to death, so feel free to ignore me. :-)

Personally I find a recursive definition is often a lot easier to
understand than an iterative one. My point though was only about
comparing two recursive definitions: one where the recursive
call is a tail call, and one where it is not a tail call. For
just these two cases, the one where the call is a tail call is
generally better.

[Tim Rentsch]

That has no effect on the program's semantics.

> Now, your point is based on the fact that the standard does not
> dictate a one to one relationship between storage and memory
> allocation, in fact it defines the storage duration as "minimum
> potential lifetime of the storage containing the object". But this is
> because the standard defines the behaviour of an /abstract/
> machine. Real implementations deal with real memory constraints, and
> assuming that an implementation will allocate new storage at each loop
> is just perverse, and you know it.

My comment is meant to explain a distinction between the language
formal semantics and what might occur in actual practice.
Whether such transformations are likely is irrelevant; all that
matters is that the meaning of the program is the same in both
cases.

> In fact, a
>
>> perverse implementation could compile an iterative version so it
>> would take O(n) stack space, and a recursive version so it would
>> take O(1) stack space. As far as correctness goes, the two
>> approaches have identical semantics, so either both are correct
>> or neither is. The issue here is not one of correctness in the
>> language but a practical consideration related to quality of
>> implementation. Do you see what I mean when I say that?
>
> Others have already answered why your statement above is wrong.

What I said is right. If you think it isn't then either you have
misunderstood what I was saying or you are confused about something.

> I will
> only add here another comment about language "correctness" (i.e. code
> which is legal according to the standard) and code correctness.
>
> C++ is not a language which is fool-proof, i.e. if you want to write
> correct C++ code, in addition to knowing the language rules, you have
> to know what you are doing.
>
> It is trivial to understand that, while it is true that code which is
> malformed (by the standard's rules) is also incorrect code, it is
> /not/ true that code which is legal (according to the standard's
> rules) is also guaranteed to be correct, in terms of the results it
> produces.
> In this case, code which can result in stack overflow is just wrong,
> even if it is syntactically and semantically correct (seems trivial to
> me, but appearently it needs saying).

What I think you mean is that such code is unacceptable. I wasn't
saying anything about that.

>>> In the case at hand, blind use of tail recursion can result in stack
>>> overflow, which is just broken code.
>>
>> Sure, but I'm not advocating blind use of tail recursion. In
>> fact very much the opposite - I am advocating /informed/ use of
>> tail recursion, including automated static checks to ensure
>> things don't get out of hand.
>
> It depends on what you mean for informed use. Testing is definitely
> not enough, and the same applies to static tests (see below), if you
> do not also have formal proof of defined and bounded usage of stack
> space. This means a formal proof of defined and bounded recursion
> depth and stack frame size of each recursion.

I think you don't realize quite what it is you are saying here.
But that is moving into another area of discussion so for now I
will say no more about it.

>> When I write simple tail-recursive functions like the one shown
>> upthread, my preferred method is an automated scan of the
>> generated assembly to verify there are no recursive calls. It's
>> simple to use (one extra line in the makefile), and very effective
>> at weeding out bad cases.
>
> This only holds if you are delivering /compiled/ code, but in this
> case you are not delivering C++ code, you are delivering a machine
> executable.
> If you are delivering C++ source code, your own check of the
> compilation result does not guarantee the same result when your code
> will be compiled by your employer or by your customer (possibly with
> different compiler settings, or a different version or a different
> compiler itself or on a different machine or architecture).

These things depend on what it is that is being delivered, and what
the expectations are of the people of might be taking delivery. If
you want to talk about that then we could do that, but it's outside
the scope of what I was saying.

> This is expecially true since you are relying on compiler behaviour
> which is /not/ dictated by the standard.

Using iterative code also relies on compiler behavior that is
not dictated by the standard.

> More complicated algorithms (eg binary
>
>> trees) need more sophisticated analyses, but IME a simple static
>> scan is very good as a first line of defense - ie, most uses of
>> recursion can and should be written so they compile into assembly
>> that does not recurse.
>
> In addition to the above, others have already noted that a maintenance
> action on your code might change an iterative compilation into a
> recursive compilation (e.g. triggering a destructor call). If and when
> this happens, it is still your code's fault, because it is you who
> wrote the recursive C++ source.

This falls into the same category as what I said above about what
is being delivered, etc.

[Tim Rentsch]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> On 16-Jun-17 5:42 PM, Tim Rentsch wrote:
>
>> Bilal <bilal...@googlemail.com> writes:
>>
>>> I am a bit confused about using recursion with linked list. Below
>>> is the code [...]
>>

>> [...]

>> Here is a short example
>> of how to implement list reversal using tail recursion:
>>

>> typedef struct list_node *List;
>>
>> struct list_node {
>> List next;
>> char value;
>> };
>>
>> static List
>> reverse_onto( List s, List r ){
>> List t;
>> return s ? t = s->next, s->next = r, reverse_onto( t, s ) : r;
>> }
>>
>> void
>> reverse( List &s ){
>> s = reverse_onto( s, 0 );
>> }
>
> [snipped a part that did not include discussion of how this works]
>
>
>> Do you understand how the list reversal functions shown
>> above work, or is more explanation needed?
>
> [.....objections on various points of coding style.....]
>
> I rewrote the code according to the above principles:
>
> ------------------------------------------------------------------
> using List = struct Node*;
>
> struct Node
> {
> int value; // Having this first supports curly braces init.
> List next;
> };
>
> namespace impl {
>
> auto reversed(
> List const s, // A valid list
> Node* const node_originally_before_s // Start of a rev list
> )
> -> List
> {
> if( s == nullptr )
> {
> return node_originally_before_s;
> }
>
> List const rest_of_the_list = s->next;
> s->next = node_originally_before_s;
> return reversed( rest_of_the_list, s );
> }
>
> } // namespace impl
>
> void reverse( List& s )
> {
> s = impl::reversed( s, 0 );
> }
> ------------------------------------------------------------------

Personally I find the revised definition atrocious, and decidedly
worse than what it is meant to replace. But what I was talking
about is really orthogonal to these low-level style questions,
so I will just leave it at that.

[Tim Rentsch]

cr...@spitfire.i.gajendra.net (Dan Cross) writes:

> In article <20170619171...@bother.homenet>,
> Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
>
>> On Mon, 19 Jun 2017 09:30:03 -0400
>> Jerry Stuckle <jstu...@attglobal.net> wrote:
>>
>>> A tail call can *NOT* always be optimized to an iterative solution,
>
> I plonked Stuckle some time ago, but this point deserves rebuttal since
> it is simply wrong. A true *tail call* can always be optimized away and
> replaced by a goto. [...]

I think a clarification is needed here. What you're saying is
right but may be misleading. A call that is a tail call as far
as the source language is concerned (ie, no pesky destructors to
worry about, etc) might or might not be optimizable to a goto,
depending on the actual call and what the ABI calling conventions
are. I don't pretend to understand all the issues but the question
is more subtle than it may appear at first glance. Your point
holds for a /true/ tail call, but what constitutes a true tail
call depends on more than just the source code and the language
definition.

[Alf P. Steinbach]

On 27.07.2017 08:37, Tim Rentsch wrote:
>
> Personally I find the revised definition atrocious, and decidedly
> worse than what it is meant to replace. But what I was talking
> about is really orthogonal to these low-level style questions,
> so I will just leave it at that.

You really have to get your code correct and working, before you can
have an opinion on style.


- Alf

[David Brown]

No, you don't.

It is easier to make readable code correct, than to make correct code
readable.

(For what it is worth, I don't like either of your styles. Each has its
good points and bad points, as I see it. And each is quite individual,
using features that are rarely seen in other people's code.)

[Alf P. Steinbach]

On 27.07.2017 12:11, David Brown wrote:
> On 27/07/17 10:35, Alf P. Steinbach wrote:
>> On 27.07.2017 08:37, Tim Rentsch wrote:
>>>
>>> Personally I find the revised definition atrocious, and decidedly
>>> worse than what it is meant to replace. But what I was talking
>>> about is really orthogonal to these low-level style questions,
>>> so I will just leave it at that.
>>
>> You really have to get your code correct and working, before you can
>> have an opinion on style.
>>
>
> No, you don't.
>
> It is easier to make readable code correct, than to make correct code
> readable.

Yes, as long as "readable" translates into "easy to map to a correct
picture of what should go in an abstract machine".

This kind of readability comes from correctness in the first place.

Before Tim gets to the point of ditching notation that looks good as
math, but yields execution that will fail on reasonably large data sets,
he needs to /learn/ about styles: he has no background to judge, he is
an infant in this field.

> (For what it is worth, I don't like either of your styles. Each has its
> good points and bad points, as I see it. And each is quite individual,
> using features that are rarely seen in other people's code.)

So it is.

My style has evolved through some 35+ years of programming, and I'm not
a conformist, plus I'm one of those who produce code that works, so it's
natural that my style doesn't conform to the current norm. And certainly
it may be that others won't catch up before both C and C++ are history.

Tim's style has the problem that it yields non-working code, it's a
superficial cosmetic thing from the mathematical ideals world.


Cheers!,

- Alf

[David Brown]

On 27/07/17 12:33, Alf P. Steinbach wrote:
> On 27.07.2017 12:11, David Brown wrote:
>> On 27/07/17 10:35, Alf P. Steinbach wrote:
>>> On 27.07.2017 08:37, Tim Rentsch wrote:
>>>>
>>>> Personally I find the revised definition atrocious, and decidedly
>>>> worse than what it is meant to replace. But what I was talking
>>>> about is really orthogonal to these low-level style questions,
>>>> so I will just leave it at that.
>>>
>>> You really have to get your code correct and working, before you can
>>> have an opinion on style.
>>>
>>
>> No, you don't.
>>
>> It is easier to make readable code correct, than to make correct code
>> readable.
>
> Yes, as long as "readable" translates into "easy to map to a correct
> picture of what should go in an abstract machine".
>

That is certainly part of "readability", but not all of it. That says
it should be clear what the code does at a low level. However, it
should also be clear what the code is supposed to do, and how it
achieves it algorithmically. (Yes, this is perhaps stretching the word
"readable" a bit - but it is the concept that is important here.)

> This kind of readability comes from correctness in the first place.

It is interconnected, but it does not come directly from it. Code can
be readable and wrong - it has bugs in it. But being readable, it
should be relatively easy to find and fix the bugs.

On the other hand, code can be correct but still impenetrable. Such
code is easy to break, since it is hard to modify without unintended
consequences because you can't see what is really going on in the code.

>
> Before Tim gets to the point of ditching notation that looks good as
> math, but yields execution that will fail on reasonably large data sets,
> he needs to /learn/ about styles: he has no background to judge, he is
> an infant in this field.
>

(That is an argument I am keeping away from!)

>
>> (For what it is worth, I don't like either of your styles. Each has its
>> good points and bad points, as I see it. And each is quite individual,
>> using features that are rarely seen in other people's code.)
>
> So it is.
>
> My style has evolved through some 35+ years of programming, and I'm not
> a conformist, plus I'm one of those who produce code that works, so it's
> natural that my style doesn't conform to the current norm. And certainly
> it may be that others won't catch up before both C and C++ are history.
>

A lot of people have developed their own favourite style of coding over
the years - and that's fine. Any individual is going to be better (more
productive, less bugs) at programming in a style they are very familiar
with. I am sure Tim could say pretty much the same things here as you
do despite the differences in style.

However, conformance to more common styles is sometimes important. If
you need to share your work with others (excluding others that may share
your style), or need to work on other people's code, then you need to
fit with other styles.

All I am saying here is that /I/ find some (not many) aspects of your
style of coding to be detrimental to the readability of the code. (And
similarly with Tim's code.) So I don't find it at all surprising that
other people may not like it.

> Tim's style has the problem that it yields non-working code, it's a
> superficial cosmetic thing from the mathematical ideals world.
>

I agree that it is wrong to rely on compiler optimisations for code
correctness (rather than just code efficiency). If recursive code might
not work in this case, then it is a poor choice of structuring for the
code here. In general, however, "mathematical style" code may be more
amenable to correctness proofs, and therefore have advantages at other
times.

[Manfred]

On 7/27/2017 8:22 AM, Tim Rentsch wrote:
> Manfred <non...@invalid.add> writes:
>
>> On 06/22/2017 09:07 PM, Tim Rentsch wrote:
>>
>>> Manfred <non...@invalid.add> writes:
>>>
>>>> On 6/20/2017 7:27 PM, Tim Rentsch wrote:
[...]

>>> So how about the other end? Does the language specification
>>> allow each case to be compiled to take O(n) stack frames?
>>>
>>> Iterative: yes
>>> Recursive: yes
>>>
>>> I hope these results are not surprising. As far as the abstract
>>> machine is concerned, the semantics in the two cases are
>>> identical. Under the rules laid out in the language standard,
>>> they are therefore completely interchangeable.
>>
>> No they are not. Even without practical considerations (which I will
>> explain below), a formal look already sees clearly that there is a
>> substantial difference between the two - look at the rules for
>> automatic storage variables:
>> In the iterative case the loop body is a block, and storage for
>> variables declared inside the block is destroyed at the end of the
>> block /before/ being recreated when re-entering the block.
>> In the recursive case, storage for variables declared inside the block
>> (the recursive function body) is destroyed at the end of the block
>> /after/ recreating new variables by the recursive call (which is
>> inside the block)
>>
>> So, in terms of the abstract machine there is a substantial difference
>> between the two solutions in terms of data /storage/: for the the
>> iterative case it is O(1) and for the recursive case it is O(n)
>
> That has no effect on the program's semantics.

You went further than that, in fact you wrote about the
Iterative/Recursive implementations: "Under the rules laid out in the

language standard, they are therefore completely interchangeable"

I made clear that the two solutions are /not/ interchangeable.

>
>> Now, your point is based on the fact that the standard does not
>> dictate a one to one relationship between storage and memory
>> allocation, in fact it defines the storage duration as "minimum
>> potential lifetime of the storage containing the object". But this is
>> because the standard defines the behaviour of an /abstract/
>> machine. Real implementations deal with real memory constraints, and
>> assuming that an implementation will allocate new storage at each loop
>> is just perverse, and you know it.
>
> My comment is meant to explain a distinction between the language
> formal semantics and what might occur in actual practice.
> Whether such transformations are likely is irrelevant; all that
> matters is that the meaning of the program is the same in both
> cases.

I believe that it definitely matters if one of the cases is not correct.
This is true even in a pure research environment.

>
>> In fact, a
>>
>>> perverse implementation could compile an iterative version so it
>>> would take O(n) stack space, and a recursive version so it would
>>> take O(1) stack space. As far as correctness goes, the two
>>> approaches have identical semantics, so either both are correct
>>> or neither is. The issue here is not one of correctness in the
>>> language but a practical consideration related to quality of
>>> implementation. Do you see what I mean when I say that?
>>
>> Others have already answered why your statement above is wrong.
>
> What I said is right. If you think it isn't then either you have
> misunderstood what I was saying or you are confused about something.

Just to avoid any confusion: you wrote "As far as correctness goes, the

two approaches have identical semantics, so either both are correct or
neither is."

This statement is wrong: it has been made abundantly clear that one
approach is correct and the other is not. If you still don't get it, I
would say it is you who are confused about something, sorry.

I am sorry, but this is really a gratuitous statement.

>
>>> When I write simple tail-recursive functions like the one shown
>>> upthread, my preferred method is an automated scan of the
>>> generated assembly to verify there are no recursive calls. It's
>>> simple to use (one extra line in the makefile), and very effective
>>> at weeding out bad cases.
>>
>> This only holds if you are delivering /compiled/ code, but in this
>> case you are not delivering C++ code, you are delivering a machine
>> executable.
>> If you are delivering C++ source code, your own check of the
>> compilation result does not guarantee the same result when your code
>> will be compiled by your employer or by your customer (possibly with
>> different compiler settings, or a different version or a different
>> compiler itself or on a different machine or architecture).
>
> These things depend on what it is that is being delivered, and what
> the expectations are of the people of might be taking delivery. If
> you want to talk about that then we could do that, but it's outside
> the scope of what I was saying.

The context of this discussion is C++ code, so the point that when
delivering C++ code the method that you describe above does not hold, is
pretty much on topic.

>
>> This is expecially true since you are relying on compiler behaviour
>> which is /not/ dictated by the standard.
>
> Using iterative code also relies on compiler behavior that is
> not dictated by the standard.

This is also not true. It is really getting boring to have to correct
all these mistakes, anyway let's do this too:
You propose to rely on some compiler optimization feature (specifically
tail recursion optimization) to avoid your program to run out of stack
space. Appearantly it has to be recalled here that compiler
optimizations are not dictated by the standard.
Iterative code does /not/ run out of stack space, even with no
optimizations at all.

>
>> More complicated algorithms (eg binary
>>
>>> trees) need more sophisticated analyses, but IME a simple static
>>> scan is very good as a first line of defense - ie, most uses of
>>> recursion can and should be written so they compile into assembly
>>> that does not recurse.
>>
>> In addition to the above, others have already noted that a maintenance
>> action on your code might change an iterative compilation into a
>> recursive compilation (e.g. triggering a destructor call). If and when
>> this happens, it is still your code's fault, because it is you who
>> wrote the recursive C++ source.
>
> This falls into the same category as what I said above about what
> is being delivered, etc.
>

Indeed it is about what is being delivered, which is C++ code.