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

[Robert A Duff]

I agree.

However C++ has also the ideal to be able to write these libraries with
the language itself.

As opposed to... ?

- Bob

 

[Dr. Adrian Wrigley]

On Mon, 14 Mar 2005 16:02:43 -0500, Robert A Duff wrote:

I agree -- that's a pain.

The only way around it, it seems to me, is to have the compiler
automatically create a hash function (or something) for every type --
after all, you can't expect to create these kinds of containers without
a hash function (or something, like "<"), whether the user is required
to write it or not. Lots of languages do something like that...

precisely. That was my point (Friday) about needing proper
language support for associative arrays in both C++ and Ada, or
(as you suggest) lower-level prerequisites. In Ada, maybe it could
be a 'Hash attribute.

I think we can also see clearly how generics/templates are only
superficially equivalent in what programmers demand of them.
The contract model being a big part of the encapsulation process
considered essential by Ada users, but *worse than useless* from
the C++ view.

Thnaks Rob for putting the points more eloquently!

 

[Greg Comeau]

Well, let's see. Off the top of my head, Ada compilers are available
from Sofcheck (that's my company), AdaCore (that's the free software
version; they make their money by providing support), Greenhills
(which uses the SofCheck Ada front end, and supports many embedded
targets), Aonix (also uses the SofCheck front end), RR Software,
DDC-I, ICSC (sp?), IBM... (Did I forget some?)

I don't know which ones pass (the required portion of) the ACATS.
My guess is: all of them.

(The reason there are ACATS tests that are not required is that some
portions of the language standard are optional. The standard has
optional annexes for various specialized purposes: real-time,
information systems, safety critical, etc.)

By the way, SofCheck's current focus is not Ada compilers: we're
concentrating on static analysis tools for Java and Ada and eventually
other languages such as C++. But we still make most of our revenue
from the compiler side of the business.


...but of course there's a lot of market pressure to produce
standard-conforming compilers, for those languages that have official
standards (Ada, C, C++, Fortran, Cobol, etc).

And hence why I'm curious exactly which ones are fully standard
conforming, optional parts aside (or at least clearly labelled).

 

[Robert A Duff]

Newsgroups: comp.lang.ada,comp.lang.c++,comp.realtime,comp.software-eng
Subject: Re: Teaching new tricks to an old dog (C++ -->Ada)
References: <[email protected]> <[email protected]> <[email protected]> <[email protected]> <[email protected]> <[email protected]> <[email protected]>
From: Robert A Duff <[email protected]>
Organization: The World Public Access UNIX, Brookline, MA
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2
Date: 14 Mar 2005 17:35:28 -0500
Message-ID: <[email protected]>
Lines: 139
--text follows this line--

My knowledge of this is a little dated and hazy, so I could be wrong.

If we're doing something like:
foo()
{
int x, y;
bar()
{
int y;
gah()
{
use(x), use(y);
}
}
}

then, at run-time, in use(x), x comes from the stack-frame of the
nearest invocation of foo() on the stack, and in use(y), y comes from
the stack-frame of the nearest invocation of bar().

Right. Note that multi-level nesting as in this example is rare in
languages that allow nesting. (And of course nonexistent in languages
that don't!) The vast majority of procedures are not nested (level 0),
some are nested (level 1), and extremely few are more nested (level 2 or
more). So to implement this stuff efficiently, the compiler writer
should keep this in mind.

There has to be a mechanism to identify the nearest invocation of
foo()/bar(). There are, if I remember correctly, 4 mechanisms to find
the invocation:
- dynamic chaining: you just follow the back-chain pointers, stepping
through all stack frames, till you come to the right stack frame.

I don't know of any compilers that do that. To make that work, you'd
have to have some way to identify the "right" stack frame, and I can't
think of any way to do that efficiently.

- static chianing: you maintain a separate chain (the static chain) that
directly link to the stack frame of the enclosing functions. Thus the
static chain for gah() would have the last invocation of bar() followed
by the last invocation of foo().

That's the method I prefer. The best way to think about it is: the
static link is an extra parameter passed to the called function.
Each nested function needs a parameter that somehow represents its
context.

Given that multi-level nesting is rare, the chain is usually length 1
(or we don't need to do anything at all, for the nonnested ones).

- display: somewhat like the static chain, except its an array instead
of a list

To me, that seems like an attempt to optimize multi-level nesting, which
is why I don't prefer it.

- currying (?): this one I'm really hazy about, but, roughly, you passed
pointers to the correct uplevel variables as extra arguments to the
functions. Thus bar would be passed the pointer to x and gah would be
passed pointers to x and y, as well as their other arguments, or
something like that.

Yes, something like that makes sense; I view it as an optimization of
static chains. It's not what I know as "currying", though, which is
something completely different. In the example you gave, you can pass x
and y, not pointers to them.

There were some additional nastinesses dealing with what happens when a
nested function is passed as an argument

It's really no big deal. When passing a nested procedure to an outer
one, you need to pass an extra parameter indicating the enclosing
context. When using static chains, this is just the static link.
Or, in some cases, optimize by doing what you called "currying" above.
(Which is just like optimizing by passing the components of a struct
instead of passing a pointer to it.)

Note that Ada distinguishes (syntactically) the case where the passed
procedure can be nested, and the case where it cannot. The case where
it cannot is handled exactly as in C -- pass just the address of the
procedure's code.

(Actually, that's an oversimplification -- the nonnested case is really
the same-nested case, which includes the C case of nonnested.)

Or, in many cases, inline the whole mess, and there's no call overhead
at all.

Yes, there is some cost -- it complexifies the compiler, for one thing.
But the run-time cost is really near zero.

By the way, there's another method you didn't mention. The gcc dialect
of C supports nested functions (and passing those as parameters), and
they're implemented using trampolines.

Depending on the techinques, you either pay whenever you access
variables of enclosing functions, or you pay to maintain the
data-structures [static-chain,display] which make this access cheaper,
or both.

Right. But in most cases, you pay nothing, and in the cases where you
pay, you're getting something for it (like, not having to pass extra
parameters, which you would have to pay for instead).

On some implementations (on RISC architectures) a register is reserved
for the static-chain. This means one less register for *every* function
(or maybe only for enclosed functions?) when used with a language that
support this kind of nested functions.

Only for nested functions. And when passing functions as parameters, if
the function *might* be nested (which, in Ada, the compiler knows).

C++ probably left it out because of its C heritage,
Yes.

... while Ada probably
dropped it in because of its Pascal heritage.

Perhaps, but it's not just Pascal. It's pretty much every language from
Algol and Lisp onward. This feature is really extremely useful!

... IMHO, its probably not
worth the cost.

Well, my philosophy is: the (run-time) cost is irrelevant. If you need
some feature, you need it, and if it's not in the language, you have to
implement it yourself, and that will cost at least as much. What's
relevant is distributed overhead: if you pay the cost for a feature when
you *don't* use a feature, then that's a good reason to leave it out of
the language. IMHO, to argue against nested procedures, you have to
either argue that they're not very useful, or you have to argue that
they cause distributed overhead (cost when you don't need them). You
can't just argue that they're slow, because the alternatives
(implemented by hand) are just as slow.

- Bob

 

[Ioannis Vranos]

OK. How about a trivial but reasonable example:

#include <time.h>
#include <map>

struct interval {
tm start, finish;
};

int main()
{
std::map<interval, float> hash;
interval fred;

// set fred here!

hash[fred] = 0.123;
}

No suitable place to put the compare operator!

I am not sure I understood what you are saying. First, map is not using
hash, so the identifier hash may be misleading.

Secondly you can either specify an operator<, or a predicate like this:


#include <ctime>
#include <map>

struct interval
{
std::tm start, finish;
};

struct IntervalLessCompare
{
inline bool operator() (interval a, interval b) const
{
using namespace std;

return difftime( mktime(&a.finish), mktime(&a.start) ) <
difftime( mktime(&b.finish), mktime(&b.start) );
}
};

int main()
{
using namespace std;

map<interval, float, IntervalLessCompare> somemap;

interval fred;

// set fred here!

somemap[fred] = 0.123f;
}

 

[Ioannis Vranos]

As opposed to... ?

.... other slimmer languages using "exotic" libraries.

 

[Martin Dowie]

Other posts seems to disagree. Please clarify for us.
Also include how and why your company is the _official_ lab.
(I'm not challenging you, but seems to me a mixed message
is coming through this thread.)

Because the "Ada Compiler Assesment Authority" authorised it.

Some usefull links:
http://www.ada-auth.org/info.html
http://www.adaic.com/compilers/testing.html
http://www.adalog.fr/acal2.htm

Cheers

-- Martin

 

[Randy Brukardt]

....

Let's address the Ada side first. Official Ada validation was done
under the auspices of NIST, who delegated this task to the Ada Joint
Program Office. The AJPO ceased to exist years ago, and the job was
never turned over to anybody else when that happened.

This statement is false. I was going to try to explain precisely what
happened, but it probably is better to just point to the articles on that
topic that were published at the time. See:
http://www.adaic.com/compilers/index.html
and in particular:
http://www.adaic.com/compilers/acaa.html

The ARA funding of the ACAA continues today; the process is alive and well.
There has been a significant drop off in formal testing, supposedly because
customers aren't demanding it as much as they did in the past. (Personally,
I think that is a good thing, because it lets implementers concentrate on
what's important to their customers rather than formal testing -- even
though it means I make less money. It's also less necessary because all Ada
vendors run the test suite regularly as part of their in-house regression
tests -- there isn't anyone trying to get by without conforming.)

Randy Brukardt
ACAA Technical Agent

 

[Randy Brukardt]

....> >
I can assure you that there is still one official ACAL (laboratory for

Other posts seems to disagree. Please clarify for us.
Also include how and why your company is the _official_ lab.
(I'm not challenging you, but seems to me a mixed message
is coming through this thread.)

See the links I posted earlier. The ACAA is an instantiation of ISO 18009
funded by the Ada Resource Association. AdaLog is an accredited ACAL under
ISO 18009.

Note that AJPO transferred pretty much all of its programs and materials to
the ARA, including its website (www.adaic.org), validation testing,
marketing programs, and so on. Anyway, it seemed better to put "conformity
assessment" under an International Standard rather than a program managed by
a specific country.

Randy Brukardt

 

[Robert A Duff]

... other slimmer languages using "exotic" libraries.

Such as... ?

I'm still not understanding your point. Are you referring to the fact
that the Java garbage collector cannot reasonably be implemented in
Java, and things like that?

- Bob

 

[Hyman Rosen]

Even in simple cases, the encapsulation has to be broken

Free functions that help implement an abstraction don't break
encapsulation, they are part of it.

 

[Ioannis Vranos]

Such as... ?

I'm still not understanding your point. Are you referring to the fact
that the Java garbage collector cannot reasonably be implemented in
Java, and things like that?

Apart from these, let's talk about Pascal for example. I do not think
everything in its library can be written with the language itself.

 

[Hyman Rosen]

Because the "<" (or Hash) needs to know the internals of the thing.

It may be possible to order the objects through information
available from public accessors, so this is false.

In other words, at the point where you declare a type, you have to think
ahead: this type might want to live inside one of those containers, so
I'd better define the necessary operations.

False, as per above. In fact, the ordered containers can be instantiated
with order functions, so there need not be a single unique ordering for
a given type.

For example, any string type has a public way of delivering up the
characters it contains. That lets you define string containers which
hold their strings in alphabetical order, in case-insensitive order,
or even in pig-latin order if you want. None of this requires the
string implementor to anticipate such ordering requirements.

 

[Hyman Rosen]

This means that you can't write an implementation of a template/generic
function using a map/hash without changing some/all the implementations
and interfaces up the instantiation tree (am I right?).

No, you are wrong. Simply write your comparison or hash function at the
point where you need it. Use the public accessors to get the data you
need to perform the operations.

 

[Robert A Duff]

It may be possible to order the objects through information
available from public accessors, so this is false.

OK, please let me amend my statement to "...*usually* needs to know...".

So "this is false" should be "this is sometimes false".

False, as per above. In fact, the ordered containers can be instantiated
with order functions, so there need not be a single unique ordering for
a given type.

For example, any string type has a public way of delivering up the
characters it contains. That lets you define string containers which
hold their strings in alphabetical order, in case-insensitive order,
or even in pig-latin order if you want. None of this requires the
string implementor to anticipate such ordering requirements.

Yes, if the thing has a natural "<" function, or some public information
from which that can be garnered, then "<" is not a problem. That's true
of character strings. And of course I understand that you can sort
backwards by using a different function (as in "<" => ">" in Ada
terms).

But if you want to hide most of the data of some abstraction, and
there's no "natural" meaning of "<", then you have to think ahead, and
define some "<" operation just in case somebody wants to put the thing
into a container. (Or, of course, go back and add that in to an
existing data type when you find it's needed.)

The same is true with Hash. For a character string type, you can
declare it on the fly, because such a type exposes all the data. But
for a type that's "private" in Ada, or has protected/private members in
C++, the Hash function, like the "<" function, often needs access to the
private data. In Ada, you can use a child (which does not require
modifying the original thing). In C++, you can use a friend. Or, in
either language, you can just put Hash or "<" in the original thing.

One possibility is to have a coding convention: always declare "<" and
Hash for every data type, just in case it might be needed for one of
these containers.

- Bob

 

[Dr. Adrian Wrigley]

struct IntervalLessCompare
{
inline bool operator() (interval a, interval b) const
{
using namespace std;

return difftime( mktime(&a.finish), mktime(&a.start) ) <
difftime( mktime(&b.finish), mktime(&b.start) );
}
};

Doesn't this break down for times beyond the end of the epoch,
which are valid tm values, but invalid time_t values?
You've ended up mapping all post-epoch times to the same entry!

Doesn't it also break down when someone adds a microsecond
value in the tm struct for some platforms? Seems like
a reasonable thing for someone to try to do, but breaks this
code. You have to then introduce a platform specific fix.
Maybe unlikely for ctime, but there are plenty of less stable
interfaces. What if it was mm.h's mem_core struct (Linux)?
What about things with floating point components, where
different values compare as equal (+0 and -0) and
identical values (NaN) give inconsistent comparison?

In general, you may need to use "private" implementation details
of the class when defining the operator, ending up with
broken code, broken "contracts" and broken encapsulation.

This is sounding too much like a troll, and I think the points
have been fully made by Robert and others. I have learnt that
there is a major gulf between users' expectations of C++ templates
and of Ada generics. "contract model" is the difference.

 

[Dr. Adrian Wrigley]

No, you are wrong. Simply write your comparison or hash function at the
point where you need it. Use the public accessors to get the data you
need to perform the operations.

That's the point... there aren't any public accessor functions
for opaque data types such as non-limited generic formal parameters.

 

[Robert A Duff]

Apart from these, let's talk about Pascal for example. I do not think
everything in its library can be written with the language itself.

Pascal (as defined by Wirth) doesn't even support separate compilation,
so there is no concept of libraries in Pascal, so nothing in its
"libraries" can be written in Pascal.

- Bob

 

[Ioannis Vranos]

Pascal (as defined by Wirth) doesn't even support separate compilation,
so there is no concept of libraries in Pascal, so nothing in its
"libraries" can be written in Pascal.

Actually I had turbo pascal 6.x-7.x in mind.

 

[Larry Kilgallen]

On some implementations (on RISC architectures) a register is reserved
for the static-chain. This means one less register for *every* function
(or maybe only for enclosed functions?) when used with a language that
support this kind of nested functions.

It does not have much to do with whether one language supports it,
so long as _some_ language supports it.

If I have a call chain:

Ada => C => Ada

that second Ada subprogram might want to access a variable in the first
Ada subprogram. So the C implementation must pass the context along.
As I understand it, that is the job of the "Bound Procedure Value"
construct in the VMS Calling Standard. Such relationships between
languages must be defined by the calling standard for the platform,
meaning that the C compiler should honor it as well. I imagine that
HP Ada and HP Pascal interact properly in this regard -- I have no idea
about HP C.

C++ probably left it out because of its C heritage, while Ada probably
dropped it in because of its Pascal heritage. IMHO, its probably not
worth the cost.

If that is your opinion, I would say you have not done enough programing
in a language where it is provided.