static polymorphism --- How it actually Happens ?

Discussion in 'C++' started by Pallav singh, Jun 3, 2009.

  1. Pallav singh

    Pallav singh Guest

    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();
    };
    Pallav singh, Jun 3, 2009
    #1
    1. Advertising

  2. * 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

    --
    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!
    Alf P. Steinbach, Jun 3, 2009
    #2
    1. Advertising

  3. Pallav singh

    James Kanze Guest

    Re: static polymorphism --- How it actually Happens ?

    On Jun 3, 5:39 pm, Jeff Schwab <> 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 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:
    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
    James Kanze, Jun 4, 2009
    #3
  4. Pallav singh

    ld Guest

    Re: static polymorphism --- How it actually Happens ?

    Hi James,

    On 4 juin, 10:35, James Kanze <> wrote:
    > On Jun 3, 5:39 pm, Jeff Schwab <> 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.
    ld, Jun 4, 2009
    #4
  5. Pallav singh

    James Kanze Guest

    Re: static polymorphism --- How it actually Happens ?

    On Jun 4, 12:16 pm, ld <> wrote:

    > On 4 juin, 10:35, James Kanze <> wrote:
    > > On Jun 3, 5:39 pm, Jeff Schwab <> 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.

    --
    James Kanze (GABI Software) email:
    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
    James Kanze, Jun 5, 2009
    #5
  6. Pallav singh

    ld Guest

    Re: static polymorphism --- How it actually Happens ?

    On 5 juin, 10:35, James Kanze <> 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).  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.
    ld, Jun 5, 2009
    #6
  7. Re: static polymorphism --- How it actually Happens ?

    ld wrote:
    > On 5 juin, 10:35, James Kanze <> 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
    Thomas J. Gritzan, Jun 5, 2009
    #7
  8. Pallav singh

    ld Guest

    Re: static polymorphism --- How it actually Happens ?

    On 5 juin, 17:27, "Thomas J. Gritzan" <> wrote:
    > ld wrote:
    > > On 5 juin, 10:35, James Kanze <> 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.
    ld, Jun 5, 2009
    #8
  9. Re: static polymorphism --- How it actually Happens ?

    ld schrieb:
    > On 5 juin, 17:27, "Thomas J. Gritzan" <> wrote:
    >> ld wrote:
    >>> On 5 juin, 10:35, James Kanze <> 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.


    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
    Thomas J. Gritzan, Jun 9, 2009
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stacey
    Replies:
    1
    Views:
    1,805
    Collin VanDyck
    Feb 10, 2004
  2. srikanth
    Replies:
    5
    Views:
    278
    Richard Heathfield
    Feb 28, 2006
  3. Divick
    Replies:
    1
    Views:
    290
    Sunil Varma
    Mar 17, 2006
  4. Krivenok Dmitry
    Replies:
    13
    Views:
    1,422
    Axter
    Jun 1, 2006
  5. NM
    Replies:
    6
    Views:
    461
    Default User
    Sep 20, 2006
Loading...

Share This Page