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

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 --0015174a0ef2ff97140480bf86dc Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Mon, Mar 1, 2010 at 10:16, Norbert Ne= mec <span dir=3D"ltr">&lt;<a href=3D"mailto:Norbert nemec-online.de">Norber= t nemec-online.de</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> Is there any fundamental error in my thinking? Some simple misunderstanding= ? Some slightly different syntax to be used? Or is it simply an unnessessar= y restriction in the compiler that could easily be removed?<br></blockquote=

has the nice side-effect of simplfying the syntax (templated functions do = all the type deducing):<br><br>import std.stdio;<br><br>struct Sum(A,B) {<b= r> =A0=A0 A a;<br>=A0=A0 B b;<br><br>=A0=A0 auto opAdd(T)(T a) { return sum(th= is,a); }<br>}<br><br><br>struct Base {<br>=A0=A0 auto opAdd(T)(T a) { retur= n sum(this,a); }<br>}<br><br>Sum!(A,B) sum(A,B)(A a, B b) { return Sum!(A,B= )(a,b);}<br> Base!(A,B) base(A,B)(A a, B b) { return Base!(A,B)(a,b);}<br><br>void main(= ) {<br>=A0=A0 Base a,b,c;<br><br>=A0=A0 auto d =3D a+b;<br>=A0=A0 writeln(t= ypeof(e).stringof); // Sum!(Base, Base)<br>=A0=A0 auto e =3Dde+a;<br>=A0=A0= writeln(typeof(f).stringof); // Sum!(Sum!(Base, Base),Base)<br> =A0=A0 auto f =3D e+e+d;=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 // Look Ma,= no parenthesis<br>=A0=A0 writeln(typeof(g).stringof); // Sum!(Sum!(Sum!(Su= m!(Base,Base),Base), Sum!(Sum!(Base,Base),Base)),Sum!(Base,Base))<br>}<br>= =A0<br><br>Cheers,<br><br>=A0 Philippe<br> <br><br></div></div> --0015174a0ef2ff97140480bf86dc--
Mar 01 2010
parent 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
prev sibling next 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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0015174c3b0efb718f0480c0d89e
Content-Type: text/plain; charset=ISO-8859-1

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 --0015174c3b0efb718f0480c0d89e Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Mon, Mar 1, 2010 at 17:26, Norbert Ne= mec <span dir=3D"ltr">&lt;<a href=3D"mailto:Norbert nemec-online.de">Norber= t nemec-online.de</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;"> Thanks, Philippe, for the elegant workaround!<br></blockquote><div><br>De n= ada. I vaguely remembered being confronted by this one, but didn&#39;t know= it was a bug (my code wasn&#39;t as clear as yours). I now realize that my= coding in D is a least partially made of such tricks.<br> =A0<br></div><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> Still I would like to know the reason for my original failure, especially s= ince 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...<br> </blockquote><div><br>What bugs (!) me is that a+(b+c) didn&#39;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...<br><br>As for the l= ine numbers, yes it&#39;s hard and it&#39;s reason enough to put this on bu= gzilla. Maybe even as 2 different tickets.<br> <br>I remember having other incomplete error messages some days ago. I shou= ld strive to note them and put them on puremagic.<br><br>=A0 Philippe<br><b= r><br><br></div></div> --0015174c3b0efb718f0480c0d89e--
Mar 01 2010
prev sibling 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