I am interested in expressing some data structure relationships like the half-edge data structure using templates.  For example, consider these classes with these type dependencies:

class edge(TFace, TVector) {
 ...
}

class face(TSurface, TEdge) {
 ...
}

class surface(TFace) {
 ...
}

class vector(TNumeric) {
 ...
}

The idea being any one of these classes could be subclassed - for example to represent weighted edges, weighted faces, etc.. Or a different kind of basic numeric could be used. Now I would like to say this..

alias vector!(double) vector3D;
alias edge!(face3D, vector3D) edge3D;
alias face!(surface3D, edge3D) face3D;
alias surface!(face3D) surface3D;

But I get an error about a forward reference when trying to do it like this.  C++ has difficulty expressing the same kind of relationship because it doesn't forward reference templates.  I believe that Java can represent this kind of relationship though.

Does anyone know if this can't be done in D? Or is there a better "D" way to do it?  Thanks!

James Dean Palmer wrote:
> I am interested in expressing some data structure relationships like the half-edge data structure using templates.  For example, consider these classes with these type dependencies:
> 
> class edge(TFace, TVector) {
>  ...
> }
> 
> class face(TSurface, TEdge) {
>  ...
> }
> 
> class surface(TFace) {
>  ...
> }
> 
> class vector(TNumeric) {
>  ...
> }
> 
> The idea being any one of these classes could be subclassed - for example to represent weighted edges, weighted faces, etc.. Or a different kind of basic numeric could be used. Now I would like to say this..
> 
> alias vector!(double) vector3D;
> alias edge!(face3D, vector3D) edge3D;
> alias face!(surface3D, edge3D) face3D;
> alias surface!(face3D) surface3D;
> 
> But I get an error about a forward reference when trying to do it like this.  C++ has difficulty expressing the same kind of relationship because it doesn't forward reference templates.  I believe that Java can represent this kind of relationship though.
> 
> Does anyone know if this can't be done in D? Or is there a better "D" way to do it?  Thanks!


If you substitute surface3D into the alias for face3D, you get

alias face!(surface!(face3D), edge3D) face3D;

This shows that the alias for face3D is being defined by face3D. Isn't that an infinitely recursive definition?

How would you construct a similar relationship in Java?

  Bradley

Bradley Smith wrote:
> James Dean Palmer wrote:
>> I am interested in expressing some data structure relationships like the half-edge data structure using templates.  For example, consider these classes with these type dependencies:
>>
>> class edge(TFace, TVector) {
>>  ...
>> }
>>
>> class face(TSurface, TEdge) {
>>  ...
>> }
>>
>> class surface(TFace) {
>>  ...
>> }
>>
>> class vector(TNumeric) {
>>  ...
>> }
>>
>> The idea being any one of these classes could be subclassed - for example to represent weighted edges, weighted faces, etc.. Or a different kind of basic numeric could be used. Now I would like to say this..
>>
>> alias vector!(double) vector3D;
>> alias edge!(face3D, vector3D) edge3D;
>> alias face!(surface3D, edge3D) face3D;
>> alias surface!(face3D) surface3D;
>>
>> But I get an error about a forward reference when trying to do it like this.  C++ has difficulty expressing the same kind of relationship because it doesn't forward reference templates.  I believe that Java can represent this kind of relationship though.
>>
>> Does anyone know if this can't be done in D? Or is there a better "D" way to do it?  Thanks!
> 
> 
> If you substitute surface3D into the alias for face3D, you get
> 
> alias face!(surface!(face3D), edge3D) face3D;
> 
> This shows that the alias for face3D is being defined by face3D. Isn't that an infinitely recursive definition?
> 
> How would you construct a similar relationship in Java?

For what it's worth, Java generics have very little relation to D/C++ templates.  Java generics are basically just some compile-time type checking plus implicit cast operations from Object when reading generic values.  This stands in stark contract to templates which are a compile-time code generation tool.  If forward referencing is the only issue then D compiler changes should be able to address the problem, but if this is really a matter of a circular dependency I think the OP is out of luck.


Sean

Bradley Smith wrote:
> James Dean Palmer wrote:
>> I am interested in expressing some data structure relationships like the half-edge data structure using templates.  For example, consider these classes with these type dependencies:
>>
>> class edge(TFace, TVector) {
>>  ...
>> }
>>
>> class face(TSurface, TEdge) {
>>  ...
>> }
>>
>> class surface(TFace) {
>>  ...
>> }
>>
>> class vector(TNumeric) {
>>  ...
>> }
>>
>> The idea being any one of these classes could be subclassed - for example to represent weighted edges, weighted faces, etc.. Or a different kind of basic numeric could be used. Now I would like to say this..
>>
>> alias vector!(double) vector3D;
>> alias edge!(face3D, vector3D) edge3D;
>> alias face!(surface3D, edge3D) face3D;
>> alias surface!(face3D) surface3D;
>>
>> But I get an error about a forward reference when trying to do it like this.  C++ has difficulty expressing the same kind of relationship because it doesn't forward reference templates.  I believe that Java can represent this kind of relationship though.
>>
>> Does anyone know if this can't be done in D? Or is there a better "D" way to do it?  Thanks!
> 
> 
> If you substitute surface3D into the alias for face3D, you get
> 
> alias face!(surface!(face3D), edge3D) face3D;
> 
> This shows that the alias for face3D is being defined by face3D. Isn't that an infinitely recursive definition?

Sure, but remove the template aspect and consider the classes - we have no trouble representing classes with infinitely recursive relationships.  class Bob can point to an object of type Alice and Alice can point to an object of type Bob.  I'd like to be able to do the same thing with templatized classes.

> How would you construct a similar relationship in Java?

I gathered from this page that it seemed at least possible though I have not tested a construction:
http://www.angelikalanger.com/GenericsFAQ/FAQSections/TypeParameters.html

Sean Kelly wrote:
> For what it's worth, Java generics have very little relation to D/C++ templates.  Java generics are basically just some compile-time type checking plus implicit cast operations from Object when reading generic values.  This stands in stark contract to templates which are a compile-time code generation tool.  If forward referencing is the only issue then D compiler changes should be able to address the problem, but if this is really a matter of a circular dependency I think the OP is out of luck.

My gut feeling is it should be representable - somehow.  Whether this is a small issue with forward referencing or a larger issue specific to how D implements templates I have no idea.

James

James Dean Palmer wrote:

> Sure, but remove the template aspect and consider the classes - we have no trouble representing classes with infinitely recursive relationships.  class Bob can point to an object of type Alice and Alice can point to an object of type Bob.  I'd like to be able to do the same thing with templatized classes.

That would be like the following, which does compile.

class edge(TNumeric) {
  face!(TNumeric) f;
  vector!(TNumeric) v;
}

class face(TNumeric) {
  surface!(TNumeric) s;
  edge!(TNumeric) e;
}

class surface(TNumeric) {
  face!(TNumeric) f;
}

class vector(TNumeric) {
}

alias vector!(double) vector3D;
alias edge!(double) edge3D;
alias face!(double) face3D;
alias surface!(double) surface3D;

Bradley Smith wrote:
> James Dean Palmer wrote:
> 
>> Sure, but remove the template aspect and consider the classes - we have no trouble representing classes with infinitely recursive relationships.  class Bob can point to an object of type Alice and Alice can point to an object of type Bob.  I'd like to be able to do the same thing with templatized classes.
> 
> That would be like the following, which does compile.
> 
> ... snipped

Right, except I want Alice and Bob referenced when passed in as template parameters.  :-)

James Dean Palmer wrote:
> Bradley Smith wrote:
>> James Dean Palmer wrote:
>>
>>> Sure, but remove the template aspect and consider the classes - we have no trouble representing classes with infinitely recursive relationships.  class Bob can point to an object of type Alice and Alice can point to an object of type Bob.  I'd like to be able to do the same thing with templatized classes.
>>
>> That would be like the following, which does compile.
>>
>  > ... snipped
> 
> Right, except I want Alice and Bob referenced when passed in as template parameters.  :-)

D uses name mangling, and the mangled typenames of template parameters are included in the mangled name of the instantiated template type. Since if name A (strictly) includes name B and name B (strictly) includes name A then names A and B can't exist as finite strings, that makes it impossible to mangle A and B and thus to compile any code that uses them.

It could theoretically work if you use typedefs instead of aliases, since typedefs mangled names don't depend on the referenced type.
Currently also gives an error though:
test.d(19): typedef test.face3D circular definition

(the original code gives this error:
test.d(18): forward reference to 'face!(surface3D,edge3D)'
)

James Dean Palmer wrote:
> I am interested in expressing some data structure relationships like the half-edge data structure using templates.  For example, consider these classes with these type dependencies:
> 
> class edge(TFace, TVector) {
>  ...
> }
> 
> class face(TSurface, TEdge) {
>  ...
> }
> 
> class surface(TFace) {
>  ...
> }
> 
> class vector(TNumeric) {
>  ...
> }
> 
> The idea being any one of these classes could be subclassed - for example to represent weighted edges, weighted faces, etc.. Or a different kind of basic numeric could be used. Now I would like to say this..
> 
> alias vector!(double) vector3D;
> alias edge!(face3D, vector3D) edge3D;
> alias face!(surface3D, edge3D) face3D;
> alias surface!(face3D) surface3D;
> 
> But I get an error about a forward reference when trying to do it like this.  C++ has difficulty expressing the same kind of relationship because it doesn't forward reference templates.  I believe that Java can represent this kind of relationship though.
> 
> Does anyone know if this can't be done in D? Or is there a better "D" way to do it?  Thanks!

It's possible, but it's quite hackish. Probably too hackish to be worth it.To create the equivalent of this:

  class Foo(TYPE) { }
  alias Foo!(RecursiveFoo) RecursiveFoo;

One has to do this:
--------
import std.stdio;

template Foo_Wrapper(alias SELF_THUNK) {

	class Foo() {
		alias SELF_THUNK!() SELF;
		// SELF is now the current instance of Foo_Wrapper
		alias SELF.Foo!() TYPE;
		static assert(is(TYPE)); //Ensure entity TYPE is a type
		static assert(is(TYPE == Foo)); //Ensure it's the same
		void test() {
			writefln(typeid(Foo), " ", Foo.mangleof);
			writefln(typeid(TYPE), " ", TYPE.mangleof);
		}
	}
}

template RecursiveFooWrapper_thunk() {
	alias RecursiveFoo_Wrapper RecursiveFooWrapper_thunk;
}

// The recursive definition
alias Foo_Wrapper!(RecursiveFooWrapper_thunk) RecursiveFoo_Wrapper;

alias RecursiveFoo_Wrapper.Foo!() RecursiveFoo;

int main() {
	RecursiveFoo myfoo = new RecursiveFoo();
	myfoo.test();
	return 0;
}
--------

Basically to do this, two delayed-evaluation thunks (same as http://en.wikipedia.org/wiki/Lazy_evaluation) must be created. The first is RecursiveFooWrapper_thunk, to wrap/delay the recursive alias parameter. The second one is Foo itself, which is a template ( 'class Foo()' ) , because inside the immediate body of Foo_Wrapper one cannot create the instance SELF_THUNK!() , since it gives a recursive error too. So instead, SELF_THUNK is instanciated inside Foo, after Foo_Wrapper is successfully instanciated.


-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D