Boost Workshop at OOPSLA 2004

[kanze]

Think of it this way. In your first example, the argument for T (let's
call it arg) is looked up in the scope of the instantiation. Then, the
scope of the definition of f is loaded. The equivalent of:

typedef arg T;

is executed, which declares T to be of type arg, and the T is
installed in the scope of instantiation. Then, the semantic analysis
of f happens in the scope of the instantiation. T is found using
normal lookup rules. It works just like a function call does, except
that the "parameter passing" into the definition scope happens at
compile time rather than run time. The analogous happens with Base in
the second example.

So in sum, symbols inside the template body are looked up in the context
of the point of instantiation, and not in the context of the point of
definition. To make it clearer:

extern void g( int ) ;

template< typename T >
void
f( T const& t )
{
g( t ) ; // #1
g( 1.5 ) ; // #2
}

User code, in another module... (I'm supposing we've done whatever is
necessary to use the f, above here. In C++, we've included the header
where f is defined. In D, I don't know what is necessary.)

void g( double ) {}

void
h()
{
f( 2.5 ) ; // #3
}

In the instantiation of f triggered by line #3, which g is called in
line #1? In line #2? If symbols are looked up in the context of the
definition, both lines should call g(int), because that is the only
symbol g visible at the point of instantiation. If symbols are looked
up at the point of instantiation (as is the case in traditional C++,
e.g. CFront, early Borland, etc.), then both lines call g(double). The
two phase look-up in standard C++ means that line #1 calls g(double),
and line #2 g(int).

C++ tries to emulate this behavior with the two-phase lookup
rules. But it's hashed up - did you know you cannot declare a local
with the same name as a template parameter? It follows weird rules
like that that are all its own.

There are, IMHO, two problems with two phased look-up as it is
implemented in C++. The first is that which names are dependant, and
which aren't, is determined by fairly subtle rules -- even when quickly
scanning f, above, you might miss the fact that the two g's are looked
up in entirely different contexts, and this is an extremely simple
case. (I'm not sure but what I wouldn't have prefered an explicit
declaration -- a name is only dependant if the template author
explicitly says it is.) The second is the fact that the name lookup is
not only in a different context, but follows subtly different rules.

I don't have enough experience with compilers implementing two phase
lookup correctly to say whether this will be a real problem in actual
practice. It may turn out to be like function overload resolution: the
rules are so complicated that almost no pratitioner begins to really
understand them, but in real code, provided a few, common sense rules
are followed, the results are what one would intuitively expect, and
there is no problem. I hope this is the case, but I'm not counting on
it. (Part of the problem, of course, is that many pratitioners already
have concrete experience with a different set of rules, which works
differently. Just being aware that two phase lookup exists, and knowing
a few simple rules to force dependency when you want it, goes a long
way.)

 

[Matthew Hall]

Think of it this way. In your first example, the argument for T (let's call
it arg) is looked up in the scope of the instantiation. Then, the scope of
the definition of f is loaded. The equivalent of:

typedef arg T;

is executed, which declares T to be of type arg, and the T is installed in
the scope of instantiation. Then, the semantic analysis of f happens in the
scope of the instantiation. T is found using normal lookup rules. It works
just like a function call does, except that the "parameter passing" into the
definition scope happens at compile time rather than run time. The analogous
happens with Base in the second example.

I'm a bit confused here - in the first paragraph, you wrote:
"The symbols inside the template body are looked up in the context of
the point of definition."
I think the point of James' example was to inquire about how the symbol
'g' is looked up -- at the point of definition g(T t) may not yet be
declared for any type T, so how is the symbol 'g', which is in the
template body, looked up at definition time?

-matt

 

[Bo Persson]

diversion
of vendors
who

Managed Extensions, and C++/CLI. Plus the D language.

[snip]

Much like export, these are of questionable benefit to those who need
portable C++ .

Sure, but they *are* presented as massive improvements by their
respective implementor.

I would for sure have preferred export to Managed Extensions. It was a
real anti climax after waiting 4 years for a compiler upgrade: "We
haven't implemented much of the C++ Standard, but we have added these
fine extensions."

Somehow portability seems to have a low priority for some of the
compiler providers.


Bo Persson

 

[Jean-Marc Bourguet]

3) The faster compilation is theoretically based on the idea that
the template implementation doesn't need to be rescanned and
reparsed every time it is #include'd. However, many modern C++
compilers already support "precompiled headers", which already
provide just that capability without export at all. I'd be happy to
accept a compilation speed benchmark challenge of Digital Mars DMC++
with precompiled headers vs an export implementation.

I've already mentionned my experiments here in the past. I could
built test cases with Como where the ratio between pre-compiled
headers and export is as high as wanted by just adding more
compilation units. That was easy and was done only to check that
there was a possible win.

But, I was suprised that, in an example built to test what was the
break even point in a more realistic domain level template, there was
a win to use export as soon as two compilations units made use of the
same specialisation.

BTW, the win will depend on the way template are instanciated. Como
use the model which benefits the most of export. Other could have no
benefit at all. Google seems to be unreachable, but if you look at my
old posts on this subject you should find more details.

Yours,

 

[Rich Grise]

Doesn't that tend to argue that export isn't solving a real problem?

Does that mean that the problem it's solving isn't a real problem, or
that some real problem that should be getting solved, isn't?

Thanks,
Rich

 

[Walter]

So instead of making their C++ standard-compliant, they used the
time saved by not implementing export to create a different language.
OK, I'm puzzled.

There's an awful lot more to a C++ compiler than standards compliance. It's
quite possible to have a standards compliant compiler that is thoroughly
useless, for example. Compiler vendors answer to their customers, and by and
large do what their customers want them to do. I suspect that Microsoft was
under a lot of customer pressure to produce something like C++/CLI.

Yes. Does the list of improvements made get added to at the same rate
as well?

I wish. I have very limited resources, and have to be careful about where I
apply them.

 

[Walter]

So in sum, symbols inside the template body are looked up in the context
of the point of instantiation, and not in the context of the point of
definition.

No, you have it exactly reversed.

To make it clearer:

extern void g( int ) ;

template< typename T >
void
f( T const& t )
{
g( t ) ; // #1
g( 1.5 ) ; // #2
}

User code, in another module... (I'm supposing we've done whatever is
necessary to use the f, above here. In C++, we've included the header
where f is defined. In D, I don't know what is necessary.)

void g( double ) {}

void
h()
{
f( 2.5 ) ; // #3
}

In the instantiation of f triggered by line #3, which g is called in
line #1? In line #2? If symbols are looked up in the context of the
definition, both lines should call g(int), because that is the only
symbol g visible at the point of instantiation.

Yup. In D, g(int) is called in both instances, for the reason you give.

There are, IMHO, two problems with two phased look-up as it is
implemented in C++. The first is that which names are dependant, and
which aren't, is determined by fairly subtle rules -- even when quickly
scanning f, above, you might miss the fact that the two g's are looked
up in entirely different contexts, and this is an extremely simple
case. (I'm not sure but what I wouldn't have prefered an explicit
declaration -- a name is only dependant if the template author
explicitly says it is.) The second is the fact that the name lookup is
not only in a different context, but follows subtly different rules.

There are other problems, such as the fiasco around forward declarations
interacting with the point of definition. Most of these problems come about
because of the inability to parse C++ without doing symbol lookups, so
there's all these kludge-o-matic rules around the lookup rules inside
template bodies so they can be parsed with incomplete symbolic info. D
solves this problem neatly by having a grammar that can be parsed without
needing any symbol information.

 

[Walter]

I've already mentionned my experiments here in the past. I could
built test cases with Como where the ratio between pre-compiled
headers and export is as high as wanted by just adding more
compilation units. That was easy and was done only to check that
there was a possible win.

But, I was suprised that, in an example built to test what was the
break even point in a more realistic domain level template, there was
a win to use export as soon as two compilations units made use of the
same specialisation.

BTW, the win will depend on the way template are instanciated. Como
use the model which benefits the most of export. Other could have no
benefit at all. Google seems to be unreachable, but if you look at my
old posts on this subject you should find more details.

Try your compilation speed benchmarks with Digital Mars C++ precompiled
headers!

 

[Walter]

I'm a bit confused here - in the first paragraph, you wrote:
"The symbols inside the template body are looked up in the context of
the point of definition."
I think the point of James' example was to inquire about how the symbol
'g' is looked up -- at the point of definition g(T t) may not yet be
declared for any type T, so how is the symbol 'g', which is in the
template body, looked up at definition time?

The solution there is to write g as a member of T, so that g(t) is instead
written as t.g().

 

[John Torjo]

Faster by a factor of 3.7. The point is not to have faster
compilation, although that would be nice, but to have cleaner
compilation, so that implementations do not intertwine with
the usage environments any more than required by the lookup
rules.


Huh? Why? Just because you have to repeat the template
header part? That's not that much more onerous than
repeating ClassName:: in front of ordinary methods.
Make a macro if it's that bothersome. With export, you
won't have to worry about the macros colliding with
client code!

Do you really expect programmers to make macros for every class they
make? What next, a macro generator ?

Since you have so many possibilities, you'd end up with way too many
macros in source files. I am not very confortable with that. But, as
time goes by, I might

That said, I'm very keep to try out the 'export' keyword. I also have
the perfect candiate for this (win32gui)


However, in case I want to create a portable library, and want to make
use of the export feature (for the compilers it's implemented on), for
each templated class, I'll have to provide the definitions in a
different file, and if export is not available, #include it. This is
sooooo tedious, and will make code harder to read and maintain IMO.


Best,
John

John Torjo
Freelancer
-- (e-mail address removed)

Contributing editor, C/C++ Users Journal
-- "Win32 GUI Generics" -- generics & GUI do mix, after all
-- http://www.torjo.com/win32gui/

Professional Logging Solution for FREE
-- http://www.torjo.com/code/logging.zip (logging - C++)
-- http://www.torjo.com/logview/ (viewing/filtering - Win32)
-- http://www.torjo.com/logbreak/ (debugging - Win32)

 

[John Torjo]

| > Currently is also seriously tedious to implement class
| > template member functions outside the class.
|
| Huh? Why? Just because you have to repeat the template
| header part?

yes.

| That's not that much more onerous than
| repeating ClassName:: in front of ordinary methods.

many templates have several parameters; then they might have templated member functions.
This get *very* tedious to define outside a class.

I can only agree with you here. Especially templated members of templated classes?

Best,
John

John Torjo
Freelancer
-- (e-mail address removed)

Contributing editor, C/C++ Users Journal
-- "Win32 GUI Generics" -- generics & GUI do mix, after all
-- http://www.torjo.com/win32gui/

Professional Logging Solution for FREE
-- http://www.torjo.com/code/logging.zip (logging - C++)
-- http://www.torjo.com/logview/ (viewing/filtering - Win32)
-- http://www.torjo.com/logbreak/ (debugging - Win32)

 

[kanze]

I've already mentionned my experiments here in the past. I could
built test cases with Como where the ratio between pre-compiled
headers and export is as high as wanted by just adding more
compilation units. That was easy and was done only to check that
there was a possible win.

But, I was suprised that, in an example built to test what was the
break even point in a more realistic domain level template, there was
a win to use export as soon as two compilations units made use of the
same specialisation.

BTW, the win will depend on the way template are instanciated. Como
use the model which benefits the most of export. Other could have no
benefit at all. Google seems to be unreachable, but if you look at my
old posts on this subject you should find more details.

I've been thinking about this myself. Just yesterday, I ran into what
seems to be a frequent scenario in my code, where the template class
itself consists of a lot of small, simple functions, and one or two very
complex functions, and the template is used in a number of different
source modules, instantiated over the same type. Every time I make the
slightest modification in the complicated function, I touch the header
file, which means that my make system recompiles all of the sources
which include that header. And that is slow.

I would expect export to improve this, for the simple reason that I
don't expect to have to specify the implementation file in my
dependencies in the make file. I hope not, anyway; the dependencies are
generated automatically depending on the files explicitly included. So
the automatically generated dependencies will NOT include the
implementation file for exported templates.

In an earlier thread, I raised the same point, and David Vandevoorde
(the author of the export implementation used in Como) assured me that
this was a scenario where build times would be improved. That said, and
to be honest, I suspect that the improvement is really because it is the
compiler handling the dependencies, instead of make, and that it handles
them more intelligently; that is, it would probably be possible to
obtain the same improvements without export (but David would be in a
better position than I am to confirm or deny this).

 

[tom_usenet]

No, you have it exactly reversed.

How do you call operator overloads on template parameters? e.g.
consider the D equivalent of this C++:

template <class T>
T sum(T lhs, T rhs)
{
return lhs + rhs;
}

How is the operator+ found if lookup only occurs at the point of
definition? I have a horrible feeling you are about to tell me that
all operator overloads are member functions in D, and members of
template parameters of course considered. If that's the case, how
about if the operator in question is a member of a different class
than the template parameter?

Tom

 

[tom_usenet]

Try your compilation speed benchmarks with Digital Mars C++ precompiled
headers!

Given that Digital Mars C++ doesn't have export, what are you
suggesting the times are compared against?

Tom

 

[kanze]

How much would you estimate Digital Mars spends on advertising? <g>

Actually, they weren't one of the vendors I was thinking of. As
another poster has pointed out, they invested in a new language, rather
than conformant C++.

Given all the talk about the cost of implementing export (which I agree
isn't negligible), I think it worth pointing out that the one company
which has implemented it are also in advance of most other companies in
all other aspects of conformance, and in terms of support for legacy
code. So it can't be a question of either export or other
features/conformance, or support for legacy code, etc.

It's also worth pointing out that the company in question only has three
technical employees, and that they also managed to implement a Java
compiler at the same time. Now, I don't know about Digital Mars, but
I'm pretty sure that some of the other vendors do have a few more
technical employees. For some, by several magnitudes even.

So I don't understand it. Even if it only takes a single man year to
implement export, I can understand companies like Digital Mars having
some hesitancy -- I would imagine that even one man year represents a
significant part of your development budget. I can understand the
problem by g++ as well -- they have more than three developpers, but
since you don't feed a family on what you make working on g++, their
developers can't normally work full time on it. But even supposing that
it takes five man years (although others have done it in less), there
are vendors out there for whom five man years is less that a tenth of
one percent of their advertising budget. What's their excuse?

I find it particularly hypocritical that some of these companies (and
there isn't just one of them) are extremely active and visible in the
standardization effort, and then choose to totally ignore the results
when it doesn't suit them. Personally, it gives me the impression that
this activity is just a sophisticated form of advertising. False
advertising, in fact.

 

[Hyman Rosen]

most actual templates that people write don't have weird name-capturing problems.

Doesn't that tend to argue that export isn't solving a real problem?

No. I just meant that I believe that in most template code,
you are not going to find calls to free non-dependent functions
that vary by instantiation context. But export lets you write
the template method definitions without requiring them to be
safe for bodily inclusion into arbitrary compilation units.
For example, library writers can write their template code
without having to prefix every name in sight with '__' to avoid
potential name clashes with user code.

 

[Steven E. Harris]

Yup. In D, g(int) is called in both instances, for the reason you
give.

In D, is f() essentially sealed against any other g() overload
becoming visible? Could one, perhaps by way of changing inclusion or
"import" order, introduce the g(double) overload to make it available
within f()?

It seems that there are several C++ template programming tactics in
active use that this "sealing" would preclude. For example, in a
typical Standard Library sequence algorithm, templated iterator types
usually have at least three functions or operators invoked:

operator*
operator++
operator==

Surely not all custom iterator types are declared in a manner visible
to, say, the <algorithm> header, but the sequence algorithms wind up
figuring out which operators to call for any iterator type
supplied. Would this approach still work in D?

 

[David B. Held]

[...]
I contend that, all other things being equal, export templates are more
pleasant to work with than the equivalent inclusion templates. That by
itself is sufficient to cast doubt on your claim that the feature is "broken
and useless."

What are your comments on N1426, given that you and the rest of EDG are
thoroughly quoted as being against export?

Dave

 

[Paul Mensonides]

"Andrei Alexandrescu (See Website for Email)"

[snip closing points that I agree with]

In an attempt to try to lure you into a discussion on would-be nice
features, here's a snippet from an email exchanged with a friend. It has to
do with the preprocessor distinguishing among tokens and more complex
expressions:
Okay.

In my vision, a good macro system understands not only tokens, but also
other grammar nonterminals (identifiers, expressions, if-statements,
function-call-expressions, ...)

My immediate reaction to this is that such a system understands too much, which
usually gets in the way.

For example, let's think of writing a nice "min" macro. It should avoid
double evaluation by distinguishing atomic tokens (identifiers or integral
constants) from other expressions:

$define min(token a, token b) {
(a < b ? a : b)
}

$define min(a, b) {
min_fun(a, b)
}

I understand that this is just an example, so I'll bite, but I don't like this
example. Given two single identifier tokens, min(a, b) is not sufficiently
better than just writing the expression directly (a < b ? a : b). Given a
"significant" multiple evaluation situation, std::max (or similar) should be
used directly.

The second thing that I don't like about this example is that it is back to the
idea of macro-to-function equivalence. Sometimes that is acceptable, but it is,
by far, the border case.

Next we think, how about accepting any number of arguments. So we write:

$define min(token a, b $rest c) {
min(b, min(a, c))
}

$define min(a, b $rest c) {
min(a, min(b, c))
}

The code tries to find the most clever combination of inline operators ?:
and function calls to accomodate any number of arguments. In doing so, it
occasionally moves an identifier around in hope to catch as many identifier
pairs as possible. That's an example of a nice syntactic transformation.

In my opinion, the feature is too specific. Direct recursion, that's good.
Overloading via number of arguments, that's good. Overloading by number and
types of tokens per argument is just way too specific a feature to be generally
useful. Solutions like this are solutions for things like this. I want a
general solution that covers everything that I can think of, and more
importantly, everything that I *might* think of. Given the ability to classify
(and understand) arbitrary tokens (as I mentioned before) is the fundamental
necessity--and not indirectly through yet another overloading-type hack. Things
such as the above would be just one small, specific kind of solution in a much
larger world. After that, *then* give me true recursion, and *then* give me
overloading on number of arguments.

Basically, I want the tools to be able to make my own tools when direct language
support doesn't exist. No matter how many features you add that situation will
occur. Direct feature support such as you mention above are a result of
analysis of use-cases, rather than analysis of the general problem.

Now, having said that, there are things that are so common that they are worth
considering as direct language features, _but_ those things need to be addressed
after the underlying lower-level machinery is there. Then we might actually be
able to decide what things are actually common enough to justify direct language
support while still being able to do both those things and do those things which
are useful but definitely not common enough to justify such support.

Regards,
Paul Mensonides

 

[Hyman Rosen]

I can only agree with you here. Especially templated members of templated classes?

If you find yourself repeating the same headers, use a macro.
That's what the preprocessor is for.