The Artima Developer Community
Sponsored Link

Weblogs Forum
The Concept of Concepts

14 replies on 1 page. Most recent reply: Aug 2, 2005 5:19 PM by Christopher Diggins

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 14 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

The Concept of Concepts (View in Weblogs)
Posted: Jul 11, 2005 11:10 AM
Reply to this message Reply
Summary
The next Heron release will be replacing the interface construct with the concept construct.
Advertisement
The next version of Heron will be introducing the "concept" construct which will supercede the interface construct. A Heron concept is very much like the C++ standard library notion of a concept, except that in Heron it will be an actual type which can be used as a variable declaration or function arguments.

A concept is a set of function declations, contract clauses, and local type declarations which describe a class. A concept variable or parameter is compatible with any class which models the concept. In order for a class to model a concept it is only has to provide public functions which match the signatures of the functions in the contract, and provide public types which have the appropriate name and match the requirements.

Concepts can be used to describe template parameters, but can also be used simply as function parameters. For example a simple concept is the Array concept.

concept Array[A : type]
{
  contract
  {
    GetAt(int n) : A {
      pre {
        n >= 0;
        n < Count();
      }
    }
    SetAt(int n, A x) {
      pre {
        n >= 0;
        n < Count();
      }
      post {
        GetAt(n) == x;
      }
    }
    Count() : uint;
  }
  types
  {
    value_type : type;
  }
}

If you want to write a function which can accept any object which models the Array concept you can write:

  output_array(Array a) {
    for (int i=0; i<a.Count(); ++i) {
      println(a.GetAt(i));
    }
  }

A concept also provides support for Programming with Contracts by providing a mechanism for expressing contractual clauses. The pre section delineates the set of contractual preconditions, while the post section delineates the contractual postconditions.

For more information on concepts visit I strongly recommend The SGI STL Introduction. For more on the shortcomings of C++ concepts you can visit the Boost Concept Checking library.

I'd like your feedback, do you approve or disapprove of the the concept construct? Does it make sense what I am trying to do? Are the advantages of the approach obvious?


Keith Ray

Posts: 658
Nickname: keithray
Registered: May, 2003

Re: The Concept of Concepts Posted: Jul 12, 2005 9:31 AM
Reply to this message Reply
Sounds a bit like the "informal protocol" idea of Objective-C. (which also has formal protocols.)

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Concept of Concepts Posted: Jul 12, 2005 11:42 AM
Reply to this message Reply
> Sounds a bit like the "informal protocol" idea of
> Objective-C. (which also has formal protocols.)

The Objective-C informal protocol is very similar but only goes part of the way. AFAIK it only expresses member function requirements. The Heron concept also provides a way to express and have verified at runtime) preconditions and postconditions. The Heron concept can also allow the expression of member types.

Incidentally informal protocols are similar to a structural subtyping library for C++ (where they are called interfaces) at http://www.kangaroologic.com/interfaces/

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: The Concept of Concepts Posted: Jul 14, 2005 6:38 AM
Reply to this message Reply
> A Heron concept is very
> much like the C++ standard library notion of a concept,
> except that
> in Heron it will be an actual type which can be used as a
> variable declaration
> or function arguments.

Support for concepts is definitively useful (and there exists a couple of proposals for this for C++0x, with a good chance of it actually making it into the next C++ standard).

What I'm wondering with this approach, is: if you have for example a concept Incrementable (meaning you can do "++<variable>"), and variables modelling this, such as Int, Float, etc., what will something like the following (C++ syntax) mean in Heron:

void f(Incrementable i)
{
int value=i;
}

What I mean, is, should the above succeed or not? f() might be called with an int, but it might also (in C++) be called with something that is incrementable _but not convertible to int_, such as a pointer.

Usually, concepts are not considered types in themselves, but rather like "types of types", or type sets (Incrementable may be considered the set of all types modelling it). This is also the case for the concepts proposals for C++, which extends the template system to implement this. One syntax is:

template<Incrementable I>
void f(I value)
{
...
}

Here, Incrementable is a concept (defined elsewhere), and I is the actual type used to instantiate the template (such as "int"). Thus, in this case, concepts are not types in themselves, but something else.

Another way you can look at it, is to consider the usual template:

template<class T>
void f(T)

Here, this models the mathematical concept "for all types T, do...". I.e., it accepts any type; it's unrestricted. This is a rich source of template-related error messages in C++... (which is part of the reason for the concept proposals).

However, with concepts, you get "restricted templates" or "constrained genericity", so you can say "for all types T, where (constraint), do..."

> For more on the shortcomings
> of C++ concepts you can visit the
> Boost Concept Checking library.

An alternative to this is the "Concept Traits Library" (http://neoscientists.org/~tschwinger/boostdev/concept_traits/libs/concept_traits/doc/) which avoids some of the problems of BCCL, including allowing you to overload on concepts.

Regards,

Terje

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Concept of Concepts Posted: Jul 14, 2005 11:24 AM
Reply to this message Reply
> What I'm wondering with this approach, is: if you have for
> example a concept Incrementable (meaning you can do
> "++<variable>"), and variables modelling this, such as
> Int, Float, etc., what will something like the following
> (C++ syntax) mean in Heron:
>
> void f(Incrementable i)
> {
> int value=i;
> }
>
> What I mean, is, should the above succeed or not?

No.

> f()
> might be called with an int, but it might also (in C++) be
> called with something that is incrementable _but not
> convertible to int_, such as a pointer.

Exactly. In this case you could could have a separate concept Convertible[int], for instance, and combine it with Incrementable (through inheritance) to create a new concept (i.e. IncrementableIntegerCompatible or IntLike)

> Usually, concepts are not considered types in themselves,
> but rather like "types of types", or type sets
> (Incrementable may be considered the set of all types
> modelling it).

A Heron concept is more than just a set of types. It is actually a type in its own right. For instance you will be able to write:


Incrementable i;

int n = 4;
i = n;
n = ++i.Cast<int>();
Print(IToS(n)); // outputs 5

char c = 'a';
c = ++i.Cast<char>();
Print(CToS(c)); // outputs 'b'


This implies Heron concepts are like polymorphic pointers. The results of this are sigificant. For instance you can have a collection of Incrementables (not just a list of types which model Incrementable).


int x;
char c;
list[Incrementable] l;
l.push_back(x);
l.push_back(c);
l.push_back(l::iterator());
l.push_back(1);
l.push_back(FuBar());


This completely removes the need for any other runtime polymorphism mechanism. This way Heron doesn't have to have virtual functions, abstract functions, abstract base classes, and interfaces, to be object oriented.

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: The Concept of Concepts Posted: Jul 14, 2005 2:34 PM
Reply to this message Reply
> This completely removes the need for any other runtime
> polymorphism mechanism. This way Heron doesn't have to
> have virtual functions, abstract functions, abstract base
> classes, and interfaces, to be object oriented.

Really? Then how would you model something like this? (Java)

interface Shape
{
abstract void draw();
}

class Line implements Shape
{
void draw() { /* draw line */ }
}

class Circle implements Shape
{
void draw() { /* draw circle */ }
}

void f(Shape s)
{
s.draw();
}

It seems to me that for this to work, you need some form of runtime dispatch, i.e. something like virtual functions, even if it may be called something else, and if so, what's the big difference (if there is one), when it comes to run-time polymorphism?

In other words, it seems Heron's concepts takes the place of interfaces in other languages (i.e. defining a set of types that may be used for it), except that it's not "inclusion polymorphism" (inheritance), but rather something like compile-time and run-time "parametric polymorphism" (the way polymorphism is defined here: http://research.microsoft.com/Users/luca/Papers/OnUnderstanding.A4.pdf).

Regards,

Terje

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Concept of Concepts Posted: Jul 14, 2005 3:09 PM
Reply to this message Reply
interface Shape {
  contract {
    draw();
  }
}
 
class Line { 
  draw() { 
   /* draw line */ 
  }
}
 
class Circle {
  public {
    draw() { 
     /* draw circle */ 
    } 
  }
}
 
f(Shape s) {
  s.draw();
}


That's all there is to it :-)

> It seems to me that for this to work, you need some form
> of runtime dispatch,

Yes, the Heron concept provides that when it is required. It intelligently chooses between dynamic dispatching and type replacement. The mechanism is a bit complicated, but I'll be writing a paper on it soon.

> i.e. something like virtual
> functions, even if it may be called something else, and if
> so, what's the big difference (if there is one), when it
> comes to run-time polymorphism?

Well there's no "big difference" as far as I can tell.

> In other words, it seems Heron's concepts takes the place
> of interfaces in other languages (i.e. defining a set of
> types that may be used for it), except that it's not
> "inclusion polymorphism" (inheritance), but rather
> something like compile-time and run-time "parametric
> polymorphism" (the way polymorphism is defined here:
> http://research.microsoft.com/Users/luca/Papers/OnUnderstan
> ding.A4.pdf).

I am not sure I understand what you are saying here, (and that is a rather dense paper to read), but Heron concepts can be used as you would expect a C++0x concept to be used:

concept SortableArray[T : type] {
  inherits {
    Array[T];
  }
  contract {
    Swap(int n1, int n2) {
      pre {
       n1 >= 0);
    }
    Compare(int n1, int n2) : int;
  }
  public {
    Sort() { ... }
  }
}
 
concept Comparable {
  public {
    Compare(self x) : int;
  }
}
 
class MyArray[T : Comparable] {
  public {
    _init(int n) { ... }
    GetAt(int n) : T { ... }
    SetAt(T n) : T { ... }  
    Swap(int n1, int n2) { ... }
    Compare(int n1, int n2) : int { ... }
  }     
}


But can also be used as a runtime polymorphic variable:

main() {
  SortableArray[int] a = SortableArray[int](3);
  a.SetAt(0, 4);
  a.SetAt(1, 2);
  a.SetAt(2, 3);
  a.Sort();
  Print(a); // outputs 2, 3, 4
}


So technically Heron concepts are two separate things depending on their context, a set of constraints on a template parameter, or a structurally subtyped polymorphic variable.

By the way this is a great discussion, and is really helping me hone and clarify my ideas. Thanks!

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: The Concept of Concepts Posted: Jul 14, 2005 3:50 PM
Reply to this message Reply
>
> interface Shape {
>   contract {
>     draw();
>   }
> }
> 
> class Line { 
>   draw() { 
>    /* draw line */ 
>   }
> }
> 
> class Circle {
>   public {
>     draw() { 
>      /* draw circle */ 
>     } 
>   }
> }
> 
> f(Shape s) {
>   s.draw();
> }
> 

>
> That's all there is to it :-)

I see. Yes, it looks like an interesting application of signature-based polymorphism, that not only works at compile-time (like templates in C++) but also at run-time (similar to interfaces in other languages, but not requiring inheritance to work).

I now understand how there may be an advantage in having concepts as types, somehow, in that you get run-time polymorphism, that way. With the C++ proposals, the type is deduced at compile-time, so any run-time polymorphism needs the usual inheritance-based approach (at least when it comes to what there's language support for).

There's a similar synergy between the concept proposals and the DbC proposal in C++, where concepts check conformance at compile-time (the part of the concept that may be compile-time checked), and contracts check the run-time requirements.

However, the DbC proposal checks the conformance of (compile-time resolved) types, not "run-time concepts".

> Yes, the Heron concept provides that when it is required.
> It intelligently chooses between dynamic dispatching and
> type replacement.

Nice.

> Heron concepts
> can be used as you would expect a C++0x concept to be
> used:
>
>
> concept SortableArray[T : type] {
>   inherits {
>     Array[T];
>   }
>   contract {
>     Swap(int n1, int n2) {
>       pre {
>        n1 >= 0);
>     }
>     Compare(int n1, int n2) : int;
>   }
>   public {
>     Sort() { ... }
>   }
> }
> 
> concept Comparable {
>   public {
>     Compare(self x) : int;
>   }
> }
> 
> class MyArray[T : Comparable] {
>   public {
>     _init(int n) { ... }
>     GetAt(int n) : T { ... }
>     SetAt(T n) : T { ... }  
>     Swap(int n1, int n2) { ... }
>     Compare(int n1, int n2) : int { ... }
>   }     
> }


How does Heron's concepts check conformance? In the C++ proposals, there are two approaches:

1) Name-based conformance: You have to explicitly specify that a type models a concept

2) Signature-based conformance: If a type matches the signatures of the concept, it's taken as a match

Based on your Shape/Line/Circle example, it seems 2) is used. There's then a potential issue of "accidental conformance". As "the Guru" in the CUJ "Conversations"-series might have said it: :) Consider this parable (quoting from your example):

interface Shape {
contract {
draw();
}
}

class DeckOfCards {
public {
draw() {
/* draw a card */
}
}
}

drawShape(Shape s) {
s.draw();
}

DeckOfCards d;

drawShape(d); // Oops, not that kind of draw.

This example may be a bit contrieved, but at the last C++ standards meeting (at Lillehammer), the "Indiana"-gang (Jeremy Siek and Doug Gregor) - whose concept proposal uses named conformance - showed an example of how signature-based conformance (Bjarne Stroustrup and Gabriel Dos Reis' concept proposal) may not work with some types, because there may be types that are "structually equal", but having different semantics. Their example was an istream_iterator, which is an input-iterator (so the range it delimits can only be read once), but which you can't distinguish, just based on the signature, from a forward iterator (where you may pass over the range multiple times).

> By the way this is a great discussion, and is really
> helping me hone and clarify my ideas. Thanks!

Likewise. :)

Regards,

Terje

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: The Concept of Concepts Posted: Jul 14, 2005 4:09 PM
Reply to this message Reply
>
> interface Shape {
>   contract {
>     draw();
>   }
> }
> 
> class Line { 
>   draw() { 
>    /* draw line */ 
>   }
> }
> 
> class Circle {
>   public {
>     draw() { 
>      /* draw circle */ 
>     } 
>   }
> }
> 
> f(Shape s) {
>   s.draw();
> }
> 

>
> That's all there is to it :-)
>
> > i.e. something like virtual
> > functions, even if it may be called something else, and
> if
> > so, what's the big difference (if there is one), when
> it
> > comes to run-time polymorphism?
>
> Well there's no "big difference" as far as I can tell.

The above may have come off a bit "edgy", sorry about that. I'd say that not requiring inheritance for run-time polymorphism is a big difference. :)

Dynamically typed languages also has something similar. However, typically, the checking is missing. E.g. in PHP, you may write:

function f($value)
{
$value->f(); // Error here, if $value's type doesn't have a member function f();
}

The type of the variable $value may be anything, and may change at run-time, so it's basically a variant. However, you can't say - like you can with Heron - that $value should model such and such concept. Far from it. The only checking you _can_ get, is that you can write:

function f(SomeClass $value)
{
}

This checks that the type of $value is (derived from) SomeClass. This is similar to classic inheritance-based run-time polymorphism.

Since you can specify so little about types in interfaces in PHP, it has much of the same problems (extended to runtime!) that unrestricted genericity has in C++: You risk getting errors deep into the implementation of something, rather than at the call site, where they belong.

Regards,

Terje

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Concept of Concepts Posted: Jul 14, 2005 4:30 PM
Reply to this message Reply
> I see. Yes, it looks like an interesting application of
> signature-based polymorphism, that not only works at
> compile-time (like templates in C++) but also at run-time
> (similar to interfaces in other languages, but not
> requiring inheritance to work).

That's a nice description.

> I now understand how there may be an advantage in having
> concepts as types, somehow, in that you get run-time
> polymorphism, that way. With the C++ proposals, the type
> is deduced at compile-time, so any run-time polymorphism
> needs the usual inheritance-based approach (at least when
> it comes to what there's language support for).
>
> There's a similar synergy between the concept proposals
> and the DbC proposal in C++, where concepts check
> conformance at compile-time (the part of the concept that
> may be compile-time checked), and contracts check the
> run-time requirements.
>
> However, the DbC proposal checks the conformance of
> (compile-time resolved) types, not "run-time concepts".

The Heron concept check both.

> Nice.

Thanks!

> How does Heron's concepts check conformance? In the C++
> proposals, there are two approaches:
>
> 1) Name-based conformance: You have to explicitly specify
> that a type models a concept
>
> 2) Signature-based conformance: If a type matches the
> signatures of the concept, it's taken as a match

Number 2 along with runtime verification of contractual requirements, obligations and invariants.

> Based on your Shape/Line/Circle example, it seems 2) is
> used. There's then a potential issue of "accidental
> conformance". As "the Guru" in the CUJ
> "Conversations"-series might have said it: :) Consider
> this parable (quoting from your example):

This is a possibility only in severely underspecified concepts. Heron concepts come with precondition and postcondition specifiers, which help to identify accidental conformance.

> This example may be a bit contrieved, but at the last C++
> standards meeting (at Lillehammer), the "Indiana"-gang
> (Jeremy Siek and Doug Gregor) - whose concept proposal
> uses named conformance - showed an example of how
> signature-based conformance (Bjarne Stroustrup and Gabriel
> Dos Reis' concept proposal) may not work with some types,
> because there may be types that are "structually equal",
> but having different semantics. Their example was an
> istream_iterator, which is an input-iterator (so the range
> it delimits can only be read once), but which you can't
> distinguish, just based on the signature, from a forward
> iterator (where you may pass over the range multiple
> times).

This can be identified through the use of invariants, which will be part of the concept as well.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Concept of Concepts Posted: Jul 14, 2005 4:39 PM
Reply to this message Reply
> The above may have come off a bit "edgy", sorry about
> that.

No problem :-)

> I'd say that not requiring inheritance for run-time
> polymorphism is a big difference. :)

Yes you are right.

> Since you can specify so little about types in interfaces
> in PHP, it has much of the same problems (extended to
> runtime!) that unrestricted genericity has in C++: You
> risk getting errors deep into the implementation of
> something, rather than at the call site, where they
> belong.

I can see that can be a problem, but hopefully I can trust programmers to be prudent. It takes a certain amount of delinquency to use objects where they are not supposed to, and a certain amount of bad-luck to achieve accidental conformance. However this embodies the programming language designer's dilemma, how much expressiveness to give to the programmer. Too much and you risk them making big errors, too little and you risk alienating them.

Tim LS

Posts: 37
Nickname: parchandri
Registered: Jul, 2005

Re: The Concept of Concepts Posted: Jul 18, 2005 11:46 PM
Reply to this message Reply
I agree that Terje's example shouldn't work

void f(Incrementable i)
{
int value=i;
}


but what about this?

void f(Incrementable i)
{
Incrementable value=i;
}


What I'm getting at is how can you declare a variable to hold onto i if you don't know the actual type, and you only know the concept? Can you do this at run-time sensibly? Or do you treat Incrementable like a C++ template parameter and compile versions for different types (but the syntax has an obvious problem: what if your function g is like this and a and b are different types?)...

void g(Incrementable a, Incrementable b)
{
Incrementable x = a;
}

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Concept of Concepts Posted: Jul 19, 2005 2:53 PM
Reply to this message Reply
> I agree that Terje's example shouldn't work
>
>
void f(Incrementable i)
> {
> int value=i;
> }

>
> but what about this?
>
>
void f(Incrementable i)
> {
> Incrementable value=i;
> }


Yes that works.

> What I'm getting at is how can you declare a variable to
> hold onto i if you don't know the actual type, and you
> only know the concept? Can you do this at run-time
> sensibly?

Yes, but you can also use the compiler to deduct the type in many cases at compile-time.

> Or do you treat Incrementable like a C++
> template parameter and compile versions for different
> types (but the syntax has an obvious problem: what if your
> function g is like this and a and b are different
> types?)...
>
>
void g(Incrementable a, Incrementable b)
> {
> Incrementable x = a;
> }


By initializing x to be the same as a it has the same concrete type as a.

Mike Capp

Posts: 11
Nickname: mikecapp
Registered: Aug, 2005

Re: The Concept of Concepts Posted: Aug 2, 2005 2:55 PM
Reply to this message Reply
> Heron concepts come with precondition and postcondition
> specifiers, which help to identify accidental conformance.

Could you give some concrete examples? I was worried about this too, and still think that there are cases where you'd want to require an explicit "yes, this object/class implements this concept" declaration. Similarly, I'd sometimes want to declare when writing a class that it implements concept X, just because it allows the IDE and/or compiler to diagnose problems that much sooner.

The other thing that strikes me is that people are going to want a convenient "adaptor" syntax to handle the diametrically opposite case of "accidental nonconformance". That is, you have a sort algorithm that expects a "Sortable" concept, where Sortable requires a "compare" method, and you have a class which has a method with exactly the right behaviour but which happens to have been named "compareTo".

Such an adaptor syntax might also allow explicit named conformance to be added to third-party classes without modifiable source, which is presumably the big downside of that approach.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Concept of Concepts Posted: Aug 2, 2005 5:19 PM
Reply to this message Reply
> Could you give some concrete examples?

Surprisingly no. Maybe FIFO versus LIFO stack, but checking the post-condition of the pop operation is so expensive that it is practically pointless.

> I was worried about
> this too, and still think that there are cases where you'd
> want to require an explicit "yes, this object/class
> implements this concept" declaration. Similarly, I'd
> sometimes want to declare when writing a class that it
> implements concept X, just because it allows the IDE
> and/or compiler to diagnose problems that much sooner.

In these cases it might be best to use the actual concrete types, or common base types. In fact you can force at compile-time that a class inherits from a specific base, and implements a concept. Together this should provide the safety needed.

> The other thing that strikes me is that people are going
> to want a convenient "adaptor" syntax to handle the
> diametrically opposite case of "accidental
> nonconformance". That is, you have a sort algorithm that
> expects a "Sortable" concept, where Sortable requires a
> "compare" method, and you have a class which has a method
> with exactly the right behaviour but which happens to have
> been named "compareTo".
>
> Such an adaptor syntax might also allow explicit named
> conformance to be added to third-party classes without
> modifiable source, which is presumably the big downside of
> that approach.

I am not sure that syntactic support for an adaptor is neccessary, the following code should do the trick:

class AdaptToComparable[T : type] {
  inherits {
    T;
  }
  public {
    compare(T x) : int { 
      return compareTo(x);  
    }
  }
}


This is hopefully sufficient.

Flat View: This topic has 14 replies on 1 page
Topic: Are Tests First Class Clients? Previous Topic   Next Topic Topic: C++ Preconceptions


Sponsored Links



Google
  Web Artima.com   

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