where exactly c++,c fail and Ada gets thru'

where exactly c++,c fail and Ada gets thru'

[Ananth the Boss]

we are developing safety critical software.my seniors say that c and
c++ are not suitable for safety critical software development and ada
is very much safe.NASA aslo uses Ada.at what point c++ or c turns to be
not suitable for devleloping flight software. i may be wrong also. can
any one give some more justifications for telling "ADA is safe" thanks
in advance

Re: where exactly c++,c fail and Ada gets thru'

[jimmaureenrogers]

Ananth the Boss wrote:
> we are developing safety critical software.my seniors say that c and
> c++ are not suitable for safety critical software development and ada
> is very much safe.NASA aslo uses Ada.at what point c++ or c turns to be
> not suitable for devleloping flight software. i may be wrong also. can
> any one give some more justifications for telling "ADA is safe" thanks
> in advance

The Coding Standards for the Joint Strike Fighter
http://public.research.att.com/~bs/JSF-AV-rules.pdf
give you an idea of the kinds of safety problems recognized in both
C and C++.

For example, the standard prohibits the use of C-style arrays as
function parameters. The problem cited is the degeneration of an
array function argument into a pointer. The pointer provides no
information about the size of the array it points to. This problem
commonly leads to overflowing arrays. Accessing elements beyond
the end of an array is always problematic. The C standard explicitly
allows one to access one element beyond the end of an array to
support common practice in thousands of C programs. The C
standard indicates that accessing more than one beyond the end
of an array leads to undefined behavior.

Polymorphism is one of the heavily used features of C++.
Polymorphism intentionally makes it difficult to determine
which over-ridden version of a function will be called. Safety
critical software standards require the ability to statically determine
which function will be called. Polymorphism seriously
complicates such static analysis.

Neither C nor C++ provides any standard means for detecting
overflow or underflow of numeric types.  C provides no way to
ensure that a numeric type uses only a valid set of values. C++
forces you to define a class wrapping the numeric value. You
must also provide all the range checking, resulting in a very
inefficient use of programmer time as well as processor time.
C++ allows you to define a restricted range integer class as a
template. It does not allow you to define a restricted range
floating point class because you cannot use floating point
values as template parameters.

There is no way in C++ to define a template class that achieves
the equivalent of:

type Normalized_Type is digits 10 range 0.0..1.0;

Jim Rogers

Re: where exactly c++,c fail and Ada gets thru'

[Ananth the Boss]

thnk you

Re: where exactly c++,c fail and Ada gets thru'

[Rod Chapman]

Ananth the Boss wrote:
> can any one give some more justifications for telling "ADA is safe" thanks
> in advance

Have you considered the SPARK Ada subset?  Read chapters 1-3 of the
SPARK
textbook - that will give you a very good idea of the issues involved
in the design
of high-integrity languages.
 - Rod, SPARK Team, Praxis

Re: where exactly c++,c fail and Ada gets thru'

[Martin Krischik]

Hi Ananth

> Ananth the Boss wrote:

>> NASA aslo uses Ada.at what point c++ or c turns to be
>> not suitable for devleloping flight software. i may be wrong also. can
>> any one give some more justifications for telling "ADA is safe" thanks
>> in advance

> Neither C nor C++ provides any standard means for detecting
> overflow or underflow of numeric types. ï¿œC provides no way to
> ensure that a numeric type uses only a valid set of values. C++
> forces you to define a class wrapping the numeric value.

Just in case you have not read up on Ada typing here some pointers:

http://en.wikibooks.org/wiki/Ada_Programming/Types
http://en.wikibooks.org/wiki/Ada_Programming/Subtypes

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: where exactly c++,c fail and Ada gets thru'

[Simon Wright]

"jimmaureenrogers@worldnet.att.net" <jimmaureenrogers@worldnet.att.net> writes:

>                                      The C standard explicitly
> allows one to access one element beyond the end of an array to
> support common practice in thousands of C programs. The C
> standard indicates that accessing more than one beyond the end
> of an array leads to undefined behavior.

As I remember it, you are allowed to use the address of the element
one past the end of the array in a comparison with the addresses of
other elements of the same array, but not to access its content?

Re: where exactly c++,c fail and Ada gets thru'

[Keith Thompson]

"jimmaureenrogers@worldnet.att.net" <jimmaureenrogers@worldnet.att.net> writes:
> Ananth the Boss wrote:
>> we are developing safety critical software.my seniors say that c and
>> c++ are not suitable for safety critical software development and ada
>> is very much safe.NASA aslo uses Ada.at what point c++ or c turns to be
>> not suitable for devleloping flight software. i may be wrong also. can
>> any one give some more justifications for telling "ADA is safe" thanks
>> in advance
>
> The Coding Standards for the Joint Strike Fighter
> http://public.research.att.com/~bs/JSF-AV-rules.pdf
> give you an idea of the kinds of safety problems recognized in both
> C and C++.
>
> For example, the standard prohibits the use of C-style arrays as
> function parameters. The problem cited is the degeneration of an
> array function argument into a pointer. The pointer provides no
> information about the size of the array it points to.

In fact, it's not possible in C to pass an array directly as a
function parameter.  The language allows a parameter to be declared
with array syntax, but this is exactly equivalent to declaring it as a
pointer.  For example, these two C declarations are exactly
equivalent:

    void func(int arr[]);
    void func(int *arr);

It's a common misconception that arrays are "really" pointers in C.
In fact they're not, but there are some features of the language
(certain implicit conversions, the above syntax for parameter
declarations) that can make it look that way.  If you're curious about
the details, section 6 of the comp.lang.c FAQ has a good summary.

I haven't looked at the coding standards document in question.
Possibly it just forbids the use of array syntax to represent what's
really a pointer parameter.  Forbidding pointer parameters would be a
serious problem; much of the standard library does this, and it's the
normal way to achieve the effect of passing an array.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

Re: where exactly c++,c fail and Ada gets thru'

[Keith Thompson]

Simon Wright <simon@pushface.org> writes:
> "jimmaureenrogers@worldnet.att.net"
> <jimmaureenrogers@worldnet.att.net> writes:
>
>>                                      The C standard explicitly
>> allows one to access one element beyond the end of an array to
>> support common practice in thousands of C programs. The C
>> standard indicates that accessing more than one beyond the end
>> of an array leads to undefined behavior.
>
> As I remember it, you are allowed to use the address of the element
> one past the end of the array in a comparison with the addresses of
> other elements of the same array, but not to access its content?

Correct.  Note that "allowed to" is a fairly weak statement in C;
accessing elements beyond the bounds of an array isn't "allowed", but
it's undefined behavior, meaning that the implementation is under no
obligation to diagnose the error.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

Re: where exactly c++,c fail and Ada gets thru'

[Steve]

"Ananth the Boss" <anboss@gmail.com> wrote in message 
news:1145852356.559455.222600@i39g2000cwa.googlegroups.com...
> we are developing safety critical software.my seniors say that c and
> c++ are not suitable for safety critical software development and ada
> is very much safe.NASA aslo uses Ada.at what point c++ or c turns to be
> not suitable for devleloping flight software. i may be wrong also. can
> any one give some more justifications for telling "ADA is safe" thanks
> in advance
>

Learn Ada and you will have your answer.

I have never heard a question like this from someone who knows Ada.

Steve
(The Duck) 

Re: where exactly c++,c fail and Ada gets thru'

[Jeffrey R. Carter]

Keith Thompson wrote:
> 
> I haven't looked at the coding standards document in question.
> Possibly it just forbids the use of array syntax to represent what's
> really a pointer parameter.  Forbidding pointer parameters would be a
> serious problem; much of the standard library does this, and it's the
> normal way to achieve the effect of passing an array.

It's also the source for Ritchie's observation that "C's solution to 
this [variable-sized array parameters] has real problems, and people who 
are complaining about safety definitely have a point."

-- 
Jeff Carter
"Why don't you bore a hole in yourself and let the sap run out?"
Horse Feathers
49

Re: where exactly c++,c fail and Ada gets thru'

[Maciej Sobczak]

Hi,

jimmaureenrogers@worldnet.att.net wrote:

 > The C standard explicitly
 > allows one to access one element beyond the end of an array to
 > support common practice in thousands of C programs.

The "access" word is misleading. It's allowed to use such address for 
comparisons and in arithemtics. It is *not* allowed to dereference it.

 > Polymorphism is one of the heavily used features of C++.

But it is not forced (as is the case in some other "OO" languages).
It is perfectly possible to write programs without the use of run-time 
polymorphism.

 > Safety
 > critical software standards require the ability to statically
 > determine which function will be called.

It's possible to write such programs in C++.

 > Neither C nor C++ provides any standard means for detecting
 > overflow or underflow of numeric types.

That's true.

 > C provides no way to
 > ensure that a numeric type uses only a valid set of values.

True.

 > C++
 > forces you to define a class wrapping the numeric value.

Yes, classes are used to define new types. Is there any problem with 
this? It is also necessary in Ada if we want to do just a bit more of 
what is provided by type and subtype constructs.

 > You
 > must also provide all the range checking, resulting in a very
 > inefficient use of programmer time as well as processor time.

Depends. The former can be automated and the latter can be statically 
elided. It's all the question of how it's done and templates provide a 
powerful mechanism that can help here.

 > C++ allows you to define a restricted range integer class as a
 > template. It does not allow you to define a restricted range
 > floating point class because you cannot use floating point
 > values as template parameters.

That's true - at least if you require direct use of floating point.

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: where exactly c++,c fail and Ada gets thru'

[Martin Krischik]

Maciej Sobczak wrote:

> Yes, classes are used to define new types. Is there any problem with
> this? It is also necessary in Ada if we want to do just a bit more of
> what is provided by type and subtype constructs.

Say:

type Y_Type is range 1 .. 10;
subtype X_Type is new x range 1 .. 5;

function F (X: X_Type) return Y_Type is
begin
  return X + 3;
end F

Now I would expect that an Ada compiler will not insert any runtime checks
as X + 3 is allways in the range of Y_Type. However:

function G (X: X_Type) return Y_Type is
begin
  return X + 7;
end G;

may well be outside the range of Y_Type and if so CONSTRAINT_ERROR will be
raised.

Now say we have a suitable C++ range template:

typedef range<int, 1, 10> Y_Type;
typedef range<Y_Type, 1, 5> X_Type;

Y_Type F (X_Type X)
  {
  return X + 3;
  }

Y_Type G (X_Type X)
  {
  return X + 7;
  }

Now anyone up to the challenge to define:

template <typename Base_Type, Base_Type First, Base_Type Last>
range::operator = (Base_Type right)

template <typename Base_Type, Base_Type First, Base_Type Last>
range::operator + (Base_Type right)

template <typename Base_Type, Base_Type First, Base_Type Last>
range::range (Base_Type right)

in such a way that it works like Ada - inclusive the *realistic* change that
the compiler will optimize away the range check in F ().

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: where exactly c++,c fail and Ada gets thru'

[Martin Krischik]

Keith Thompson wrote:

> In fact, it's not possible in C to pass an array directly as a
> function parameter.

Actually C99 can pass arrays. The declaration looks something like this:

F (int A_Lenght, double A [A_Lenght])

or

G (double A [static 10])

or even

H (double A [*])

But then: AFAIK: there is only one compiler which prides itself with
actually implementing C99 arrays and one compiler which at least tries and
and has the failures on it's bug list.

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: where exactly c++,c fail and Ada gets thru'

[Keith Thompson]

Martin Krischik <krischik@users.sourceforge.net> writes:
> Keith Thompson wrote:
>> In fact, it's not possible in C to pass an array directly as a
>> function parameter.
>
> Actually C99 can pass arrays. The declaration looks something like this:
>
> F (int A_Lenght, double A [A_Lenght])
>
> or
>
> G (double A [static 10])
>
> or even
>
> H (double A [*])
>
> But then: AFAIK: there is only one compiler which prides itself with
> actually implementing C99 arrays and one compiler which at least tries and
> and has the failures on it's bug list.

I'm fairly sure that still passes a pointer, not the actual array.
For example, the expression "sizeof(A)" inside the function will yield
the size of a pointer, not the size of the array.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

Re: where exactly c++,c fail and Ada gets thru'

[Maciej Sobczak]

Martin Krischik wrote:

> Now say we have a suitable C++ range template:
> 
> typedef range<int, 1, 10> Y_Type;
> typedef range<Y_Type, 1, 5> X_Type;
> 
> Y_Type F (X_Type X)
>   {
>   return X + 3;
>   }
> 
> Y_Type G (X_Type X)
>   {
>   return X + 7;
>   }
> 
> Now anyone up to the challenge to define:
> 
> template <typename Base_Type, Base_Type First, Base_Type Last>
> range::operator = (Base_Type right)
> 
> template <typename Base_Type, Base_Type First, Base_Type Last>
> range::operator + (Base_Type right)
> 
> template <typename Base_Type, Base_Type First, Base_Type Last>
> range::range (Base_Type right)
> 
> in such a way that it works like Ada - inclusive the *realistic* change that
> the compiler will optimize away the range check in F ().

The C++ standard does not define to what extent the compilers are 
allowed to optimize the resulting code. This is the quality of 
implementation issue and an area of competition between compiler 
vendors. Without any further checks I can claim that it is possible for 
the compiler to optimize it the way you want.

And without any further checks I take the risk to claim that the Ada 
standard does not require any conforming compiler to optimize range 
checks away as you described (or please throw some references) - 
similarly, this is the QoI issue.

So - what was your point?

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: where exactly c++,c fail and Ada gets thru'

[REH]

Martin Krischik wrote:
> Maciej Sobczak wrote:
>
> > Yes, classes are used to define new types. Is there any problem with
> > this? It is also necessary in Ada if we want to do just a bit more of
> > what is provided by type and subtype constructs.
>
> Say:
>
> type Y_Type is range 1 .. 10;
> subtype X_Type is new x range 1 .. 5;
>
> function F (X: X_Type) return Y_Type is
> begin
>   return X + 3;
> end F
>
> Now I would expect that an Ada compiler will not insert any runtime checks
> as X + 3 is allways in the range of Y_Type. However:
>
> function G (X: X_Type) return Y_Type is
> begin
>   return X + 7;
> end G;
>
> may well be outside the range of Y_Type and if so CONSTRAINT_ERROR will be
> raised.
>
> Now say we have a suitable C++ range template:
>
> typedef range<int, 1, 10> Y_Type;
> typedef range<Y_Type, 1, 5> X_Type;
>
> Y_Type F (X_Type X)
>   {
>   return X + 3;
>   }
>
> Y_Type G (X_Type X)
>   {
>   return X + 7;
>   }
>
> Now anyone up to the challenge to define:
>
> template <typename Base_Type, Base_Type First, Base_Type Last>
> range::operator = (Base_Type right)
>
> template <typename Base_Type, Base_Type First, Base_Type Last>
> range::operator + (Base_Type right)
>
> template <typename Base_Type, Base_Type First, Base_Type Last>
> range::range (Base_Type right)
>
> in such a way that it works like Ada - inclusive the *realistic* change that
> the compiler will optimize away the range check in F ().

I have done this.

Re: where exactly c++,c fail and Ada gets thru'

[Keith Thompson]

Maciej Sobczak <no.spam@no.spam.com> writes:
> Martin Krischik wrote:
>> Now say we have a suitable C++ range template:
>> typedef range<int, 1, 10> Y_Type;
>> typedef range<Y_Type, 1, 5> X_Type;
>> Y_Type F (X_Type X)
>>   {
>>   return X + 3;
>>   }
>> Y_Type G (X_Type X)
>>   {
>>   return X + 7;
>>   }
>> Now anyone up to the challenge to define:
>> template <typename Base_Type, Base_Type First, Base_Type Last>
>> range::operator = (Base_Type right)
>> template <typename Base_Type, Base_Type First, Base_Type Last>
>> range::operator + (Base_Type right)
>> template <typename Base_Type, Base_Type First, Base_Type Last>
>> range::range (Base_Type right)
>> in such a way that it works like Ada - inclusive the *realistic*
>> change that
>> the compiler will optimize away the range check in F ().
>
> The C++ standard does not define to what extent the compilers are
> allowed to optimize the resulting code.

Actually, I think it does; it just doesn't define to what extent
compilers are *required* to optimize.  (In C, allowed optimizations
are determined by what's loosely called the "as-if rule"; C++ is
probably similar.)

>                                         This is the quality of
> implementation issue and an area of competition between compiler
> vendors. Without any further checks I can claim that it is possible
> for the compiler to optimize it the way you want.
>
> And without any further checks I take the risk to claim that the Ada
> standard does not require any conforming compiler to optimize range
> checks away as you described (or please throw some references) -
> similarly, this is the QoI issue.
>
> So - what was your point?

Probably the point was that range checks are an intrinsic feature of
Ada, and any decent Ada compiler will optimize them as much as
practical.  In C++, on the other hand, any range checks would have to
be done as explicit user code, and a typical C++ compiler might be
less likely to recognize an idiom that it can optimize.

A sufficiently clever C++ compiler should be able, in most cases, to
optimize as well as a sufficiently clever Ada compiler (though I
suspect Ada's aliasing rules allow for better optimizations in some
cases).  I have no idea whether current C++ compilers are
"sufficiently clever".

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

Re: where exactly c++,c fail and Ada gets thru'

[Martin Krischik]

Maciej Sobczak wrote:

> Martin Krischik wrote:
>
> > Now say we have a suitable C++ range template:
> >
> > typedef range<int, 1, 10> Y_Type;
> > typedef range<Y_Type, 1, 5> X_Type;
> >
> > Y_Type F (X_Type X)
> >   {
> >   return X + 3;
> >   }
> >
> > Y_Type G (X_Type X)
> >   {
> >   return X + 7;
> >   }
> >
> > Now anyone up to the challenge to define:
> >
> > template <typename Base_Type, Base_Type First, Base_Type Last>
> > range::operator = (Base_Type right)
> >
> > template <typename Base_Type, Base_Type First, Base_Type Last>
> > range::operator + (Base_Type right)
> >
> > template <typename Base_Type, Base_Type First, Base_Type Last>
> > range::range (Base_Type right)
> >
> > in such a way that it works like Ada - inclusive the *realistic* change that
> > the compiler will optimize away the range check in F ().
>
> The C++ standard does not define to what extent the compilers are
> allowed to optimize the resulting code. This is the quality of
> implementation issue and an area of competition between compiler
> vendors. Without any further checks I can claim that it is possible for
> the compiler to optimize it the way you want.
>
> And without any further checks I take the risk to claim that the Ada
> standard does not require any conforming compiler to optimize range
> checks away as you described (or please throw some references) -
> similarly, this is the QoI issue.
>
> So - what was your point?

The point is - of corse -  it that the semantic tree of the Ada
compiler contains the information that X will be in the range of (1 ..
5) and then the optimizer can easily calculate that (1 .. 5) + 3 < 10
and then optimize away the check.

The sematinc tree of the C++ will contain the information that X is in
the range of (-2*32 .. +2*32-1) and that is a pretty useless
information to the optimizer.

Martin

Re: where exactly c++,c fail and Ada gets thru'

[Martin Krischik]

REH wrote:
> Martin Krischik wrote:
> > Maciej Sobczak wrote:
> >
> > > Yes, classes are used to define new types. Is there any problem with
> > > this? It is also necessary in Ada if we want to do just a bit more of
> > > what is provided by type and subtype constructs.
> >
> > Say:
> >
> > type Y_Type is range 1 .. 10;
> > subtype X_Type is new x range 1 .. 5;
> >
> > function F (X: X_Type) return Y_Type is
> > begin
> >   return X + 3;
> > end F
> >
> > Now I would expect that an Ada compiler will not insert any runtime checks
> > as X + 3 is allways in the range of Y_Type. However:
> >
> > function G (X: X_Type) return Y_Type is
> > begin
> >   return X + 7;
> > end G;
> >
> > may well be outside the range of Y_Type and if so CONSTRAINT_ERROR will be
> > raised.
> >
> > Now say we have a suitable C++ range template:
> >
> > typedef range<int, 1, 10> Y_Type;
> > typedef range<Y_Type, 1, 5> X_Type;
> >
> > Y_Type F (X_Type X)
> >   {
> >   return X + 3;
> >   }
> >
> > Y_Type G (X_Type X)
> >   {
> >   return X + 7;
> >   }
> >
> > Now anyone up to the challenge to define:
> >
> > template <typename Base_Type, Base_Type First, Base_Type Last>
> > range::operator = (Base_Type right)
> >
> > template <typename Base_Type, Base_Type First, Base_Type Last>
> > range::operator + (Base_Type right)
> >
> > template <typename Base_Type, Base_Type First, Base_Type Last>
> > range::range (Base_Type right)
> >
> > in such a way that it works like Ada - inclusive the *realistic* change that
> > the compiler will optimize away the range check in F ().
>
> I have done this.

I had a look. Looks impressive with all those includes. Looks like one
of thoses templates I never want to debug thrue.

But don't expect me to have found that magic static analysis something
trick. So:

How exactly did you do it?

Martin

Re: where exactly c++,c fail and Ada gets thru'

[REH]

"Martin Krischik" <krischik@users.sourceforge.net> wrote in message 
news:1146210553.562353.140540@j73g2000cwa.googlegroups.com...
>> I have done this.
>
> I had a look. Looks impressive with all those includes. Looks like one
> of thoses templates I never want to debug thrue.
>
> But don't expect me to have found that magic static analysis something
> trick. So:
>
> How exactly did you do it?

If you are truly interested, I can email you an article about its 
implementation.  If you are just looking for a chance to language-bash, I 
won't bother.  I wrote it because I don't always have to luxury of language 
choice.

REH

Re: where exactly c++,c fail and Ada gets thru'

[Maciej Sobczak]

Martin Krischik wrote:

> The point is - of corse -  it that the semantic tree of the Ada
> compiler contains the information that X will be in the range of (1 ..
> 5) and then the optimizer can easily calculate that (1 .. 5) + 3 < 10
> and then optimize away the check.
> 
> The sematinc tree of the C++ will contain the information that X is in
> the range of (-2*32 .. +2*32-1) and that is a pretty useless
> information to the optimizer.

Except that the optimizer is not limited to use only this information.
With the two example ranges (1..5 and 1..10) the result of inlining will 
be that the following operations - all operating on the single value - 
will be placed one after another:

1. compare against 5
2. add 3
3. compare against 10

It doesn't take a rocket scientist to deduce that the third operation 
has a dead branch and can be therefore eliminated.

Of course, Ada provides more information to the compiler and the more 
information the compiler has, the wider are the optimization 
opportunities, therefore languages with richer type systems are easier 
to optimize. Nobody questions that. But this is very far from the 
optimization being guaranteed in Ada or impossible in C++ - neither is 
the case.


-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: where exactly c++,c fail and Ada gets thru'

[Martin Krischik]

REH wrote:

> 
> "Martin Krischik" <krischik@users.sourceforge.net> wrote in message
> news:1146210553.562353.140540@j73g2000cwa.googlegroups.com...
>>> I have done this.
>>
>> I had a look. Looks impressive with all those includes. Looks like one
>> of thoses templates I never want to debug thrue.
>>
>> But don't expect me to have found that magic static analysis something
>> trick. So:
>>
>> How exactly did you do it?
> 
> If you are truly interested, I can email you an article about its
> implementation.  If you are just looking for a chance to language-bash, I
> won't bother. 

I did so many years of C++ I allways like a little language-bash. But then,
I allways like to learn something new and I don't mind been proven wrong.

> I wrote it because I don't always have to luxury of 
> language choice.

So did I. And I must have missed something as my class has no magic static
analysis something.

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: where exactly c++,c fail and Ada gets thru'

[Martin Krischik]

Maciej Sobczak wrote:

> Martin Krischik wrote:
> 
>> The point is - of corse -  it that the semantic tree of the Ada
>> compiler contains the information that X will be in the range of (1 ..
>> 5) and then the optimizer can easily calculate that (1 .. 5) + 3 < 10
>> and then optimize away the check.
>> 
>> The sematinc tree of the C++ will contain the information that X is in
>> the range of (-2*32 .. +2*32-1) and that is a pretty useless
>> information to the optimizer.
> 
> Except that the optimizer is not limited to use only this information.
> With the two example ranges (1..5 and 1..10) the result of inlining will
> be that the following operations - all operating on the single value -
> will be placed one after another:
> 
> 1. compare against 5
> 2. add 3
> 3. compare against 10
> 
> It doesn't take a rocket scientist to deduce that the third operation
> has a dead branch and can be therefore eliminated.

But it is the callers responsibility to check the input parameter before
calling the function. That way range checks need only be performed on input
and type convertions. Remember that Ada defines + as:

function "+" is (L, R: in Integer'Base) return Integer'Base;

Back to my example: If you call F(3) no check is needed. The caller knows
that 3 is in range and the callee knows that X + 3 is in range. Of course:
If the optimizer spots that is a different story.

Now I do wonder if REH managed some template/boolean magic to get the same
result on C++. 

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: where exactly c++,c fail and Ada gets thru'

[REH]

"Martin Krischik" <krischik@users.sourceforge.net> wrote in message 
news:1201812.r16X2gYOJE@linux1.krischik.com...
> Now I do wonder if REH managed some template/boolean magic to get the same
> result on C++.
>

The simplistic answer is for each ranged type R, there is an intermediate 
type I.  I has the same properties as R, except it is allowed to "grow." 
That is, as the results of partial expressions become large, I chooses an 
integer type with a larger range (sadly, my technique will not work with 
floating point types).  If I is not able to find a type with a larger enough 
range, it is flagged has having the possibility of overflowing.  The math is 
basically done by partial specializing on whether overflow is possible.  The 
tricky part is determining whether an overflow can occur.  For this I took a 
page from my COBOL days.  If you performed an operation on two values and 
tried to shove it into a variable without enough digits, COBOL would warning 
you.  For example, multiplying two two-digit values and trying to assign it 
to anything less than a 4-digit variable can overflow.  Of course, it is 
trivial to determine this for every algebraic operator.  So, for each 
operation, we calculate the maximum number of digits needed for the result 
and try to use a type with that ranged.  The maximum digits is kept in I. 
This allows intermediate values to exceed the bounds of the ranged type 
(like doing the math using R'Base).  When a type I is assigned to type R, it 
is ranged check if necessary.  If the lower or upper bounds of I is within 
the bounds of R, that particular check is also removed.  This is all done at 
compile time.

 As an example, assume R is an unsigned type with a ranged of [0, 100].  The 
number of binary digits necessary to hold R is 7.  So, if x and y are 
variables of type R, then x * y needs at most 14 digits.  On any system, 
unsigned int can hold a 14-digit number.  No overflow can happen, so no 
check is done.  The result is of type I.  I is a class temple whose template 
parameters hold information needed at compile-time.  I "contains" type 
unsigned int, and 14 for the digits.  I also "knows" it's base type (R), so 
is able to keep types unique.  R can be instantiated with or without 
explicit construction (defines whether or not conversion to R requires an 
explicit cast), and with or without conversion operators (defines whether R 
can be implicitly converted to other types).  R can bound the largest type 
allowed in its calculations.  For example, assume we are on a system where 
int is 16 bits and long is 32 bits.  If we take the resulting value of type 
I above and do I * I, this needs a 28-digit type.  Normally, the resulting I 
type would use unsigned long.  R can be bounded to stop at 16-bits if, for 
some reason you do not want to use type long.  Thus, instead of growing, the 
new I would be flagged and the operation would be checked for overflow.

Now, you may ask why I didn't just define I with the resulting range of [0, 
1000].  The answer is that it would be a lot nastier because then I would 
also have to do overflow checking on the ranges at compile-time.  It would 
be really nasty for signed types because you cannot just do the operation 
and check for overflow.  Allowing a signed operation to overflow is 
undefined behavior.

The above technique works for both signed and unsigned types, and all three 
integer representations allowed by the C++ standard.  I'd like to enhance it 
to handle floating points, but I currently have no clue how that could be 
done.  I'll admit the templates are very, very complex, but for the most 
part the client software does not have to worry about it.  You can just use 
you would any other numerical type.  I don't recall having any issue with 
"error messages" while writing it.  Modern C++ compiler have gotten very 
good at giving more sane messages.  They have also gotten better at compile 
times.  My ranged type is not perfect, and there is no way to perfectly 
replicate what Ada can do, but as I said I cannot always use Ada.  I also 
realize that the class will never be able to remove as many checks as an Ada 
compiler, but it is much better than nothing.  The checks are very expensive 
since they are done in standard C++ (though one could sacrifice portability 
for speed if their compiler supported inline assembly).  On benchmarks I've 
run, the class can be very close to raw integers in terms of speed, where 
not eliminating any checks can cost 10x or more.  Of course this all depends 
on your system, compiler, etc., and the particular expressions (what the 
class can catch).  In particular, very complex expressions will saturate the 
range of the types available quickly and inhibit anymore optimizations. 
Breaking the expression up can help to alleviate this, but each time an I is 
assigned to an R, a range check may have to be done (those range checking is 
much, much more efficient than overflow checking).

REH

Re: where exactly c++,c fail and Ada gets thru'

[Xcriber51]

REH, my hat is off, but say, do you mind if I query how much the treatments
cost afterwards?

Also, I'd be interested in that article on its implementation - and the
source code. Like all mortals in coding business, I too have a thing for
brain damage. :-)

Thanks in advance!

Cheers
K

Re: where exactly c++,c fail and Ada gets thru'

[REH]

Xcriber51 wrote:
> REH, my hat is off, but say, do you mind if I query how much the treatments
> cost afterwards?

I'm not sure that you are asking.

>
> Also, I'd be interested in that article on its implementation - and the
> source code. Like all mortals in coding business, I too have a thing for
> brain damage. :-)
>
The latest source can be found here:
http://www.richherrick.com/software/herrick_library.html

The article is in doc/articles

REH

Re: where exactly c++,c fail and Ada gets thru'

[Maciej Sobczak]

Martin Krischik wrote:

> But it is the callers responsibility to check the input parameter before
> calling the function.

Of course - and it's where the code inlining can be useful. The biggest 
advantage of inlining is not in removing function call/return stuff, but 
in putting together things that otherwise could not be analysed together.

We could now start endless debate on the cases where you can or cannot 
have code inlining, but the whole point in optimization is that there 
are many ways to do it (including global program optimization, things 
like JIT and so on) - and, as already said, it's where compiler vendors 
compete. It's easier to optimize languages that have richer type 
information (and again - nobody questions that), but at the end of the 
day it's only the sequence of *observable behaviours* that is of 
interest to the programmer and everything else is left at the mercy of 
the optimizer - in this light, range checking is one of those things 
that are relatively easy to optimize.


-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/