static polymorphism --- How it actually Happens ?

P

Pallav singh

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.

template <class Derived>
struct base
{
void interface()
{
// ...
static_cast<Derived*>(this)->implementation();
// ...
}
};

struct derived : base<derived>
{
void implementation();
};
 
A

Alf P. Steinbach

* Pallav singh:
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
 
J

James Kanze

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).
 
L

ld

Hi James,

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.)


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.

the const qualifier can be removed.

a+, ld.
 
J

James Kanze

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.
 
L

ld

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.
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.
 
T

Thomas J. Gritzan

ld said:
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).
 
L

ld

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.
 
T

Thomas J. Gritzan

ld said:
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.

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.
Which is pretty similar to Java generics if you want to avoid runtime
tests (cast).

And to C++ templates, then?
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.
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?
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,754
Messages
2,569,527
Members
44,998
Latest member
MarissaEub

Latest Threads

Top