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

[Ioannis Vranos <ivr@remove.this.grad.com>]

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