View mode: basic / threaded / horizontal-split · Log in · Help
October 25, 2006
Forward referencing templates..
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!
October 25, 2006
Re: Forward referencing templates..
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
October 25, 2006
Re: Forward referencing templates..
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
October 26, 2006
Re: Forward referencing templates..
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
October 26, 2006
Re: Forward referencing templates..
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
October 26, 2006
Re: Forward referencing templates..
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;
October 26, 2006
Re: Forward referencing templates..
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.  :-)
October 26, 2006
Re: Forward referencing templates..
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)'
)
October 30, 2006
Re: Forward referencing templates..
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
Top | Discussion index | About this forum | D home