Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #67072 > unrolled thread

Why does this work on Xcode ???

Back to article view | Back to comp.lang.c++

Contents

  Why does this work on Xcode ??? Bob Langelaan <bobl0456@gmail.com> - 2019-07-16 22:03 -0700
    Re: Why does this work on Xcode ??? Paavo Helde <myfirstname@osa.pri.ee> - 2019-07-17 08:46 +0300
    Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-17 00:06 -0700
      Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-17 01:44 -0700
    Re: Why does this work on Xcode ??? Juha Nieminen <nospam@thanks.invalid> - 2019-07-17 07:46 +0000
    Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-07-17 09:12 -0400
    Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-17 17:01 +0200
      Re: Why does this work on Xcode ??? Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2019-07-17 22:15 +0100
        Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-17 23:29 +0200
          Re: Why does this work on Xcode ??? Christian Gollwitzer <auriocus@gmx.de> - 2019-07-19 08:27 +0200
            Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-19 09:09 +0200
              Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-19 09:24 +0200
              Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-10 11:18 -0700
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-10 21:05 +0200
                  Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-22 10:28 -0700
                    Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-22 19:50 +0200
                      Re: Why does this work on Xcode ??? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-22 23:45 +0100
                        Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 07:22 +0200
                          Re: Why does this work on Xcode ??? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-23 13:12 +0100
                            Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 16:02 +0200
                            Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-09-18 08:50 -0700
                          Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-23 09:28 -0400
                            Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-23 16:37 +0200
                              Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 23:07 +0200
                                Re: Why does this work on Xcode ??? Richard Damon <Richard@Damon-Family.org> - 2019-08-23 19:10 -0400
                                  Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-24 06:49 +0200
                                Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-23 19:49 -0400
                                  Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-24 06:45 +0200
                                    Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 12:06 +0200
                                      Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 13:25 +0200
                                        Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 15:11 +0200
                                          Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 17:12 +0200
                                            Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 23:32 +0200
                                              Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-26 11:51 +0200
                                                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-26 13:26 +0200
                                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 11:36 +0200
                                  Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 13:27 +0200
                                    Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 15:15 +0200
                                    Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-26 00:43 -0400
                          Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-24 04:58 -0700
                      Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-26 09:53 -0700
                      Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-28 18:03 -0700
            Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-19 00:20 -0700
            Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-09 07:41 -0700
        Re: Why does this work on Xcode ??? Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-24 19:49 +0200
      Re: Why does this work on Xcode ??? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-07-21 11:41 +0000
        Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-10 09:29 -0700

Page 1 of 3  [1] 2 3  Next page →

#67072 — Why does this work on Xcode ???

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.

[toc] | [next] | [standalone]

#67074

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.

[toc] | [prev] | [next] | [standalone]

#67076

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.

[toc] | [prev] | [next] | [standalone]

#67082

On Wednesday, 17 July 2019 10:06:39 UTC+3, Öö Tiib  wrote:
> 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.

Sorry, gcc has -D_GLIBCXX_DEBUG

[toc] | [prev] | [next] | [standalone]

#67080

Bob Langelaan <bobl0456@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).

[toc] | [prev] | [next] | [standalone]

#67086

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

[toc] | [prev] | [next] | [standalone]

#67092

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

[toc] | [prev] | [next] | [standalone]

#67102

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

[toc] | [prev] | [next] | [standalone]

#67103

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

[toc] | [prev] | [next] | [standalone]

#67113

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

[toc] | [prev] | [next] | [standalone]

#67114

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

[toc] | [prev] | [next] | [standalone]

#67116

On 19.07.2019 09:09, Alf P. Steinbach wrote:
> 
> 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.

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

[toc] | [prev] | [next] | [standalone]

#67532

"Alf P. Steinbach" <alf.p.steinbach+usenet@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.

[toc] | [prev] | [next] | [standalone]

#67533

On 10.08.2019 20:18, Tim Rentsch wrote:
> "Alf P. Steinbach" <alf.p.steinbach+usenet@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.

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

[toc] | [prev] | [next] | [standalone]

#67881

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> writes:

> On 10.08.2019 20:18, Tim Rentsch wrote:
>
>> "Alf P. Steinbach" <alf.p.steinbach+usenet@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.
>
> If resource limits are not exceeded.

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.

[toc] | [prev] | [next] | [standalone]

#67883

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

[toc] | [prev] | [next] | [standalone]

#67893

"Alf P. Steinbach" <alf.p.steinbach+usenet@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.

[toc] | [prev] | [next] | [standalone]

#67898

On 23.08.2019 00:45, Ben Bacarisse wrote:
> "Alf P. Steinbach" <alf.p.steinbach+usenet@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

[toc] | [prev] | [next] | [standalone]

#67903

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> writes:

> On 23.08.2019 00:45, Ben Bacarisse wrote:
>> "Alf P. Steinbach" <alf.p.steinbach+usenet@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.

[toc] | [prev] | [next] | [standalone]

#67908

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c++

csiph-web