www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Imperative templates

reply Robert Clipsham <robert octarineparrot.com> writes:
So in several presentations given about D that I've seen there's a list 
of supported paradigms given which looks something like this:

  - Imperative
  - Metal
  - Object-oriented
  - RAII
  - Functional
  - Generic
  - Generative
  - Concurrent

(That list from 
http://assets.en.oreilly.com/1/event/45/The%20D%20Programming%20Languag
%20Presentation.pdf 
). But if this is the case, why do we not get this choice for template 
programming?

Currently templates have to be written in a functional manner, which is 
incredibly difficult if you're used to imperative programming, and I've 
found the code that it leads to is really difficult to maintain, even if 
it's well commented (this may not be the case for folk that are well 
versed in functional programming).

What I'd like to suggest is something like this:
----
/// Template to get every other type in a type tuple
template AlternateEven(T...)
{
     enum U = TypeTuple!();
     for (size_t i = 0; i < T.length; i++)
     {
         if ((i & 1) == 0)
         {
             U ~= T[i];
         }
     }
     alias U AlternateEven;
}
----

To do this currently you need something like:
----
template AlternateEven(T...)
{
     alias AlternateEvenImpl!(0, T) AlternateEven;
}

template AlternateEvenImpl(size_t i, T...) if ((i & 1) == 0)
{
     static if (i < T.length)
     {
         alias TypeTuple!(T[i], AlternateEvenImpl!(i + 1, T)) 
AlternateEvenImpl;
     }
     else
     {
         alias TypeTuple!() AlternateEvenImpl;
     }
}

template AlternateEvenImpl(size_t i, T...) if ((i & 1) != 0)
{
     static if (i < T.length)
     {
         alias AlternateEvenImpl!(i + 1, T) AlternateEvenImpl;
     }
     else
     {
         alias TypeTuple!() AlternateEvenImpl;
     }
}
----

Which is a lot more code, and a lot harder to understand at a quick 
glance. It gets even worse if you want to do something more 
complicated[1][2].

I don't think my example is the best example for a possible syntax, but 
that could be worked on. What does anyone else think?

[1] https://github.com/mrmonday/dmd/blob/js/dsrc/bind/util.d#L134
[2] 
https://github.com/mrmonday/serenity/blob/master/serenity/persister/Sqlite.d#L126

-- 
Robert
http://octarineparrot.com/
Jul 16 2011
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday 16 July 2011 16:58:25 Robert Clipsham wrote:
 So in several presentations given about D that I've seen there's a list
 of supported paradigms given which looks something like this:
 
   - Imperative
   - Metal
   - Object-oriented
   - RAII
   - Functional
   - Generic
   - Generative
   - Concurrent
 
 (That list from
 http://assets.en.oreilly.com/1/event/45/The%20D%20Programming%20Language%20P
 resentation.pdf ). But if this is the case, why do we not get this choice
 for template programming?
 
 Currently templates have to be written in a functional manner, which is
 incredibly difficult if you're used to imperative programming, and I've
 found the code that it leads to is really difficult to maintain, even if
 it's well commented (this may not be the case for folk that are well
 versed in functional programming).
 
 What I'd like to suggest is something like this:
 ----
 /// Template to get every other type in a type tuple
 template AlternateEven(T...)
 {
      enum U = TypeTuple!();
      for (size_t i = 0; i < T.length; i++)
      {
          if ((i & 1) == 0)
          {
              U ~= T[i];
          }
      }
      alias U AlternateEven;
 }
 ----
 
 To do this currently you need something like:
 ----
 template AlternateEven(T...)
 {
      alias AlternateEvenImpl!(0, T) AlternateEven;
 }
 
 template AlternateEvenImpl(size_t i, T...) if ((i & 1) == 0)
 {
      static if (i < T.length)
      {
          alias TypeTuple!(T[i], AlternateEvenImpl!(i + 1, T))
 AlternateEvenImpl;
      }
      else
      {
          alias TypeTuple!() AlternateEvenImpl;
      }
 }
 
 template AlternateEvenImpl(size_t i, T...) if ((i & 1) != 0)
 {
      static if (i < T.length)
      {
          alias AlternateEvenImpl!(i + 1, T) AlternateEvenImpl;
      }
      else
      {
          alias TypeTuple!() AlternateEvenImpl;
      }
 }
 ----
 
 Which is a lot more code, and a lot harder to understand at a quick
 glance. It gets even worse if you want to do something more
 complicated[1][2].
 
 I don't think my example is the best example for a possible syntax, but
 that could be worked on. What does anyone else think?
 
 [1] https://github.com/mrmonday/dmd/blob/js/dsrc/bind/util.d#L134
 [2]
 https://github.com/mrmonday/serenity/blob/master/serenity/persister/Sqlite.d
 #L126

You can actually do that a lot more simply than that: template AlternateEven(T...) { static if(T.length == 0) alias TypeTuple!() AlternateEven; else static if(T.length == 1) alias TypeTuple!(T[0]) AlternateEven; else alias TypeTuple!(T[0], AlternateEven!(T[2 .. $])) AlternateEven; } But it is true that template metaprogramming is functional in nature. In fact, I'd recommend reading this: http://bartoszmilewski.wordpress.com/2009/10/21/what-does-haskell-have-to-do- with-c/ It talks about how template metaprogramming in C++ is very much like Haskell, and even suggests essentially writing such templates as Haskell first (primarily because Haskell's syntax is so clean and C++'s template syntax is so insanely ugly). The basic concepts carry over to template metaprogramming in D, since it's essentially the same problem - we just have better syntax for it (so, designing your templates in Haskell first really shouldn't be necessary, but the concepts covered in that article would be good for you to go over). Now, as for implementing templates in an imperative style... I don't know how feasible that is. You're essentially asking for a CTFE function which processes types. Instead of the type system handling it all, you're trying to run arbitrary code which does it. It's not an altogether unreasonable request, but I'd expect it to be a hard problem to solve. It's probably something that should be considered, since it would make life much easier for those who aren't familiar with how to program with functional languages, but it would probably take a lot of work to do, so I wouldn't expect it anytime soon. Now, just for your general growth as a programmer, I'd suggest that you learn a functional language like Haskell. It definitely takes some getting use to, but there are some types of problems that are solved much more easily in a functional style, and having that in your programming toolbox would be of definite value to you (completely aside from the template metaprogramming issue). So, I think that your request makes good sense as long as it can be reasonably implemented, but it's likely to take a lot of work to do it, and there may be some underlying issue that I don't see which makes it completely infeasible. So, it may happen, but it's the sort of thing that's likely to be a D3 feature if it every happens. - Jonathan M Davis
Jul 16 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On Saturday 16 July 2011 16:58:25 Robert Clipsham wrote:
 So in several presentations given about D that I've seen there's a list
 of supported paradigms given which looks something like this:

   - Imperative
   - Metal
   - Object-oriented
   - RAII
   - Functional
   - Generic
   - Generative
   - Concurrent

 (That list from
 http://assets.en.oreilly.com/1/event/45/The%20D%20Programming%20Language%20P
 resentation.pdf ). But if this is the case, why do we not get this choice
 for template programming?

 Currently templates have to be written in a functional manner, which is
 incredibly difficult if you're used to imperative programming, and I've
 found the code that it leads to is really difficult to maintain, even if
 it's well commented (this may not be the case for folk that are well
 versed in functional programming).

 What I'd like to suggest is something like this:
 ----
 /// Template to get every other type in a type tuple
 template AlternateEven(T...)
 {
      enum U = TypeTuple!();
      for (size_t i = 0; i < T.length; i++)
      {
          if ((i & 1) == 0)
          {
              U ~= T[i];
          }
      }
      alias U AlternateEven;
 }
 ----

 To do this currently you need something like:
 ----
 template AlternateEven(T...)
 {
      alias AlternateEvenImpl!(0, T) AlternateEven;
 }

 template AlternateEvenImpl(size_t i, T...) if ((i & 1) == 0)
 {
      static if (i < T.length)
      {
          alias TypeTuple!(T[i], AlternateEvenImpl!(i + 1, T))
 AlternateEvenImpl;
      }
      else
      {
          alias TypeTuple!() AlternateEvenImpl;
      }
 }

 template AlternateEvenImpl(size_t i, T...) if ((i & 1) != 0)
 {
      static if (i < T.length)
      {
          alias AlternateEvenImpl!(i + 1, T) AlternateEvenImpl;
      }
      else
      {
          alias TypeTuple!() AlternateEvenImpl;
      }
 }
 ----

 Which is a lot more code, and a lot harder to understand at a quick
 glance. It gets even worse if you want to do something more
 complicated[1][2].

 I don't think my example is the best example for a possible syntax, but
 that could be worked on. What does anyone else think?

 [1] https://github.com/mrmonday/dmd/blob/js/dsrc/bind/util.d#L134
 [2]
 https://github.com/mrmonday/serenity/blob/master/serenity/persister/Sqlite.d
 #L126

You can actually compute most things in an imperative way using this idiom: enum x = {/*imperative code to compute value of x*/}(); When TypeTuples are involved, you can get away with mostly imperative code and careful workarounds for bugs and limitations of the compiler: import std.stdio, std.conv; import std.array, std.range; import std.algorithm; import std.typecons, std.typetuple; // Appender should be made ctfe-able soon... string[] ctfeSplit(string s,char d)/*insert sensible constraint here*/{ string[] r; size_t l=0; foreach(i,c;s) if(c==d) r ~= s[l..i], l=i+1; if(l<s.length) r~=s[l..$]; return r; } string[] stripParens(string[] s){ // modifying in-place segfaults the compiler... bug. // strips the parens around types stringof inserts, that make the result invalid D code... enhancement? string[] r; foreach(x;s) if(x[0]=='(') r~=x[1..$-1]; else r~=x; return r; } template TypeTupleToStringArray(T...){ enum TypeTupleToStringArray={ string s = T.stringof[6..$-1]; return stripParens(ctfeSplit(s,',')); }(); } alias TypeTupleToStringArray TTTSA; template SATTImpl(string s){ // only piece of somewhat functional code: needed to construct the TypeTuple enum a = mixin(s); pragma(msg,a); static if(a.length == 0) alias TypeTuple!() val; else static if(a[0][0]=='"') alias TypeTuple!(mixin(a[0]),SATTImpl!(a[1..$].stringof).val) val; // does not work with types... enhancement. else mixin("alias TypeTuple!("~a[0]~",SATTImpl!(a[1..$].stringof).val) val;"); } template StringArrayToTypeTuple(string s){ //have to compensate for restrictions on template parameter types...enhancement. alias SATTImpl!s.val StringArrayToTypeTuple; } alias StringArrayToTypeTuple SATTT; // finally, an imperative implementation of AlternateEven! template AlternateEvenImpl(T...){ enum U ={ string[] t=TTTSA!T, u; for (size_t i = 0; i < T.length; i++){ if(!(i & 1)) u ~= t[i]; } return u; }(); alias SATTT!(U.stringof) val; } template AlternateEven(T...){ alias AlternateEvenImpl!T.val AlternateEven; } void main(){ assert(AlternateEven!(1,2,int,double,2,"hello","hi\"hi\"").stringof == TypeTuple!(1,int,2,"hi\"hi\"").stringof); // have to use stringof... bug/enhancement. } But usually, well written functional code is both more concise and better maintainable than imperative code. Cheers, -Timon
Jul 16 2011
parent Robert Clipsham <robert octarineparrot.com> writes:
On 17/07/2011 01:36, Timon Gehr wrote:
 On Saturday 16 July 2011 16:58:25 Robert Clipsham wrote:
 So in several presentations given about D that I've seen there's a list
 of supported paradigms given which looks something like this:
    // List
 (That list from
 http://assets.en.oreilly.com/1/event/45/The%20D%20Programming%20Language%20P
 resentation.pdf ). But if this is the case, why do we not get this choice
 for template programming?

 Currently templates have to be written in a functional manner, which is
 incredibly difficult if you're used to imperative programming, and I've
 found the code that it leads to is really difficult to maintain, even if
 it's well commented (this may not be the case for folk that are well
 versed in functional programming).
 // Code
 Which is a lot more code, and a lot harder to understand at a quick
 glance. It gets even worse if you want to do something more
 complicated[1][2].

 I don't think my example is the best example for a possible syntax, but
 that could be worked on. What does anyone else think?

 [1] https://github.com/mrmonday/dmd/blob/js/dsrc/bind/util.d#L134
 [2]
 https://github.com/mrmonday/serenity/blob/master/serenity/persister/Sqlite.d
 #L126

You can actually compute most things in an imperative way using this idiom: enum x = {/*imperative code to compute value of x*/}(); When TypeTuples are involved, you can get away with mostly imperative code and careful workarounds for bugs and limitations of the compiler:

Have these been reported?
 // Code here

This is cool, if hacky! What's it like performance wise compared to the fully functional version?
 But usually, well written functional code is both more concise and better
 maintainable than imperative code.

Well that's debatable ;)
 Cheers,
 -Timon

-- Robert http://octarineparrot.com/
Jul 17 2011
prev sibling parent Robert Clipsham <robert octarineparrot.com> writes:
On 16/07/2011 23:36, Jonathan M Davis wrote:
 You can actually do that a lot more simply than that:

 template AlternateEven(T...)
 {
      static if(T.length  == 0)
          alias TypeTuple!() AlternateEven;
      else static if(T.length  == 1)
          alias TypeTuple!(T[0]) AlternateEven;
      else
          alias TypeTuple!(T[0], AlternateEven!(T[2 .. $])) AlternateEven;
 }

I didn't doubt there'd be a simpler way to write it, it was just a quick hack that I could use as an example. Didn't really wanna paste my huge real-world examples which I cited.
 But it is true that template metaprogramming is functional in nature. In fact,
 I'd recommend reading this:

 http://bartoszmilewski.wordpress.com/2009/10/21/what-does-haskell-have-to-do-
 with-c/

I'm subscribed to Bartosz's blog, I tend to find his posts are too long and in depth for me to read in the time I have available to me, which is unfortunate, as I'm interested in a lot of the things he posts.
 It talks about how template metaprogramming in C++ is very much like Haskell,
 and even suggests essentially writing such templates as Haskell first
 (primarily because Haskell's syntax is so clean and C++'s template syntax is
 so insanely ugly). The basic concepts carry over to template metaprogramming
 in D, since it's essentially the same problem - we just have better syntax for
 it (so, designing your templates in Haskell first really shouldn't be
 necessary, but the concepts covered in that article would be good for you to
 go over).

 Now, as for implementing templates in an imperative style... I don't know how
 feasible that is. You're essentially asking for a CTFE function which
 processes types. Instead of the type system handling it all, you're trying to
 run arbitrary code which does it. It's not an altogether unreasonable request,
 but I'd expect it to be a hard problem to solve. It's probably something that
 should be considered, since it would make life much easier for those who
 aren't familiar with how to program with functional languages, but it would
 probably take a lot of work to do, so I wouldn't expect it anytime soon.

That's exactly what I'm asking for - how can we claim the language supports all of the aforementioned idioms when you're forced to use one of them for operating on types? (Unless you use Timon's funky hack of course)
 Now, just for your general growth as a programmer, I'd suggest that you learn
 a functional language like Haskell. It definitely takes some getting use to,
 but there are some types of problems that are solved much more easily in a
 functional style, and having that in your programming toolbox would be of
 definite value to you (completely aside from the template metaprogramming
 issue).

I tried learning haskell once, I gave up due to time constraints and the lack of any projects to play with (I lose interest quick if there isn't code for me to play with/tweak to do something I wanna do). Having used it I frequently get annoyed with languages that don't have map/reduce, I don't doubt there's other cool idioms in there that I'd also get annoyed that other languages don't have too.
 So, I think that your request makes good sense as long as it can be reasonably
 implemented, but it's likely to take a lot of work to do it, and there may be
 some underlying issue that I don't see which makes it completely infeasible.
 So, it may happen, but it's the sort of thing that's likely to be a D3 feature
 if it every happens.

I wasn't really expecting anything to be done about it, just wondering if anyone else would find such a feature useful. Not that I'd complain if something like it was implemented! (I might even have a go at implementing it myself if someone came up with a reasonable syntax for it, the one I proposed has multiple issues with it).
 - Jonathan M Davis

-- Robert http://octarineparrot.com/
Jul 17 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday 17 July 2011 12:23:55 Robert Clipsham wrote:
 On 16/07/2011 23:36, Jonathan M Davis wrote:
 You can actually do that a lot more simply than that:
 
 template AlternateEven(T...)
 {
 
      static if(T.length  == 0)
      
          alias TypeTuple!() AlternateEven;
      
      else static if(T.length  == 1)
      
          alias TypeTuple!(T[0]) AlternateEven;
      
      else
      
          alias TypeTuple!(T[0], AlternateEven!(T[2 .. $]))
          AlternateEven;
 
 }

I didn't doubt there'd be a simpler way to write it, it was just a quick hack that I could use as an example. Didn't really wanna paste my huge real-world examples which I cited.
 But it is true that template metaprogramming is functional in nature. In
 fact, I'd recommend reading this:
 
 http://bartoszmilewski.wordpress.com/2009/10/21/what-does-haskell-have-t
 o-do- with-c/

I'm subscribed to Bartosz's blog, I tend to find his posts are too long and in depth for me to read in the time I have available to me, which is unfortunate, as I'm interested in a lot of the things he posts.
 It talks about how template metaprogramming in C++ is very much like
 Haskell, and even suggests essentially writing such templates as
 Haskell first (primarily because Haskell's syntax is so clean and C++'s
 template syntax is so insanely ugly). The basic concepts carry over to
 template metaprogramming in D, since it's essentially the same problem
 - we just have better syntax for it (so, designing your templates in
 Haskell first really shouldn't be necessary, but the concepts covered
 in that article would be good for you to go over).
 
 Now, as for implementing templates in an imperative style... I don't
 know how feasible that is. You're essentially asking for a CTFE
 function which processes types. Instead of the type system handling it
 all, you're trying to run arbitrary code which does it. It's not an
 altogether unreasonable request, but I'd expect it to be a hard problem
 to solve. It's probably something that should be considered, since it
 would make life much easier for those who aren't familiar with how to
 program with functional languages, but it would probably take a lot of
 work to do, so I wouldn't expect it anytime soon.

That's exactly what I'm asking for - how can we claim the language supports all of the aforementioned idioms when you're forced to use one of them for operating on types? (Unless you use Timon's funky hack of course)

We support all of the the mentioned paradigms. But that doesn't mean that they all apply to templates. For instance, would concurrent programming apply to templates? You can program using all of the list paradigms, but template metaprogramming is its own beast, and its essentially functional by nature. Just because you can use a particular paradigm in normal code doesn't mean that it needs to be useable in template metaprogramming or that we can't claim that we support it. I can see why you would want to be able to template metaprogramming imperatively, but just because you can't doesn't mean that D isn't properly supporting imperative programming. It just means that its template metaprogramming features can't be used in that way. - Jonathan M Davis
Jul 17 2011