Why does this work on Xcode ???

[Bob Langelaan]

Several of my students have submitted the following solution (or something very similar) for a recursive function to add the contents of an array:

// Returns true if the supplied value is found in the array of values
// and false otherwise
template <typename type, size_t size>
bool isMember(const array<type,size> & myArray, const int n, const type value)
{
if ( n < 0 )
{
return false;
}
else if ( myArray[n] == value )
{
return true;
}
return isMember( myArray, n - 1, value );
}

Clearly it should not work since the line:

else if ( myArray[n] == value )

will attemppt to reference an out of bounds element past the end of the array the first time the function is invoked. The above code has a runtime error, as expected, when executed on MS VS C++ 2017 but evidently not on the Xcode IDE.

I have two questions:

- why does the runtime not catch the fact that the array is referenced out of bounds as with MS VS C++?

- is there a compiler option that my students using Xcode could use so this logic error is caught at runtime?

Thanks in advance.

[Paavo Helde]

On 17.07.2019 8:03, Bob Langelaan wrote:
> Several of my students have submitted the following solution (or something very similar) for a recursive function to add the contents of an array:

The function does not appear to add any contents to anywhere.

> // Returns true if the supplied value is found in the array of values
> // and false otherwise
> template <typename type, size_t size>
> bool isMember(const array<type,size> & myArray, const int n, const type value)
> {
> if ( n < 0 )
> {
> return false;
> }
> else if ( myArray[n] == value )
> {
> return true;
> }
> return isMember( myArray, n - 1, value );
> }
>
> Clearly it should not work since the line:
>
> else if ( myArray[n] == value )
>
> will attemppt to reference an out of bounds element past the end of the array the first time the function is invoked.

Only if n >= size when first invoked. One can easily call it with size-1
instead for example, making it to work perfectly well (assuming size>0
&& size-1<=INT_MAX).

The above code has a runtime error, as expected,

Why do you expect a specific behavior from UB? Clearly, to get a runtime
error one should have written myArray.at(n) instead.

MSVC++ has defined this particular piece of UB by having the "checked
iterators" feature switched on by default in Debug builds (in earlier
MSVC++ versions, also in Release builds). One can turn this feature off
by defining suitable macros.

when executed on MS VS C++ 2017 but evidently not on the Xcode IDE.
>
> I have two questions:
>
> - why does the runtime not catch the fact that the array is referenced out of bounds as with MS VS C++?

Because clang or gcc does not have any "checked iterators" feature
switched on by default.

> - is there a compiler option that my students using Xcode could use so this logic error is caught at runtime?

Not sure, but that would rely on non-standard extensions anyway. Teach
your students std::array::at() instead.

[Öö Tiib]

On Wednesday, 17 July 2019 08:03:16 UTC+3, Bob Langelaan wrote:
>
> - is there a compiler option that my students using Xcode could use so this logic error is caught at runtime?

clang has -D_LIBCPP_DEBUG for debug bounds checking.

I don't have mac in front of me at the moment to check if it works
with your code.

Similarly gcc has -D_LIBCPP_DEBUG for that.

[Juha Nieminen]

Bob Langelaan <bobl...@gmail.com> wrote:
> will attemppt to reference an out of bounds element past the
> end of the array the first time the function is invoked.
> The above code has a runtime error,

It may be a "runtime error" in the logical sense, but not in the
standard sense. The standard says it's undefined behavior, which
is a completely different thing.

> as expected, when executed on MS VS C++ 2017 but evidently
> not on the Xcode IDE.

Neither compiler is doing a wrong thing. Since it's undefined
behavior, they can do whatever they want. Throwing some kind of
error, crashing, behaving in a weird way, or seemingly working
"correctly" are all valid actions. Undefined behavior means
anything goes, nothing is guaranteed.

> - why does the runtime not catch the fact that the array is
> referenced out of bounds as with MS VS C++?

Because the standard doesn't require it, and most compilers will
not add such boundary checks for efficiency reasons. Adding a
boundary check to every single array access is expensive.

I'm certain that VS C++ will also not add such boundary checks
if you specify enough optimization parameters (and/or remove enough
debugging parameters).

[Öö Tiib]

Sorry, gcc has -D_GLIBCXX_DEBUG

[James Kuyper]

On 7/17/19 1:03 AM, Bob Langelaan wrote:
> Several of my students have submitted the following solution (or something very similar) for a recursive function to add the contents of an array:
>
> // Returns true if the supplied value is found in the array of values
> // and false otherwise

I don't see how such a function would be of any use when adding the
contents of the array. What value would you supply to it, and why?

> template <typename type, size_t size>
> bool isMember(const array<type,size> & myArray, const int n, const type value)
> {
> if ( n < 0 )
> {
> return false;
> }
> else if ( myArray[n] == value )
> {
> return true;
> }
> return isMember( myArray, n - 1, value );
> }
>
> Clearly it should not work since the line:
>
> else if ( myArray[n] == value )
>
> will attemppt to reference an out of bounds element past the end of the array the first time the function is invoked.

Only if it's invoked with the wrong value; the first time it should be
invoked with size-1 as the second argument.

> The above code has a runtime error, as expected, when executed on MS VS C++ 2017 but evidently not on the Xcode IDE.
>
> I have two questions:
>
> - why does the runtime not catch the fact that the array is referenced out of bounds as with MS VS C++?

Because you used myArray[n], for which the defined behavior is
*(a.begin() + n) (Table 88, 26.2.3p14). That expression dereferences a
past-the-end iterator value. A past-the-end iterator value is not
required to be dereferenceable (Table 95, 27.2.3p2: ++r returns either a
value which is guaranteed to be dereferenceable, or a past-the-end
iterator). The undefined behavior of dereferencing a past-the-end
iterator includes, as one possibility, a runtime error (as MSVC C++
does), but that is not required.

If you want guaranteed runtime bounds checking, use myArray.at(n)
(26.2.3p15).

>
> - is there a compiler option that my students using Xcode could use so this logic error is caught at runtime?

No, but there is a way to modify the code to guarantee such checking:
use at().

[Alf P. Steinbach]

On 17.07.2019 07:03, Bob Langelaan wrote:
> Several of my students have submitted the following solution (or
> something very similar) for a recursive function to add the contents
> of an array:

The presented code doesn't “add the contents”, I guess that's just typo.

> // Returns true if the supplied value is found in the array of values
> // and false otherwise
> template <typename type, size_t size>
> bool isMember(const array<type,size> & myArray, const int n, const type value)
> {
> if ( n < 0 )
> {
> return false;
> }
> else if ( myArray[n] == value )
> {
> return true;
> }
> return isMember( myArray, n - 1, value );
> }

The two main problems with this function are:

* Passing `value` by value may incur severe copying inefficiency.
* The tail recursion may easily consume all stack space and yield UB.

The last problem is because C++ does not guarantee tail recursion
optimization, so it's a pretty dangerous thing to do for an O(n)
algorithm as this is.

It's generally OK for O(log n), as long as things are done properly such
as here, if one passed `value` by reference to `const`.

> Clearly it should not work since the line:
>
> else if ( myArray[n] == value )
>
> will attemppt to reference an out of bounds element past the end of
> the array the first time the function is invoked.

Only if `n` is the array size or larger in the first call.

Since `n` is of signed type `int` the reasonable deduction from the
signature and implementation is that the function is intended to be
called with `n` as the index of the last item to be checked.

Tip: in 64-bit Windows `int` is just 32-bit. The function is then unable
to handle large arrays in that environment. Using `ptrdiff_t` or C++20
`ssize_t` supports also large arrays in a 64-bit address space.

> The above code has a runtime error, as expected, when executed on MS
> VS C++ 2017 but evidently not on the Xcode IDE.

You can in general not count on any specific behavior for UB.

It can even vary from run to run of the same program.

However, particular compilers can support ways of handling situations
that for portable code would be UB.

> I have two questions:
>
> - why does the runtime not catch the fact that the array is
> referenced out of bounds as with MS VS C++?

Because you didn't ask for it.

MSVC is one of the compilers supporting bounds checking of the standard
library containers, but you have to ask for it.

I believe it's the default in a Visual Studio project Debug build.

> - is there a compiler option that my students using Xcode could use
> so this logic error is caught at runtime?

Xcode is an IDE, for the Mac; it uses a compiler but isn't a compiler.

Unless XCode has a general setting for bounds checking you will have to
use the relevant option for the /compiler/ you use. Typically bounds
checking is requested by defining some preprocessing symbol in the
build, via compiler option `-D` (or '/D' with Visual C++).

By default your compiler will be clang, and I seem to recall that the
apparent g++ on the mac is clang in disguise, but I'm not sure. I don't
have a Mac. Anyway look up the options in the compiler's documentation.


> Thanks in advance.

Cheers!,

- Alf

[Mr Flibble]

On 17/07/2019 16:01, Alf P. Steinbach wrote:
> On 17.07.2019 07:03, Bob Langelaan wrote:
>> Several of my students have submitted the following solution (or
>> something very similar) for a recursive function to add the contents
>> of an array:
>
> The presented code doesn't “add the contents”, I guess that's just typo.
>
>
>> // Returns true if the supplied value is found in the array of values
>> // and false otherwise
>> template <typename type, size_t size>
>> bool isMember(const array<type,size> & myArray, const int n, const type
>> value)
>> {
>>     if ( n < 0 )
>>     {
>>         return false;
>>     }
>>     else if ( myArray[n] == value )
>>     {
>>         return true;
>>     }
>>     return isMember( myArray, n - 1, value );
>> }
>
> The two main problems with this function are:
>
> * Passing `value` by value may incur severe copying inefficiency.
> * The tail recursion may easily consume all stack space and yield UB.

The whole point of using tail recursion is that is doesn't use up stack
space, silly boy.

/Flibble

--
"Snakes didn't evolve, instead talking snakes with legs changed into
snakes." - Rick C. Hodgin

“You won’t burn in hell. But be nice anyway.” – Ricky Gervais

“I see Atheists are fighting and killing each other again, over who
doesn’t believe in any God the most. Oh, no..wait.. that never happens.” –
Ricky Gervais

"Suppose it's all true, and you walk up to the pearly gates, and are
confronted by God," Bryne asked on his show The Meaning of Life. "What
will Stephen Fry say to him, her, or it?"
"I'd say, bone cancer in children? What's that about?" Fry replied.
"How dare you? How dare you create a world to which there is such misery
that is not our fault. It's not right, it's utterly, utterly evil."
"Why should I respect a capricious, mean-minded, stupid God who creates a
world that is so full of injustice and pain. That's what I would say."

[Alf P. Steinbach]

On 17.07.2019 23:15, Mr Flibble wrote:
> On 17/07/2019 16:01, Alf P. Steinbach wrote:
>> On 17.07.2019 07:03, Bob Langelaan wrote:
>>> Several of my students have submitted the following solution (or
>>> something very similar) for a recursive function to add the contents
>>> of an array:
>>
>> The presented code doesn't “add the contents”, I guess that's just typo.
>>
>>
>>> // Returns true if the supplied value is found in the array of values
>>> // and false otherwise
>>> template <typename type, size_t size>
>>> bool isMember(const array<type,size> & myArray, const int n, const
>>> type value)
>>> {
>>>     if ( n < 0 )
>>>     {
>>>         return false;
>>>     }
>>>     else if ( myArray[n] == value )
>>>     {
>>>         return true;
>>>     }
>>>     return isMember( myArray, n - 1, value );
>>> }
>>
>> The two main problems with this function are:
>>
>> * Passing `value` by value may incur severe copying inefficiency.
>> * The tail recursion may easily consume all stack space and yield UB.
>
> The whole point of using tail recursion is that is doesn't use up stack
> space, silly boy.

Unfortunately the C++ standard gives you no such guarantee.

But a particular compiler may.

It's difficult to predict because it may not be documented for the
compiler, and the compiler may optimize or not based on criteria that
only make sense internally (e.g., is the return type floating point?).


Cheers!,

- Alf

[Christian Gollwitzer]

Am 17.07.19 um 23:29 schrieb Alf P. Steinbach:

Is it true that it depends on the type of something in practical cases?
I thought that tail recursion can be mechanically translated like this:

===========
type myfunc(x, y, z) {
....

return myFunc(a, b, c);
}
===========

becomes

==========
type myfunc(x, y, z) {
start:

...

x=a, y=b, z=c;
goto start;

}
==========

Since I can do this at the source code level, I don't see why it can't
be done for every function. Of course, for mutual tail recursion I can't
do that because of the non-local goto, but for the compiler that should
also be easy.

Christian

[Alf P. Steinbach]

On 19.07.2019 08:27, Christian Gollwitzer wrote:
> Am 17.07.19 um 23:29 schrieb Alf P. Steinbach:
>> On 17.07.2019 23:15, Mr Flibble wrote:
>>> The whole point of using tail recursion is that is doesn't use up
>>> stack space, silly boy.
>>
>> Unfortunately the C++ standard gives you no such guarantee.
>>
>> But a particular compiler may.
>>
>> It's difficult to predict because it may not be documented for the
>> compiler, and the compiler may optimize or not based on criteria that
>> only make sense internally (e.g., is the return type floating point?).
>
> Is it true that it depends on the type of something in practical cases?

Yes, it's the practical particular cases where it depends.

For portable code it doesn't depend: you just have no guarantee and
hence risk UB.

And a risk of UB = UB.

> I thought that tail recursion can be mechanically translated like this:
>
> ===========
> type myfunc(x, y, z) {
>     ....
>
>     return myFunc(a, b, c);
> }
> ===========
>
> becomes
>
> ==========
> type myfunc(x, y, z) {
>     start:
>
>     ...
>
>     x=a, y=b, z=c;
>     goto start;
>
> }
> ==========

Modulo a number of caveats, yes.

The two most important ones, to my mind:

* That `type` can't be a class type with a non-trivial destructor.
A rewrite can often still be done but it's more complicated, in
general involving a stack, so it may not buy any efficiency.

* That for a debug build the compiler can't optimize away calls.
Because you can't trace into a call if it's optimized away.

> Since I can do this at the source code level, I don't see why it can't
> be done for every function. Of course, for mutual tail recursion I can't
> do that because of the non-local goto, but for the compiler that should
> also be easy.

You'd have to ask the compiler teams /why/ they choose to not always do
this for builds where debugging support has not been requested.

For the case of not doing it for floating point results I guess it has
to do with floating point operations. The original x86 architecture
supported floating point operations via a physically separate
co-processor, the 8087. This physical separation and parallelism was
retained as a logical design (although everything was put on the same
chip) in later versions, as far as I know all the way till today.

Consider this function:

auto factorial( const int n )
-> double
{
if( n == 0 ) { return 1; }
return n*factorial( n - 1 );
}

With Visual C++ 2019, release (optimized) build:

auto factorial( const int n )
-> double
{
00B71000 push esi
00B71001 mov esi,ecx

if( n == 0 ) { return 1; }
00B71003 test esi,esi
00B71005 jne factorial+11h (0B71011h)
00B71007 movsd xmm0,mmword ptr [__real@3ff0000000000000
(0B72108h)]
00B7100F pop esi
}
00B71010 ret

return n*factorial( n - 1 );
00B71011 lea ecx,[esi-1]
00B71014 call factorial (0B71000h)
00B71019 movd xmm1,esi
00B7101D cvtdq2pd xmm1,xmm1
00B71021 pop esi
00B71022 mulsd xmm0,xmm1
}
00B71026 ret

The `call` instruction there does exactly what you think it does, it
calls the function, recursively; no tail recursion optimization.


Cheers & hth.,

- Alf

[Öö Tiib]

On Friday, 19 July 2019 09:27:15 UTC+3, Christian Gollwitzer wrote:
> Am 17.07.19 um 23:29 schrieb Alf P. Steinbach:
> > On 17.07.2019 23:15, Mr Flibble wrote:
> >> The whole point of using tail recursion is that is doesn't use up
> >> stack space, silly boy.
> >
> > Unfortunately the C++ standard gives you no such guarantee.
> >
> > But a particular compiler may.
> >
> > It's difficult to predict because it may not be documented for the
> > compiler, and the compiler may optimize or not based on criteria that
> > only make sense internally (e.g., is the return type floating point?).
>
> Is it true that it depends on the type of something in practical cases?

Not to my knowledge. It is (like any other optimization) just not
required. It is not hard to implement.

Likely reason is that dummies are constantly confused when debugging
optimized programs. OTOH dummies are also confused when stack is
exhausted. Finally, when all works then they are confused that
programs fully instrumented for debugging are so sluggish.

So C++ just does not suit dummies and all efforts have been in vain.

[Alf P. Steinbach]

Oh, it does optimize the function rewritten to /pure/ tail-recursive:

auto xfactorial( const int n, double const result = 1 )
-> double
{
if( n == 0 ) { return result; }
return xfactorial( n - 1, n*result );
}

yielding Release build machine code

if( n == 0 ) { return result; }
01241000 test ecx,ecx
01241002 je xfactorial+15h (01241015h)
01241004 movd xmm0,ecx
return xfactorial( n - 1, n*result );
01241008 cvtdq2pd xmm0,xmm0
0124100C mulsd xmm1,xmm0
01241010 sub ecx,1
01241013 jne xfactorial+4h (01241004h)
}
01241015 movaps xmm0,xmm1
01241018 ret

I don't remember that behavior from earlier, but perhaps I don't
remember everything about it.


Cheers!,

- Alf

[Jorgen Grahn]

On Wed, 2019-07-17, Alf P. Steinbach wrote:
> On 17.07.2019 07:03, Bob Langelaan wrote:
>> Several of my students have submitted the following solution (or
>> something very similar) for a recursive function to add the contents
>> of an array:
>
> The presented code doesn't “add the contents”, I guess that's just typo.
>
>
>> // Returns true if the supplied value is found in the array of values
>> // and false otherwise
>> template <typename type, size_t size>
>> bool isMember(const array<type,size> & myArray, const int n, const type value)
>> {
>> if ( n < 0 )
>> {
>> return false;
>> }
>> else if ( myArray[n] == value )
>> {
>> return true;
>> }
>> return isMember( myArray, n - 1, value );
>> }
>
> The two main problems with this function are:
>
> * Passing `value` by value may incur severe copying inefficiency.
> * The tail recursion may easily consume all stack space and yield UB.

It's also fairly sad and inelegant use of recursion, with the extra
cursor being passed around. The way I learned recursion, you start by
seeing an array as either empty, or having a head element, and then:

// vaguely Haskell-like pseudo-code
ismember(value, []) -> false
ismember(value, head:tail) -> value==head || ismember(value, tail)

My point is, I'm not sure the students will appreciate recursion
properly based on that code, if that's the intention. (Perhaps not
based on any C++ code.)

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Tim Rentsch]

Christian Gollwitzer <auri...@gmx.de> writes:

> Am 17.07.19 um 23:29 schrieb Alf P. Steinbach:
>
>> On 17.07.2019 23:15, Mr Flibble wrote:
>>
>>> The whole point of using tail recursion is that is doesn't use
>>> up stack space, silly boy.
>>
>> Unfortunately the C++ standard gives you no such guarantee.
>>
>> But a particular compiler may.
>>
>> It's difficult to predict because it may not be documented for
>> the compiler, and the compiler may optimize or not based on
>> criteria that only make sense internally (e.g., is the return
>> type floating point?).
>
> Is it true that it depends on the type of something in practical
> cases?

The short answer is yes. (more below)

> I thought that tail recursion can be mechanically translated
> like this:
>
> ===========
> type myfunc(x, y, z) {
> ....
>
> return myFunc(a, b, c);
> }
> ===========
>
> becomes
>
> ==========
> type myfunc(x, y, z) {
> start:
>
> ...
>
> x=a, y=b, z=c;
> goto start;
>
> }
> ==========
>
> Since I can do this at the source code level, I don't see why it
> can't be done for every function. Of course, for mutual tail
> recursion I can't do that because of the non-local goto, but for
> the compiler that should also be easy.

I switch pretty easily (in C or C++) between functional style
code and imperative style code. So I routinely write small
functions using self-recursion, or sometimes mutual recursion
although that is less common. Of course I also want my code
to be practical so I do look at how the code is compiled,
sometimes with a visual inspection and sometimes using a
filter on the generated assembly to see where tail recursion
is compiled "badly", as a recursive call, rather than being
turned into a loop.

My experience is that direct tail recursion almost always[*] gets
turned into loops rather than recursive calls, if all the types
involved are scalar types (or references in C++). That also
holds for mutual recursion in cases where the functions involved
all have the same type (that is, the same return type and also
the same argument types, or at least "similar" argument types).
When the functions involved in a mutual recursion have different
numbers of arguments the results are not as reliable.

An important case that does *not* get compiled as iterative code
is when the return type is a struct (which I think also includes
unions). For some reason that happens even when the struct is
"simple", such as having only one member (and which has scalar
type). In C, using struct types for arguments is usually okay,
provided of course that they aren't too hairy. In C++, using
struct types for arguments often inhibits getting iterative
compiled code, even for "plain" structs. (Disclaimer: I haven't
explored what goes on when struct argument types are involved,
or more accurately I haven't explored it too deeply.)

On the flip side, a C++ case where recursion works great is
when constexpr functions are used to calculate constexpr
values. This property is important if one needs to write
constexpr functions that work in C++11 (and some people still
do), as in nearly all cases iterative code can be turned into
equivalent recursive code that adheres to the more restrictive
constraints for constexpr functions in C++11.


[*] Using gcc, clang, or g++, at optimization levels -Os/-O2 or
higher. Also, all the foregoing statements should be read as
most often true but not as absolutely true - there are always
the odd corner cases that can pop up, as with all things
programming.

[Tim Rentsch]

Jorgen Grahn <grahn...@snipabacken.se> writes:

> On Wed, 2019-07-17, Alf P. Steinbach wrote:
>
>> On 17.07.2019 07:03, Bob Langelaan wrote:
>>
>>> Several of my students have submitted the following solution (or
>>> something very similar) for a recursive function to add the contents
>>> of an array:
>>

>> The presented code doesn't ?add the contents?, I guess that's just typo.

>>
>>
>>> // Returns true if the supplied value is found in the array of values
>>> // and false otherwise
>>> template <typename type, size_t size>
>>> bool isMember(const array<type,size> & myArray, const int n, const type value)
>>> {
>>> if ( n < 0 )
>>> {
>>> return false;
>>> }
>>> else if ( myArray[n] == value )
>>> {
>>> return true;
>>> }
>>> return isMember( myArray, n - 1, value );
>>> }
>>
>> The two main problems with this function are:
>>
>> * Passing `value` by value may incur severe copying inefficiency.
>> * The tail recursion may easily consume all stack space and yield UB.
>
> It's also fairly sad and inelegant use of recursion, with the extra
> cursor being passed around. The way I learned recursion, you start by
> seeing an array as either empty, or having a head element, and then:
>
> // vaguely Haskell-like pseudo-code
> ismember(value, []) -> false
> ismember(value, head:tail) -> value==head || ismember(value, tail)
>
> My point is, I'm not sure the students will appreciate recursion
> properly based on that code, if that's the intention. (Perhaps not
> based on any C++ code.)

These comments strike me as somewhat odd. Certainly it is true
that recursive functions often offer a good fit to recursive data
types. That doesn't mean recursion is a bad fit in other cases.
On the contrary, using recursion often gives a definition that is
simpler and easier to understand than a non-recursive version. A
well-known example is finding the greatest common divisor of two
numbers, which might be written as follows (with gcd(0,0) to
return the value 1):

unsigned
gcd( unsigned a, unsigned b ){
return a == 0 ? b != 0 ? b : 1
: gcd( b%a, a );
}

Writing a nicely tail-recursive function often entails passing
arguments besides just the primary data item. This happens with
arrays in C and C++ because arrays are not recursive data types in
C or C++ (nor are they in many functional languages). Furthermore
we may want not one additional "cursor" but more than one. Here
is a function to determine if a sorted array contains a given
value:

bool
contains( int *v, size_t base, size_t limit, int item ){
if( base == limit ) return false;

size_t mid = base + (limit-base)/2;

if( v[mid] < item ) return contains( v, mid+1, limit, item );
if( v[mid] > item ) return contains( v, base, mid, item );

return true;
}

In later versions of C++ we might choose to write this function
differently, using 'span' (disclaimer: I am not an expert on
span!). Doing that would very likely give a nicer function. But
I wouldn't say the non-span version is "inelegant". It's just a
reflection of how the language-provided data types work. Do I
remember right that you are one of the people who is still
working (or forced to work) with C++11? Anyone in that boat
might choose a function definition like the one above, until such
time as better language facilities are available so it could be
re-written more attractively.

I guess my main point is that recursion is more broadly applicable
than just those situations where recursive data types are
involved. In fact, in languages like C and C++, it is much more
likely to encounter a good fit for recursion that does not make
use of recursive data types, simply because C and C++ typically do
not define data types recursively. Recursion is more fundamental
than just the cases where recursive data types are used.

[Tim Rentsch]

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

> On 19.07.2019 08:27, Christian Gollwitzer wrote:
>
>> Am 17.07.19 um 23:29 schrieb Alf P. Steinbach:
>>
>>> On 17.07.2019 23:15, Mr Flibble wrote:
>>>
>>>> The whole point of using tail recursion is that is doesn't use up
>>>> stack space, silly boy.
>>>
>>> Unfortunately the C++ standard gives you no such guarantee.
>>>
>>> But a particular compiler may.
>>>
>>> It's difficult to predict because it may not be documented for the
>>> compiler, and the compiler may optimize or not based on criteria
>>> that only make sense internally (e.g., is the return type floating
>>> point?).
>>
>> Is it true that it depends on the type of something in practical cases?
>
> Yes, it's the practical particular cases where it depends.
>
> For portable code it doesn't depend: you just have no guarantee and
> hence risk UB.
>
> And a risk of UB = UB.

Consider the following two function definitions:

#include <array>

using SomeType = double;
const unsigned long SomeFixedSize = 137;
using Array = ::std::array< SomeType, SomeFixedSize >;

bool
iterative_contains( Array & a, unsigned n, SomeType & v ){
while( n > 0 ){
if( a[n-1] == v ) return true;
n--;
}
return false;
}

bool
recursive_contains( Array & a, unsigned n, SomeType & v ){
return ! (n > 0) ? false
: a[n-1] == v ? true
: recursive_contains( a, n-1, v );
}

As far as the Standard is concerned these two functions are
semantically equivalent. They are equally well-defined. They
have exactly the same implications for observable behavior. If
one has undefined behavior then so does the other. If one has a
risk of undefined behavior then so does the other. A conforming
implementation may choose to compile an iterative definition into
recursive object code, as well as vice versa. So if you are going
to say the C++ standard gives you no guarantee about whether the
recursive function might result in undefined behavior, you should
also say the C++ standard gives you no guarantee about whether the
iterative function might result in undefined behavior.

>> I thought that tail recursion can be mechanically translated like this:
>>

>> [description]
>
> Modulo a number of caveats, yes. [...]

>
> * That for a debug build the compiler can't optimize away calls.
> Because you can't trace into a call if it's optimized away.

That depends what you mean by "debug build". In fact g++ will
compile recursive definitions into iterative object code even
when a -g or -ggdb option is given.

[Alf P. Steinbach]

If resource limits are not exceeded.


> They are equally well-defined.

Yes.

> They have exactly the same implications for observable behavior.

No.

> If one has undefined behavior then so does the other.

No.

> If one has a risk of undefined behavior then so does the other.

Repeating that claim doesn't make it less incorrect.

I'm pretty sure that you inadvertently repeated it because it was
orbiting in your mind, the key thing to communicate.

But it's trivially false: for a just some orders of magnitude larger
array size I can arrange to consistently crash the recursive function,
while the iterative one will be fine.

> A conforming
> implementation may choose to compile an iterative definition into
> recursive object code

No, absolutely not.

>, as well as vice versa.

Yes, it /can/ transform a recursive one to an iterative one that uses
less resources.

> So if you are going
> to say the C++ standard gives you no guarantee about whether the
> recursive function might result in undefined behavior, you should
> also say the C++ standard gives you no guarantee about whether the
> iterative function might result in undefined behavior.

That would follow if your premises were true, but they aren't.

However, it's not black and white only. /Any/ function runs the risk of
UB if it's called in a context where stack space is exhausted. It's just
that with an iterative function the stack space requirements are usually
fixed at compile time, i.e. constant, and generally reasonably small, so
that in practice it's like the difference between swimming from Norway
to the US, or taking a plane: both ways can get you there, but the
chance of succumbing or incurring severe health costs when one chooses
to swim, is very much higher. Saying that both ways can get you there
and that both ways run a risk, that swimming and flying are somehow on
equal terms, ignores the important real world aspects and focus on a
wholly unreasonable, dangerous academic simplification. As I see it.

And the C++ standard is a practical document. Or it was, until C++14.
Now it seems that reality-divorced academics unduly influence the
direction and details of the standard, in effect like saboteurs. That's
not a jab at you, but if you were on the committee and tried to
introduce language that permitted a compiler to rewrite an iterative
function as recursive, then that /would/ have been that kind of
in-effect-sabotage, and then I /would/ have used derogatory words. ;-)

>>> I thought that tail recursion can be mechanically translated like this:
>>>
>>> [description]
>>
>> Modulo a number of caveats, yes. [...]
>>
>> * That for a debug build the compiler can't optimize away calls.
>> Because you can't trace into a call if it's optimized away.
>
> That depends what you mean by "debug build". In fact g++ will
> compile recursive definitions into iterative object code even
> when a -g or -ggdb option is given.

What I mean by a "debug build" supports debugging.

Unless the debugging is about optimizations, a build with optimizations
is not a debug build, because it doesn't support general debugging.


Cheers!,

- Alf

[Tim Rentsch]

The semantics of a program is what is specified to happen in the
abstract machine. Resource limits come into play only when a
program is run on an actual machine; they have no bearing on
program semantics.

>> They are equally well-defined.
>
> Yes.
>
>
>> They have exactly the same implications for observable behavior.
>
> No.

Please outline a scenario in the abstract machine when the two
functions have different observable behavior.

>> If one has undefined behavior then so does the other.
>
> No.

Please outline a scenario in the abstract machine when one of the
two functions unconditionally has undefined behavior and the other
does not.

>> If one has a risk of undefined behavior then so does the other.
>
> Repeating that claim doesn't make it less incorrect.

It isn't the same claim. The first is about undefined behavior
that must occur, the second is about undefined behavior that
may occur but doesn't have to. (see next)

> I'm pretty sure that you inadvertently repeated it because it was
> orbiting in your mind, the key thing to communicate.

No, I made a separate point to address your individual idea of
what "undefined behavior" means. (As a side comment, other
people disagree with your view - see this SO question:

https://stackoverflow.com/questions/56811284/
does-this-program-with-bounded-recursion-have-undefined-behavior

in particular the most highly voted answer.)

> But it's trivially false: for a just some orders of magnitude
> larger array size I can arrange to consistently crash the
> recursive function, while the iterative one will be fine.

You point out later that /any/ function call can run out stack
space and so (under your view) has a risk of undefined behavior.
So my statement is trivially true.

>> A conforming
>> implementation may choose to compile an iterative definition into
>> recursive object code
>
> No, absolutely not.

Don't be silly, of course it can. The C and C++ standards don't say
anything about how a program is compiled except that the compiled
code has to match the observable behavior of the abstract machine.
In fact, very much the opposite: program semantics is defined in
terms of behavior in the abstract machine, and "conforming
implementations are required to emulate (only) the observable
behavior of the abstract machine". Observable behavior does not
include stack depth. Both the C and the C++ standard explicitly
give unbounded latitude as long as the observable behavior
requirement is met.

>> , as well as vice versa.
>
> Yes, it /can/ transform a recursive one to an iterative one that
> uses less resources.

I think you are confused about what "observable behavior" means.
Observable behavior does not depend on what resources are
available.

>> So if you are going
>> to say the C++ standard gives you no guarantee about whether the
>> recursive function might result in undefined behavior, you should
>> also say the C++ standard gives you no guarantee about whether the
>> iterative function might result in undefined behavior.
>
> That would follow if your premises were true, but they aren't.

You claim they aren't. Please support that claim by providing
one of the example scenarios I asked for above.

> However, it's not black and white only. /Any/ function runs the
> risk of UB if it's called in a context where stack space is
> exhausted. It's just that with an iterative function the stack
> space requirements are usually fixed at compile time, i.e. constant,
> and generally reasonably small, so that in practice it's like the
> difference between swimming from Norway to the US, or taking a
> plane: both ways can get you there, but the chance of succumbing or
> incurring severe health costs when one chooses to swim, is very much
> higher. Saying that both ways can get you there and that both ways
> run a risk, that swimming and flying are somehow on equal terms,
> ignores the important real world aspects and focus on a wholly
> unreasonable, dangerous academic simplification. As I see it.

Practical considerations are a separate concern, which I may take
up in a separate response.

> And the C++ standard is a practical document. Or it was, until
> C++14. Now it seems that reality-divorced academics unduly
> influence the direction and details of the standard, in effect like
> saboteurs. That's not a jab at you, but if you were on the
> committee and tried to introduce language that permitted a compiler
> to rewrite an iterative function as recursive, then that /would/
> have been that kind of in-effect-sabotage, and then I /would/ have
> used derogatory words. ;-)

The current standards, back to and including the original C89
standard, deliberately grant sufficient latitude to make arbitrarily
poor implementation choices as long as the observable behavior
requirement is met. I'm sure this was a conscious decision, and
not either an academic one or one divorced from reality. You are
very much swimming upstream here: do you really want to say you are
smarter than all the people who have participated in the C and C++
working groups to standardize these languages? I hope you will
understand if I view these last remarks with a fair amount of
skepticism.

[Alf P. Steinbach]

On 22.08.2019 19:28, Tim Rentsch wrote:
> You are
> very much swimming upstream here: do you really want to say you are
> smarter than all the people who have participated in the C and C++
> working groups to standardize these languages?

There are 3 main things wrong with that statement:

* The idea that I'm arguing a view at odds with the standard. I'm not.
Check how many in this group agree with your view of UB: that's 0.

* The idea that /if/ one believes the standard is sub-optimal or wrong,
one must believe that one is smarter than all the people blah blah. If
that were the case then all those non-committee members who have filed
Defect Reports against the standard, must be megalomaniacs who think
they're very very smart. That's just not so.

* It's a purely social argument.

> I hope you will
> understand if I view these last remarks with a fair amount of
> skepticism.

[Hark.]

I may address the rest of your posting later, trying to give the
examples etc. you ask for, because I feel you mean this seriously.

And I don't think you think you're smarter than everybody else in this
group just for holding an opinion on UB that nobody else here shares.

I think you're simply convinced that you're right, that your
distinctions are meaningful, and somehow my and others' arguments have
failed to move your conviction. Which I think means we're not good
enough at presenting our view. Not, that we're wrong. ;-)


Cheers!,

- Alf (fairly intelligent but at least now not at Mensa level :) )

[Ben Bacarisse]

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

<cut>

> And I don't think you think you're smarter than everybody else in this
> group just for holding an opinion on UB that nobody else here shares.

Why do you think no one else shares Tim's opinion? Tim has not said
anything here about UB that I disagree with. You have, but I've found
my life to be more pleasant if I don't reply to your posts, and anyway,
Tim has it covered.

--
Ben.

[Alf P. Steinbach]

On 23.08.2019 00:45, Ben Bacarisse wrote:
> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
> <cut>
>> And I don't think you think you're smarter than everybody else in this
>> group just for holding an opinion on UB that nobody else here shares.
>
> Why do you think no one else shares Tim's opinion?

Because he's been arguing his view for a very long time and nobody's
supported him.

Also because it's a totally impractical view so I'd not expect any
practitioner to support it.

> Tim has not said anything here about UB that I disagree with.

Well then, speak up in defense of his view.

> You have, but I've found
> my life to be more pleasant if I don't reply to your posts, and anyway,
> Tim has it covered.

If I have said things that you disagree with about UB, then most likely
so have everybody else who's responded to Tim on this subject. As far as
I recall you didn't speak up at any point, so your explanation, that
you're afraid of replying to /me/, just doesn't hold water.

So, your explanation for keeping silent appears to be an untruth that
you know is an untruth, anyway embedded in an ad hominem attack.

The thread has been civilized so far, but now (1) Tim has added a social
silly-argument (that to disagree with him one must think of oneself as
smarter than all people on the committee), and (2) you add an untruth
and an ad hominem attack.

That development of dishonest more social argumentation is probably
about something else than that you now suddenly feel you're losing a
technical debate.

Because you lost this debate very long ago: roughly nobody agree with
you that exceeding resource limits isn't UB. The standard says it is.
And that was noted early on, and repeated a gazillion times.


Cheers!,

- Alf

[Ben Bacarisse]

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

> On 23.08.2019 00:45, Ben Bacarisse wrote:
>> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>> <cut>
>>> And I don't think you think you're smarter than everybody else in this
>>> group just for holding an opinion on UB that nobody else here shares.
>>
>> Why do you think no one else shares Tim's opinion?
>
> Because he's been arguing his view for a very long time and nobody's
> supported him.

That's not a sound basis for making that assumption.

> Also because it's a totally impractical view so I'd not expect any
> practitioner to support it.

Impractical views can be correct. As it happens, I don't see this view
as an impractical one, but either way it can still be correct.

>> Tim has not said anything here about UB that I disagree with.
>
> Well then, speak up in defense of his view.

I don't see what I can add. Tim is a far better writer than I am and
has (I my opinion) put the case accurately and clearly. I don't hold
with the modern idea that my opinion matters, just because I have it. I
try to offer my opinion only when I can see some point in doing so.

I chipped in here only because I thought it would be useful to know that
silence can't be read as support for either one view or another.

>> You have, but I've found
>> my life to be more pleasant if I don't reply to your posts, and anyway,
>> Tim has it covered.
>
> If I have said things that you disagree with about UB, then most
> likely so have everybody else who's responded to Tim on this
> subject. As far as I recall you didn't speak up at any point, so your
> explanation, that you're afraid of replying to /me/, just doesn't hold
> water.

Sorry, it was not intended as an explanation for why I did not reply to
other people (and I did not say I was afraid to reply). There is no one
reason that will explain every time I choose more to post.

> So, your explanation for keeping silent appears to be an untruth that
> you know is an untruth, anyway embedded in an ad hominem attack.

Why the Latin? "ad hominem" brings to mind a logical fallacy, but I am
not making any logical argument at all. My remark was entirely
emotional. Whilst I enjoy reading your posts, I have not enjoyed my
reaction to our direct exchanges. That says as much about me as it does
your posts.

> The thread has been civilized so far, but now (1) Tim has added a
> social silly-argument (that to disagree with him one must think of
> oneself as smarter than all people on the committee), and (2) you add
> an untruth and an ad hominem attack.

I don't think it's uncivilised to say what I said, and I think it's an
extreme exaggeration to call what I wrote an attack. As I said, it's as
much about my reaction as it about your posting style.

> That development of dishonest more social argumentation is probably
> about something else than that you now suddenly feel you're losing a
> technical debate.

I am not engaged in a technical debate. I don't recall making any
technical contribution at all.

> Because you lost this debate very long ago: roughly nobody agree with
> you that exceeding resource limits isn't UB. The standard says it
> is. And that was noted early on, and repeated a gazillion times.

Then your replies make no sense to me. If it is so clearly settled (in
C++, I presume -- maybe C is different here), just cite the unequivocal
text that settles the matter. If anyone disagrees, cite the text
again.

--
Ben.

[James Kuyper]

On 8/23/19 1:22 AM, Alf P. Steinbach wrote:
> On 23.08.2019 00:45, Ben Bacarisse wrote:
>> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>> <cut>
>>> And I don't think you think you're smarter than everybody else in this
>>> group just for holding an opinion on UB that nobody else here shares.
>>
>> Why do you think no one else shares Tim's opinion?
>
> Because he's been arguing his view for a very long time and nobody's
> supported him.

I normally try (and often fail) to avoid paying attention to his posts,
because I've found discussions with him to be unproductive - when I
discuss my disagreements with him, we usually both end up wasting a lot
of time failing to convince each other. He's a lot like you in that regard.

He has a strong tendency to elevate what he believes to be the
committee's intent to play a larger role in the interpretation of the
standard than I think appropriate. This can be particularly annoying if
I disagree with him about what that intent was.
If the standard's wording is in conflict with (or even simply fails to
clearly express) the committee's intent, then that wording should be
corrected to clearly express that intent - but that discrepancy doesn't
change the meaning of the words that they actually wrote.

However, he is very knowledgeable about the standard, and he is correct
about the pre-eminence of a program's observable behavior. The
standard's definition of "observable behavior" is not "behavior which
can be observed" - it's far more specific than that:

"The least requirements on a conforming implementation are:
— Accesses through volatile glvalues are evaluated strictly according to
the rules of the abstract machine.
— At program termination, all data written into files shall be identical
to one of the possible results that
execution of the program according to the abstract semantics would have
produced.
— The input and output dynamics of interactive devices shall take place
in such a fashion that prompting
output is actually delivered before a program waits for input. What
constitutes an interactive device is
implementation-defined.
These collectively are referred to as the observable behavior of the
program. ..." (4.6p7).

The term "observable behavior" is in italics, an ISO convention
indicating that this sentence is the official definition of that term.
In the context of the C++ standard, that definition overrides any
alternative interpretation that might otherwise seem appropriate.

Note that the amount of stack space taken up by a program does not
qualify as "observable behavior".

The standard very explicitly says "The semantic descriptions in this
International Standard define a parameterized nondeterministic abstract
machine. This International Standard places no requirement on the
structure of conforming implementations. In particular, they need not
copy or emulate the structure of the abstract machine. Rather,

conforming implementations are required to emulate (only) the observable

behavior of the abstract machine as explained below." (4.6p1).

So if the same observable behavior can be achieved by using either an
iterative or a recursive algorithm, an implementation is free to use
either of those algorithms to achieve it, regardless of which algorithm
you actually expressed in your code. The fact that one algorithm runs a
higher risk of running out of stack space than the other imposes no
requirement on the implementation to avoid that risk (or to embrace it,
for that matter).

[Alf P. Steinbach]

On 23.08.2019 14:12, Ben Bacarisse wrote:
> If it is so clearly settled (in
> C++, I presume -- maybe C is different here), just cite the unequivocal
> text that settles the matter. If anyone disagrees, cite the text
> again.

That's what's been done, by others and by me.

And evidently that's not enough, but I've run out of ideas about what
would help.

Anyway, yet again, but for your convenience, first consider C++17 §1.4/2.1:
[quote]
If a program contains no violations of the rules in this International
Standard, a conforming implementation shall, within its resource limits,
accept and correctly execute that program.
[/quote]

There are no requirements, here or anywhere else in the standard, about
what should happen or not if the program is not executable within the
implementation's resource limits.

There is a requirement, the quoted text, if the the execution is within
the resource limits. There are no requirements otherwise.

And "no requirements" is the definition of Undefined Behavior.

C++17 §1.3.27
[quote]
1.3.27 [defns.undefined]
undefined behavior
behavior for which this International Standard imposes no requirements
[/quote]

One argument that has been made against this very clear and indisputable
(really) wording, is that it doesn't mean that the defined term is
equivalent to the stated definition, but rather that it just implies the
apparent definition. Thus, in that distorted view, UB would imply no
requirements, but no requirements would not necessarily imply UB.

A common example of the conventional view, the equivalence of "UB" and
"no requirements", is a `*p` dereferencing of a nullpointer outside of a
`typeid` expression.

Everybody (well, almost everybody!) agree that `*p` is Undefined
Behavior because the standard imposes no requirements about it.

If the one-way implication view was adopted, dereferencing that
nullpointer would no longer be UB.

The same goes for use of the referenced non-object, if any: in the
conventional view it's UB because there are no requirements. With the
one way implication view it's... what? I don't know, it just doesn't
make sense to me.

So, that view appears to be entirely silly, impractical, but the
discussion continues, at least for me, i.e. this is my personal reason,
because it's generally a good idea to flesh out what a so long standing
disagreement is about. One can learn things from that. Still I'm as far
as ever from understanding what it's really about.


Cheers,

- Alf

[David Brown]

Since we are expressing opinions - regardless of how much or little they
may be worth - I agree with James here. And as far as I can see, it is
the same as Tim has been saying in this regard.

Usually, changing an iterative algorithm into a recursive one will be a
pessimisation, taking more space and run-time. So it is highly unlikely
for a compiler to do this sort of thing - it would quickly become an
unpopular tool. But it is allowed to do so.

In the same way, between "int a = b + c;" and "int d = a * 2;", the
compiler is allowed to insert code calculating the first hundred digits
of pi - including the stack space needed for the job. It would be an
unpopular tool, but this would not affect the observable behaviour and
thus it would not affect the conformance of the compiler.

The standards do not impose any requirements on quality of
implementation (though they have a few hints here and there) - that is
up to the user.

[Alf P. Steinbach]

As an example, rewriting a function with loop that uses a fixed size
storage known at compile time, to a recursive function that uses storage
proportional to the function argument, changes the behavior.

With the original code one is guaranteed that it will complete.

With the recursive one one is not guaranteed completion, because for
large enough values of the parameter it will run out of stack space, an
implementation limit.

* * *

Essentially the argument about observable behavior is therefore that a
compiler is formally permitted to change a program that guarantees a
result if it compiles and loads, into a program that almost guaranteed
does not produce a correct result.

That's a perpetuum mobile construction argument. One doesn't necessarily
know where someone's logic went astray so that they ended up with a
perpetuum mobile design, but the end result is just not reality: it's
absurd. Somewhere in that argument there's necessarily something wrong,
and that's not a QoI issue.

> In the same way, between "int a = b + c;" and "int d = a * 2;", the
> compiler is allowed to insert code calculating the first hundred digits
> of pi - including the stack space needed for the job.

No, that's not the same way.

In this example a fixed storage requirement is not changed to a
requirement of storage depending on a parameter.

> It would be an
> unpopular tool, but this would not affect the observable behaviour and
> thus it would not affect the conformance of the compiler.

It would affect observable behavior. One would get wrong results or
crashes. Instead of with a conforming compiler, correct results.

> The standards do not impose any requirements on quality of
> implementation (though they have a few hints here and there) - that is
> up to the user.

That's right, but this isn't QoI, it's about correctness.


Cheers!,

- Alf

[Richard Damon]

The Standards unfortunately leave a LOT to QoI.

For instance, as far as I know, the compiler would be free to implement

unsigned i = 1;
unsigned j = 5;
unsigned k = i + j;

as
k = __add_uint(i, j);

where __add_uint() was defined as:

unsigned __add_uint(unsigned i, unsigned j) {
if(j) return __add_uint(++i, --j);
else return i;
}

You might even need something like this (but maybe iterative instead of
recursive) for a processor with very limited arithmetic operations (just
increment/decrement).

One such an implementation, the program

int main() {
unsigned i = 1U + 65000U;
}

might fail due to exhaustion of resources, and that is ok by the
standard. The Standard just requires that there be ONE program that
reaches all of the specified resource limits that the implementation can
process, any other program is allowed to fail for resource limits. This
'one program' rule is one of the big holes in the Standard (at least in
my opinion).

[James Kuyper]

On 8/23/19 5:07 PM, Alf P. Steinbach wrote:
> On 23.08.2019 16:37, David Brown wrote:
>> On 23/08/2019 15:28, James Kuyper wrote:

...

It doesn't change the observable behavior. Stack usage isn't observable.
The observable behavior won't occur at all if the program runs out of
stack space, but that's also a possibility for the iterative version of
the program, so it doesn't count as a difference in the observable behavior.

> With the original code one is guaranteed that it will complete.

From what do you derive that guarantee? What minimum amount of stack
does the standard require an implementation to provide? What upper limit
does the standard impose on the amount of stack used up by the iterative
version of that program?

In case you're having trouble locating the relevant clauses, let me give
you a hint: they don't exist. The standard doesn't say anything about
either issue. It says precisely as much about those issues for the
recursive version of the program as it does about the iterative version
- which is nothing at all.

What the standard does say that's relevant is "If a program contains no

violations of the rules in this International Standard, a conforming
implementation shall, within its resource limits, accept and correctly

execute 2 that program." (4.1p2). Note the key exception - "within its
resource limits". That's the phrase that gives the recursive version of
the program permission to fail if it runs out of stack; stack space is
one of the implementation's resources, and it is in fact limited. That
same phrase also gives the iterative version of the program permission
to fail, for precisely the same reason. The iterative version is less
likely to run out of stack space, but it's not guaranteed to have enough
stack space, any more than the recursive version is.

> Essentially the argument about observable behavior is therefore that a
> compiler is formally permitted to change a program that guarantees a
> result if it compiles and loads, into a program that almost guaranteed
> does not produce a correct result.

No, if the iterative version of the program was guaranteed to succeed,
this would not be a permitted rearrangement of the code. The only
relevant guarantee has an escape clause that can be used to justify
either version of the code failing.

> absurd. Somewhere in that argument there's necessarily something wrong,
> and that's not a QoI issue.

Having enough stack available to allow either version of the program to
complete is entirely a matter of QoI - the standard says nothing about
the issue, except to provide "resource limits" as a permissible reason
for a program to fail.

[Alf P. Steinbach]

The standard guarantees it. "shall ... within its resource limits ...
correctly execute that program".

When the resource requirements are known at compile time, there is no
question about it: if the program loads, and the provided resources are
sufficient for those known requirements, it will execute correctly.

> What minimum amount of stack
> does the standard require an implementation to provide?

The standard doesn't, AFAIK, say anything about minimum storage, but
that doesn't matter. When the program's resource requirements are known
at compile time one can provide sufficient resources for those known
requirements.

In practice, as you know, that's done by specifying the minimum stack
size in the build of the program, which ensures that it either loads and
runs correctly, or else fails to load. But conceivably it could be done
in other ways, even for each execution. However it's done, when a fixed
resource requirements program produced by a conforming compiler is run,
it produces a correct result.

One /can/ rely on a C++ program to produce correct results.

When one ensures that it will not exceed the implementation's resource
limits.

It's a different matter when the resource requirements are not known
until run time, as with a transformation from iterative to recursive.
Then one cannot in general provide guaranteed sufficient resources.
Instead one may end up with a program that always or nearly always
produce incorrect results, even, since this is the nature of UB, without
any indication that the results are wrong.

Note that such transformations include an implementation whose
executables, possibly except for `int main(){}`, /never/ work.

So then one /cannot/ rely on a C++ program to produce correct results.

Again, that a compiler can produce only non-functioning programs and
still be formally correct is absurd, only an interpretation for children
or academics. Such a compiler fails all requirements on a C++ compiler:
it's not a QoI issue. You're arguing that instead, like the watch that
just displays "NOW", it can be the most conforming compiler ever, whose
executables never do anything formally wrong, and that's meaningless.

> What upper limit
> does the standard impose on the amount of stack used up by the iterative
> version of that program?

That's an irrelevant nonsense question.

When the resource requirements are known at compile time, there is no
question about it: if the program loads, and the provided resources are
sufficient for those known requirements, it will execute correctly.


[snip]

[Alf P. Steinbach]

On 24.08.2019 01:10, Richard Damon wrote:
>
> The Standards unfortunately leave a LOT to QoI.
>
> For instance, as far as I know, the compiler would be free to implement
>
> unsigned i = 1;
> unsigned j = 5;
> unsigned k = i + j;
>
> as
> k = __add_uint(i, j);
>
> where __add_uint() was defined as:
>
> unsigned __add_uint(unsigned i, unsigned j) {
> if(j) return __add_uint(++i, --j);
> else return i;
> }
>

This is an argument by repeated assertion.

True, that's been the nature of the discussion so far. But in order to
break that cycle (if that's possible), I cut this sub-thread here, as
far as I'm concerned. Hopefully others won't chime in. :)


Cheers!,

- Alf

[Tim Rentsch]

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

> The thread has been civilized so far, but now (1) Tim has added a
> social silly-argument (that to disagree with him one must think of
> oneself as smarter than all people on the committee),

You have misunderstood me. My comment had nothing to do with
whether you agree (or disagree) with me.

I haven't had a chance yet to go through in detail the cascade of
messages following my posting upthread, but I thought I should
correct this misunderstanding right away.

[Bonita Montero]

> The whole point of using tail recursion is that is doesn't use up stack
> space, silly boy.

You can realistically rely on that a compiler will convert a tail
-recursion into an iteration when the code is optimized. But with
debug-code no compiler will convert the tail-recursion into an
iteration.

[David Brown]

Not as far as the language is concerned, no.

For the programmer, many things are important that are not covered by
the language itself. The same therefore applies to compilers.

But as far as language conformance goes - and that is what we are
discussing, /nothing/ else matters. It doesn't matter if the compiler
takes 15 years to finish compiling "Hello, world". It doesn't matter if
it uses 26 MB of ram for that program. It doesn't matter if it
generates the code as a Turing program and includes a simulator in the
exe file.

> With the original code one is guaranteed that it will complete.
>

Nonsense.

The C++ standards only describe how the language is interpreted and
certain aspects of the behaviour. They don't give guarantees about the
environment, resources, timings, etc.

The /compiler/ might give you more guarantees. The compiler distributor
might guarantee that the compiler will generate sane code or you get
your money back. (gcc guarantees that if the compiler breaks, you get
to keep both halves.)

But the C++ standards - the only things relevant for conformance - give
no such guarantees.

> With the recursive one one is not guaranteed completion, because for
> large enough values of the parameter it will run out of stack space, an
> implementation limit.
>
>   * * *
>
> Essentially the argument about observable behavior is therefore that a
> compiler is formally permitted to change a program that guarantees a
> result if it compiles and loads, into a program that almost guaranteed
> does not produce a correct result.

No. (You seem to be totally misunderstanding the concepts of observable
behaviour, C++ conformance, and the role of the language standard in
this post.)

The compiler can manipulate the code in any way, preserving the
observable behaviour, without affecting conformity. Resources don't
come into it - usually the compiler doesn't know the resources either.

It is not unknown, for real, quality compilers, for different choices of
compiler flags to result in programs that work in their target
environment or don't work - while the observable behaviour of the code
on a target with enough resources is unaffected. This can happen in
many ways in resource-constrained embedded systems - optimisation flag
choices can make the program too big for flash, use too much ram, too
much stack, take too long to run. But these aspects are usually beyond
the knowledge of the compiler, and are certainly well beyond the scope
of the standards - and therefore irrelevant for conformity.

>
> That's a perpetuum mobile construction argument. One doesn't necessarily
> know where someone's logic went astray so that they ended up with a
> perpetuum mobile design, but the end result is just not reality: it's
> absurd. Somewhere in that argument there's necessarily something wrong,
> and that's not a QoI issue.
>
>
>> In the same way, between "int a = b + c;" and "int d = a * 2;", the
>> compiler is allowed to insert code calculating the first hundred digits
>> of pi - including the stack space needed for the job.
>
> No, that's not the same way.
>
> In this example a fixed storage requirement is not changed to a
> requirement of storage depending on a parameter.

I am sure it would not stretch your imagination to adapt the example to
your liking. The compiler can insert code to calculate "a" digits of pi
between these two statements. Happy?

>
>
>>  It would be an
>> unpopular tool, but this would not affect the observable behaviour and
>> thus it would not affect the conformance of the compiler.
>
> It would affect observable behavior. One would get wrong results or
> crashes. Instead of with a conforming compiler, correct results.

No. Please re-read the part of the C++ standard explaining what
"observable behaviour" is in regards to the standards. It does /not/
mean "behaviour observed by the user".

>
>
>> The standards do not impose any requirements on quality of
>> implementation (though they have a few hints here and there) - that is
>> up to the user.
>
> That's right, but this isn't QoI, it's about correctness.
>

Yes - I'm correct, and you're wrong :-)

[David Brown]

On 24/08/2019 06:45, Alf P. Steinbach wrote:
> On 24.08.2019 01:49, James Kuyper wrote:
>> On 8/23/19 5:07 PM, Alf P. Steinbach wrote:
>>> On 23.08.2019 16:37, David Brown wrote:
>>>> On 23/08/2019 15:28, James Kuyper wrote:
>> ...

>> It doesn't change the observable behavior. Stack usage isn't observable.
>> The observable behavior won't occur at all if the program runs out of
>> stack space, but that's also a possibility for the iterative version of
>> the program, so it doesn't count as a difference in the observable
>> behavior.
>>
>>> With the original code one is guaranteed that it will complete.
>>
>>  From what do you derive that guarantee?
>
> The standard guarantees it. "shall ... within its resource limits ...
> correctly execute that program".
>
> When the resource requirements are known at compile time, there is no
> question about it: if the program loads, and the provided resources are
> sufficient for those known requirements, it will execute correctly.
>

The resource requirements most certainly are /not/ known at compile time
in general. There are exceptions, but they are very much exceptions -
for some kinds of embedded system development you can do enough static
analysis to be sure of stack usage (and typically you don't have heap
usage at all).

Are you suggesting that during the typical Windows program compilation,
the compiler knows the stack requirements of all functions called in
DLLs? Are you suggesting that during compilation, the compiler knows
the size of the RAM on the system it will run on? Are you suggesting
the compiler knows the size of the data files provided by the user?

>
>> What minimum amount of stack
>> does the standard require an implementation to provide?
>
> The standard doesn't, AFAIK, say anything about minimum storage, but
> that doesn't matter. When the program's resource requirements are known
> at compile time one can provide sufficient resources for those known
> requirements.

That's nice in theory, though completely unsupported by the standard and
completely missing in almost every practical case. I'm taking figures
out the air here, but I'd guess that for a minimum 99.9% of C and C++
programs, stack space either grows automatically as needed or the fixed
size is picked as "this is going to be /way/ more than we need".

>
> In practice, as you know, that's done by specifying the minimum stack
> size in the build of the program, which ensures that it either loads and
> runs correctly, or else fails to load.

That might be true in very limited practice. But you can't extrapolate
from experience of one Windows compiler and a misunderstanding of the
difference between a compiler and a linker, and assume it applies "in
practice" for other cases.

> But conceivably it could be done
> in other ways, even for each execution. However it's done, when a fixed
> resource requirements program produced by a conforming compiler is run,
> it produces a correct result.
>
> One /can/ rely on a C++ program to produce correct results.
>
> When one ensures that it will not exceed the implementation's resource
> limits.

Of course. The standards say as much.

>
> It's a different matter when the resource requirements are not known
> until run time, as with a transformation from iterative to recursive.

They are almost never known. Making a transformation from an iterative
to a recursive algorithm is likely to make stack requirements "more
unknown". And no one disagrees that that is a bad thing. But where you
are /wrong/ is thinking that avoiding such transformations makes stack
requirements known, or that it is remotely relevant to conformance or
observable behaviour as defined by the standards.

[Alf P. Steinbach]

On 25.08.2019 12:06, David Brown wrote:
> On 24/08/2019 06:45, Alf P. Steinbach wrote:
>> On 24.08.2019 01:49, James Kuyper wrote:
>>> On 8/23/19 5:07 PM, Alf P. Steinbach wrote:
>>>> On 23.08.2019 16:37, David Brown wrote:
>>>>> On 23/08/2019 15:28, James Kuyper wrote:
>>> ...
>
>>> It doesn't change the observable behavior. Stack usage isn't observable.
>>> The observable behavior won't occur at all if the program runs out of
>>> stack space, but that's also a possibility for the iterative version of
>>> the program, so it doesn't count as a difference in the observable
>>> behavior.
>>>
>>>> With the original code one is guaranteed that it will complete.
>>>
>>>  From what do you derive that guarantee?
>>
>> The standard guarantees it. "shall ... within its resource limits ...
>> correctly execute that program".
>>
>> When the resource requirements are known at compile time, there is no
>> question about it: if the program loads, and the provided resources are
>> sufficient for those known requirements, it will execute correctly.
>>
>
> The resource requirements most certainly are /not/ known at compile time
> in general.

What matters is that there are cases where the resource requirements are
known at compile time.

Those cases happen to include Tim's example.

The programming-in-general case is irrelevant for Tim's case, which
reduces to the absurd conclusion that no provably correct C++ program
can be made.


[snipalot associatively suggestive irrelevancies]

>> In practice, as you know, that's done by specifying the minimum stack
>> size in the build of the program, which ensures that it either loads and
>> runs correctly, or else fails to load.
>
> That might be true in very limited practice. But you can't extrapolate
> from experience of one Windows compiler and a misunderstanding of the
> difference between a compiler and a linker, and assume it applies "in
> practice" for other cases.

What misunderstanding of compiler and linker? What experience limited to
one Windows compiler?

Those are social arguments, arguing someone's extreme incompetence about
the very basics of tool use, in direct contradiction with what you know
about that person, and arguing someone's very limited experience of
platforms and compilers, also in direct contradiction with what you
know. Two untruths that you know are untrue, which means that you
intentionally lie. And they're presented as an ad hominem argument.

Which means that this argumentation you offer is not offered in good
faith, which means it's FUD.


[snip]

- Alf

[Alf P. Steinbach]

On 25.08.2019 11:36, David Brown wrote:
> On 23/08/2019 23:07, Alf P. Steinbach wrote:
>> On 23.08.2019 16:37, David Brown wrote:

>> [snip]

>>>  It would be an
>>> unpopular tool, but this would not affect the observable behaviour and
>>> thus it would not affect the conformance of the compiler.
>>
>> It would affect observable behavior. One would get wrong results or
>> crashes. Instead of with a conforming compiler, correct results.
>
> No. Please re-read the part of the C++ standard explaining what
> "observable behaviour" is in regards to the standards. It does /not/
> mean "behaviour observed by the user".

In your opinion results are not part of observable behavior.

That means you have defined yourself out of being taken seriously.


Cheers!,

- Alf

[David Brown]

For programs, rather than particular functions or parts of a program,
those cases are negligible outside of specialist cases in
high-reliability embedded programming. Agreed?

>
> Those cases happen to include Tim's example.

True. That applies to both the recursive and iterative versions of his
code.

>
> The programming-in-general case is irrelevant for Tim's case, which
> reduces to the absurd conclusion that no provably correct C++ program
> can be made.
>

In general, you can't prove that C++ programs are correct. It is, I
would think, very rare when you can do so. And even then the proof is
dependent and qualified - a program may be proven "correct for
conforming compilers", "correct for provably correct cpus (good luck
finding one)", and so on.

Provably correct programming is important - it forms a theoretical basis
on which practical work can be done. But it doesn't happen much in real
coding - it requires far too much detail, and far too many restrictions
and limitations for most work.

>
> [snipalot associatively suggestive irrelevancies]
>
>>> In practice, as you know, that's done by specifying the minimum stack
>>> size in the build of the program, which ensures that it either loads and
>>> runs correctly, or else fails to load.
>>
>> That might be true in very limited practice.  But you can't extrapolate
>> from experience of one Windows compiler and a misunderstanding of the
>> difference between a compiler and a linker, and assume it applies "in
>> practice" for other cases.
>
> What misunderstanding of compiler and linker? What experience limited to
> one Windows compiler?

Compilers do not know anything about stack size - at least, not for any
part involved in supporting the standard language. Information about
stack size is sometimes given to linkers, which can then be put in
OS-specific program headers or used during the linking process to make
the information available to the program.

And in many programs, on many systems, you don't specify the stack size
during build - you get the default for the system executing the program.

In Linux, for example, the default stack size is set by the environment
executing the program (and can be changed by the user). A running
program can also extend its own size at run time. There is no (AFAIK)
equivalent of the Windows PE header information about the required stack
size that could be set at link time.

On small embedded systems, you regularly set a desired stack size via
the linker, but never IME via the compiler. Equally regularly, your
stack size is simply from the top of ram working downwards until it hits
the heap growing upwards.

>
> Those are social arguments, arguing someone's extreme incompetence about
> the very basics of tool use, in direct contradiction with what you know
> about that person, and arguing someone's very limited experience of
> platforms and compilers, also in direct contradiction with what you
> know. Two untruths that you know are untrue, which means that you
> intentionally lie. And they're presented as an ad hominem argument.

Show me how the minimum stack size is set during build time with a range
of toolchains targetting a range of OS's, including "bare metal".
Otherwise, I believe you are extrapolating from limited experience.

There is nothing ad hominem about that - it is a statement of how your
claims appear. There is also nothing ad hominem about saying your posts
look like your experience here is highly focused on one platform, and
probably only one compiler. There is no suggestion that this makes you
a poorer programmer, or less competent - merely that it might be why you
are wrong about this point.

>
> Which means that this argumentation you offer is not offered in good
> faith, which means it's FUD.
>

Cut down on the paranoia, and you'll enjoy these discussions more.

[David Brown]

On 25/08/2019 13:27, Alf P. Steinbach wrote:
> On 25.08.2019 11:36, David Brown wrote:
>> On 23/08/2019 23:07, Alf P. Steinbach wrote:
>>> On 23.08.2019 16:37, David Brown wrote:
>>> [snip]
>>>>   It would be an
>>>> unpopular tool, but this would not affect the observable behaviour and
>>>> thus it would not affect the conformance of the compiler.
>>>
>>> It would affect observable behavior. One would get wrong results or
>>> crashes. Instead of with a conforming compiler, correct results.
>>
>> No.  Please re-read the part of the C++ standard explaining what
>> "observable behaviour" is in regards to the standards.  It does /not/
>> mean "behaviour observed by the user".
>
> In your opinion results are not part of observable behavior.

It is not /my/ opinion that matters here. (Personally, I can usually
observe the difference between programs that run as expected, and those
that crash or fail.) It is the /C++ standard definition/ of "observable
behaviour" that matters. Nothing else matters for conformity to the
standards. How can you find that so difficult?

Read 1.9 "Program Execution" of the standards. (That is the section
number from C++14, I expect it is similar in other versions.)

>
> That means you have defined yourself out of being taken seriously.
>

Complain to the C++ standards committee, not me.

[Alf P. Steinbach]

A compiler does know the size of a function's stack frame. It usually
emits instructions to adjust the stack pointer, as part of establishing
the frame, in the function prolog. So any C++ compiler knows a bit about
the stack size.

I think you meant something else than what you literally wrote.

But then, your argumentation against me has been about what I literally
wrote, with a bit of context removed.

> Information about
> stack size is sometimes given to linkers,

That's true, just as it would be true to say that it's sometimes given
to the compiler, which is often how the linker is invoked in C++.
Especially with g++ it's just too dang impractical to invoke ld directly
for linking of C++ code. One lets the front-end g++ do the job of
applying the requisite options for C++ linking.

I can't recall saying that a stack size option should be given to the
compiler, or to the linker, and you did not quote any such statement;
instead you quoted me writing "in the build". Which means you're again
trying to convey an impression that you know is false.

Which, again, is called lying.

Anyway your idea that such an option can only be given to the linker is
incorrect, and I know that you know that that is incorrect. With Visual
C++ the compiler option to set stack size is `/F<n>`. With g++ (and
hence clang) it can apparently only be given as a linker option, as
`--stack <n>`. But it can be given to the compiler, which forwards it,
as any linker option can, as `-Wl,--stack,<n>`, which for C++ would be
the preferred way due to raw use of `ld` being impractical.

Even if like me you don't go around remembering the specific options,
you're not an inexperienced novice that doesn't know about the basic
tool usage, so also this was a lie.

And again, I didn't specify how to do it, or using which of compiler and
linker: that would be in your fantasy, if you /believed/ what you wrote.

> which can then be put in
> OS-specific program headers or used during the linking process to make
> the information available to the program.
> > And in many programs, on many systems, you don't specify the stack size
> during build - you get the default for the system executing the program.
>
> In Linux, for example, the default stack size is set by the environment
> executing the program (and can be changed by the user). A running
> program can also extend its own size at run time. There is no (AFAIK)
> equivalent of the Windows PE header information about the required stack
> size that could be set at link time.

Yes, that's right, I failed to think of that. I've never needed to do
that. But then I continued, which you snipped,

"But conceivably it could be done in other ways, even for each
execution. However it's done, when a fixed resource requirements program
produced by a conforming compiler is run, it produces a correct result."

As I see it, "However it's done" covers the Linux way.

It's a little imperfection that you could have noted with fact, instead
of spewing out a series of personal lies.


> [snip]

>> Which means that this argumentation you offer is not offered in good
>> faith, which means it's FUD.
>>
>
> Cut down on the paranoia, and you'll enjoy these discussions more.

I decided some years ago to not let people get away with provable lies.

So I prove them.

That's not paranoia, and you know it.


Cheers,

- Alf

[David Brown]

Yes, a compiler knows a /bit/ about stack size. It doesn't know
everything. In particular, while it knows about the stack usage within
most functions, it rarely knows the usage of functions it calls,
especially if these are outside the current translation unit. It can't
know about functions linked at run-time, it rarely has a realistic call
tree of the functions in the program itself (since call trees are often
dynamic based on run-time properties), and it hasn't a hope when faced
with multiple threads, recursion, and call-backs.

>
> I think you meant something else than what you literally wrote.
>

I don't think I expressed myself very well. The standards don't cover
stack usage at all, in any way. And for anything outside the program
code, the compiler hasn't a clue. (I would be glad if object formats
/did/ included such information, at least for static linking.)

> But then, your argumentation against me has been about what I literally
> wrote, with a bit of context removed.
>
>
>> Information about
>> stack size is sometimes given to linkers,
>
> That's true, just as it would be true to say that it's sometimes given
> to the compiler, which is often how the linker is invoked in C++.

Until you are talking about link-time optimisation (when the build
process really gets complicated), the compiler typically does not invoke
the linker. (It's not good to be too categoric here - there are many
ways of organising tools.)

> Especially with g++ it's just too dang impractical to invoke ld directly
> for linking of C++ code. One lets the front-end g++ do the job of
> applying the requisite options for C++ linking.

Ah, I see what you are thinking about. But "g++" (or "gcc") is not the
compiler. It is a driver program, that calls the compiler, assembler,
linker, and other utilities as needed.

>
> I can't recall saying that a stack size option should be given to the
> compiler, or to the linker, and you did not quote any such statement;
> instead you quoted me writing "in the build". Which means you're again
> trying to convey an impression that you know is false.
>
> Which, again, is called lying.

No, lying would be making intentionally misleading and false statements.
I was certainly under the impression that you had said the stack size
was given to the compiler - if you didn't, then I made a mistake.

However, you have certainly made claims (unjustified in general) that
the compiler knows all about stack usage of the code, and that it knows
if the program's stack usage is within the stack available. I don't
know how you expect that to work out if the compiler doesn't know the
stack size available to the program.

>
> Anyway your idea that such an option can only be given to the linker is
> incorrect, and I know that you know that that is incorrect.

I didn't say anything like that. (But I accuse you of being mistaken,
not of lying.) I only said that was a common case, in my experience.

> With Visual
> C++ the compiler option to set stack size is `/F<n>`. With g++ (and
> hence clang) it can apparently only be given as a linker option, as
> `--stack <n>`. But it can be given to the compiler, which forwards it,
> as any linker option can, as `-Wl,--stack,<n>`, which for C++ would be
> the preferred way due to raw use of `ld` being impractical.

I don't know how MSVC handles this sort of thing. But for gcc, you are
giving the option to the /driver/ program, which passes it on to the
linker, not the compiler invocation. (The "-Wl," options are all passed
to the linker - certain other options are also passed to it.)

My guess - and it is only a guess - is that MSVC has a somewhat similar
system to gcc regarding the split between a driver program, the
compiler, and the linker (and assembler, and maybe compilers for other
languages, and assorted utilities).

>
> Even if like me you don't go around remembering the specific options,
> you're not an inexperienced novice that doesn't know about the basic
> tool usage, so also this was a lie.
>

I /do/ remember all sorts of specific options - probably more than is
healthy. But you were wrong about how gcc and the options work.

Please stop accusing me of lying. Tell me you think I'm wrong if you
think that is the case - I get things wrong sometimes. Tell me if you
think I've written something stupid or jumbled - I do that too. But I
am not lying, which is a different thing altogether.

> And again, I didn't specify how to do it, or using which of compiler and
> linker: that would be in your fantasy, if you /believed/ what you wrote.
>
>
>> which can then be put in
>> OS-specific program headers or used during the linking process to make
>> the information available to the program. > And in many programs, on
>> many systems, you don't specify the stack size
>> during build - you get the default for the system executing the program.
>>
>> In Linux, for example, the default stack size is set by the environment
>> executing the program (and can be changed by the user).  A running
>> program can also extend its own size at run time.  There is no (AFAIK)
>> equivalent of the Windows PE header information about the required stack
>> size that could be set at link time.
>
> Yes, that's right, I failed to think of that. I've never needed to do
> that. But then I continued, which you snipped,
>
> "But conceivably it could be done in other ways, even for each
> execution. However it's done, when a fixed resource requirements program
> produced by a conforming compiler is run, it produces a correct result."
>
> As I see it, "However it's done" covers the Linux way.

I didn't think it was worth commenting on everything you wrote.

Anyway, neither method in Linux (ulimit by the user, or a run-time call
within the program) lets the compiler know, at compile time, what stack
space is available to the program. (Conceivably, a compiler could take
a command-line switch for stack size and automatically generate a
run-time call to request that stack space at the start of main. I know
of no such compiler, but it is conceivable.) And this is all beside the
point as stack size is not relevant to conformity.

>
> It's a little imperfection that you could have noted with fact, instead
> of spewing out a series of personal lies.
>

If you accuse me of lying again, it will be the end of the discussion.

>
>> [snip]
>>> Which means that this argumentation you offer is not offered in good
>>> faith, which means it's FUD.
>>>
>>
>> Cut down on the paranoia, and you'll enjoy these discussions more.
>
> I decided some years ago to not let people get away with provable lies.
>

When people make mistakes, it can be helpful to correct them (especially
when the mistakes become a matter of public record). When people are
lying, they are usually not worth bothering about.

> So I prove them.

You have been factually inaccurate throughout the discussion.

>
> That's not paranoia, and you know it.
>

Do you /really/ think people would waste time concocting a web of lies
and deceits in a technical Usenet thread? To what purpose? Do you
think I (and others whom you also have accused of various types of
attack) am conducting some sort of personal vendetta against you,
perhaps to tarnish your reputation on Usenet? Do you perhaps think I am
trying to look good by making you look bad? Do you think I am so
insecure that I will lie myself into a deeper hole rather than admit to
being shown to be wrong? Or do you have some other theory? Few people
lie without very good reason - what do you think my reasons are?

Let me give you a clue - you are not /that/ important that anyone would
bother lying for your sake.

[James Kuyper]

On 8/25/19 7:27 AM, Alf P. Steinbach wrote:
> On 25.08.2019 11:36, David Brown wrote:
>> On 23/08/2019 23:07, Alf P. Steinbach wrote:
>>> On 23.08.2019 16:37, David Brown wrote:
>>> [snip]
>>>>  It would be an
>>>> unpopular tool, but this would not affect the observable behaviour and
>>>> thus it would not affect the conformance of the compiler.
>>>
>>> It would affect observable behavior. One would get wrong results or
>>> crashes. Instead of with a conforming compiler, correct results.
>>
>> No. Please re-read the part of the C++ standard explaining what
>> "observable behaviour" is in regards to the standards. It does /not/
>> mean "behaviour observed by the user".
>
> In your opinion results are not part of observable behavior.

No, certain kinds of results do qualify as observable behavior. The
problem is not the observable behavior, except insofar as stack usages
does NOT qualify as such. The problem is resource limits, and on systems
which use them, stack is definitely a resource with a finite limit.

Because an implementation is excused from executing programs correctly
when resource limits are exceeded, the requirement that observable
behavior must occur as specified by the standard applies only when
enough resources are available to execute the program. The standard
imposes no requirements on the minimum amount of resources that must be
available, nor on the maximum amount that may be required. In fact, the
standard says nothing at all about the particular resource (stack space)
that is relevant to this thread.

Therefore, the fact that a recursive implementation of a piece of code
may require more resources than an iterative one does not render
translation of iterative code into a recursive implementation
non-conforming. So long as both ways of implementing the code produce
the required observable behavior when sufficient resources are
available, it doesn't matter, as far as standard conformance is
concerned, that the amount of resources required to produce that
behavior is radically different for the two algorithms. That's purely an
issue of QoI, outside the scope of the C++ standard.

It was never intended to be the case that knowing that an implementation
of C++ is fully conforming would be sufficient to ensure that the
implementation is useful for any particular purpose (or indeed, for any
purpose whatsoever). Too many things that are relevant to usefulness are
outside the scope of the C++ standard, starting with the execution time
of C++ code, which is completely unspecified. If you consider the C++
standard to be impractical, that's because it was never intended to be
practical in that sense. You need to also evaluate the Quality of
Implementation (QoI) of a fully conforming implementation before you can
determine whether it's actually useful for anything.

[Alf P. Steinbach]

On 25.08.2019 23:32, David Brown wrote:
> Do you /really/ think people would waste time concocting a web of lies
> and deceits in a technical Usenet thread?

That's proved again and again. Including in this thread.


> To what purpose?

I don't know, because it's apparently irrational. My pet theory is that
it springs from the basic human instincts, in particular the strongest
one, that of belonging to and defending a group. But then there is also
the copy-cat behaviors and other even more unfathomable reasons.

> Do you think I (and others whom you also have accused of various types of
> attack) am conducting some sort of personal vendetta against you,
> perhaps to tarnish your reputation on Usenet?

No, that's not in your nature. I was surprised some weeks ago when I
first saw this kind of irrationality from you, but that was because it
didn't have a context. Now there is a context with your innuendo etc.
forming part of a herd response: first someone in another thread, which
I don't recall exactly what, then shortly after Tim in this thread
pointed out that disagreement with his meaningless notion (that you've
not adopted) mean to think one was smarter than everybody on the
committee, i.e. that I'm a megalomanicac; then someone else in this
thread with innuendo that he was afraid to respond to me, i.e. that I'm
a bully; then you also in this thread asserting that I'm an
inexperienced novice and that by proving the provable lies of yours, I
am most likely paranoid.

Even though I don't remember the other-thread first, the upshot from
this thread is that I'm an inexperienced novice who happens to be a
megalomaniac paranoid bully.

> Do you perhaps think I am trying to look good by making you look bad?

You have made yourself look bad, by jumping on the bandwagon.

> Do you think I am so insecure that I will lie myself into a deeper
> hole rather than admit to being shown to be wrong? Or do you have
> some other theory? Few people lie without very good reason

That happens to be contrary to established stats.

Most people lie in everyday conversations. The difference is that those
lies are not necessarily designed to have negative impact for others.

E.g., first google result about that,
<url:
https://www.eurekalert.org/pub_releases/2002-06/uoma-urf061002.php>,
"UMass researcher finds most people lie in everyday conversation".

> - what do you think my reasons are?

Given that this has been an avalanche of quite sudden onset, comprising
at least 4 persons in the "we use C a lot and love gcc" camp using
strongly negative ad hominem attacks,

I think it's probably connected to a feeling of protecting that group or
a larger group. Maybe I've insulted some of you, or maybe I was too hard
against the first person. Something like that.

Anyway I believe it's instinct-driven behavior.

> Let me give you a clue - you are not /that/ important that anyone would
> bother lying for your sake.

Here you go again, speculating that (1) I think I'm a very important person.

That's on top of the speculations so far that I'm (2) an inexperienced
(3) novice who is (4) a paranoid (5) megalomaniac.

Have you heard the expression, to “butter the bacon”? :-D
<url: https://www.youtube.com/watch?v=WYns5vR3QuQ>

* * *

But of course this shows to any reader, e.g. a prospective employer, not
that I am any of those things, but that I clearly fail to fit in with a
group of C/C++ (as opposed to pure C++) programmers; that I fail to
accept a nonsense belief in order to fit in, which is often important in
Norway; and that I have been subject to the said group's herd exclusion.

Happily that doesn't matter.


Cheers,

- Alf

[David Brown]

On 26/08/2019 11:51, Alf P. Steinbach wrote:

>> Do you perhaps think I am  trying to look good by making you look bad?
>
> You have made yourself look bad, by jumping on the bandwagon.
>

Then I'm jumping off.

I haven't been lying, and I haven't been insulting you or attacking you.
If you feel that I have, then I think that says more about you than it
does about me. And since I have no desire to attack or insult you, but
apparently have done so unintentionally when trying to discuss
technicalities of the C++ language and tools, I guess it's better not to
discuss C++ with you.

I am not a "plonker", and will continue to read your posts (sometimes
you write things that are interesting or inspirational to me), and I
might well reply to you in the future. But for now at least, this
thread is better off ending.

> Happily that doesn't matter.
>

On that we agree.

[Tim Rentsch]

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

> On 22.08.2019 19:28, Tim Rentsch wrote:
>
>> You are
>> very much swimming upstream here: do you really want to say you are
>> smarter than all the people who have participated in the C and C++
>> working groups to standardize these languages?

I am still in the process of reading through the cascade of
downstream messages, but I wanted to respond to this one item
and try to get it out of the way.

> There are 3 main things wrong with that statement:
>
> * The idea that I'm arguing a view at odds with the standard. I'm
> not. Check how many in this group agree with your view of UB: that's
> 0.

The comment of mine quoted above has nothing to do with undefined
behavior or your ideas about it. You have misunderstood the context
of the comment.

> * The idea that /if/ one believes the standard is sub-optimal or
> wrong, one must believe that one is smarter than all the people blah
> blah. If that were the case then all those non-committee members who
> have filed Defect Reports against the standard, must be megalomaniacs
> who think they're very very smart. That's just not so.

First, I never said you think you're smarter than everyone who
has worked on the C or C++ standards. Second, I never said
someone who thinks the Standard is flawed in some way (and thus
in contradiction to all the committee members who have worked on
it) must be wrong about that. You have misheard me. ISTM that
often what you hear doesn't match what I said; whether or not
it happens often, it did happen in this case.

As regards defect reports, several items are worth noting. One,
most defect reports are filed by people either who are on the
committee or who have spent extensive time working with them.
Two, a lot of defect reports are responded to by saying, in
essence, "this isn't a problem, the standard is fine." (I don't
know what the percentages are, for any of the classes of filers.)
Three, most defect reports involve issues that are odd corner
cases in one way or another, and probably just got overlooked.
In contrast, the notion of observable behavior is a core issue,
and undoubtedly one that has been given a lot of attention and
serious thought. The people who worked on C89-C99 are by nature
a practical, pragmatic bunch, and not particularly given to
academic flights of fancy. Given that the notion of observable
behavior (not the name, but the ideas behind it) has survived
essentially unchanged to the present day, the idea that it is
impractical or overly academic in nature is rightly regarded
with some skepticism. And that's all I was saying.

> * It's a purely social argument.

It isn't a social argument; rather it is an argument of
technical competence and one reflecting the nature of the people
who worked on the early C standards.

If anything, your argument that my ideas about undefined behavior
must be wrong because no one in comp.lang.c++ agrees with me is
a social argument. Even if it were true (which it isn't) that no
one here agrees with me, comp.lang.c++ is a social collection of
people, as are the subsets that choose to participate in various
threads and topics. So if anyone is making a social argument,
it's you.

[Tim Rentsch]

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

I have now carefully read through all your responses in the
cascade of messages downstream of my message two upthread.

> I may address the rest of your posting later, trying to give the
> examples etc. you ask for, because I feel you mean this seriously.

I do mean it seriously, and not at all confrontationally. I am
interested to read your further followup (ie, as mentioned above)
if you choose to post one.

> And I don't think you think you're smarter than everybody else in
> this group just for holding an opinion on UB that nobody else here
> shares.

For the most part I don't think about whether I am smarter than
any particular person, let alone everyone in the group, partly
because "smart" is a multi-dimensional quantity, and it's very
rare (if indeed it has ever happened at all) that I find a person
where I think I am smarter along all axes. Even if it were true
that my opinion on a subject were not shared by any other
contributor in the group, that would not affect my sense of what
"smarter" means.


> I think you're simply convinced that you're right,

In my view the word "right" does not apply, because I take both
of our statements as expressing opinions about how the standards
"should" be interpreted. Opinions are never right or wrong, they
just are whatever they are.

> that your distinctions are meaningful,

I do think the distinctions I have been trying to explain are
meaningful.

> and somehow my and others' arguments have failed to move your
> conviction.

I think an essential first step is missing. For my views to
change as a result of what you say (or vice versa), I must first
understand what you mean and why you think what you do (similarly
vice versa). Right now I think we are not understanding each
other. Key example: the term "undefined behavior". Even though
we both use the term "undefined behavior", I think what you mean
by the term is not the same as what I mean by it. If that is so
then obviously it gets in the way of us communicating. Normally
in discussions like this one, my efforts are directed at trying
to convey what I think and why, and not to try to convince the
other participant(s) to change their minds.


> Which I think means we're not good enough at presenting our
> view. Not, that we're wrong. ;-)

Again, I don't think either of our views is right or wrong. I
agree though that explaining what it is you think should be given
more emphasis than trying to convince me that you're right.

[Tim Rentsch]

Ben Bacarisse <ben.u...@bsb.me.uk> writes:

> Tim is a far better writer than I am [...]

I'm not sure I deserve this compliment but I do very much
appreciate it.