Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Does any widely-known program to extract template parameters requirements from source code already exist?

Reply
Thread Tools

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

 
 
Pavel Shved
Guest
Posts: n/a
 
      11-06-2007
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:perator= returning
something instead of T). Of course i mean automatic extraction
procedures.

The question is whether someone has done it already.

 
Reply With Quote
 
 
 
 
Mike Wahler
Guest
Posts: n/a
 
      11-06-2007

"Pavel Shved" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
> 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: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




 
Reply With Quote
 
 
 
 
Pavel Shved
Guest
Posts: n/a
 
      11-06-2007
On 6 , 15:50, "Mike Wahler" <(E-Mail Removed)> 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. :-\


 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      11-06-2007
Pavel Shved wrote:
> On 6 , 15:50, "Mike Wahler" <(E-Mail Removed)> 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


 
Reply With Quote
 
Pavel Shved
Guest
Posts: n/a
 
      11-06-2007
On 6 , 18:54, "Victor Bazarov" <(E-Mail Removed)> 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.

 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      11-07-2007
On Nov 6, 10:33 am, Pavel Shved <(E-Mail Removed)> 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:(E-Mail Removed)
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

 
Reply With Quote
 
Pavel Shved
Guest
Posts: n/a
 
      11-07-2007
On 7 , 12:43, James Kanze <(E-Mail Removed)> wrote:
> On Nov 6, 10:33 am, Pavel Shved <(E-Mail Removed)> 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!

 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      11-08-2007
On Nov 7, 1:54 pm, Pavel Shved <(E-Mail Removed)> wrote:
> On 7 , 12:43, James Kanze <(E-Mail Removed)> wrote:


> > On Nov 6, 10:33 am, Pavel Shved <(E-Mail Removed)> 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:(E-Mail Removed)
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

 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      11-08-2007
James Kanze wrote:
> On Nov 7, 1:54 pm, Pavel Shved <(E-Mail Removed)> wrote:
>> On 7 , 12:43, James Kanze <(E-Mail Removed)> wrote:

>
>>> On Nov 6, 10:33 am, Pavel Shved <(E-Mail Removed)> 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


 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      11-09-2007
On Nov 8, 3:34 pm, "Victor Bazarov" <(E-Mail Removed)> wrote:
> James Kanze wrote:
> > On Nov 7, 1:54 pm, Pavel Shved <(E-Mail Removed)> wrote:
> >> On 7 , 12:43, James Kanze <(E-Mail Removed)> wrote:


> >>> On Nov 6, 10:33 am, Pavel Shved <(E-Mail Removed)> 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:(E-Mail Removed)
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
skipping template parameters inside template parameters kito C++ 2 09-26-2010 12:04 AM
parse C source flow to extract program tree Crooter C Programming 6 01-16-2008 09:21 PM
501 PIX "deny any any" "allow any any" Any Anybody? Networking Student Cisco 4 11-16-2006 10:40 PM
template id does not match any template declaration? Alex Buell C++ 2 02-21-2006 06:33 PM
template-id does not match any template declaration blueblueblue2005 C++ 6 07-19-2005 02:59 PM



Advertisments