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

[Ioannis Vranos]

arrays. The [0, +] style maps closely what is happening in the machine.

Certainly. But the Ada model can maps more closely to the domain problem.
And this is an important point. We are not writting software for the machine
but to solve problems. Most of the time you just don't care how such data will
be handled by the machine (i.e. how the compiler will generate the code).

C++ maps on both. However I guess Ada maps on both too since it is a
systems programming language.


Now may you explain how the ability to use negative subranges for built
in array indices makes Ada better for any domain problem?

 

[Pascal Obry]

Now may you explain how the ability to use negative subranges for built in
array indices makes Ada better for any domain problem?

For a domain problem where you have to create an area centered on (0,0)
for example. What about a vector representing altitude, the sub-zero values
being under the water. Just some examples, I bet you'll be able to think about
lot more

Pascal.

--

--|------------------------------------------------------
--| Pascal Obry Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--| http://www.obry.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

 

[Vinzent 'Gadget' Hoefler]

I forgot to say here that the cost of map's operator[] is O(log(n))
which is fairly cheap for large amount of data.

compare O(log(n)) to O(1) where n is 1, 1000, 1_000_000.
Make this access a part of an inner loop.

If you do the maths, you will see that log(10^6) isn't that large.

Yeah, right. Binary searches are not much slower. Only about 10 or 20
times. Seem, you just rendered hashing algorithms obsolete.


Vinzent.

 

[Ioannis Vranos]

For a domain problem where you have to create an area centered on (0,0)
for example. What about a vector representing altitude, the sub-zero values
being under the water. Just some examples, I bet you'll be able to think about
lot more

I think an associative container like map fits better to this. What do
you do in Ada if you want to associate product names with prices, in the
style


productlist["something"]= 71.2;


or a name with a number (string with string) in an address book
application for example?


namelist["Obry Pascal"]="321-45563";


Also may you tell me if that famous compile-time boundary checking
applies (can be used) to user-defined containers too?

 

[Pascal Obry]

I think an associative container like map fits better to this. What do you do
in Ada if you want to associate product names with prices, in the style


productlist["something"]= 71.2;


or a name with a number (string with string) in an address book application
for example?


namelist["Obry Pascal"]="321-45563";

We use a map, using the Ada.Containers STL like library.

Also may you tell me if that famous compile-time boundary checking applies
(can be used) to user-defined containers too?

What do you mean by that ? You want to restric a map index ?

Pascal.

--

--|------------------------------------------------------
--| Pascal Obry Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--| http://www.obry.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

 

[Ioannis Vranos]

What do you mean by that ? You want to restric a map index ?

In the "STL like" library do you have something like valarray or vector?

 

[Georg Bauhaus]

I forgot to say here that the cost of map's operator[] is O(log(n))
which is fairly cheap for large amount of data.

compare O(log(n)) to O(1) where n is 1, 1000, 1_000_000.
Make this access a part of an inner loop.

If you do the maths, you will see that log(10^6) isn't that large.

Compare log(10^6) to 1.

I can't see how O(log(n)) isn't huge when compared to
O(1), in an inner loop for containers of size 10^6.


Georg

 

[Georg Bauhaus]

What do
you do in Ada if you want to associate product names with prices, in the
style

Once again you are trying to escape the problem...
We are not discussing the value of a map. We are not
debating it either.

A map *is* most valuable. A map is *not* a vector.
Sometimes you *need* a vector. A vector is *not* a convenient
replacement for a map in C++.

And of course there are maps for Ada, but this is OT.

 

[Ioannis Vranos]

Compare log(10^6) to 1.

I can't see how O(log(n)) isn't huge when compared to
O(1), in an inner loop for containers of size 10^6.

OK, but besides the fact that only explicit entries in map occupy space,
and the rest keys return 0, which means that the search and counting of
a value is faster than an array in case that no the entire range is
under use, there are also third-party hashed containers, including
hashed maps.

Also, as I said it is not difficult to define an array that takes
arbitrary signed ranges, but this does not make much sense in C++.


In other words, the direct equivalent of your array is probably
valarray/vector, ignoring the signed ranges.


BTW, the compile-time boundary checks you have been mentioning, sounds
like they are restricted to built-in arrays, which means is not of much use.


Also the lack of a "STL like" library in Ada until now probably sounds
like that Ada lacks much of the high-level abstraction that C++ provides.

 

[Ioannis Vranos]

Once again you are trying to escape the problem...
We are not discussing the value of a map. We are not
debating it either.

A map *is* most valuable. A map is *not* a vector.
Sometimes you *need* a vector. A vector is *not* a convenient
replacement for a map in C++.

And of course there are maps for Ada, but this is OT.

OK, one can use a vector then. And as I said in other messages, it is
not difficult to define an array that takes arbitrary signed ranges, but
this does not make much sense in C++.


In other words, the direct equivalent of your array is probably
valarray/vector, ignoring the signed ranges.

 

[Ioannis Vranos]

OK, one can use a vector then. And as I said in other messages, it is
not difficult to define an array that takes arbitrary signed ranges, but
this does not make much sense in C++.


In other words, the direct equivalent of your array is probably
valarray/vector, ignoring the signed ranges.

BTW does Ada provide dynamic arrays like vector/deque?

 

[Dmitry A. Kazakov]

For a domain problem where you have to create an area centered on (0,0)
for example. What about a vector representing altitude, the sub-zero values
being under the water. Just some examples, I bet you'll be able to think about
lot more

I think an associative container like map fits better to this. What do
you do in Ada if you want to associate product names with prices, in the
style

productlist["something"]= 71.2;

or a name with a number (string with string) in an address book
application for example?

namelist["Obry Pascal"]="321-45563";

In general, we use ADT. It is also a recommended practice in C++, BTW. What
would you do with

namelist["Pascal Obry"]="+0 321/45563 ";

or

namelist["321-45563"]="Pascal Obry";

Note that both Ada and C++ support ADT. Ada's arrays is just an example of
ADT. It is possible in C++ to implement an array as a set of classes though
it will be much more verbose and suffer from numerous drawbacks.

Also may you tell me if that famous compile-time boundary checking
applies (can be used) to user-defined containers too?

Of course it does. It is no different. The bounds can be specified either
as discriminants or as generic parameters (the latter has C++ equivalent).
As for the types with discriminants, they can be statically/dynamically
constrained and this is propagated down to the implementation where the
constraints are used. If corresponding methods are inlined then nothing
prevents the compiler from checking statically known bounds at
compile-time.

I seems to me that you still missing the point. Ada's ability to check
bounds is based on the idea of constrained subtypes. It is a fundamental
concept which C++ lacks. (The only weak form of constraining C++ supports
is templates specialization.)

 

[Pascal Obry]

In the "STL like" library do you have something like valarray or vector?

We have vector.

Pascal.

--

--|------------------------------------------------------
--| Pascal Obry Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--| http://www.obry.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

 

[Georg Bauhaus]

time_.


At first, it is easy to write

Not the point.

a container in C++ that accepts a
specified range for indexes.

A vector has an index range built into the language C++.
It was stated that type based indexing together with
attributes helps both the writer and the compiler.
No programmer effort needed.

The only reason that there is not one, is
because it does not make sense in C++

Interesting claim. I Don't buy it. It is just not available
in the language.

The [0, +] style maps closely what is
happening in the machine.

Another Off Topic.

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

Why are you repeating this? Not the point.

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

Elsewhere you say that it is possible and does make sense
to work around this lack using compile time assertions,
carfully placing them close to the object to which they are somehow
related. (Effectively creating an ad-hoc meta-language written in
templates. Only shows that the thing is indeed missing in C++.)

It makes sense to know the bounds of a container,
possibly in advance. Are you declaring that std::vector and
not knowing the bounds is the only reasonable thing to do in
programming?

Type attributes are a mode of expression, available with
types in Ada. You can build algorithms around language provided
attributes, for example bounds, without having to resort to
mere conventions and the hope that the compiler will do something
useful with the conventional items.

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.

In other words, C++ array like types don't have these properties.
I'm not saying this is catastrophic. It's just not available
unless you roll your own. This has consequences for how you write
your software. It has consequences for what your compiler can do.
Some of them are interesing, because of template computing.

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

It was given, starting this "sub"thread.

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?

An enum is a user defined type.
Any unconstrained type (including more than array types)
entails constrained objects, and the compiler may have a word
in this.
Maybe, if one gets used to template programming, the basis of the
language is deliberately ignored?
Ada just doesn't need templates for many things that are tried
using templates in C++, because the things are already in the
language.

Or is
this restricted to built-in arrays? If the latest is true, then its
value isn't that much.

Every bug that is found at compile time is worth a lot
to me.

Try telling someone that useful array attributes, and type attributes
and object attributes in general, aren't of much value.
What else are .begin() and .end() other than roll-my-own replacements
for something that C style arrays lack, *language-wise*?
Those working for an insurance company, in a stocks related business,
in math related computing, statistics, etc. use *Array Programming
Languages*. Why would they be doing this if good array support
isn't worth something? What is the value of good array support in
all those valuable Fortran computing libraries?

Are you saying that a robust base type system isn't worth it because
of the STL?
Consider the effort is takes to get a useful STL made of
basically, at-least-so-many-bits integers, pointers, and malloc().

Please answer this question:
Why is vector not implemented using vector? (I'm serious.)

I think that the value of defined subranges in the style
-1000, -400 has not any practical use.

Any evidence?

What do you mean by names?

I mean object names (enumerated identifiers), not strings. Like in

typedef std::map<Some_Enum, int> Slow_Array;

This is not the same as

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

You just gave an example of an assertion working around
the indexing issue... So apparently proper indexing has
a value in the world of C++, contradicting your claim.

Fastest possible access in C++.

The fastest possible element access in C++ is dereferencing a pointer.
The fastest possible element access in STL/C++ is varying with container
and method.

Compare

type Floor_Number is -2 .. 52;
-- sky scraper

type Door_Count is array(Floor_Number) of Natural;

versus

typedef char Floor_Number;
typedef std::map<Floor_Number, unsigned int> Door_Count;

We are discussing fastest access, and type based indexing.

So my question again, what does it take, in C++, to replace
Floor_Number as typedefed above with something that matches
the given building's floors exactly? What is the price to pay?

is the Ada compile-time boundaries checking available
to user-defined containers?

We are discussing the value of a container that doesn't *need*
to be defined because it is built into the language's type system,
with all bells and whistles and compiler help. No user definition
is *needed*, it's already there.

If you insist on leading us astray and on constructing your own
containers: The presence of bounds checking in programmer defined
ADTs depends on how they are defined.

can compile-time assertions be used?

The compiler will warn you when it can evaluate the expression
in a pragma assert at compile time. More importantly, the
compiler will use the compile-time checking required by Ada
array types. No need for programmer assertions expressed
using add-on templates.

Of course
one can always program improperly.

I did say that this is not the point, didn't I?

The point is, how does a language help you writing
correct and efficient programs. C++ the language doesn't
have fixed size built in arrays. In some problem domains,
fixed size arrays are very useful, if not essential.

This is why many programming languages have them.

Georg

 

[Georg Bauhaus]

OK, but besides the fact that only explicit entries in map occupy space,

Yet another issue having nothing to do with how
Ada arrays compare to C++ style arrays when the problem
requires plain arrays, not sparse arrays.

Also, as I said it is not difficult to define an array that takes
arbitrary signed ranges, but this does not make much sense in C++.

Any evidence?

In other words, the direct equivalent of your array is probably
valarray/vector, ignoring the signed ranges.

"ignoring" seems to be an attitude in your responses. ;-)

built-in arrays, which means is not of much use.

Do you know what a built in array really is, and what it does?

Also the lack of a "STL like" library in Ada until now probably sounds
like that Ada lacks much of the high-level abstraction that C++ provides.

Oh, come on. You are making claims about a language and
then guess about it? For many things a library was just not
needed in Ada. The language already provided what was needed,
including the high level of abstraction.

I've tried to picture the higher level of abstraction
in the Ada base type system that is just not present in C++.
For example, there is no need for .begin() and .end() in Ada
because it has always had these as attributes. In Ada it has always
been possible to write a generic array algorithm simply by requiring
that the G in <typename G, ...> is of an array type. There was
no need to add the hot new things like Can_Copy because they
were already in the language.

There have always been well designed ADT libraries (including
graph support). One of them has actually been ported from Ada 83 to C++,
and later to Ada 95 (Booch components).

Come to think of it, I don't know of anything like task *types*
and shared variable *types* built into the language C++.
This is right under your nose as high level abstractions
in plain Ada program structuring.

µC++ adds concurrency support to the C++ type system, at a somewhat
lower level of abstraction than Ada.
Still, µC+++ reimports the weaknesses of the precursor languages.
Sad, but successful because of mass momentum.

Georg

 

[Vinzent 'Gadget' Hoefler]

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.

So? Let me take a look at some current project:

|type DAC_Range is new Interfaces.Unsigned_8;
|type Offset is new Interfaces.Integer_8;
|
|-- lookup tables are faster
|type Offset_Skew is array(Offset) of DAC_Range;

So the array indices are - of course - from -127 to 128.

(Of course you can remap that to 0 to 255, but because I am calculating
in signed range for relatively obvious reasons, this is much more
convenient.)


Vinzent.

 

[Matthew Heaney]

Ada 2005 will have both ordered ("sorted") maps and hashed maps. The
current C++ standard only has ordered maps.

I have probably missed a trick in the C++, but I couldn't get
std::map code to compile (except in the trivial cases):

#include <map>

struct compoundindex {
int a, b, c;
};

This type doesn't have a relational operator, which you need to
instantiate the map.

--
The Ada associative arrays from the new draft standard
are specified as something like:

generic
type Key_Type is private;
type Element_Type is private;
with function Hash (Key : Key_Type)
return Hash_Type is <>;
with function Is_Equal_Key (Left, Right : Key_Type)
return Boolean is "=";
with function "=" (Left, Right : Element_Type)
return Boolean is <>;
package Ada.Containers.Hashed_Maps is...

Yes, but the analog to the C++ map is Ada.Containers.Ordered_Maps, not
the hashed map.

Which clearly won't work unless you can find the three
function generic parameters. I don't see how this can be
used easily in a generic context.

But this is true of C++ as well. There's no magic: your key either
needs a relational operator (for the ordered map), or it needs a hash
function (for the hashed map).

I don't think I am being *that* unreasonable in asking for arrays
indexed by arbitrary types, without jumping through hoops

Requiring that the key used to instantiate a hashed map have a hash
function hardly constitutes "jumping through hoops." In any event, you
probably want an ordered map anyway:

generic

type Key_Type is private;

type Element_Type is private;

with function "<" (Left, Right : Key_Type) return Boolean is <>;

with function "=" (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Ordered_Maps is


in which case all you need is a relational op:

function "<" (L, R : Compound_Index) return Boolean is
begin
if L.A < R.A then
return True;
end if;

if L.A > R.A then
return False;
end if;

if L.B < R.B then ...
end;

package Compound_Index_Maps is
new Ada.Containers.Ordered_Maps (Compound_Index, Float);

declare
M : Compound_Index_Maps.Map;
begin
M.Include (Key => (1, 2, 4), New_Item => 0.123);
end;

 

[fabio de francesco]

BTW does Ada provide dynamic arrays like vector/deque?

Ciao,

I think we don't have to care about the presence of a high-level
construct like whatever container. When C++ hadn't yet standardised
containers, everyone could actually build these higher-level structures
by himself. The only problem is standardisation. If you have languages
that are sufficienly low-level like C++ and Ada you can manufacture
every type of algorithm and containers you need.

You build higher-level components by using lower-level built-in
language features. Every compile-time or run-type check that you can
have for built-in types you "inherit" for user created structures. This
is said to answer your past question about Ada having or not same
checks for built-in types and user defined types.

I suppose std::vector is a simple array which must be copied to a
larger one in order to insert a new element while it is full. You know
it can be done in Ada too.

What's more in Ada is that you can, in a standardised way, directly
create low-level representation of user defined types with a lot of
attributes that C++ doesn't provide. Ada programmers prefer to build
their own types rather than using built-in Integer, Float, Long_Float
(int, float, double) and so on in order to gain a much finer control.

In Ada you can decide representation attributes like range, digit,
delta, mod, address, alignment, size, byte-order (little or big endian)
in record component, and many other things like these. As an example
you can write:

type Counter is new Integer;
for Counter'Size use 48;
for Counter'Alignment use 16;

What's more, you get a compiler error if your machine can't use some
sort of representation you need in order to free you from knowing how
much space a type can provide.

You said that real C++ code hardly need to specify ranges, because you
should be careful not to assign a value that can't be held by a
variable of some specific type. Imagine you have know a variable is to
hold numbers not larger than 99_999 and you choose to store them in an
"int" knowing that you have enough space. When later you port your
program to a machine where "int" is 16 bits you don't have any warning
from a C++ compiler and program run for years until for some reason
that variable is assigned with say 86_000. I think you know what
happens..

If you had that type declared as "type Var_T is range 0 .. 99_999;", at
the very moment you port your program to this new machine the compiler
would choose the correct size to hold values of that type so program is
no more restricted to this 16 bits C++ "int" and consequently won't
raise this bug.

Do you still think you don't need ranges?

Regards,

fabio de francesco

 

[bjarne]

Hmm... Isn't that language called Simula 67? ;-)


- Bob

The Algol I was talking about in that context was Algol68. The result
would have been a more flexible and efficient language than Simula67
and a cleaner language than C++ became. Unfortunately, there was no
chance of such a language succeeding at that time and place - the
understanding of the basic concepts among the intended users and the
infrastructure needed to get work done were missing. It would have been
yet another beautiful, but stillborn, language. C++ was designed in
response to pressing problems, not as a 10-year project aimed at
abstract beauty. I think that in the long run, it actually gained from
that.

If you want to understand how and why C++ was done, have a look at
Stroustrup: "The Design and Evolution of C++" (Addison-Wesley). If
nothing else, it might help you to avoid revisionist history and wild
conjecture. I think that documenting decisions about major tools is
important and should not be confused with "confessions".

I chose C as a base for C++ because - among the many languages I knew
of - it was the one that came closest to my needs. It wasn't perfect
and C compatibility became a bigger problem than I had bargained for,
but noone "forced me" (as is conjectured, incl. in this thread).

And no, C++ was never meant solely for object-oriented programming
(when defined as programming using class hierarchies). Support for data
abstraction and procedural programming was mentioned in my earliest
papers, and a 1981 paper grapples (rather unsuccessfully) with the
basics of generic programming.

-- Bjarne Stroustrup; http://www.research.att.com/~bs

 

[Robert A Duff]

The Algol I was talking about in that context was Algol68.

OK, fair enough. I *did* put a smiley there!

...The result
would have been a more flexible and efficient language than Simula67
and a cleaner language than C++ became.

I agree.

... Unfortunately, there was no
chance of such a language succeeding at that time and place - the
understanding of the basic concepts among the intended users and the
infrastructure needed to get work done were missing. It would have been
yet another beautiful, but stillborn, language. C++ was designed in
response to pressing problems, not as a 10-year project aimed at
abstract beauty. I think that in the long run, it actually gained from
that.

If you want to understand how and why C++ was done, have a look at
Stroustrup: "The Design and Evolution of C++" (Addison-Wesley).

I've read it. (And enjoyed it very much!)

... If
nothing else, it might help you to avoid revisionist history and wild
conjecture. I think that documenting decisions about major tools is
important and should not be confused with "confessions".

I apologize for what might seem like "wild conjecture". That wasn't my
intent -- I was just making a silly joke based on the phrase "Algol with
classes". Sorry.

I chose C as a base for C++ because - among the many languages I knew
of - it was the one that came closest to my needs. It wasn't perfect
and C compatibility became a bigger problem than I had bargained for,

As one of the designers of Ada 95, I know very well what it is like to
design a language when compatibility is a constraint.

but noone "forced me" (as is conjectured, incl. in this thread).

And no, C++ was never meant solely for object-oriented programming
(when defined as programming using class hierarchies). Support for data
abstraction and procedural programming was mentioned in my earliest
papers, and a 1981 paper grapples (rather unsuccessfully) with the
basics of generic programming.

-- Bjarne Stroustrup; http://www.research.att.com/~bs

- Bob