Sharing generic bodies across instantiations.

Sharing generic bodies across instantiations.

[Peter C. Chapin]

It has been my understanding that Ada's generics are designed in such a
way as to allow implementations to share the code of a generic body
across all the instantiations. I understand that doing this might
involve a performance penalty relative to creating independent code for
each instantiation. However, I can see that there are cases where such
sharing would be desirable.

Is my understanding still accurate (was it ever accurate), for example
even with Ada 2005?

Thanks!

Peter

Re: Sharing generic bodies across instantiations.

[Gene]

On Jul 26, 8:51 pm, "Peter C. Chapin" <pcc482...@gmail.com> wrote:
> It has been my understanding that Ada's generics are designed in such a
> way as to allow implementations to share the code of a generic body
> across all the instantiations. I understand that doing this might
> involve a performance penalty relative to creating independent code for
> each instantiation. However, I can see that there are cases where such
> sharing would be desirable.
>
> Is my understanding still accurate (was it ever accurate), for example
> even with Ada 2005?
>
> Thanks!
>
> Peter

I don't believe this is true.  Early compilers replicated code for
each instantiation even when they might have been able to share. But
I've read that the compiler is free to choose to generate
parameterized code that's highly sharable.  Yes, in that case the
implementation will generate smaller but likely to be slower code.

You may be thinking of java templates, which explicitly require that
code is shared among all instances.  This is much easier in Java due
to the reference semantics.

Re: Sharing generic bodies across instantiations.

[AdaMagica]

As far as I understand, GNAT replicates, RR shares generic code.
(Don't know about IBM (former Rational).)

Re: Sharing generic bodies across instantiations.

[Martin]

On 27 July, 01:51, "Peter C. Chapin" <pcc482...@gmail.com> wrote:
> It has been my understanding that Ada's generics are designed in such a
> way as to allow implementations to share the code of a generic body
> across all the instantiations. I understand that doing this might
> involve a performance penalty relative to creating independent code for
> each instantiation. However, I can see that there are cases where such
> sharing would be desirable.
>
> Is my understanding still accurate (was it ever accurate), for example
> even with Ada 2005?
>
> Thanks!
>
> Peter

Allowed yes, required no.

-- Martin

Re: Sharing generic bodies across instantiations.

[Ludovic Brenta]

AdaMagica writes:
> As far as I understand, GNAT replicates, RR shares generic code.
> (Don't know about IBM (former Rational).)

My understanding is similar; indeed, Janus/Ada is the only compiler that
shares generics.  Unfortunately, no compiler offers the option to
choose; this is an implementation decision.

-- 
Ludovic Brenta.

Re: Sharing generic bodies across instantiations.

[Tero Koskinen]

On 07/27/2010 02:29 PM, Ludovic Brenta wrote:
> AdaMagica writes:
>> As far as I understand, GNAT replicates, RR shares generic code.
>> (Don't know about IBM (former Rational).)
>
> My understanding is similar; indeed, Janus/Ada is the only compiler that
> shares generics.  Unfortunately, no compiler offers the option to
> choose; this is an implementation decision.

If I have understood correctly, Irvine's Ada compiler supports
shared generics *and* provides a compile time option for this.

On the other hand, Janus/Ada doesn't provide an option. With it,
shared generics are always used.

-Tero

Re: Sharing generic bodies across instantiations.

[anon]

In <4c4e2d69$0$2378$4d3efbfe@news.sover.net>, "Peter C. Chapin" <pcc482719@gmail.com> writes:
>It has been my understanding that Ada's generics are designed in such a
>way as to allow implementations to share the code of a generic body
>across all the instantiations. I understand that doing this might
>involve a performance penalty relative to creating independent code for
>each instantiation. However, I can see that there are cases where such
>sharing would be desirable.
>
>Is my understanding still accurate (was it ever accurate), for example
>even with Ada 2005?
>
>Thanks!
>
>Peter

The Replication versus the Sharing of Generic code was initial based on the 
Ada Optimize pragma statement.  That is, when the users define the option 
of "Time" the Generic code would be replicated, but the "Space" option 
would cause the compiler to share the code body. Not using the pragma 
statement or the Ada 95 "off" option allowed the designer to set an 
implementation default.

Now as for GNAT it uses the optimization based on the GCC back end 
( -OX   where X in 0 .. 4 ). GNAT still preforms a syntactical check of the 
Optimize pragma statement, then treat's the statement as a comment like a 
number of other built-in Ada pragma statement.  Which allows GNAT to 
replicate code and let the GCC handle rather its switches to shared or not. 
And at this time GCC does not understand the Ada's concept replication 
versus the sharing code for optimization.

Re: Sharing generic bodies across instantiations.

[Peter C. Chapin]

On 2010-07-27 16:06, anon@att.net wrote:

> Now as for GNAT it uses the optimization based on the GCC back end 
> ( -OX   where X in 0 .. 4 ). GNAT still preforms a syntactical check of the 
> Optimize pragma statement, then treat's the statement as a comment like a 
> number of other built-in Ada pragma statement.  Which allows GNAT to 
> replicate code and let the GCC handle rather its switches to shared or not. 
> And at this time GCC does not understand the Ada's concept replication 
> versus the sharing code for optimization.

Thanks for all the replies to my question. I want to emphasize that my
interest is not so much in what is done by current compilers but rather
what is allowed by the standard. Is the standard (even the latest
standard) written in such a way as to make a shared implementation of
generic bodies possible? It sounds like the answer is yes.

In contrast I have the impression that in C++ it is not really possible,
or at least not feasible, for a compiler to share template bodies across
instantiations. That is, the nature of C++ essentially requires a
replication strategy. To be honest I'm not sure why I think this and I
might be wrong. This isn't a C++ group so it's probably not appropriate
to explore C++'s issues in too much detail here, but I will say that
haven't heard any serious talk in the C++ community about
implementations sharing template bodies.

Peter

Re: Sharing generic bodies across instantiations.

[Keith Thompson]

anon@att.net writes:
[...]
> The Replication versus the Sharing of Generic code was initial based on the 
> Ada Optimize pragma statement.  That is, when the users define the option 
> of "Time" the Generic code would be replicated, but the "Space" option 
> would cause the compiler to share the code body. Not using the pragma 
> statement or the Ada 95 "off" option allowed the designer to set an 
> implementation default.

I don't believe the definition of pragma Optimize was ever that
specific; as far as I know, it was always intended merely as a vague
hint.

Here's the description from the Ada 83 reference manual:

    OPTIMIZE Takes one of the identifiers TIME or SPACE as the single
    argument. This pragma is only allowed within a declarative part
    and it applies to the block or body enclosing the declarative
    part. It specifies whether time or space is the primary
    optimization criterion.

Using it to control generic code sharing would certainly be reasonable,
but it's not required.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

Re: Sharing generic bodies across instantiations.

[Maciej Sobczak]

On 28 Lip, 00:23, "Peter C. Chapin" <pcc482...@gmail.com> wrote:

> In contrast I have the impression that in C++ it is not really possible,
> or at least not feasible, for a compiler to share template bodies across
> instantiations.

Why?

> That is, the nature of C++ essentially requires a
> replication strategy.

Why? What part of that "nature" requires it?

From the point of view of object model and execution model, C++ and
Ada are very similar. Compilation and deployment strategies are more
or less equivalent.

> To be honest I'm not sure why I think this and I
> might be wrong.

To be honest I'm not sure why you came up with such an idea.
Formally, the C++ standard places no restrictions on how this should
be done.

> This isn't a C++ group so it's probably not appropriate
> to explore C++'s issues in too much detail here,

Don't worry, C and C++ are a frequent target of criticism here, so we
might as well discuss some details from time to time. ;-)

> but I will say that
> haven't heard any serious talk in the C++ community about
> implementations sharing template bodies.

Because the code-expansion model is easier to implement and that's
what most (all?) compiler vendors chosen to do.

But, for the sake of exercise, think about a C++ *interpreter*.

--
Maciej Sobczak * http://www.inspirel.com

YAMI4 - Messaging Solution for Distributed Systems
http://www.inspirel.com/yami4

Re: Sharing generic bodies across instantiations.

[Markus Schoepflin]

Am 28.07.2010 02:55, schrieb Keith Thompson:

[...]

> I don't believe the definition of pragma Optimize was ever that
> specific; as far as I know, it was always intended merely as a vague
> hint.
>
> Here's the description from the Ada 83 reference manual:
>
>      OPTIMIZE Takes one of the identifiers TIME or SPACE as the single
>      argument. This pragma is only allowed within a declarative part
>      and it applies to the block or body enclosing the declarative
>      part. It specifies whether time or space is the primary
>      optimization criterion.
>
> Using it to control generic code sharing would certainly be reasonable,
> but it's not required.

And Ada compiler is certainly not required to do anything but syntax 
checking for pragma optimize, but at least they had code sharing in mind 
when specifying the pragma.

 From the 2005 AARM:

<quote>
27.a Implementation defined: Effect of pragma Optimize.
27.b Discussion: For example, a compiler might use Time vs. Space to 
control whether generic instantiations are implemented with a 
macro-expansion model, versus a shared-generic-body model.
</quote>

Re: Sharing generic bodies across instantiations.

[Dmitry A. Kazakov]

On Wed, 28 Jul 2010 00:59:03 -0700 (PDT), Maciej Sobczak wrote:

> On 28 Lip, 00:23, "Peter C. Chapin" <pcc482...@gmail.com> wrote:
> 
>> That is, the nature of C++ essentially requires a
>> replication strategy.
> 
> Why? What part of that "nature" requires it?

Macro's nature

[...]
 
> But, for the sake of exercise, think about a C++ *interpreter*.

Interpreter is an obvious non-starter in this context. Generics are
considered compilable. Well, they are kind of compilable. Templates aren't
compilable, almost not. (There is no crisp line between compiled and
interpreted)

In other context, it could be different. E.g. both generics and templates
are in fact shared in the visual debugger. You can step into a "generic
body," even if there is no such object-code entity. That was not the OP's
question.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Sharing generic bodies across instantiations.

[anon]

In <lnvd80xw5l.fsf@nuthaus.mib.org>, Keith Thompson <kst-u@mib.org> writes:
>anon@att.net writes:
>[...]
>> The Replication versus the Sharing of Generic code was initial based on the 
>> Ada Optimize pragma statement.  That is, when the users define the option 
>> of "Time" the Generic code would be replicated, but the "Space" option 
>> would cause the compiler to share the code body. Not using the pragma 
>> statement or the Ada 95 "off" option allowed the designer to set an 
>> implementation default.
>
>I don't believe the definition of pragma Optimize was ever that
>specific; as far as I know, it was always intended merely as a vague
>hint.
>
>Here's the description from the Ada 83 reference manual:
>
>    OPTIMIZE Takes one of the identifiers TIME or SPACE as the single
>    argument. This pragma is only allowed within a declarative part
>    and it applies to the block or body enclosing the declarative
>    part. It specifies whether time or space is the primary
>    optimization criterion.
>
>Using it to control generic code sharing would certainly be reasonable,
>but it's not required.
>
>-- 
>Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
>Nokia
>"We must do something.  This is something.  Therefore, we must do this."
>    -- Antony Jay and Jonathan Lynn, "Yes Minister"


Besides Ada 83 chapter B on pragmas, a little more detail can be found 
in 10.3, 10.6, 11.6.

There are many forms of Optimizations. Sharing vs replicated and removing 
dead or unused code are some of the easiest to implement. Altering algorithms 
and expressions can be coslty.

If the optimization criterion is set to "Space" then using shared generic 
code reduces the memory but may increase time for the program to execute 
those routines.  As well as when the criterion is set to "Time" replicated 
code may be faster at the cost of using more memory.  So, the Ada Optimize 
pragma statement does not limited it self to only expressions it also 
includes the way generic codes are generated and used.


For Ada 95 RM 2.8 Pragmas

    27   A pragma Optimize takes one of the identifiers Time, Space, or 
         Off as the single argument.  This pragma is allowed anywhere a 
         pragma is allowed, and it applies until the end of the immediately 
         enclosing declarative region, or for a pragma at the place of a 
         compilation_unit, to the end of the compilation.  It gives advice to 
         the implementation as to whether time or space is the primary 
         optimization criterion, or that optional optimizations should be 
         turned off.  It is implementation defined how this advice is
         followed.

also check out D.12 Other Optimizations and Determinism Rules

Re: Sharing generic bodies across instantiations.

[Peter C. Chapin]

On 2010-07-28 03:59, Maciej Sobczak wrote:

> To be honest I'm not sure why you came up with such an idea.
> Formally, the C++ standard places no restrictions on how this should
> be done.

I understand that there is no statement in the C++ standard that says
template bodies can't be shared. My assumption has been that such a
conclusion follows indirectly from the other requirements.

I admit that I'm not a C++ implementer but I know that in general C++
imposes few restrictions on the way names in templates are used. Since
those names can be dependent on template parameters there would be a
large number of corner cases to support that might make a shared
implementation model "unreasonably" difficult. For example

template< typename T >
void f(const T &object)
{
  typename T::helper internal;
  ...
}

Here T::helper might be a class or a typedef. Depending on what it is a
wide variety of uses are possible. Dealing with all of these variations
in a shared implementation model would be quite a burden on the
compiler, it seems like. It might not be theoretically impossible but it
might be practically infeasible. There could well be other corner cases
I'm not seeing right now... that is the 'nature' of C++ of which I spoke.

I realize that implementing the shared model in Ada would be hard as
well, but Ada constrains much more the way names in generic bodies can
be used. I speculate that those limitations make implementing the shared
model in Ada easier and, in particular, easy enough to be feasible and
useful. Is that actually true? That's the essence of my original question.

> But, for the sake of exercise, think about a C++ *interpreter*.

That seems like a different situation to me. A pure interpreter executes
code only as needed and only when needed. Without a compilation step
isn't the question of shared or replicated bodies meaningless?
Everything is shared... or maybe everything is replicated... it would
depend on how one defined one's terms.

Peter

Re: Sharing generic bodies across instantiations.

[anon]

In <4c4f5c28$0$2375$4d3efbfe@news.sover.net>, "Peter C. Chapin" <pcc482719@gmail.com> writes:
>On 2010-07-27 16:06, anon@att.net wrote:
>
>> Now as for GNAT it uses the optimization based on the GCC back end 
>> ( -OX   where X in 0 .. 4 ). GNAT still preforms a syntactical check of the 
>> Optimize pragma statement, then treat's the statement as a comment like a 
>> number of other built-in Ada pragma statement.  Which allows GNAT to 
>> replicate code and let the GCC handle rather its switches to shared or not. 
>> And at this time GCC does not understand the Ada's concept replication 
>> versus the sharing code for optimization.
>
>Thanks for all the replies to my question. I want to emphasize that my
>interest is not so much in what is done by current compilers but rather
>what is allowed by the standard. Is the standard (even the latest
>standard) written in such a way as to make a shared implementation of
>generic bodies possible? It sounds like the answer is yes.
>
>In contrast I have the impression that in C++ it is not really possible,
>or at least not feasible, for a compiler to share template bodies across
>instantiations. That is, the nature of C++ essentially requires a
>replication strategy. To be honest I'm not sure why I think this and I
>might be wrong. This isn't a C++ group so it's probably not appropriate
>to explore C++'s issues in too much detail here, but I will say that
>haven't heard any serious talk in the C++ community about
>implementations sharing template bodies.
>
>Peter

For any compiler that uses the GCC backend (like GNAT, GCC C/C++) will 
use replicated for generic routines  It's easier for the compiler to handle 
"oops" programming. And that the way the GCC backend is written. 

Re: Sharing generic bodies across instantiations.

[Maciej Sobczak]

On 28 Lip, 11:28, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> >> That is, the nature of C++ essentially requires a
> >> replication strategy.
>
> > Why? What part of that "nature" requires it?
>
> Macro's nature

Wrong. Macros have nothing to do with templates.

> > But, for the sake of exercise, think about a C++ *interpreter*.
>
> Interpreter is an obvious non-starter in this context. Generics are
> considered compilable.

Paragraph, please.

> (There is no crisp line between compiled and
> interpreted)

That's the point.
A C++ or Ada interpreter can be fully standard-compliant, which makes
it a very valid "starter" in this context.

--
Maciej Sobczak * http://www.inspirel.com

YAMI4 - Messaging Solution for Distributed Systems
http://www.inspirel.com/yami4

Re: Sharing generic bodies across instantiations.

[Maciej Sobczak]

On 28 Lip, 13:27, "Peter C. Chapin" <pcc482...@gmail.com> wrote:

> For example
>
> template< typename T >
> void f(const T &object)
> {
>   typename T::helper internal;
>   ...
>
> }
>
> Here T::helper might be a class or a typedef.

Which makes no difference from the point of view of how to implement
that.
Think about:

char buf[sizeof(T)];

This is essentially the only problem that you have to solve, and that
does not seem to be very difficult.

> Depending on what it is a
> wide variety of uses are possible.

No, all uses have to be compatible with the code of the template. Even
though each T can have different ways of being used, the template has
to target the common subset of all such possibilities - otherwise the
program will not compile.
In other words, it does not matter how wide is the variety introduced
by different Ts - if the program compiles at all, it means that the
template is compatible with the common subset of all Ts uses. This
removes the variety out of the picture.

> There could well be other corner cases
> I'm not seeing right now... that is the 'nature' of C++ of which I spoke.

Sorry, but you did not identify any corner case for the moment.

> I realize that implementing the shared model in Ada would be hard as
> well, but Ada constrains much more the way names in generic bodies can
> be used.

Not really. AARM explicitly refers to the code copying when defining
the meaning of generics, see 12.3, especially this:

"The instance is a copy of the text of the template." (12.3/13)

and then a whole lot of consequent descriptions that are implied by
this.

I would even say that by being so explicit with this, AARM gives more
reasons to do macro-expansion than C++.

> > But, for the sake of exercise, think about a C++ *interpreter*.
>
> That seems like a different situation to me. A pure interpreter executes
> code only as needed and only when needed. Without a compilation step
> isn't the question of shared or replicated bodies meaningless?

Bingo and that's my point. This is why it does not make any sense to
say that C++ prevents some implementation scenario.
I can even imagine a combined approach, where each instantiation has a
facade that is distinct (this can target stuff like static objects)
and an actual implementation that is shared.

--
Maciej Sobczak * http://www.inspirel.com

YAMI4 - Messaging Solution for Distributed Systems
http://www.inspirel.com/yami4

Re: Sharing generic bodies across instantiations.

[Dmitry A. Kazakov]

On Wed, 28 Jul 2010 05:55:36 -0700 (PDT), Maciej Sobczak wrote:

> On 28 Lip, 11:28, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
> 
>>>> That is, the nature of C++ essentially requires a
>>>> replication strategy.
>>
>>> Why? What part of that "nature" requires it?
>>
>> Macro's nature
> 
> Wrong. Macros have nothing to do with templates.

They have the nature of source level uncontrolled and untyped substitution
and reinterpretation.

>>> But, for the sake of exercise, think about a C++ *interpreter*.
>>
>> Interpreter is an obvious non-starter in this context. Generics are
>> considered compilable.
> 
> Paragraph, please.
> 
>> (There is no crisp line between compiled and
>> interpreted)
> 
> That's the point.

Nope. The difference still exists, even if not qualitative. It can be
measured in terms of performance, usability, complexity, security etc.

> A C++ or Ada interpreter can be fully standard-compliant, which makes
> it a very valid "starter" in this context.

Interpreter does not qualify as a compiler, per definition of both. You
might say that apple is as edible as orange, but that would not make it
orange in the context of the greengrocery.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Sharing generic bodies across instantiations.

[Peter C. Chapin]

On 2010-07-28 09:10, Maciej Sobczak wrote:

>> Here T::helper might be a class or a typedef.
> 
> Which makes no difference from the point of view of how to implement
> that. Think about:
> 
> char buf[sizeof(T)];
> 
> This is essentially the only problem that you have to solve, and that
> does not seem to be very difficult.

Well there could be more to it than that. If T is a class with methods
(that are used in the template body) then the shared implementation
approach would have to contend with that. If the template body tries to
derive a class from T, perhaps overriding some of T's virtual functions
there is that to think about as well. Perhaps the template body will
throw a T object as an exception... although that might not be any more
complicated than tracking T's copy constructor and destructor.

In any case it seems like the compiler, in the shared implementation
approach, would have to pass in a hidden object into the template code
that details the capabilities of T that could be used by the shared
generic code (pointers to appropriate functions, etc). I can see that
only the capabilities actually used by the template would need to be
described but there would certainly be more than just the size of a T
involved.

I assume this is how it would work in Ada as well. The difference is
(might be) that in Ada there are more limitations on what a generic can
do so the list of things to worry about would be shorter.

As I said I haven't implemented either an Ada compiler nor a C++
compiler so I'm not sure exactly what the problems might be. That is
what I was asking. :)

> Not really. AARM explicitly refers to the code copying when defining
> the meaning of generics, see 12.3, especially this:
> 
> "The instance is a copy of the text of the template." (12.3/13)

That's interesting. Thanks for pointing that out. I wonder if that's
intended to be taken literally or if that really means the instance must
behave "as if" it is a copy of the text of the template.

> Bingo and that's my point. This is why it does not make any sense to
> say that C++ prevents some implementation scenario.

Well, okay. I see what you mean. To say the standard forbids a certain
implementation strategy is perhaps going too far. But there is a sense
of what can reasonably be done. The C++ community doesn't talk much
about a shared implementation of templates. Is that because it's just
unreasonably difficult in C++? I think many people in that community
would regard a pure interpreter as having too big a performance hit to
be acceptable. Of course I can't speak for everyone.

Peter

Re: Sharing generic bodies across instantiations.

[Robert A Duff]

"Peter C. Chapin" <pcc482719@gmail.com> writes:

> That's interesting. Thanks for pointing that out. I wonder if that's
> intended to be taken literally or if that really means the instance must
> behave "as if" it is a copy of the text of the template.

All formal language rules of all high-level languages mean "as if".
That goes without saying.

- Bob

Re: Sharing generic bodies across instantiations.

[Maciej Sobczak]

On 28 Lip, 15:16, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> > Wrong. Macros have nothing to do with templates.
>
> They have the nature

We were talking about the nature of templates, not the nature of
macros.
Macros have nothing to do with templates except for the fact that both
are supported by a single language, but there are also languages that
support only one or none of them. Reasoning about templates based on
macros' nature is pointless.

> Interpreter does not qualify as a compiler,

So the discussion was limited to compilers only? I did not found this
constraint in the original post.
Even if we assume such a limitation of discussion, there is still
nothing particular in the C++ standard that would prevent code sharing
as an implementation strategy for templates.

Interestingly, macros cannot use this strategy by their definition.

--
Maciej Sobczak * http://www.inspirel.com

YAMI4 - Messaging Solution for Distributed Systems
http://www.inspirel.com/yami4

Re: Sharing generic bodies across instantiations.

[Keith Thompson]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> On Wed, 28 Jul 2010 05:55:36 -0700 (PDT), Maciej Sobczak wrote:
>
>> On 28 Lip, 11:28, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
>> wrote:
>> 
>>>>> That is, the nature of C++ essentially requires a
>>>>> replication strategy.
>>>
>>>> Why? What part of that "nature" requires it?
>>>
>>> Macro's nature
>> 
>> Wrong. Macros have nothing to do with templates.
>
> They have the nature of source level uncontrolled and untyped substitution
> and reinterpretation.

Macros do.  Templates don't.

[...]

>> A C++ or Ada interpreter can be fully standard-compliant, which makes
>> it a very valid "starter" in this context.
>
> Interpreter does not qualify as a compiler, per definition of both. You
> might say that apple is as edible as orange, but that would not make it
> orange in the context of the greengrocery.

Apples and oranges are both fruits.  Compilers and interpreters
are both implementations.

Either a compiler or an interpreter can be a compliant implementation
of a language.

If you think a compiler is required, consider a hypothetical system
in which the "compiler" simply creates a copy the source code, and
the run-time environment interprets and executes the source code.
Such an implementation wouldn't be easy to create, but I can't think
of any way in which it violates the standard for either C++ or Ada.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

Re: Sharing generic bodies across instantiations.

[Maciej Sobczak]

On 28 Lip, 18:32, "Peter C. Chapin" <pcc482...@gmail.com> wrote:

> The C++ community doesn't talk much
> about a shared implementation of templates. Is that because it's just
> unreasonably difficult in C++?

Or maybe just pointless, regardless of the difficulty.

I don't see any reason for doing it, really. The only possible reason
would be to minimize the size of executable, possibly targeting some
very constrained environment, but there are ways to do it more
efficiently than with code sharing in templates - the technique, based
on making a facade template implemented in terms of non-template
actual code, was described by Scott Meyers, although at the moment I
don't remember exactly which of his book covered it. The major
advantage of this technique was *no performance penalty*. That is -
small *and* fast code.

In other words, the real reason for not having such compiler
implementations might be that simply nobody needs them. Imagine
yourself as a compiler vendor and try to answer a question if it makes
sense to invest effort in this implementation strategy. If nobody asks
for it, then probably not - and the market position of those Ada
compilers that do it (code sharing) when compared to those that don't
might indicate that this technique is not terribly shaking the Ada
community either.

--
Maciej Sobczak * http://www.inspirel.com

YAMI4 - Messaging Solution for Distributed Systems
http://www.inspirel.com/yami4

Re: Sharing generic bodies across instantiations.

[Dmitry A. Kazakov]

On Wed, 28 Jul 2010 13:01:43 -0700, Keith Thompson wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>> On Wed, 28 Jul 2010 05:55:36 -0700 (PDT), Maciej Sobczak wrote:
>>
>>> On 28 Lip, 11:28, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
>>> wrote:
>>> 
>>>>>> That is, the nature of C++ essentially requires a
>>>>>> replication strategy.
>>>>
>>>>> Why? What part of that "nature" requires it?
>>>>
>>>> Macro's nature
>>> 
>>> Wrong. Macros have nothing to do with templates.
>>
>> They have the nature of source level uncontrolled and untyped substitution
>> and reinterpretation.
> 
> Macros do.  Templates don't.

They do. The only limit put on the substitution is that the
reinterpretation does not fail. There are no traces of any semantics in the
declaration of the template parameters.

Generics suffer this too, but to a lesser extent.

>>> A C++ or Ada interpreter can be fully standard-compliant, which makes
>>> it a very valid "starter" in this context.
>>
>> Interpreter does not qualify as a compiler, per definition of both. You
>> might say that apple is as edible as orange, but that would not make it
>> orange in the context of the greengrocery.
> 
> Apples and oranges are both fruits.

So what? You don't pay for apples when buy oranges.

> Compilers and interpreters are both implementations.

It is about the implementation to take. The question was about shared
implementation of generics. Certainly, expanded implementations do
implement generics, or at least we hope so...
 
-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Sharing generic bodies across instantiations.

[Dmitry A. Kazakov]

On Wed, 28 Jul 2010 12:48:57 -0700 (PDT), Maciej Sobczak wrote:

> On 28 Lip, 15:16, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
> 
>>> Wrong. Macros have nothing to do with templates.
>>
>> They have the nature
> 
> We were talking about the nature of templates, not the nature of
> macros.

Yep, and the point was that templates being by the nature marcos like to be
expanded on the source level. You are free to disagree and put any other
reason why templates are 99.(9)% expanded. But this one is good to me.

>> Interpreter does not qualify as a compiler,
> 
> So the discussion was limited to compilers only? I did not found this
> constraint in the original post.

It came as Peter tried to define the meaning of a template body being
shared. A sound definition would be compiled body.

> Even if we assume such a limitation of discussion, there is still
> nothing particular in the C++ standard that would prevent code sharing
> as an implementation strategy for templates.

It would be technically meaningless, because the back-end tools down to the
linker and loader were unsuitable for this.

> Interestingly, macros cannot use this strategy by their definition.

They perfectly can. For example DEC indeed had macro libraries. They were
nothing but collections of shared macros. If the strategy were to call
MACRO-11 at run time of the library member each time you liked to
execute/interpret/expand it, then this could be done. No problem, except
that nobody would do that. Why? Because of the nature of macros and
templates.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Sharing generic bodies across instantiations.

[Maciej Sobczak]

On 29 Lip, 10:03, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> > We were talking about the nature of templates, not the nature of
> > macros.
>
> Yep, and the point was that templates being by the nature marcos

Paragraph, please. Otherwise this discussion is just hand-waving.

> You are free to disagree

I do. Templates are not macros, do not have the nature of macros, are
not their siblings and have no other association with them.

> > Even if we assume such a limitation of discussion, there is still
> > nothing particular in the C++ standard that would prevent code sharing
> > as an implementation strategy for templates.
>
> It would be technically meaningless, because the back-end tools down to the
> linker and loader were unsuitable for this.

First: C++ standard places no constraints on how the implementation is
organized at the system level.

Second: so, I understand, "the back-end tools down to the linker and
loader" were more suitable to do it in Ada, right?

> > Interestingly, macros cannot use this strategy by their definition.
>
> They perfectly can.

No. 2.1 (C++ standard) defines the phases of translation - macro
expansion is performed before syntactic and semantic analysis of
tokens.
In other words, macros are expanded even before the compiler gets a
chance to realize that it compiles a C++ code.

--
Maciej Sobczak * http://www.inspirel.com

YAMI4 - Messaging Solution for Distributed Systems
http://www.inspirel.com/yami4

Re: Sharing generic bodies across instantiations.

[Dmitry A. Kazakov]

On Thu, 29 Jul 2010 07:02:25 -0700 (PDT), Maciej Sobczak wrote:

> On 29 Lip, 10:03, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:

>> You are free to disagree

> I do.

I know.

>>> Even if we assume such a limitation of discussion, there is still
>>> nothing particular in the C++ standard that would prevent code sharing
>>> as an implementation strategy for templates.
>>
>> It would be technically meaningless, because the back-end tools down to the
>> linker and loader were unsuitable for this.
> 
> First: C++ standard places no constraints on how the implementation is
> organized at the system level.

What are you trying to say by this?

> Second: so, I understand, "the back-end tools down to the linker and
> loader" were more suitable to do it in Ada, right?

You mean shared Ada generic bodies? Yes they require much less late binding
than C++ templates would, if anybody came to a silly idea to compile and
then share them.

>>> Interestingly, macros cannot use this strategy by their definition.
>>
>> They perfectly can.
> 
> No. 2.1 (C++ standard) defines the phases of translation - macro
> expansion is performed before syntactic and semantic analysis of
> tokens.

1. My example of shared macros was MACRO-11.

2. The standard does not put any requirements on how the compiler actually
works. Precompiled headers and IDEs with "go to the declaration point" for
a #define, or just showing the source, not yet expanded, code, even daring
to colorize it, do not take this advise literally.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Sharing generic bodies across instantiations.

[Maciej Sobczak]

On 29 Lip, 16:40, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> >> It would be technically meaningless, because the back-end tools down to the
> >> linker and loader were unsuitable for this.
>
> > First: C++ standard places no constraints on how the implementation is
> > organized at the system level.
>
> What are you trying to say by this?

That it does not matter what was the suitability of the back-end
tools, as there is no obligation (as far as the standard is concerned)
to use the existing tools. If you are not obliged to use existing
tools, you are not constrained by their (lack of) suitability.

> > Second: so, I understand, "the back-end tools down to the linker and
> > loader" were more suitable to do it in Ada, right?
>
> You mean shared Ada generic bodies? Yes they require much less late binding
> than C++ templates would,

Can you elaborate on this, please?

> >>> Interestingly, macros cannot use this strategy by their definition.
>
> >> They perfectly can.
>
> > No. 2.1 (C++ standard) defines the phases of translation - macro
> > expansion is performed before syntactic and semantic analysis of
> > tokens.
>
> 1. My example of shared macros was MACRO-11.

I thought we were talking about C++. Or Ada.

> 2. The standard does not put any requirements on how the compiler actually
> works.

Bingo. So why do you put claims that are based on the suitability of
some tools? The above point basically contradicts most of what you
have said.

--
Maciej Sobczak * http://www.inspirel.com

YAMI4 - Messaging Solution for Distributed Systems
http://www.inspirel.com/yami4

Re: Sharing generic bodies across instantiations.

[Dmitry A. Kazakov]

On Thu, 29 Jul 2010 13:27:05 -0700 (PDT), Maciej Sobczak wrote:

> On 29 Lip, 16:40, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
> 
>>>> It would be technically meaningless, because the back-end tools down to the
>>>> linker and loader were unsuitable for this.
>>
>>> First: C++ standard places no constraints on how the implementation is
>>> organized at the system level.
>>
>> What are you trying to say by this?
> 
> That it does not matter what was the suitability of the back-end
> tools, as there is no obligation (as far as the standard is concerned)
> to use the existing tools. If you are not obliged to use existing
> tools, you are not constrained by their (lack of) suitability.

This is obviously wrong. It is like to say that you are not constrained to
fly to the Moon even if there is no rocket available.

>>> Second: so, I understand, "the back-end tools down to the linker and
>>> loader" were more suitable to do it in Ada, right?
>>
>> You mean shared Ada generic bodies? Yes they require much less late binding
>> than C++ templates would,
> 
> Can you elaborate on this, please?

Compiled generic bodies, at least in Ada 83, can be parametrized using
linker expressions. I didn't looked into Ada 95 tagged types derived within
the body from a formal generic parameter, you better as Randy for details.

>>>>> Interestingly, macros cannot use this strategy by their definition.
>>
>>>> They perfectly can.
>>
>>> No. 2.1 (C++ standard) defines the phases of translation - macro
>>> expansion is performed before syntactic and semantic analysis of
>>> tokens.
>>
>> 1. My example of shared macros was MACRO-11.
> 
> I thought we were talking about C++. Or Ada.

We were about macros. You claimed that implementation of a macro cannot use
something that templates can. This is a sweeping claim, which is obviously
wrong.

(Especially because C++ templates are macros (:-))

>> 2. The standard does not put any requirements on how the compiler actually
>> works.
> 
> Bingo. So why do you put claims that are based on the suitability of
> some tools?

Because any implementation must use these tools. BTW, the CPU is also such
a tool. (To preempt silly claims: the strength of the word "must" may vary
from tool to tool.)

> The above point basically contradicts most of what you have said.

How so? What I said was:

1) C++ tells something about templates
2) C++ is silent about some other things about templates
3) 1 makes something allowed by 2 difficult

Where is a contradiction?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Sharing generic bodies across instantiations.

[Maciej Sobczak]

On 30 Lip, 11:09, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> >> What are you trying to say by this?
>
> > That it does not matter what was the suitability of the back-end
> > tools, as there is no obligation (as far as the standard is concerned)
> > to use the existing tools. If you are not obliged to use existing
> > tools, you are not constrained by their (lack of) suitability.
>
> This is obviously wrong. It is like to say that you are not constrained to
> fly to the Moon even if there is no rocket available.

This is obviously wrong. The language standard is not concerned with
what is available, but with what will be developed. Existing practice
can of course provide the valuable guideline as well as feasibility
data, but is but no means formally constraining.
You can standardize flights to the Moon even if there is no rocket.
Rockets will be built according to what the standard says.

> >> You mean shared Ada generic bodies? Yes they require much less late binding
> >> than C++ templates would,
>
> > Can you elaborate on this, please?
>
> Compiled generic bodies, at least in Ada 83, can be parametrized using
> linker expressions.

1. What are linker expressions? Why they cannot be used with C++?
2. How does this affect the amount of late binding and why is there
less of it than with C++ templates?

> >> 1. My example of shared macros was MACRO-11.
>
> > I thought we were talking about C++. Or Ada.
>
> We were about macros.

No, we were talking about going to the Moon.

Your tendency to pull the subject in every possible direction just to
keep the discussion going is nothing new here.
*I* was talking about C++ templates and in that context your claims
were wrong. During the discussion I have referred to the C++ standard,
whereas you have failed to substantiate your claims in any way other
than with unrelated stories.

> (Especially because C++ templates are macros (:-))

Handwaving. We are close to EOF.

> >> 2. The standard does not put any requirements on how the compiler actually
> >> works.
>
> > Bingo. So why do you put claims that are based on the suitability of
> > some tools?
>
> Because any implementation must use these tools.

Implementation must use *some* tools. It might bring its own.

> 1) C++ tells something about templates
> 2) C++ is silent about some other things about templates
> 3) 1 makes something allowed by 2 difficult

And we're still nowhere close to the conclusion on sharing generic
bodies across instantiations.

(we got, however, closer to the Moon in the meantime)

> Where is a contradiction?

1. "the back-end tools down to the linker and loader were unsuitable"
2. "The standard does not put any requirements on how the compiler
actually
works."

The two above are exact citations.

Frankly, I'm both tired and bored of this discussion. Can we stop?

--
Maciej Sobczak * http://www.inspirel.com

YAMI4 - Messaging Solution for Distributed Systems
http://www.inspirel.com/yami4

Re: Sharing generic bodies across instantiations.

[Dmitry A. Kazakov]

On Fri, 30 Jul 2010 05:31:41 -0700 (PDT), Maciej Sobczak wrote:

> On 30 Lip, 11:09, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
> 
>>>> What are you trying to say by this?
>>
>>> That it does not matter what was the suitability of the back-end
>>> tools, as there is no obligation (as far as the standard is concerned)
>>> to use the existing tools. If you are not obliged to use existing
>>> tools, you are not constrained by their (lack of) suitability.
>>
>> This is obviously wrong. It is like to say that you are not constrained to
>> fly to the Moon even if there is no rocket available.
> 
> This is obviously wrong. The language standard is not concerned with
> what is available, but with what will be developed. Existing practice
> can of course provide the valuable guideline as well as feasibility
> data, but is but no means formally constraining.
> You can standardize flights to the Moon even if there is no rocket.
> Rockets will be built according to what the standard says.

Can I buy a ticket?

>>>> You mean shared Ada generic bodies? Yes they require much less late binding
>>>> than C++ templates would,
>>
>>> Can you elaborate on this, please?
>>
>> Compiled generic bodies, at least in Ada 83, can be parametrized using
>> linker expressions.
> 
> 1. What are linker expressions?

Formulae used to define symbols.

> Why they cannot be used with C++?

They are used with C++, but not to instantiate templates.

> 2. How does this affect the amount of late binding and why is there
> less of it than with C++ templates?

Because Ada generics were intentionally designed to support sharing and
thus not to become a burden for linkers and loaders of existing OSes. C++
templates were never intended for this.

>>>> 1. My example of shared macros was MACRO-11.
>>
>>> I thought we were talking about C++. Or Ada.
>>
>> We were about macros.
> 
> No, we were talking about going to the Moon.
> 
> Your tendency to pull the subject in every possible direction just to
> keep the discussion going is nothing new here.
> *I* was talking about C++ templates and in that context your claims
> were wrong.

You didn't show that.

> During the discussion I have referred to the C++ standard,
> whereas you have failed to substantiate your claims in any way other
> than with unrelated stories.
> 
>> (Especially because C++ templates are macros (:-))
> 
> Handwaving. We are close to EOF.

Talking about discussion methods, I did explain what macros and templates
have in common. All your responses so far did not go beyond "has nothing to
do".

>>>> 2. The standard does not put any requirements on how the compiler actually
>>>> works.
>>
>>> Bingo. So why do you put claims that are based on the suitability of
>>> some tools?
>>
>> Because any implementation must use these tools.
> 
> Implementation must use *some* tools. It might bring its own.

Show me a C++ compiler coming with another OS, loader, linker.

>> 1) C++ tells something about templates
>> 2) C++ is silent about some other things about templates
>> 3) 1 makes something allowed by 2 difficult
> 
> And we're still nowhere close to the conclusion on sharing generic
> bodies across instantiations.

We are done with debunking your claim about alleged contradiction.

> (we got, however, closer to the Moon in the meantime)
> 
>> Where is a contradiction?
> 
> 1. "the back-end tools down to the linker and loader were unsuitable"
> 2. "The standard does not put any requirements on how the compiler
> actually
> works."
> 
> The two above are exact citations.

See above.

> Frankly, I'm both tired and bored of this discussion. Can we stop?

Sure.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Sharing generic bodies across instantiations.

[Randy Brukardt]

"Peter C. Chapin" <pcc482719@gmail.com> wrote in message 
news:4c4f5c28$0$2375$4d3efbfe@news.sover.net...
...
> Thanks for all the replies to my question. I want to emphasize that my
> interest is not so much in what is done by current compilers but rather
> what is allowed by the standard. Is the standard (even the latest
> standard) written in such a way as to make a shared implementation of
> generic bodies possible? It sounds like the answer is yes.

I have been very vigilant to preserve the ability for generic sharing in the 
Ada Standard. (It's something that would be very easy to lose because of 
some obscure combination of features.) I can't say for sure that I have kept 
every such case out of the Standard, but there is agreement that at least 
limited sharing (when the parameters are "similar enough") ought to be a 
permitted implementation. "Universal sharing" (where there only one body for 
each generic), as used in Janus/Ada, is more controversal (but is still 
allowed by Ada 2005).

                          Randy.

Re: Sharing generic bodies across instantiations.

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:94v29hel87y$.8jvqfyw964yt.dlg@40tude.net...
...
>> Can you elaborate on this, please?
>
> Compiled generic bodies, at least in Ada 83, can be parametrized using
> linker expressions. I didn't looked into Ada 95 tagged types derived 
> within
> the body from a formal generic parameter, you better as Randy for details.

Deriving from a formal tagged type is illegal in generic bodies (always has 
been), see 3.9.1(4/2). This rule has less to do with generic sharing than 
with inheritance of abstract operations (Ada wants the bodies of instances 
to be always legal no matter what the actual parameters of the instance 
are). But it is convinient for generic sharing. (Derivation in the 
specification of a generic unit can be treated like an implicit formal 
parameter.)

                             Randy.

Re: Sharing generic bodies across instantiations.

[Randy Brukardt]

"Maciej Sobczak" <see.my.homepage@gmail.com> wrote in message 
news:14342188-c6f4-4b60-9284-8eff4f3f9ecd@k19g2000yqc.googlegroups.com...
...
> 2. How does this affect the amount of late binding and why is there
> less of it than with C++ templates?

You need to read about the Ada contract model for generics. (Off-hand, I 
can't think of a good reference, however.) Part of the Ada contract model is 
that there cannot be an error caused by the actual parameters of an instance 
in an instance body. Tucker Taft liked to describe the model as 
"assume-the-best" in the specification and "assume-the-worst" in the generic 
body. Thus there are a lot of things that are illegal in a generic body in 
Ada simply because they *could* be illegal in some instance of that generic. 
C++ has no such counterpart (indeed, I recall reading that Stoustrup [sp] 
explicitly eliminated it from C++ templates because it was too complex).

In addition, binding of names in the generic body always takes place at the 
point of the compilation of that body. That means that most operations at 
determined at that point, facilitating sharing. (This also causes the 
sometimes bug of "reemergence" in generics, where a hidden predefined 
operator is used instead of the user-defined one for the actual type.) C++ 
uses a more macro approach to template expansion.

                Randy.

P.S. When Dmitry talks about "macros", he means the general concept of macro 
processing. You seem to think he's talking about C macros, which is a 
specific instance of macro processing. It is pretty likely that some form of 
macro processing will be used to implement templates (and Ada generics in 
most compilers), but that has nothing whatsoever to do with the C 
preprocessor.

Re: Sharing generic bodies across instantiations.

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> I have been very vigilant to preserve the ability for generic sharing in the 
> Ada Standard. (It's something that would be very easy to lose because of 
> some obscure combination of features.) I can't say for sure that I have kept 
> every such case out of the Standard, but there is agreement that at least 
> limited sharing (when the parameters are "similar enough") ought to be a 
> permitted implementation. "Universal sharing" (where there only one body for 
> each generic), as used in Janus/Ada, is more controversal (but is still 
> allowed by Ada 2005).

Like Randy, I am in favor of retaining the ability to share generic body
code (universal or otherwise) in Ada.  I am not in favor of trying
to make universal sharing efficient at run time -- that's not
possible.  It's a trade-off -- it may make compile time faster,
at the expense of run time.

It is not feasible to share generic spec code.

- Bob

Re: Sharing generic bodies across instantiations.

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> You need to read about the Ada contract model for generics. (Off-hand, I 
> can't think of a good reference, however.)

The AARM talks about it.  Not exactly an "easy read".  ;-)

I think maybe the Ada 83 Rationale talks about it.
There were some holes in the contract model in Ada 83,
which were patched in Ada 95.

>... Part of the Ada contract model is 
> that there cannot be an error caused by the actual parameters of an instance 
> in an instance body. Tucker Taft liked to describe the model as 
> "assume-the-best" in the specification and "assume-the-worst" in the generic 
> body. Thus there are a lot of things that are illegal in a generic body in 
> Ada simply because they *could* be illegal in some instance of that generic. 
> C++ has no such counterpart (indeed, I recall reading that Stoustrup [sp] 
> explicitly eliminated it from C++ templates because it was too complex).
>
> In addition, binding of names in the generic body always takes place at the 
> point of the compilation of that body. That means that most operations at 
> determined at that point, facilitating sharing. (This also causes the 
> sometimes bug of "reemergence" in generics, where a hidden predefined 
> operator is used instead of the user-defined one for the actual type.) C++ 
> uses a more macro approach to template expansion.

It makes C++ templates more powerful than Ada generics.  The downside is
that if you're writing a reusable and widely-reused library, it's
difficult to know (in C++) whether some change might break clients.
The other downside is that error messages are typically
incomprehensible; in Ada you don't get normally get errors in instance
bodies, so they can't be incomprehensible.  ;-)

- Bob