Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c++ Subject: Re: Why does this work on Xcode ??? Date: Thu, 22 Aug 2019 10:28:03 -0700 Organization: A noiseless patient Spider Lines: 191 Message-ID: <86v9upglek.fsf@mailhub.linuxsc.com> References: <1b10612f-47b9-4097-be59-d00dec4a800b@googlegroups.com> <86lfw0994w.fsf@mailhub.linuxsc.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="59398aca864cd103291b848dd2e1e135"; logging-data="32291"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/agj2N8LxpOeAc3AeoAGvI6m2UDBvYg18=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:DPlBF1uwJF6iacsLyPxrmmQ4Uxw= sha1:ssVoXHv56JqLV/VXuszyH8ONZA4= Xref: csiph.com comp.lang.c++:67881 "Alf P. Steinbach" writes: > On 10.08.2019 20:18, Tim Rentsch wrote: > >> "Alf P. Steinbach" 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 >> >> 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.