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
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 reply 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
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