From: Joel Eidsath on
I came across a comment on Slashdot that gives me an excuse to write
about the "A concept design" paper before the standards committee:

"It was certainly interesting in the 'bad old days' when no two
compilers implemented things like templates the same way. Of course,
I'm no fan of templates, since they are essentially a kludge to work
around the fact that there are atomic variable types that are not part
of the OO implentation in C. If there were some abstract type from
which int, char, etc, were derived then templates would be unnecessary.
In other words, templates only exist because C++ isn't fully OO.

Of course, then we wouldn't have 'template metaprogramming' and there
would be a whole bunch of computer geeks who would have to stop writing
papers and articles showing us how smart they are implementing the
Sieve of Eratosthanes that prints prime numbers in compiler warnings,
and get back to doing useful work. :-P"

This is wrong (except maybe for the stuff about template
metaprogramming). But there is not much functional difference between
templates, as implemented now, and functions in more OO languages that
work on the base object for all types.

What makes templates different is the idea behind them. The OO idea of
a generic function is a function that works for some base type and any
type derived from it. The reasoning behind this is something like
"type hierarchies are 'IS A' so a function that works for a base should
work for derived types as well." Real world code does not follow this
paradigm, however. Instead, generic functions are envisioned to work
on types with a given set of properties. There is no reason to expect
that these properties should obey class hierarchies, even a majority of
the time.

It is the OO languages that have the kludge: an abstract base class
from which everything derives, not C++. And C++ 'concepts' are going
to make this clear:

Stroustrup's and Dos Reis' paper for the standard committee is
available here:
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1782.pdf

Abstract:
"We describe a design of 'concepts' (a type system for types) for
improved support of generic programming in C++. This paper presents a
current best-effort design based on previous work followed by lengthy
discussions of technical details. The design is based on the principles
that simple things should be simple (whereas more advanced programming
techniques may require some extra work), that there should be no
performance degradation compared to current template techniques, and
that essentially all current template techniques should be improved by
the use of concepts. The design achieves perfect checking of separately
compiled templates at the cost of minor restrictions on the
instantiation mechanism."

The rest of this post is some comments about the paper.

We're first asked to consider STL's fill():

template<class ForwardIterator, class ValueType>
void fill(ForwardIterator first, ForwardIterator last, const ValueType
& v)
{
while (first!=last) { *first = v; ++first; }
}

Here it is with concepts:

template<class For, class V>
where Forward_iterator<For>
&& Value_type<V>
&& Assignable<For::value_type,V>
void fill(For first, For last, const V& v)
{
while (first!=last) { *first = v; ++first; }
}

In a more condensed form:

template<Forward_iterator For, Value_type V>
where Assignable<For::value_type,V>
void fill(For first, For last, const V& v)
{
while (first!=last) { *first = v; ++first; }
}

That For "is a" Forward_iterator and V "is a" Value_type should not be
confused with the OO "is a." For "is a" Forward_iterator in that it
obeys the properties defined for Forward_iterator.

Concepts allow two sorts of errors to be picked up by the compiler:
1) Concept violations in the arguments passed to a template at point
of call.
2) Concept violations inside the template itself.

I am somewhat wary about this. Catching 1 should be the main
justification of concepts. In effect, it is the template designer
saying to the user of the template "your types must possess these
properties, or they won't work as template arguments." Catching 2,
however, is saying "so long as your types possess these properties,
they will work as template arguments." The problem with 2 is that it
won't always be true. I see this as a problem similar to exception
specifications. I don't really see a problem with catching both types
of violations, but I wish it was possible to separate them.

Section 2.2 describes overloading based on concepts. This is amazing
and my mouth is watering for a compiler that implements it.

Section 3 describes how to create concepts. I dislike that there are
no provisions for negative concepts. For example, I might like to have
something like "Not_Assignable" for use in creating slow careful
algorithms rather than the fast awesome algorithms I might create with
"Assignable". (This is something different than negative
static_asserts mentioned later.) Most of the time, the fact that a
compiler uses the most constrained concept definition seems to
obliviate the need for this, but this would allow a more obvious
implementation of advance, as done in 6.4. There may be concepts that
violate "the predicate of L must imply the predicate of K" (from 6.4)
but we still want to choose one or the other.

Another feature that is missing is some sort of user concept
specification. I imagine that this will be achieved with type traits,
but a formal implementation would be nice. User concept specification
would allow class designers to specify runtime guarantees for their
classes. Something like
"Trust_me_guys_this_member_function_wont_ever_return_zero" might be a
useful thing to have.

One thing that puzzled me was that there were no examples in the paper
that involved concepts involving OO hierarchy determination. Would one
use dynamic_cast<>?

There is another thing missing from concepts that limit their utility.
I don't see how to implement it, however:

Hopefully everyone learned about induction proofs in high school. For
induction to work, you need to prove that "P true for x" implies "P
true for x + 1" and also a specific instance of P. (Usually P of 1 or
0.) I see concepts as equivalent to the first general condition of
induction, but not the second. It would be nice to have some
constraints on class T initialized with 0, for instance. Sometimes
this will be possible to know at compile-time, sometimes not. Hence
the difficulty. (Other similar constraints might be the behavior of an
empty container, or an iterator at the end of a container.) Again,
this seems impossible to implement in general, but maybe someone
reading will have a flash of insight. Perhaps something along these
lines could be be achieved with a mix of user concept declarations and
compiler-evaluated declarations.

Joel Eidsath


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: David Abrahams on
"Joel Eidsath" <jeidsath(a)gmail.com> writes:

> I came across a comment on Slashdot that gives me an excuse to write
> about the "A concept design" paper before the standards committee:
>
> "It was certainly interesting in the 'bad old days' when no two
> compilers implemented things like templates the same way. Of course,
> I'm no fan of templates, since they are essentially a kludge to work
> around the fact that there are atomic variable types that are not part
> of the OO implentation in C. If there were some abstract type from
> which int, char, etc, were derived then templates would be unnecessary.
> In other words, templates only exist because C++ isn't fully OO.

Hah.

> Of course, then we wouldn't have 'template metaprogramming' and there
> would be a whole bunch of computer geeks who would have to stop writing
> papers and articles showing us how smart they are implementing the
> Sieve of Eratosthanes that prints prime numbers in compiler warnings,
> and get back to doing useful work. :-P"
>
> This is wrong (except maybe for the stuff about template
> metaprogramming).

No comment.

> But there is not much functional difference between templates, as
> implemented now, and functions in more OO languages that work on the
> base object for all types.

Yes, there is. Covariant argument types (the kind you need in order
to do int + int and complex + complex with the same '+' operation --
or swap, for that matter) can't be implemented using traditional OO
without compromising static type safety. Among other things.

> It is the OO languages that have the kludge: an abstract base class
> from which everything derives, not C++. And C++ 'concepts' are going
> to make this clear:
>
> Stroustrup's and Dos Reis' paper for the standard committee is
> available here:
> http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1782.pdf

I hope you're aware that there's a competing concepts proposal:
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1849.pdf

> Concepts allow two sorts of errors to be picked up by the compiler:
> 1) Concept violations in the arguments passed to a template at point
> of call.
> 2) Concept violations inside the template itself.
>
> I am somewhat wary about this. Catching 1 should be the main
> justification of concepts. In effect, it is the template designer
> saying to the user of the template "your types must possess these
> properties, or they won't work as template arguments." Catching 2,
> however, is saying "so long as your types possess these properties,
> they will work as template arguments." The problem with 2 is that it
> won't always be true.

What do you mean?

> I see this as a problem similar to exception
> specifications. I don't really see a problem with catching both types
> of violations, but I wish it was possible to separate them.
>
> Section 2.2 describes overloading based on concepts. This is amazing
> and my mouth is watering for a compiler that implements it.

I hope you're aware that the competing concepts proposal supports
that, and it has been implemented:
http://www.osl.iu.edu/~dgregor/ConceptGCC/

You can download that compiler and use it today.

> Section 3 describes how to create concepts. I dislike that there are
> no provisions for negative concepts. For example, I might like to have
> something like "Not_Assignable" for use in creating slow careful
> algorithms rather than the fast awesome algorithms I might create with
> "Assignable".

You don't need that. If you create two overloads, only one of which
requires Assignable, it will be chosen in preference to the other
one. You can put the slow implementation in the overload that doesn't
require Assignable.

> (This is something different than negative static_asserts mentioned
> later.)

Thank goodness. The need for those is what bothers me the most about
the Stroustrup and Dos Reis proposal.

> Most of the time, the fact that a compiler uses the most constrained
> concept definition seems to obliviate the need for this, but this
> would allow a more obvious implementation of advance, as done in
> 6.4.

You can always create a Not_Assignable concept that contains no
requirements and is thus satisfied by everything, if that helps.

> Another feature that is missing is some sort of user concept
> specification.

I don't know what that means.

> I imagine that this will be achieved with type traits,

No, concepts will obviate type traits.

> but a formal implementation would be nice. User concept specification
> would allow class designers to specify runtime guarantees for their
> classes. Something like
> "Trust_me_guys_this_member_function_wont_ever_return_zero" might be a
> useful thing to have.

What you're referring to sounds a lot more like it should be called
"runtime semantic guarantees" than "user concept specification."

> One thing that puzzled me was that there were no examples in the
> paper that involved concepts involving OO hierarchy determination.
> Would one use dynamic_cast<>?

You lost me.

> There is another thing missing from concepts that limit their utility.
> I don't see how to implement it, however:
>
> Hopefully everyone learned about induction proofs in high school. For
> induction to work, you need to prove that "P true for x" implies "P
> true for x + 1" and also a specific instance of P. (Usually P of 1 or
> 0.) I see concepts as equivalent to the first general condition of
> induction, but not the second. It would be nice to have some
> constraints on class T initialized with 0, for instance.

Again, these are runtime semantic guarantees.

> Sometimes this will be possible to know at compile-time, sometimes
> not.

How could it ever be known at compile time?

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Hyman Rosen on
Joel Eidsath wrote:
> Stroustrup's and Dos Reis' paper for the standard committee is
> available here:
> http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1782.pdf

It would be nice if they could vet the paper and remove
its many typographical and grammatical errors.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Edson Manoel on
>...If there were some abstract type from
>which int, char, etc, were derived then templates would be unnecessary.
>In other words, templates only exist because C++ isn't fully OO.
>...
>This is wrong (except maybe for the stuff about template
>metaprogramming). But there is not much functional difference between
>templates, as implemented now, and functions in more OO languages that
>work on the base object for all types.

There is a HUGE difference that I think you didn't understand well:
in other OO languages, such as Java, every object is actually a pointer
to an object in the heap. So, you can have a generic "Object" from whom
everyone is derived, and you can have horrible functions taking Object
as parameter that dynamically cast it down to some Interface or object
and use it... but the casting is made AT RUNTIME, and if you pass the
wrong object, the user will get a RUNTIME error. The templates in C++
are all bound and checked AT COMPILATION TIME -- if you pass the wrong
object, the compiler will spit an error, forcing you to fix it.

Also, the code runs faster because you don't need to have the
overhead of dynamic casts, virtual table calls and heap allocation; it
uses less memory because your containers can store the values directly
instead of storing pointers to the objects allocated one-by-one in the
heap.

Metaprogramming is a very powerful and useful tool... but maybe
_template_ metaprogramming is not the best approach to it, maybe in the
future they can come up with better ways to do metaprogramming, because
template metaprogramming is being abused in ways that compilers just
wasn't made to support.

You will only fully understand Concepts when you understand what
really templates are all about. You are confusing runtime behavior with
compilation time behavior... Concepts have nothing to do with
dynamic_casts... they will be something like "static interfaces" (or
traits) checked on compilation time. Concepts already exists, read a
STL documentation for example... they just are not "implemented" in the
language... although the Boost libraries implement a concept_check, the
article is proposing adding it to the core language.

Edson T. M. Manoel


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: kanze on
Joel Eidsath wrote:
> I came across a comment on Slashdot that gives me an excuse to
> write about the "A concept design" paper before the standards
> committee:

> "It was certainly interesting in the 'bad old days' when no
> two compilers implemented things like templates the same way.
> Of course, I'm no fan of templates, since they are essentially
> a kludge to work around the fact that there are atomic
> variable types that are not part of the OO implentation in C.
> If there were some abstract type from which int, char, etc,
> were derived then templates would be unnecessary. In other
> words, templates only exist because C++ isn't fully OO.

> Of course, then we wouldn't have 'template metaprogramming'
> and there would be a whole bunch of computer geeks who would
> have to stop writing papers and articles showing us how smart
> they are implementing the Sieve of Eratosthanes that prints
> prime numbers in compiler warnings, and get back to doing
> useful work. :-P"

> This is wrong (except maybe for the stuff about template
> metaprogramming). But there is not much functional difference
> between templates, as implemented now, and functions in more
> OO languages that work on the base object for all types.

> What makes templates different is the idea behind them.

With regards to the comments in Slashdot: what makes templates
different is that they enforce invariants accross the type
system at compile time. In a language with purely dynamic
typing (Lisp, Smalltalk), there is no need for templates (in the
C++ sense -- some dialects of Lisp are very powerful when it
comes to generic programming).

It's interesting to note that Java has felt the need to add a
form of templates, exactly for this reason -- Java's
implementation, from what little I understand, does not support
generic programming, but it does allow compile time enforcement
of invariants over the type system.

In the end, the distinction has nothing to do with OO or not OO;
it has to do with static typing vs. dynamic typing. A language
with static typing needs some form of generic classes or
templates. (And it doesn't need a common base class like Object
in order to be OO. Supposing "being OO" is a useful goal, or
even has a meaning.)

> The OO idea of a generic function is a function that works for
> some base type and any type derived from it. The reasoning
> behind this is something like "type hierarchies are 'IS A' so
> a function that works for a base should work for derived types
> as well." Real world code does not follow this paradigm,
> however. Instead, generic functions are envisioned to work on
> types with a given set of properties. There is no reason to
> expect that these properties should obey class hierarchies,
> even a majority of the time.

I disagree. The whole point of static type checking is that the
compiler detects errors, rather than the run-time library. For
run-time genericity, the requirement of a common base type (or
something similar) is essential for static type checking.

> It is the OO languages that have the kludge: an abstract base
> class from which everything derives, not C++.

That is a kludge. Because what functionality is common to all
possible classes?

But the problem isn't there. Having a common base class doesn't
do any harm in itself; it may even be useful for supporting
things like reflection. The problem is elsewhere: given an
abstract container, how do you ensure at compile time that only
type X is inserted into that container? Or more generally, how
do you enforce invariants over the type system at compile time
(which is what static type checking is all about)?

--
James Kanze GABI Software mailto:james.kanze(a)free.fr
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: C++/CLI limitations?
Next: SHA1