static polymorphism --- How it actually Happens ?
Pallav singh
polymorphic behaviour needed is invariant and can be determined at
compile time.
Then the Curiously Recurring Template Pattern (CRTP) can be used to
achieve static polymorphism, which is an imitation of polymorphism in
programming code but which is resolved at compile time and thus does
away with run-time virtual-table lookups.
template <class Derived>
struct base
{
void interface()
{
// ...
static_cast<Derived*>(this)->implementation();
// ...
}
};
struct derived : base<derived>
{
void implementation();
};
Alf P. Steinbach
> Can anyone explain How it actually Happens ?
Your assumption that readers are telepathic is pretty stupid. *What* is it that
you wonder how happens?
> polymorphic behaviour needed is invariant and can be determined at
> compile time.
If you says so.
> Then the Curiously Recurring Template Pattern (CRTP) can be used to
> achieve static polymorphism, which is an imitation of polymorphism
"imitation of polymorphism" is a meaningless phrase.
> in
> programming code
"programming code" is a meaningless phrase.
> but which is resolved at compile time
There is apparently no contradiction with what you've written earlier, so it
seems that the "but" is meaningless.
> and thus does
> away with run-time virtual-table lookups.
That conclusion is incorrect. "Does not require" does not mean the same as "does
away with".
> template <class Derived>
> struct base
> {
> void interface()
> {
> // ...
> static_cast<Derived*>(this)->implementation();
> // ...
> }
> };
>
> struct derived : base<derived>
> {
> void implementation();
> };
What is the question?
Cheers & hth.,
- Alf
--
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! :-) Just going there is good. Linking
to it is even better! Thanks in advance!
Jeff Schwab
> Can anyone explain How it actually Happens ?
>
> polymorphic behaviour needed is invariant and can be determined at
> compile time.
> Then the Curiously Recurring Template Pattern (CRTP) can be used to
> achieve static polymorphism, which is an imitation of polymorphism in
> programming code but which is resolved at compile time and thus does
> away with run-time virtual-table lookups.
Static polymorphism isn't an imitation of anything. In canonical
OO-speak, "polymorphism" is the ability of different objects to respond
to the same message in different ways.
In languages that are not restricted to OO, "static" polymorphism means
roughly "the ability of fixed syntax to mean different things, depending
on context." This kind of polymorphism is "static" in the sense that
the mapping is implemented at compile-time. The traditional example is
overloaded functions:
int square(int const i) { return i * i; }
double square(double const d) { return d * d; }
/* Function resolution depends on the type of n.
* Which function to call is determined at compile-time.
*/
square(n);
In statically typed languages that support operator overloading, viz.
C++, static polymorphism can be more subtle:
/* This syntax may or may not imply a function call.
* The determination is made at compile-time, though
* the operation may be performed at run-time.
*/
v += 5;
James Kanze
> Pallav singh wrote:
> > Can anyone explain How it actually Happens ?
> > polymorphic behaviour needed is invariant and can be
> > determined at compile time. Then the Curiously Recurring
> > Template Pattern (CRTP) can be used to achieve static
> > polymorphism, which is an imitation of polymorphism in
> > programming code but which is resolved at compile time and
> > thus does away with run-time virtual-table lookups.
> Static polymorphism isn't an imitation of anything. In
> canonical OO-speak, "polymorphism" is the ability of different
> objects to respond to the same message in different ways.
Polymorphism isn't restricted to OO; it's a well established
concept, first described, I think, in a paper by Christopher
Strachey in 1967. The "reference", as far as I know, is "On
Understanding Types, Data Abstraction, and Polymorphism", by
Cardelli and Wegner
(http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf). The
concept includes such things as function overloading and
implicit conversions, as well as parametric polymorphism and
inclusion. Roughly speaking, a function or operator is
polymorphic if it can be invoked on different types. (Thus, in
C, the + operator is polymorphic, since I can add integers, or
floating point values.)
> In languages that are not restricted to OO, "static"
> polymorphism means roughly "the ability of fixed syntax to
> mean different things, depending on context."
Formally, static doesn't mean anything when applied to
polymorphism. Informally, it is usually used to mean that the
polymorphism is somehow resolved at compile time, as opposed to
runtime. But even this doesn't mean much when more dynamic
languages are involved, like Lisp. Or for that matter, even in
C++: if I provide a single class interface (no virtual
functions), with several different implementations, in different
DLL's, and choose which DLL to load at runtime, is that static
polymorphism, or dynamic?
> This kind of polymorphism is "static" in the sense that the
> mapping is implemented at compile-time. The traditional
> example is overloaded functions:
> int square(int const i) { return i * i; }
> double square(double const d) { return d * d; }
> /* Function resolution depends on the type of n.
> * Which function to call is determined at compile-time.
> */
> square(n);
> In statically typed languages that support operator
> overloading, viz. C++, static polymorphism can be more
> subtle:
> /* This syntax may or may not imply a function call.
> * The determination is made at compile-time, though
> * the operation may be performed at run-time.
> */
> v += 5;
I think you mean that the syntax may or may not imply using
semantics defined by the user. I've used machines on which a
function would be called for the above even if v had type double
or long. The syntax for defining user defined semantics in C++
is, however, that of a function (with a somewhat special name).
Note that in C++, such a statement may involve all four types of
polymorphism: it clearly involves overloading; if v is a double,
it also involves coercion; if the operator+= function for type v
is a template, it involves parametric polymorphism, and if the
operator+= function is virtual, in involves inclusion
polymorphism. In C++, the first three are normally resolved at
compile time (but consider my example using DLL's, above); the
last is normally not resolved until runtime (but if the compiler
can determine the dynamic type of v at compile time, this might
not be true either).
--
James Kanze (GABI Software) email:james...@gmail.com
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
ld
On 4 juin, 10:35, James Kanze <james.ka...@gmail.com> wrote:
> On Jun 3, 5:39 pm, Jeff Schwab <j...@schwabcenter.com> wrote:
>
> > Pallav singh wrote:
> > > Can anyone explain How it actually Happens ?
> > > polymorphic behaviour needed is invariant and can be
> > > determined at compile time. Then the Curiously Recurring
> > > Template Pattern (CRTP) can be used to achieve static
> > > polymorphism, which is an imitation of polymorphism in
> > > programming code but which is resolved at compile time and
> > > thus does away with run-time virtual-table lookups.
> > Static polymorphism isn't an imitation of anything. In
> > canonical OO-speak, "polymorphism" is the ability of different
> > objects to respond to the same message in different ways.
>
> Polymorphism isn't restricted to OO; it's a well established
> concept, first described, I think, in a paper by Christopher
> Strachey in 1967. The "reference", as far as I know, is "On
> Understanding Types, Data Abstraction, and Polymorphism", by
> Cardelli and Wegner
> (http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf). The
> concept includes such things as function overloading and
> implicit conversions, as well as parametric polymorphism
except that in this paper, parametric polymorphism doesn't refer to C+
+ templates (i.e. type injection) but to Java generics (i.e. type
erasure) which are fundamentally different. A refinement/extension is
needed to be clear/complete.
> and
> inclusion. Roughly speaking, a function or operator is
> polymorphic if it can be invoked on different types. (Thus, in
> C, the + operator is polymorphic, since I can add integers, or
> floating point values.)
>
> > In languages that are not restricted to OO, "static"
> > polymorphism means roughly "the ability of fixed syntax to
> > mean different things, depending on context."
>
> Formally, static doesn't mean anything when applied to
> polymorphism. Informally, it is usually used to mean that the
> polymorphism is somehow resolved at compile time, as opposed to
> runtime. But even this doesn't mean much when more dynamic
> languages are involved, like Lisp. Or for that matter, even in
> C++: if I provide a single class interface (no virtual
> functions), with several different implementations, in different
> DLL's, and choose which DLL to load at runtime, is that static
> polymorphism, or dynamic?
It's not polymorphic at all because it's exclusive, that is only one
class implementation (one morph) is available at a time in the
program.
> > This kind of polymorphism is "static" in the sense that the
> > mapping is implemented at compile-time. The traditional
> > example is overloaded functions:
> > int square(int const i) { return i * i; }
> > double square(double const d) { return d * d; }
the const qualifier can be removed.
a+, ld.
Jeff Schwab
>>> int square(int const i) { return i * i; }
>
> the const qualifier can be removed.
But need not be. I prefer variables to be const whenever possible. In
particular, if a variable is not const, I believe there should be a
reason. In my opinion, the five characters one could save by removing "
const" in the above expression would be insufficient justification to
make the variable non-const. If you choose to provide a separate
declaration of the above function, it may omit the const:
int square(int i);
// ...
James Kanze
> On 4 juin, 10:35, James Kanze <james.ka...@gmail.com> wrote:
> > On Jun 3, 5:39 pm, Jeff Schwab <j...@schwabcenter.com> wrote:
> > > Pallav singh wrote:
> > > > Can anyone explain How it actually Happens ?
> > > > polymorphic behaviour needed is invariant and can be
> > > > determined at compile time. Then the Curiously Recurring
> > > > Template Pattern (CRTP) can be used to achieve static
> > > > polymorphism, which is an imitation of polymorphism in
> > > > programming code but which is resolved at compile time and
> > > > thus does away with run-time virtual-table lookups.
> > > Static polymorphism isn't an imitation of anything. In
> > > canonical OO-speak, "polymorphism" is the ability of different
> > > objects to respond to the same message in different ways.
> > Polymorphism isn't restricted to OO; it's a well established
> > concept, first described, I think, in a paper by Christopher
> > Strachey in 1967. The "reference", as far as I know, is "On
> > Understanding Types, Data Abstraction, and Polymorphism", by
> > Cardelli and Wegner
> > (http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf). The
> > concept includes such things as function overloading and
> > implicit conversions, as well as parametric polymorphism
> except that in this paper, parametric polymorphism doesn't
> refer to C++ templates (i.e. type injection) but to Java
> generics (i.e. type erasure) which are fundamentally
> different.
The paper refers to neither C++ templates nor Java generics,
since neither existed at the time it was written. The paper
also isn't really concerned with implementation details; both
C++ templates and Java generics meet its definition of
parametric polymorphism. (The authors do cite Ada's generic
procedures as an example parametric polymorphism. As far as I
know, Ada's generic procedures are implemented very much like
C++'s templates.)
> A refinement/extension is needed to be clear/complete.
The paper is from 1985. Obviously (or hopefully), there's been
some evolution since then; if nothing else, both parametric
polymorphism and inclusion have become very mainstream. I don't
think that the basic theoretical aspects have changed much,
however.
ld
> > > The "reference", as far as I know, is "On
> > > Understanding Types, Data Abstraction, and Polymorphism", by
> > > Cardelli and Wegner
> > > (http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf). The
> > > concept includes such things as function overloading and
> > > implicit conversions, as well as parametric polymorphism
> > except that in this paper, parametric polymorphism doesn't
> > refer to C++ templates (i.e. type injection) but to Java
> > generics (i.e. type erasure) which are fundamentally
> > different.
>
> The paper refers to neither C++ templates nor Java generics,
> since neither existed at the time it was written.
Sometimes James, I wonder if you do it intensionally. Obviously the
paper cannot cite something that doesn't exist at the time of its
writing, that is why I put explicitly the purpose in parenthesis just
after the (not so much) "modern" example.
> The paper
> also isn't really concerned with implementation details; both
> C++ templates and Java generics meet its definition of
> parametric polymorphism.
No. The semantic described for parametric polymorphism cannot handle
value semantic like C++ templates do (and Java generics cannot) and
this is explicitly stated in the paper (without referring to the not-
yet-existing C++ templates). This is why I am talking of a fundamental
difference: type injection (generated implementation) versus type
erasure (shared implementation).
> (The authors do cite Ada's generic
> procedures as an example parametric polymorphism. As far as I
> know, Ada's generic procedures are implemented very much like
> C++'s templates.)
No, very much like Java generics (type erasure with shared
implementation). Ada generics cannot handle value semantic.
> > A refinement/extension is needed to be clear/complete.
>
> The paper is from 1985. Obviously (or hopefully), there's been
> some evolution since then; if nothing else, both parametric
> polymorphism and inclusion have become very mainstream.
and this is why there is so much confusion between C++ templates and
other languages' generics.
> I don't
> think that the basic theoretical aspects have changed much,
> however.
I prefer to use a different classification in my seminar, more
orthogonal and less ambiguous.
a+, ld.
Thomas J. Gritzan
> On 5 juin, 10:35, James Kanze <james.ka...@gmail.com> wrote:
>>>> The "reference", as far as I know, is "On
>>>> Understanding Types, Data Abstraction, and Polymorphism", by
>>>> Cardelli and Wegner
>>>> (http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf).
James Kanze wrote:
>> The paper
>> also isn't really concerned with implementation details; both
>> C++ templates and Java generics meet its definition of
>> parametric polymorphism.
>
> No. The semantic described for parametric polymorphism cannot handle
> value semantic like C++ templates do (and Java generics cannot) and
> this is explicitly stated in the paper (without referring to the not-
> yet-existing C++ templates). This is why I am talking of a fundamental
> difference: type injection (generated implementation) versus type
> erasure (shared implementation).
While it is true, that parametric polymorphism as described in this
paper should share a single implementation, but they also don't need
"any kind of run-time test or special encondings", so Java generics are
not a kind of parametric polymorphism.
Java generics just build a type-checking layer above Java's inclusion
polymorphism with classes and interfaces.
Ada's generic procedures are described like C++ templates, with the
difference that they need to be instantiated explicitly.
"However, generic type polymorphism in Ada is syntactic since generic
instantiation is performed at compile time with actual type
values that must be determinable (manifest) at compile time."
"With respect to polymorphism, they have the advantage that
specialized optimal code can be generated for the different forms of
inputs. On the other hand, in true polymorphic systems code is generated
only once for every generic procedure."
The paper distinguish _true parametric polymorphism_, where source code
*and* the implementations are identical, and some kind of relaxed
parametric polymorphism, with the example of Ada's generic procedures.
An example for the true form would be qsort of the C library, which only
has one implementation but works on any types (using void*).
You can do similar with C++ templates, using one implementation
(template specialisation) for void* and type-safe wrappers that use this
implementation.
In terms of this paper, C++ templates are a mix between the relaxed form
of parametric polymorphism (normal templates) and ad-hoc polymorphism
(template specialisation).
--
Thomas
ld
> ld wrote:
> > On 5 juin, 10:35, James Kanze <james.ka...@gmail.com> wrote:
> >>>> The "reference", as far as I know, is "On
> >>>> Understanding Types, Data Abstraction, and Polymorphism", by
> >>>> Cardelli and Wegner
> >>>> (http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf).
> James Kanze wrote:
> >> The paper
> >> also isn't really concerned with implementation details; both
> >> C++ templates and Java generics meet its definition of
> >> parametric polymorphism.
>
> > No. The semantic described for parametric polymorphism cannot handle
> > value semantic like C++ templates do (and Java generics cannot) and
> > this is explicitly stated in the paper (without referring to the not-
> > yet-existing C++ templates). This is why I am talking of a fundamental
> > difference: type injection (generated implementation) versus type
> > erasure (shared implementation).
>
> While it is true, that parametric polymorphism as described in this
> paper should share a single implementation, but they also don't need
> "any kind of run-time test or special encondings", so Java generics are
> not a kind of parametric polymorphism.
This is effectively the paragraph I was referring to ;-) But I don't
catch your conclusion. Java generics do not need always runtime tests,
specially when applied on interfaces and used through these
interfaces. Pretty much like Ada generics.
> Java generics just build a type-checking layer above Java's inclusion
> polymorphism with classes and interfaces.
>
> Ada's generic procedures are described like C++ templates, with the
> difference that they need to be instantiated explicitly.
>
> "However, generic type polymorphism in Ada is syntactic since generic
> instantiation is performed at compile time with actual type
> values that must be determinable (manifest) at compile time."
Which is pretty similar to Java generics if you want to avoid runtime
tests (cast).
> "With respect to polymorphism, they have the advantage that
> specialized optimal code can be generated for the different forms of
> inputs. On the other hand, in true polymorphic systems code is generated
> only once for every generic procedure."
It is so close to Java generics that it has been implemented too:
http://files.slembcke.net/misc/JavaGenericSpecialization.pdf
> The paper distinguish _true parametric polymorphism_, where source code
> *and* the implementations are identical, and some kind of relaxed
> parametric polymorphism, with the example of Ada's generic procedures.
the latter looks more as ad-hoc polymorphism to me (see below).
> An example for the true form would be qsort of the C library, which only
> has one implementation but works on any types (using void*).
qsort uses high order function to manage different types, not
polymorphism.
> You can do similar with C++ templates, using one implementation
> (template specialisation) for void* and type-safe wrappers that use this
> implementation.
yes. this is often used to avoid code bloat but this require to use
types with a semantic by reference and type erasure (e.g. void*) which
means that you use templates (+overloading) to emulate the generics.
On the opposite, generics cannot emulate templates for types with a
semantic by value.
> In terms of this paper, C++ templates are a mix between the relaxed form
> of parametric polymorphism (normal templates) and ad-hoc polymorphism
> (template specialisation).
Indeed, this is very close to my conclusion. But in practice (in my
seminar), I prefer to use different terms (more orthogonal). I
consider C++ templates as parametric *types* (no polymorphism), where
each parametrized type is a new type (i.e. type injection). Then
overloading achieves the ad-hoc polymorphism. Combining template and
overloading looks like a form of parametric polymorphism as described
in the paper (a-la-generics), but it is not since the former (not
polymorphic) is of little use without the latter (polymorphic) and
cannot be dissociated (not true for the reverse). So in term of the
paper, I would say that it is a parametrized ad-hoc polymorphism.
a+, ld.
Thomas J. Gritzan
When Java generics are used through interfaces, they do need "any kind
of run-time test or special encondings". You can only use generics with
any class in Java, because they all are sub-classes of java.lang.Object.
Functionally, you cannot do anything with generics that can't be done
without them. Generics just do the type-checking at compile time.
Pretty much unlike Ada generics, which are more like a restricted subset
of C++ templates.
>> "However, generic type polymorphism in Ada is syntactic since generic
>> instantiation is performed at compile time with actual type
>> values that must be determinable (manifest) at compile time."
>
> Which is pretty similar to Java generics if you want to avoid runtime
> tests (cast).
And to C++ templates, then?
>> "With respect to polymorphism, they have the advantage that
>> specialized optimal code can be generated for the different forms of
>> inputs. On the other hand, in true polymorphic systems code is generated
>> only once for every generic procedure."
>
> It is so close to Java generics that it has been implemented too:
>
> http://files.slembcke.net/misc/JavaGenericSpecialization.pdf
So you talk about an optimisation of Java generics. But if Java generics
are instantiated like C++ templates for optimization, they are not
parametric polymorphism as described in the paper, because that requires
_one_ implementation that handles every type universally.
>> An example for the true form would be qsort of the C library, which only
>> has one implementation but works on any types (using void*).
>
> qsort uses high order function to manage different types, not
> polymorphism.
qsort uses a function as parameter (it's parametic polyphormism, isn't
it?) to specify the sorting order. The actual sorting logic as well as
the movement of values is type agnostic.
Wikipedia says:
"polymorphism is a programming language feature that allows values of
different data types to be handled using a uniform interface."
While C doesn't have it as direct language feature, qsort provides a
uniform interface and a single implementation and can handle different
data types. These types don't have common interfaces or super classes as
Java requires for it's polymorphism. So why is qsort not a polymorphic
function?
>> In terms of this paper, C++ templates are a mix between the relaxed form
>> of parametric polymorphism (normal templates) and ad-hoc polymorphism
>> (template specialisation).
>
> Indeed, this is very close to my conclusion. But in practice (in my
> seminar), I prefer to use different terms (more orthogonal). I
> consider C++ templates as parametric *types* (no polymorphism), where
> each parametrized type is a new type (i.e. type injection). Then
> overloading achieves the ad-hoc polymorphism.
Do you mean overloading or template specialisation?
And what are template function? Are they parametric types, too?
And why isn't it polymorphism?
> Combining template and
> overloading looks like a form of parametric polymorphism as described
> in the paper (a-la-generics), but it is not since the former (not
> polymorphic) is of little use without the latter (polymorphic) and
> cannot be dissociated (not true for the reverse). So in term of the
> paper, I would say that it is a parametrized ad-hoc polymorphism.
So you say that templates (the former) are not polymorphic and are of
little use without overloading (the latter), which is polymorphic.
Well, while templates without overloading (do you mean template
specialisation?) is similar to what Ada generics (and Java generics) do,
and you consider both these as parametric polymorphism, but templates as
something else.
I can't follow your conclusions.
--
Thomas