Walter,

First of all, I would like to say that I like the direction that D is going so far, and appreciate your innovative work on this new language.

I know support for generics in D is probably still on the horizin, but have you given it any serious thought?  We can definitely improve on C++ templates, both in ease of implementation and flexibility.  Even before you start on templates it would be good to have in mind at least a vague concept of what you plan to do.  I use C++ templates aggressively, so I have some ideas about features to add and drop.

First, if you haven't read Modern C++ Design: Generic Programming and Design Patterns Applied by Andrei Alexandrescu, you should get a copy.  A great book!  I have already applied many of the concepts he covers.  It should be required reading for anyone who wants in depth understand of Generic Programming.

I have so many ideas and could write forever about generics, here's just some food for thought.  If you're interested, I would be glad to share more ideas.

I will just give you a few insights of where you can improve on C++.  First, we generic programmers need a compile-time typeof operator.  I have run into so many cases where I said to myself, "I sure wish I had a typeof operator." It would make generic programming so much more elegant.  Then you could have compile-time conditionals to handle different types in different ways, like this:

cswitch(typeof(variable))
{
   case int:  // handle an integer
   case string: // hangle a string
   ...
}

Here "cswitch" is a compile-time conditional.  This means the conditional is resolved at compile time, and optimized appropriately so that no performance is lost and dead code is eliminated.  You could also have cif, celse, etc.

Another idea I have to improve on C++ is type specialization syntax.  We could implement type specialization more explicitly using typelists.  This would provide a more readable type specialization that (I think) would be easier to implement.

Here's a simple example:

template <typename T : {int, uint, long, ulong, float, double}>
T Add(T a, T b)
{
   return a + b;
}

This specializes the Add function to need apply only to int, float, double, and extended.  You could then write another Add template that would handle concatenation of container types.

This leads me to another feature that would be nice to have: type lists (see chapter 3 of Modern C++ design.)  It would be nice to categorize types something like this:

typelist NumericTypes { int, uint, long, ulong, float, double }; typelist ContainerTypes { list, set, vector, queue, stack };

Then you could rewrite the Add function:

template <typename T : NumericTypes>
T Add(T a, T b)
{
   return a + b;
}

template <typename T : ContainerTypes>
T Add(T a, T b)
{
   T result;
   result.append(a);
   result.append(b);
   return result;
}

Like I said, I have many other ideas, including making generic programming even more generic to reduce code duplication and improve maintainabiliity.

Let me know what you think.

Craig

I like your typelist idea, but am dubious about the compile-time switch. Can you expound on this idea and give a non-trivial example?

Matthew

"Craig Black" <cblack@ara.com> wrote in message news:af7k2g$1f31$1@digitaldaemon.com...
> Walter,
>
> First of all, I would like to say that I like the direction that D is
going
> so far, and appreciate your innovative work on this new language.
>
> I know support for generics in D is probably still on the horizin, but
have
> you given it any serious thought?  We can definitely improve on C++ templates, both in ease of implementation and flexibility.  Even before
you
> start on templates it would be good to have in mind at least a vague
concept
> of what you plan to do.  I use C++ templates aggressively, so I have some ideas about features to add and drop.
>
> First, if you haven't read Modern C++ Design: Generic Programming and
Design
> Patterns Applied by Andrei Alexandrescu, you should get a copy.  A great book!  I have already applied many of the concepts he covers.  It should
be
> required reading for anyone who wants in depth understand of Generic Programming.
>
> I have so many ideas and could write forever about generics, here's just some food for thought.  If you're interested, I would be glad to share
more
> ideas.
>
> I will just give you a few insights of where you can improve on C++.
First,
> we generic programmers need a compile-time typeof operator.  I have run
into
> so many cases where I said to myself, "I sure wish I had a typeof
operator."
> It would make generic programming so much more elegant.  Then you could
have
> compile-time conditionals to handle different types in different ways,
like
> this:
>
> cswitch(typeof(variable))
> {
>    case int:  // handle an integer
>    case string: // hangle a string
>    ...
> }
>
> Here "cswitch" is a compile-time conditional.  This means the conditional
is
> resolved at compile time, and optimized appropriately so that no
performance
> is lost and dead code is eliminated.  You could also have cif, celse, etc.
>
> Another idea I have to improve on C++ is type specialization syntax.  We could implement type specialization more explicitly using typelists.  This would provide a more readable type specialization that (I think) would be easier to implement.
>
> Here's a simple example:
>
> template <typename T : {int, uint, long, ulong, float, double}>
> T Add(T a, T b)
> {
>    return a + b;
> }
>
> This specializes the Add function to need apply only to int, float,
double,
> and extended.  You could then write another Add template that would handle concatenation of container types.
>
> This leads me to another feature that would be nice to have: type lists
(see
> chapter 3 of Modern C++ design.)  It would be nice to categorize types something like this:
>
> typelist NumericTypes { int, uint, long, ulong, float, double }; typelist ContainerTypes { list, set, vector, queue, stack };
>
> Then you could rewrite the Add function:
>
> template <typename T : NumericTypes>
> T Add(T a, T b)
> {
>    return a + b;
> }
>
> template <typename T : ContainerTypes>
> T Add(T a, T b)
> {
>    T result;
>    result.append(a);
>    result.append(b);
>    return result;
> }
>
> Like I said, I have many other ideas, including making generic programming even more generic to reduce code duplication and improve maintainabiliity.
>
> Let me know what you think.
>
> Craig
>
>
>
>

Craig Black wrote:
> I will just give you a few insights of where you can improve on C++.  First,
> we generic programmers need a compile-time typeof operator.  I have run into
> so many cases where I said to myself, "I sure wish I had a typeof operator."
> It would make generic programming so much more elegant.  Then you could have
> compile-time conditionals to handle different types in different ways, like
> this:
> 
> cswitch(typeof(variable))
> {
>    case int:  // handle an integer
>    case string: // hangle a string
>    ...
> }

Good idea, but the new statements aren't necessary.  Just having the clauses in the language that:

a) Dead code and blocks made inaccessible through constant folding must not be compiled.

b) Trivial constant folding must be performed.

Is enough to do the same.  Then the above code becomes:

    switch(variable.typeinfo)
    {
        case int:
        case char[]:
    }

These additions aren't difficult to comply with and have value elsewhere.

> Then you could rewrite the Add function:
> 
> template <typename T : NumericTypes>
> T Add(T a, T b)
> {
>    return a + b;
> }
> 
> template <typename T : ContainerTypes>
> T Add(T a, T b)
> {
>    T result;
>    result.append(a);
>    result.append(b);
>    return result;
> }

That could easily become, using my generics methodology:

    $T Add ($T a, $T b)
    {
        if ($T.has_field ("length"))
            return a ~ b;
        else
            return a + b;
    }

So I think you introduced a good idea - cswitch/cif/celse - and then didn't use it right when it would work great.  Can you produce an example of code where typelist is necessary?

LX/XL has an interesting solution to the problem that automatically handles new types.  The generic type for a min and max function is:

generic type ordered if
   with ordered A, B
   with boolean Test := A < B

So a type is ordered if it can handle (A < B) and return a boolean. Whether this is just a mind-blower or of actual value is hard to say at this point.  Smalltalk has also been tossed around here on occasion, but I don't think anyone's described it and I can't google any information about it.

"Burton Radons" <loth@users.sourceforge.net> wrote in message news:3D17D5CE.3040608@users.sourceforge.net...
> Craig Black wrote:
> > I will just give you a few insights of where you can improve on C++.
First,
> > we generic programmers need a compile-time typeof operator.  I have run
into
> > so many cases where I said to myself, "I sure wish I had a typeof
operator."
> > It would make generic programming so much more elegant.  Then you could
have
> > compile-time conditionals to handle different types in different ways,
like
> > this:
> >
> > cswitch(typeof(variable))
> > {
> >    case int:  // handle an integer
> >    case string: // hangle a string
> >    ...
> > }
>
> Good idea, but the new statements aren't necessary.  Just having the clauses in the language that:
>
> a) Dead code and blocks made inaccessible through constant folding must not be compiled.
>
> b) Trivial constant folding must be performed.

Good points.  It would just be nice to force the compiler to resolve the conditional at compile time, and give you an error message if it can't so that you know for sure whether the optimization is performed.  Perhaps the compile-time conditionals are unnecessary, but if it a construct that is easily added to a language, it would ease my conscience to use them in performance-critical situations.

Just a thought: the concept of compile-time conditionals could be extended to looping constructs (cfor, cwhile, etc) to force the unrolling of loops. This idea almost causes me to drool on myself.

> Is enough to do the same.  Then the above code becomes:
>
>      switch(variable.typeinfo)
>      {
>          case int:
>          case char[]:
>      }
>
> These additions aren't difficult to comply with and have value elsewhere.
>
> > Then you could rewrite the Add function:
> >
> > template <typename T : NumericTypes>
> > T Add(T a, T b)
> > {
> >    return a + b;
> > }
> >
> > template <typename T : ContainerTypes>
> > T Add(T a, T b)
> > {
> >    T result;
> >    result.append(a);
> >    result.append(b);
> >    return result;
> > }
>
> That could easily become, using my generics methodology:
>
>      $T Add ($T a, $T b)
>      {
>          if ($T.has_field ("length"))
>              return a ~ b;
>          else
>              return a + b;
>      }
>

I like this syntax.  A quick question, as I am paranoid about performance, is the $T.has_field("length") resolved at compile time?  I am assuming that "length" here is a static member variable.  After all, we do not want to have to add a member variable every time we want to classify an attribute of a class.

Another question, this looks to me like reflection, introspection, whatever you want to call it.  In D, will this information be available at both run-time and compile-time?  I can see applications for compile-time reflection and run-time reflection.  Is there also an API to get a container of member methods, or a container member variables?  An is_class() method? is_basic_type() method?  If this API is in existence, and can be resolved at compile-time, then perhaps this is just the solution I have been looking for to solve all my generic programming problems.

> So I think you introduced a good idea - cswitch/cif/celse - and then didn't use it right when it would work great.  Can you produce an example of code where typelist is necessary?

All my examples (that I can think of right now) would be a result of the problems introduced with C++ generics.  As mentioned previously, type lists would provide a more flexible and better solution for the ugly C++ specialization syntax, and C++ type traits.  But as you have proposed above, perhaps compile-time reflection would be an even better solution.

> LX/XL has an interesting solution to the problem that automatically handles new types.  The generic type for a min and max function is:
>
> generic type ordered if
>     with ordered A, B
>     with boolean Test := A < B
>
> So a type is ordered if it can handle (A < B) and return a boolean. Whether this is just a mind-blower or of actual value is hard to say at this point.

I remember reading about LX one time.  This guy is trying to unify every programming paradigm in existence into one language.  An immense task.  He certainly has some creative and original ideas.  Unfortunately, even if he is successful, his language probably won't be widely adopted because the syntax is not close enough to C++, Java style syntax.

> Smalltalk has also been tossed around here on occasion, but
> I don't think anyone's described it and I can't google any information
> about it.

Sorry, I don't know anything about Smalltalk, so I can't comment.

Sounds to me like you are totally on the right track here.  Perhaps compile-time reflection will more elegantly resolve many current issues in regard to generics.  I guess my main concern is how well the compiler is able to resolve things at compile-time.  This is what makes C++ templates so powerful.  More concise, maintainable source code with absolutely no run-time overhead, because the compiler does all the work.

Are you involved with the D compiler development?  If you are, this gives me more confidence in D.  Do you have specs for your implementation of generics?

I think tommorrow I may post another idea and if you want you can critique it for me.

Regards,

Craig

"Burton Radons" <loth@users.sourceforge.net> wrote in message news:3D17D5CE.3040608@users.sourceforge.net...
> Craig Black wrote:
> > Then you could rewrite the Add function:
> >
> > template <typename T : NumericTypes>
> > T Add(T a, T b)
> > {
> >    return a + b;
> > }
> >
> > template <typename T : ContainerTypes>
> > T Add(T a, T b)
> > {
> >    T result;
> >    result.append(a);
> >    result.append(b);
> >    return result;
> > }
>
> That could easily become, using my generics methodology:
>
>      $T Add ($T a, $T b)
>      {
>          if ($T.has_field ("length"))
>              return a ~ b;
>          else
>              return a + b;
>      }
>
> So I think you introduced a good idea - cswitch/cif/celse - and then didn't use it right when it would work great.  Can you produce an example of code where typelist is necessary?
>

Imagine that Add for numerical and Add for containers are placed in different libraries and written by different authors. Then there is no way to unite then into one function you showed.

Another example for using typelists is to restrict using template with some
types.
Of course, without using typelists you should get plenty of compiler errors
when attempting to instantiate template for wrong type/class. Sometimes you
can hardly understand what happenings.

But I would like to have only one error: "type '...' is not suitable for template '..'".

Nic Tiger.

You'll have to wait a few days for Walters return.

He informs us that he is working on templates at this very moment.  Well probably only in his subconscious at present because he's on holidays. We'll probably have to wait and see what he comes up with.  I'd be a good idea to get any good ideas into the design though.

Burton Radons <loth@users.sourceforge.net> wrote in news:3D17D5CE.3040608@users.sourceforge.net:

> That could easily become, using my generics methodology:
> 
>      $T Add ($T a, $T b)
>      {
>          if ($T.has_field ("length"))
>              return a ~ b;
>          else
>              return a + b;
>      }

I generally like this form of generics. It works well for
generic fuctions but what about generic types?  A tree
of int or char[]?

I have a rather crazy idea.  What if we treated "type" as a type?

type IntType = int;

IntType b = 3;

One of the things you could do with this is create functions that dealt with types.  Here is a function that builds a binary tree type.

type BinaryTree(type T)
{
  struct Tree
  {
    T data;
    Tree left;
    Tree right;
  };

  return Tree;
}

Another idea I have is that design by contract can be extended to deal type in generics.

void Func($T a)
in
{
  // Make sure $T has a cmp function with the
  // correct signature
  assert($T.cmp && $T.cmp.type == (int (*)($T,$T)));
}
body
{
  //...
}

This could help with some of the really bad error messages you see with C++ templates.

> 
> Smalltalk has also been tossed around here on
> occasion, but I don't think anyone's described it and I can't google
> any information about it.

There are more that one type of generic.  Generic types.  Generic
functions. Generic algorthms.  Smalltalk and Ruby are
good languages to look at for how they do generic algorthms.

Here is what I think people need to look at when doing
generics.  Take a look at the C++ STL.  It is a good idea
with a poor implementaion due to the the way C++ does
templates.  How can you do the same sorts of things in
a way that is more understandable and easier to deal with?

"Patrick Down" <pat@codemoon.com> wrote in message news:Xns92385BBDDAE20patcodemooncom@63.105.9.61...
> Burton Radons <loth@users.sourceforge.net> wrote in news:3D17D5CE.3040608@users.sourceforge.net:
>
> > That could easily become, using my generics methodology:
> >
> >      $T Add ($T a, $T b)
> >      {
> >          if ($T.has_field ("length"))
> >              return a ~ b;
> >          else
> >              return a + b;
> >      }
>
> I generally like this form of generics. It works well for
> generic fuctions but what about generic types?  A tree
> of int or char[]?
>
> I have a rather crazy idea.  What if we treated "type" as a type?
>
> type IntType = int;

Isn't this very similar to typedef or alias?

> IntType b = 3;
>
> One of the things you could do with this is create functions that dealt with types.  Here is a function that builds a binary tree type.
>
> type BinaryTree(type T)
> {
>   struct Tree
>   {
>     T data;
>     Tree left;
>     Tree right;
>   };
>
>   return Tree;
> }

Things that make you go "Hmmm.....".

Fundamentally type generics use "parametric types".  You propose to introduce type syntax just as if it were a fundamental type.  I'm not trying to shoot down this idea, but is there any reason do this?  What then is the difference between the above and a template like this:

struct Tree<$T>
{
    $T data;
    Tree left;
    Tree right;
};

> Another idea I have is that design by contract can be extended to deal type in generics.
>
> void Func($T a)
> in
> {
>   // Make sure $T has a cmp function with the
>   // correct signature
>   assert($T.cmp && $T.cmp.type == (int (*)($T,$T)));
> }
> body
> {
>   //...
> }

That's a good idea.  This would be a compile-time assertion.  Perhaps we could have a "cassert" to denote this.

> This could help with some of the really bad error messages you see with C++ templates.
>
> >
> > Smalltalk has also been tossed around here on
> > occasion, but I don't think anyone's described it and I can't google
> > any information about it.
>
> There are more that one type of generic.  Generic types.  Generic
> functions. Generic algorthms.  Smalltalk and Ruby are
> good languages to look at for how they do generic algorthms.
>
> Here is what I think people need to look at when doing
> generics.  Take a look at the C++ STL.  It is a good idea
> with a poor implementaion due to the the way C++ does
> templates.  How can you do the same sorts of things in
> a way that is more understandable and easier to deal with?

Yes STL is good.  How can we achieve the same functionality and performance with more understandable syntax and less code?  More readability and greater genericity.

"Craig Black" <cblack@ara.com> wrote in news:afa0ae$pm0$1@digitaldaemon.com:

> "Patrick Down" <pat@codemoon.com> wrote in message news:Xns92385BBDDAE20patcodemooncom@63.105.9.61...
>> Burton Radons <loth@users.sourceforge.net> wrote in news:3D17D5CE.3040608@users.sourceforge.net:
>>
>> > That could easily become, using my generics methodology:
>> >
>> >      $T Add ($T a, $T b)
>> >      {
>> >          if ($T.has_field ("length"))
>> >              return a ~ b;
>> >          else
>> >              return a + b;
>> >      }
>>
>> I generally like this form of generics. It works well for
>> generic fuctions but what about generic types?  A tree
>> of int or char[]?
>>
>> I have a rather crazy idea.  What if we treated "type" as a type?
>>
>> type IntType = int;
> 
> Isn't this very similar to typedef or alias?

Yes it is.  But it's not all that weard C++ was forced to create a similar concept.

template<class T> class X {
  typename T::Y;    // treat Y as a type

  Y m_y;
};


> 
> Fundamentally type generics use "parametric types".  You propose to introduce type syntax just as if it were a fundamental type.  I'm not trying to shoot down this idea, but is there any reason do this?

Conditional data structure building, although I can't think of a good example right now.  So I'll give a really bogas one.

type BinaryTree(type T)
{
  if(T == int)
  {
    struct Tree
    {
      T data;
      Tree left;
      Tree right;
    }

    return Tree;
  }
  else
  {
    struct Tree
    {
      T data;
      int  key;
      Tree left;
      Tree right;
    }

    return Tree;
  }
}


> Yes STL is good.  How can we achieve the same functionality and performance with more understandable syntax and less code?  More readability and greater genericity.

Yes, with some care.  One of the problems I think C++ templates has
is that they use the same syntax to try to solve a a bunch of unrelated
problems.

> Yes, with some care.  One of the problems I think C++ templates has
> is that they use the same syntax to try to solve a a bunch of unrelated
> problems.

Sorry that was't very clear.  I mean that C++ uses the template syntax where other solutions might be more appropriate.