On 2009-01-30 17:28, Pete Becker wrote:
> On 2009-01-28 21:08:04 -0500, Yechezkel Mett <ymett.on.usenet@gmail.com>
> said:
>
>> WRT to tail-recursion optimisation:
>>
>> On Jan 27, 10:42 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
>>> A C++ compiler is free to generate stack overflow anytime anyway, even
>>> for code where the stack usage is constant. (and most will)
>>
>> What do you mean by this?
>>
>>> As for why an optimization shouldn't be part of a language description
>>> and semantics, that is because something that doesn't change the
>>> observable behaviour of a program doesn't really have any place in the
>>> description of its semantics.
>>
>> So why does the C++ standard give complexity guarantees?
>>
>
> The places where the library gives complexity guarantees all involve
> operations that can be counted by user-written types. That is, the
> effects are directly observable by the program. Optimizations aren't
> observable, that is, they don't change the result of a conforming
> program.

And the exception to this rule is copy constructor elision, where the
standard explicitly allows the compiler to change the observable behaviour.

--
Erik Wikstr  m


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"Mathias Gaunard" <loufoque@gmail.com>
>> 2.  Function goto instead of call
>>
>> When you call a function (typically) a call stack is created.  When the
>> function returns the return goes to the calling function.  Some C
>> compilers can do tail call elimination in certain circumstances but it
>> is never guaranteed to support tail calls in all obvious conditions.
>
> So you would like the standard to mandate tail call optimization.
> Mandating optimizations in the description of a language and its
> semantics has never been such a good idea. You can rely on it or not
> if you want, that's up to the quality of your implementation.

Why wasn't it a good idea? Lisp-like languages state that the
implementation
must discover tail recursion and implement it similarly as an iterative(-li
coded) version. What is the problem with that?

It is not simply az efficiency optimisation, but allows the programmer the
freedom to express ideas in optimal code -- instead of writing gotos,
because SOME compilers could generate stack-overflowing code otherwise.

A general tail-call opt is certainly a bigger bite with too much burden.



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 27 jan, 08:58, "Balog Pal" <p...@lib.hu> wrote:

> It is not simply az efficiency optimisation, but allows the programmer the
> freedom to express ideas in optimal code -- instead of writing gotos,
> because SOME compilers could generate stack-overflowing code otherwise.

A C++ compiler is free to generate stack overflow anytime anyway, even
for code where the stack usage is constant. (and most will)

As for why an optimization shouldn't be part of a language description
and semantics, that is because something that doesn't change the
observable behaviour of a program doesn't really have any place in the
description of its semantics.
Lisp mandates this optimization mainly to enforce a programming style.

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

WRT to tail-recursion optimisation:

On Jan 27, 10:42 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
> A C++ compiler is free to generate stack overflow anytime anyway, even
> for code where the stack usage is constant. (and most will)

What do you mean by this?

> As for why an optimization shouldn't be part of a language description
> and semantics, that is because something that doesn't change the
> observable behaviour of a program doesn't really have any place in the
> description of its semantics.

So why does the C++ standard give complexity guarantees?

Yechezkel Mett


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Yechezkel Mett wrote:
>
> WRT to tail-recursion optimisation:
>
> On Jan 27, 10:42 pm, Mathias Gaunard <loufo...@gmail.com> wrote:

....
>>
>> As for why an optimization shouldn't be part of a language description
>> and semantics, that is because something that doesn't change the
>> observable behaviour of a program doesn't really have any place in the
>> description of its semantics.
>
> So why does the C++ standard give complexity guarantees?

Because the C++ standard template library makes extensive use of
functions defined by the user, and the complexity guarantees give you
important information about how many times those functions will be
called. That number is part of the observable behavior, at least if
such calls have side effects.

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 2009-01-28 21:08:04 -0500, Yechezkel Mett <ymett.on.usenet@gmail.com>
said:

> WRT to tail-recursion optimisation:
>
> On Jan 27, 10:42 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
>> A C++ compiler is free to generate stack overflow anytime anyway, even
>> for code where the stack usage is constant. (and most will)
>
> What do you mean by this?
>
>> As for why an optimization shouldn't be part of a language description
>> and semantics, that is because something that doesn't change the
>> observable behaviour of a program doesn't really have any place in the
>> description of its semantics.
>
> So why does the C++ standard give complexity guarantees?
>

The places where the library gives complexity guarantees all involve
operations that can be counted by user-written types. That is, the
effects are directly observable by the program. Optimizations aren't
observable, that is, they don't change the result of a conforming
program.

--
   Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greetings,

I am a long-time C programmer (close to 30 years) with very little C++
experience.  I don't keep up with the standards process but there are
two features that I've long thought needed.  It might be that C++
already has these features or that the upcoming standards for C or C++
have these features.  I suppose I'm just asking and if they are not
there already, I'm suggesting their addition.  They are as follows:

1.  Computed goto

It would be very useful to have a computed goto.  This would involve two
things.  First you should be able to use labels as read-only variables.
   Second, you should be able to branch assign the label to an array and
branch to it via indexing into the array as follows:

lbl1:
      ...
lbl2:
      ...
void *labels[] = {lbl1, lbl2};

goto labels[x];

The labels should not have to appear before the assignment, and there
should be a way of making this runtime assignment to labels once.

The use of this feature is in virtual machines.  VM's typically process
op-codes.  These op-codes can be treated as indexes into the branch
array.  This would be very, very fast.  I know C can use arrays of
function pointers that can be indexed into and executed but the problem
is that you have the (often huge) function overhead associated with each
instruction.  The other probable response is a case statement.  The
problem is that a case statement must do a lot of time-consuming
compares in order get to the correct case.  In index and branch is much
faster.  (I know case statement are optimized to a point but I don't
think they are guaranteed to be as fast as an index and branch).

2.  Function goto instead of call

When you call a function (typically) a call stack is created.  When the
function returns the return goes to the calling function.  Some C
compilers can do tail call elimination in certain circumstances but it
is never guaranteed to support tail calls in all obvious conditions.  C
is often used as an intermediate language for other languages compilers
(like Lisp, Scheme, etc.).  Languages such as Scheme require tail call
optimization.  Coding in assembler is very un-portable.  Using C as a
portable assembler is great but not being able to eliminate tail calls
is a big problem.  Scheme compilers often use a set of tricks to make C
eliminate tail calls but these tricks are very slow compared to what is
really needed.  If C had the ability to "goto" a function in addition to
being able to "call" a function, other compiler writers can take
advantage of this feature to give their languages tail call elimination
without costly tricks or having to resort to assembler.

Does anyone know if these facilities are in upcoming C or C++ standards?
   Have there been any discussion or even mention of these issues?

Thanks.

Blake McBride
blake@mcbride.name
http://blake.mcbride.name

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 7 jan, 17:28, Blake McBride <bl...@mcbride.name> wrote:
> The other probable response is a case statement.  The
> problem is that a case statement must do a lot of time-consuming
> compares in order get to the correct case.  In index and branch is much
> faster.  (I know case statement are optimized to a point but I don't
> think they are guaranteed to be as fast as an index and branch).

Any sane compiler will produce code that is constant time for a switch/
case (they will, indeed, use tables if that is the most efficient
solution). I am not sure, however, whether that is mandated by the
standard or not.
Have you even tested the efficiency of a case statement, or even
looked at the generated assembly, to say it is far slower?

>
> 2.  Function goto instead of call
>
> When you call a function (typically) a call stack is created.  When the
> function returns the return goes to the calling function.  Some C
> compilers can do tail call elimination in certain circumstances but it
> is never guaranteed to support tail calls in all obvious conditions.

So you would like the standard to mandate tail call optimization.
Mandating optimizations in the description of a language and its
semantics has never been such a good idea. You can rely on it or not
if you want, that's up to the quality of your implementation.


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]