Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #67881
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: Why does this work on Xcode ??? |
| Date | 2019-08-22 10:28 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <86v9upglek.fsf@mailhub.linuxsc.com> (permalink) |
| References | (3 earlier) <qgo3vt$6ti$1@dont-email.me> <qgrnrq$ud9$1@dont-email.me> <qgrqbu$9th$1@dont-email.me> <86lfw0994w.fsf@mailhub.linuxsc.com> <qin4h5$4jb$1@dont-email.me> |
"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.
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web