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:
--0015174c14427403fc04849b455a
Content-Type: text/plain; charset=ISO-8859-1

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 --0015174c14427403fc04849b455a Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Mon, Apr 19, 2010 at 20:16, Ellery Newcomer <= span dir=3D"ltr">&lt;<a href=3D"mailto:ellery-newcomer utulsa.edu">ellery-n= ewcomer utulsa.edu</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quot= e" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204,= 204); padding-left: 1ex;"> Hello.<br> <br> Say I have a [struct] template T, which takes a param S.<br> <br> 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 l= ist. Is there any good way to express the type for this?<br> </blockquote></div><br>So, you have<br><br>struct S(T) {}<br><br>and W!(S!T= )) is true, whatever T is. Right?<br><br>S!T is a type by itself, different= from S!U, S!V, ... So I&#39;m afraid there is no direct way to store them = in an array. S by itself is not a type nor a struct, it&#39;s code waiting = to be instantiated.<br> <br>Maybe you could use Variant to hide the inner type away, and do an arra= y of S!Variant. But then, there is no easy way to get back the type inside = the variant.<br><br>Another solution is to use a TypeTuple or a Tuple:<br> <br>import std.traits;<br>struct SList(Ss...) if (allSatisfy!(W, Ss))<br>{<= br>=A0=A0=A0 Ss theList;<br>}<br><br>I&#39;m using W as a predicate here.<b= r><br>Philippe<br><br> --0015174c14427403fc04849b455a--
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 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 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 languages like C# and Java with a full runtime reflection capabilities.
 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 "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
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:
--00151747927a2bc92604849d3212
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

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. --00151747927a2bc92604849d3212 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Mon, Apr 19, 2010 at 21:52, Ali =C7eh= reli <span dir=3D"ltr">&lt;<a href=3D"mailto:acehreli yahoo.com">acehreli y= ahoo.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); p= adding-left: 1ex;"> <div class=3D"im">Ellery Newcomer wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> I want to be able to store heterogeneous T!(S) in a single list<br> </blockquote> <br></div> std.boxer or std.variant may be useful:<br> <br> =A0<a href=3D"http://digitalmars.com/d/2.0/phobos/std_boxer.html" target= =3D"_blank">http://digitalmars.com/d/2.0/phobos/std_boxer.html</a><br> <br> =A0<a href=3D"http://digitalmars.com/d/2.0/phobos/std_variant.html" target= =3D"_blank">http://digitalmars.com/d/2.0/phobos/std_variant.html</a><br><fo= nt color=3D"#888888"> <br> Ali<br> </font></blockquote></div><br>But how do you get back what was stored insid= e a Variant without any indication as to what it was initially? <br>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. <br> <br>I also regularly want to use it to store _one_ thing, anything, to get = it back later. But then I&#39;m at a loss as to how crack open the Variant = afterwards, without storing some sort of type information somewhere.<br> <br> --00151747927a2bc92604849d3212--
Apr 19 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--00151747927a466d9204849d24ca
Content-Type: text/plain; charset=ISO-8859-1

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.


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 --00151747927a466d9204849d24ca Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Mon, Apr 19, 2010 at 21:20, Steven Schveighof= fer <span dir=3D"ltr">&lt;<a href=3D"mailto:schveiguy yahoo.com">schveiguy = yahoo.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); p= adding-left: 1ex;"> <div class=3D"im"><br><blockquote class=3D"gmail_quote" style=3D"margin: 0p= t 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1= ex;"> Here is a quick-and-dirty solution, if you don&#39;t mind using classes/int= erfaces.=A0 <br></blockquote></div></blockquote><div>(snip)<br><br>I&#39;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&= #39;re lost?<br> <br> 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), c= ast them to IW and... what? erase the types?<br><br><br> Philippe<br><br>=A0</div></div><br> --00151747927a466d9204849d24ca--
Apr 19 2010
prev sibling next sibling parent "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.


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
prev sibling next 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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0015175885f6a6dc460484a4ce80
Content-Type: text/plain; charset=ISO-8859-1

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? --0015175885f6a6dc460484a4ce80 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Mon, Apr 19, 2010 at 22:58, Steven Sc= hveighoffer <span dir=3D"ltr">&lt;<a href=3D"mailto:schveiguy yahoo.com">sc= hveiguy yahoo.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote= " style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, = 204); padding-left: 1ex;"> <br><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; b= order-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D= "im"> I&#39;m not used to using interfaces in this way. What become the stored T<= br> values when you cast the classes into IW to construct your array? I suppose= <br> they&#39;re lost?<br> </div></blockquote><br> <br> Not sure what you mean...<br></blockquote><div><br>What if the class has so= me value in it? In your code:<br><br>class WByVal(T) if (implementsW!T)<br> {<br> =A0 this(T val) {this._t =3D val;}<br> =A0 private T _t;<br> =A0 int foo(int x)<br> =A0 {<br> =A0 =A0 =A0return _t.foo(x);<br> =A0 }<br> }<br> <br>What happens to _t when I cast a WByVal to a IW?<br></div></div> --0015175885f6a6dc460484a4ce80--
Apr 19 2010
prev sibling 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