Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: Why does this work on Xcode ???
Date: Sat, 10 Aug 2019 11:18:39 -0700
Organization: A noiseless patient Spider
Lines: 78
Message-ID: <86lfw0994w.fsf@mailhub.linuxsc.com>
References: <1b10612f-47b9-4097-be59-d00dec4a800b@googlegroups.com> <qgnd93$tap$1@dont-email.me> <odMXE.11583$0A3.11258@fx21.fr7> <qgo3vt$6ti$1@dont-email.me> <qgrnrq$ud9$1@dont-email.me> <qgrqbu$9th$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="4bad90a7c43721789c432acb03dbc8ee"; logging-data="20262"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19c2QlfD719RZLRNSAhpaeIkFdEPvHPWa4="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:mJsmukgpjaDUbxKfrw3jQCaEZoA= sha1:hVZ2BRsocLAoWxRlHLUyZdEi71k=
Xref: csiph.com comp.lang.c++: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.