Does any widely-known program to extract template parameters requirements from source code already e

Discussion in 'C++' started by Pavel Shved, Nov 6, 2007.

  1. Pavel Shved

    Pavel Shved Guest

    Is there a program of wide use that automatically extracts template
    parameters requirements from source code of template functions?

    I mean the following: assume we have a template function that demands
    its template parameter(s) to meet certain requirements. For example
    simple sorting function

    template <typename T> void sort(T* t, int N)
    {
    for (int i=0;i<N-1; i++)
    for (int j=N-1;j>i;j--)
    if (t[j-1] < t[j]) {
    T temp=t[j];
    t[j]=t[j-1];
    t[j-1]=temp;
    }
    }

    requires T to have the following members: a) operator<(T) returning
    bool; b) copy-constructor, accepting T, and c) operator=(T) (usually
    these operators use passing-by-reference, but this assumption is way
    too strict).

    I know (or at least I'm sure I do) there is a way to formalize and
    extract strict requirements (which the above axample doesn't
    intgroduce) as there is also possibility to form unstrict, common ones
    (common is that hardly anyone would write T::eek:perator= returning
    something instead of T). Of course i mean automatic extraction
    procedures.

    The question is whether someone has done it already.
     
    Pavel Shved, Nov 6, 2007
    #1
    1. Advertising

  2. Pavel Shved

    Mike Wahler Guest

    "Pavel Shved" <> wrote in message
    news:...
    > Is there a program of wide use that automatically extracts template
    > parameters requirements from source code of template functions?
    >
    > I mean the following: assume we have a template function that demands
    > its template parameter(s) to meet certain requirements. For example
    > simple sorting function
    >
    > template <typename T> void sort(T* t, int N)
    > {
    > for (int i=0;i<N-1; i++)
    > for (int j=N-1;j>i;j--)
    > if (t[j-1] < t[j]) {
    > T temp=t[j];
    > t[j]=t[j-1];
    > t[j-1]=temp;
    > }
    > }
    >
    > requires T to have the following members: a) operator<(T) returning
    > bool; b) copy-constructor, accepting T, and c) operator=(T) (usually
    > these operators use passing-by-reference, but this assumption is way
    > too strict).
    >
    > I know (or at least I'm sure I do) there is a way to formalize and
    > extract strict requirements (which the above axample doesn't
    > intgroduce) as there is also possibility to form unstrict, common ones
    > (common is that hardly anyone would write T::eek:perator= returning
    > something instead of T). Of course i mean automatic extraction
    > procedures.
    >
    > The question is whether someone has done it already.


    I think that if you write code which instantiates such a template,
    a compiler will issue diagnostics if its requirements are not
    met. Or perhaps I misunderstand your question.

    As for your specific example above, the only thing a compiler
    would complain about would be operator<(), since lacking
    a definition of copy ctor and operator=(), the compiler will
    synthesize them. Of course those default semantics might
    not be what you need.

    template <typename T> void sort(T* t, int N)
    {
    for (int i=0;i<N-1; i++)
    for (int j=N-1;j>i;j--)
    if (t[j-1] < t[j]) {
    T temp=t[j];
    t[j]=t[j-1];
    t[j-1]=temp;
    }
    }

    class T
    {
    };


    int main()
    {
    T t;
    sort(&t, 42);
    return 0;
    }

    ..\usenet.cpp(475) : error C2676: binary '<' : 'T' does not define this
    operator or a conversion to a type acceptable to the predefined operator
    .\usenet.cpp(490) : see reference to function template instantiation
    'void sort<T>(T *,int)' being compiled
    with
    [
    T=T
    ]


    Modify type T to:

    class T
    {
    public:
    bool operator<(const T& rhs)
    {
    return true;
    }
    };

    No errors or warnings. (VC++ 2005 Express)


    -Mike
     
    Mike Wahler, Nov 6, 2007
    #2
    1. Advertising

  3. Pavel Shved

    Pavel Shved Guest

    On 6 , 15:50, "Mike Wahler" <> wrote:

    > I think that if you write code which instantiates such a template,
    > a compiler will issue diagnostics if its requirements are not
    > met. Or perhaps I misunderstand your question.


    What i need is to deduce TEXT like 'parameter T must have the
    following members: etc. etc.' from the source code.

    >
    > Modify type T to:
    >
    > class T
    > {
    > public:
    > bool operator<(const T& rhs)
    > {
    > return true;
    > }
    >
    > };
    >
    > No errors or warnings. (VC++ 2005 Express)


    But this class does have default operator= and copy-constructor
    granted him by the compiler. Anyway that's not the essence of the
    problem.

    PS. I'm noob and i can only hope that my message will appear in a
    proper place of this topic. :-\
     
    Pavel Shved, Nov 6, 2007
    #3
  4. Pavel Shved wrote:
    > On 6 , 15:50, "Mike Wahler" <> wrote:
    >
    >> I think that if you write code which instantiates such a template,
    >> a compiler will issue diagnostics if its requirements are not
    >> met. Or perhaps I misunderstand your question.

    >
    > What i need is to deduce TEXT like 'parameter T must have the
    > following members: etc. etc.' from the source code.
    >
    >>
    >> Modify type T to:
    >>
    >> class T
    >> {
    >> public:
    >> bool operator<(const T& rhs)
    >> {
    >> return true;
    >> }
    >>
    >> };
    >>
    >> No errors or warnings. (VC++ 2005 Express)

    >
    > But this class does have default operator= and copy-constructor
    > granted him by the compiler. Anyway that's not the essence of the
    > problem.
    >
    > PS. I'm noob and i can only hope that my message will appear in a
    > proper place of this topic. :-\


    Sorry, I haven't followed the thread. I just have a couple of cents
    worth of a note: when C++ gets the "concept" support (some of that is
    already included in G++ in research form, IIRC), there will be plenty
    of tools that would reverse-engineer classes to extract "concepts"
    from them (I can see a tool that extracts a common concept from more
    than one class).

    It can be worth asking in a G++ discussion forum, the folks who right
    now are involved with adding "concepts" to G++ might know a simple
    way (or have thought about it) to reverse the process.

    Right now I don't know of any tool which would do that.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Nov 6, 2007
    #4
  5. Pavel Shved

    Pavel Shved Guest

    On 6 , 18:54, "Victor Bazarov" <> wrote:
    > Sorry, I haven't followed the thread. I just have a couple of cents
    > worth of a note: when C++ gets the "concept" support (some of that is
    > already included in G++ in research form, IIRC), there will be plenty
    > of tools that would reverse-engineer classes to extract "concepts"
    > from them (I can see a tool that extracts a common concept from more
    > than one class).


    Thank you for the info. Discarding these mysterious 'concepts' from
    my search results was a true mistake.
     
    Pavel Shved, Nov 6, 2007
    #5
  6. Pavel Shved

    James Kanze Guest

    On Nov 6, 10:33 am, Pavel Shved <> wrote:
    > Is there a program of wide use that automatically extracts
    > template parameters requirements from source code of template
    > functions?


    It's fundamentally impossible. How can a program divine the
    intent of the author?

    > I mean the following: assume we have a template function that
    > demands its template parameter(s) to meet certain
    > requirements. For example simple sorting function


    > template <typename T> void sort(T* t, int N)
    > {
    > for (int i=0;i<N-1; i++)
    > for (int j=N-1;j>i;j--)
    > if (t[j-1] < t[j]) {
    > T temp=t[j];
    > t[j]=t[j-1];
    > t[j-1]=temp;
    > }
    > }


    > requires T to have the following members: a) operator<(T) returning
    > bool; b) copy-constructor, accepting T, and c) operator=(T) (usually
    > these operators use passing-by-reference, but this assumption is way
    > too strict).


    First, your requirements are far more restrictive than the code
    requires. All that the code requires is that the specified
    operations are supported. Taking all implicit conversions into
    account. Secondly, of course, the function has very definite
    requirements with regards to the semantics of some of the
    operators. Requirements which I don't think any tool could
    deduce. And finally, in most real cases, the author will define
    the required concepts as part of the requirements; the actual
    implementation may not use them all but he has a right to use
    them in the next version. The standard lists a return type of
    T& as part of the Assignable concept; it's quite possible for an
    implementation never to use it, but it remains a requirement.
    And std::list requires Assignable, although most implementations
    never use assignment. For class templates, some requirements
    apply to the class itself, others just to specific functions in
    the class---how would you distinguish?

    --
    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, Nov 7, 2007
    #6
  7. Pavel Shved

    Pavel Shved Guest

    On 7 , 12:43, James Kanze <> wrote:
    > On Nov 6, 10:33 am, Pavel Shved <> wrote:
    >
    > > Is there a program of wide use that automatically extracts
    > > template parameters requirements from source code of template
    > > functions?

    >
    > It's fundamentally impossible. How can a program divine the
    > intent of the author?


    Fundamentally - it IS possible. Imagine the (infinite) set of all
    possible C++ types; we are to deduce a subset of it: which of them can
    be used as template parameters. We have a procedure to check whether
    a single class statisfies original requirements - mere experiment
    (compiling our class against the function in question). So we should
    only invent proper terms in which we describe the subset. Is english
    (or any other human language) rich enough to describe it? I think it
    is.

    One can argue that the ability of compiling t[j-1] < t[j] depends on
    the environment. It truly does, but then let's expand our set to the
    set of all possible C++ programs, and add environment descrioption to
    it.

    > > I mean the following: assume we have a template function that
    > > demands its template parameter(s) to meet certain
    > > requirements. For example simple sorting function
    > > template <typename T> void sort(T* t, int N)
    > > {
    > > for (int i=0;i<N-1; i++)
    > > for (int j=N-1;j>i;j--)
    > > if (t[j-1] < t[j]) {
    > > T temp=t[j];
    > > t[j]=t[j-1];
    > > t[j-1]=temp;
    > > }
    > > }
    > > requires T to have the following members: a) operator<(T) returning
    > > bool; b) copy-constructor, accepting T, and c) operator=(T) (usually
    > > these operators use passing-by-reference, but this assumption is way
    > > too strict).

    >
    > First, your requirements are far more restrictive than the code
    > requires. All that the code requires is that the specified
    > operations are supported. Taking all implicit conversions into
    > account.


    Would the following form of requirement statisfy you?
    vv
    a) T has member function operator<(.) visible in public scope which
    return type is implicitely castable to bool and which argument is
    implicitely castable from T with no ambiguity that cannot be resolved
    by standard rules; or there is [bool] operator>( ]T[ , ]T[ ) in one of
    the wrapping namespaces with no ambiguity etc...
    ^^
    We are only to define in english (which is done in standard!) two
    terms denoted above like ]something[ and [something] with aid of known
    implicit casting rules. By ther way, defining LessThanComparable, C++
    Standard uses the same terms, referring to them as 'convertible to
    bool'.
    As we can see, this description involves some restrictions to the
    environment which our class is in.

    > Secondly, of course, the function has very definite
    > requirements with regards to the semantics of some of the
    > operators. Requirements which I don't think any tool could
    > deduce.


    Does the persistance of unsolvable equations forces us not to solve
    linear ones? ;-)

    > And finally, in most real cases, the author will define
    > the required concepts as part of the requirements; the actual
    > implementation may not use them all but he has a right to use
    > them in the next version. The standard lists a return type of
    > T& as part of the Assignable concept; it's quite possible for an
    > implementation never to use it, but it remains a requirement.
    > And std::list requires Assignable, although most implementations
    > never use assignment.


    You are very right when we deal with something that a) is already
    standartized; b) should be implementation-independent. In my certain
    case neither the former nor the latter takes place. Moreover, the
    study of the discreapancies between author's and real requirements is
    valuable, both when checking what can we do wrong failing then to
    compile against 'future versions' and aiding the author to test
    whether his implementation is covered by the concepts he wrote in
    documentaion.

    > For class templates, some requirements
    > apply to the class itself, others just to specific functions in
    > the class---how would you distinguish?


    Why should we distinguish? We'd rather gather them!
     
    Pavel Shved, Nov 7, 2007
    #7
  8. Pavel Shved

    James Kanze Guest

    On Nov 7, 1:54 pm, Pavel Shved <> wrote:
    > On 7 , 12:43, James Kanze <> wrote:


    > > On Nov 6, 10:33 am, Pavel Shved <> wrote:


    > > > Is there a program of wide use that automatically extracts
    > > > template parameters requirements from source code of template
    > > > functions?


    > > It's fundamentally impossible. How can a program divine the
    > > intent of the author?


    > Fundamentally - it IS possible.


    Fundamentally, it is NOT. The information simply isn't there
    for any tool to extract.

    I gave a simple example in my posting: std::list requires that
    the class over which it is instantiated by Assignable. Most
    implementations never use assignment. How could a tool
    determine that an assignment operator is necessary (and that it
    must return T&) if there isn't the slightest reference to it in
    the code.

    > Imagine the (infinite) set of all possible C++ types; we are
    > to deduce a subset of it: which of them can be used as
    > template parameters. We have a procedure to check whether a
    > single class statisfies original requirements - mere
    > experiment (compiling our class against the function in
    > question).


    The problem is where to find the original requirements. There's
    not necessarily any trace of them in the code, so the procedure
    will have to read the comments. Except that the requirements
    may not even have been copied into the source as comments; most
    of the implementations of std::list simply refer to the standard
    for the requirements.

    [...]
    > Would the following form of requirement statisfy you?
    > vv
    > a) T has member function operator<(.) visible in public scope which
    > return type is implicitely castable to bool and which argument is
    > implicitely castable from T with no ambiguity that cannot be resolved
    > by standard rules; or there is [bool] operator>( ]T[ , ]T[ ) in one of
    > the wrapping namespaces with no ambiguity etc...


    Certainly not. First, it requires operator< to be a member
    function, which certainly isn't necessary. Secondly, it doesn't
    take into account possible conversions. A class like:

    class C
    {
    public:
    explicit C( int i ) : myI( i ) {}
    operator int() const { return myI ; }

    private:
    int myI ;
    } ;

    will work for your function, for example, and there's not an
    operator< in site.

    Most importantly, of course, even a human, just reading your
    code, cannot determine what the requirements are. Do you
    "require" support for all of the comparison operators, or simply
    <? (In other words, is the fact that you just use <, and none
    of the others, an accident of the implementation, or is it a
    contractual restriction.)

    > > Secondly, of course, the function has very definite
    > > requirements with regards to the semantics of some of the
    > > operators. Requirements which I don't think any tool could
    > > deduce.


    > Does the persistance of unsolvable equations forces us not to solve
    > linear ones? ;-)


    False analogy. In this case, we have the requirements. They
    must exist before anyone can write the code. Rather than asking
    a tool to produce a necessarily incomplete, and possibly
    incorrect version of them, doesn't it make more sense to require
    the author to publish them with his code?

    > > For class templates, some requirements apply to the class
    > > itself, others just to specific functions in the class---how
    > > would you distinguish?


    > Why should we distinguish? We'd rather gather them!


    Because it's important. The implementations of std::list that
    I've seen all use operator<, and very few use operator=. Never
    the less, it is legal to instantiate an std::list over a type
    which doesn't support operator<, but not over a type which
    doesn't support operator=. The requirement for the first is
    limited to certain functions; the requirement for the second
    applies to the class.

    --
    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, Nov 8, 2007
    #8
  9. James Kanze wrote:
    > On Nov 7, 1:54 pm, Pavel Shved <> wrote:
    >> On 7 , 12:43, James Kanze <> wrote:

    >
    >>> On Nov 6, 10:33 am, Pavel Shved <> wrote:

    >
    >>>> Is there a program of wide use that automatically extracts
    >>>> template parameters requirements from source code of template
    >>>> functions?

    >
    >>> It's fundamentally impossible. How can a program divine the
    >>> intent of the author?

    >
    >> Fundamentally - it IS possible.

    >
    > Fundamentally, it is NOT. The information simply isn't there
    > for any tool to extract.
    >
    > I gave a simple example in my posting: std::list requires [..]


    I believe you're arguing different points. Pavel (as I see it)
    says that extracting at least something would be possible and in
    many cases enough. James says that it is impossible to capture
    *all* requirements in *every* case. Would you agree that both
    are correct?

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Nov 8, 2007
    #9
  10. Pavel Shved

    James Kanze Guest

    On Nov 8, 3:34 pm, "Victor Bazarov" <> wrote:
    > James Kanze wrote:
    > > On Nov 7, 1:54 pm, Pavel Shved <> wrote:
    > >> On 7 , 12:43, James Kanze <> wrote:


    > >>> On Nov 6, 10:33 am, Pavel Shved <> wrote:


    > >>>> Is there a program of wide use that automatically extracts
    > >>>> template parameters requirements from source code of template
    > >>>> functions?


    > >>> It's fundamentally impossible. How can a program divine the
    > >>> intent of the author?


    > >> Fundamentally - it IS possible.


    > > Fundamentally, it is NOT. The information simply isn't there
    > > for any tool to extract.


    > > I gave a simple example in my posting: std::list requires [..]


    > I believe you're arguing different points. Pavel (as I see
    > it) says that extracting at least something would be possible
    > and in many cases enough.


    Extracting something is certainly possible, but what you can
    extract is of absolutely no use at all, ever. It has no real
    advantage over just trying and seeing if it compiles. And as we
    all know, the fact that something compiles without errors
    doesn't mean that it is correct.

    --
    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, Nov 9, 2007
    #10
  11. James Kanze wrote:
    > On Nov 8, 3:34 pm, "Victor Bazarov" <> wrote:
    >> James Kanze wrote:
    >>> On Nov 7, 1:54 pm, Pavel Shved <> wrote:
    >>>> On 7 , 12:43, James Kanze <> wrote:

    >
    >>>>> On Nov 6, 10:33 am, Pavel Shved <> wrote:

    >
    >>>>>> Is there a program of wide use that automatically extracts
    >>>>>> template parameters requirements from source code of template
    >>>>>> functions?

    >
    >>>>> It's fundamentally impossible. How can a program divine the
    >>>>> intent of the author?

    >
    >>>> Fundamentally - it IS possible.

    >
    >>> Fundamentally, it is NOT. The information simply isn't there
    >>> for any tool to extract.

    >
    >>> I gave a simple example in my posting: std::list requires [..]

    >
    >> I believe you're arguing different points. Pavel (as I see
    >> it) says that extracting at least something would be possible
    >> and in many cases enough.

    >
    > Extracting something is certainly possible, but what you can
    > extract is of absolutely no use at all, ever. It has no real
    > advantage over just trying and seeing if it compiles. And as we
    > all know, the fact that something compiles without errors
    > doesn't mean that it is correct.


    What's the term for a person who continues arguing even though it
    is apparent that there is no argument to be continued? Here are
    two principles you might consider: "never say 'never' (or 'ever')",
    and "one man's trash is another man's treasure". OK?

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Nov 9, 2007
    #11
  12. Pavel Shved

    Pavel Shved Guest

    On Nov 9, 17:23, "Victor Bazarov" <> wrote:

    > "one man's trash is another man's treasure". OK?


    True.
    I must thank James though, his arguments are of much use and I really
    should to review what I'm trying to achieve.
     
    Pavel Shved, Nov 12, 2007
    #12
    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. Chuck Roth
    Replies:
    3
    Views:
    1,087
    Jim Lewis
    Sep 14, 2005
  2. Bucco
    Replies:
    2
    Views:
    412
    Peter Flynn
    Aug 10, 2005
  3. Carl Tribble
    Replies:
    2
    Views:
    391
    Mark Rae
    Jun 18, 2006
  4. kito
    Replies:
    2
    Views:
    439
  5. Ross
    Replies:
    3
    Views:
    378
    Arne Vajhøj
    Aug 6, 2011
Loading...

Share This Page