Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>>>   At least Java generics do not support basic types, so I don't really
>>> understand what you are talking about.
> 
>> I'm saying you could pre-compile many templates if the templates only 
>> are capable of doing what generics do.
> 
>   I don't see why that would be so.

Because if the templates calculate something at compile-time based on a 
parameter you pass in (like the number of elements in an array), then 
you can't precompile it.

>>>   I suppose that no compiler so far uses this optimization, but I can
>>> perfectly imagine it being absolutely possible: When a template class or
>>> function is instantiated for a certain type, the compiler could compile
>>> it into some type of object file. Next time that template is used with
>>> the same type (be it in the same compilation process, by another compilation
>>> unit, or in a future one) it can simply use that object file instead of
>>> recompiling the template code. 
> 
>> Yes. Bingo. That's a generic.
> 
>   I don't see why. (Or, more precisely, I don't see why this would limit
> anything in templates.)

I'm saying that the things templates do that generics don't are the 
things that make it difficult to precompile templates.

>> You can't do that with templates because 
>> you (a) can't tell if the template will generate the same code with 
>> different classes/parameters
> 
>   I was just saying that the compiler could generate reusable object files
> from used types (so that when those types are used again with those templates,
> the template code doesn't need to be compiled again). Granted, you still
> can't make binary-only distributions of libraries, but at least you cut
> down compilation times if the same types are used a lot with a given
> template.

Sure. Generics are (usually) restricted in a way that allows you to 
distribute the executable (or .o file) without distributing the source 
and others can still use it.

>   What this means in practice is that the linker will re-call the compiler
> for any export template which is used in the code in order to get the
> actual template instance. OTOH, the template is instantiated only once
> instead of being instantiated for every usage.

Funky. OK.  That's getting closer to being what people generally mean by 
"generics". :-)

Put it this way: If you can't compile it and distribute a .o file 
*before* you know what type you're instantiating it with, it's probably 
not what people mean by the word "generic".

>>>   The linker always merges all template instantiations of a given type
>>> into one (this is required by the C++ standard, AFAIK). In other words,
>>> the final executable will have only one instance of those functions.
>>> That's not the problem.
> 
>> OK. So the linker is doing duplicate-code removal.
> 
>   No. The compiler marks the function type names with the 'inline' tag,
> which means that when the linker sees that type name in more than one
> object file, it only uses one of them (instead of giving you a linker
> error about duplicate function type names).

Isn't that duplicate code removal by the linker? Maybe we're in 
agreement and I'm just not understanding the subtleties or something. :-)

>   I assume it would be possible for the functions to actually be different
> in content (which might happen if you have broken dependencies),

Yeah. That's the sort of "bondage and discipline" that Ada enforces to 
keep that mistake from surfacing. If you compile a generic in Ada, you 
can't change the header file and then link against the old .o file.

[snip of lots of explanation]
Thanks for clarifying that for me.


>> It also would seem to 
>> assume that all your object code is compiled with the same template 
>> source code? Or does it actually look at the object code to make sure 
>> it's the same?
> 
>   I actually don't know. I suppose that a smart linker could actually
> double-check that the functions in the different object files actually
> are identical and give an error if they aren't. I have never tested
> what eg. the gnu linker does. It would sound rather trivial to do.

It would seem that way, especially if you're generating different code 
for every type even if you don't have to. Or you could even have the 
linker detect (say) that the code generated for MyTemplate<int*> and 
MyTemplate<long*> both come out the same and use the same object code 
for both.

>> I.e., if I compile A.cpp that includes T.chh to instantiate 
>> xyz:vector<long>, and then I edit T.chh and then compile B.cpp that 
>> instantiates xyz:vector<long> but that now generated different code, 
>> does the linker carry around both versions of the object code?
> 
>   The object file created from A.cpp and the one created from B.cpp
> both will claim to contain the same function, but their machine code
> will be different. 

Got it. That's what I thought.

>   Btw, what is the basic difference between generics (as in Eiffel&co)
> and delegation?
> 
>   If I'm not completely mistaken, delegation is like having all functions
> virtual, but without having to declare them in the base class. In other
> words, if you have a reference-to-Base, but that reference is actually
> pointing to an object of type Derived, and then you call a function foo()
> through that reference, and there is no foo() in Base, but there is one
> in Derived, it gets called ok. The delegation system checks at runtime
> what is the actual object behind that reference, and if it has a function
> called foo(), and calls it if that's so. (If I'm not mistaken, this is
> how inheritance works in Objective-C.)

That's essentially right, yes.  Generics and delegation are actually 
unrelated, and you probably can't even reasonably have both in the same 
language.  Generics are a way of having one function/class/etc work with 
variables of multiple types, which implies you have static typing, i.e., 
that your variables have types to start with. Delegation is an 
alternative to inheritance, where you "inherit" from object instances 
instead of statically from classes. `In other words, instead of having 
class A say "I'm just like class B, except for the differences I declare 
here," you have *instance* A say "I'm just like *instance* B, except for 
what I have dynamically assigned into my object." It's also called 
"prototype inheritance" sometimes.  You can do delegation "manually" in 
statically-typed languages (or get compiler support for it), and it's 
still called "delegation", but it's only "prototype inheritance" if 
every object works that way.


>   Delegation sounds like an alternative to templates/generics.

It's more an alternative to inheritance. You don't need generics if you 
don't have static typing (i.e., if your variables are untyped, 
regardless of whether operations on values are type-checked).

Here's my understanding of the terms as they're used in a more general 
sense:

Macro - transforms almost arbitrary pieces of text into other pieces of 
text at compile time.

Macro[2] - (Lisp sense, Erlang "parse transform" sense) - transforms 
arbitrary subtrees of the parse tree into other arbitrary subtrees of 
the parse tree. (I.e., if it didn't parse before you applied the macro, 
it won't parse after, either. Erlang has both types, fwiw.)

Template - A macro that is restricted to generating a particular node of 
a parse tree, given other particular nodes of a parse tree. I.e., a C++ 
template can only generate functions or classes (IIUC) and can only take 
types or integers as parameters. These restrictions let the compiler do 
things like duplicate code removal. But it's still essentially a 
compile-time source transformation.

Generics - A type of object that is parameterized at compile-time. 
Usually only takes types as arguments. Invariably can be (often, must 
be) compiled before being instantiated, and can be instantiated with 
types created after the generic is compiled.

"is-a" inheritance  - (I don't remember what the people who play with 
different inheritance methods call this, beyond "class-based 
inheritance".) The usual class/superclass inheritance.

"prototype inheritance" - Object instances inherit from other object 
instances. There usually isn't the idea of a "type" as such in the 
language, other than as defined by the behavior of different objects. 
Naturally, you often have lots of objects delegating to some other 
object that has only functions in it, at which point it behaves a lot 
like "is-a" inheritance.

"delegation" - Manual or automated support for dispatching unknown 
method invocations to another object when the original target object 
doesn't define the method.

"aspect-oriented programming" - Took me a while to figure this one out. 
It lets you say things like "every method in class B should call "debug" 
before it starts and "end_debug" before it exits", and in another place 
say "every method of A or subclasses should call "transaction_begin" at 
the start and "transaction_end" at the end, and if B is a subclass of A, 
then B gets both new behaviors, without having to muck with B or callers 
of B. Sort of like how some languages let you use "super" to say "first 
do this, then invoke my superclass's behavior for this method, then do 
that", only in a more general way. Same sorts of advantages you get with 
inheritance/dynamic dispatch not making you put case statements all over.

>>>   The amount of code "bloat" caused by templates is usually
> 
>> I wasn't aware the linker removed duplicate object code. That's the 
>> bloat I was speaking of.
> 
>   It's not so much that the linker "removes" code per se, it's more that
> it just uses one instance of a given function and ignores the rest. (Well,
> I assume that's how linkers do it in practice.) After all, the linker is
> building an executable from a bunch of object files, deciding what to
> take from each object file. In the case of inline/template functions it
> just takes one duplicate and leaves the rest.

So, like the same object file showing up in separate libraries in C, it 
just links in the first one because it already satisfied the 
dependencies. OK. Now that I realize templates really only build code 
that you dont *have* to inline, it makes sense. (Contrasted with C-style 
macros, which can build expressions that would make no sense on their own.)

It's all coming together... :-)

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message