www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - templates

reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
Hello.

Say I have a [struct] template T, which takes a param S.

Any T!(S) satisfies a certain template constraint W, so I can use any 
T!(S) the same way. I want to be able to store heterogeneous T!(S) in a 
single list. Is there any good way to express the type for this?
Apr 19 2010
next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Apr 19, 2010 at 20:16, Ellery Newcomer
<ellery-newcomer utulsa.edu>wrote:


 Hello.

 Say I have a [struct] template T, which takes a param S.

 Any T!(S) satisfies a certain template constraint W, so I can use any T!(S)
 the same way. I want to be able to store heterogeneous T!(S) in a single
 list. Is there any good way to express the type for this?


So, you have

struct S(T) {}

and W!(S!T)) is true, whatever T is. Right?

S!T is a type by itself, different from S!U, S!V, ... So I'm afraid there is
no direct way to store them in an array. S by itself is not a type nor a
struct, it's code waiting to be instantiated.

Maybe you could use Variant to hide the inner type away, and do an array of
S!Variant. But then, there is no easy way to get back the type inside the
variant.

Another solution is to use a TypeTuple or a Tuple:

import std.traits;
struct SList(Ss...) if (allSatisfy!(W, Ss))
{
    Ss theList;
}

I'm using W as a predicate here.

Philippe
Apr 19 2010
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Ellery Newcomer:


 Say I have a [struct] template T, which takes a param S.
 
 Any T!(S) satisfies a certain template constraint W, so I can use any 
 T!(S) the same way. I want to be able to store heterogeneous T!(S) in a 
 single list. Is there any good way to express the type for this?


In D the templates with their arguments create a Nominative type system, so
they are all seen as distinct types:
http://en.wikipedia.org/wiki/Nominative_type_system

So in D the standard, simpler and safer way to create a (flat) hierarchy of
things that can be mixed in a container is to use the same strategy you use in
Java, to create a base class/interface/abstract class, create a container of
such base thing, and then populate it.

If you don't want objects, and you want templated structs, then you have to
work more, and your code will probably be less safe. In your situation you can
create a common struct, it can contain several common fields, or just a tag,
this is the minimal:

enum FooTags { Tag1, Tag2, ... }

struct BaseFoo {
    FooTags tag;
    // few common attributes
    // few common methods
}

(That BaseFoo can also be a template mixin, then you can mix in this template
at the top of all your derived structs.)

struct Foo1 {
    FooTags tag = FooTags.Tag1;
    ...
}

Then you have to read the tag and cast the pointer to the pointer of the
correct type, in a switch if necessary...
If your structs are allocated from the C heap, and you have only up to 8 or 16
different structs, you can even use a tagged pointer, but you also need an
aligned malloc wrapper. This saves the 1 or or 2 or 4 bytes for the tag.

Bye,
bearophile
Apr 19 2010
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 Apr 2010 14:16:03 -0400, Ellery Newcomer  
<ellery-newcomer utulsa.edu> wrote:


 Hello.

 Say I have a [struct] template T, which takes a param S.

 Any T!(S) satisfies a certain template constraint W, so I can use any  
 T!(S) the same way. I want to be able to store heterogeneous T!(S) in a  
 single list. Is there any good way to express the type for this?


What you are looking for is a conversion from compile-time interface to  
runtime interface.  The only drawback is, you can't go backwards (from a  
runtime interface to a compile-time).

This can be possible in runtime reflection systems, but the theory is that  
RTTI can be built from compile-time type info.

Here is a quick-and-dirty solution, if you don't mind using  
classes/interfaces.  You are going to need some sort of runtime interface  
in order to get this to work, classes/interfaces are not the leanest way  
to do this, but it should get the job done:

The S is an extra complication that can be factored out, so let's forget  
about S for now.  Let's assume W defines a single function int foo(int).   
Let's make a W interface:

interface IW
{
    int foo(int);
}

Now, we can define a class template to hold your values:

class WByVal(T) if (implementsW!T)
{
    this(T val) {this._t = val;}
    private T _t;
    int foo(int x)
    {
       return _t.foo(x);
    }
}

Maybe a helper function

WByVal!(T) makeW(T)(T _t)
{
    return new WByVal!(T)(_t);
}

Now you can easily convert a T to a IW with makeW, and by definition, any  
IW implements the W functions, so it can be used in anything that accepts  
W by constraint.  So you can now form lists/arrays of IW objects to be  
used as needed.

One other possibility is to use a union, but I think Variant might be  
better at that point.

-Steve
Apr 19 2010
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 Apr 2010 15:16:46 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 On Mon, 19 Apr 2010 14:16:03 -0400, Ellery Newcomer  
 <ellery-newcomer utulsa.edu> wrote:


 Hello.

 Say I have a [struct] template T, which takes a param S.

 Any T!(S) satisfies a certain template constraint W, so I can use any  
 T!(S) the same way. I want to be able to store heterogeneous T!(S) in a  
 single list. Is there any good way to express the type for this?


 What you are looking for is a conversion from compile-time interface to  
 runtime interface.  The only drawback is, you can't go backwards (from a  
 runtime interface to a compile-time).

 This can be possible in runtime reflection systems, but the theory is  
 that RTTI can be built from compile-time type info.

 Here is a quick-and-dirty solution, if you don't mind using  
 classes/interfaces.  You are going to need some sort of runtime  
 interface in order to get this to work, classes/interfaces are not the  
 leanest way to do this, but it should get the job done:

 The S is an extra complication that can be factored out, so let's forget  
 about S for now.  Let's assume W defines a single function int  
 foo(int).  Let's make a W interface:

 interface IW
 {
     int foo(int);
 }

 Now, we can define a class template to hold your values:

 class WByVal(T) if (implementsW!T)


Whoops!  Forgot the interface!

class WByVal(T) : IW if (implementsW!T)

-Steve
Apr 19 2010
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Apr 19, 2010 at 21:20, Steven Schveighoffer <schveiguy yahoo.com>wrote:


 Here is a quick-and-dirty solution, if you don't mind using

 classes/interfaces.


 (snip)


I'm not used to using interfaces in this way. What become the stored T
values when you cast the classes into IW to construct your array? I suppose
they're lost?

Does that mean that if we have a bunch of T (all different types),you map a
call to makeW on it, get back a bunch of WByVal!T (all different types),
cast them to IW and... what? erase the types?


Philippe
Apr 19 2010
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 Apr 2010 16:52:40 -0400, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:


 On Mon, Apr 19, 2010 at 21:20, Steven Schveighoffer  
 <schveiguy yahoo.com>wrote:


 Here is a quick-and-dirty solution, if you don't mind using

 classes/interfaces.


 (snip)


 I'm not used to using interfaces in this way. What become the stored T
 values when you cast the classes into IW to construct your array? I  
 suppose
 they're lost?


Not sure what you mean...


 Does that mean that if we have a bunch of T (all different types),you  
 map a
 call to makeW on it, get back a bunch of WByVal!T (all different types),
 cast them to IW and... what? erase the types?


What I had in mind was:

struct S
{
   int foo(int x) { return x * 2; }
}

struct S2
{
   int foo(int x) { return x + 2; }
}

void main()
{
    S s1;
    S2 s2;

    IW[] ws;

    ws ~= makeW(s1);
    ws ~= makeW(s2);

    assert(ws[0].foo(3) == 6);
    assert(ws[1].foo(3) == 5);
}

does this help?

-Steve
Apr 19 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Steven Schveighoffer:


 What I had in mind was:
 
 struct S
 {
    int foo(int x) { return x * 2; }
 }
 
 struct S2
 {
    int foo(int x) { return x + 2; }
 }
 
 void main()
 {
     S s1;
     S2 s2;
 
     IW[] ws;
 
     ws ~= makeW(s1);
     ws ~= makeW(s2);
 
     assert(ws[0].foo(3) == 6);
     assert(ws[1].foo(3) == 5);
 }
 
 does this help?


A possible solution, this code is just an idea that needs improvements, it's
not generic:

struct S1 {
   int foo(int x) { return x * 2; }
}

struct S2 {
   int foo(int x) { return x + 2; }
}

enum TypeTag { TS1, TS2 }

struct Wrapper {
    TypeTag tag;

    union {
        S1 s1;
        S2 s2;
    }

    int foo(int x) {
        final switch(this.tag) {
            case TypeTag.TS1: return s1.foo(x);
            case TypeTag.TS2: return s2.foo(x);
       }
    }
}

Wrapper makeW(T)(T s) if (is(T == S1) || is(T == S2)) {
    static if (is(T == S1)) {
        Wrapper result = Wrapper(TypeTag.TS1);
        result.s1 = s;
        return result;
    } else static if (is(T == S2)) {
        Wrapper result = Wrapper(TypeTag.TS2);
        result.s2 = s;
        return result;
    } else
        assert(0);
}

void main() {
    S1 s1;
    S2 s2;

    Wrapper[] ws;
    ws ~= makeW(s1);
    ws ~= makeW(s2);

    assert(ws[0].foo(3) == 6);
    assert(ws[1].foo(3) == 5);
}


There are several other ways to solve this problem. This version is a bit nicer
because it contains no pointer casts.
Languages that have a tagged union (like Cyclone) need quite less code here,
but probably D2 can be used to remove some of that code duplication.

Bye,
bearophile
Apr 19 2010
parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
Won't the union balloon Wrapper's size to always be that of the largest 
inner struct that you use?
Apr 19 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Ellery Newcomer:


 Won't the union balloon Wrapper's size to always be that of the largest 
 inner struct that you use?


Yes, all items in an array must have the same size. If you want items of
different size you have to add a level of indirection, storing inside the array
pointers to the structs. Then your structs can be of different size, and you
need pointer casts, as I have written in another post.

Bye,
bearophile
Apr 19 2010
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Ellery Newcomer:


 Won't the union balloon Wrapper's size to always be that of the largest 
 inner struct that you use?


Beside using the array of struct-enums, or using an array of pointers I've
explained in the other answer, there are other solutions, but they are even
more complex, there are ways to create variable-sized items inside the "array"
that becomes more like a memory arena for the structs.

Then you need ways to find your structs inside this array, there are many ways
to do this, with various compromises between memory used and retrieval
performance.

The minimum extra memory comes from scanning this arena linearly, because the
tags tell you how much big each struct is, this has O(n) search. The max extra
memory comes storing a second array of starting pointers that give you O(1)
search. An intermediate solution is for example to add a skip list inside the
array, with O(ln n) both in extra space and access time, etc.

But in most situations all this work is not necessary, unless you are in needs
of space and performance are very demanding...

Bye,
bearophile
Apr 19 2010
prev sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Apr 19, 2010 at 22:58, Steven Schveighoffer <schveiguy yahoo.com>wrote:


 I'm not used to using interfaces in this way. What become the stored T

 values when you cast the classes into IW to construct your array? I
 suppose
 they're lost?



 Not sure what you mean...


What if the class has some value in it? In your code:

class WByVal(T) if (implementsW!T)
{
  this(T val) {this._t = val;}
  private T _t;
  int foo(int x)
  {
     return _t.foo(x);
  }
}

What happens to _t when I cast a WByVal to a IW?
Apr 19 2010
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 20 Apr 2010 02:01:23 -0400, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:


 On Mon, Apr 19, 2010 at 22:58, Steven Schveighoffer  
 <schveiguy yahoo.com>wrote:


 I'm not used to using interfaces in this way. What become the stored T

 values when you cast the classes into IW to construct your array? I
 suppose
 they're lost?



 Not sure what you mean...


 What if the class has some value in it? In your code:

 class WByVal(T) if (implementsW!T)
 {
   this(T val) {this._t = val;}
   private T _t;
   int foo(int x)
   {
      return _t.foo(x);
   }
 }

 What happens to _t when I cast a WByVal to a IW?


Nothing, it's still there.  Casting to an interface does nothing to the  
data.  An interface is simply an abstracted set of functions that can be  
used to access any object that implements that interface.

It's the same as casting to a base class.  Having a pointer to a base  
class, you don't have direct access to the data defined in the derived  
class, but the data is still there.

-Steve
Apr 20 2010
prev sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 04/19/2010 02:16 PM, Steven Schveighoffer wrote:

 What you are looking for is a conversion from compile-time interface to
 runtime interface. The only drawback is, you can't go backwards (from a
 runtime interface to a compile-time).


That hurts. The thing is, I'm eventually going to need to get that T 
back so I can access the non-common parts of it.

The T types already correspond to an enum, so the interface could look like

interface IW{
   Type type();
   int foo(int);
}

then whenever I want T, I can just test type and perform a cast.

Now I'm thinking of how to express that mapping in a centralized 
function or template or whatever, and I think I'm back where I started. 
Oh well. I'm probably going to have to write out each case longhand anyways.

It probably isn't important, but aren't dynamic casts rather expensive?
Apr 19 2010
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
Ellery Newcomer Wrote:


 On 04/19/2010 02:16 PM, Steven Schveighoffer wrote:

 What you are looking for is a conversion from compile-time interface to
 runtime interface. The only drawback is, you can't go backwards (from a
 runtime interface to a compile-time).


 
 That hurts. The thing is, I'm eventually going to need to get that T 
 back so I can access the non-common parts of it.


This is possible, via dynamic casting:

IW x;
if(auto wofT = cast(WByVal!T)x)
{
   wofT._t.specializedMethod(); // need to expose _t in the class definition
}

If you need to figure out what type the IW is, you can do a switch on the
classinfo.  However, bottom line is, when you want to access a compile-time
interface, you need to know about that type during compile time.  So for
instance if you add another type that can be wrapped by IW, you need to add
another case statement for that type.  Compile-time means the compiler has to
know about everything, so there is no abstraction, everything must be concrete.

RTTI can do some incredible things, and I hope D can join the ranks of



 The T types already correspond to an enum, so the interface could look like
 
 interface IW{
    Type type();
    int foo(int);
 }
 
 then whenever I want T, I can just test type and perform a cast.


You can get this info via the classinfo, it's already there.


 Now I'm thinking of how to express that mapping in a centralized 
 function or template or whatever, and I think I'm back where I started. 
 Oh well. I'm probably going to have to write out each case longhand anyways.


Yes, each case must be explicitly handled.  There is no generic way to do it! 
It is one of those things that seems like it should work, but if you ever try
to solve it, you realize why it doesn't ;)


 It probably isn't important, but aren't dynamic casts rather expensive?


I wouldn't call them rather expensive, dynamic casts aren't particularly cheap,
but they might be your only option.  I would cache any dynamic cast so you
aren't doing it over and over again.

If you want the absolute best speed, you will have to implement your own type
of "dynamic cast" instead of using D's class/interface system, similar to what
bearophile stated.

-Steve
Apr 19 2010
prev sibling next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
Ellery Newcomer wrote:

 I want to be able to store heterogeneous T!(S) in a 
 single list


std.boxer or std.variant may be useful:

   http://digitalmars.com/d/2.0/phobos/std_boxer.html

   http://digitalmars.com/d/2.0/phobos/std_variant.html

Ali
Apr 19 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Apr 19, 2010 at 21:52, Ali =C7ehreli <acehreli yahoo.com> wrote:


 Ellery Newcomer wrote:


 I want to be able to store heterogeneous T!(S) in a single list


 std.boxer or std.variant may be useful:

  http://digitalmars.com/d/2.0/phobos/std_boxer.html

  http://digitalmars.com/d/2.0/phobos/std_variant.html

 Ali


But how do you get back what was stored inside a Variant without any
indication as to what it was initially?
As far as I get it, Variant is useful to have a variable that can be
assigned with many other variables of different types during its lifetime.

I also regularly want to use it to store _one_ thing, anything, to get it
back later. But then I'm at a loss as to how crack open the Variant
afterwards, without storing some sort of type information somewhere.
Apr 19 2010
prev sibling parent reply BLS <windevguy hotmail.de> writes:
On 19/04/2010 20:16, Ellery Newcomer wrote:

 Hello.

 Say I have a [struct] template T, which takes a param S.

 Any T!(S) satisfies a certain template constraint W, so I can use any
 T!(S) the same way. I want to be able to store heterogeneous T!(S) in a
 single list. Is there any good way to express the type for this?


Why not simply...

class C(O)
{
   private O obj;
   object next;
   this(O obj)
   {
     this.obj = obj;
   }
   ...
   invariant()
   {
     assert(this.obj fulfills W);
   }
   ...
}
Apr 19 2010
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
BLS Wrote:


 On 19/04/2010 20:16, Ellery Newcomer wrote:

 Hello.

 Say I have a [struct] template T, which takes a param S.

 Any T!(S) satisfies a certain template constraint W, so I can use any
 T!(S) the same way. I want to be able to store heterogeneous T!(S) in a
 single list. Is there any good way to express the type for this?


 
 Why not simply...
 
 class C(O)
 {
    private O obj;
    object next;
    this(O obj)
    {
      this.obj = obj;
    }
    ...
    invariant()
    {
      assert(this.obj fulfills W);
    }
    ...
 }


W is a compile-time interface.  this.obj is Object, so at compile time all you
have are Object's methods.

So no, it can't simply be that.

-Steve
Apr 19 2010