The Artima Developer Community
Sponsored Link

Weblogs Forum
Thinking out loud about Concepts

12 replies on 1 page. Most recent reply: Aug 11, 2005 3:45 AM by Vincent O'Sullivan

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 12 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Thinking out loud about Concepts (View in Weblogs)
Posted: Aug 6, 2005 11:10 AM
Reply to this message Reply
Summary
Here is an interesting problem with making C++ style concepts a real type in a programming language.
Advertisement
In Heron you are supposed to be allowed to be able to write a concept as follows:
  concept Stack {
    contract {
      push(value_type x);
      pop() : value_type;
      is_empty() : bool;
    }
    requires {
      value_type : Any;
    }
  }
This should make immediate sense to most C++ programmers (hopefully). But now here is an interesting predicament:
  void MyFxn(Stack& x, Stack& y) {
    y.push(x.pop()); 
  }

  int main() {
    MyStack[int] s1;
    MyStack[string] s2;
    MyFxn(s1, s2); // compiler accepts this happily 
  }
What I don't like about this is that the compiler can't catch the error until inside of the implementation of MyFxn. The current implementation I am looking at would make things even worse, because it might end up being a runtime error ... yuck!

One solution for the programmer is to use the C++ way of doing things:

  void MyFxn[T : Stack](T& x, T& y) {
    y.push(x.pop()); 
  }
This enforces the fact that both parameters must be precisely the same, but leaves the flexibility that they are constrained to the Stack concept. I was really hoping to find a more elegant solution than this, in fact I was hoping to be able to entirely avoid template functions altogether in the languauge. Any thoughts or comments?


Ron Ruble

Posts: 10
Nickname: ronr
Registered: Aug, 2004

Re: Thinking out loud about Concepts Posted: Aug 6, 2005 12:10 PM
Reply to this message Reply
I wonder if the reason this is uncomfortable isn't that we're mixing some metaphors.

In the concept declaration, you are using the term value_type to mean, basically, any type. This implies that a Stack will either be a generic container, holding anything (as a VB Collection can hold anything that could be assigned to a variant, or typeless languages like Perl offer generic containers), or a specialization, for a specific type, leading to an instance of Stack<int>, Stack<String>

In the definition of MyFxn, you are saying it accepts 2 Stack references. This is only accurate if Stacks are unspecialized. If Stacks are specialized, then the C++ definition is accurate. If the implementation of Heron treats the function definition as more of a template, even if the syntax remains the same, then it can tell that the usage of MyFxn is a syntax violation. If the implementation of Heron treats the function definition as a definition of a function, then it's a syntax error at the function definition.

Or am I blowing smoke?

Robert Parnell

Posts: 22
Nickname: robparnl
Registered: Jul, 2005

Re: Thinking out loud about Concepts Posted: Aug 6, 2005 12:28 PM
Reply to this message Reply
This might be way off topic. But, it almost sounds like a meta-data problem?

What are your standards for comments? Sure, it sould follow the C-style and form. Why not put hints to the compiler in the comments?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Thinking out loud about Concepts Posted: Aug 6, 2005 12:58 PM
Reply to this message Reply
> This might be way off topic. But, it almost sounds like a
> meta-data problem?
>
> What are your standards for comments? Sure, it sould
> follow the C-style and form. Why not put hints to the
> compiler in the comments?

This is an interesting idea. I am planning to use template metaprogramming techniques in the standard library for compiler hints. I can pass compiler-hints as template parameters to modules when I import them.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Thinking out loud about Concepts Posted: Aug 6, 2005 1:04 PM
Reply to this message Reply
> I wonder if the reason this is uncomfortable isn't that
> we're mixing some metaphors.
>
> In the concept declaration, you are using the term
> value_type to mean, basically, any type. This implies that
> a Stack will either be a generic container, holding
> anything (as a VB Collection can hold anything that could
> be assigned to a variant, or typeless languages like Perl
> offer generic containers), or a specialization, for a
> specific type, leading to an instance of Stack<int>,
> Stack<String>

Yes.

> In the definition of MyFxn, you are saying it accepts 2
> Stack references. This is only accurate if Stacks are
> unspecialized. If Stacks are specialized, then the C++
> definition is accurate.

I don't follow what you are saying here.

> If the implementation of Heron
> treats the function definition as more of a template, even
> if the syntax remains the same, then it can tell that the
> usage of MyFxn is a syntax violation. If the
> implementation of Heron treats the function definition as
> a definition of a function, then it's a syntax error at
> the function definition.
>
> Or am I blowing smoke?

I don't think so, but I am a little lost.

Just so we are clear: Stack is a polymorphic type which can refer to any class which provides the three functions and a member type called value_type. Nothing more.

Tanton Gibbs

Posts: 20
Nickname: tanton
Registered: Aug, 2005

Re: Thinking out loud about Concepts Posted: Aug 6, 2005 2:34 PM
Reply to this message Reply
You definitely don't want this to be a runtime error; it should be caught at compile time. In C++, we usually get an error like "Error on line x in MyFun, instantiated from line y with types IntStack, FooStack" That way, you get the entire error stack. For a staticly typed language, that shouldn't be a problem.

One question that I had when dealing with ConceptC was how to say that two concepts should represent the same type. For instance, in your MyFxn function, you have two Stacks that should both be of the same type. How do you specify this? Currently, if you pass in two different typed Stacks you (might/should/will) get a compiler error depending on the convertability of the Stacks, etc...

One thing to think about is allowing users to explicitly specify what type an Any member should bind to when writing a concept. This would be similar to a template, but the compiler would check to make sure the provided type is identical to the specified type. For instance:

void MyFxn( Stack[value_type=int]& x,
Stack[value_type=int]& y )
{
y.push(x.pop());
}


In this case, if you passed in a FloatStack, the compiler would complain; furthermore, it shows in the function specification what the type should be.

For syntax sugar, if the concept only has one Any type, then you could leave off the name= part.


void MyFxn( Stack[int]& x,
Stack[int]& y )
{
y.push(x.pop());
}


In both of these cases, calling MyFxn would result in an error if the type instantiating the concept did not provide a value_type member that was an int.

Secondly, what if you wanted both of them to be the same, but you didn't care what type they were? Perhaps something like:


void MyFxn( Stack[T1:Any]& x,
Stack[T1]& y )


This says that both x and y are Stacks of Anys, but both must be the same (T1).

Thirdly, what if you had three types, two of which should be the same, and the third you didn't care about


void MyFxn( Stack[T1:Any]& x,
Stack[T1]& y,
Stack& z );


Finally, what if you had two types and wanted them both different types


void MyFxn( Stack[T1:Any]& x,
Stack[T2:Any]& y );


You may have already solved this problem much more elegantly than this, but it has plagued me for quite some time.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Thinking out loud about Concepts Posted: Aug 7, 2005 3:39 PM
Reply to this message Reply
> You may have already solved this problem much more
> elegantly than this, but it has plagued me for quite some
> time.

My solution to all of this is to allow parameterization of concepts.

By the way Tanton are you still actively pursuing ConceptC? I have a lot of code I would be happy to share with you. Feel free to write me: cdiggins@videotron.ca

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Thinking out loud about Concepts Posted: Aug 7, 2005 8:50 PM
Reply to this message Reply
> In Heron you are supposed to be allowed to be able to
> write a concept as follows:
>
> <pre>
> concept Stack {
> contract {
> push(value_type x);
> pop() : value_type;
> is_empty() : bool;
> }
> requires {
> value_type : Any;
> }
> }
> </pre>
>
> This should make immediate sense to most C++ programmers
> (hopefully). But now here is an interesting predicament:
>
> <pre>
> void MyFxn(Stack& x, Stack& y) {
> y.push(x.pop());
> }
>
> int main() {
> MyStack[int] s1;
> MyStack[string] s2;
> MyFxn(s1, s2); // compiler accepts this happily
> }
> </pre>
>
> What I don't like about this is that the compiler can't
> catch the error until inside of the implementation of
> <code>MyFxn</code>. The current implementation I am
> looking at would make things even worse, because it might
> end up being a runtime error ... yuck!

It's worse than that. Unless MyFxn knows whether you have an int or string stack, you can't really use it at all. (well, you can find out if it's empty, but that's not much).

I don't know much about concepts (I think I read Stroustrup's paper a long time ago) but from the example you gave, they have the same subtyping restrictions as inheritance. Generic parameters are viral in the presence of inheritance.

Pablo Aguilar

Posts: 1
Nickname: pmag
Registered: Aug, 2005

Re: Thinking out loud about Concepts Posted: Aug 7, 2005 9:12 PM
Reply to this message Reply
> One solution for the programmer is to use the C++ way of
> doing things:
>
> <pre>
> void MyFxn[T : Stack](T& x, T& y) {
> y.push(x.pop());
> }
> </pre>
>
> This enforces the fact that both parameters must be
> precisely the same, but leaves the flexibility that they
> are constrained to the Stack concept. I was really hoping
> to find a more elegant solution than this, in fact I was
> hoping to be able to entirely avoid template functions
> altogether in the languauge. Any thoughts or comments?

Well, shouldn't you be able to do something like the following?

int main() {
MyStack[int] s1;
MyStack[long] s2;
MyFxn(s1, s2); // ok, because int can be converted to long
}

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Thinking out loud about Concepts Posted: Aug 7, 2005 10:58 PM
Reply to this message Reply
> I don't know much about concepts (I think I read
> Stroustrup's paper a long time ago) but from the example
> you gave, they have the same subtyping restrictions as
> inheritance.

pardon my ignorance, but what specifically do you mean by the subtyping restrictions on inheritance?

> Generic parameters are viral in the presence
> of inheritance.

By this do you mean that they are required all the way throughout the inheritance tree, with each level of inheritance adding their own parameters? Or are you referring to something else?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Thinking out loud about Concepts Posted: Aug 7, 2005 11:04 PM
Reply to this message Reply
> Well, shouldn't you be able to do something like the
> following?
>

> int main() {
> MyStack[int] s1;
> MyStack[long] s2;
> MyFxn(s1, s2); // ok, because int can be converted to
> d to long
> }
>


I agree that this is natural. I am not sure that I will allow it. Some languages allow this kind of subtyping, but others don't.

Sean Conner

Posts: 19
Nickname: spc476
Registered: Aug, 2005

Re: Thinking out loud about Concepts Posted: Aug 10, 2005 4:03 PM
Reply to this message Reply
I've been playing around with the following concept:


int example(int a,int b)
where (a >= 0), (a < 32),
(b > a), (b < 400)
{
// code that returns some value on a and b
}


The intent is to provide a bit more diagnosis either during compiling (if constant paramters are compiled in) or runtime (kind of like C's assert() and can be turned off if needed). So, how about something like:


void MyFunction(Stack& x,Stack& y)
where (typeof(x) == typeof(y))
{
y.push(x.pop());
}


or maybe:


void MyFunction(Stack& x,Stack& y)
where(derivedfrom(x,y) || derivedfrom(y,x))
{
y.push(x.pop());
}


Just thowing out ideas ...

Vincent O'Sullivan

Posts: 724
Nickname: vincent
Registered: Nov, 2002

Re: Thinking out loud about Concepts Posted: Aug 11, 2005 3:45 AM
Reply to this message Reply
That just handles preconditions. Post-conditions would be the next locical step. Using that notation why not:
int example(int a,int b)
where (a >= 0), (a < 32),
(b > a), (b < 400)
whence (a >= example), (example < b)
{
// code that returns some value on a and b
}
Vince.

Flat View: This topic has 12 replies on 1 page
Topic: High Performance Dynamic Typing in C++ Previous Topic   Next Topic Topic: The Tortoise and the Hare


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us