www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Recursive template expansion

reply Norbert Nemec <Norbert Nemec-online.de> writes:
Hi there,

trying out a few ideas on expression templates, I stumbled over the 
following problem, for which I cannot find a solution. The code below 
demonstrates what I try to do:

I need to construct a nested template type at compile time. Any 
expression should correspond to an equivalent nested tree of templates 
which can then be unraveled at compile time.

For some reason, the D compiler complains about a "recursive template 
expansion" as soon as I use ((a+b)+c). My guess is that this is supposed 
to protect against infinite recursions at compile time. In this case, 
however, there is actually no risk of that. Nested types are only needed 
at the depth of nested expressions that actually occur.

Is there any fundamental error in my thinking? Some simple 
misunderstanding? Some slightly different syntax to be used? Or is it 
simply an unnessessary restriction in the compiler that could easily be 
removed?

Apart from all that, I want to point out that the error message does not 
even give a line number in the code. If any such error occurs within a 
larger piece of software, identifying the problem would be a nightmare!

Greetings,
Norbert


---------------
import std.stdio;

struct sum(A,B) {
     A a;
     B b;

     auto opAdd(T)(T a) { return .sum!(sum,T)(this,a); }
}


struct base {
     auto opAdd(T)(T a) { return .sum!(base,T)(this,a); }
}

void main() {
     base a,b,c;

     // first a few working examples
     writeln(typeid(a));       // base
     writeln(typeid(a+b));     // sum!(base,base).sum
     writeln(typeid(a+(b+c))); // sum!(base,sum!(base,base)).sum

     sum!(sum!(base,base),base) d;
     writeln(typeid(d));       // sum!(sum!(base,base),base).sum

     // the following produces
     //   Error: recursive template expansion for
     //   template argument sum!(base,base)
     writeln(typeid((a+b)+c)); // sum!(sum!(base,base),base).sum
}

---------------
Mar 01 2010
next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Mar 1, 2010 at 10:16, Norbert Nemec <Norbert nemec-online.de> wrote:


 Is there any fundamental error in my thinking? Some simple
 misunderstanding? Some slightly different syntax to be used? Or is it simply
 an unnessessary restriction in the compiler that could easily be removed?


I don't know. Using factory functions, it seems to work and it has the nice
side-effect of simplfying the syntax (templated functions do all the type
deducing):

import std.stdio;

struct Sum(A,B) {
   A a;
   B b;

   auto opAdd(T)(T a) { return sum(this,a); }
}


struct Base {
   auto opAdd(T)(T a) { return sum(this,a); }
}

Sum!(A,B) sum(A,B)(A a, B b) { return Sum!(A,B)(a,b);}
Base!(A,B) base(A,B)(A a, B b) { return Base!(A,B)(a,b);}

void main() {
   Base a,b,c;

   auto d = a+b;
   writeln(typeof(e).stringof); // Sum!(Base, Base)
   auto e =de+a;
   writeln(typeof(f).stringof); // Sum!(Sum!(Base, Base),Base)
   auto f = e+e+d;              // Look Ma, no parenthesis
   writeln(typeof(g).stringof); // Sum!(Sum!(Sum!(Sum!(Base,Base),Base),
Sum!(Sum!(Base,Base),Base)),Sum!(Base,Base))
}


Cheers,

  Philippe
Mar 01 2010
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Thanks, Philippe, for the elegant workaround!

Still I would like to know the reason for my original failure, 
especially since the compiler error message did not contain any line 
number whatsoever. Getting this kind of error message in a large project 
must be really ugly to solve, even if the workaround is so 
straightforward...




Philippe Sigaud wrote:

 
 
 On Mon, Mar 1, 2010 at 10:16, Norbert Nemec <Norbert nemec-online.de 
 <mailto:Norbert nemec-online.de>> wrote:
 
 
     Is there any fundamental error in my thinking? Some simple
     misunderstanding? Some slightly different syntax to be used? Or is
     it simply an unnessessary restriction in the compiler that could
     easily be removed?
 
 
 I don't know. Using factory functions, it seems to work and it has the 
 nice side-effect of simplfying the syntax (templated functions do all 
 the type deducing):




 
 import std.stdio;
 
 struct Sum(A,B) {
    A a;
    B b;
 
    auto opAdd(T)(T a) { return sum(this,a); }
 }
 
 
 struct Base {
    auto opAdd(T)(T a) { return sum(this,a); }
 }
 
 Sum!(A,B) sum(A,B)(A a, B b) { return Sum!(A,B)(a,b);}
 Base!(A,B) base(A,B)(A a, B b) { return Base!(A,B)(a,b);}
 
 void main() {
    Base a,b,c;
 
    auto d = a+b;
    writeln(typeof(e).stringof); // Sum!(Base, Base)
    auto e =de+a;
    writeln(typeof(f).stringof); // Sum!(Sum!(Base, Base),Base)
    auto f = e+e+d;              // Look Ma, no parenthesis
    writeln(typeof(g).stringof); // Sum!(Sum!(Sum!(Sum!(Base,Base),Base), 
 Sum!(Sum!(Base,Base),Base)),Sum!(Base,Base))
 }
  
 
 Cheers,
 
   Philippe
Mar 01 2010
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Mar 1, 2010 at 17:26, Norbert Nemec <Norbert nemec-online.de> wrote:


 Thanks, Philippe, for the elegant workaround!


De nada. I vaguely remembered being confronted by this one, but didn't know
it was a bug (my code wasn't as clear as yours). I now realize that my
coding in D is a least partially made of such tricks.



 Still I would like to know the reason for my original failure, especially
 since the compiler error message did not contain any line number whatsoever.
 Getting this kind of error message in a large project must be really ugly to
 solve, even if the workaround is so straightforward...


What bugs (!) me is that a+(b+c) didn't create an error, whereas (a+b)+c
did... I first tried to define opAdd_r so that the compiler could try
c.opAdd_r((a+b)), but to no avail...

As for the line numbers, yes it's hard and it's reason enough to put this on
bugzilla. Maybe even as 2 different tickets.

I remember having other incomplete error messages some days ago. I should
strive to note them and put them on puremagic.

  Philippe
Mar 01 2010
parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 01 Mar 2010 12:47:49 -0500, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:
[snip]


 Still I would like to know the reason for my original failure,  
 especially
 since the compiler error message did not contain any line number  
 whatsoever.
 Getting this kind of error message in a large project must be really  
 ugly to
 solve, even if the workaround is so straightforward...


 What bugs (!) me is that a+(b+c) didn't create an error, whereas (a+b)+c
 did... I first tried to define opAdd_r so that the compiler could try
 c.opAdd_r((a+b)), but to no avail...


Well, it makes sense. a+(b+c) is base.op_Add(sum), which is okay. And  
opApp will always be tried before opAdd_r, and so DMD fails.
Mar 01 2010
prev sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 01 Mar 2010 04:16:41 -0500, Norbert Nemec  
<Norbert nemec-online.de> wrote:

 Hi there,

 trying out a few ideas on expression templates, I stumbled over the  
 following problem, for which I cannot find a solution. The code below  
 demonstrates what I try to do:

 I need to construct a nested template type at compile time. Any  
 expression should correspond to an equivalent nested tree of templates  
 which can then be unraveled at compile time.

 For some reason, the D compiler complains about a "recursive template  
 expansion" as soon as I use ((a+b)+c). My guess is that this is supposed  
 to protect against infinite recursions at compile time. In this case,  
 however, there is actually no risk of that. Nested types are only needed  
 at the depth of nested expressions that actually occur.

 Is there any fundamental error in my thinking? Some simple  
 misunderstanding? Some slightly different syntax to be used? Or is it  
 simply an unnessessary restriction in the compiler that could easily be  
 removed?

 Apart from all that, I want to point out that the error message does not  
 even give a line number in the code. If any such error occurs within a  
 larger piece of software, identifying the problem would be a nightmare!

 Greetings,
 Norbert


 ---------------
 import std.stdio;

 struct sum(A,B) {
      A a;
      B b;

      auto opAdd(T)(T a) { return .sum!(sum,T)(this,a); }
 }


 struct base {
      auto opAdd(T)(T a) { return .sum!(base,T)(this,a); }
 }

 void main() {
      base a,b,c;

      // first a few working examples
      writeln(typeid(a));       // base
      writeln(typeid(a+b));     // sum!(base,base).sum
      writeln(typeid(a+(b+c))); // sum!(base,sum!(base,base)).sum

      sum!(sum!(base,base),base) d;
      writeln(typeid(d));       // sum!(sum!(base,base),base).sum

      // the following produces
      //   Error: recursive template expansion for
      //   template argument sum!(base,base)
      writeln(typeid((a+b)+c)); // sum!(sum!(base,base),base).sum
 }

 ---------------


Well, first and foremost you should file the missing line number bug in  
bugzilla. As for the RTE itself, logically it shouldn't happen with this,  
but here are some work arounds.
1) Alter the type signature with a dummy var
struct sum(A,B,bool FLAG = false) {
      A a;
      B b;
      auto opAdd(T)(T a) { return sum!(sum!(A,B,!FLAG),T)(this,a); }
}
2) use a typedef
struct sum(A,B) {
      A a;
      B b;
private typedef sum __sum;
      auto opAdd(T)(T a) { return sum!(__sum,T)(this,a); }
}

3) You could also switch to using a generic expression template. i.e.  
op(string expression, string nextVar, T...) {}
Mar 01 2010