Gabor Greif wrote:
> On Thu, Sep 16, 1999 6:20 Uhr, Bill Wade <mailto:bill.wade@stoner.com>
> wrote:
> >[...]  Also the presence of destructors make it problematical
> >
> >struct foo { ~foo(); };
> >void bar()
> >{
> >  foo a;
> >  if(something())
> >   bar();
> >}
> >
> >Only a very stupid or a very smart compiler will perform the tail recursion
> >optimization, since the language requires that a.~foo() be called after the
> >recursive call returns.
>
> [...] Maybe Ahn Ki-yung is interested in the answer to this question:
>
> Are there any implementations of standard C++ that can perform tail-call
> optimization?

The ARM C++ compiler performs tail-call optimization when possible.  It's a
useful thing to do even when the tail-call isn't recursive, e.g. forwarding
functions.  It's not possible[1] to do the optimization if there is any "live"
local variable, e.g. a local variable that is still in scope and has a
non-trivial destructor (e.g. 'a' above) or has had it's address taken, e.g.:

int *g;
void baz();
void bar2(int i)
{
  g = &i;
  baz(); // tail-call not possible[1]; 'baz' may 'i' through 'g'
}

Because a destructor gets a 'this' pointer it is not possible[1] to tail-call
them either.  If the destructor is trivial or inline then things are different.

[1] in a straight-forward way (No, I don't know a non-straight-forward way
either but I bet someone could come up with some alloca-like trick.)


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Thu, Sep 16, 1999 6:20 Uhr, Bill Wade <mailto:bill.wade@stoner.com>
wrote:
>Ahn Ki-yung wrote in message <37DC433F.FDF66A81@daidun.kaist.ac.kr>...
>>In functional laguages the it is required that
>>tail recursion should be optimized by interpreter
>>or compiler of the language. I have two questions.
>>
>>Is it so in C++ ?
>
>No.  Also the presence of destructors make it problematical
>
>struct foo { ~foo(); };
>
>void bar()
>{
>  foo a;
>  if(something())
>   bar();
>}
>
>Only a very stupid or a very smart compiler will perform the tail
recursion
>optimization, since the language requires that a.~foo() be called after
the
>recursive call returns.
>

I would second what you say, but I have to add that the call to bar in your
example is not in tail position _because_ of the semantics of destructors.
So I would never expect it to be optimized. In C++ an expression _looking_
to be in tail position does not always _is_ a tail position. Maybe Ahn
Ki-yung is interested in the answer to this question:

Are there any implementations of standard C++ that can perform tail-call
optimization?

I have heard that the gnu compilers can be optioned in such a behaviour, is
this still true?

Certainly the C++ standard does not mandate an implementation to perform
tail-call optimization. Also, most functional languages do not require
tail-call optimization as opposed to the original assertion (with Scheme
and Dylan, ML? being notable exceptions).

 Gabor




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard wrote:
>
> blargg wrote:
>
> > In article <yJcD3.972$m84.27043@burlma1-snr2>, Barry Margolin
> > <barmar@bbnplanet.com> wrote:
>
> > > No, C++ does not require tail recursion optimization.
>
> > Can a conforming program even tell?
>
> Is
>
>   void foo () { foo (); }
>
> equivalent with
>
>   void foo () {for(;;);}

Guess it depends on the implementation. On a non-optimizing compiler on
a 'traditional' system[1], I'd expect the second to push CPU usage to
100% and stay there indefinitely. I'd expect the first to push CPU usage
to 100% and stay there until the computer ran out of stack space.

Adam

[1] Meaning your common-or-garden command-line-based OS with a
directory-based filesystem and such, along with a 'cc'-style compiler.
YMMV on other systems.

--
Why is it that the smaller and easier a bug is to fix, the less I want
to actually fix it?

----------------
The opinions expressed in this email are mine alone, and do not
neccesarily represent those of my employer, my parents, or the people
who wrote the email software I use.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <Bonnard.V@wanadoo.fr> writes:

| Gabriel Dos_Reis wrote:
|
| > Well, Valentin's point was that
| >
| >         void foo() { foo(); }
| >
| > isn't equivalent to
| >
| >         void foo() { foo(;;); }
| >
| > as far as observable behaviour is concerned.  I disagree with
| > with him according to 1.9/6.
|
| Which means that, under a conforming implementation, the
| following program can core dump:
|
| int main(){}
|
| even if enougth ressources are available.
|
| > Whether an implementation should make tail recursion optimization
| > depends entirely on that implementation's audience.  But the C++
| > definition doesn't pevent it to do so.
|
| But don't worry: if the committee wanted to mandate
| tail-recursion it would have done so.

No, I don't think so.  In various places, the committee deliberatly
decided not to mandate several useful optimizations (e.g. the named
and unnamed return value optimizations); instead it says that
implementations are *permitted* to do funny things which make
well-formed programs observable behaviours -with the same input data-
highly unreproducible.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

blargg wrote:

> In article <yJcD3.972$m84.27043@burlma1-snr2>, Barry Margolin
> <barmar@bbnplanet.com> wrote:

> > No, C++ does not require tail recursion optimization.

> Can a conforming program even tell?

Is

  void foo () { foo (); }

equivalent with

  void foo () {for(;;);}

--

Valentin Bonnard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <Bonnard.V@wanadoo.fr> writes:

| blargg wrote:
|
| > In article <yJcD3.972$m84.27043@burlma1-snr2>, Barry Margolin
| > <barmar@bbnplanet.com> wrote:
|
| > > No, C++ does not require tail recursion optimization.
|
| > Can a conforming program even tell?
|
| Is
|
|   void foo () { foo (); }
|
| equivalent with
|
|   void foo () {for(;;);}

Yes, as far as the observable behaviour is concerned.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Gabriel Dos_Reis wrote:

> Valentin Bonnard <Bonnard.V@wanadoo.fr> writes:
>
> | blargg wrote:
> |
> | > In article <yJcD3.972$m84.27043@burlma1-snr2>, Barry Margolin
> | > <barmar@bbnplanet.com> wrote:
> |
> | > > No, C++ does not require tail recursion optimization.
> |
> | > Can a conforming program even tell?
> |
> | Is
> |
> |   void foo () { foo (); }
> |
> | equivalent with
> |
> |   void foo () {for(;;);}
>
> Yes, as far as the observable behaviour is concerned.

Yet, the first one outputs

  zsh: segmentation fault  ./a.out

which can only be undefined behaviour, while the second one
doesn't (yet). This is different (to me).

--

Valentin Bonnard


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <Bonnard.V@wanadoo.fr> writes:

| Gabriel Dos_Reis wrote:
|
| > Valentin Bonnard <Bonnard.V@wanadoo.fr> writes:
| >
| > | blargg wrote:
| > |
| > | > In article <yJcD3.972$m84.27043@burlma1-snr2>, Barry Margolin
| > | > <barmar@bbnplanet.com> wrote:
| > |
| > | > > No, C++ does not require tail recursion optimization.
| > |
| > | > Can a conforming program even tell?
| > |
| > | Is
| > |
| > |   void foo () { foo (); }
| > |
| > | equivalent with
| > |
| > |   void foo () {for(;;);}
| >
| > Yes, as far as the observable behaviour is concerned.
|
| Yet, the first one outputs
|
|   zsh: segmentation fault  ./a.out

That isn't an observale behaviour as per 1.9/6.

| which can only be undefined behaviour, while the second one
| doesn't (yet). This is different (to me).

Well, can you tell us what you think thses programs' observable
behavior should be?

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In the LISP world, specifications require tail recursion optimization to
make it clear to programmers what to expect from an implementation. (I.e.
you can write tail recursive code as readily as you would write iterative
code.) A programmer can certainly tell if the implementation meets the
requirement. Writing an automated test case is more difficult, but there
are ways to do it. (Generally running two versions of the same routine and
measuring their runtimes and memory usage. Or writing a routine that will
use more stack space than any machine available has if it is not optimized
properly.)

The whole concept of specifying quality of implementation constraints
really doesn't come up in C/C++ standardization. (I'm not passing judgement
here. Merely pointing out a difference in the cultures involved.)

As a practical matter, when writing C++ code, it definitely pays to use an
iterative style. (Of course if you have an inherently recursive algorithm,
then use recursion, but tail recursion optimization wouldn't help there
anyway.)

-Z-


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Zalman Stern <zalman@netcom6.netcom.com> writes:

[...]

| The whole concept of specifying quality of implementation constraints
| really doesn't come up in C/C++ standardization. (I'm not passing judgement
| here. Merely pointing out a difference in the cultures involved.)

I think that concept is actually present in the C++ definition through
the notion of observable behaviour, but good quality of implementation
isn't mandated.  Instead it's left to the market place to make such a
prescription.

| As a practical matter, when writing C++ code, it definitely pays to use an
| iterative style. (Of course if you have an inherently recursive algorithm,
| then use recursion, but tail recursion optimization wouldn't help there
| anyway.)


Well, Valentin's point was that

 void foo() { foo(); }

isn't equivalent to

 void foo() { foo(;;); }

as far as observable behaviour is concerned.  I disagree with
with him according to 1.9/6.

Whether an implementation should make tail recursion optimization
depends entirely on that implementation's audience.  But the C++
definition doesn't pevent it to do so.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Gabriel Dos_Reis wrote:

> Well, Valentin's point was that
>
>         void foo() { foo(); }
>
> isn't equivalent to
>
>         void foo() { foo(;;); }
>
> as far as observable behaviour is concerned.  I disagree with
> with him according to 1.9/6.

Which means that, under a conforming implementation, the
following program can core dump:

int main(){}

even if enougth ressources are available.

> Whether an implementation should make tail recursion optimization
> depends entirely on that implementation's audience.  But the C++
> definition doesn't pevent it to do so.

But don't worry: if the committee wanted to mandate
tail-recursion it would have done so.

--

Valentin Bonnard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <yJcD3.972$m84.27043@burlma1-snr2>, Barry Margolin
<barmar@bbnplanet.com> wrote:

> In article <37DC433F.FDF66A81@daidun.kaist.ac.kr>,
> Ahn Ki-yung  <kyagrd@chiak.kaist.ac.kr> wrote:
> >In functional laguages the it is required that
> >tail recursion should be optimized by interpreter
> >or compiler of the language. I have two questions.
> >
> >Is it so in C++ ?
>
> No, C++ does not require tail recursion optimization.

Can a conforming program even tell? I would think that tail recursion
isn't even an issue for the standard. I assume there is some
implementation limit on recursion. In functions that have tail recursion
optimization performed on them, this limit is effectively infinite.

[snip way of enabling if on gcc]


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Ahn Ki-yung wrote in message <37DC433F.FDF66A81@daidun.kaist.ac.kr>...
>In functional laguages the it is required that
>tail recursion should be optimized by interpreter
>or compiler of the language. I have two questions.
>
>Is it so in C++ ?

No.  Also the presence of destructors make it problematical

struct foo { ~foo(); };

void bar()
{
  foo a;
  if(something())
   bar();
}

Only a very stupid or a very smart compiler will perform the tail recursion
optimization, since the language requires that a.~foo() be called after the
recursive call returns.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <7roui4$fee@library2.airnews.net>,
Bill Wade <bill.wade@stoner.com> wrote:
>Ahn Ki-yung wrote in message <37DC433F.FDF66A81@daidun.kaist.ac.kr>...
>>In functional laguages the it is required that
>>tail recursion should be optimized by interpreter
>>or compiler of the language. I have two questions.
>>
>>Is it so in C++ ?
>
>No.  Also the presence of destructors make it problematical
>
>struct foo { ~foo(); };
>
>void bar()
>{
>  foo a;
>  if(something())
>   bar();
>}
>
>Only a very stupid or a very smart compiler will perform the tail recursion
>optimization, since the language requires that a.~foo() be called after the
>recursive call returns.

That's not really a tail call, since it's implicitly:

void bar()
{
  foo a;
  if(something())
   bar();
  a.~foo();
}

The compiler should perform this transformation internally before looking
for tail call opportunities.  In this case, the call to the destructor
could be done using a goto, since that's the tail call.

--
Barry Margolin, barmar@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In functional laguages the it is required that
tail recursion should be optimized by interpreter
or compiler of the language. I have two questions.

Is it so in C++ ?

Is there any compiler which suppot this kind of
optimization ?
My friend tested this and concluded that it was not in gcc.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <37DC433F.FDF66A81@daidun.kaist.ac.kr>,
Ahn Ki-yung  <kyagrd@chiak.kaist.ac.kr> wrote:
>In functional laguages the it is required that
>tail recursion should be optimized by interpreter
>or compiler of the language. I have two questions.
>
>Is it so in C++ ?

No, C++ does not require tail recursion optimization.

>Is there any compiler which suppot this kind of
>optimization ?
>My friend tested this and concluded that it was not in gcc.

Sure it is, although it's not enabled by default:

     -mtail-call

     -mno-tail-call
          Do (or do not) make additional attempts  (beyond  those
          of the machine-independent portions of the compiler) to
          optimize tail-recursive calls into branches.   You  may
          not  want  to  do  this  because the detection of cases
          where this is not valid is not totally  complete.   The
          default is -mno-tail-call.

--
Barry Margolin, barmar@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]