www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Forward referencing templates..

reply James Dean Palmer <james tiger3k.com> writes:
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!
Oct 25 2006
next sibling parent reply Bradley Smith <user domain.invalid> writes:
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
Oct 25 2006
next sibling parent reply Sean Kelly <sean f4.ca> writes:
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
Oct 25 2006
parent James Dean Palmer <james tiger3k.com> writes:
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
Oct 26 2006
prev sibling parent reply James Dean Palmer <james tiger3k.com> writes:
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
Oct 26 2006
parent reply Bradley Smith <user domain.invalid> writes:
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;
Oct 26 2006
parent reply James Dean Palmer <james tiger3k.com> writes:
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.  :-)
Oct 26 2006
parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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)'
)
Oct 26 2006
prev sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
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
Oct 29 2006