Re: Teaching new tricks to an old dog (C++ -->Ada)

From: Ioannis Vranos (ivr_at_remove.this.grad.com)
Date: 03/23/05 

Date: Wed, 23 Mar 2005 11:00:04 +0200

Georg Bauhaus wrote:

> We want a vector type indexed by values between M and N only *and* we
> want the compiler + tools to help us make data structures in accord
> with these ranges. We want it to take advantage of what it can learn
> from the type system which allows index range checking _at compile time_.

At first, it is easy to write a container in C++ that accepts a
specified range for indexes. The only reason that there is not one, is
because it does not make sense in C++ (when I learned some Pascal in the
past, I could not understand what was the use of the ability to use
negative indexes in arrays. The [0, +] style maps closely what is
happening in the machine.

Also it is possible to define range-checked at run-time, operations.
vector::at() is an example.

vector is also a dynamic-type array, so placing compile-time bounds
checking isn't possible/doesn't make sense.

For fixed size arrays and containers it is true, the compiler does not
catch at compile time any out of boundaries access. However we can do
this explicitly, by using compile-time checked assertions. For example:

#include <vector>
#include <boost/static_assert.hpp>

int main()
{
     using namespace std;

     const int MAX_SIZE=10;

     vector<int> vec(MAX_SIZE);

     // Many lines of code

     BOOST_STATIC_ASSERT(10<MAX_SIZE);

     vec[10]=4;
}

C:\c\temp.cpp In function `int main()':

14 C:\c\temp.cpp incomplete type `boost::STATIC_ASSERTION_FAILURE<
false>' used in nested name specifier

> No. I mean a double subtype whose values range from N.M to N'.M'.

May you give an example for a container along with such a subtype?

> Here you can see one point that you might want to demonstrate:
> The compiler won't tell you that there is something wrong
> with
>
> doors[10].SetOpen().SetNoVan();
>
> Worse, the program won't tell you either. This shows the missing
> link between vector indexing and the base type system in your
> approach. You could use
>
> doors.at(10).SetOpen().SetNoVan();
>
> and handle the exception _at run time_.
> In Ada, the compiler will tell you: "index value 10 is no good!"
> because the array "doors" can only be indexed by values effectively
> between 0 .. 9. These and only these are the values of the type
> enumerating the ten doors, and only these are allowed as index
> values x in expressios doors(x).
> No exception handling, no .at() needed when you listen to your
> compiler and fix the indexing error before you deliver a program.
> You get this for free as a result of the language's type handling
> at compile time.

Will the Ada compiler tell you this, for user-defined types too? Or is
this restricted to built-in arrays? If the latest is true, then its
value isn't that much.

> There is a reason that arrays still exist. One of the reasons
> should be obvious when comp.realtime is on the recipient list.
> Again, imagine a wave file manipulation process. A map indexed by
> strings is probably not the recommended container
> when you need fast matrix computations. In fact, a map might not be
> suitable at all irrespective of its key type, when r/w should be in O(1).

OK, although O(log(n)) is fairly cheap, let's stick to O(1). However
personally I think that the value of defined subranges in the style
-1000, -400 has not any practical use.

> - Given an enum, and
> - given a language that allows the enum as a basis for the construction
> of an array type in the type system (not using some run time computation
> method, like those you have shown here, IINM)
> - given that the compiler can use its knowledge of the enum
> + when it sees an array type based on the enum
> + when it sees an array
> + when it sees an array indexed by a statically known enum value
> + etc.,
> you have
> (a) useful names for objects in your problem domain, checked at
> compile-time

What do you mean by names?

> (b) a conceptual link between the enum (naming the single items) and
> a container _type_ (containing these items); you cannot use anything
> but these named numbers for indexing

Which has no value in the world of C++, but I guess many things in Ada
depend on this.

> (c) the fastest possible access, for both reading and writing, possibly
> checked at compile time

Fastest possible access in C++. Checked at run-time. Explicitly checked
at compile-time with compile-time assertions (which are restricted only
to constants), but is the Ada compile-time boundaries checking available
to user-defined containers? If not, can compile-time assertions be used?

> (d) etc.
>
> The STL descriptions provide further reaonsing why there can be
> restrictions
> on the uses of specific containers in specific situations, viz. >O(f(n)).

The access of vector, deque, string, valarray and bitset (and built in
arrays) is O(1) and of map O(log(n)) which is fairly cheap.

If you have access to TC++PL 3, you may check page 17.1.2 on page 464.

>>> I hope these example illustrate some points. They are not meant to
>>> trigger a discussion as to whether an array is the best data
>>> structure for everything. (Note that it might be necessary to read
>>> values from the array/Vector using random access in O(1), and to
>>> store and replace values in O(1), another reason to use an array.)
>
>
> What if a compiler or other tool can show that in the following
expression
> (pseudo notation)
>
> array_variable.at_index [n + m] <- f(x)
>
> does not need an index range check on the lhs? (Again, yes, it is
possible
> to write correct programs. The question is, does one notation +
compilation
> system have advantages when compared to another? What is the price to
pay?)

Apart from being eager to see whether this compile-time range checking
is available to user-defined containers, :-) in C++ there is no much
need for run-time boundary checking, if programming properly. Of course
one can always program improperly. :-) 

-- 
Ioannis Vranos
http://www23.brinkster.com/noicys

Relevant Pages

  • Re: Teaching new tricks to an old dog (C++ -->Ada)
    ... For fixed size arrays and containers it is true, ... by using compile-time checked assertions. ... a map might not be ...
    (comp.lang.cpp)
  • RE: Using InvokeMethod to circumvent compile-time type checking
    ... Abstract classes can serve you well, but accepting an instance of an abstract ... I have a separate comparer class full of AreEqual ... I've got another method designed to compare arrays of concrete types. ... Of course, the compiler wouldn't let me do this at compile-time, 'cause ...
    (microsoft.public.dotnet.framework)
  • Re: global constant variables in mex
    ... I am trying to pass a couple of values into a mex function. ... done at compile-time, either with a const value that the compiler ... Declare your arrays as pointers, ...
    (comp.soft-sys.matlab)
  • Re: A tale of three Suns
    ... >>data on three Sun machines. ... > be found at compile-time. ... or having arrays with different numbers of ... declared that way - so there is no chance of mismatch. ...
    (comp.lang.fortran)
  • Re: Memory occupied by Map
    ... I want to know the memory occupied by Map, Is there a way to do that. ... The result of the sizeof operator is a constant fixed at compile-time. ... rettrieve back. ... Serialize the map as ...
    (microsoft.public.vc.stl)